U A BC niversidad utónoma de aja alifornia

Métodos Cuantitativos (11859)

1.5.
Lecturas
© [email protected] +526461528229;65050 Cubículo 321
 (414) 1.5.2. 2
1.5.2.
Programación Lineal
En este tema englobamos las técnicas y métodos usados para lograr la optimización de la función
objetivo, manteniéndose siempre dentro de la factibilidad que dictaminan restricciones y
condiciones.
Se limita a modelos matemáticos lineales constituidos por sistemas de relaciones de primer orden
y grado con dos o más variables.
Cuando hay el mismo número de relaciones linealmente independientes1 que, de variables, solo
existe una solución. Es imposible tener más relaciones linealmente independientes que el número
de variables. Si hay más relaciones linealmente independientes que el número de variables, la
solución es única descartando cualquiera de las ecuaciones que estén de más. Si hay un número
menor de relaciones que de variables, el número de soluciones es infinito, pero en ese caso se puede
buscar la mejor solución, mediante el arbitrio de una función de utilidades (costos) que permita
discernir cual es el valor de cada solución, y mediante esta valoración encontrar el óptimo.
1.5.2.1.
En una dimensión
El problema es trivial, sería segmento de la recta numérica, coloreado gradualmente de blanco
(máximo) a negro (mínimo).

Máximo Mínimo

1
Las relaciones linealmente independientes son aquellas que ninguna de ellas se puede generar de las otras por
operaciones de multiplicación por alguna variable y la suma de ellas. Su número es iguakl al número de bvariables.

© [email protected] Lecturas 2 Programación lineal

 (414) 1.5.2. 3
1.5.2.2.
En dos dimensiones
Las restricciones configuran relaciones, que forman un polígono (ilustrado a continuación en
el primer recuadro), en el que cada vértice es la intersección de dos rectas que representan la
utilización al máximo de ese recurso.
La iluminación representa la utilidad, que a continuación se ilustra en los siguientes recuadros,
haciendo la utilidad el eje z.

© [email protected] Lecturas 2 Programación lineal

 (414) 1.5.2. 4
1.5.2.3.
En 3 dimensiones

La limitación de nuestra conciencia para

Las restricciones son planos recortados para ubicar más de tres dimensiones impide
configurar las caras de un poliedro irregular continuar con la imagen geométrica. Aun en
en el que la intersección de dos caras es una tres dimensiones solo se podría visualizar si el
recta llamada arista, y la intersección de tres máximo se encontrará en una cara, que es el
restricciones es un vértice. Las utilidades se caso de los modelos lineales, pero si este es un
exhiben como un color. La gama “jet” del punto interno del poliedro de soluciones, no
SCILAB, van desde el azul profundo, para la sería factible visualizarlo sin tomografía2.
mínima utilidad, hasta el marrón, para la
máxima ganancia. A continuación, se
muestran varias vistas de esta figura en otros
“mapas de colores”

Con objeto de ilustrar los métodos y técnicas

empezaremos con dos variables e
implementaremos un método gráfico, que, si
bien es impreciso, es muy ilustrativo. El
motivo de usar dos dimensiones es el de
ubicar la utilidad como tercera dimensión y así
poder demostrar la solución como una
construcción geométrica.

2Una visión de cómo se vería un cuerpo si se cortara en secciones planas. Ejemplo:

https://youtube.com/watch?v=z9xQqlNM20U

© [email protected] Lecturas 2 Programación lineal

 UABC (414) Métodos Cuantitativos 5
(11859) Raúl Espejo Rodarte(11950)1.5.2.

1.5.2.4.
Caso Ejemplar3
Se tiene un taller en el que se producen Mesas y Sillas
(Variables independientes: Cantidad de Mesas y cantidad de Sillas)
Los Recursos, en una base de tiempos diaria, con que cuenta son:
• Mano de Obra dos empleados a tiempo completo y dos empleados a medio tiempo:
___ 2 * 8hh +2 * 4hh = 16hh +8hh = 24hh
• Materiales se cuenta diariamente con 24 hojas de triplay
• Equipo Hay 15 puestos de trabajo.
Las restricciones son:
Cada Mesa se lleva 1hh, 2 hojas de triplay y requiere de 1 banco de trabajo.
Cada Silla ocupa 2hh, 1 hoja de triplay y necesita de 1 banco de trabajo.
Recursos
Productos
Mano de Obra <=24 Materiales <=24 Equipo <=15
Mesas 1 hh 2 hoja 1 banco
Sillas 2 hh 1 hoja 1 banco
Restricción 1M + 2S <= 24 2M + 1S <= 24 1M + 1S <= 15
El costo al público es de $15por cada Mesa y de $9 por cada Silla
El costo de producción $12por cada Mesa y de $5 por cada Sillas
Mesas Sillas La Utilidad neta es de
Costo al Publico 15 $/Mesa 9 $/silla $3*Mesas + $4*Sillas
Costo de Producción 12 $/Mesa 5 $/silla
Utilidad neta 3 $/Mesa 4 $/silla
Formulemos: Función Objetivo:
maximizar 3*M + 4*S = Z4 [$]
Sujeto a las restricciones:
Ninguna de las variables puede tomar valores negativos: 1*M ≥ 0. [Mesas]
1*S ≥ 0. [Sillas]
Mano de obra 1*M + 2*S ≤ 24 [Horas Hombre]
Materiales 2*M + 1*S ≤ 24 [Hojas de Triplay]
Equipo 1*M + 1*S ≤ 15 [Bancos de Trabajo]

3
Siempre usaremos este ejemplo para poder ilustrar prácticamente la técnica usada para
implementar el método bajo discusión.
4
Z es una variable de la que desconcemos su valor. Debemos encontrar los valores de M y S de modo que se cumplan
las rerstricciones y Z sea máxima

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 6
Planteamiento Matricial de Problema de Programación Lineal
Tabla 1: Planteamiento Matricial
Maximizar Sujeto a: 𝟏 𝟐 𝟐𝟒
𝑴
𝑴 𝟏 𝟎 𝑴 𝟎 [𝟐 𝟏] ∙ [ ] ≤ [𝟐𝟒]
[𝟑 𝟒] ∙ [ ] = 𝒁 [ ]∙[ ]≥ [ ] 𝑺
𝑺 𝟎 𝟏 𝑺 𝟎 𝟏 𝟏 𝟏𝟓
Vector de Utilidades
No negatividad de Matriz de Coeficientes Tecnológicos
por las variables igual a
las variables * Vector de Variables menor igual a
Utilidad
Vector de Recursos
(Función Objetivo)

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 7
1.5.2.5.
Método Gráfico
La solución gráfica permite entender los principales conceptos del problema a resolver. En dos
dimensiones, las restricciones son rectas en un plano cartesiano coordenado euclidiano, en donde
cada eje representa la variable de decisión.
Las rectas representan situaciones límite de aprovechamiento de un recurso. Al trazarse
configuran límites del plano que marcan la factibilidad como una superficie. Conforme se trazan
más restricciones se acota el espacio de soluciones factibles, y al final resulta en un polígono, que
por necesidad es convexo (panzón).
La mejor solución se encuentra cuando se usan al máximo dos recursos, esto es cuando dos rectas
se cruzan. Puede darse el caso de que sean más de dos las rectas que se cruzan por un solo punto,
pero esto corresponde a una situación artificial en la que se forzó un recurso. En la vida real esto
es altamente inestable y es muy raro que suceda.
Así, la mejor solución es forzosamente un vértice del polígono de factibilidad de las soluciones.
Para ubicar el mejor vértice se hace uso del gradiente, que tiene la dirección marcada por el vector
de utilidades
El Plano Euclidiano.
Es un sistema axiomático en el cual todos los teoremas se derivan de un pequeño número de
axiomas (verdades tan evidentes que no requieren demostración).
Las conclusiones más importantes para nosotros son:
• Una línea recta es una sucesión de puntos a la mínima distancia de todos los demás puntos
de ella.
• Entre dos puntos solo hay una recta
• Solo hay una recta que pasa por un punto y tiene una pendiente
• La mínima distancia entre dos puntos es sobre una trayectoria recta.
• Una recta puede extenderse infinitamente.
• Dos rectas o se cruzan en un punto o son paralelas. (Tienen la misma pendiente).
La Recta
Todas las técnicas que se describen en estos dos cursos son lineales. Esto implica que todas las
ecuaciones que describen los diferentes modelos, son de primer orden y primer grado (la máxima
y única potencia es 1 y no hay diferenciales).
Ecuación Canónica
En esta se ofrece la ecuación de la recta de tal forma que la variable dependiente (eje vertical,
“y”) se plantea como una función de la variable independiente (eje horizontal, “x”). Así la recta se
define como un punto (donde cruza el eje vertical) y una inclinación (dada por la pendiente):
𝒚=𝜶+𝜷∙𝒙
Ecuación 1
Presenta dos parámetros:
• a La intercepción con las abscisas, o la intercepción con el eje vertical, o simplemente
intercepto.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 8
• ,β La pendiente. Se define como la razón de los incrementos en yyx, que significa lo que
asciende (sube) entre lo que avanza
∆𝒚 𝑳𝒐 𝒒𝒖𝒆 𝒂𝒔𝒄𝒊𝒆𝒏𝒅𝒆
𝜷≡ = Ecuación 2
∆𝒙 𝒍𝒐 𝒒𝒖𝒆 𝒂𝒗𝒂𝒏𝒛𝒂
8
Y=3+.5X
7
Incremento de X
Incremento de Y 6

∆Y→
4
β=∆Y/ΔX
ΔX→ β=1/2=0.5
3

0
-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10

Otras Ecuaciones.

La recta, definida por dos puntos: las

X/ζ + Y/α =1 intersecciones con los dos ejes:
7

6 𝒙 𝒚
+ =𝟏 Ecuación 3
𝜻 𝜶
5
X/3 + Y/6 =1 Cuyos parámetros son:
4 • ,αLa intercepción con el eje vertical.
α 3 • ,ζ La intercepción con el eje
horizontal.
2 −𝜶
𝜷= Ecuación 4
1 𝜻

0
0 1 2 3 4

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2.9
Aunque no es única la mencionamos por que esta
AX + BY = C forma de definición es la que estaremos usando:
𝒂𝒙 + 𝒃𝒚 = 𝒄 Ecuación 5
7 Así esta recta puede ser:
6x + 3y = 18
6 60x + 30y = 180
6X + 3Y = 18 30x + 15y = 90
5 Etc.…
Y todas estas son la que se grafica aquí.
4

0
0 1 2 3 4

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 10
1.5.2.5.1.
Desigualdades
Indican una relación en la que se define un conjunto de valores que se encuentran limitados por
una constante. El símbolo siempre apunta del mayor al menor A<B se lee “A menor que B” que
puede expresarse como B>A “B mayor que A”.
Se dice ser un intervalo (todo el conjunto de valores que cumple la expresión).
1.5.2.5.1.1.
Menor
La desigualdad
𝒂𝒙 + 𝒃𝒚 < 𝒄 Ecuación 6
Indica todos los puntos que se encuentran a la izquierda y por debajo de la recta
𝒂𝒙 + 𝒃𝒚 = 𝒄 Ecuación 7
𝒄 𝒂
𝒚= + 𝒚 Ecuación 8
𝒃 𝒃
Que indica todos los puntos que ya no están en el intervalo. A esta indefinición se llama intervalo
abierto, que puede estar tan cerca como se quiera, pero no incluye la frontera.
1.5.2.5.1.2.
Menor o igual
Cuando el símbolo de relación es ≤ indica que son los puntos que o bien están en la recta o bien
por debajo y a la izquierda del ella. Como se incluye la frontera es un intervalo cerrado
1.5.2.5.1.3.
Mayor
Con el símbolo > señala todo el intervalo de puntos que se encuentran por encima y a la derecha
de la recta que lo limita, es un intervalo abierto.
1.5.2.5.1.4.
Mayor o igual
Son los puntos del conjunto que contiene tanto los puntos a la derecha y arriba como los puntos
que se encuentran en la recta (intervalo cerrado)
1.5.2.5.1.5.
Igualdades.
En este caso es el conjunto de puntos que se encuentran dentro de la línea.
1.5.2.5.2.
Áreas
Cualquier objeto en un plano euclideano que se encuentre delimitando un conjunto de puntos.
1.5.2.5.2.1.
Polígonos
Es un área delimitada por segmentos de línea recta, únicamente.
1.5.2.5.2.2.
Concavidad
Es el concepto de figuras en las que se tienen puntos que NO se pueden unir con una recta sin
abandonar dicha superficie

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 11

1.5.2.5.2.3.
Convexidad
En un espacio Euclideano, un objeto es convexo si para cualquier par de puntos dentro del objeto,
se pueden unir por un segmento de recta que contiene todos sus puntos dentro de dicho objeto.De
otra manera se dice que es concavo.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 12
1.5.2.5.3.
Espacio de soluciones

Las posibles soluciones se encuentran limitadas por rectas que señalan la máxima (o mínima)
utilización de algún recurso. Es por esto que también se denomina Espacio de Factibilidad.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 13
25

20

15
M≥0 S≥0

10

5 Espacio de
Factibilidad
0
0 5 10 15 20 25

Ilustración 1 Espacio de soluciones: X>0 y Y>0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 14
25

20
M≥0

15
S≥0

1*M + 2*S ≤ 24
10

5 Espacio de
Factibilidad
0
0 5 10 15 20 25

Ilustración 2Espacio de soluciones: X>0 y Y>0 y M+2S≤0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 15
25

20 M≥0

S≥0

1*M + 2*S ≤ 24
15

2*M + 1*S ≤ 24
10

5 Espacio
de
0
Factibilidad
0 5 10 15 20 25

Ilustración 3 Espacio de soluciones: X>0 y Y>0 y M+2S≤0 y 2M+S<24

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 16
25

20
M≥0

S≥0

1*M + 2*S ≤ 24
15

2*M + 1*S ≤ 24

1*M + 1*S ≤ 15
10

5
Espacio
de
Factibilidad
0
0 5 10 15 20 25

