Taller 5

Universidad Nacional de Colombia

Ingeniería Industrial
Optimización
David Andrés Hoyos Rondón
Camilo Castañeda Forero
Duver Andrés Herrera Torres

Todos los problemas se resolvieron mediante el software Matlab. Para probar la solución
se debe colocar el contenido de la sección de código de cada problema en la consola del
programa.

Problema 1. Para los problemas siguientes:

● Formular el PL en forma estándar.
● Formular el problema en forma básica .
● Resolver utilizando el Método Simplex revisado.
● Resolver utilizando el Software Matlab.
a)

Formulación del PL en forma estándar:

Para poder llevar este problema a su forma estándar, debemos cambiar X3 por X3’- X3’’ y
agregar las variables de holgura y exceso, obteniendo las siguientes ecuaciones.

MIN Z = x1 + 4x2 -x4

-2x1 + 2x2 - x3’ + x3’’ + 2x4 + s1 = 2 2x1 +
3x2 + 2x3’ -2x3’’ - 2x4 = 4
x1 - 3x3’ + 3x3’’ + x4 - s2 = 2

x1, x2, x3’, x3’’, x4 >= 0

b)

Forma Estándar:

x1 + 2x2 + x3 - x4 + x5 =4
2x1 -x3 - x6 + x7 =3
x2 + x3 + x8 = 2

Forma básica:
x1 + 2x2 + x3 - x4 + x5 +x9 =4
2x1 -x3 - x6 + x7 +x10 =3
x2 + x3 + x8 + x11 =2
Resolviendo con simplex revisado:
Vector de coeficientes = (-1,-2,3)
Matriz de coeficientes = [1,2,1,-4,1,0,0,0;
2,0,-1,0,0,-1,1,0;
0,1,1,0,0,0,0,1]
B = B = [1 0 0
−1

010
0 0 1]
b = [4
3
2]

variables basicas = [x9

x10
x11
]

XB = B−1 * b =[4
3
2
]
nuevo vector C = [1,2,-3]
entra x3
4/ 1 = 4; 3/-1 no se tiene en cuenta, 2/1 = 2, asi que sale x11

vector epsilon = [2
3/2
1]

aca la solucion es no acotada luego no se puede encontrar solución factible al problema

Solucion Matlab:
>> C = [-1,-2,1];
>> A = [1,2,1;2,0,-1;0,1,1];
>> B = [4,3,2];
>> lb = [];
>> ub = [];
>> Tipo_Res = "LLU";
>> Tipo_Var = "CCC";
>> Max = 1;
>> [valor_variables, valor_funcion, status] = glpk (C, A, B, lb, ub, Tipo_Res, Tipo_Var,
Max)
glp_simplex: unable to recover undefined or non-optimal
solution valor_variables =

NA
NA
NA

valor_funcion = NA
status = 11
>>
c)
Formulación del PL en forma estándar:
Para poder llevar este problema a su forma estándar, debemos cambiar X3 por X31-X32,
agregar las variables de holgura y multiplicar las restricciones 2 y 3 por -1, obteniendo
las siguientes ecuaciones.

MAX Z = 4x1 + 5x2 + 7x31 -7x32 -x4

x1 + x2 + 2x31 - 2x32 - x4 - s1 = 1
-2x1 + 6x2 - 3x31 + 3x32 - x4 - s2 = 3
2x1 - 4x2 - 2x31 + 2x32 - 2x4 = 5

x1, x2, x31, x32, x4 >= 0

Formular el problema en forma
básica:

Para poder llevar este problema a su forma básica, debemos cambiar X3 por X31-X32,
agregar las variables de holgura y artificiales, obteniendo las siguientes ecuaciones.

MAX Z = 4x1 + 5x2 + 7x31 -7x32 -x4

x1 + x2 + 2x31 - 2x32 - x4 + A1 - s1 = 1
2x1 - 6x2 + 3x31 - 3x32 + x4 + s2 = -3
-2x1 + 4x2 + 2x31 - 2x32 + 2x4 + A2 = -5

x1, x2, x31, x32, x4 >= 0

Resolución utilizando el Método Simplex revisado:

Primero debemos cambiar X3 por X31-X32 y dividir la restricción 3 que es una igualdad
en 2 desigualdades, obteniendo las siguientes ecuaciones.

MAX Z = 4x1 + 5x2 + 7x31 -7x32 -x4

