PROGRAMACION LINEAL

Unidad 2. Modelos de optimización determinísticos

PABLO CESAR GONZALEZ CAMACHO

GRUPO_100404_128

TUTOR
MICHAEL ALEXIS SANTOYA

UNIVERSIDAD NACIONAL ABIERTA Y ADISTANCIA

UNAD
BOGOTA D, C
Nov-19
Ejercicio 3.

La empresa Carbones de oriente debe ingresar a la empresa un requerimiento mínimo diario de carbón de 5000
carbón de alto volátil, 4000 kg de medio volátil y 3000 kg de bajo volátil para su debido proceso y trasformación.
entrada de estos se da de la siguiente manera: De la mina sur en un viaje se reciben 80 kg de alto volátil, 70 kg de
volátil y 65 kg de bajo volátil, de la mina norte en un viaje se reciben 60kg de alto volátil, 50 kg de medio volátil y
bajo volátil, de la mina central en un viaje se reciben 40kg de alto volátil, 30kg de medio volátil y 20 de bajo voláti
costo del trasporte de un viaje de cada mina es de 2500 dólares, 1500 dólares y 900 dólares, respectivamente. ¿C
viajes de cada mina se deben recibir a diario para suplir los requerimientos mínimos y generar el menor costo de
transporte? ¿Este ejercicio es maximización o de minimización?

Vajo volatil
Medio volatil 3000 kg
Alto volatil 5000 4000 kg Transporte
X3
kg X1 X2
Mina sur 80 kg 70 Kg 65 Kg $ 2,500
Mina norte 60 Kg 50 Kg 40 Kg $ 1,500
mina central 40 Kg 30 Kg 20 Kg $ 900

¿Este ejercicio es maximización o de minimización? Este ejercicio es de Minimización.

VARIABLES
X1 = Carbon de alto volatil
X2= Carbon de medio volatil
X3 = Carbon de bajo volatil

Funciòn objetivo

Cuántos viajes de cada mina se deben recibir a diario para suplir

los requerimientos mínimos y generar el menor costo de
transporte

Se lleva el modelo a su forma estándar. En nuestro ejemplo esto se logra agr

Z = 5000 X1 + 4000X2 + 3000X2 variables de exceso en cada una de las restricciones (3 primeras: S1, S2, S3,
respectivamente). Luego, se multiplica cada fila de las restricciones por -1 de
de disponer una solución básica inicial (infactible) en las variables de exceso S
S3. De esta forma se obtiene la siguiente tabla inicial.

RESTRICCIONES
Costo de viaje mina sur X1 X2 X3 S1
80X1 + 70X2+ 65X3 ≥ 2500 -80 -70 -65 -1
Costo de viaje mina norte -60 -50 -40 0
60X1 + 50X2 + 40X3 ≥ 1500 -40 -30 -20 0
Costo de viaje mina central 5000 4000 3000 0
40X1 + 30X2 +2 0X3 ≥ 900
Min -5000/-80, -4000/-70, -3000/-65

Función objetivo minimizar Z = 5000 X1 + 4000 X2 + 3000 X3

 nimo diario de carbón de 5000 kg de
ebido proceso y trasformación. La
en 80 kg de alto volátil, 70 kg de medio
volátil, 50 kg de medio volátil y 40kg de
medio volátil y 20 de bajo volátil, el
00 dólares, respectivamente. ¿Cuántos
mos y generar el menor costo de

uestro ejemplo esto se logra agregando se debe dejar a la variable A como básica y S1 como
ciones (3 primeras: S1, S2, S3, no básica. La tabla que resulta es la siguiente:
la de las restricciones por -1 de modo
ble) en las variables de exceso S1, S2 y
a inicial.

S2 S3 X1 X2 X3 S1
0 0 -2500 1 0 10 -1
-1 0 -1500 0 0 5 0
0 -1 -900 0 1 3/4 1/2
0 0 0 0 0 -15 -35
Continuar las iteraciones y siguiendo el mismo procedimiento hasta dis
de una solución básica factible. Luego de unas iteraciones se obtiene la
siguiente tabla final:

X1 X2 X3 S1
1 0 0
0 1 0
0 0 1
0 0 0
La solución óptima es Z = 126500
X1 = 8.5
X2 = 0
X3 = 28