Ilustración 4 Ilustración 1 Espacio de soluciones: X>0 y Y>0 y M+2S≤0 y 2M +S<24 y M+S<15

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 17
1.5.2.5.4.
Gradiente de utilidades
M≥0
S≥0
1*M + 2*S ≤ 24
2*M + 1*S ≤ 24
1*M + 1*S ≤ 15
10 Gradiente
$1
$2
$3
$4

0
0 5 10
Ilustración 5 Ilustración 1 Espacio de soluciones: Gradiente y diferentes utilidades
1.5.2.5.5.
Programa SCILAB para visualización de las
C=[1 2;2 1;1 1;-1 0;0 -1];R=[24;24;15;0;0];U=[3,4];
soluciones
X=[0,12,9,6,00,0,12,09,06,00,0,12,12,12,9,09,9,6,06,6,00,00,00];
Y=[0, 0,6,9,12,0,00,06,09,12,0,00,00,00,6,06,6,9,09,9,12,12,12];
Z=[0,00,0,0,00,0,36,51,54,48,0,00,36,00,0,51,0,0,54,0,00,48,00];
param3d(X,Y,Z);
d=.5;c=[1];x=[-d;d;d;-d];y=[-d,-d,d,d]';z=x;
fori=0:24;for j=0:24; p=[i;j]; if and(C*p <= R) then b=U*p;
c=[c,b,b];x=[x,[i-d;i+d;i+d;i-d],[i-d;i+d;i+d;i-d]];y=[y,[j-d;j-d;j+d;j+d],[j+d;j+d;j-d;j-d]];
z=[z,[b-.01;b-.01;b-.01;b-.01],[b+.01;b+.01;b+.01;b+.01]];
end;end;end;
plot3d(x,y,list(z,c))
f=gcf();f.color_map=rainbowcolormap(max(c));h=gce();h.color_mode=-2;h.color_flag=2;
a=gca(); a.grid=[1 1 1]; a.data_bounds=[0,0,0;12,12,55];
for j=0:.5:360;a.rotation_angles=[j,2*j];end;

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 18
1.5.2.5.5.1.
Ejemplo
35
Z=4X+3Y
Sujeto a:
30
3X+Y<=30
2X+Y<=30
25 X+2Y<=30
X>=0
20 Y>=0

15

10

0
0 5 10 15 20 25 30 35

Solucion:
X=6
Y=12
Z=60
1.5.2.5.5.2.
Ejercicios
Maximizar: Maximizar: Maximizar: Maximizar: Maximizar: Maximizar:
Z= 3x + 2y Z= 4x + 2y Z=5x + 2y Z= A + B Z= U + V Z=3M + 4N
Sujeto a: Sujeto a: Sujeto a: Sujeto a: Sujeto a: Sujeto a:
3x + y ≤ 24 2x + y ≤ 18 2x + y ≤ 12 A+ B≤9 2U + 3V ≤ 6 2M + N ≤ 12
x + y ≤ 16 x + y ≤ 13 3x + y ≤ 18 A +2B ≤ 8 2U+ V ≤ 8 3M +2N ≤ 18
x + 3y ≤ 24 3x + 2y ≤ 30 y≤4 3A + B ≤ 9 U ≤5 M+ N≤7
x ≥0 x ≥0 x ≥0 A ≥0 U ≥0 M ≥0
y ≥0 y ≥0 y≥0 B≥0 V ≥0 N≥0
x=6 y=6 z=30

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 19
1.5.2.5.6.
Desarrollo en tres dimensiones
El eje Z atraviesa el papel por el punto rojo y representa la utilidad. Recorte las líneas punteadas
y doble hacia abajo por las líneas continuas.

Sillas→

Mesas→
$3
$6
$9
$12
$15
$18
$21
$24
Z= $36→

$27
$30
$33

Maximo $54→
Z= $51→

Z= $48→

Ilustración 6 Desarrollo tridimensional (corta aqui)

Secuencia de
Construcción

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 20

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 21
1.5.2.5.7.
Desigualdades: Mayor o Igual
En este caso, la recta limita el espacio de Espacio de Soluciones
soluciones por debajo y a la izquierda: Ejemplo:
Y
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟:
↑
10
𝑍 = 𝑋 + 3𝑌 X + Y ≤ 11

𝑆𝑢𝑗𝑒𝑡𝑜 𝑎: X + 2Y ≤ 14
𝑋 + 𝑌 ≤ 11 5
𝑋 + 2𝑌 ≤ 14 X + 3Y ≥ 15

𝑋 + 3𝑌 ≥ 15 0 X→
2𝑋 + 𝑌 ≥ 10 0 5 10 15
𝑋 ≥ 0; 𝑌 ≥0 La última restricción delimita el polígono de
La primera restricción limita el espacio de soluciones a la derecha y por encima de la
soluciones por arriba y a la derecha hasta la línea morada
recta azul
Espacio de Soluciones
Espacio de Soluciones
Y
Y X + Y ≤ 11
↑
10
10 ↑ X + Y ≤ 11
X + 2Y ≤ 14
5 5
X + 3Y ≥ 15

0 X→ 2X + Y ≥ 10
0
0 5 10 15
0 5 10 15 X
X→
La segunda restricción delimita el espacio El gradiente apunta hacia (6,2) con una
de soluciones por debajo y a la derecha de la utilidad de $20
recta roja
Espacio de Soluciones
Espacio de Soluciones
Y
Y X + Y ≤ 11
↑
10 X + Y ≤ 11 10↑
Máximo X + 2Y ≤ 14
X + 2Y ≤ 14 5 X + 3Y ≥ 15
5
2X + Y ≥ 10
0
0 X→ 0 5 10 15 Gradiente
0 5 10 15 X→ Utilidad: $20

La tercera restricción es mayor que, por lo

que limita el espacio de soluciones por debajo
y a la izquierda
1.5.2.5.7.1.
Ejercicios en 1.5.2.5.10

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 22
1.5.2.5.8.
Restricciones por igualdad
En este caso, la recta es el limite del espacio de Espacio de Soluciones
solucionesEjemplo:
Y
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟:
↑
10
𝑍 = 𝑋 + 3𝑌 X + Y ≤ 11

𝑆𝑢𝑗𝑒𝑡𝑜 𝑎: X + 2Y ≤ 14
𝑋 + 𝑌 ≤ 11 5
𝑋 + 2𝑌 ≤ 14 X + 3Y ≥ 15

𝑋 + 3𝑌 = 15 0 X→
2𝑋 + 𝑌 ≥ 10 0 5 10 15
𝑋 ≥ 0; 𝑌 ≥0 La última restricción delimita el polígono de
La primera restricción limita el espacio de soluciones a la línea morada
soluciones por arriba y a la derecha hasta la
Espacio de Soluciones
recta azul
Y
Espacio de Soluciones X + Y ≤ 11
↑
10
Y
10 ↑ X + Y ≤ 11 X + 2Y ≤ 14
5
X + 3Y ≥ 15
5

0 2X + Y ≥ 10
0 X→
0 5 10 15 X
X→
0 5 10 15
El gradiente apunta hacia (6,2) con una
La segunda restricción delimita el espacio utilidad de $20
de soluciones por debajo y a la derecha de la
recta roja Espacio de Soluciones

Espacio de Soluciones Y
Y 10↑
Máximo 2X + Y ≥ 10
↑
10 X + Y ≤ 11
5
X + 2Y ≤ 14
5 0
0 5 10 15 Gradiente
0 X→ X→
0 5 10 15

La tercera restricción es mayor que, por lo

que limita el espacio de soluciones por debajo
1.5.2.5.8.1.
y a la izquierda Ejercicios en 1.5.2.5.10

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 23
10
1.5.2.5.9.
Optimización. X>0

Y→
Se traza el gradiente, que es la dirección en
que crece más la utilidad. Es una dirección y Y>0
no un camino, por lo que se puede trazar en
cualquier parte de la figura, lo importante es
que se trace en una región en que no estorbe 5 X+3Y<9
la visualización de todo el espacio de
soluciones.
A partir de cualquier punto P, se cuenta a la
derecha la cantidad que en la función objetivo
acompañe a la primera variable, y hacia arriba
la cantidad indicada por la segunda variable. 0
Apoyando la regla en este punto y en el punto 0 5 10
P inicial, se traza una recta auxiliar del X→
tamaño del papel.
1.5.2.5.9.1.
Maximización 1.5.2.5.9.2.
Minimización.
Si deslizamos una escuadra, apoyada en la Si deslizamos una escuadra, apoyada en la
regla (ubicada sobre el gradiente en un lugar regla encontraremos la línea en que se
lejano al espacio de soluciones), encuentra el conjunto de soluciones que
encontraremos la línea en que se encuentra el tienen la misma utilidad, deslizándola hacia la
conjunto de soluciones que tienen la misma izquierda y hacia abajo, se ubica el punto
utilidad, deslizándola hacia la derecha y hacia mínimo, donde se toca apenas el espacio de
arriba, se ubica el punto máximo, donde se soluciones, que corresponde a un vértice y en
toca apenas el espacio de soluciones, que algunos casos raros en toda la arista.
corresponde a un vértice y en algunos casos 10
raros en toda la arista. Como ejemplo tenemos X>0
el primer ejercicio
Y→

Y>0
5

0
0 5 10
X→

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 24
1.5.2.5.10.
Ejercicios (≤)
Maximizar:
Z = X + 3Y U = 2A + 3B R = 3P + 4Q Ω = 3λ + 2μ Λ=Φ+Ξ
Sujeto a:
X + 2Y ≤ 10 A + 3B ≤ 15 2P + Q ≤ 6 λ≤3 Φ≤3
X+ Y≤ 6 A + 2B ≤ 12 P+ Q≤4 λ+ μ≤5 Ξ≤5
3X + Y ≤ 12 A + B ≤ 10 Q≤3 λ + 2μ ≤ 8 Φ+Ξ≤6
X≥ 0 A≥ 0 P≥0 λ≥0 2Φ+Ξ≤8

Y≥ 0 B≥ 0 Q≥0 μ≥0 Φ ≥ 0 , Ξ ≥0
Φ=1; Ξ =5; H1=2;
X=0; Y=5; H1=0; H2=1; A=8; B=2; H1=1; H2=0; P=1; Q=3; H1=1; H2=0; λ =3; μ =2; H1=0; H2=0;
H2=0; H3=0; H4=1;
H3=7; Z=15. H3=0; U=22. H3=0; R=15. H3=1; Ω=13.
Λ=13.

1.5.2.5.10.1.
Ejercicios (≥)
Maximizar:
Z = X + 3Y U = 2A + 3B R = 3P + 4Q Ω = 3λ + 2μ Λ=Φ+Ξ
Sujeto a:
X + 2Y ≤ 12 A + 3B ≤ 15 2P + Q ≤ 6 λ≥3 Φ≤ 3
2X + Y ≤ 12 A + 2B ≤ 12 Q≤3 λ+ μ≥5 Ξ≤5
X+ Y≥ 4 A + B ≥ 12 P+ Q≥6 λ + 2μ ≥8 Φ+Ξ≥6
X≥ 0 X≥ 0 P≥0 λ≥0 2Φ+Ξ≥8

Y≥ 0 Y≥ 0 Q≥0 Φ ≥ 0, Ξ ≥0
μ≥0 Φ=3; Ξ =5; H1=0;
X=0; Y=6; H1=0; H2=6; A=12; B=0; H1=3; H2=0; ¡No es factible! Espacio de
¡NO ACOTADO! H2=0; H3=2; H4=3;
H3=2; Z=18. H3=0; U=24. soluciones vacío
Λ=8.

1.5.2.5.10.2.
Ejercicios (=)
Maximizar: IGUALDADES
Z = X + 3Y U = 2A + 3B R = 3C + 2D T = 2G + 4H S= 4K + 5L
Sujeto a:
X + 2Y ≤ 12 A + 3B ≤ 30 C + 2D ≥12 G + 3H ≤9 K+L≥4
2X + Y = 12 A + 2B ≥ 24 C + 3D ≤ 24 2G + H ≥ 8 K + 2L≤ 6
X+ Y≥ 7 A + B = 20 C + D=7 G =5 K + L =5
X≥ 0 A≥ 0 C≥0 λ≥0 K≥0
Y≥ 0 B≥ 0 D≥0 μ≥0 L ≥0
X=4; Y=4; H1=0; H3=1; Z=16. A=15; B=5; U=45. C=7;D=0;H1=5;H2=3;R=21. K=4 L=1 S=21

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 25

Minimizar:
Z = X + 3Y U = 2A + 3B R = 3*P + 4Q Ω = 3λ + 2μ Λ=Φ+Ξ
Sujeto a:
X + 2Y ≤ 12 A + 3B ≤ 15 2P + Q ≤ 6 λ ≤3 Φ ≤3
2X + Y ≤ 12 A + 2B ≤ 12 P+ Q≤4 λ+ μ≤5 Ξ≤5
3X + Y ≥ 7 A + B ≥ 10 Q≤3 λ + 2μ ≤ 8 Φ + Ξ ≥6
X≥ 0 X≥ 0 P≥0 λ≥0 2 Φ+ Ξ ≥8
Y≥ 0 Y≥ 0 Q≥0 μ≥0 Φ ≥ 0, Ξ ≥0

Minimizar:
Z = X + 3Y U = 2A + 3B R = 3*P + 4Q Ω = 3λ + 2μ Λ=Φ+Ξ
Sujeto a:
X + 2Y ≤ 12 A + 3B ≤ 15 2P + Q ≤ 6 λ ≤3 Φ ≤3
2X + Y ≤ 12 A + 2B ≤ 12 P+ Q≤4 λ+ μ≤5 Ξ≤5
3X + Y ≥ 7 A + B ≥ 10 Q≤3 λ + 2μ ≤ 8 Φ + Ξ ≥6
X≥ 0 X≥ 0 P≥0 λ≥0 2 Φ+ Ξ ≥8
Y≥ 0 Y≥ 0 Q≥0 μ≥0 Φ ≥ 0, Ξ ≥0