x1 + x2 + 2x31 - 2x32 - x4 >= 1
2x1 - 6x2 + 3x31 - 3x32 + x4 <= -3
-2x1 + 4x2 + 2x31 - 2x32 + 2x4 >= -5
-2x1 + 4x2 + 2x31 - 2x32 + 2x4 <= -5

x1, x2, x31, x32, x4 >= 0

Ya que el método Simplex revisado nos pide que Ax <= b, procedemos a
multiplicar la restricción 1 y 3 por -1, luego agregamos las variables de holgura,
quedando el siguiente sistema.
MAX Z = 4x1 + 5x2 + 7x31 -7x32 -x4

-x1 - x2 - 2x31 + 2x32 + x4 + s1 <= -1

2x1 - 6x2 + 3x31 - 3x32 + x4 + s2 <= -3
2x1 - 4x2 - 2x31 + 2x32 - 2x4 + s3 <= 5
-2x1 + 4x2 + 2x31 - 2x32 + 2x4 + s4 <= -5
Aquí ya podemos comenzar con el método Simplex revisado, para lo cual definiremos las
matrices que usaremos.

Cj= 4 5 7 -7 -1
-1 -1 -2 2 1
Aj= 2 -6 3 -3 1
2 -4 -2 2 -2
-2 4 2 -2 2

CB= 0 0 0 0 0
1 0 0 0 -1 S1
B= 0 1 0 0 b= -3 Xb= S2
0 0 1 0 5 S3
0 0 0 1 -5 S3

Ahora procedemos a calcular qué variable entra a Xb, por medio de la siguiente fórmula.
Zj-Cj=(Cb)(B^-1)(Aj)-Cj *(1)
Al realizar las operaciones necesarias, obtenemos en vector [ -4 -5 -7 7 1], del cual podemos
deducir que la variable que entra en Xb es X31, ahora debemos decidir que variable sale de la
base por medio del siguiente cálculo.

*(2)

De donde escogemos el resultado mínimo, del cual obtenemos que la variable saliente es S4,
luego de esto procedemos a actualizar nuestras matrices.

CB= 0 0 0 3,5 -17,5

1 0 0 1 -6
B^-1= 0 1 0 -1,5 b= 4,5
0 0 1 1 0
0 0 0 0,5 -2,5

Repetimos el cálculo descrito en (1) para verificar que variable sale, obtenemos el vector [-11 9
0 0 8], por lo que la variable que entrará a Xb es X1, luego realizamos el cálculo de
(2) y encontramos que la variable que sale de Xb es S2, procedemos a actualizar nuestras
matrices.
(3)
CB= 0 2,2 0 0,2 -7,6

1 0,6 0 0,1 -3,3

B^-1= 0 0,2 0 -0,3 b= 0,9
0 0 1 1 0
0 0,2 0 0,2 -1,6

Repetimos el cálculo descrito en (1) para verificar que variable sale, obtenemos el vector [0
-17.4 0 0 3.6], por lo que la variable que entrará a Xb es X2, luego realizamos el cálculo de (2),
pero en esta ocasion observamos que ningún Yi cumple la condición de ser mayor que cero, por
lo que no podemos determinar la variable de salida de Xb, se concluye que no existe solución
factible para el problema, lo que coincide con lo encontrado en Matlab.

Resolución en Matlab:
% Matriz de coeficientes de Zmax
%Zmax = 4*X1+5*X2+7*X3-1*X4 C = [4.0
5.0 7.0 -1.0];
% Matriz de variables presentes en las restricciones A = [1 1 1 -1;
2 -6 3 1;
-2 4 2 2];
% Matriz de resultado de las restricciones B = [1 -3 -
5];
% Cota inferior de las variables lb = [0 0
-inf 0]';
% Cota superior de las variables ub = [];
% Tipo de restricciones S=igual, L=mayor, U= menor Tipo_Res =
"LUS";
% Tipo de variables
Tipo_Var = "CCCC";
% Tipo de problema dir =
-1;
% Sol. problema transporte
[valor_variables, valor_funcion, status] = glpk (C, A, B, lb, ub, Tipo_Res, Tipo_Var, dir);
valor_variables=valor_variables';
valor_variables
valor_funcion
status

Resultado
glp_simplex: unable to recover undefined or non-optimal solution valor_variables
=