a) ¿Cuál es el resultado de Z y a que corresponde?

b) ¿Cuál es el resultado de cada variable X1, X2, X3, X4, etc. y a qué corresponde?
c) ¿Qué significa el termino: “Precio sombra”?

¿Cuál es el resultado de Z y a que corresponde? El valor de Z es de 126500 y corresponde al valor total

implicito de los tipos de cabones de cada mina

¿Cuál es el resultado de cada variable X1, X2, X3, X4, etc. y a qué corresponde?
X1 = 8.5 Corresponde a la catidad de carbon que transporta cada mina
X2 = 0. Corresponde a la catidad de carbon que transporta cada mina
X3 = 28 Corresponde a la catidad de carbon que transporta cada mina
¿Qué significa el termino: “Precio sombra”?

Según hemos abordado en artículos anteriores el Precio Sombra de una restricción representa la tasa de cambio del valor ópti
del lado derecho de una restricción. Se entiende por “marginal” aquella modificación que no cambia la geometría del problem
óptima se puede encontrar a través de la resolución del sistema de ecuaciones al que da origen las restricciones activas origin
parámetro que estamos modificando). En este contexto el precio sombra puede ser un valor positivo, negativo o cero y en par
último caso en este artículo.
S2 S3
-1 0 700
0 0 150
0 1 45/5
1 1 0
ismo procedimiento hasta disponer
unas iteraciones se obtiene la

S2 S3
375
350
125/4
156250
 tasa de cambio del valor óptimo ante una modificación marginal