Minimizar: IGUALDADES
Z = X + 3Y U = 2A + 3B R = 3*P + 4Q Ω = 3λ + 2μ Λ=Φ+Ξ
Sujeto a:
X + 2Y ≤ 12 A + 3B ≤ 15 2P + Q ≤ 6 λ ≥3 Φ ≤3
2X + Y ≤ 12 A + 2B ≤ 12 P+ Q≥4 λ+ μ≤5 Ξ≤5
3X + Y ≥ 7 A + B ≥ 10 Q≤3 λ + 2μ ≤ 8 Φ + Ξ ≥6
X≥ 0 X≥ 0 P≥0 λ≥0 2 Φ+ Ξ ≥8
Y≥ 0 Y≥ 0 Q≥0 μ≥0 Φ ≥ 0, Ξ ≥0

Continúa en página 60

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 26
El algoritmo SIMPLEX trabaja sobre
1.5.2.6.
Método Simplex vértices de un espacio de soluciones,
El Método Simplex publicado por fundamentado en la solución de un sistema de
GeorgeDantzig en 1947 (3) consiste en un ecuaciones en el que cada iteración elije un
algoritmo iterativo que secuencialmente a vértice con mayor utilidad. Se genera un
través de iteraciones se va aproximando al renglón discriminante, que indica si se puede
óptimo del problema de Programación Lineal mejorar la solución. Todas las variables están
en caso de existir esta última. restringidas a ser positivas o cero. Debe
La primera implementación computacional empezar en algún lugar del espacio de
del Método Simplex es el año 1952 para un soluciones, convexo por definición, ya que la
problema de 71 variables y 48 ecuaciones. Su trayectoria de este punto inicial a cualquier
resolución tarda 18 horas. Luego, en 1956, un punto del espacio de soluciones. Y un vértice
código llamado RSLP1, implementado en un en particular, es una recta que no abandona el
IBM con 4Kb en RAM, admite la resolución espacio de soluciones, se ubica el vértice que
de modelos con 255 restricciones. ofrezca una mejor utilidad, lo que obliga a
transformar el sistema de ecuaciones para
En 1984, el matemático Narendra Karmakar
lograrlo, a lo que llamamos iteración. La
creó un algoritmo nuevo para solucionar
implementación del tableau se hizo siguiendo
modelos lineales. Este algoritmo permite
los lineamientos de Anderson, Sweeney y
manejar cantidades enormes de variables y
Williams(4) en su libro Introducción a los
restricciones. AT&T desarrolló su
Modelos Cuantitativos para la
implementación en computadora en 1988 y
administración.
ha presentado versiones posteriores. IBM
agregó variantes al algoritmo en 1990. DE PUNTOS INTERIORES.
Mientras tanto, se han elaborado miles de El Método Simplex hace uso de la
trabajos dirigidos a desarrollar variantes propiedad de que la solución óptima de un
mejoradas del algoritmo. problema de Programación Lineal se
El Método de Karmakar también es un encuentra en un vértice o frontera del dominio
algoritmo iterativo, como el Simplex, pero de puntos factibles (esto último en casos muy
parte de una solución de prueba, obtenida especiales), por lo cual, la búsqueda
DENTRO de la región de soluciones posibles. secuencial del algoritmo se basa en la
En cada iteración se mueve dentro de la evaluación progresiva de estos vértices hasta
región solución a una mejor solución de encontrar el óptimo, descartando una variable
prueba y así continúa hasta obtener la mejor de la solución actual, haciendo que intervenga
solución en un punto extremo. La principal la mejor de las variables no consideradas en
diferencia con el Algoritmo Simplex es que la solución básica, por medio del método de
trabaja con puntos interiores de la región Gauss-Jordan de eliminación. Cabe destacar
solución. que para aplicar el Método Simplex a un
modelo lineal, este debe estar en un formato
especial conocido como formato estándar el
cual definiremos a continuación.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 27
•
1.5.2.6.1.
Método de Se puede multiplicar cualquier renglón
(completo) por un número cualquiera
Eliminación de 1x1 + 2x2 = 3 ➔ 7 * (1x1 + 2x2 = 3)
Gauss-Jordan ➔ 7x1 +14x2 = 21
Constituye un algoritmo para resolver un
conjunto de ecuaciones. En el caso de tener n 1 2  x1  3 7 14  x1  21
ecuaciones (linealmente independientes) con  4 5     = 6  ➔  4 5     =  6 
   x2       x2   
n incógnitas, en cuyo cado solo hay una
solución para las n incógnitas:
• Se puede sustituir cualquier renglón
 c11 c12  c1n   x1  por una combinación lineal de
c c22  c2 n  x 
cualquier número de renglones.
C =  21 X =  2
      1x1 + 2x2 = 3 ➔5 * (1x1 + 2x2 = 3)
    ➔ 5x1 +10x2 = 15
cn1 cn 2  cnn   xn 
4x1 + 5x2 = 6 ➔ -2*(4x1 + 5x2 = 6)
 r1 
r  ➔ -8x1-10x2 = -12
R =  2

  1 2  x1  3
rn   4 5     = 6  ➔
   x2   
C  X = R C −1  C  X = C −1  R (5 1) + (−2  4) (5  2) + (−2  5)  x1  (5  3) + (−2  6)
C −1  C  I IX  X    =  
−1  4 5   x2   6 
C C  X = I  X
 X = C −1  R − 3 0  x1  3
➔  4 5     = 6 
Si C −1  R = S entonces I  X = S    x2   
1 0  0  x1   s1 
0 1  0   x   s 
  2 =  2
         
     
0 0  1   x n   s n 
Entonces debemos operar C de tal modo
que resulte I, y si las mismas operaciones se
las ejecutamos a R el resultado será S. Las
operaciones permitidas son:
• Se puede intercambiar cualquier
renglón (completo, por supuesto)
1x1+ 2x2 = 3 ➔ 4x1 + 5x2 = 6
4x1 + 5x2 = 6 1x1+ 2x2 = 3
1 2  x1  3 4 5  x1  6
4 5    = 6 ➔ 1 2    = 3
   x2       x2   

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 28
Para ilustrarlo con el sistema anterior: Que indica que valores de x1 y de x2 (-1 y 2
respectivamente), satisfacen ambas
1 2  x1  3
 4 5     = 6  ➔ ecuaciones:
   x2    1(-1) + 2(2) = -1 + 4 = 3 y
4(-1) + 5(2) = -4 + 10 = 6
(5 1) + (−2  2) (5  2) + (−2  5)  x1  Para nuestro problema:
   = Hacer de todas las desigualdades
 4 5   x2 
igualdades, sumando o restando una nueva
(5  3) + (−2  6) variable que llamaremos holgura, con lo que
 6  tendremos n ecuaciones con n incógnitas.
 
Si es necesario realizar una iteración esta
trata de lograr un uno en la columna de interés
− 3 0  x1  3 (columna pivote), que resulte en ceros en esa
 4 5     = 6  ➔
   x2    columna en los demás renglones, los demás
coeficientes se alterarán en consecuencia a
dicha operación.
− 1  (−3) − 1  (0)  x1  − 1  (3)
 3 3   =  3 ➔ Para indicar cual es el renglón y columna
 4 5   x2   6  pivote se hacen ciertos cálculos que resultan
en el renglón y columna discriminante, que
además indican si se requiere o no la siguiente
1 0  x1  − 1 iteración.
 4 5    =  6  ➔
   x2    Para lograr esto se ha llegado al siguiente
algoritmo llamado SIMPLEX.
 1 0   x1 
1  (4) − 4  (1) 1  (5) − 4  (0)    =
   x2 
 −1 
1  (6) − 4  (−1)
 

 1 0   x1   − 1 
4 − 4 5 − 0    = 6 + 4 ➔
   x2   

1 0  x1  − 1
0 5    = 10  ➔
   x2   

 1 0   x1   − 1 
0  1 5  1     = 10  1  ➔
 5 5   x2   5

1 0  x1  − 1  x1  − 1
0 1     =  2  ➔   =  2 
   x2     x 2   

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 29
Z= [34]*[M S]’
1.5.2.6.2.
Nomenclatura: [12; 21; 11]*[M S]’< [242415]’
[10; 01]*[M S]’
Notación:
Z: valor de la medida global de efectividad.
Z= [3 4 0 0 0]*[M S H1 H2 H3]’
Dj: nivel de la actividad j (para j = 1, 2,….,
n) [1 2 1 0 0; 2 1 0 1 0; 1 1 0 0 1]*
Dj: incremento en Z que resulta al aumentar [M S H1 H2 H3] = [24 24 15]’
una unidad en el nivel de la actividad j [1 0 0 0 0; 0 1 0 0 0; 0 0 1 0 0; 0 0 0 1 0; 0 0 0 0 1]*
Bi: cantidad del recurso i disponible para [M S H1 H2 H3]’ ≥ [0 0 0 0 0]’
asignar a las actividades (para i = 1, 2,…, m)
Aij: cantidad del recurso i consumido por ¿? M S H1 H2 H3
M US R
Variables de Decisión
cada unidad de la actividad j.
3H1 H
4 2 H03 0 0
Los valores xj son las variables de decisión 3 4 0 0 0 0 Utilidades
y los valores de cj, bi, y aij son las constantes H1 0 1 2 1 0 0 0 24
de Entrada al modelo (parámetros del H
H12 00 2 1 0 01 0 24
modelo). H23 00 1 Solución
1 0 Básica
0 1 15
Formato Estándar del Modelo: H3Z 0 0 0 0 0 0 0
Maximizar: 1U - Z
3 11 40 00 Coeficientes
0 0
Z=3M+4S 2 2 0 1 0 Tecnológicos
Sujeto a: 1 4 0 0 1
1M+2S≤ 24 24
2M+1S≤ 24 24 Recursos
1M+1S≤ 15 15
1M≥ 0, 1S ≥ 0 0 0 0 0 0 Utilidad Parcial
0 Utilidad Total (Función Objetivo)
1 4 0 0 0 Renglón Discriminante

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 30
1.5.2.6.3.
Procedimiento
A continuación se esquematiza el algoritmo, cada proceso se describe a continuación.

≤ Sume una holgura (sin utilidad)

Para desigualdades con ≥ Reste una holgura sin utilidad y sume una Artificial altamente
1) Holguras el signo: penalizada en las Utilidades (-M)
= Sume una Artificial altamente penalizada en las Utilidades (-M)
El primer renglón contiene todas las variables. El segundo renglón tiene las utilidades. Las
primera columna contienen las artificiales o en su defecto las holguras. En la segunda
2) TABLEAU columna las utilidades correspondientes a cada variable en la primer columna. El cuerpo de
Inicial
la tabla presenta los coeficientes tecnológicos. La última columna contiene los recursos. Los
dos últimos renglones en blanco
Penúltimo renglón. La suma de los productos de cada utilidad en la segunda columna por el
coeficiente tecnológico correspondiente a esta columna. En la columna de los recursos se
3) Utilidades encuentra la utilidad para la solución indicada.
parciales
El Valor de la variable en la primera columna se encuentra en la columna de los recursos,
en el renglón correspondiente
En el último renglón: La diferencia del primer renglón menos el ¿Terminó? SI→FIN
4) Renglón penúltimo.
Discriminante N O ↓ CONTINÚE
Si hay valores positivos no se ha terminado.
5) Determina La correspondiente al mayor valor positivo del renglón discriminante
Columna pivote
Divida los recursos entre los coeficientes de la columna pivote. El
6) Determina menor de los cocientes positivos indica cual es el renglón pivote. ¡Terminó? SI→FIN
Renglón pivote
Si no hay valores positivos, se ha terminado. NO ↓ CONTINÚE
7) Nuevo En las primeras dos columnas. Sale la variable marcada en el renglón pivote y entra la que
TABLEAU indica la columna pivote, con sus utilidades respectivas
8) Nueva En los coeficientes de la columna pivote. Uno en el pivote y ceros en las demás celdas
columna pivote
9) Nuevo En los coeficientes tecnológicos y recursos del renglón pivote. El renglón pivote entre el
renglón pivote pivote
10) Cálculo de
los otros El renglón de la tabla anterior menos el nuevo renglón pivote multiplicado Continúe
por el coeficiente tecnológico correspondiente de la columna pivote.
renglones en 3

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 31
1.5.2.6.3.1.
El Planteamiento
Maximizar Z = 1 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 1 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2 M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M + S ≤ 15

El modelo matemático termina en la propuesta de función objetivo y en número dado de inecuaciones

tecnológicas con un símbolo de relación (≤, =, ≥) y un recurso, respectivamente
1.5.2.6.3.2.
1 Las Holguras
Para poder trabajar, debemos transformar las desigualdades en igualdades. Esto tiene el precio de
obligar a agregar una variable positiva o cero, por cada desigualdad ≤. La llamaremos H1 por ser la del
primer renglón, H2 y H3 las de los siguientes renglones. En el problema del ejemplo inicial:
1*M ≥0
1*S ≥ 0
Son obligadas, pues todas las variables deben ser positivas y 0 cuando menos
Función Objetivo maximizar
3*M+ 4 *S = Z [$]
Mano de obra
1*M + 2*S ≤ 24 [Horas Hombre]
Materiales
2*M +1*S≤ 24 [Hojas de Triplay]
Equipo
1*M +1*S ≤ 15 [Bancos De Trabajo]
La Mano de obra utilizada debe ser menor o igual a 24hh, si añadimos una cantidad conveniente
1*M + 2*S + 1 * H1= 24 [hh]
Que significa: 1hh / mesa por la cantidad de mesas producidas, más 2hh / silla por la cantidad
de sillas producidas, mas las hh que se desperdicien deben ser 24hh (recurso disponible).
Los Materiales usados deben ser menores o iguales a 24hojas, agregamos su holgura:
2*M + 1*S + 1*H2= 24 [HsT]
2 hojas/mesa por las mesas producidas mas 1 hoja/silla por las sillas producidas más las hojas
desperdiciadas deben ser 24.
El uso de equipo, con su holgura es:
1*M + 1*S + 1* H3= 15 [BsT]
1 equipo/ mesa mas un equipo/silla mas los equipos que no se usen deben ser 15
En la Función Objetivoestas holguras no tienen ninguna contribución:
Z =3*M+4 *S+0*H1+0*H2+0*H3 [$]
© [email protected] Lecturas 2 Programación lineal
 UABC Ensenada B.C. México (414) 1.5.2. 32