NA NA NA NA
valor_funcion = NA
status = 11
Problema 2. Resolver por el Método Simplex revisado.

Maximizar 3x1 + 2x2 + X3 + X4

Sujeto a 8x1+ 3x2 + 4x3 + x4 <= 7
2x1 + x2 + X3 + 5x4 <= 3
x1 + 4x2 + 5x3 + 2x4 <= 8

x1, x2 , x3, x4 >= 0.

Primero, pasamos el sistema a su forma básica, agregando variables de holgura quedando

el siguiente sistema.

MAX Z = 4x1 + 5x2 + 7x31 -7x32 -x4

-x1 - x2 - 2x31 + 2x32 + x4 + s1 <= -1
2x1 - 6x2 + 3x31 - 3x32 + x4 + s2 <= -3
2x1 - 4x2 - 2x31 + 2x32 - 2x4 + s3 <= 5
-2x1 + 4x2 + 2x31 - 2x32 + 2x4 + s4 <= -5
Problema 3.

Una compañía desea utilizar la madera de uno de sus bosques en su aserradero o su

planta de celulosa. Esto significa que la madera puede convertirse en cualquier
combinación de tablas de madera aserrada y celulosa. Para producir 1000 pies de tablas
de madera hace falta 1000 pies de Pino tipo A o 3000 pies de Pino tipo B. Para producir
1000 Kg. de celulosa hace falta 2000 pies de Pino tipo A o 4000 pies de Pino tipo B. Este
bosque cuenta con 32000 pies de Pino tipo A y 72000 pies de Pino tipo B. Compromisos
de venta nos obligan a producir al menos 4000 pies de tablas de madera y 12000 Kg. de
celulosa. Los beneficios son $40 por cada 1000 pies de tablas de madera y $60 por cada
1000 Kg. de celulosa.
(a) Plantear el problema lineal y resolverlo mediante el método simplex Revisado.
Expresar la solución en términos económicos.
(b) Verificar gráficamente la solución.
(c) Expresar el problema dual asociado e interpretarlo económicamente.
(d) Suponga que es posible adquirir un bosque adyacente con 10000 pies de Pino tipo
A.
¿Debemos adquirirlo? ¿Hasta cuanto estaremos dispuestos a pagar por este bosque?
(e) Suponga que el beneficio por las tablas de madera cambia a $40+w. ¿Para qué
valores de w la base actual permanecerá óptima?

Variables:
x1: Cantidad de tablas de madera en 1000 pies.
x2: Cantidad de celulosa en 1000 Kg.

MAX Z = 40x1 + 60x2

S.A:
1000x1 + 2000x2 ≤ 32000 3200
3000x1 + 4000x2 ≤ 72000
x1 ≤ 4
x2 ≤ 12

x1,x2 ≥ 0

Se pasa el problema a la forma estandar y básica, agregando las variables de holgura

x3,x4,x5 y x6
1000x1 + 2000x2 + x3=32000
3000x1 + 4000x2 + x4= 72000
x1 + x5 = 4
x2 + x6 = 12

x1,x2,x3,x4,x5,x6 ≥ 0

Cj= 40 60 0 0 0 0
1000 2000 1 0 0 0
Aj= 3000 4000 0 1 0 0
1 0 0 0 1 0
0 1 0 0 0 1

CB= 0 0 0 0 0
1 0 0 0 32000 x3
B= 0 1 0 0 b= 72000 Xb = x4
0 0 1 0 4 x5
0 0 0 1 12 x6

Ahora procedemos a calcular qué variable entra a Xb, por medio de la siguiente fórmula.
Zj-Cj=(Cb)(B^-1)(Aj-Cj)
Al realizar las operaciones necesarias, obtenemos en vector [ -40 -60 ], del cual podemos
deducir que la variable que entra en Xb es X2, ahora debemos decidir qué variable sale de la
base por medio del siguiente cálculo.

De donde escogemos el resultado mínimo, del cual obtenemos que la variable saliente es x6,
luego de esto procedemos a actualizar nuestras matrices:

CB= 0 0 0 60 -17,5
1 0 0 -4000 -16000
B^-1= 0 1 0 -2000 b= 48000
0 0 1 0 4
0 0 0 1 12