mbia la geometría del problema, es decir, que la nueva solución
as restricciones activas originales (previa actualización del
tivo, negativo o cero y en particular nos referiremos a este
Ejercicio 3.

La empresa Carbones de oriente debe ingresar a la empresa un requerimiento mínimo diario de carbón de 5000
volátil, 4000 kg de medio volátil y 3000 kg de bajo volátil para su debido proceso y trasformación. La entrada de e
siguiente manera: De la mina sur en un viaje se reciben 80 kg de alto volátil, 70 kg de medio volátil y 65 kg de baj
norte en un viaje se reciben 60kg de alto volátil, 50 kg de medio volátil y 40kg de bajo volátil, de la mina central e
reciben 40kg de alto volátil, 30kg de medio volátil y 20 de bajo volátil, el costo del trasporte de un viaje de cada m
dólares, 1500 dólares y 900 dólares, respectivamente. ¿Cuántos viajes de cada mina se deben recibir a diario par
requerimientos mínimos y generar el menor costo de transporte? ¿Este ejercicio es maximización o de minimizac

Medio Vajo volatil

Alto volatil volatil 4000 3000 kg
5000 kg kg Transporte
X3
X1 X2
Mina sur 80 kg 70 Kg 65 Kg $ 2,500
Mina norte 60 Kg 50 Kg 40 Kg $ 1,500
mina central 40 Kg 30 Kg 20 Kg $ 900

min 5000X1 + 4000X2 + 3000X3

80X1 + 70X2 + 65X3 >= 2500
60X1 + 50X2 + 40X3 >= 1500
40X1 + 30X2 + 20X3 >= 900

Para llevar el problema anterior a la forma estándar se requiere agregar 2 variables de

exceso no negativas para la restricción 1 y 2, que llamaremos respectivamente X4, X5 y X6
De esta forma el problema en su formato estándar queda definido por:

min 5000X1 + 4000X2 + 3000X3

80X1 + 70X2 + 65x3 -X4 = 2500
60X1 + 50X2 + 40X3 -X5 = 1500
40X1 + 30X2 + 20X3
Xi ≥ 0,i = 1,2,3,4,5,6

X1 X2 X3 X4 X5 X6
80 70 65 -1 0 0 2500
60 50 40 0 -1 0 1500
40 30 20 0 0 -1 900
5000 4000 3000 0 0 0 0
En consecuencia para formar la identidad podemos multiplicar por “-1” la fila 1 y 2, obten

X1 X2 X3 X4 X5 X6
-80 -70 -65 1 0 0 -2500
-60 -50 -40 0 1 0 -1500
-40 -30 -20 0 0 1 -900
5000 4000 3000 0 0 0 0

En la tabla anterior se tiene una solución básica (infactible en las variables primales), pero al
tener costos reducidos no negativos esto define una solución básica factible en el dual.

Ahora X4, X5 y X6 son variables básicas y adoptan los valores de -1 y -3/2, respectivamente,
lo que claramente no satisface las condiciones de no negatividad para las variables de
decisión, es decir, no corresponde a una solución básica factible.

min {-5000/-80; -4000/-80; -3000/-80} = 50

el cuociente mínimo se alcanza en la segunda columna asociada a la variable no básica X2,
por tanto dicha variable entra a la base.

En cada iteración del Método Simplex Dual se escoge un lado derecho con valor negativo,
identificando la respectiva variable básica primal, quien deja la base.
 nimo diario de carbón de 5000 kg de carbón de alto
y trasformación. La entrada de estos se da de la
g de medio volátil y 65 kg de bajo volátil, de la mina
bajo volátil, de la mina central en un viaje se
l trasporte de un viaje de cada mina es de 2500
ina se deben recibir a diario para suplir los
es maximización o de minimización?
r “-1” la fila 1 y 2, obteniendo lo siguiente:
Microsoft Excel 15.0 Informe de confidencialidad
Hoja de cálculo: [unidad 2 programacion lineal.xlsx]Analisis de sensibilidad
Informe creado: 01/12/19 20:18:00

Celdas de variables
Final Reducido Objetivo Permisible Permisible
Celda Nombre Valor Coste Coeficiente Aumentar Reducir
$I$24 >= X1 7.0833333333 0 5000 200 1769.2307692
$J$24 >= X2 0 125 4000 1E+030 125
$K$24 >= X3 30.833333333 0 3000 500 500

Restricciones
Final Sombra Restricción Permisible Permisible
Celda Nombre Valor Precio Lado derecho Aumentar Reducir
$I$28 Mina sur Lado izq. 2500 16.666666667 2500 425 1.136868E-13
$I$29 Mina norte Lado izq. 1658.3333333 0 1500 158.33333333 1E+030
$I$30 Mina central Lado izq. 900 0 900 0 1E+030
$I$28 Mina sur Lado izq. 2500 0 2500 1.136868E-13 1E+030
$I$29 Mina norte Lado izq. 1658.3333333 0 1500 158.33333333 1E+030
$I$30 Mina central Lado izq. 900 95.833333333 900 528.57142857 0

¿Cuál es el resultado de cada variable X1, X2, X3, X4, etc. y a qué corresponde??
X1 = 7,083 corresponde al valor de viaje de la mina sur
X2 = 0 corresponde al valor de viaje de la mina norte
X3 = 30,8 corresponde al valor de viaje de la mina central

b) ¿Cuál es el resultado de Z y a que corresponde?

El valor de Z es de 126500 y corresponde al valor total implicito de los tipos de cabones de cada mina

c) Si el ejercicio es de maximización: ¿Cuánto se incrementa o se reduce la ganancia por cada

unidad de recurso que se pudiera adquirir o suprimir?
El ejercicio es de minimizaciòn

d) Si el ejercicio es de minimización: ¿Cuánto se incrementa o se reduce el costo por cada unidad de recurso
que se pudiera adquirir o suprimir
Se incrementa de 200 a 500

Cuáles son los rangos en los cuales los coeficientes de la función objetivo pueden cambiar para que la
solución óptima se mantenga?

Objetivo
Coeficiente
5000
4000
 3000

Cuáles son los rangos en los cuales pueden adquirirse o reducirse recursos disponibles
Permisible Permisible
Aumentar Reducir
425 1.136868E-13
158.333333333333 1E+030
0 1E+030
1.13686837721616E-13 1E+030
158.333333333333 1E+030
528.571428571429 0

Paso 4: Revisar el ejercicio original desarrollado por el método simplex algebraico en el paso 2 de la guía anterior
correspondiente a la tarea 1 y realizar las siguientes actividades:
esponde??
sos disponibles