Resumiendo, tenemos:
3*M+4*S+0*H1+0*H2+0*H3=Z
1*M+ 2*S +1*H1+0*H2+0*H3=24
2*M+ 1*S +0*H1+1*H2+0*H3=24
1*M+ 1*S +0*H1+0*H2+1*H3=15
Iniciamos el planteamiento escribiendo la función objetivo, un símbolo por cada cuadrito
Maximizar Z = 3 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 1 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2 M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M + S ≤ 15

Para
desigualdades
1) Holguras con el signo:
≤ Sume una holgura (sin utilidad)0
(2.5.2.3.2.1)
El subíndice de la variable H es el número de ecuación, pues todas pueden ser diferentes. Para la
primera desigualdad de las restricciones:
Maximizar Z = 3 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 1 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2 M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M + S ≤ 15
Para la segunda desigualdad de las restricciones:
Maximizar Z = 3 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 1 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2 M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M + S ≤ 15
Para la tercera desigualdad de las restricciones:
Maximizar Z = 3 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 1 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2 M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M + S ≤ 15
Completamos con coeficientes 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 33
Maximizar Z = 3 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 1 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2 M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M + S ≤ 15
Ya que tenemos todas las variables (de decisión, holguras y artificiales) podemos iniciar el Tablau
En seguida, de acuerdo con el paso
1.5.2.6.3.3.
2 El Tableau inicial
Con los datos anteriores elaboramos la siguiente tabla (“TABLEAU”). No es una tabla de referencia,
es un instrumento de cálculo. Esta tabla es el producto de las influencias que he tenido de los autores
consultados(4), (5), (6). Es posible encontrar otras tablas que pueden cambiar la distribución de los
mismos contenidos. Por facilidad al alumno se ha llegado al tableau indicado para hacer más fácil su
operación.
El primer renglón contiene todas las variables. El segundo
renglón tiene las utilidades. Las primera columna contienen las
artificiales o en su defecto las holguras. En la segunda columna
2) TABLEAU (1.5.2.6.3.2) las utilidades correspondientes a cada variable en la primer
Inicial
columna. El cuerpo de la tabla presenta los coeficientes
tecnológicos. La última columna contiene los recursos. Los dos
últimos renglones en blanco

1.5.2.6.3.3.1.
Las variables
El primer TABLEAU, en el primer renglón contiene todas las variables, incluyendo artificiales u
holguras (hasta ahora no hemos estudiado las artificiales, que mas adelante estudiaremos)

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 34
Maximizar Z = 3 M + 4 S - 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 2 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M+ S ≤ 15 ¿? M S H1 H2 H3
R
U 1 4 -m 0 0
El segundo renglón siempre contiene las utilidades de la función objetivo.
Maximizar Z = 3 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 2 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S = 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2M + S ≥ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M+ S ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0

1.5.2.6.3.3.2.
El contenido del Tableau
En la primera columna, se agregan las variables artificiales, y si en ese renglón no existieran, se colocan
las holguras.
El subíndice indica el número de relación de restricción, así H1 es la holgura de la primera restricción
(M+2S<24)

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 35
Maximizar Z = 3 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 2 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M+ S ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 -m 1 2 1 0 0 6 6/2=3
H2 -m 1 1 0 -1 0 4 4/1=4
H3 0 1 1 0 0 1 5 5/1=5
Z -2m -3m -m m 0 -10m
U-Z 1+2m 4+3m 0 -m 0
El cuerpo de la tabla contiene los Coeficientes Tecnológicos
Maximizar Z = 3 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 2 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M+ S ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 6 6/2=3
H2 0 2 1 0 1 0 4 4/1=4
H3 0 1 1 0 0 1 5 5/1=5
Z -2m -3m -m m 0 -10m
U-Z 1+2m 4+3m 0 -m 0
La última columna tiene los Recursos
Maximizar Z = 3 M + 4 S + 0 H1 + 0 H2 + 0 H3
Z= 3 M+ 4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 = 24
Sujeto a: 2 M + 1 S + 0 H1 + 1 H2 + 0 H3 = 24
M + 2 S ≤ 24 1 M + 1 S + 0 H1 + 0 H2 + 1 H3 = 15
2M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M+ S ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24 6/2=3
H2 0 2 1 0 1 0 24 4/1=4
H3 0 1 1 0 0 1 15 5/1=5
Z -2m -3m -m m 0 -10m
U-Z 1+2m 4+3m 0 -m 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2.36
Para esta solución, las variables de la primera columna con la asignación de la última columna. Si
alguna variable no se encuentra entre las variables de la primera columna, su asignación es 0.
De acuerdo con el tableau anterior, la solución es:
H1=24, Se desperdician: 24 Horas hombre,
H2 = 24, 24 hojas de triplay y
H3 = 15, 15 bancos de trabajo,
M = 0, se fabrican 0 mesas y
S =0. 0 sillas
1.5.2.6.3.4.
3 Cálculo de Utilidades Parciales
Cada celda contiene la suma delos productos de la segunda columna por la columna que se encuentra
por encima de esa celda. El último valor de este renglón tiene el valor de la utilidad con esta solución
básica:
2
2M + S ≤ --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
4
1 H3
M+ S≤ ¿? M S H1 H2
5 R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24
4/1=
H2 0 2 1 0 1 0 24
4
5/1=
H3 0 1 1 0 0 1 15
5
0*2+0*1+0* 0*1+0*0+0* 0*0+0*1+0* 0*1+0*2+0* 0*24+0*24+0*1
0*1+0*2+0*1
Z 1 0 0 1 5
=0 =0 =0 =0 =0 =0
U-Z 1+2m 4+3m 0 -m 0

Así en esta solución: Z = 0 La utilidad