Repetimos el cálculo descrito antes para verificar que variable sale, obtenemos el vector [-40,
60], por lo que la variable que entrará a Xb es X1, luego realizamos el cálculo para determinar la
variable que sale de la base y encontramos que la variable que sale de Xb es x5, procedemos a
actualizar nuestras matrices.
CB= 0 2,2 0 0,2 -7,6

1 0 0 -4000 -3,3
B^-1= 0 1 0 -2000 b= 0,9

0 0 1 0 0

0 2 0 1 -1,6

Repetimos el cálculo descrito en (1) para verificar que variable sale, obtenemos el vector [-40,
60], por lo que la variable que entrará a Xb es X1, luego realizamos el segundo cálculo para
determinar la variable saliente de la base, pero en esta ocasion observamos que ningún Yi
cumple la condición de ser mayor que cero, por lo que no podemos determinar la variable de
salida de Xb, se concluye que no existe solución factible para el problema, lo que coincide con lo
encontrado en Matlab.
Problema 4.

Dorian Auto fabrica autos y camionetas de lujo para hombres y mujeres. La empresa
desea hacer avisos de 1 minuto en programas de humor y en partidos de fútbol. Cada
aviso en un programa de humor cuesta $50000 y es visto por 7 millones de mujeres y 2
millones de hombres. Cada aviso en un partido de fútbol cuesta $100000 y es visto por 2
millones de mujeres y 12 millones de hombres. Cómo puede hacer Dorian para hacer
llegar su aviso a 28 millones de mujeres y 24 millones de hombres con el menor costo?
(a) Resuelva mediante simplex revisado el problema dado.
(b) Basándose en la última tabla del simplex calcule la última tabla del dual.
(c) Plantee el modelo matemático del problema dual e interprételo económicamente.
(d) Encuentre el intervalo de los valores del costo de un comercial en programas de
humor, para los cuales la base permanece óptima.
(e) Encuentre el intervalo de los valores del costo de un comercial en partidos de fútbol,
para los cuales la base permanece óptima.
(f) Encuentre el intervalo de los valores de la cantidad de hombres y mujeres a los
cuales hacer llegar el aviso para los cuales la base permanece óptima.
(g) Encuentre los precios sombra de cada restricción. Qué significan?

Variables:
x1: Cantidad de mujeres medida en
millones x2: Cantidad de hombres medida
en millones

MIN Z = 50000x1 +
100000x2 S.A:
7x1 + 2x2 ≥ 28
2x1 + 12x2 ≥ 24

x1,x2 ≥ 0

estandarizamos las
fórmulas: 7x1 + 2x2 + x3 +
x4 = 28
2x1 + 12x2 + x5 + x6 = 24
donde x3 y x5 son variables de exceso y x4 y x6 son variables artificiales

Z x1 x2 x3 x4 x5 x6 L.D
Z 1 -50000 -100000 0 0 0 0 0
x4 0 7 2 1 1 0 0 28
x6 0 2 12 0 0 1 1 29
la última tabla simplex es la siguiente

Z x1 x2 x3 x4 x5 x6 L.D
Z 1 300000 0 -500000 0 500000 0 140000
x4 0 40 0 6 1 6 -1 144
x2 0 7/2 1 1/2 0 1/2 0 14
es no cotada

b)

Cj Xj Bj y1 y2 x3 x4

28 x1 5000 1 0 3/20 -1/40

24 x2 7000 0 1 -1/40 7/10

820000 0 0 18/45 0

c)
y1: dinero para comerciales en los programas de
humor y2: dinero para comerciales en los
programas de futbol

MAX Z = 28y1 +24y2

s.a
7y1 + 2y2 ≤ 50000
2y1 + 12y2 ≤ 100000

acá se busca maximizar la ganancia de los 28 millones de espectadores hombres y los 24

millones de las espectadoras mujeres, y con las restricciones buscamos minimizar los
costos de pagar tiempo al aire de los comerciales

d) C1 = 50000
C1 = Cub * B−1 * aj − c1
= [50000 + Δ, ][3/20, -¼; -1/40, 7/18][7
100000 2] - 5000

= [3 Δ /20 + 5000, 7000- Δ /40][7

2] = Δ

x3 = Cvb * B−1 * aj = [3 Δ /20 + 5000, 7000- Δ /40][1

0]
= 3 Δ /20 + 5000

x4 = Cub * B−1 * aj = [3 Δ /20 + 5000, 7000- Δ /40][0

1]
= 7000- Δ /40
 Δ ≥ 0 , Δ ≥− 100000 , Δ ≤ 28000 , 0 ≤ Δ ≤ 28000