la guía anterior
Microsoft Excel 15.0 Informe de respuestas
Hoja de cálculo: [unidad 2 programacion lineal.xlsx]Analisis de sensibilidad
Informe creado: 01/12/19 20:46:11
Resultado: Solver se detuvo a solicitud del usuario.
Motor de Solver
Motor: Simplex LP
Tiempo de la solución: 30,953 segundos.
Iteraciones: 1 Subproblemas: 0
Opciones de Solver
Tiempo máximo Ilimitado, Iteraciones Ilimitado, Precision 0,000001, Mostrar resultados de iteraciones
Máximo de subproblemas Ilimitado, Máximo de soluciones de enteros Ilimitado, Tolerancia de enteros 1%, Asumir no nega

Celda objetivo (Mín)

Celda Nombre Valor original Valor final
$J$22 Z = 0 112500

Celdas de variables
Celda Nombre Valor original Valor final Entero
$I$24 >= X1 0 22.5 Continuar
$J$24 >= X2 0 0 Continuar
$K$24 >= X3 0 0 Continuar

Restricciones
Celda Nombre Valor de la celda Fórmula Estado Demora
$I$28 Mina sur Lado izq. 1575 $I$28>=$K$28 Vinculante 0
$I$29 Mina norte Lado izq. 1350 $I$29>=$K$29 Vinculante 0
$I$30 Mina central Lado izq. 900 $I$30>=$K$30 Vinculante 0
e enteros 1%, Asumir no negativo
Ejercicio 3.

La empresa Carbones de oriente debe ingresar a la empresa un requerimiento mínimo diario de carbón de 50
4000 kg de medio volátil y 3000 kg de bajo volátil para su debido proceso y trasformación. La entrada de esto
la mina sur en un viaje se reciben 80 kg de alto volátil, 70 kg de medio volátil y 65 kg de bajo volátil, de la min
60kg de alto volátil, 50 kg de medio volátil y 40kg de bajo volátil, de la mina central en un viaje se reciben 40k
volátil y 20 de bajo volátil, el costo del trasporte de un viaje de cada mina es de 2500 dólares, 1500 dólares y
¿Cuántos viajes de cada mina se deben recibir a diario para suplir los requerimientos mínimos y generar el m
ejercicio es maximización o de minimización?

Funciòn objetivo a minimizar

min Z = 5000X1 + 4000X2 + 3000X3

Restricciones
80X1 + 70X2 + 65X3 ≥ 2500
60X1 + 50X2 + 40X3 ≥ 1500
40X2 + 30X2 + 20X3 ≥ 900
X1,X2,X3 ≥ 0

X1 X2 X3 Costos
Mina sur 70 60 65 >= 2500
Mina norte 60 50 40 >= 1500
Mina central 40 30 20 >= 900
 to mínimo diario de carbón de 5000 kg de carbón de alto volátil,
trasformación. La entrada de estos se da de la siguiente manera: De
l y 65 kg de bajo volátil, de la mina norte en un viaje se reciben
central en un viaje se reciben 40kg de alto volátil, 30kg de medio
de 2500 dólares, 1500 dólares y 900 dólares, respectivamente.
imientos mínimos y generar el menor costo de transporte? ¿Este

F.Objetivo
Z= 112500
X1 X2 X3
22.5 0 0
5000 4000 3000

Lado izq. Signo Lado der

Mina sur 1575 >= 2500
Mina norte 1350 >= 1500
Mina central 900 >= 900
Microsoft Excel 15.0 Informe de confidencialidad
Hoja de cálculo: [unidad 2 programacion lineal.xlsx]Analisis de sensibilidad
Informe creado: 01/12/19 19:33:12

Celdas de variables
Final Reducido Objetivo Permisible Permisible
Celda Nombre Valor Coste Coeficiente Aumentar Reducir
$I$24 >= X1 7.0833333333 0 5000 200 1769.2307692
$J$24 >= X2 0 125 4000 1E+030 125
$K$24 >= X3 30.833333333 0 3000 500 500

Restricciones
Final Sombra Restricción Permisible Permisible
Celda Nombre Valor Precio Lado derecho Aumentar Reducir
$I$28 Mina sur Lado izq. 2500 16.666666667 2500 425 475
$I$29 Mina norte Lado izq. 1658.3333333 0 1500 158.33333333 1E+030
$I$30 Mina central Lado izq. 900 95.833333333 900 528.57142857 130.76923077