1.5.2.6.3.5.
4 Cálculo del Renglón Discriminante
La diferencia del primer renglón menos el penúltimo. Si solo tiene valores negativos o ceros, ya no se
puede optimizar más y se acabó. Entonces la solución básica corresponde a las variables de la primera
columna con los valores de la última columna.
Si hay algún valor positivo, continúe en el siguiente paso

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 37
2 M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M + S ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24
H2 0 2 1 0 1 0 24 4/1=4
H3 0 1 1 0 0 1 15 5/1=5
Z 0 0 0 0 0 0
3-0= 4-0= 0-0= 0-0= 0-0=
U-Z
3 4 0 0 0
Aquí hay valores positivos:
Y por lo tanto no hemos terminado, continuamos con el siguiente paso (5).
1.5.2.6.3.6.
5 Columna Pivote
Se elije el mayor entero positivo de los valores del renglón discriminante, lo que selecciona la columna
pivote. En el primer renglón en esta columna se indica la variable que entrará a la solución básica (con la
utilidad indicada en el segundo renglón de dicha columna.
Aquí el mayor valor positivo es:
4 por lo tanto la columna de la variable S es la columna pivote, en la siguiente iteración (si la hay, ya
que hay algún valor positivo en el renglón pivote), en las soluciones básicas entra S con su4

2 M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M + S ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24
H2 0 2 1 0 1 0 24 4/1=4
H3 0 1 1 0 0 1 15 5/1=5
Z 0 0 0 0 0 0
U-Z 3 4 0 0 0
Si hubiera varios con el mismo valor, se puede seleccionar cualquiera, se sugiere usar el de la derecha
(den ser posible no se seleccione ninguna variable artificial)

1.5.2.6.3.7.
6 Renglón Pivote
Para seleccionar el renglón pivote, se dividen los recursos entre el valor correspondiente de la columna
pivote y seleccione el menor positivo diferente de cero
Como hay valores mayores que cero, continuamos

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2.38
Si hubiera varios candidatos, seleccionamos el de arriba (de ser posible, seleccionar una variable
artificial)
2 M + S ≤ 24 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
M + S ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24 24/2=12
H2 0 2 1 0 1 0 24 24/1=24
H3 0 1 1 0 0 1 15 15/1=15
Z 0 0 0 0 0 0
U-Z 3 4 0 0 0
El menor positivo es 12, por lo que la variable que sale de la solución básica es H 1 con su 0, y en su
lugar entra S con su 4
La celda que se encuentra en la intersección entre el renglón pivote y la columna pivote, es el pivote.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 39
1.5.2.6.3.8.
7 Nuevo Tableau
El nuevo tableau repite los dos primeros renglones. En la primera columna, con las variables que antes
tenía, sale la variable del renglón pivote y entra la variable de la columna pivote. En la segunda columna,
se reemplaza el valor del renglón pivote por el de la utilidad de la columna pivote, pues a las variables
siempre las acompaña su utilidad

X+ Y ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24 24/2=12
H2 0 2 1 0 1 0 24 24/1=24
H3 0 1 1 0 0 1 15 15/1=15
Z 0 0 0 0 0 0
U-Z 3 4 0 0 0

m ¿? M S H2 H2 H3
R
U 3 4 0 -m 0
S 4
H2 0
H3 0
Z
U–Z

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 40
1.5.2.6.3.9.
8 Nueva columna pivote
La celda pivote debe tener 1 y todas las demás Coeficientes Tecnológicos de la columna deben tener
0.Esta columna debe tener un 1 en el pivote y ceros en los otros renglones.

X+ Y ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24 24/2=12
H2 0 2 1 0 1 0 24 24/1=24
H3 0 1 1 0 0 1 15 15/1=15
Z 0 0 0 0 0 0
U-Z 3 4 0 0 0

m ¿? M S H2 H2 H3
R
U 3 4 0 -m 0
S 4 1
H2 0 0
H3 0 0
4*1+0*0+0*0=
Z
4
4-4=
U–Z
0

Para que la suma de productos de los valores de la segunda columna por los de la columna pivote
resulten en la utilidad de dicha columna, y que para obtener la celda del renglón determinante en esta
columna resulte en 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2.41
Las otras variables de la solución básica tienen 1 en la columna respectiva (rotulada con esa misma
variable), acompañado de ceros en los otros renglones de esa columna. Estos resultados permiten ratificar
los siguientes cálculos.
1 H3
X+ Y≤ ¿? M S H1 H2
5 R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24 24/2=12
H2 0 2 1 0 1 0 24 24/1=24
H3 0 1 1 0 0 1 15 15/1=15
Z 0 0 0 0 0 0
U-Z 3 4 0 0 0

m ¿? M S H2 H2 H3
R
U 3 4 0 0 0
S 4 1 0 0
H2 0 0 1 0
H3 0 0 0 1
Z 4
U–Z 0

1.5.2.6.3.10.
9 Nuevo renglón pivote
Para lograr que el pivote sea 1: divida el renglón pivote entre el pivote.
X + Y ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24 24/2=12
H2 0 2 1 0 1 0 24 24/1=24
H3 0 1 1 0 0 1 15 15/1=15
Z 0 0 0 0 0 0
U-Z 3 4 0 0 0

1 2 1 0 0 24 /2
.5 1 .5 0 0 12 ¿? M S H2 H2 H3
R
U 3 4 0 0 0
1/2= 2/2= 1/2= 0/2= 0/2= 24/2=
S 4
.5 1 .5 0 0 12
H2 0 0 1 0
H3 0 0 0 1
Z 4
U–Z 0
Los resultados ya escritos ratifican la corrección del procedimiento.
© [email protected] Lecturas 2 Programación lineal
 UABC Ensenada B.C. México (414) 1.5.2. 42
1.5.2.6.3.11.
10 Cálculo de los demás Renglones
Para lograr que la celda correspondiente a la columna pivote sea 0, al renglón que vamos a trabajar le
restamos en nuevo renglón pivote multiplicado por el valor en la celda de la columna pivote
correspondiente a éste renglón.
X + Y ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24 24/2=12
H2 0 2 1 0 1 0 24 24/1=24
H3 0 1 1 0 0 1 15 15/1=15
Z 0 0 0 0 0 0
U-Z 3 4 0 0 0

1 2 1 0 0 24 /2
.5 1 .5 0 0 12 ¿? M S H2 H2 H3
R
2 1 0 1 0 24 U 3 4 0 0 0
.5 1 .5 0 0 12 *1 S 4 .5 1 .5 0 0 12
2-.5(1)= 1-1(1)= 0-.5(1)= 1-0(1)= 0-0(1)= 24-12(1)=
1.5 0 -.5 1 0 12 H2 0
1.5 0 -.5 1 0 12

H3 0 0 0 1
Z 4
U-Z 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 43
1.5.2.6.3.11.1.
10 bis Cálculo de los demás Renglones
Y con los demás renglones, lo mismo:
X + Y ≤ 15 ¿? M S H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 24 24/2=12
H2 0 2 1 0 1 0 24 24/1=24
H3 0 1 1 0 0 1 15 15/1=15
Z 0 0 0 0 0 0
U-Z 3 4 0 0 0

1 2 1 0 0 24 /2
.5 1 .5 0 0 12 ¿? M S H2 H2 H3
R
2 1 0 1 0 24 U 3 4 0 0 0
.5 1 .5 0 0 12 *1 S 4 .5 1 .5 0 0 12
1.5 0 -.5 1 0 12 H2 0 1.5 0 -.5 1 0 12

1-.5(1)= 1-1(1)= 0-.5(1)= 0-0(1)= 1-0(1)= 15-12(1)=

1 1 0 0 1 15 H3 0
.5 0 -.5 0 1 3
.5 1 .5 0 0 12 *1 Z 4
.5 0 -.5 0 1 3 U-Z 0

Que resulta en:

De acuerdo con el tableau anterior, la solución es:
S=12, H2=12, H3 =3, H1=0, M =0
Al fabricar 12 sillas, sobran 12 hojas de triplay y quedan libres 3bancos de trabajo, no desperdicio
horas hombre y no fabrico mesas.
1.5.2.6.3.12.
Continuación del algoritmo
Como lo indica el diagrama de flujo, brinca a 3
1.5.2.6.3.12.1.
3 Cálculo de Utilidades Parciales
1 2 1 0 0 24 /2
.5 1 .5 0 0 12 ¿? M S H2 H2 H3
R
2 1 0 1 0 24 U 3 4 0 0 0
.5 1 .5 0 0 12 *1 S 4 .5 1 .5 0 0 12
1.5 0 -.5 1 0 12 H2 0 1.5 0 -.5 1 0 12

1 1 0 0 1 15 H3 0 .5 0 -.5 0 1 3
4(.5)+0(1.5)+0(.5) 4(1)+0(0)+0(0) 4(.5)+0+0 0+0+0 0+0+0 4(12)+0(12)+0(3)
.5 1 .5 0 0 12 *1 Z
=2 =4 =2 =0 =0 =48
.5 0 -.5 0 1 3 U-Z 0

Solución que tiene una utilidad de $48. Por la fabricación de 12 sillas

© [email protected] Lecturas 2 Programación lineal
 UABC Ensenada B.C. México (414) 1.5.2. 44
1.5.2.6.3.12.2.
4 Calculo de Renglón Discriminante
1 2 1 0 0 24 /2
.5 1 .5 0 0 12 ¿? M S H2 H2 H3
R
2 1 0 1 0 24 U 3 4 0 0 0
.5 1 .5 0 0 12 *1 S 4 .5 1 .5 0 0 12
1.5 0 -.5 1 0 12 H2 0 1.5 0 -.5 1 0 12

1 1 0 0 1 15 H3 0 .5 0 -.5 0 1 3
.5 1 .5 0 0 12 *1 Z 2 4 2 0 0 48
3-2= 4-4= 0-2= 0-0= 0-0=
.5 0 -.5 0 1 3 U-Z
1 0 -2 0 0
Como hay un valor positivo, no hemos terminado

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 45
1.5.2.6.3.12.3.
5 Determina Columna Pivote
1 2 1 0 0 24 /2
.5 1 .5 0 0 12 ¿? M S H2 H2 H3
R
2 1 0 1 0 24 U 3 4 0 0 0
.5 1 .5 0 0 12 *1 S 4 .5 1 .5 0 0 12
1.5 0 -.5 1 0 12 H2 0 1.5 0 -.5 1 0 12

1 1 0 0 1 15 H3 0 .5 0 -.5 0 1 3
.5 1 .5 0 0 12 *1 Z 2 4 2 0 0 48
.5 0 -.5 0 1 3 U-Z 1 0 -2 0 0

1.5.2.6.3.12.4.
6 Determina Renglón Pivote
1 2 1 0 0 24 /2
.5 1 .5 0 0 12 ¿? M S H2 H2 H3
R
2 1 0 1 0 24 U 3 4 0 0 0
.5 1 .5 0 0 12 *1 S 4 .5 1 .5 0 0 12 12/.5=24
1.5 0 -.5 1 0 12 H2 0 1.5 0 -.5 1 0 12 12/1.5=8
1 1 0 0 1 15 H3 0 .5 0 -.5 0 1 3 3/.5=6
.5 1 .5 0 0 12 *1 Z 2 4 2 0 0 48
.5 0 -.5 0 1 3 U-Z 1 0 -2 0 0

1.5.2.6.3.12.5.
7 Nuevo Tableau
1 2 1 0 0 24 /2
.5 1 .5 0 0 12 ¿? M S H2 H2 H3
R
2 1 0 1 0 24 U 3 4 0 0 0
.5 1 .5 0 0 12 *1 S 4 .5 1 .5 0 0 12 12/.5=24
1.5 0 -.5 1 0 12 H2 0 1.5 0 -.5 1 0 12 12/1.5=8
1 1 0 0 1 15 M 3 .5 0 -.5 0 1 3 3/.5=6
.5 1 .5 0 0 12 *1 Z 2 4 2 0 0 48
.5 0 -.5 0 1 3 U-Z 1 0 -2 0 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 46
1.5.2.6.3.12.6.
8 Nueva Columna Pivote
1 2 1 0 0 24 /2
.5 1 .5 0 0 12 ¿? M S H2 H2 H3
R
2 1 0 1 0 24 U 3 4 0 0 0
.5 1 .5 0 0 12 *1 S 4 0 1 .5 0 0 12 12/.5=24
1.5 0 -.5 1 0 12 H2 0 0 0 -.5 1 0 12 12/1.5=8
1 1 0 0 1 15 M 3 1 0 -.5 0 1 3 3/.5=6
.5 1 .5 0 0 12 *1 Z 2 4 2 0 0 48
.5 0 -.5 0 1 3 U-Z 1 0 -2 0 0

1.5.2.6.3.12.7.
9 Nuevo Renglón Pivote
.5 0 -.5 0 1 3 /.5
1 0 -1 0 2 6 ¿? M S H2 H2 H3
R
2 1 0 1 0 24 U 3 4 0 0 0
.5 1 .5 0 0 12 *1 S 4 0 1 .5 0 0 12 12/.5=24
1.5 0 -.5 1 0 12 H2 0 0 0 -.5 1 0 12 12/1.5=8
1 1 0 0 1 15 M 3 1 0 -1 0 2 6 3/.5=6
.5 1 .5 0 0 12 *1 Z 2 4 2 0 0 48
U-Z 1 0 -2 0 0

1.5.2.6.3.12.8.
10 Calculo de otros renglones
.5 0 -.5 0 1 3 /.5
1 0 -1 0 2 6 ¿? M S H2 H2 H3
R
.5 1 .5 0 0 12 U 3 4 0 0 0
.5 0 -.5 0 1 3 *.5 S 4 0 1 1 0 -1 9
0 1 1 0 -1 9 H2 0
1 1 0 0 1 15 M 3 1 0 -1 0 2 6
.5 1 .5 0 0 12 *1 Z
U-Z

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 47
1.5.2.6.3.12.8.1.
10bis Calculo de otros renglones
.5 0 -.5 0 1 3 /.5
1 0 -1 0 2 6 ¿? M S H2 H2 H3
R
.5 1 .5 0 0 12 U 3 4 0 0 0
.5 0 -.5 0 1 3 *.5 S 4 0 1 1 0 -1 9
0 1 1 0 -1 9 H2 0 0 0 1 1 -3 3

1.5 0 -.5 1 0 12 M 3 1 0 -1 0 2 6
1.5 0 -1.5 0 3 9 *1.5 Z
0 0 1 1 -3 3 U-Z

1.5.2.6.3.12.9.
3 Calculo Utilidades Parciales
.5 0 -.5 0 1 3 /.5
1 0 -1 0 2 6 ¿? M S H2 H2 H3
R
.5 1 .5 0 0 12 U 3 4 0 0 0
.5 0 -.5 0 1 3 *.5 S 4 0 1 1 0 -1 9
0 1 1 0 -1 9 H2 0 0 0 1 1 -3 3

1.5 0 -.5 1 0 12 M 3 1 0 -1 0 2 6
4-3= -4+6= 36+18=
1.5 0 -1.5 0 3 9 *1.5 Z 3 4 0
1 2 54
0 0 1 1 -3 3 U-Z

1.5.2.6.3.12.10.
3 Calculo Renglón Discriminante
.5 0 -.5 0 1 3 /.5
1 0 -1 0 2 6 ¿? M S H2 H2 H3
R
.5 1 .5 0 0 12 U 3 4 0 0 0
.5 0 -.5 0 1 3 *.5 S 4 0 1 1 0 -1 9
0 1 1 0 -1 9 H2 0 0 0 1 1 -3 3

1.5 0 -.5 1 0 12 M 3 1 0 -1 0 2 6
1.5 0 -1.5 0 3 9 *1.5 Z 3 4 1 0 2 54
0 0 1 1 -3 3 U-Z 0 0 -1 0 -2

Como no hay valores positivos hemos terminado:

S=9 M=6 H1=0 H2=3 H3=0 Z=54
Fabríquense 9 sillas, 6 mesas, y sobrarán 3 hojas de triplay, los recursos humanos y el equipo se usan
completamente.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 48
1.5.2.6.3.13.
Ejercicio
Maximizar Z= 4 X + 3 Y + 0 H1 + 0 H2
Z=4X + 3Y 1 X + 1 Y + 1 H1 + 0 H2 = 4
Sujeto a: +2 X + 1 Y + 0 H1 + 1 H2 = 6
X + Y <4
2X + Y <6

¿? X Y H1 H2
R
U 4 3 0 0
H1 0 1 1 1 0 4 4/1=4
0
H2 0 2 1 0 1 6 6/2=3
Z 0 0 0 0 0
U-Z 4 3 0 0

2 1 0 1 6 / 2 ¿? X Y H1 H2
R
1 0.5 0 .5 3 NuevoPivote U 4 3 0 0
H1 0 0 .5 1 -.5 1 1/.5=2
1 1 1 0 4 X 4 1 .5 0 .5 3 3/.5=6

1 .5 0 .5 3 * 1 Z 4 2 0 2 12

0 .5 1 -.5 1 OtroRenglón U-Z 0 1 0 -2

0 .5 1 -.5 1 / .5 ¿? X Y H1 H2
R
0 1 2 -1 2 NuevoPivote U 4 3 0 0
Y 3 0 1 2 -1 2
1 .5 0 .5 3 X 4 1 0 -1 1 2
0 .5 1 -.5 1 * .5 Z 4 3 2 1 14
1 0 -1 1 2 OtroRenglón U-Z 0 0 -2 -1

X= 2 Y= 24 Z= 14 H1= 0 H2= 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 49
1.5.2.6.3.13.1.
Ejercicio
Maximizar Z= 4 X + 3 Y + 0 H1 + 0 H2
Z=4X + 3Y 1 X + 1 Y + 1 H1 + 0 H2 = 4
Sujeto a: +2 X + 1 Y + 0 H1 + 1 H2 = 6
X+ Y<4
2X + Y < 6

¿? X Y H1 H2
R
U 4 3 0 0
H1 0 1 1 1 0 4 4/1=4
0
H2 0 2 1 0 1 6 6/1=6

Z 0 0 0 0 0
U-Z 4 3 0 0

1 1 1 0 4 / 1 ¿? X Y H1 H2
R
1 1 1 0 4 NuevoPivote U 4 5 0 0
X 4 1 1 1 0 4
2 1 0 1 6 H2 0 1 0 -1 1 2
1 1 1 0 4 * 1 Z 5 5 5 0 20
1 0 -1 1 2 OtroRenglón U-Z -1 0 0 0

1.5 0 -.5 1 6 / 1.5 ¿? X Y H1 H2

R
1 0 -.3 .6 4 NuevoPivote U 4 5 0 0
Y 4 0 1 .6 -.3 4
.5 1 .5 0 6 X 4 1 0 -.3 .6 4
.5 0 -.16 .3 2 * .5 Z 4 5 2 1 36
0 1 .6 -.3 4 OtroRenglón U-Z 0 0 -2 -1

X= 1 Y= 4 Z= 16 H1= 0 H2= 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 50
1.5.2.6.3.13.2.
Ejercicio
Maximizar por el método Simplex:
Maximizar Z = 3 X + 4 Y - 0 H1 + 0 H2 + 0 H3
Z= 3 X +4 Y 1 X + 2 Y + 1 H1 + 0 H2 + 0 H3 = 6
Sujeto a: 2 X + 1 Y + 0 H1 + 1 H2 + 0 H3 = 4
X + 2 Y ≤ 12 1 X + 1 Y + 0 H1 + 0 H2 + 1 H3 = 5
2X+ Y ≤ 12 --- --- --- --- --- -- -- -- -- -- -- -- -- -- --- --- --- --- ---
X+ Y≤ 7 ¿? X Y H1 H2 H3
R
U 3 4 0 0 0
H1 0 1 2 1 0 0 12 12/2=6
H2 0 1 1 0 1 0 12 12/1=12
H3 0 1 1 0 0 1 7 7/1=7
Z 0 0 0 0 0 0
U-Z 3 4 0 0 0

1 2 1 0 0 12 /2
.5 1 .5 0 0 6 ¿? X Y H1 H2 H3
R
1 1 0 1 0 12 U 3 4 0 0 0
.5 1 .5 0 0 6 *1 Y 4 .5 1 .5 0 0 6 6/.5 = 12
.5 0 -.5 1 0 6 H2 0 .5 0 -.5 1 0 6 6/.5 = 12
1 1 0 0 1 7 H3 0 .5 0 -.5 0 1 1 1/.5 = 2
.5 1 .5 0 0 6 *1 Z 2 4 2 0 0 24
.5 0 -.5 0 1 1 U-Z 1 0 -2 0 0

.5 0 -.5 0 1 1 /.5
1 0 -1 0 2 2 ¿? X Y H1 H2 H3
R
.5 1 .5 0 0 6 U 3 4 0 0 0
.5 0 -.5 0 1 1 *.5 Y 4 0 1 1 0 -1 5
0 1 1 0 -1 5 H2 0 0 0 0 1 -1 5

.5 0 -.5 1 0 6 X 3 1 0 -1 0 2 2
.5 0 -.5 0 1 1 *.5 Z 3 4 1 0 2 26
0 0 0 1 -1 5 U-Z 0 0 -1 0 -2

X= 2 Y = 5 Z = 26 H1 = 0 H2 = 5 H3 = 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 51
1.5.2.6.3.14.
Desigualdades por ≥
Como ahora la solución 0,0no es factible, se requiere una nueva variable de desgaste, una artificial
que se soporta hasta que desaparezca, después de esto se descarta dicha variable, pues ya se trata de una
solución factible. La holgura, ahora sobra, en vez de faltar, indica exceso, por eso se resta.
El algoritmo continúa con el mismo método. Como ejemplo al problema ejemplo le añadiremos la
restricción 3*M + 4M ≥ 52
MaximizarZ=1*M + 4 S
Sujeto a las restricciones:
1*M ≥0
1*S ≥ 0
1*M + 2*S ≤ 24
1*M + 1*S ≤ 15
3*M + 4*S ≥ 54
Holguras:
Se resta una holgura y se suma una artificial altamente penalizada (-m)5
3*M+ 4*S+0*H1+0*H2-1*H3 + 1*A3= 54

Maximizar Z= 1 M + 4 S + 0 H1 + 0 H2 + 0 H3 - m A3
Z= M+4 S 1 M + 2 S + 1 H1 + 0 H2 + 0 H3 + 0 A3 = 24
Sujeto a: 1 M + 1 S + 0 H1 + 1 H2 + 0 H3 + 0 A3 = 15

M + 2 S ≤ 24 3 M + 4 S + 0 H1 + 0 H2 - 1 H3 + 1 A3 = 24

M+ S ≤ 15 --- --- --- --- --- -- -- -- -- -- -- -- -- -- -- --- --- --- --- --- --- ---

3 M + 4 S ≥ 24 ¿? X Y A1 H2 A2 H3 R

En este caso m significa un número suficientemente grande para que no pueda ser tomado en cuenta. Puede ser un número
5

mayor que cualquiera de los que aparezcan en el TABLEAU. Para facilitar las cosas imagínese que es un millón
© [email protected] Lecturas 2 Programación lineal
 UABC Ensenada B.C. México (414) 1.5.2. 52
Maximizar por el método Simplex
Maximizar Z= 1 M + 4 S + 0 H1 + 0 H2 + 0 H3 - m A3
Z = M+ 4 S 1 M + 2S + 1 H1 + 0 H2 + 0 H3 + 0 A3 = 24
Sujeto a: 1 M + 1S + 0 H1 + 1 H2 + 0 H3 + 0 A3 = 15
M + 2 S ≤ 24 3 M + 4S + 0 H2 + 0 H2 - 1 H3 + 1 A3 = 24
M + S ≤ 15
3 M + 4 S ≥ 24 ¿? M S H1 H2 H3 A3
R
U 1 4 0 0 0 -m

H1 0 1 2 1 0 0 0 24 24/2=12
H2 0 1 1 0 1 0 0 15 15/1=15
A3 -m 3 4 0 0 -1 1 24 24/4=6
Z -3m -4m 0 0 m -m -24m
U-Z 1+3m 4+4m 0 0 -m 0

3 4 0 0 -1 24
.75 1 0 0 -.25 6 ¿? M S H1 H2 H3
R
1 2 1 0 0 24 U 1 4 0 0 0
1.5 2 0 0 -.5 12 H1 0 -.5 0 1 0 .5 12 12/.5=24
-.5 0 1 0 .5 12 H2 0 .25 0 0 1 .25 18 18/.25=72
1 1 0 1 0 24 S 4 .75 1 0 0 -.25 6 6/-.25=-24
.75 1 0 0 -.25 6 Z 3 4 0 0 -1 24
.25 0 0 1 .25 18 U-Z -2 0 0 0 1

-.5 0 1 0 .5 12
-1 0 2 0 1 24 ¿? M S H1 H2 H3
R
.25 0 0 1 .25 18 U 1 4 0 0 0
-.25 0 .5 0 .25 6 H3 0 -1 0 2 0 1 24
.5 0 -.5 1 0 12 H2 0 .5 0 -.5 1 0 12
.75 1 0 0 -.25 6 S 4 .5 1 .5 0 0 12
.25 0 -.5 0 -.25 -6 Z 2 4 2 0 0 48
.5 1 .5 0 0 12 U–Z -1 0 -2 0 0

4 H1 H2=12 H
M= 0 S = 12 Z= 0 = 24
8 = 3

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 53
1.5.2.6.3.15.
Desigualdades por =
Como ahora la solución 0,0 no es factible, se requiere una nueva variable de desgaste, una artificial
que se soporta hasta que desaparezca, después de esto se descarta dicha variable, pues ya se trata de una
solución factible. El algoritmo continúa con el mismo método. La holgura no es necesaria pues ya es una
ecuación.
Como ejemplo al problema ejemplo le añadiremos la restricción 3*M + 4M ≥ 52
Maximizar Z=1*M + 4*S
Sujeto a las restricciones:
1*M ≥0
1*S ≥ 0
1*M + 2*S = 24
1*M + 1*S ≥ 15
3*M + 4*S ≤ 54
Holguras:
Se suma una artificial altamente penalizada (-m)
1*M + 2*S + 1*A1+0*H2-1*H3 + 1*A3= 24

Maximizar Z= 1 M + 4 S - m A1 + 0 H2 - m A2 + 0 H3
Z= M+4 S 1 M + 2 S + 1 A1 + 0 H2 + 0 A2 + 0 H3 = 24
Sujeto a: 1 M + 1 S + 0 A1 - 1 H2 + 1 A2 + 0 H3 = 15
M + 2 S = 24 3 M + 4 S + 0 A1 + 0 H2 + 0 A2 + 1 H3 = 54

M+ S ≥ 15 --- --- --- --- --- -- -- -- -- -- -- -- -- -- -- --- --- --- --- --- --- ---

3 M + 4 S ≤ 54 ¿? X Y A1 H2 A2 H3 R

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 54
Maximizar por el método Simplex
Maximizar Z= 1 M + 4 S - m A1 + 0 H2 - m A2 + 0 H3
Z = M+ 4 S 1 M + 2 S + 1 A1 + 0 H2 + 0 A2 + 0 H3 = 24
Sujeto a: 1 M + 1 S + 0 A1 - 1 H2 + 1 A2 + 0 H3 = 15
M + 2 S = 24 3 M + 4 S + 0 A1 + 0 H2 + 0 A2 + 1 H3 = 54
M+ S ≥ 15
3 M + 4 S ≤ 54 ¿? M S A1 H2 A2 H3
R
U 1 4 -m 0 -m 0
A1 -m 1 2 1 0 0 0 24 24/2=12
A2 -m 1 1 0 -1 1 0 15 15/1=15
H3 0 3 4 0 0 0 1 54 54/4=13.5
Z -2m -3m -m m -m 0 -10m
U-Z 1+2m 4+3m 0 -m 0 0

1 2 0 0 0 24
.5 1 0 0 0 12 ¿? M S H2 A2 H3
R
1 1 -1 1 0 15 U 1 4 0 -m 0
.5 1 0 0 0 12 S 4 .5 1 0 0 0 12 12/.5 = 24
.5 0 -1 1 0 3 A2 -m .5 0 -1 1 0 3 3/.5 = 6
3 4 0 0 1 54 H3 0 1 0 0 0 1 6 6/1 = 6
2 4 0 0 0 48 Z 2-.5m 4 m -m 0 48-3m Podría elegirse
1 0 0 0 1 6 U-Z -1+.5m 0 -m 0 0 cualquier renglón,
pero preferimos la
.5 0 -1 0 3 artificial Siempre

1 0 -2 0 6 ¿? M S H2 H3
R
.5 1 0 0 12 U 1 4 0 0
.5 0 -1 0 3 S 4 0 1 1 0 9
0 1 1 0 9 M 1 1 0 -2 0 6
1 0 0 1 6 H3 0 0 0 2 1 0
1 0 -2 0 6 Z 1 4 2 0 42
0 0 2 1 0 U–Z 0 0 -2 0

M= 6 S = 9 Z = 42 H2 = 0 H3 = 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 55
1.5.2.6.4.
Minimización
Se hace negativa la función objetivo. Al terminar invertir el resultado de la utilidad.

Minimizar Z=2*X + 3 Y
Maximizar Z=-2*X - 3 Y

Sujeto a las restricciones:

1*X ≥0
1*Y ≥0
1*X + 1*Y ≤7
2*X + 1*Y ≥6
1*X + 1*Y ≥4
Holguras:
Maximizar Z= - 2 X - 3Y +4X
Z = -2 X - 3 Y 1 X +1Y
Sujeto a: 2 X +1Y
1X + Y≤ 7 1 X +1Y
2X + Y≥ 6 --- --- --- --- --- -- -- -- -- -- -- -- -- -- -- --- --- --- --- --- --- ---

1X + Y≥ 4 ¿? X Y R

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 56
Maximizar por el método Simplex
Maximizar Z= - 2 X - 3 Y + 0 H 1 + 0 H 2 - m A2 + 0 H 3 - m A3
Z = -2 X - 3 Y 1 X + 1 Y + 1 H 1 + 0 H 2 + 0 A2 + 0 H 3 + 0 A3 = 7
Sujeto a: 2 X + 1 Y + 0 H 1 - 1 H 2 + 1 A2 + 0 H 3 + 0 A3 = 6
1 X + 1 Y ≤ 7 1 X + 1 Y + 0 H 1 + 0 H 2 + 0 A2 - 1 H 3 + 1 A3 = 4
2 X + 1 Y ≤ 6
1 X + 1 Y ≥ 4 ¿? X Y H1 H2 A2 H3 A3
R
U -2 -3 0 0 -m 0 -m

H1 0 1 1 1 0 0 0 0 7 7/1=7
A2 -m 2 1 0 -1 1 0 0 6 6/2=3
A3 -m 1 1 0 0 0 -1 1 4 4/1=4
Z -3m -2m 0 m -m m -m -39m
U-Z -2+3m -3+2m 0 -m 0 -m 0

2 1 0 -1 0 0 6 X

1 1/2 0 -1/2 0 0 3 ¿? X Y H1 H2 H3 A3
R
1 1 1 0 0 0 7 U -2 -3 0 0 0 -m
1 1 / 2 0 -1 / 2 0 0 3 H 1 0 0 1/2 1 1/2 0 0 4 4/½=8
0 ½ 1 ½ 0 0 4 X -2 1 ½ 0 -1 / 2 0 0 3 3 / 1/2 =6

1 1 0 0 -1 1 4 A3 -m 0 1/2 0 1/2 -1 1 1 1/½=2

1 1 / 2 0 -1 / 2 0 0 3 Z -2 -1-1/2m 0 1-1/2m m -m -6-m
0 1/2 0 1/2 -1 1 1 U-Z 0 -2+1/2m 0 -1+1/2m -m 0

0 1/2 0 1/2 -1 1
0 1 0 1 -2 2 ¿? X Y H1 H2 H3
R
0 1/2 1 1/2 0 4 U -2 -3 0 0 0
0 1/2 0 1/2 -1 1 H1 0 0 0 1 0 1 3
0 0 1 0 1 3 X -2 1 0 0 -1 1 2
1 ½ 0 -1 / 2 0 3 Y -3 0 1 0 1 -2 2
0 1/2 0 1/2 -1 1 Z -2 -3 0 1 4 -10
1 0 0 -1 1 2 U–Z 0 0 0 -1 -4

X = 2 Y = 2 Z = 10 H1= 3 H2=0 H3 = 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 57
1.5.2.6.5.
Casos especiales:
Como siempre las soluciones se vuelven difíciles cuando el problema se acerca al límite de factibilidad
para el método de solución. Existen combinaciones de datos que conllevan a situaciones especiales, y
requieren de la experiencia y criterio del analista para lograr una solución adecuada.
Analicemos los casos de Degeneración, Soluciones múltiples, Soluciones no acotadas, y por último,
inexistencia de soluciones
1.5.2.6.5.1.
Degeneración
Z
Maximizar 3 X + 9 Y + 0 H1 + 0 H2
=
Z =3 X + 9 Y 1 X + 4 Y + 1 H1 + 0 H2 = 8
Sujeto a: 1 X + 2 Y + 0 H1 + 1 H2 = 4
1 X + 4 Y ≤ 8
1 X + 2 Y ≤ 4
¿? X Y H1 H2
R
U 3 9 0 0
H1 0 1 4 1 0 8 8/4=2
H2 0 1 2 0 1 4 4/2=2
Z 0 0 0 0 0
U-Z 3 9 0 0

¿? X Y H1 H2
R
1 4 1 0 8 / 4 U 3 9 0 0
.25 1 .25 0 2 Y 9 .25 1 .25 0 2 2/.25=8
1 2 0 1 4 H2 0 .5 0 -.5 1 0 0/.5=0
.5 2 .5 0 4 * 2 Z 2.25 9 2.25 0 18
.5 0 -.5 1 0 U-Z .75 0 -2.25 0

¿? X Y H1 H2
R
.25 1 .25 0 2 / .25 U 3 9 0 0
1 4 1 0 8 X 3 1 4 1 0 8
.5 0 -.5 1 0 H2 0 0 -2 -1 1 -4

.5 2 .5 0 4 3 12 3
0 24

0 -2 -1 1 -4 U–Z 0 -3 -3 0

X = 8 Y = 0 Z = 24 H2= -4

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 58

Maximizar Z= 3 X + 9 Y + 0 H1 + 0 H2
Z =3 X + 9 Y 1 X + 4 Y + 1 H1 + 0 H2 = 8
Sujeto a: 1 X + 2 Y + 0 H1 + 1 H2 = 4
1 X + 4 Y ≤ 8
1 X + 2 Y ≤ 4
¿? X Y H1 H2
R
U 3 9 0 0
H1 0 1 4 1 0 8 8/4=2
H2 0 1 2 0 1 4 4/2=2
Z 0 0 0 0 0
U-Z 3 9 0 0

¿? X Y H1 H2
R
U 3 9 0 0

Z
U-Z

¿? X Y H1 H2
R
U

U–Z

X = Y = Z = H1=

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 59
http://148.204.211.134/polilibros/portal/polilibros/P_Terminados/InvOper1Virg/InvOperac/UMD/Unid
ad%204/Contenido/Casos%20Especiales/degeneracion.htm

Método de
1.5.2.6.5.1.1.

Perturbación

1.5.2.6.5.1.2.
Método Léxico-
Gráfico.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 60
1.5.2.6.5.2.
Soluciones Múltiples

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 61
1.5.2.6.5.3.
Soluciones no acotadas

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 62
1.5.2.6.5.4.
Soluciones no factibles.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 63
1.5.2.7.
Métodos Computacionales.
Existen una gran cantidad de paquetes de cómputo que permiten resolver estos problemas, en cada
plataforma y en cada ambiente operativo.
También existen muchas plataformas para su solución, pero la mas empleada (que no la única, ni la
mejor) es la PC compatible, que dadas las condiciones actuales de prestaciones es suficiente para la
solución de la mayor parte de los problemas profesionales actuales. Sin embargo, para la resolución de
grandes problemas planteados por inmensas empresas transnacionales, que además requieren una rápida
solución para la toma de decisiones (incluso automatizadas), si hace falta el uso de equipos de cómputo
de las midi y aún de las maxi computadoras. Por ejemplo, las operaciones militares del Ejercito de los
Estados Unidos.
En un ambiente como el nuestro, la plataforma mas económica es la PC, que se encuentra soportada
por el sistema operativos de Micosoft: Windows (que no es el único ni el mejor), pero los ambientes tipo
UNIX, solo son reservados para grandes conocedores de cómputo (“nerds”), y nosotros por falta de
tiempo para aprender otros sistemas usamos el Windows, lo que nos impide concebir su enorme
ineficiencia.
En el ambiente Windows existen una gran cantidad de paquetes y programas que pueden resolver
nuestros problemas, pero las soluciones, que tienen que ser anotadas para después ser utilizadas en el
reporte de resultados hace difícil su uso.
Como conclusión (personal) creo que el mas adecuado de los prospectos es el EXCEL del paquete
OFFICE de la marca MICROSOFT, que además es la marca propietaria del ambiente operativo
WINDOWS, lo que le da la máxima compatibilidad de operación, además de ser un paquete que aglutina
una gran cantidad de horas hombre de experiencia en su concepción y creación, dando lugar a un
ambiente de operación altamente amigable, soportable, poderoso y confiable.
Definitivamente, para los profesionales de las ciencias administrativas la mejor opción es esta.

Estos problemas se pueden resolver automáticamente con el paquete HTML de “Finite

mathematics&AppliedCaiculus”, que se detalla en el siguiente capítulo
1.5.2.7.1.
“Finite Mathematics&AppliedCalculus”
En esta página de internet, se encuentran muchas aplicaciones entre las cuales se ha identificado
las que usaremos como
Primera aproximación:
1.5.2.7.1.1.
Método gráfico6
En la aplicación cuyo vínculo se encuentra al pie de página, se debe usar la siguiente sintaxis:
• El primer renglón debe decir graph
• Los nombres de las variables deben ser x y y.
• Para fracciones la variable debe estar a la derecha, por ejemplo: ((1/3)x y no x/3)
• No se requiere introducir las restricciones x >= 0yy>= 0

6
Stefan Waner (http://www.zweigmedia.com/RealWorld/simplex.html) linear programminggrapher a UtilityforFinite
Mathematics and AppliedCalculus
© [email protected] Lecturas 2 Programación lineal
 UABC Ensenada B.C. México (414) 1.5.2. 64
• Una desigualdad en cada renglón, como se muestra en el siguiente ejemplo:
Graph
2x - y <= 4
2x + 3y <= 12
y <= 3
Esto se puede hacer automáticamente si selecciona: GraphingExample
Estas notas se escriben en inglés si se oprime la tecla Show LP example
Una vez que haya definido el problema si selecciona Solve aparecerá en la pantalla de
respuestas:
Vértices LíneasQueSeCruzan ValorDelObjetivo
Vertex LinesThroughVertex ValueOfObjective
(3,2) 2x-y = 4; 2x+3y = 12 11 Maximum
(2,0) 2x-y = 4; y = 0 6
(1.5,3) 2x+3y = 12; y = 3 7.5
(0,3) y = 3; x = 0 3
(0,0) x = 0; y = 0 0
Seleccionando Graph explota una nueva ventana con la gráfica en ella, la región de factibilidad
aparece en blanco.
Erase Everithing borra todo para volver a comenzar.
Los siguientes cuadros permiten modificar la exhibición del polígono de factibilidad:
Xmin y Xmax determinan los límites horizontales donde empieza y termina la gráfica exhibida.
Mientras que Ymin y Ymax delimitan las dimensiones verticales.
X-Gridlinesevery y Y-Gridlinesevery indican cada cuantas unidades se ponen las rayitas de
la cuadrícula. Se indica que se dejen en blanco si no quiere cuadrícula.
Round answers para indicar el número de cifras decimales que se quieren.
FractionMode para indicar si se manejarán fracciones comunes.
En la página “Finite Mathematics&AppliedCalculusResource Page”
http://www.zweigmedia.com/RealWorld/index.html, y específicamente “Finite mathematics utility: linear
programming grapher“:en http://www.zweigmedia.com/utilities/lpg/index.html?lang=es, puede
encontrarse una

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 65

. ejemplo.html

1.5.2.7.1.2.
Método Simplex7
En esta aplicación, en el vinculo ofrecido en el pie de página, y que ahora describimos permite
obtener la solución de sistemas de hasta
Se ofrece un tutorial8, que facilita el aprendizaje por parte del alumno. El principal problema es
la diferencia en la elaboración de tableaus.

7
Stefan Waner (http://www.zweigmedia.com/RealWorld/simplex.html) Simplex Method Tool a Utilityfor Finite
Mathematics and Applied Calculus
8Stefan Waner(http://www.zweigmedia.com/RealWorld/tutorialsf4/frames4_3.html) 4.3:
The Simplex Method: Solving Standard Maximization Problems Finite Mathematics and Applied
Calculus

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 66
1.5.2.7.1.3.
SCILAB®
function Xoptima=SIMPLEX(Utilidades, CoeficientesTecnologicos, Recursos)
Xoptima=karmarkar([],[],-Utilidades',[],[],[],[],[],CoeficientesTecnologicos,Recursos)
endfunction
Que una vez ejecutada permite ejecutar una función SIMPLEX cuyos argumentos son:
Utilidades columna con
U=[3,4]
U =
3. 4.

C=[1,2;2,1;1,1;-1,0;0,-1]
C =
1. 2.
2. 1.
1. 1.
-1. 0.
0. -1.

,R=[24;24;15;0;0]
R =
24.
24.
15.
0.
0.

X=SIMPLEX(U,C,R)
X =
6.
8.9998989

Z=U*X
Z = 53.999596

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 67

1.5.2.7.1.4.
EXCEL®
Una de las herramientas más ponderosas con que cuentan los profesionales de la
administración es esta Hoja de Datos comercial ofrecida por Microsoft. Ya que además
de ofrecer sus servicios como optimizador, permite el manejo de bases de datos,
tabulaciones, análisis estadísticos, y matemáticos en general, Graficación, presentación,
y programación. Su enorme valor agregado (algunos de los mejores programadores del
mundo, trabajando en equipo durante muchos años), ha logrado un paquete amigable y
que permite simplificar mucho el trabajo de usuarios y programadores. Además, ofrece:
Seguridad, liga a través de internet, una gran cantidad de programas accesorios, asesoría,
tutoría, documentación, compatibilidad, y finalmente, prácticamente todas las
computadoras PC lo tienen instalado.
Sus principales desventajas son: el precio, cierta dificultad en su programación sobre
todo en Visual y la enorme cantidad de recursos computacionales que requiere, haciendo
su trabajo dificultoso y lento.
En lo que a nosotros concierne, el uso de SOLVER, no se parece en nada a las técnicas
SIMPLEX recién estudiadas, pero sin embargo permite la solución de problemas no
lineales, que lo hacen aún más útil en el trabajo profesional
1.5.2.7.1.4.1.
SOLVER®
Este complemento permite optimizar una fórmula9 que debe depender directa o
indirectamente de ciertas celdas (variables de decisión), reservadas para que en ellas el
EXCEL ponga sus resultados, que deben estar sujetas a restricciones, en las que el lado
izquierdo es una fórmula (también dependiente directa o indirectamente de las variables
de decisión).
A diferencia de otros programas de computo, este no requiere del uso de sistemas
lineales de ecuaciones, pudiéndose usar cualquier función para su planteamiento, lo que
lo hace aún mas poderosa que los otros programas que solo dependen de sistemas lineales
de ecuaciones.
Inicialmente debe ser instaurado en el EXCEL, previamente a su uso. Una vez instalado
no se vuelve a requerir su instalación. Como las máquinas que se manejan pueden ser
públicas, y aún en las de uso propio en la primera vez, se requerirá dicha instalación, por
lo que a continuación se detalla esa secuencia de ejecuciones.
Las fases para su uso son:
• Instalación;
• Preparación y formulación;
• Argumentos;
• Afinaciones;

9
Conjunto de operaciones entre parámetros fijos y valores de otras celdas. Entre las operaciones cuenta
con muchas funciones preestablecidas (como tangente, o logaritmo) o definidas por el usuario.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 68
1.5.2.7.1.4.1.1.
Instalación

En el Botón de Office (icono arriba a su izquierda en el monitor) , se oprime la

tecla izquierda de su ratón. Aparece la siguiente ventana:

En la que hay que seleccionar , resultando en la siguiente ventana:

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 69

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 70

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 71

Ahora seleccionar en el cintillo izquierdo aparece la siguiente

ventana

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 72

Asegurarse que en la parte inferior esté seleccionado

, en cuyo caso de selecciona ir y aparece la

ventana:

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 73

En el que debe estar seleccionado el Solver con una palomita verde. Se selecciona el

recuadro . A partir de ahora el Icono de Solver aparecerá en el cintillo de

datos arriba a la derecha

, de donde lo hemos de invocar cada vez que así se requiera.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 74
1.5.2.7.1.4.1.2.
Preparación y Formulación
Para poder acceder a los datos adecuadamente se recomienda nombrar las diferentes
secciones, para fines didácticos las iluminaremos de diferentes colores

Resultados 6 9 Z
Utilidades 3 4 54.00002346 Recursos
Coeficientes
Tecnologicos 1 2 24 ≤ 24
2 3 39.00001173 ≥ 24
1 1 15.00001173 = 15
{=SUMA($B$2:$F$2*B6:F6)}
1.5.2.7.1.4.1.3.
Variables de decisión

Para poder usar el Solver, se requiere establecer:

1.5.2.7.1.4.1.3.1.
Celda Objetivo
Una celda que contenga una formula en función de las variables de decisión;
Contiene la suma de productos de las utilidades por las variables de decisión

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 75

{=SUMA($B$2:$F$2*B3:F3)}
1.5.2.7.1.4.1.4.
Sentido de la optimización
Se indica si la función objetivo se quiere minimizar, maximizar o hacer igual a un valor

1.5.2.7.1.4.1.5.
Variables de decisión
Un rango de celdas para la solución; EXCEL intentará mover estos valores, optimizando
la celda objetivo

Resultados 12 0

1.5.2.7.1.4.1.6.
Restricciones
Dos rangos de celdas de las mismas dimensiones:

24 ≤ 24
39.00001173 ≥ 24
15.00001173 = 15
{=SUMA($B$2:$F$2*B6:F6)}
1.5.2.7.1.4.1.6.1.
Parte variable.
Variables cuyos valores dependen de las Variables de decisión y los coeficientes
tecnológicos correspondientes.
1.5.2.7.1.4.1.6.2.
Desigualdad
Si se trata de mayor, menor o igual.
1.5.2.7.1.4.1.6.3.
Valores límite.
Los valores que limitan las restricciones.
1.5.2.7.1.4.1.6.1.
Otras alternativas.
Las restricciones también pueden ser de un solo elemento en el que las partes variables
se limitan a ser positivas, enteras o booleanas (1 o 0)

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 76

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 77
1.5.2.7.1.4.1.7.
Soluciones a problemas no lineales
SOLVER aunque limitado a pocas variables y pocas restricciones, puede resolver
problemas no lineales continuos en su espacio de factibilidad.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 78
1.5.2.7.1.4.1.7.1.
Ejemplo
Un casquete esférico: x # 0 0 0 0 0 1 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8
X Y de radio 8, -0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 1 centrado en (4,1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 4 1 8 Z 2 2
Z=(8 - (X-4) - (Y-1) ) 2 1/2
0.4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.1 2 0.221 >= 0 -2SEN(.01X) + Y ≥ 0 0.8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.1 2 -0.84 <= 0 -2COS(.01X) + Y ≤ 0 1.2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 9 <= 16 2X + Y ≤ 16 1.6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7
4 3 19 >= 12 4X +3Y ≥ 12 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7.736 7.73 7.723 7.714 7.705 7
2.4 0 0 0 0 0 0 0 0 0 7.836 7.838 7.838 7.838 7.836 7.833 7.828 7.822 7.815 7.807 7.797 7
2.8 0 0 0 0 0 0 0 7.899 7.904 7.907 7.909 7.909 7.909 7.907 7.904 7.899 7.894 7.887 7.878 7.869 7
3.2 0 0 0 0 0 0 0 0 7.954 7.957 7.959 7.96 7.959 7.957 7.954 7.95 7.944 7.937 7.929 7.92
3.6 0 0 0 0 0 0 0 0 0 7.987 7.989 7.99 7.989 7.987 7.984 7.98 7.974 7.967 7.959 7.95
4 0 0 0 0 0 0 0 0 0 7.997 7.999 8 7.999 7.997 7.994 7.99 7.984 7.977 7.969 7.96
4.4 0 0 0 0 0 0 0 0 0 0 7.989 7.99 7.989 7.987 7.984 7.98 7.974 7.967 7.959 7.95
4.8 0 0 0 0 0 0 0 0 0 0 0 7.96 7.959 7.957 7.954 7.95 7.944 7.937 7.929 0
5.2 0 0 0 0 0 0 0 0 0 0 0 7.909 7.909 7.907 7.904 7.899 7.894 7.887 7.878 0
5.6 0 0 0 0 0 0 0 0 0 0 0 0 7.838 7.836 7.833 7.828 7.822 7.815 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 7.743 7.74 7.736 7.73 7.723 0 0
6.4 0 0 0 0 0 0 0 0 0 0 0 0 0 7.629 7.626 7.621 7.615 7.608 0 0
6.8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7.488 7.483 7.477 0 0 0
7.2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7.321 7.315 0 0 0
7.6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8.4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 79
En SCILAB:
cx=6;cy=5;r=6; //Centrado en (6,5), de radio 6
function s=Z(x, y); //Casquete esférico
s=(-(x-cx).^2-(y-cy).^2+r^2)^.5;
s=s.*(sign(-(x-cx).^2-(y-cy).^2+r^2)+1)/2;
endfunction;
z=0;
d=.04;
n=300;
for i=1:n;
for j=1:n;
x=(i-1)*d;
y=(j-1)*d;
z(i,j)=Z(x,y); // restringido a
z(i,j)=z(i,j)*(sign(30-2*(i-1)*d-3*(j-1)*d)+1)/2; // 2x +3y<=36
z(i,j)=z(i,j)*(sign(-8+2*(i-1)*d+1*(j-1)*d)+1)/2; // 2x + y>= 8
z(i,j)=z(i,j)*(sign(-3*sin(((i-1)*d)/3)+1*(j-1)*d)+1)/2; //3*sin(x/3)- y<= 0
end;
end;
x=(0:n-1)*d;
y=x;
plot3d(x,y,z);
h=gce(); //get handle on current entity (here the surface)
a=gca(); //get current axes
a.grid=[1 1 1]; //make grids
a.axes_visible="on"; //axes are hidden
h.color_flag=1; //color according to z
h.color_mode=-2; //remove the facets boundary by setting color_mode to white color
h.color_mode = -1; // put the facets boundary back by setting color_mode to black color
f=gcf();//get the handle of the parent figure
f.color_map=rainbowcolormap(n*2);
c=[1:n,1:n];
TL.color = [c;c+1;c+2;c+3];
x=input("Teclee ENTER para empezar la animación?");

for i=0:1:360;
for j=0:6:90;
a.rotation_angles=[i,j];
sleep(10);
end;
end;

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 80
1.5.2.7.1.4.2.
Scilab10
Se trata de un paquete para el manejo matemático y gráfico de operaciones matemáticas
de muy alto nivel, pero sumamente sencillo en su programación y uso.
Posee miles de funciones de las cuales solo usaremos “karmarkar” que es el apellido
del matemático que planteo el algoritmo, y solamente usaremos las restricciones ≤ . Las
restricciones por igualdad (=), las transformamos en dos (una ≤ y otra ≥). Todas las mayor
o igual las multiplicamos (ambos miembros) por -1, resultando menor o igual (≤) .
La función SIMPLEX que permite usar la función function [o, z, e, i, y]=SIMPLEX(u, ct, r)
[o,z,e,i,y]=karmarkar([],[],-u',[],[],[],[],[],ct,r);
karmakar, sumamente compleja como una muy simple: endfunction

Caso Magistral
Maximizar Sujeto a: 𝟏 𝟐 𝟐𝟒
𝑴
𝑴 𝟏 𝟎 𝑴 𝟎 [𝟐 𝟏] ∙ [ ] ≤ [𝟐𝟒]
[𝟑 𝟒] ∙ [ ] = 𝒁 [ ]∙[ ]≥[ ] 𝑺
𝑺 𝟎 𝟏 𝑺 𝟎 𝟏 𝟏 𝟏𝟓
No negatividad de las Matriz de Coeficientes
variables Tecnológicos * Vector de
Vector de Utilidades Variables menor igual a
por las variables Sujeto a: Vector de Recursos
igual a Utilidad 𝟏 𝟎 𝑴 𝟎 𝟏 𝟐 𝟐𝟒
−[ ]∙[ ]≤[ ]
(Función Objetivo) 𝟎 𝟏 𝑺 𝟎 𝟐 𝟏 𝟐𝟒
𝑴
[
−𝟏 𝟎 𝑴 𝟎
]∙[ ] ≤[ ] 𝟏 𝟏 ∙ [ 𝑺 ] ≤ 𝟏𝟓
𝟎 −𝟏 𝑺 𝟎 −𝟏 𝟎 𝟎
[ 𝟎 −𝟏] [𝟎]

--> function [o, z, e, i, y]=SIMPLEX(u, ct, r)

> [o,z,e,i,y]=karmarkar([],[],-u',[],[],[],[],[],ct,r);
> endfunction
-->
--> [o,z]=SIMPLEX([3,4],[1,2;2,1;1,1;-1,0;0,-1],[24;24;15;0;0])
z =
-53.999596

o =
6.
8.9998989
-->
Pantalla en la consola del Scilab
1.5.2.7.1.4.2.1.
Ejemplo
Maximizar: Maximizar: Maximizar: Maximizar: Maximizar:

10
Paquete de programación Freeware (gratis) para manejo matemático.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 81
W=4U + 3V W=4U + 3V W=4U + 3V W=4U + 3V 𝐔
𝐖 = [𝟒 𝟑] [ ]
Sujeto a: Sujeto a: Sujeto a: Sujeto a: 𝐕
Sujeto a:
U + 2V ≤ 20 1U + 2V ≤ 20 1U + 2V ≤ 20 1U + 2V ≤ 20
𝟏 𝟐 𝟐𝟎
3U + 4V = 120 𝟑 𝟒 𝟏𝟐𝟎
5U + 6V ≥ 300 3U + 4V = 120 3U + 4V ≤ 120 3U + 4V ≤ 120 −𝟑 −𝟒 [𝐔] ≤ −𝟏𝟐𝟎
U≥0 3U + 4V ≥ 120 -3U + -4V ≤ -120 −𝟓 −𝟔 𝐕 −𝟑𝟎𝟎
V≥0 −𝟏 𝟎 𝟎
[ 𝟎 −𝟏] [ 𝟎 ]
5U + 6V ≥ 300 5U + 6V ≥ 300 -5U + -6V ≤ -300
1U + 0V ≥ 0 1U + 0V ≥ 0 -1U + 0V ≤ 0
0U + 1V ≥ 0 0U + 1V ≥ 0 0U + -1V ≤ 0
SIMPLEX(Utilidades,CoefictsTecnlgcs,Recursos) entrega [Máximo, -Utilidad, Status,Número de iteraciones, Yoptima]
--> [o,z]=SIMPLEX([4,3],[1,2;3,4;-3,-4;-5,-6;-1,0;0,-1],[20;120;-120;-300;0;0])

ERROR

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 82
1.5.2.8.
El Problema Dual
Asociado a todo problema de programación lineal, (Primal) existe otro, llamado Dual.

Dado un problema en la forma estándar

Primal: Dual:
Maximizar Minimizar
𝐧 𝐦

𝐙 = ∑ 𝐮𝐣 ∙ 𝐱 𝐣 𝐖 = ∑ 𝐫𝐢 𝐲𝐢
𝐣=𝟏 𝐢=𝟏
Sujeta a: Sujeta a:
𝐧 𝐦
∑ 𝐜𝐢𝐣 𝐱 𝐣 ≤ 𝐫𝐢 ∑ 𝐜𝐢𝐣 𝐲𝐣 ≥ 𝐮𝐣
𝐣=𝟏
𝐢=𝟏
Para i = 1, 2,…,my Para I = 1, 2, m y
𝐱𝐣 ≥ 𝟎 𝐱𝐣 ≥ 𝟎
Para j = 1, 2,…, m Para j = 1, 2,…, m
Maximizar Minimizar
Z = UX W=YR
Sujeto a Sujeto a
CX ≤ R YC≥U
X≥0 Y≥0
U y Y son vectores renglón y R y X son vectores columna

1.5.2.8.1.
Ejemplo
Maximizar:
Minimizar
Z=3X1+5X2
W=4Y1+12Y2+18Y3
Sujeto a:
Sujeto a:
Primal 1X1 + 2X2 ≤ 4 Dual 1Y1 +3Y2 +3Y3 ≥ 3
3X1 + 1X2 ≤ 12
2Y2 +1Y2 +2Y3 ≥ 3
3X1 + 2X2 ≤ 18
Y1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0
X1 ≥ 0, X2 ≥ 0

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 83
Primal and Dual LP Problems
Economic theory indicates that scarce (limited) resources have value. In LP models,
limited resources are allocated, so they should be, valued.
Whenever we solve an LP problem, we implicitly solve two problems: the primal
resource allocation problem, and the dual resource valuation problem.
Here we cover the resource valuation, or as it is commonly called, the Dual LP
Primal
Max c
j
j Xj

s.t. a
j
ij Xj  bi for all i

Xj  0 for all j
Dual

Min U b
i
i i

s.t. U a
i
i ij  c j for all j
Ui  0 for all i
Primal Dual Pair and Their Units
Primal
Max c
j
j Xj

s.t. a
j
ij Xj  bi for all i

Xj  0 for all j

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 84
wherex is the variable and equals units sold
max sum (per unit profits) * (units sold)
s.t.sum (per unit res. use)*(units sold) < res on hand
Dual
Min U b
i
i i

s.t. U a
i
i ij  c j for all j
Ui  0 for all i
U is the variable and equals per unit resource value
min sum (per unit res value) * (res on hand)
s.t. sum (per unit res value) * (per unit res use)
>per unit profits
So resource values – shadow prices are set up so per unit profits are exhausted.
Primal Dual Pair and Example

max 2000Xfancy + 1700Xfine + 1200Xnew

s.t. X fancy + X fine + X new  12
25X fancy + 20X fine + 19X new  280
X fancy , X fine , X new  0
(van cap) (labor) (profits)
min 12U1 + 280U 2 (Resource Payments)
s.t. U1 + 25U 2  2000 (X fancy )
U1 + 20U 2  1700 (X fine )
U1 + 19U 2  1200 (X new )
U1 , U2  (nonegativ ity)
Primal rows become dual columns
Primal Dual Objective Correspondence
Dual Variable
Relation
Given Feasible X* and U* to Partial
Derivative

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 85

CX*  U* AX*  U* b

CX*  U* b
* Z -1
u = CB B =
b
Complementary Slackness Zero Profits
At Optimal X*, u* Given Optimal

U (b - AX ) = 0
* *

( U A - C) X
* *
= 0. u' b = c x

Primal Dual Interrelations

Constructing Dual Solutions
Note we can construct a dual solution from optimal primal solution without resolving the
problem.
Given optimal primal XB* = B-1b and XNB* = 0. This solution must be feasible;
XB* = B-1b 0 and X 0
and must satisfy nonnegative reduced cost
CBB-1ANB - CNB 0.
U
*
Given this, suppose try = CBB-1 as a dual solution.
First, is this feasible in the dual constraints.
To be feasible, we must have U* A C and U* 0.

U
*
We know ANB - CNB 0 because at optimality this is equivalent to the reduced cost
criteria,
CBB-1ANB - CNB 0.
Further, for basic variables reduced cost is
CBB-1AB - CB = CBB-1B - CB = CB - CB = 0,
So unifying these statements, we know when U* A> C
Primal Dual Interrelations
Constructing Dual Solutions

Now are dual nonnegativity conditions U 0 satisfied.

We can look at this by looking the implication of the nonnegative reduced costs over the
slacks (UA>C).

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 86

For the slacks, A contains an identity matrix and the associated entries in C are all 0's.

Thus, UA = UI = U C =0 or U > 0.

So the U's are non-negative. Thus, U=CBB-1is a feasible dual solution.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 87
Primal Dual Interrelations
Constructing Dual Solutions

Now the question becomes, is this choice optimal?

In this case the primal objective function Z equals CX* = CBXB* + CNBXNB* = CBB-1b +
CNB0 = CBB-1b.

Simultaneously, the dual objective equals Ub = CBB-1b which equals the primal objective.
Therefore, the primal and dual objectives are equal at optimality.

Furthermore, since for a feasible primal we have AX < b and for the dual UA > C then
multiplying both so term on left is UAX we see Ub>Cx or all feasible primal objectives
must be less than or equal to all feasible dual objectives.

Thus CBB-1 is an optimal dual solution.

This demonstration shows that given the solution from the primal the dual solution can
simply be computed without need to solve the dual problem.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 88
Primal Dual Interrelations
Interpreting Dual Solutions

In addition given the derivation in the last chapter we can establish the interpretation of
the dual variables. In particular, since the optimal dual variables equal CB B-1 (which are
called the primal shadow prices) then the dual variables are interpretable as the marginal
value product of the resources since we showed

Z
= CB B1 = U* .
b
Also

Complementary Slackness Zero Profits

At Optimal X*, U* Given Optimal

U (b − AX ) = 0
*' *

( U * A − C) X * = 0. U*'b = cx*

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 89
Primal Dual Interrelations

Primal Dual ObjectiveCorrespondence

Primal Solution Item Dual Solution Item

Primal Solution Information Corresponding Dual Solution Information

Objectivefunction Objectivefunction

Shadow prices Variable values

Slacks Reducedcosts

Variable values Shadow prices

Reducedcosts Slacks

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 90
Degeneracy and Duality

The above interpretations for the dual variables depend upon whether the basis still exists
after the change occurs.

When a basic primal variable equals zero, dual has alternative optimal solutions. The
cause of this situation is generally primal constraints are redundant at the solution point
and the range of right hand sides is zero.

Max 3X1 + 2X 2
X1 + X2  100
X1  50
X2  50
X1 , X2  0
At the optimal solution, X1 = 50, X2 = 50, constraints are redundant.

If first slack variable is basic then X1 = 50, X2 = 50, S1 = 0 while S1 is basic. Shadow
prices are 0, 3, and 2.

If S3 basic X1 = 50, X2 = 50 S3 = 0 with shadow prices 2, 1, 0. Sameobjectivevalue --

multiplesolutions.

Degeneracy and Duality

Max 3X1 + 2X 2
X1 + X2  100
X1  50
X2  50
X1 , X2  0
u1 u2 u3 = [0 3 2] or [ 2 1 0 ]

The main difficulty with degeneracy is in interpreting the shadow prices as they take on
a direction.

If one were to increase the first right hand side from 100 to 101 this would lead to a zero
change in the objective function and X1 and X2 would remain at 50.

Decrease first constrainrhs from 100 to 99 then objective function which is two units
smaller because X2 would need to be reduced from 50 to 49.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 91
This shows that the two alternative shadow prices for the first constraint (i.e., 0 and 2)
each hold in a direction.

Similarly if bound on X1 51, obj increases by 1, whereas, if moved downward to 49, it

would cost 3.
Meanwhile, reducing X2 bound costs 2 and increasing by 0. this explains all shadow
prices

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 92
Primal Columns are Dual Constraints

Columns in the primal, form constraints on the dual shadow price information.

Thus, for example, when a column is entered into a model indicating as much of a
resource can be purchased at a fixed price as one wants, then this column forms an upper
bound on the shadow price of that resource.

Note that it would not be sensible to have a shadow price of that resource above the
purchase price since one could purchase more of that resource.

Similarly, allowing goods to be sold at a particular price without restriction provides a

lower bound on the shadow price.

In general, the structure of the columns in a primal linear programming model should be
examined to see what constraints they place upon the dual information.

The linear programming modeling chapter extends this discussion.

© [email protected] Lecturas 2 Programación lineal

 UABC Ensenada B.C. México (414) 1.5.2. 93
1.5.2.9.
Análisis de sensibilidad.
Dada la importancia que tiene conocer la vigencia de las soluciones establecidas Solo
estimaciones de condiciones futuras), es necesario saber como cambia la solución óptima
cuando se alteran las condiciones del problema.

© [email protected] Lecturas 2 Programación lineal