5000 ≤ Δ ≤ 780000

e) C2 = 100000
−1
C2 = Cub * B
= [50000 , 100000 Δ ][3/20, -¼; -1/40, 7/18][2
+ 12] -
100000

= [5000 - Δ /40 , 7500- 7Δ /80][2

12] - 100000 = Δ

x3 = Cvb * B−1 * aj = [5000 - Δ /40 , 7500- 7Δ

/80][1 0]
= 5000 - Δ /40
−1
x4 = Cub *B * aj = [5000 - Δ /40 , 7500- 7Δ
/80][0 1]
= 7500+ 7Δ /80

Δ ≥ 0 , Δ ≥− 600000/7 , Δ ≤ 200000 , 0 ≤ Δ ≤ 200000

100000 ≤ C2 ≤ 300000

f)
X b = B−1 * b

X b = [3/20, -1/40; -1/40, 7/80][28+ Δ ;24]

= [12/5 + 3 Δ /20; 7/5 - Δ/40 ]

− 24 ≤ Δ ≤ 50

4 ≤ b1 ≤ 78

Xb = [3/20, -1/40; -1/40, 7/80][28;24+ Δ ]

= [18/5 - Δ /40; 7/5 + 7Δ/80 ]

− 16 ≤ Δ ≤ 144

8 ≤ Δ ≤ 168

g)
5000 es lo que se debe pagar si se quiere que un millón más de mujeres vean el
anuncio 7500 es lo que se debe pagar si se quiere que un millón más de hombres
vean el anuncio

Problema 6.

Considere el siguiente problema:

Minimizar z = 2x1 + 15x2 + 5x3 + 6x4
Sujeto a
x1 + 6x2 + 3x3 + x4 >= 2
-2x1 + 5x2 – 4x3 + 3x4 <= -3

x1, x2, x3, x4 >= 0

a. Escribir el problema dual.

Primero pasamos a ecuaciones estrictas

MIN Z = 2x1 + 15x2 +5x3 +6x4 +0x5 +0x6

x1 + 6x2 + 3x3 +x4 - x5 + 0x6 = 2

-2x1 + 5x2 -4x3+3x4 +0x5 + x6 = -3

generamos el problema dual

MAX W = 2y1 -3y2

sujeto a
y1 - 2y2 ≤ 2
6y1 + 5y2 ≤ 15
3y1 - 4y2 ≤5
y1 + 3y2≤ 6
-y1 + 0y2 ≤0
0y1 + y2≤ 0
b. Resolver el dual geométricamente.

el único punto que cumple con las restricciones es el Punto H con un valor de
1.66666 para obtener un Z = 3.3333333

c. Utilizar la información acerca del problema dual y el teorema de la

dualidad para resolver el problema primal.

Dado que ya resolvimos el problema dual, la solución a este acota por el lado
izquierdo la solución del problema primal, el valor objetivo del problema de
maximización es menor o igual al valor objetivo del problema de minimización

Problema 9.

Resolver el problema por el método Simplex dual

Maximizar z = 2x1 + 6x2
Sujeto a x1 + x2 >= 3
X1 + 2x2 <= 3

X1, x2 >= 0
Primero llevamos la restricción 1 a la forma canónica multiplicándola por -1, para poder
aplicar el método Simplex dual, ya que el profesor nos indicó en la clase que el punto
debía ser resuelto de forma directa por este método.
Maximizar z = 2x1 + 6x2
Sujeto a -x1 - x2 <= -3
X1 + 2x2 <= 3

X1, x2 >= 0
Agregamos las variables de holgura.
Maximizar z = 2x1 + 6x2 -> z - 2x1 - 6x2 = 0
Sujeto a -x1 - x2 + s1 <= -3
X1 + 2x2 + s2 <= 3

X1, x2 >= 0
En este momento ya podemos pasar las ecuaciones a un tabloide.
 X1 X2 S1 S2 L.D
Z -2 -6 0 0 0
S1 -1 -1 1 0 -3
S2 1 2 0 1 3

Se observa que respecto al algoritmo del método Dual, es la variable S1 la que debe salir
de la base, pero no encontramos una variable que cumpla los parámetros de entrada,
por lo que el problema no puede ser solucionado por el método Simplex Dual.