1 PROGRAMACIÓN LINEAL.

1.1 Sistemas de inecuaciones lineales en 2 variables.

DEFINICIÓN
Una desigualdad lineal en las variables x y y puede escribirse de una de las siguientes formas:
ax + by + c 0; ax + by + c 0; ax + by + c < 0; ax + by + c > 0
donde a; b y c son constantes donde a y b no son cero ambos.
Si b 6= 0; despejando y en la recta ax + by + c = 0, se obtiene la ecuación de la recta en forma punto
pendiente: y = mx + b

En forma geométrica, la solución (o grá…ca) de una desigualdad lineal en x y y consiste en todos los
puntos (x; y) en el plano, cuyas coordenadas satisfacen dicha desigualdad.
Por ejemplo, una solución de x + 3y < 20 es el punto (2; 4), puesto que la sustitución da
2 + 3(4) < 20, que equivale a 14 < 20, que es verdadera.
Una solución de la inecuación ax + by + c 0; es un punto del plano (x0 ; y0 ) tal que al reemplazar x por
x0 y y por y0 en la inecuación esta se transforma en verdadera.
Es claro que existe un número in…nito de soluciones, esto es común para toda desigualdad lineal.
Para considerar las desigualdades lineales en general, advierta primero que la grá…ca de una recta no
vertical y = mx + b, separa al plano en tres partes distintas

1
 1. La recta misma, que consiste en todos los puntos (x, y) cuyas coordenadas satisfacen
la ecuación y = mx + b.
2. La región por encima de la recta, que consiste en todos los puntos (x, y), cuyas
coordenadas satisfacen la desigualdad y > mx + b (esta región se conoce como un
semiplano abierto).
3. El semiplano abierto por debajo de la recta, que consiste en todos los puntos (x, y)
cuyas coordenadas satisfacen la desigualdad y < mx + b.
En la situación donde la desigualdad estricta “<” se reemplaza por “ ” la solución de
y mx + b consiste en la recta y = mx + b, junto con el semiplano por debajo de ella.
En este caso se dice que la solución es un semiplano cerrado. Se puede hacer una a…rmación semejante
cuando “>” se reemplaza por “ ”. Para una recta vertical x = a, se habla de un semiplano a la derecha
(x > a) de la recta o a la izquierda (x < a).
La solución de una inecuación lineal en dos variables es un semiplano.

Ejemplo: Gra…car la solución de la inecuación 5x + 8y 10

i)Gra…car la recta 5x + 8y = 10

2
 Corte eje X Corte eje Y
10 5
y = 0 ! 5x = 10 ! x = 2 x = 0 ! 8y = 10 ! y = 8 = 4

(2; 0) 0; 54
ii)Para gra…car el semiplano tomamos como punto de prueba
(0; 0) reemplazar x = 0; y = 0 : 5x + 8y 10 ! 0 10 falso, esto implica que el conjunto solución
de la inecuación es el semiplano que no contiene a (0; 0)

Un sistema de n inecuaciones lineales en dos variables tiene la forma:

a1 x + b1 y c1

a2 x + b2 y c2
la solución de cada inecuación representa un semiplano.
..
.
an x + bn y cn
La solución del sistema de inecuaciones lineales es la intersección de los n semiplanos solución de cada
inecuación.
Esta solución puede ser
Vacia o una región del plano R2
Casi siempre son regiones poligonales que pueden ser acotadas o no acotadas.
Las condiciones x 0; y 0 son condiciones de no negatividad y nos restringe la solución al primer
cuadrante.
Para resolver gra…camente un sisitema de inecuaciones lineales en 2 variables se gra…ca el semiplano
correspondiente a cada inecuación y se gra…ca la región común a todos los semiplanos (Intersección de los
semiplanos solución correspondiente a cada inecuación)
Ejemplo: Resolver gra…camente el sistema de inecuaciones lineales:

3
 8
>
> 8x + 3y 24 Rectas Corte eje X Corte eje Y Semiplano
>
>
>
>
>
> x+y 4 y=0 x=0 x = 0; y = 0
>
<
x + 3y 6 L1 : 8x + 3y = 24 8x = 24 ! x = 3 3y = 24 ! y = 8 0 24 : V
>
>
>
>
>
> x 0 L2 : x + y = 4 x=4 y=4 0 4:V
>
>
>
: y 0 L3 : x + 3y = 6 x=6 3y = 6 ! y = 2 0 6:V

El conjunto solución esla región encerrada por un polígono cerrado y acotado.

Hallar las coordenadas de los vértices del polígono solución

V ertices :
O = (0; 0) ; A = (0; 2) ; C = (3; 0)
8
< 8x + 3y = 24
B = L1 \ L3 :
: x + 3y = 6
18
Re star : L1 L3 : 7x = 18 ! x = 7
18
y : reemplazamos x = 7 en L2 :
18
18 6 8
7 + 3y = 6 ! y = 3
7
= 7
18 8
B= 7 ; 7 :

Ejemplo 2 Hallar gra…camente el conjunto solución del sistema de inecuaciones lineales y encuentre las
coordenadas
8 del poligono frontera de la solución.
>
> 3x + y 14 Corte eje X Corte eje Y semiplano
>
>
>
>
>
> x + y 10 Re ctas y=0 x=0 Punto de prueba (0; 0)
>
>
>
>
< x + 2y 16 L : 3x + y = 14 3x = 14; x = 14 y = 14 0 14 : F
1 3
>
> x + 3y 21 L2 : x + y = 10 x = 10 y = 10 0 10 : F
>
>
>
>
>
> x 0 L3 : x + 2y = 16 x = 16 2y = 16; y = 8 0 16 : F
>
>
>
>
: y 0 L4 : x + 3y = 21 x = 21 3y = 21; y = 7 0 21 : F
4
 V ertices :
A : corte de L1 eje Y (0; 14)
8
< L : 3x + y = 14
1
B : L1 \ L2 :
: L : x + y = 10
2

L1 L2 : 2x = 4; x = 2; y = 8:B = (2; 8)
8
< L : x + y = 10
2
C : L2 \ L3 :
: L : x + 2y = 16
3

L3 L2 : y = 6; x = 4: C = (4; 6)
8
< L : x + 2y = 16
3
D : L3 \ L4 :
: L : x + 3y = 21
4

L4 L3 : y = 5; x = 6: D = (6; 5)

Conjunto solución Región no acotada E : corte del eje X con L4 : E = (21; 0)

cuya frontera es un poligono abierto

Ejemplo 3 Hallar gra…camente el conjunto solución del sistema de inecuaciones lineales y obtener las
coordenadas
8 de los vértices del poligono frontera.
>
> x + 6y 67
>
>
>
>
>
> x + 2y 27
>
<
x + y 18 y hallar las coordenadas de los vértices del polinomio frontera.
>
>
>
>
>
> x 0
>
>
>
: y 0
Solución.
8
>
> x + 6y 67 Rectas Corte eje X Corte eje Y Semiplano
>
>
>
>
>
> x + 2y 27 y=0 x=0 (0; 0)
>
<
67
x + y 18 L1 : x + 6y = 67 x = 67 6y = 67 ! y = 6 0 67 : V
>
>
>
>
>
> x 0 L2 : x + 2y = 27 x = 27 2y = 27 ! y = 27 0 27 : V
>
> 2
>
: y 0 L3 : x + y = 18 x = 18 y = 18 0 18 : V
Puento de prueba (0; 0) Satisface las inecuaciones por tanto los semiplanos solución son los que contienen
al punto (0; 0) :

5
 Coordenadas de los V ertices :
A = (0; 0) ; B : corte eje Y y L1 : B = 0; 67
6

E : corte eje X y L3 : E = (18; 0)

8
< L : x + 6y = 67
1
C = L1 \ L2 :
: L : x + 2y = 27
2

L1 L2 : 4y = 40 ! y = 10
En L2 : x + 2 (10) = 27 ! x = 7 : C = (7; 10)
8
< L : x + 2y = 27
2
D = L2 \ L3 :
: L : x + y = 18
3

L2 L3 : y = 9
En L3 : x + 9 = 18 ! x = 9 : D = (9; 9)
Conjunto solución es la región encerrada por el poligono frontera
cerrado; acotado y convexo.
PROGRAMACIÓN LINEAL
Algunas veces se desea maximizar o minimizar una función sujeta a algunas limitaciones (o restricciones).
Por ejemplo, probablemente un fabricante desee maximizar una función de utilidad sujeta a las restricciones
de producción que imponen las limitaciones sobre el uso de la maquinaria y la mano de obra. Ahora se
considerará cómo resolver tales problemas cuando la función que será maximizada o minimizada es lineal.
Una función lineal en x y y tiene la forma: Z = ax+by donde a y b son constantes. También se requerirá que
las correspondientes restricciones estén representadas por un sistema de desigualdades lineales (que incluyan
“ ”o “ ”) o ecuaciones lineales en x y y, además de que ninguna de las variables sea negativa. Una
situación que involucra todas estas condiciones se llama problema de programación lineal.
La programación lineal fue desarrollada por George B. Dantzig al …nal de la década de 1940, y la Fuerza
Aérea de Estados Unidos fue quien la utilizó primero, como una ayuda en la toma de decisiones. Actualmente
tiene una amplia aplicación en los análisis industrial y económico. En un problema de programación lineal,
la función que se debe maximizar o minimizar se llama función objetivo. Aunque por lo regular existe un
número in…nito de soluciones para el sistema de restricciones, llamadas soluciones factibles o puntos factibles,
la meta es encontrar una que sea una solución óptima (es decir, una que dé el valor máximo o mínimo de la
función objetivo).
Metodo Grá…co para resolver problemas de programación lineal en 2 variables.
El problema de programación lineal:

6
 1)Maximizar : Z = px + qy 2)Minimizar : Z = px + qy
sujeto a: sujeto a:
a1 x + b1 y c1 a1 x + b1 y c1

a2 x + b2 y c2 o a2 x + b2 y c2
.. ..
. .
am x + bm y cm am x + bm y cm

x 0; y 0 x 0; y 0
Cuando tiene solución, esta se encuentra en alguno de los vértices del poligono frontera del conjunto
solución del sistema de inecuaciones lineales correspondiente a las restricciones del problema de programación
lineal correspondiente. (Este conjunto solución es llamado región factible del problema)
Pasos del metodo grá…co
1) Gra…car la región factible (Gra…car la solución del sistema de inecuaciones lineales)
2)Hallar los vértices del poligono frontera: (x1 ; y1 ) ; (x2 ; y2 ) ; :::; (xn ; yn )
3)Evaluar la función objetivo Z = px + qy en cada uno de los vértices del poligono frontera
Z (x1 ; y1 ) ; Z (x2 ; y2 ) ; ; Z (xn ; yn )
Elegir el valor máximo si el problema es de maximización o el mínimo si el problema es de minimización.
El problema no tiene solución si:.
i) La región factible es vacia
Ejemplo
Graf icar los semiplanos determinados por las restricciones
y hallamos su intersección (Región factible)

max : Z = 8x + 7y
s:a:
2x + 3y 2
6x + 9y 8
x; y 0

L1 y L2 son paralelas
La región factible es vacia y por tanto el problema no tiene solución
o
ii) En el problema de maximizar, la región factible es no acotada.
Ejemplo

7
 Graf icar los semiplanos determinados por las restricciones
y hallamos su intersección (Región factible)

maximizar : Z = 10x + 8y
s:a : x + y 2
2x + 3y 5
x 0; y 0

El problema no tiene solución pues la región factible es no acotada.

Al evaluar Z en puntos de la región factible siempre existen puntos (x; y) tal que Z (x; y) toma valores
muy grandes.
Ejemplos Resolver el PPL con el método gra…co.
8 cortes cortes
>
> Maximizar: Z = 6x + 5y
>
>
>
> eje X eje Y
>
> s:a : x + 5y 50
>
>
>
> L1 : x + 5y 50 x = 50 y = 10
< 2x + 3y 37
Ejemplo: L2 : 2x + 3y = 37 x = 37 y= 37
>
> x + y 15
2 3
>
>
>
> L3 : x + y = 15 x = 15 y = 15
>
> 2x + y 26
>
>
>
> L4 : 2x + y = 26 x = 13 y = 26
: x 0; y 0:

i)Graf icar la región Factible

ii)Coordenadas de los vértices
A = (0; 0) ; B corte eje Y y L1 B = (0; 10)
C corte eje X y L4 : C = (13; 0)
8
< L : x + 5y 50
1
D = L1 \ L2 :
: L : 2x + 3y = 37
2

2L1 L2 : 7y = 63 ! y = 9; x = 5 : D = (5; 9)
8
< L : 2x + 3y = 37
2
E = L2 \ L3 :
: L : x + y = 15
3

L2 2L3 : y = 7; L3 : x = 8 : E = (8; 7)
8
< L : x + y = 15
3
F = L3 \ L4 :
: L : 2x + y = 26
4

L4 L3 : x = 11; L3 : y = 4 : F = (11; 4)

8
 iii)Evaluar la función objetivo en los vértices Z = 6x + 5y
Z (A) = Z (0; 0) = 6 (0) + 5 (0) = 0
Z (B) = Z (0; 10) = 6 (0) + 5 (10) = 50
Z (C) = Z (13; 0) = 6 (13) + 5 (0) = 78
Z (D) = Z (5; 9) = 6 (5) + 5 (9) = 75
Z (E) = Z (8; 7) = 6 (8) + 5 (7) = 83
Z (F ) = Z (11; 4) = 6 (11) + 5 (4) = 86
Elegimos el valor más grande de Z: Z (11; 4) = 86
El máximo de Z es 86 Y Ocurre cuando x = 11 y y = 4:
max Z = 59x + 60y
s:a: : x + 4y 48
2)Tarea: x + 2y 28
2x + y 32
x 0; y 0
8
>
> max Z = 66x + 55y
>
>
>
>
>
> s:a : x + 6y 67
>
>
>
>
< x + 2y 27
3)
>
> x + y 18
>
>
>
>
>
> 7x + 5y 112
>
>
>
>
: x 0; y 0
Aquiii
Ejemplo Resolver el problema de programación lineal:.
i)Graf icar la región Factible

8
>
> min Z = 100x + 90y
>
>
>
> Rectas
>
> s:a : 4x + y 11
>
>
>
> Roja : 4x + y = 11
< x+y 8
V erde : x + y = 8
>
> x + 2y 14
>
>
>
> Azul : x + 2y = 14
>
> x + 3y 19
>
>
>
> Amarilla : x + 3y = 19
: x 0; y 0

Azul : x + 2y = 14
Amarilla : x + 3y = 19
Restar hacia arriba:y = 5
Re emplazar en Azul:x + 2 5 = 14 ! x = 4

9
 iii)Evaluar la función objetivo en los
ii)Coordenadas de los vértices vertices y elegir la solución adecuada
A = (0; 11) Z = 100x + 90y
B = (1; 7) : Intersección dos primeras rectas Z (0; 11) = 100 0 + 90 11 = 990
C = (2; 6) : Intersección segunda y tercera rectas Z (1; 7) = 100 1 + 90 7 = 730
D = (4; 5) : Intersección tercera y cuarta rectas Z (2; 6) = 100 2 + 90 6 = 740
E = (19; 0) Z (4; 5) = 100 4 + 90 5 = 850
Z (19; 0) = 100 19 + 90 0 = 1900
Escogemos el valor mínimo: La solución es
El mínimo de Z=730 y ocurre cuando x=1, y=7.
min Z = 160x + 180y
3x + y 14
x+y 10
5.
x + 2y 16
x + 3y 21
x + 5y 29

Planteamiento Problemas de programación lineal 2 variables (Método grá…co).

Ejemplo 1
Un fabricante produce dos tipos de reproductores de DVD: Vista y Xtreme. Para su producción requieren
del uso de dos máquinas, A y B. El número de horas necesarias para ambas está indicado en la tabla siguiente:
Máq A Máq B Si cada máquina puede utilizarse 24 horas por día y las utilidades en los modelos Vista
Vista 1h 2h y Xtreme son de $50 y $80, respectivamente, ¿cuántos reproductores de cada tipo deben
Xtreme 3 h 2h producirse por día para obtener una utilidad máxima? ¿Cuál es la utilidad máxima?
Solución. i)Nombrar variables
x = # de reproductores vista a fabricar por día. y = # de reproductores Xtreme a fabricar por día.
ii)Escribir la Función a optimizar y restricciones en términos de las variables:
Función a maximizar U =utilidad total.
M ax : U = 50x + 80y
M ax : U = 50x + 80y corets Eje X Eje Y
s:a :
s:a : x + 3y 24 Rectas y=0 x=0
U so maquina A: x + 3y 24
2x + 2y 24 x + 3y = 24 x = 24 y=8
U so maquina B: 2x + 2y 24
x 0; y 0 2x + 2y = 24 x = 12 y = 12
x 0; y 0

10
 Región Factible
Vértices Evaluación en vértices U = 50x + 80y
O = (0; 0) U (O) = U (0; 0) = 50 0 + 80 0 = 0
A = (0; 8) U (A) = U (0; 8) = 80 8 = 640
B = (6; 6) U (B) = U (6; 6) = 50 6 + 80 6 = 780
C = (12; 0) U (C) = U (12; 0) = 50 12 = 600
8
< L : x + 3y = 24
1
B: L1 21 L2 : 2y = 12 ! y = 6
: L : 2x + 2y = 24
2

Reemplazando en L1 : x = 24 3 6 = 6 : B = (6; 6)

La utilidad máxima es U = 780 y se obtiene cuando se fabrican 6 reproductores vista y 6 Xtreme.

Ejemplo 2.
Una compañía química diseña una planta para producir dos tipos
P lanteamiento :
de polímeros, P1 y P2. La planta debe tener una capacidad de
x = # camaras tipo A
producción de al menos 100 unidadesde P1 y 420 unidades de
y = # camaras tipo B
P2 cada día. Existen dos posibles diseños para las principales
Función a optimizar:
cámaras de reacción que se incluirán en la planta. Cada cámara
M inimizar : C = costo total
de tipo A cuesta $600000, y es capaz de producir 10 unidades de
C = 600000x + 300000y
P1 y 20 unidades de P2 por día; el tipo B es un diseño más económico,
Restricciones
cuesta $300000 y es capaz de producir 4 unidades de P1 y 30 unidades
Producción de P1: 10x + 4y 100
de P2 por día. Debido a los costos de operación, es necesario tener al
Producción de P2: 20x + 30y 420
menos 4 cámaras de cada tipo en la planta. ¿Cuántas de cada tipo
Número de camaras:x 4
deben incluirse para minimizar el costo de construcción y aún así
y 4
satisfacer el programa de producción requerido? (Suponga que existe
un costo mínimo.)
Solución.
M inimizar
C = 600000x + 300000y
s.a.
10x + 4y 100
20x + 30y 420
x 4;
y 4

11
 cortes con cortes con
Rectas x=4 y=4
10x + 4y = 100 40 + 4y = 100 ! y = 15 10x + 16 = 100 ! x = 8:4
420 80 34 300
20x + 30y = 420 80 + 30y = 420 ! y = 30 = 3 20x + 120 = 420 ! x = 20 = 15
M
L:10x + 4y = 100 L:10x + 4y = 100 2 L : 11y = 110 ! y = 10
M
M:20x + 30y = 420 2 : 10x + 15y = 210 L : 10x + 40 = 100 ! x = 6

Evaluación FAO en Vértices

V ertices C = 600000x + 300000y
A = (4; 15) C (A) = C (4; 15) = 600000 4 + 300000 15 = 6900 000
C = (15; 4) C (C) = C (15; 4) = 600000 15 + 300000 4 = 10 200 000
B = (6; 10) C (B) = C (6; 10) = 600000 6 + 300000 10 = 6600 000

Elegimos el mínimo
Respuesta: El costo mínimo es C=6600000 y se obtiene con 6 camaras tipo A y 10 camaras tipo B.

Ejemplo 3.
Una compañía petrolera que tiene dos re…nerías necesita al menos 8000, 14000 y 5000 barriles de petróleo
de grados bajo, medio y alto, respectivamente. Cada día, la re…nería I produce 2000 barriles de grado bajo,
3000 barriles de grado medio y 1000 barriles de grado alto, en tanto que la re…nería II produce 1000 barriles
de cada uno de los grados alto y bajo, y 2000 barriles de petróleo de grado medio. Si operar la re…nería I
cuesta $25000 por día, y operar la re…nería II $20000 diarios, ¿cuántos días debe operar cada re…nería para
satisfacer los requerimientos de producción a un costo mínimo? Suponga que existe un costo mínimo. ¿Cuál
es?
Planteamiento: x = # de dias a operar la re…neria I y = # de dias a operar la re…neria II
Función a minimizar C=costo total. C = 25000x + 20000y
Restricciones: # de barriles de grado bajo: 2000x + 1000y 8000
# de barriles de grado medio: 3000x + 2000y 14000
# de barriles de grado alto: 1000x + 1000y 5000
x 0; y 0:

12
 A = fx = 0g \ f2000x + 1000y = 8000g ! y = 8
M in : C = 25000x + 20000y s.a D = fy = 0g \ f1000x + 1000y = 5000g ! x = 5
8
azul 2000x + 1000y 8000 < L : 2000x + 1000y = 8000
1 1
B= L L :
roja : 3000x + 2000y 14000 : L : 3000x + 2000y = 14000 1 2 2
2
8
verde : 1000x + 1000y 5000 < 3000x + 2000y = 14000
C=
x 0; y 0 : 1000x + 1000y = 5000

Evaluar C = 25000x + 20000y en los vértices Escoger el mínimo.

Terminar de resolver en casa..

1.2 7.3 Soluciones óptimas múltiples

El problema de programación lineal:

1)Maximizar : Z = px + qy 2)Minimizar : Z = px + qy
sujeto a: sujeto a:
a1 x + b1 y c1 a1 x + b1 y c1

a2 x + b2 y c2 o a2 x + b2 y c2
.. ..
. .
am x + bm y cm am x + bm y cm

x 0; y 0 x 0; y 0
Tiene in…nitas soluciones, si al evaluar la función objetivo Z en dos vértices distintos A = (x1 ; y1 ) y
B = (x2 ; y2 ) su resultado es igual y es óptimo (es decir es mínimo o máximo en el correspondiente caso) y las
in…nitas soluciones corresponden a los puntos del segmento entre A y B. Que se escriben formalmente por:

8
>
> x = x2 t + x1 (1 t)
>
<
y = y2 t + y1 (1 t) es la paramatrización del segmento que une los
>
>
>
: 0 t 1

13
puntos A y B
Ejemplo.
Minimizar Z = 20x + 30y
s.a 5x + 2y 20
2x + 3y 19
3x + 7y 36
x; y 0
Gra…car la región factible
Puntos de corte

Rectas eje X y=0 eje Y: x=0

L1 : 5x + 2y = 20 x=4 y = 10
19 19
L2 : 2x + 3y = 19 x= 2 y= 3
36
L3 : 3x + 7y = 36 x = 12 y= 7

8
< 5x + 2y = 20
Vertices del poligono frontera A=(0; 10) B = L1 \ L2 = = (2; 5) :
: 2x + 3y = 19
8
< 2x + 3y = 19
C = L2 \ L3 C = (5; 3) D = (12; 0)
: 3x + 7y = 36
Z = 20x + 30y
Z (A) = Z (0; 10) = 20 0 + 30 10 = 300
Z (B) = Z (2; 5) = 20 2 + 30 5 =190 mínimo
Z (C) = Z (5; 3) = 20 5 + 30 3 =190 mínimo
Z (D) = Z (12; 0) = 20 12 + 30 0 = 240
In…nitas soluciones
Segmento de recta que une B = (2; 5) y C = (5; 3): Ct + (1 t)
8B
< x = 3t + 2
8 0 t 1
< x = 5t + 2 (1 t) : y = 2t + 5
0 t 1 Presentación de las in…nitas soluciones:
: y = 3t + 5 (1 t)

14
 Ejemplo 2 In…nitas soluciones. Analizar en casa:
Maximizar Z = 80x + 120y
s.a. x + 4y 28
2x + 3y 26
4x + 3y 40 x; y 0
Rectas eje X y=0 eje Y: x=0
L1 : x + 4y = 28 x = 28 y=7
26
L2 : 2x + 3y = 26 x = 13 y= 3
40
L3 : 4x + 3y = 40 x = 10 y= 3

Evaluación en los vertices

V erticesA = (0; 7)
8 Z (A) = 80 0 + 120 7 = 840
< x + 4y = 28
B = L1 \ L2 : (4; 6) Z (B) = 80 4 + 120 6 = 1040
: 2x + 3y = 26
8 Z (C) = 80 7 + 120 4 = 1040
< 2x + 3y = 26
C = L2 \ L3 : (7; 4) Z (D) = 80 10 + 120 0 = 800
: 4x + 3y = 40
Z (E) = 80 0 + 120 0 = 0
D = (10; 0) ; E = (0; 0)
Z (A) = 80 0 + 120 7

26 3 2 26
8
< 2x + 3y = 26 40 3 4 40
26 3 40 3 80 26 4
Con cramer:C = L2 \ L3 : x= = 6 12 = 7; y = = 6 =
: 4x + 3y = 40 2 3 2 3
4 3 4 3
4:
In…nitas soluciones en B=(4; 6) y C=(7; 4) la función a maximizar da igual a 1040

8
8 >
> x = 3t + 4
< x = 7t + 4 (1 >
<
t)
0 t 1 y= 2t + 6
: y = 4t + 6 (1 t) >
>
>
: 0 t 1

15
METODO SIMPLEX....
PPLE: PROBLEMA DE PROGRAMACIÓN LINEAL ESTANDAR

Condiciones de no negatividad x1; x2 ; x3 ; ::xn 0

Si aparece una restricción x1 + 2x2 3x3 4 se debe mult por ( 1) x1 2x2 + 3x3 4

Matricialmente el PPLS:
Maximizar Z = CX s.a. AX B X 0; B 0:
SIMPLEX EXPLICACIÓN EN UN CASO 3 VARIABLES Y 4 RESTRICCIONES
Ejemplo de PPLE 3 incognitas y 4 restricciones
P ASO (0) PLANTEAR EL S.E.A.
M aximizar : Z = c1 x1 + c2 x2 + c3 x3 s:a :
(Sistema de ecuaciones asociado)
a11 x1 + a12 x2 + a13 x3 b1 8
>
> E1)a11 x1 + a12 x2 + a13 x3 + s1 = b1
>
>
a21 x1 + a22 x2 + a23 x3 b2 >
>
>
> E2)a21 x1 + a22 x2 + a23 x3 + s2 = b2
>
<
a31 x1 + a32 x2 + a33 x3 b3
E3)a31 x1 + a32 x2 + a33 x3 + s3 = b3
a41 x1 + a42 x2 + a43 x3 b4 >
>
>
>
>
> E4)a41 x1 + a42 x2 + a43 x3 + s4 = b4
x1 0; x2 0; x3 0; bi 0 >
>
>
: E5) c1 x1 c2 x2 c3 x3 + Z = 0
En cada restricción se agrega una variablede holgura si 0 para convertir cada desigualdad en igualdad
TSI T abla simpex inicial es la matriz de coe…cientes

16
 P ASO (0) PLANTEAR EL S.E.A.
8
>
> E1)a11 x1 + a12 x2 + a13 x3 + s1 = b1
>
>
>
>
>
> E2)a21 x1 + a22 x2 + a23 x3 + s2 = b2
>
<
E3)a31 x1 + a32 x2 + a33 x3 + s3 = b3
>
>
>
>
>
> E4)a41 x1 + a42 x2 + a43 x3 + s4 = b4
>
>
>
: E5) c x
1 1 c2 x2 c3 x3 + Z = 0
si : variables de holgura
Un paso del metodo simplex.
1)Si todos los indicadores son no negativos FIN
Solución x1 = x2 = x3 = 0; max de Z = 0:
2)Si hay indicadores negativos
2.1)Escoger de los indicadores el mas negativo nos da la variable de entrada supongamos que es x2 :
2 3
V:E: # COCIEN T ES
6 7
6 Resultados 7
6 x1 x2 x3 s1 s2 s3 s4 Z R oper element. 7
6 Elem . var entr 7
6 b 7
6 s1 a11 a11 a13 1 0 0 0 0 b1 1
F1 ! aa3111
F3 + F1 7
6 a11 7
6 b2 7
6 s2 a21 a21 a21 0 1 0 0 0 b2 F2 ! aa3121
F3 + F2 7
6 a21 7
6 b 1 7
6 VS s3 a31 a31 a31 0 0 1 0 0 b3 a31 menor
3
F3 ! a31 F3 7
6 7
6 b4 7
6 s4 a41 a41 a41 0 0 0 1 0 b4 F4 ! aa3141
F3 + F4 7
4 a41 5
c2
Z c1 c2 mas c3 0 0 0 0 1 0 F5 ! a31 F3 + F4
2.2) Ahora se hacen los cocientes entre la columna de los resultados y la correspondiente columna de la
variable de entrada
2.3) De los cocientes eliges el mas pequeño esto nos da la VARIABLE DE SALIDA en este caso s3 :
Nota: Si algun cociente da 0 en el denominador o negativo,entonces se escribe no hay cociente en el
cociente de esa …la.
2.4) Con operaciones elementales debes convertir en 1 la posición del pivote (que es la correspondiente a
la …la de la varible de salida con la columna de la variable de entrada)
2.5)
2 Convertir en 0 los otros elementos de la columna de la variable de3entrada.
COCIEN T ES
6 7
6 resultados 7
6 x1 x2 x3 s1 s2 s3 s4 Z R 7
6 elem . var entr 7
6 7
6 s1 a11 0 a13 1 0 0 0 0 b1 r1 7
6 7
6 7
6 s2 a21 0 a21 0 1 0 0 0 b2 r2 7
6 7
6 7
6 x2 a31 1 a31 0 0 1 0 0 b3 r3 7
6 7
6 7
6 s4 a41 0 a41 0 0 0 1 0 b4 r4 7
4 5
Z i1 i2 i3 0 1 0 r5
2.5) Si todos los indicadores son no negativos FIN
Solución x1 = 0; x2 = r3 ; x3 = 0; max de Z = r5 :

17
 Si hay indicadores negativos se comienza un nuevo paso de simplex hasta que todos los indicadores sean
no negativos.

Ejercicios: Resolver el problema de programación lineal usando el metodo simplex.

Max Z = x1 + 2x2 s:a
3x1 + 2x2 5
1) x1 + 3x2 3
x1 0; x2 0
forma estandar okk
Tabla Simplex Inicial TSI
2 3
SEA VE # COC OP ERACION ES
8 6 7
> 6 7
>
> 3x1 + 2x2 + s1 = 5 6 x1 x2 s1 s2 Z R 7
< 6 7
6 2 7
x1 + 3x2 + s2 = 3 6 s1 3 2 1 0 0 5 5 2 F1 ! 3 F2 + F1 7
>
> 6 7
>
: x 6 1 7
1 2x2 + Z = 0 6 VS s2 1 3 0 1 0 3 3 3 = 1X F2 ! 3 F2
7
4 5
Z 1 2 0 0 1 0 F3 ! 23 F2 + F3
2 3
COC
6 7
6 7
6 x1 x2 s1 s2 Z R 7
6 7
6 11 2 7
6 s1 0 1 0 3 7 F IN::::: (INDICADORES NO NEGATIVOS)
6 3 3 7
6 1 1 7
6 x2 1 0 0 1 7
4 3 3 5
1 2
Z 3 0 0 3 1 2
SOLUCIÓN: x1 = 0; x2 = 1; M aximo de Z = 2:
Aquiii
2)
P.P.L.Estandar
M ax : Z = 2x1 + x2 x3
M ax : Z = 2x1 + x2 x3 s:a :
s:a : x1 + x2 1 a
Debes multiplicar la 2 restrición por ( 1) x1 + x2 1
x1 2x2 x3 2
x1 + 2x2 + x3 2
x1 ; x2 ; x3 0
x1 ; x2 ; x3 0
S:E:A
8 T:S:I
>
> x1 + x2 + s1 = 1 2 3
>
< VE # COC OP ERACION ES
x1 + 2x2 + x3 + s2 = 2 6 7
> 6 7
>
> 6 x1 x2 x3 s1 s2 Z R 7
: 2x1 x2 + x3 + Z = 0 6 7
6 7
6 VS s1 1 1 0 1 0 0 1 1 1 = 1X 7
si un cociente es negativo 6 7
6 7
6 s2 1 2 1 0 1 0 2 2 1@ F2 ! F1 + F2 7
decimos no hay cociente 4 5
Z 2 1 1 0 0 1 0 F3 ! 2F1 + F3
@ : No existe

18
2 3
COC OP ERACION ES solucion
6 7
6 7
6 x1 x2 x3 s1 s2 Z R 7 indic x1 = 1
6 7
6 7
6 x1 1 1 0 1 0 0 1 7 no F IN:: x2 = 0 :
6 7
6 7
6 s2 0 3 1 1 1 0 3 7 negativos x3 = 0
4 5
Z 0 1 1 2 0 1 2 Zmax = 2
Ejemplo 3. Resolver el ppl con simplex
Maximizar:W = 4x1 + 0x2 x3
S:E:A:
s.a.: x1 + x2 + x3 6 8
>
> x1 + x2 + x3 + s1 = 6
>
>
x1 x2 + x3 10 > >
< x1 x2 + x3 + s2 = 10
x1 x2 x3 4
>
> x1 x2 x3 + s3 = 4
>
>
x1 ; x2 ; x3 0 >
>
: 4x1 + 0x2 + x3 + W = 0
Es tan dar okk
T:S:I
2 3
VE # COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 W R 7
6 7
6 7
6 s1 1 1 1 1 0 0 0 6 6 F1 ! F3 + F1 7
6 7
6 7
6 s2 1 1 1 0 1 0 0 10 10 F2 ! F3 + F2 7
6 7
6 7
6 VS s3 1 1 1 0 0 1 0 4 4X 7
4 5
W 4 0 1 0 0 0 1 0 F4 ! 4F3 + F4
2 3
VE # COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 W R 7
6 7
6 p 7
6 VS s1 0 2 2 1 0 1 0 2 1 F1 ! 12 F1 7
6 7
6 7
6 s2 0 0 2 0 1 1 0 6 6 0 N O HAY 7
6 7
6 7
6 x1 1 1 1 0 0 1 0 4 4 1 N O HAY F3 ! 21 F1 + F3 7
4 5
W 0 4 3 0 0 4 1 16 F4 ! 2F1 + F4
2 3
COC OP ERACION ES
6 7 SOLU CI ON
6 7
6 x1 x2 x3 s1 s2 s3 W R 7
6 7 x1 = 5
6 1 1 7
6 x2 0 1 1 0 0 1 7
6 2 2 7 F IN XXX x2 = 1
6 7
6 s2 0 0 2 0 1 1 0 6 7
6 7 x3 = 0
6 1 1 7
6 x1 1 0 0 0 0 5 7
4 2 2 5 M axW = 20
W 0 0 1 2 0 2 1 20
.

Ejemplo 4 Resolver .

19
M ax : Z = 60x1 + 0x2 + 90x3 + 0x4 S:E:A
s:a: : x1 2x2 2 x1 2x2 + s1 = 2
x1 + x2 5 x1 + x2 + s2 = 5
x3 + x4 4 x3 + x4 + s3 = 4
x3 2x4 7 x3 2x4 + s4 = 7
x1 ; x2 ; x3 ; x4 0 60x1 + 0x2 90x3 + 0x4 + Z = 0
2 3
VE COC OP ERACION ES
6 7 S:E:A
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 Z R 7
6 7 x1 2x2 + s1 = 2
6 7
6 s1 1 2 0 0 1 0 0 0 0 2 NO 7
6 7 x1 + x2 + s2 = 5
6 7
6 s2 1 1 0 0 0 1 0 0 0 5 NO 7
6 7 x3 + x4 + s3 = 4
6 7
6 VS s3 0 0 1 1 0 0 1 0 0 4 4X 7
6 7 x3 2x4 + s4 = 7
6 7
6 s4 0 0 1 2 0 0 0 1 0 7 7 F4 ! F3 + F4 7
4 5 60x1 + 0x2 90x3 + 0x4 + Z = 0
Z 60 0 90 0 0 0 0 0 1 0 F5 ! 90F3 + F5
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 Z R 7
6 7
6 7
6 VS s1 1 2 0 0 1 0 0 0 0 2 2X 7
6 7
6 7
6 s2 1 1 0 0 0 1 0 0 0 5 5 F2 ! F1 + F2 7
6 7
6 7
6 x3 0 0 1 1 0 0 1 0 0 4 NO 7
6 7
6 7
6 s4 0 0 0 3 0 0 1 1 0 3 NO 7
4 5
Z 60 0 0 90 0 0 90 0 1 360 F5 ! 60F1 + F5
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 Z R 7
6 7
6 7
6 x1 1 2 0 0 1 0 0 0 0 2 NO F1 ! 23 F2 + F1 7
6 7
6 7
6 VS s2 0 3 0 0 1 1 0 0 0 3 1X F2 ! 13 F2 7
6 7
6 7
6 x3 0 0 1 1 0 0 1 0 0 4 NO 7
6 7
6 7
6 s4 0 0 0 3 0 0 1 1 0 3 NO 7
4 5
Z 0 120 0 90 60 0 90 0 1 480 F5 ! 40F2 + F5
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 Z R 7
6 7
6 1 2 7
6 VS x1 1 0 0 0 0 0 0 4 12X F1 ! 3F1 7
6 3 3 7
6 1 1 7
6 x2 0 1 0 0 0 0 0 1 NO F2 ! F1 + F2 7
6 3 3 7
6 7
6 x3 0 0 1 1 0 0 1 0 0 4 NO 7
6 7
6 7
6 s4 0 0 0 3 0 0 1 1 0 3 NO 7
4 5
Z 0 0 0 90 100 40 90 0 1 600 F5 ! 300F1 + F5

20
2 3
COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 Z R 7
6 7 x1 = 0
6 7
6 s1 3 0 0 0 1 2 0 0 0 12 7
6 7 x2 = 5
6 7
6 x2 1 1 0 0 0 1 0 0 0 5 7 F IN
6 7 x3 = 4
6 7
6 x3 0 0 1 1 0 0 1 0 0 4 7
6 7 x4 = 0
6 7
6 s4 0 0 0 3 0 0 1 1 0 3 7
4 5 Zmax = 1800
Z 300 0 0 90 0 240 90 0 1 1800
60x1 + 0x2 + 90x3 + 0x4
x1 2x2 2
x1 + x2 5
x3 + x4 4
x3 2x4 7 , Maximum is at: fx2 = 1; x4 = 0; x1 = 4; x3 = 4g.
x1 0
x2 0
x3 0
x4 0

METODO SIMPLEX CON EJERCICIOS DE ENUNCIADO (PROBLEMAS)

Plantear y resolver
Leer y entender
Restricciones:tiempo de uso de maquina y acabado
P LAN T EAM IEN T O
x1 = # de unidades del producto X a fabricar
x2 = # de unidades del producto Y a fabricar
x3 = # de unidades del producto Z a fabricar
U = U T ILIDAD TOTAL
M ax : U = 6x1 + 8x2 + 12x3
Restricción tiempo maq : x1 + 2x2 + 3x3 900
Restricción tiempo acab : 4x1 + 4x2 + 8x3 5000
x1 ; x2 ; x3 0

P P LE
8
>
> M ax : U = 6x1 + 8x2 + 12x3
>
>
>
>
< s.a : x + 2x + 3x 900
1 2 3
>
> 4x1 + 4x2 + 8x3 5000
>
>
>
>
: x1 ; x2 ; x3 0

21
 T:S:I
2 3
SEA VE COC OP ERACION ES
8 6 7
> 6 7
>
> x + 2x2 + 3x3 + s1 = 900 6 x1 x2 x3 s1 s2 U R 7
< 1 6 7
6 900 p 1 7
4x1 + 4x2 + 8x3 + s2 = 5000 6 VS s1 1 2 3 1 0 0 900 3 F1
7
>
> 6 3 7
>
: 6 5000 8 7
6x1 8x2 12x3 + U = 0 6 s2 4 4 8 0 1 0 5000 3 F1 + F2 7
4 8 5
U 6 8 12 0 0 1 0 4F1 + F3
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 U R 7
6 7
6 1 2 1 p 7
6 VS x3 3 1 0 0 300 900 3F1 7
6 3 3 7
6 4 4 8 7
6 s2 0 1 0 2600 1950 4F1 + F2 7
4 3 3 3 5
U 2 0 0 4 0 1 3600 6F1 + F3
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 U R 7 x1 = 900
6 7
6 7
6 VS x1 1 2 3 1 0 0 900 7 x2 = 0; x3 = 0
6 7
6 7
6 s2 0 4 4 4 1 0 1400 7 Umax = 5400
4 5
p
U 0 4 6 6 0 1 5400 F in
:
Ejemplo 2.

Leer y entender
Restricciones:tiempo de Ensamble y empaque
P LAN T EAM IEN T O
x1 = Número de aparatos tipo 1 a fabricar:
M ax : U = 150x1 + 250x2 + 200x3
x2 = Número de aparatos tipo 2 a fabricar:
s.a. : 300x1 + 300x2 + 400x3 30000
x3 = Número de aparatos tipo 3 a fabricar:
15x1 + 15x2 + 10x3 1200
U = U T ILIDAD TOTAL
2x1 + 2x2 + 3x3 180
M ax : U = 150x1 + 250x2 + 200x3
x1 ; x2 ; x3 0
costo total : 300x1 + 300x2 + 400x3 30000
Horas de ensamble : 15x1 + 15x2 + 10x3 1200
Horas de empaque : 2x1 + 2x2 + 3x3 180
x1 ; x2 ; x3 0

22
 2 3
VE COC OP ERACION ES
SEA 6 7
6 7
6 x1 x2 x3 s1 s2 s3 U R 7
300x1 + 300x2 + 400x3 + s1 = 30000 6
6
7
7
6 s1 300 300 400 1 0 0 0 30000 100 20F2 + F1 7
15x1 + 15x2 + 10x3 + s2 = 1200 6 7
6 p 1 7
6 VS s2 15 15 10 0 1 0 0 1200 80 15 F2
7
2x1 + 2x2 + 3x3 + s3 = 180 6 7
6 2 7
6 s3 2 2 3 0 0 1 0 180 90 15 F2 + F3 7
150x1 250x2 200x3 + U = 0 4 5
50
U 150 250 200 0 0 0 1 0 3 F2 + F4
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 U R 7
6 7
6 7
6 s1 0 0 200 1 20 0 0 6000 30 120F3 + F1 7
6 7
6 2 1 2 7
6 x2 1 1 0 0 0 80 120 5 F3 + F2 7
6 3 15 7
6 5 2 p 3 7
6 VS s3 0 0 3 0 1 0 20 12 5 F3
7
4 15 5
100 50
U 100 0 3 0 3 0 1 20000 20F3 + F4
2 3
COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 U R 7 x2 = 72
6 7
6 7
6 s1 0 0 0 1 4 120 0 3600 7 x3 = 12
6 7
6 3 2 7
6 x2 1 1 0 0 0 72 7 x1 = 0
6 25 5 7
6 2 3 7
6 x3 0 0 1 0 0 12 7 Umax = 20400
4 25 5 5
U 100 0 0 0 14 20 1 20400 f in
ej 3
Una compañía fabrica tres tipos de muebles para patio: sillas,
mecedoras y sillones. Cada uno requiere de madera,plástico
y aluminio, como se muestra en la tabla. La compañía cuenta
con 400 unidades disponibles de madera, 500 de plástico y
1450 de aluminio. Cada silla, mecedora y sillón se vende a
$21, $24 y $36, respectivamente. Suponga que todos los
muebles pueden venderse, determine la producción para
que el ingreso total sea máximo. ¿Cuál es el ingreso máximo?
I : ingreso máximo x1 : # de sillas a fabricar,x1 : # de mecedoras afabricar, x3 : # de sillones afabricar
M aximizar : I = 21x1 + 24x2 + 36x3 ;
x1 + x2 + x3 400
x1 + x2 + 2x3 500 En casa terminar SEA; T SI simplex …n.
2x1 + 3x2 + 5x3 14500
x1 ; x2 ; x3 0:
Hoy 22-5-21
SIMPLEX CON INFINITAS SOLUCIONES Y SIN SOLUCIÓN:
1) Sin solución.
23
 Si en algún paso del metodo simplex obtenemos que no hay cocientes, entonces el problema de progra-
mación lineal no tiene solución (La región factible es no acotada).
2) In…nitas soluciones.
Se obtiene una solución con simplex (todos los indicadores son no negativos). Una variable que tiene valor
cero tambien tiene indicador cero. (xi = 0 y su indicador es tambien 0)
Una segunda solución se obtiene realizando otro paso del metodo simplex tomando como variable de
entrada la columna de xi :
Ejemplos
M ax : Z = 8x1 + 2x2 + 4x3 M ax : Z = 8x1 + 2x2 + 4x3
s:a: : x1 x2 + 4x3 6 s:a: : x1 x2 + 4x3 6
1. x1 x2 x3 4 por ( 1) x1 + x2 + x3 4
x1 6x2 + x3 8 x1 6x2 + x3 8
x1 ; x2 ; x3 0 x1 ; x2 ; x3 0
2 3
VE COC OP ERACION ES
SEA 6 7
6 7
6 x1 x2 x3 s1 s2 s3 Z R 7
x1 x2 + 4x3 + s1 = 6 6 7
6 p 7
6 VS s1 1 1 4 1 0 0 0 6 6 7
x1 + x2 + x3 + s2 = 4 6 7
6 7
6 s2 1 1 1 0 1 0 0 4 4 1 No F1 + F2 7
x1 6x2 + x3 + s3 = 8 6 7
6 7
6 s3 1 6 1 0 0 1 0 8 8 F1 + F3 7
8x1 2x2 4x3 + Z = 0 4 5
Z 8 2 4 0 0 0 1 0 8F1 + F4
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 Z R 7
6 7
6 7
6 x1 1 1 4 1 0 0 0 6 6 1 NO 7
6 7
6 7
6 s2 0 0 5 1 1 0 0 10 10 0 NO F1 + F2 7
6 7
6 7
6 s3 0 5 3 1 0 1 0 2 2 5 NO F1 + F3 7
4 5
Z 0 10 28 8 0 0 1 48 8F1 + F4
Como no hay cocientes entonces el problema no tiene solución pues la región factible es no acotada.
2.
Max:Z = 6x1 + 2x2 + x3 Max:Z = 6x1 + 2x2 + x3 SEA
s:a : 2x1 + x2 + x3 7 s:a : 2x1 + x2 + x3 7 2x1 + x2 + x3 + s1 = 7
4x1 x2 6 por ( 1) 4x1 + x2 6 4x1 + x2 + s2 = 6
x1 ; x2 ; x3 0 x1 ; x2 ; x3 0 6x1 2x2
x3 + Z = 0
2 32
VE COC OP ERACION ES VE COC O
6 76
6 76
6 x1 x2 x3 s1 s2 Z R 76 x1 x2 x3 s1 s2 Z R
6 76
6 1 76 1 1 p
6 s1 2 1 1 1 0 0 7 3:5 2 F2 + F1
7 6 V S s1 0 1 1 0 4 4
6 76 2 2
6 p 1 76 1 1 3
6 VS s2 4 1 0 0 1 0 6 1:5 F2 76 x1 1 0 0 0 NO
4 4 54 4 4 2
3 1 3
Z 6 2 1 0 0 1 0 2 F2 + F3 Z 0 2 1 0 2 1 9

24
 2 3
VE COC OP ERACION ES Primera solución
6 7
6 7
6 x1 x2 x3 s1 s2 Z R 7 x3 = 4
6 7
6 1 1 7 3
6 x3 0 1 1 0 4 8 2F2 + F1 7 x1 =
6 2 2 7 2
6 1 1 3 p 7
6 VS x1 1 4 0 0 0 6 4F2 7 x2 = 0
4 4 2 5
Z 0 0 0 1 1 1 13 F IN ZM ax = 13
Como la variable x2 = 0 y tiene indicador 0, el problema tiene In…nitas soluciones. Para hallar una
segunda
2 solución, hacemos otro paso de simplex con x2 como variable de 3
entrada:
COC OP ERACION ES Segunda solución
6 7
6 7
6 x1 x2 x3 s1 s2 Z R 7 x1 = 0
6 7
6 7
6 x3 2 0 1 1 1 0 1 7 x2 = 6
6 7
6 7
6 x2 4 1 0 0 1 0 6 7 x3 = 1
4 5
Z 0 0 0 1 1 1 13 F IN Zmax = 13
Segunda solución Inf initas soluciones: 8
Primera solución
>
> 3
> x1 = 2 (1 t)
x1 = 0 x1 = 23 x1 = 0t + 32 (1 t) > >
>
< x = 6t
2
x2 = 6 x2 = 0 ! x2 = 6t + 0 (1 t) .
>
> x3 = 3t + 4
>
x3 = 1 x3 = 4 x3 = 1t + 4 (1 t) > >
>
: 0 t 1
Zmax = 13 ZM ax = 13 0 t 1
Las in…nitas soluciones corresponden al segmento de recta que une los puntos (x1 ; x2 ; x3 ) de la primera
solución con el punto (x1 ; x2 ; x3 ) de la segunda solución
3. Problema:
Una compañía produce tres clases de dispositivos que requieren de tres diferentes procesos de producción.
La empresa ha asignado un total de 120 horas para el proceso 1, 180 para el 2 y 170 horas para el 3. La tabla
siguiente proporciona el número de horas por dispositivo para cada procedimiento.

max : U = 50x1 + 50x2 + 20x3

Dispositivo 1 Dispositivo 2 Dispositivo 3
s:a : Pro1 : 3x1 + 3x2 + 6x3 120
Proceso 1 3 3 6
Pro1 : 3x1 + 6x2 + 7x3 180
Proceso 2 3 6 7
Pro1 : 4x1 + 6x2 + 6x3 170
Proceso 3 4 6 6
x1 ; x2 ; x3 0

Si la utilidad es de $50 por el dispositivo 1, de $50 por el 2 y de $20 por el 3, encuentre el número de
dispositivos de cada clase que la compañía debe producir para maximizar la utilidad.
Plantemiento: x1 : # de dispositivos tipo 1 a fabricar, x2 : # de dispositivos tipo 2 a fabricar, x3 : # de
dispositivos tipo 3 a fabricar. U utilidad total.

25
 2 3
VE COC OP ERACION ES
6 7
6 7
3x1 + 3x2 + 6x3 + s1 = 120 6 x1 x2 x3 s1 s2 s3 U R 7
6 7
6 p 1 7
3x1 + 6x2 + 7x3 + s2 = 180 6 V S s1 3 3 6 1 0 0 0 120 40 3 F1
7
6 7
6 7
4x1 + 6x2 + 6x3 + s3 = 170 6 s2 3 6 7 0 1 0 0 180 60 F1 + F2 7
6 7
6 170 4 7
50x1 50x2 20x3 + U = 0 6 s3 4 6 6 0 0 1 0 170 3 F1 + F3 7
4 4 5
50
U 50 50 20 0 0 0 1 0 3 F1 + F4
2 3
VE COC OP ERACION ES
6 7 solución 1
6 7
6 x1 x2 x3 s1 s2 s3 U R 7
6 7 x1 = 40
6 1 1 7
6 x1 1 1 2 0 0 0 40 40 2 F3 + F1 7
6 3 7 x2 = 0
6 3 7
6 s2 0 3 1 1 1 0 0 60 20 2 F3 + F2 7
6 7 x3 = 0
6 4 p 1 7
6 VS s3 0 2 2 0 1 0 10 5 2 F3
7
4 3 5 Umax = 2000
U 0 0 80 50 3 0 0 1 2000 F IN SOL1
Como
2 x2 = 0 y su indicador es cero .inf initas soluciones. 3
COC OP ERACION ES
6 7 solución 2
6 7
6 x1 x2 x3 s1 s2 s3 U R 7
6 7 x1 = 35
6 1 7
6 x1 1 0 3 1 0 0 35 7
6 2 7 x2 = 5
6 3 7
6 s2 0 0 4 1 1 0 45 7
6 2 7 x3 = 0
6 2 1 7
6 x2 0 1 1 0 0 5 7
4 3 2 5 Umax = 2000
U 0 0 80 50 3 0 0 1 2000 F IN SOL2
In…nitas soluciones
solución 2 solución 1 IN F solución 8
>
>
> x1 = 5t + 40
x1 = 35 x1 = 40 x1 = 35t + 40 (1 t) > >
>
< x2 = 5t
x2 = 5 x2 = 0 x2 = 5t + 0 (1 t)
>
> x3 = 0
>
x3 = 0 x3 = 0 x3 = 0t + 0 (1 t) > >
>
: 0 t 1
Umax = 2000 Umax = 2000 0 t 1
Ejercicio:
M ax : P = x1 + 2x2 + x3 + 2x4 SEA
x1 x2 2 x1 x2 + s1 = 2
x2 x3 3 x2 x3 + s2 = 3
x2 3x3 + x4 4 x2 3x3 + x4 + s3 = 4
x1 ; x2 ; x3 ; x4 0 x1 2x2 x3 2x4 + P = 0
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 P R 7
6 7
6 7
6 s1 1 1 0 0 1 0 0 0 2 F2 + F1 7
6 7
6 p 7
6 VS s2 0 1 1 0 0 1 0 0 3 3 7
6 7
6 7
6 s3 0 1 3 1 0 0 1 0 4 4 F2 + F3 7
4 5
P 1 2 1 2 0 0 0 1 0 2F2 + F4
26
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 P R 7
6 7
6 7
6 s1 1 0 1 0 1 1 0 0 5 N o hay 7
6 7
6 7
6 x2 0 1 1 0 0 1 0 0 3 N o hay 7
6 7
6 7
6 s3 0 0 2 1 0 1 1 0 1 N o hay 7
4 5
P 1 0 3 2 0 2 0 1 6
El problema no tiene solución (No hay cocientes) la región factible es no acotada.
AQUIII
2x1 + x2 4x3
6x1 + 3x2 3x3 10
x1 x2 + x3 1
2x1 x2 + 2x3 12 , Maximum is at: x3 = 0; x2 = 49 ; x1 = 13
9

x1 0
x2 0
x3 0
M ax : Z = 2x1 + x2 4x3
6x1 + 3x2 3x3 10
Ejercicio x1 x2 + x3 1
2x1 x2 + 2x3 12
x1 ; x2 ; x3 0
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 Z R 7
6 7
6 7
6 s1 7
6 7
6 7
6 VS s2 7
6 7
6 7
6 s3 7
4 5
Z
Leer SIMPLEX Y VARIABLES ARTIFICIALES

8x1 + 2x2 + 4x3

x1 x2 + 4x3 6
x1 x2 x3 4
x1 6x2 + x3 8 , Maximum is at: UNBOUNDED
x1 0
x3 0
x2 0

27
 x1 + 2x2 + x3 + 2x4
x1 x2 2
x2 x3 3
x2 3x3 + x4 4
, Maximum is at: UNBOUNDED
x1 0
x3 0
x2 0
x4 0
5x1 + 6x2 + x3 2 3
VE COC OP ERACION ES
9x1 + 3x2 2x3 5 6
6
7
7
6 x1 x2 x3 s1 s2 s3 W R 7
4x1 + 2x2 x3 2 66
7
7
6 3 7
s1 9 3 2 1 0 0 0 5 1:66 F1 ! 2 F2 + F1
x1 4x2 + x3 3 66
7
7
6 VS 1 7
s2 4 2 1 0 1 0 0 2 1 F2 ! 2 F2
x1 0 6 7
6 7
6 s3 1 4 1 0 0 1 0 3 no F3 ! 2F2 + F3 7
x3 0 4 5
W 5 6 1 0 0 0 1 0 F4 ! 3F2 + F4
x2 0
2 32 3 2 3
3 1 3
1 0 0 9 3 2 1 0 0 0 5 3 0 1 0 0 2
6 2 76 7 6 2 2 7
6 1 76 7 6 1 1 7
6 0 0 0 76 4 2 1 0 1 0 0 2 7 6 2 1 0 0 0 1 7
6 2 76 7=6 2 2 7
6 76 7 6 7
6 0 2 1 0 76 1 4 1 0 0 1 0 3 7 6 9 0 1 0 2 1 0 7 7
4 54 5 4 5
0 3 0 1 5 6 1 0 0 0 1 0 7 0 4 0 3 0 1 6
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 W R 7
6 7
6 1 3 7
6 s1 3 0 1 0 0 2 no 7
6 2 2 7
6 1 1 7
6 s2 2 1 0 0 0 1 no 7
6 2 2 7
6 7
6 s3 9 0 1 0 2 1 0 7 no 7
4 5
W 7 0 4 0 3 0 1 6
Como no hay cocientes el problema no tiene solución porque la región factible es no acotada.

Problema:
Una compañía produce tres clases de dispositivos que requieren de tres diferentes procesos de producción.
La empresa ha asignado un total de 120 horas para el proceso 1, 180 para el 2 y 170 horas para el 3. La tabla
siguiente proporciona el número de horas por dispositivo para cada procedimiento.

Dispositivo 1 Dispositivo 2 Dispositivo 3

Proceso 1 3 3 6
Proceso 2 3 6 7
Proceso 3 4 6 6

28
 Si la utilidad es de $50 por el dispositivo 1, de $50 por el 2 y de $20 por el 3, encuentre el número de
dispositivos de cada clase que la compañía debe producir para maximizar la utilidad.

Una compañía produce tres clases de dispositivos que requieren de tres diferentes procesos de producción.
La empresa ha asignado un total de 190 horas para el proceso 1, 180 para el 2 y 165 horas para el 3. La tabla
siguiente proporciona el número de horas por dispositivo para cada procedimiento.

Dispositivo 1 Dispositivo 2 Dispositivo 3

Proceso 1 5.5 5.5 6.5
Proceso 2 3.5 6.5 7.5
Proceso 3 4.5 6 6.5
Si la utilidad es de $50 por el dispositivo 1, de $50 por el 2 y de $50 por el 3, encuentre el número de
dispositivos de cada clase que la compañía debe producir para maximizar la utilidad.
M ax : U = 50x1 + 50x2 + 50x3 S:E:A:
8
5:5x1 + 5:5x2 + 6:5x3 190 por 2 > >
> 11x1 + 11x2 + 135x3 + s1 = 380
>
>
>
<
3:5x1 + 6:5x2 + 7:5x3 180 por 2 7x1 + 13x2 + 15x3 + s2 = 360
4:5x1 + 6x2 + 6:5x3 165 por 2 > > 9x + 12x + 13x + s = 165
>
> 1 2 3 3
>
>
x1 0; x2 0; x3 0 : 50x1 50x2 50x3 + U = 0
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 W R 7
6 7
6 7
6 V S s1 11 11 13 1 0 0 0 380 380 = 34: 545 F 1 ! 1
F1 7
6 11 11 7
6 360 7 7
6 s2 7 13 15 0 1 0 0 360 = 51: 429 F2 ! F
11 1 + F 2 7
6 7 7
6 330 9 7
6 s3 9 12 13 0 0 1 0 330 F3 ! 11 F1 + F3 7
4 9 5
W 50 50 50 0 0 0 1 0 36: 667 F4 ! 50 11 F 1 + F 4
2 32 3 2 3
1 13 1 380
0 0 0 11 11 13 1 0 0 0 380 1 1 11 0 0 0
6 11 76 7 6 11 11 7
6 7 76 7 6 7
6 11 1 0 0 76 7 13 15 0 1 0 0 360 7 6 0 6 74 7
1 0 0 1300 7
6 76 7=6 11 11 11 7
6 9 76 7 6 26 9 210 7
6 11 0 1 0 7 6 9 12 13 0 0 1 0 330 7 6 0 3 11 0 1 0 7
4 54 5 4 11 11 5
50 100 50 19 000
0 0 1 50 50 50 0 0 0 1 0 0 0 0 0 1
2 11 11 11
3 11

VE COC OP ERACION ES
6 7 Solución 1:
6 7
6 x1 x2 x3 s1 s2 s3 W R 7
6 7 x1 = 380
6 13 1 380 1 7 11
6 x1 1 1 0 0 0 F 1 ! F
3 3 + F 1 7
6 11 11 11 7 x = 0
6 74 7 1300 7 2
6 s2 0 6 1 0 0 F 2 ! 2F 3 + F 2 7
6 11 11 11 7 x3 = 0
6 7
6 V S s3 0 3 26 9
0 1 0 210
XX F3 ! 1
F 3 7
4 11 11 11 3 5 Umax = 19 000
100 50 19 000 11
W 0 0 11 11 0 0 1
2911
x
22 = 0 variable de3valor
2 0 con indicador 0 in…nitas soluciones
3 2iteramos simplex conVE= x2 3
1 13 1 380
1 0 0 1 1 0 0 0 1 0 13 4
0 1
0 310
6 3 76 11 11 11 7 6 33 11 3 11 7
6 76 74 7 1300 7 7 6 7
6 0 1 2 0 76 0 6 1 0 0 6 0 0 2 1 1 2 0 80 7
6 76 11 11 11 7=6 7
6 1 76 26 9 210 7 6 7
6 0 0 0 76 0 3 0 1 0 7 6 0 1 26 3
0 1
0 70 7
4 3 54 11 11 11 5 4 33 11 3 11 5
100 50
0 0 0 1 0 0 11 11 0 0 1 1911 000
0 0 100
11
50
11 3 0 0 1 1911 000
2
COC OP ERACION ES
6 7 Solución 2:
6 7
6 x1 x2 x3 s1 s2 s3 W R 7
6 7 x1 = 310
6 13 4 1 310 7 11
6 x1 1 0 0 0 7
6 33 11 3 11 7 x2 = 70
6 7 11
6 s2 0 0 2 1 1 2 0 80 7
6 7 x = 0
6 7 3
6 x2 0 1 26 3
0 1
0 70
XX 7
4 33 11 3 11 5 Umax = 19 000
100 50 19 000 11
W 0 0 11 11 0 0 1 11

Solución 1: Solución 2: In…nitas oluciones 8

>
> x1 = 380 70
380 310 >
> 11 11 t
x1 = x1 = x1 = 310 t + 380
(1 t) >
>
11 11 11 11 < x = 70 t
2 11
70 70 :
x2 = 0 x2 = x2 = 11 t + 0 (1 t)
11 >
> x3 = 0
>
>
x3 = 0 x3 = 0 x3 = 0t + 0 (1 t) >
>
: 0 t 1
19 000 19 000
Umax = 11 Umax = 11 Umax = 1911 000

5x1 + 6x2 + x3 2 3
VE COC OP ERACION ES
9x1 + 3x2 2x3 5 6
6
7
7
6 x1 x2 x3 s1 s2 s3 W R 7
4x1 + 2x2 x3 2 66
7
7
6 3 7
s1 9 3 2 1 0 0 0 5 1:66 F1 ! 2 F2 + F1
x1 4x2 + 11x3 3 6
6
7
7
6 VS 1 7
s2 4 2 1 0 1 0 0 2 1 F2 ! 2 F2
x1 0 6 7
6 7
6 s3 1 4 11 0 0 1 0 3 no F3 ! 2F2 + F3 7
x3 0 4 5
W 5 6 1 0 0 0 1 0 F4 ! 3F2 + F4
x2 0
2 32 3 2 3
3 1 3
1 0 0 9 3 2 1 0 0 0 5 3 0 1 0 0 2
6 2 76 7 6 2 2 7
6 1 76 7 6 1 1 7
6 0 0 0 76 4 2 1 0 1 0 0 2 7 6 2 1 0 0 0 1 7
6 2 76 7=6 2 2 7
6 76 7 6 7
6 0 2 1 0 76 1 4 11 0 0 1 0 3 7 6 9 0 9 0 2 1 0 7 7
4 54 5 4 5
0 3 0 1 5 6 1 0 0 0 1 0 7 0 4 0 3 0 1 6
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 W R 7
6 7
6 1 3 1 7
6 s1 3 0 1 0 0 2 no F1 ! 18 F3 + F1 7
6 2 2 7
6 1 1 1 7
6 VS x2 2 1 0 0 0 1 no F2 ! 18 F3 + F2 7
6 2 2 7
6 1 7
6 s3 9 0 9 0 2 1 0 7 o:k: F3 ! 9 F3
7
4 5
W 7 0 4 0 3 0 1 6 F4 ! 94 F3 + F4
30
 2 32 3 2 3
1 1 3 7 25 1 43
1 0 0 3 0 1 0 0 2 0 0 1 0
6 18 76 2 2 7 6 2 18 18 18 7
6 1 76 1 1 7 6 7
6 0 1 0 76 2 1 0 0 1 7 6 52 1 0 0
0 11 1
0 25 7
6 18 76 2 2 7=6 18 18 18 7
6 1 76 7 6 2 1 7 7
6 0 0 0 76 9 0 9 0 2 1 0 7 7 6 1 0 1 0 0 7
4 9 54 5 4 9 9 9 5
4 35 4 82
0 0 9 1 7 0 4 0 3 0 1 6 11 0 0 0 9 9 1 9
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 W R 7
6 7 x =0
6 7 25 1 43 7 1
6 s1 0 0 1 0 7
6 2 18 18 18 7 x = 25
6 5 11 1 25 7 2 18
6 x2 1 0 0 0 7
6 2 18 18 18 7 x =7
6 2 1 7 7 3 9
6 x3 1 0 1 0 0 7
4 9 9 9 5
35 4 82
W 11 0 0 0 9 9 1 9

28 DE ABRIL 2021
7.6 Variables arti…ciales.
Para iniciar el método simplex se requiere de una solución básica factible, SBF. (Álgebraicamente, se
comienza en un vértice con el uso de la tabla simplex inicial y cada tabla subsecuente conduce a otro vértice
hasta que se llega al punto que representa una solución óptima.) Para un problema de programación lineal
estándar, se empieza con la SBF, en la que todas las variables de decisión son 0. Sin embargo, para un
problema de maximización que no esté en la forma estándar, tal SBF podría no existir. En esta sección se
presentará la forma en que se utiliza el método simplex en estas situaciones.
Si se tiene un problema de programación lineal donde se debe maximizar una función lineal sujeta a
restricciones de mayor o igual o igual la solución nula no es una solución basica factible del problema por
tanto no puedes aplicar simplex. Se debe replantear el problema usando variables arti…ciales ti para que la
solución nula sea una solución basica factible y podamos iniciar simplex.

Supongamos que tenemos el problema de programación lineal:

Maximizar Z = c1 x1 + c2 x2 + c3 x3 + + cn xn
Sujeto a:
a11 x1 + a21 x2 + a31 x3 + + an1 xn b1
a21 x1 + a22 x2 + a23 x3 + + a2n xn = b2
Como tenemos dos restricciones una de tipo y otra de tipo = debemos agregar dos variables arti…ciales
t1 y t2 para replantear el problema de programación lineal:
c1 x1 + c2 x2 + c3 x3 + + cn xn Z=0
Se replante el problema y ahora se maximizar W = Z M t1 M t2 (M es un numero grande y positivo)
y el sistema de ecuaciones asociado es:
W = Z M t1 M t2 ! Z + M t1 + M t2 + W = 0
8
>
> a11 x1 + a11 x2 + a13 x3 + + a1n xn s1 + t1 = b1 restar una variable de excedencia s1 y sumar t1
>
<
a21 x1 + a22 x2 + a23 x3 + + a2n xn + t2 = b2 = sumar una variable arti…cial t2
>
>
>
: c x
1 1 c2 x2 c3 x3 cn xn + M t1 + M t2 + W = 0 Z + M t1 + M t2 + W = 0
31
 2 3
OP ERACION ES
6 7
6 7
6 x1 x2 x3 xn s1 t1 t2 W R 7
6 7
6 7
6 S t1 a11 a12 a13 a1n 1 1 0 0 b1 7
6 7
6 7
6 t2 a21 a22 a23 a2n 0 0 1 0 b2 7
6 7
6 7
6 W c1 c2 c3 cn 0 M M 1 0 F3 ! M F 1 + F3 7
6 7
6 = = 7
6 W 0 M 1 M b1 F3 ! M F2 + F3 7
4 5
W m1 m2 m3 mn mn+1 0 0 1 M b1 M b2
2 3
VE COC OP
6 7
6 7
6 x1 x2 x3 xn s1 t1 t2 W R 7
6 7
6 7
TSI:6 V S t1 a11 a11 a11 a11 1 1 0 0 b1 7
6 7
6 7
6 t2 a11 a11 a11 a11 0 0 1 0 b2 7
4 5
W m1 m2 m3 mn mn+1 0 0 1 M b1 M b2
Aplicar simplex
La
2 idea es que salgan las variables arti…ciales t1 y t2 : 3
VE COC OP
6 7
6 7
6 x1 x2 x3 xn s1 t1 t2 W R 7
6 7
6 7
6 V S v1 a11 a11 a11 a11 1 1 0 0 r1 7
6 7
6 7
6 v2 a11 a11 a11 a11 0 0 1 0 r2 7
4 5
W c1 c2 c3 cn 0 0 0 1 r3
En este momento tomamos una solución parcial: t1 = 0; t2 = 0 y W = Z M t1 M t2 = Z:
Y
2 eliminamos en la siguiente tabla las columnas de las variables arti…ciales.
3
VE COC OP
6 7
6 7
6 x1 x2 x3 xn s1 Z R 7
6 7
6 7
6 V S v1 a11 a11 a11 a11 1 0 r1 7
6 7
6 7
6 v2 a11 a11 a11 a11 0 0 r2 7
4 5
Z c1 c2 c3 cn 0 1 r3
y se sigue con el metodo simplex hasta llegar a que todos los indicadores son no negativos y obtener la
solución.
EJEMPLO:
M ax : Z = 2x1 + x2 x3
x1 + 2x2 + x3 5
1)
x1 + x2 + x3 1
Esta restricción requiere de una variable arti…cial t
x1 ; x2 ; x3 0

32
 2
C OP ERACION E
6
Replantear V.A.
6
6 x1 x2 x3 s1 s2 t W R
Max: W = Z M t ! Z + M t + W = 0 66
6 s1 1 2 1 1 0 0 0 5
SEA : x1 + 2x2 + x3 + s1 = 5 6
6
6 t 1 1 1 0 1 1 0 1
x1 + x2 + x3 s2 + t = 1 6
6
6 W 2 1 1 0 0 M 1 0 F3 ! M F2 + F
2x1 x2 + x3 + M t + W = 0 4
W M 2 M 1 M +1 0 M 0 1 M
T SI
2 3
VE C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 t W R 7
6 7
6 7
6 s1 1 2 1 1 0 0 0 5 2:5 2F2 + F1 7 (M + 1) ( 1)+
6 7
6 p 7
6 VS t 1 1 1 0 1 1 0 1 1 7
4 5
W M 2 M 1 M +1 0 M 0 1 M (M + 1) F2 + F3
M 22 = 3 3
COC OP ER
6 7 Solucion parcial
6 7
6 x1 x2 x3 s1 s2 t W R 7
6 7 Salieron la var arti…ciales
6 7
6 s1 3 0 1 1 2 2 0 3 7
6 7 t = 0; W = Z M t = Z
6 7
6 x2 1 1 1 0 1 1 0 1 7
4 5 Eliminar la columna t
W 3 0 2 0 1 M +1 1 1
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 Z R 7
6 7
6 1 7
6 VS s1 3 0 1 1 2 0 3 1 3 F1
7
6 7
6 1 7
6 x2 1 1 1 0 1 0 1 No 3 F1 + F3 7
4 5
Z 3 0 2 0 1 1 1 F1 + F3
2 3
OP F IN
6 7
6 7
6 x1 x2 x3 s1 s2 Z R 7 x1 = 1
6 7
6 1 1 2 7
6 x1 1 0 0 1 7 x2 = 2
6 3 3 3 7
6 2 1 1 7
6 x2 0 1 0 2 7 x3 = 0
4 3 3 3 5
Z 0 0 1 2 1 1 4 Zmax = 4
Las restricciones de igualdad nos permiten replantear el problema con menos variables.
M ax : Z = 3x1 2x2 + x3
x1 + x2 + x3 1
2) x1 x2 + x3 2
x1 + x2 + x3 6
x1 ; x2 ; x3 0

33
 Replantear M ax : W = Z M t1 M t2 ! Z + M t1 + M t2 + W = 0
x1 + x2 + x3 + s1 = 1
x1 x2 + x3 s2 + t1 = 2
x1 + x2 + x3 s3 + t2 = 6
3x1 + 2x2 x3 + M t1 + M t2 + W = 0
2 3
C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t1 t2 W R 7
6 7
6 7
6 s1 1 1 1 1 0 0 0 0 0 1 7
6 7
6 7
6 t1 1 1 1 0 1 0 1 0 0 2 7
6 7
6 7
6 t2 1 1 1 0 0 1 0 1 0 6 7
6 7
6 7
6 W 3 2 1 0 0 0 M M 1 0 F4 ! M F 2 + F4 7
6 7
6 7
6 W M 3 M +2 M 1 0 M 0 0 M 1 2M F5 ! M F3 + F5 7
4 5
W 3 2 2M 1 0 M M 0 0 1 8M
TSI:
2 3
VE COC OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t1 t2 W R 7
6 7
6 7
6 VS s1 1 1 1 1 0 0 0 0 0 1 1F 7
6 7
6 7
6 t1 1 1 1 0 1 0 1 0 0 2 2 F1 + F2 7
6 7
6 7
6 t2 1 1 1 0 0 1 0 1 0 6 6 F1 + F3 7
4 5
W 3 2 2M 1 0 M M 0 0 1 8M (2M + 1) F1 + F4
2 3
COC OP
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t1 t2 W R 7
6 7
6 7
6 x3 1 1 1 1 0 0 0 0 0 1 7
6 7
6 7
6 t1 0 2 0 1 1 0 1 0 0 1 7
6 7
6 7
6 t2 2 0 0 1 0 1 0 1 0 5 7
4 5
W 2M 2 2M + 3 0 2M + 1 M M 0 0 1 6M + 1
F IN
Los indicadores son no negativos
Si las variable arti…ciales no salen el problema no tiene solución (Región factible vacía). FIN
Ejemplo 3 una restricción de igualdad y una de mayor o igual.
M ax : Z = x1 + 4x2 x3 Replantear M ax : W = Z M t1 M t2
x1 + x2 x3 5 x1 + x2 x3 s1 + t1 = 5
x1 + x2 + x3 3 x1 + x2 + x3 + s2 = 3
x1 x2 + x3 = 7 x1 x2 + x3 + t2 = 7
x1 ; x2 ; x3 0 x1 4x2 + x3 + M t1 + M t2 + W = 0

34
2 3
C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 t1 t2 W R 7
6 7
6 7
6 t1 1 1 1 1 0 1 0 0 5 7
6 7
6 7
6 s2 1 1 1 0 1 0 0 0 3 7
6 7
6 7
6 t2 1 1 1 0 0 0 1 0 7 7
6 7
6 7
6 W 1 4 1 0 0 M M 1 0 F4 ! M F1 + F4 7
6 7
6 7
6 W M 1 M 4 M +1 M 0 0 M 1 5M F5 ! M F3 + F5 7
4 5
W 2M 1 4 1 M 0 0 0 1 12M
2 3
VE COC OP ERACION
6 7
6 7
6 x1 x2 x3 s1 s2 t1 t2 W R 7
6 7
6 7
6 t1 1 1 1 1 0 1 0 0 5 F1 ! F2 + F1 7
TSI6
6
7
7
6 VS s2 1 1 1 0 1 0 0 0 3 3F 7
6 7
6 7
6 t2 1 1 1 0 0 0 1 0 7 F3 ! F2 + F3 7
4 5
W 2M 1 4 1 M 0 0 0 1 12M F4 ! (2M + 1) F2 + F4
2 3
VE F IN
6 7
6 7
6 x1 x2 x3 s1 s2 t1 t2 W R 7 IN DIC 0
6 7
6 7
6 t1 0 0 2 1 1 1 0 0 2 7 Las var artif no salieron
6 7
6 7
6 VS s2 1 1 1 0 1 0 0 0 3 7
6 7
6 7
6 t2 1 1 1 0 0 0 1 0 7 7 N o tiene SOLU CI ON
4 5
W 0 2M 3 2M + 2 M 2M + 1 0 0 1 6M + 3 Re gion factible V AC IA
OTRA FORMA: Las restricciones de igualdad permiten replantear el problema con menos variables
M ax : Z = x1 + 4x2 x3
x1 + x2 x3 5
De la restricción de igualdad se despeja una variable
x1 + x2 + x3 3
y se reemplaza en todas partes
x1 x2 + x3 = 7 , x3 = 7 x1 + x2
x1 ; x2 ; x3 0
M ax : Z = x1 + 4x2 (7 x1 + x2 ) M ax : Z = 2x1 + 3x2 7 M ax : Z = 2x1 + 3x2 7
x1 + x2 (7 x1 + x2 ) 5 2x1 12 ! x1 6 x1 6
x1 + x2 + 7 x1 + x2 3 2x2 4 ! x2 2 x2 2
x3 = 7 x1 + x2 0! x1 + x2 7 por ( 1) x1 x2 7 x1 x2 7
x1 ; x2 0 x1 ; x2 0 x1 ; x2 0
Método grá…co.
Al intersecar los semi planos x2 2 y x2 0 tenemos que la región factible es vacía.

35
 M ax : Z = 3x1 2x2 + x3
x1 + x2 + x3 5
x1 x2 + 2x3 2
Tarea 3x1 x2 x3 3 pend..
x1 0
x2 0
x3 0
Restricciones de igualdad: Rebajar el número de variables:
Ejemplo Solución de la Tarea: Resolver usando las restricciones de igualdad para rebajar dos variables y
resolver usando metodo gra…co
max : Z = 4x1 + 2x2 + 3x3 + x4 Despejar una variable
s:a : x1 + 3x3 + 4x4 = 8 en cada la restricción
x2 + 3x3 + 5x4 = 9 de igualdad
x1 + 2x2 + 2x3 + x4 1 x1 = 8 3x3 4x4
3x1 + x2 + x3 + 2x4 2 x2 = 9 3x3 5x4
x1 ; x2 ; x3 ; x4 0 Reemplazar x1 ; x2
max Z = 4 (8 3x3 4x4 ) + 2 (9 3x3 5x4 ) + 3x3 + x4 max Z = 50 15x3 25x4 max Z = 50 15x3 25x4
8 3x3 4x4 0 8 3x3 + 4x4 3x3 + 4x4 8
9 3x3 5x4 0 9 3x3 + 5x4 3x3 + 5x4 9
8 3x3 4x4 + 2 (9 3x3 5x4 ) + 2x3 + x4 1 7x3 13x4 + 26 1 7x3 + 13x4 25
3 (8 3x3 4x4 ) + 9 3x3 5x4 + x3 + 2x4 2 33 11x3 15x4 2 11x3 + 15x4 31
x3 0 x3 0 x3 0
x4 0 x4 0 x4 0
Metodo gra…co

3x3 + 4x4 = 8
, Solution is: x3 = 34 ; x4 = 1
3x3 + 5x4 = 9

V ertices : A = (0; 0) ; B = 0; 59 ; C = 8
3; 0 ;D = 4
3; 1 Evaluacion : Z = 50 15x3 25x4
x1 = 8 3x3 4x4
9 8 4
Z (A) = 50; Z (B) = 50 25 5 = 5; Z (C) = 50 15 3 = 10; Z (D) = 50 15 3 25 (1) = 5
x2 = 9 3x3 5x4
Zmax = 50 y se obtiene cuando x3 = 0; x4 = 0
Sol x3 = 0; x4 = 0; x1 = 8; x2 = 9; Zmax = 50:
PROBLEMAS: Planteamiento maximizar, usar variables arti…ciales para restricciones de ; o rebajar el
36
número de variables si hay restricciones de igualdad.

P lanteamiento
x = # de libreros estandar a fabricar
y = # de libreros ejecutivo a fabricar
U = Utilidad total
M ax U = 35x + 40y sujeto a:
T iempo ensamble: 2x + 3y 400
T iempo acabado: 3x + 4y 500
T iempo sindicado: 3x + 4y 250
x; y 0
Rutina para el estudiante resolverlo con metodo grá…co
..
.

P lanteamiento
x1 = # de productos X a fabricar
x2 = # de productos Y a fabricar
x3 = # de productos Z a fabricar
U = Utilidad total
2.
M ax U = 50x1 + 60x2 + 75x3 sujeto a:
T iempo maquina A: x1 + 2x2 + 2x3 40
T iempo maquina B: x1 + x2 + 2x3 30
x3 5 ! una var artif
x1 ; x2 ; x3 0

37
Replanteo: M ax W = U M t = 50x1 + 60x2 + 75x3 Mt :
SEA : x1 + 2x2 + 2x3 + s1 = 40
x1 + x2 + 2x3 + s2 = 30
x3 s3 + t = 5
50x1 60x2 75x3 + M t + W = 0
2 3
C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t W R 7
6 7
6 7
6 s1 1 2 2 1 0 0 0 0 40 7
6 7
6 7
6 s2 1 1 2 0 1 0 0 0 30 7
6 7
6 7
6 t 0 0 1 0 0 1 1 0 5 7
6 7
6 7
6 W 50 60 75 0 0 0 M 1 0 F4 ! M F3 + F4 7
4 5
W 50 60 M 75 0 0 M 0 1 5M
2 3
VE C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t W R 7
6 7
6 7
6 s1 1 2 2 1 0 0 0 0 40 F1 ! 2F3 + F1 7
6 7
6 7
6 s2 1 1 2 0 1 0 0 0 30 F2 ! 2F3 + F2 7
6 7
6 7
6 VS t 0 0 1 0 0 1 1 0 5 5F 7
4 5
W 50 60 M 75 0 0 M 0 1 5M
F4 ! (M + 75) F3 + F4
2 3
VE C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t W R 7
6 7 SOLUCIÓN PARCIAL
6 7
6 s1 1 2 0 1 0 2 2 0 30 F1 ! F2 + F1 7
6 7 t = 0 ! W = U Mt = U
6 7
6 VS s2 1 1 0 0 1 2 2 0 20 10F F2 ! 12 F2 7
6 7 elimino la columna de t
6 7
6 x3 0 0 1 0 0 1 1 0 5 no F3 ! 12 F2 + F3 7
4 5
W 50 60 0 0 0 75 M + 75 1 375 F4 ! 75 F
2 32 + F 4
2
VE C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 U R 7
6 7
6 7
6 VS s1 0 1 0 1 1 0 0 10 10F 7
6 7 45 5 + 1125
6 1 1 1 1 7
6 s3 0 0 1 0 10 F 2 ! F
2 1 + F 2 7
6 2 2 2 7
6 1 1 1 1 7
6 x3 1 0 0 0 15 F 3 ! F 1 + F 3 7
4 2 2 2 2 5
25 45 75 45
U 2 2 0 0 2 0 1 1125 F 4 ! F
2 1 + F4
2 3
VE C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 U R 7
6 7
6 7
6 x2 0 1 0 1 1 0 0 10 no 7
6 7
6 1 1 7
6 VS s2 2 0 0 1 1 0 5 10F F2 ! 2F2 7
6 2 7
6 1 1 7
6 x3 0 1 1 0 0 10 20 F3 ! F2 + F3 7
4 2 2 5
25 45
U 2 0 0 2 15 0 1 1350 F4 ! 25F2 + F4
38
 2 3
C OP ERACION ES
6 7 SOLU CI ON
6 7
6 x1 x2 x3 s1 s2 s3 U R 7
6 7 x1 = 10
6 7
6 x2 0 1 0 1 1 0 0 10 7
6 7 x2 = 10
6 7
6 x1 1 0 0 1 2 2 0 10 7
6 7 x3 = 5
6 7
6 x3 0 0 1 0 0 1 0 5 7
4 5 U
M AX = 1475
U 0 0 0 10 40 25 1 1475
3)El folleto informativo de un fondo de inversión establece que todo el dinero está invertido en bonos que
están considerados como A, AA y AAA; no más de 30% de la inversión total se encuentra en bonos A y AA,
y al menos el 50% está en bonos AA y AAA. Los bonos A, AA y AAA, respectivamente, obtienen 8, 7 y
6% anual. Determine los porcentajes de la inversión total que serán comprometidos a cada tipo de bono, de
modo que el fondo maximice el rendimiento anual. ¿Cuál es ese rendimiento?
P LAN T EAM IEN T O
x1 = % de la inversión total en bonos A
x2 = % de la inversión total en bonos AA
x3 = % de la inversión total en bonos AAA
Z = Rendimiento de la inversión total
I = inversión total
3
ZI = 0:08x1 I + 0:07x2 I + 0:06x3 I I
M AX : Z = 0:08x1 + 0:07x2 + 0:06x3
S:A: x1 + x2 + x3 = 1
x1 + x2 0:3
x2 + x3 0:5
x1 ; x2 ; x3 0
Re planteamos usando solo dos variables para metodo gra…co
x3 = 1 x1 x2
M AX : Z = 0:08x1 + 0:07x2 + 0:06x3
M AX : Z = 0:08x1 + 0:07x2 + 0:06 (1 x1 x2 )
S:A: x1 + x2 + x3 = 1
S:A: 1 x1 x2 0
x1 + x2 0:3
x1 + x2 0:3
x2 + x3 0:5
x2 + 1 x1 x2 0:5
x1 ; x2 ; x3 0
x1 ; x2 0

39
 M AX : Z = 0:02x1 + 0:01x2 + 0:06
V ertices
S:A: x1 + x2 1
A = (0; 0)
x1 + x2 0:3
B = (0:3; 0)
x1 0:5
C = (0; 0:3)
x1 ; x2 0

Evaluacion
Z = 0:02x1 + 0:01x2 + 0:06
Z (0; 0) = 0:06
Z(B) = Z (0:3; 0) = 0:02 (0:3) + 0:01 0 + 0:06 = 0:066

Z (C) = Z (0; 0:3) = 0:02 0 + 0:01 (0:3) + 0:06 = 0:063

Sol x2 = 0; x1 = 0:3; x3 = 1 x1 x2 = 0:7 Zmax = 0:066:
Se debe invertir 30% en bonos A, 0% en AA y 70% en AAA para obtener un rendimiento maximo de
6.6% de la inversión total.
Tarea: Plantear y resolver si el problema es de 3 variables.
3)La compañía GHI fabrica dos modelos de snowboards, estándar y de lujo, en dos diferentes plantas
de manufactura. La producción máxima en la planta I es de 1200 snowboards,en tanto que la producción
máxima en la planta II es de 1000 al mes. Debido a las obligaciones contractuales,el número de modelos de
lujo producidos en la planta 1 no puede exceder el número de modelos estándar producidos en la misma planta
1 en más de 200. La utilidad por la fabricación de tablas para nieve de los modelos estándar y de lujo en la
planta I es de $40 y $60, respectivamente, mientras que para la planta II es de $45 y $50, respectivamente,
en tanto que para la planta II, es de $45 y $50, respectivamente. Este mes, GHI recibió un pedido por
1000 snowboards del modelo estándar y 800 del modelo de lujo. Determine cuántos de cada modelo deben
producirse en cada planta para satisfacer el pedido y maximizar la utilidad. [Una pista: Sea x1 el número de
modelos estándar producidos y x2 el número de modelos de lujo fabricados en la planta I.]

MINIMIZACIÓN.
Para funciones de una variable y = f (x) se cumple que

40
 min f = max ( f )

Para reslover min : Z s.a AX ; b

primero resolvemos max; Z s.a AX ; b
Si la solución max ( Z) = m
Entonces el min Z = max ( Z) = m:

Ejemplo 1.
minimizar Z = 2x1 + 3x2 + x3 maximizar Z= 2x1 3x2 x3
s.a. x1 + x2 + x3 6; s.a. x1 + x2 + x3 6;
x1 x3 4; por ( 1) x1 + x3 4 v:artif:
x2 + x3 5; x2 + x3 5
x1 ; x2 ; x3 0 x1 ; x2 ; x3 0
maximizar W = Z Mt ! Z + Mt + W = 0
x1 + x2 + x3 + s1 = 6;
Replanteo y SEA x1 + x3 s2 + t = 4
x2 + x3 + s3 = 5
2x1 + 3x2 + x3 + M t + W = 0
2 3
C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t W R 7
6 7
6 7
6 s1 1 1 1 1 0 0 0 0 6 7
6 7
6 7
6 t 1 0 1 0 1 0 1 0 4 7 T SI !
6 7
6 7
6 s3 0 1 1 0 0 1 0 0 5 7
6 7
6 7
6 W 2 3 1 0 0 0 M 1 0 F4 ! M F2 + F4 7
4 5
W M +2 3 M +1 0 M 0 0 1 4M

41
2 3
VE C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t W R 7
6 7
6 7
6 s1 1 1 1 1 0 0 0 0 6 F2 + F1 7
6 7
6 7
6 VS t 1 0 1 0 1 0 1 0 4 F 7
6 7
6 7
6 s3 0 1 1 0 0 1 0 0 5 F2 + F3 7
4 5
W M +2 3 M +1 0 M 0 0 1 4M (M 1) F2 + F4
IN DICADORES
2 3
C OP ERACION ES NO NEGATIVOS
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t W R 7 F IN t = 0; W = Z
6 7
6 7
6 s1 2 1 0 1 1 0 1 0 2 7 x1 = 0
6 7 :
6 7
6 x3 1 0 1 0 1 0 1 0 4 7 x3 = 4
6 7
6 7
6 s3 1 1 0 0 1 1 1 0 1 7 x2 = 0
4 5
W 3 3 0 0 1 0 M 1 1 4 M ax ( Z) = 4
M in (Z) = M ax ( Z) = 4
Ejemplo 2
Minimizar Z = x1 + 8x2 + 5x3 Maximizar Z= x1 8x2 5x3
s:a : x1 + x2 + x3 8 s:a : x1 + x2 + x3 8 var artif t1
x1 + 2x2 + x3 2 x1 + 2x2 + x3 2 var artif t2

Re planteo y SEA Re planteo y SEA

M az = W = Z M t1 M t2 M az = W = Z M t1 M t2
x1 + x2 + x3 s1 + t1 = 8 x1 + x2 + x3 s1 + t1 = 8
x1 + 2x2 + x3 s2 + t2 = 2 x1 + 2x2 + x3 s2 + t2 = 2
Z + M t1 + M t2 + W = 0 x1 + 8x2 + 5x3 + M t1 + M t2 + W = 0
2 3
C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 t1 t2 W R 7
6 7
6 7
6 t1 1 1 1 1 0 1 0 0 8 7
6 7
6 7
6 t2 1 2 1 0 1 0 1 0 2 7 T SI !
6 7
6 7
6 W 1 8 5 0 0 M M 1 0 F3 ! M F1 + F3 7
6 7
6 7
6 W M +1 M +8 M +5 M 0 0 M 1 8M F4 ! M F2 + F4 7
4 5
W 1 3M + 8 2M + 5 M M 0 0 1 10M

2 3
VE C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 t1 t2 W R 7
6 7
6 1 7
6 t1 1 1 1 1 0 1 0 0 8 F1 ! 2 F2 + F1 7
6 7
6 1 7
6 VS t2 1 2 1 0 1 0 1 0 2 1~ F2 ! 2 F2
7
4 5
3M 8
W 1 3M + 8 2M + 5 M M 0 0 1 10M F3 ! 2 F2 + F3
42
 3M 8 3 3M 8 1 3M 8 1
2 2 +1=5 2M 2 2M + 5 : 1 2M 2 +M : 4 2M 3
VE C OP ERACION ES
6 7
6 7
6 x1 x2 x3 s1 s2 t1 t2 W R 7
6 7
6 3 1 1 1 14 7
6 VS t1 2 0 1 1 0 7 3 ~ F1 ! 23 F1 7
6 2 2 2 7
6 1 1 1 1 7
6 x2 1 0 0 0 1 NO F2 ! 31 F1 + F2 7
4 2 2 2 2 5
3 1 1 3M 8 10
W 2M +5 0 2M +1 M 2M +4 0 2 1 7M 8 F3 ! M 3 F1 + F3
2 3
VE C OP
6 7
6 7
6 x1 x2 x3 s1 s2 t1 t2 W R 7 Solución parcial
6 7
6 1 2 1 2 1 14 7
6 x1 1 0 0 7 t1 = t 2 = 0 W = Z
6 3 3 3 3 3 3 7
6 2 1 1 1 1 10 7
6 VS x2 0 1 0 7 Eliminar columnas de t
4 3 3 3 3 3 3 5
2 10 7 10 7 94
W 0 0 3 3 3 M 3 M 3 1 3
2 3
VE C OP
6 7
6 7
6 x1 x2 x3 s1 s2 W R 7
6 7
6 1 2 1 14 1 7
6 x1 1 0 0 14 F1 ! 2 F2 + F1 7
6 3 3 3 3 7
6 2 1 1 10 7
6 VS x2 0 1 3 0 5~ F2 ! 23 F2 7
4 3 3 3 5
2 10 7 94
Z 0 0 3 3 3 1 3 F3 ! F2 + F3
2 3 F IN
VE C OP
6 7 x1 = 3
6 7
6 x1 x2 x3 s1 s2 Z R 7
6 7 x2 = 0
6 1 1 1 7
6 x1 1 0 0 3 7
6 2 2 2 7 x3 = 5
6 3 1 1 7
6 VS x3 0 1 0 5 7
4 2 2 2 5 M ax ( Z) = 28
Z 0 1 0 3 2 1 28
M in (Z) = M ax ( Z) = 28
EJEMPLO
M in : Z = 5x1 + x2 + 3x3
s:a : 3x1 + x2 x3 4
2x1 + 2x3 5
artif t x1 + x2 + x3 2
x1 ; x2 ; x3 0
Replanteo y SEA
M ax : W = Z Mt ! Z + Mt + W = 0
3x1 + x2 x3 + s1 = 4
2x1 + 2x3 + s2 = 5
x1 + x2 + x3 s3 + t = 2
5x1 + x2 + 3x3 + M t + W = 0

43
2 3
C OP
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t W R 7
6 7
6 7
6 s1 3 1 1 1 0 0 0 0 4 7
6 7
6 7
6 s2 2 0 2 0 1 0 0 0 5 7
6 7
6 7
6 t 1 1 1 0 0 1 1 0 2 7
6 7
6 7
6 W 5 1 3 0 0 0 M 1 0 M F 3 + F4 7
4 5
W M +5 M +1 M +3 0 0 M 0 1 2M
2 3
VE C OP
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t W R 7
6 7
6 7
6 s1 3 1 1 1 0 0 0 0 4 F3 + F1 7
6 7
6 7
6 s2 2 0 2 0 1 0 0 0 5 7
6 7
6 7
6 VS t 1 1 1 0 0 1 1 0 2 2F 7
4 5
W M +5 M +1 M +3 0 0 M 0 1 2M (M 1) F3 + F4
2 3
C F IN::
6 7
6 7
6 x1 x2 x3 s1 s2 s3 t W R 7 t = 0 ! W = Z + Mt = Z
6 7
6 7
6 s1 2 0 2 1 0 1 1 0 2 7 x1 = 0; x2 = 2
6 7
6 7
6 s2 2 0 2 0 1 0 0 0 5 7 x3 = 0
6 7
6 7
6 x2 1 1 1 0 0 1 1 0 2 7 max ( Z) = 2
4 5
W 4 0 2 0 0 1 M 1 1 2 min (Z) = max ( Z) = 2

Ejercicio Tarea 1...

M in : Z = 4x1 + 4x2 + 6x3
s:a : x1 x2 x3 3
artif t x1 x2 + x3 3
x1 ; x2 ; x3 0

2 3
C
Replanteo y SEA 66
7
7
6 x1 x2 x3 s1 s2 t W R 7
M ax : W = Z M t ! Z + M t + W = 0 6 6
7
7
6 s1 1 1 1 1 0 0 0 3 7
x1 x2 x3 + s1 = 3 6 6
7
7
6 t 1 1 1 0 1 1 0 3 7
x1 x2 + x3 s2 + t = 3 6 6
7
7
6 W 4 4 6 0 0 M 1 0 M F 2 + F3 7
4x1 + 4x2 + 6x3 + M t + W = 0 4 5
W M +4 M +4 M +6 0 M 0 1 3M

44
 2 3
VE C
6 7
6 7
6 x1 x2 x3 s1 s2 t W R 7
6 7
6 7
6 s1 1 1 1 1 0 0 0 3 F2 + F1 7
6 7
6 7
6 VS t 1 1 1 0 1 1 0 3 F 7
4 5
W M +4 M +4 M +6 0 M 0 1 3M (M 4) F2 + F4
2 3 F IN : SOLU CI ON
C
6 7 t = 0; W = Z Mt = Z
6 7
6 x1 x2 x3 s1 s2 t W R 7
6 7 x1 = 3
6 7
6 s1 1 1 1 1 0 0 0 3 7
6 7 x2 = 0
6 7
6 x1 1 1 1 0 1 1 0 3 7
4 5 x3 = 0
W 0 8 2 0 4 M 4 1 12
M in (Z) = max ( Z) = ( 12) = 12
Problemas de aplicación
Planteamiento de problemas.
Ejemplo 1. (Problemas de transporte) Tarea plantear y resolver 5 de mayo.
Un vendedor al detalle tiene tiendas en Columbus y Dayton, y bodegas en Akron y Spring…eld. Cada
tienda requiere de la entrega de exactamente 150 reproductores de DVD. En la bodega de Akron hay 200
reproductores de DVD y en la de Spring…eld hay 150. Los costos de transporte para enviar reproductores
de DVD desde los almacenes a las tiendas están dados en la tabla siguiente:
Columbus Dayton
Akron $5 #pr:x1 $7 #pr:x2
Spring…eld $3 #pr:x3 $2 #pr:x4
Por ejemplo, el costo para enviar un reproductor desde Akron a la tienda de Columbus es de $5. ¿Cómo
es que el detallista debe pedir los reproductores de modo que los requerimientos de las tiendas se satisfagan,
y los costos totales de transporte se minimicen? ¿Cuál es el costo mínimo de transporte?
x1 = # de Dvd a transportar de la bodega en Akron a la tienda en Columbus.
x2 = # de Dvd a transportar de la bodega en Akron a la tienda en Dayton
x3 = # de Dvd a transportar de la bodega en Spring…eld a la tienda en Columbus.
x4 = # de Dvd a transportar de la bodega en Spring…eld a la tienda en Dayton
Minimizar : C=costo total del transporte: 5x1 + 7x2 + 3x3 + 2x4 Restricciones:
Debe llegar a Columbus: x1 + x3 = 150 ! x3 = 150 x1 0
Debe llegar a Dayton: x2 + x4 = 150 ! x4 = 150 x2 0
Sale de Akron x1 + x2 200
Sale de Spring…eld x3 + x4 150 ! 150 x1 + 150 x2 150
x1 ; x2 ; x3 ; x4 0
M in : C = 5x1 + 7x2 + 3 (150 x1 ) + 2 (150 x2 )
Usando las restricciones de igualdad para rebajar el número de variables obtenemos el Problema:

45
 M in : C = 2x1 + 5x2 + 750
V ERT
x1 150
A = (0; 150)
x2 150
B = (50; 150)
x1 + x2 200
C = (150; 50)
x1 + x2 150
D = (150; 0)
x1 ; x2 0

EVALUACIÓN EN VERTICES
c = 2x1 + 5x2 + 750
c (A) = 5 150 + 750 = 1500
c (B) = 2 50 + 5 150 + 750 = 1600
c (C) = 2 150 + 5 50 + 750 = 1300
c (D) = 2 150 + 750 = 1050
SOLUCIÓN: x1 = 150; x2 = 0; x3 = 150 x1 = 0; x4 = 150 x2 = 150 cmin imo = 1050:
En el contexto
Se deben transportar 150 productos de la primera bodega a la primera tienda
y 150 productos de la segunda bodega a la segunda tienda. para un costo mínimo de transporte de 1050.
Mas problemas
Minas Universal opera tres minas en West Virginia. El mineral de cada una se separa, antes de embarcarse,
en dos grados. La capacidad diaria de producción de las mismas así, como sus costos diarios de operación
son los siguientes:
Mineral de grado Mineral de grado costo de
alto ton/dia bajo ton/dia operación miles $/dia
Mina I 4 4 20
Mina II 6 4 22
Mina III 1 6 16
La Universal se comprometió a entregar 54 toneladas de mineral de grado alto y 65 toneladas de mineral
de grado bajo para …nes de la siguiente semana. Determínese el número de días que cada mina debería operar
durante la siguiente semana, si Minas Universal ha de cumplir su compromiso a un costo total mínimo.
x1 = # de días a operar MI. x2 = # de días a operar M II. : x3 = # de días a operar M III.
MIN c = 20x1 + 22x2 + 16x3 s:a: 4x1 + 6x2 + x3 54; 4x1 + 4x2 + 6x3 65

46
 20x1 + 22x2 + 16x3
4x1 + 6x2 + x3 54
4x1 + 4x2 + 6x3 65
x1 7
7
x2 7 , Minimum is at: x3 = 5; x2 = 7; x1 = 4

x3 7
0 x1
0 x2
0 x3
Plantear yresolver PROBLEMA 4)
Un vendedor de autos tiene tiendas en C y D, y bodegas en A y B. Las tiendas C y D requieren de la
entrega de al menos 100 y 150 autos respectivamente. En la bodegas A y B hay respectivamente 100 y 200
autos. Los costos (en miles de dolares) de transporte para enviar los autos desde las bodegas a las tiendas
están dados en la tabla siguiente:
C D
Cuantos autos deben transportarse de las bodegas a las tiendas
A 8 4
para que los costos totales de transporte se minimicen.
B 5 6
x1 = # de autos a transportar de la bodega A a la tienda C
x2 = # de autos a transportar de la bodega A a la tienda D
x3 = # de autos a transportar de la bodega B a la tienda C
x4 = # de autos a transportar de la bodega B a la tienda D
Min c = 8x1 + 4x2 + 5x3 + 6x4 sujeto a: Replantear M ax : W = c M t1 M t2 ! c + M t1 + M t2 + W = 0 : SEA
tienda C x1 + x3 100 var art t1 x1 + x3 s1 + t1 = 100
tienda D x2 + x4 150 var art t2 x2 + x4 s2 + t2 = 150
bodega A x1 + x2 100 x1 + x2 + s3 = 100
bodega B x3 + x4 200 x3 + x4 + s4 = 200
x1 ; x2 ; x3 ; x4 0 8x1 + 4x2 + 5x3 + 6x4 + M t1 + M t2 + W = 0
2 3
C OP
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 t1 t2 W R 7
6 7
6 7
6 t1 1 0 1 0 1 0 0 0 1 0 0 100 7
6 7
6 7
6 t2 0 1 0 1 0 1 0 0 0 1 0 150 7
6 7
6 7
6 s3 1 1 0 0 0 0 1 0 0 0 0 100 7 T SI :
6 7
6 7
6 s4 0 0 1 1 0 0 0 1 0 0 0 200 7
6 7
6 7
6 W 8 4 5 6 0 0 0 0 M M 1 0 7
6 7
6 7
6 W M +8 4 M +5 6 M 0 0 0 0 M 1 100M M F1 + F5 7
4 5
W M +8 M4 M +5 M +6 M M 0 0 0 0 1 250M M F2 + F6

47
 2 3
VE C OP
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 t1 t2 W R 7
6 7
6 7
6 t1 1 0 1 0 1 0 0 0 1 0 0 100 7
6 7
6 7
6 t2 0 1 0 1 0 1 0 0 0 1 0 150 F3 + F2 7
6 7
6 7
6 VS s3 1 1 0 0 0 0 1 0 0 0 0 100 F 7
6 7
6 7
6 s4 0 0 1 1 0 0 0 1 0 0 0 200 7
4 5
W M +8 M +4 M +5 M +6 M M 0 0 0 0 1 250M (M 4) F3 + F5
2 3
VE C OP
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 t1 t2 W R 7
6 7
6 7
6 VS t1 1 0 1 0 1 0 0 0 1 0 0 100 F 7
6 7
6 7
6 t2 1 0 0 1 0 1 1 0 0 1 0 50 7
6 7
6 7
6 x2 1 1 0 0 0 0 1 0 0 0 0 100 7
6 7
6 7
6 s4 0 0 1 1 0 0 0 1 0 0 0 200 F1 + F4 7
4 5
W 4 0 M +5 M +6 M M M 4 0 0 0 1 150M 400 (M 5) F1 + F5
2 3
VE C OP
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 t1 t2 W R 7
6 7
6 7
6 x3 1 0 1 0 1 0 0 0 1 0 0 100 7
6 7
6 7
6 VS t2 1 0 0 1 0 1 1 0 0 1 0 50 F 7
6 7
6 7
6 x2 1 1 0 0 0 0 1 0 0 0 0 100 7
6 7
6 7
6 s4 1 0 0 1 1 0 0 1 1 0 0 100 F2 + F4 7
4 5
W M 1 0 0 M +6 5 M M 4 0 M 5 0 1 50M 900 (M 6) F2 + F5
2 3
C OP F IN:t1 = t2 = 0; W = c
6 7
6 7
6 x1 x2 x3 x4 s1 s2 s3 s4 t1 t2 W R 7 x1 = 0
6 7
6 7
6 x3 1 0 1 0 1 0 0 0 1 0 0 100 7 x3 = 100
6 7
6 7
6 x4 1 0 0 1 0 1 1 0 0 1 0 50 7 x4 = 50
6 7
6 7
6 x2 1 1 0 0 0 0 1 0 0 0 0 100 7 x2 = 100
6 7
6 7
6 s4 1 0 0 1 1 0 0 1 1 0 0 100 7 M ax ( c) = 1200
4 5
W 5 0 0 0 5 6 2 0 M 5 M 6 1 1200 M inc = M ax ( c) = 1200
PROBLEMA 5)
Un vendedor de motores tiene tiendas en B,C y D, y una bodega en A . Las tiendas B,C y D requieren de
la entrega de al menos 100,120 y 150 motores respectivamente. En la bodegas A hay 500 autos. Los costos
(en miles de pesos) de transporte para enviar los motores desde las bodegas a las tiendas están dados en la
tabla siguiente:
B C D
A 4 5 6
Cuantos motores deben transportarse de la bodega a las tiendas para que los costos totales de transporte

48
se minimicen.
4x1 + 5x2 + 6x3
x1 100
x2 120 , Minimum is at: fx1 = 100; x2 = 120; x3 = 150g
x3 150
x1 + x2 + x3 400

DUALIDAD.
Suponga que una compañía fabrica dos tipos de podadoras, manuales y eléctricas, y cada una requiere
del uso de las máquinas A y B para su producción. En la tabla
Máq A Máq B Util/unid se indica que una podadora manual requiere del uso de A durante
Manual 1h 1h $10 1 hora y de B durante otra hora. Las eléctricas requieren de A durante 2
Electrico 2h 4h $24 horas y de B durante 4 horas. Los números máximos de horas disponibles
Horas disp. 120h 180h por mes para las máquinas A y B, son 120 y 180, respectivamente.
La utilidad por una podadora manual es de $10 y por una eléctrica es de $24. Suponga que la compañía
puede vender todos los artículos que produce, determine la utilidad mensual máxima. Si x1 y x2 son los
números de podadoras manuales y eléctricas que se producen por mes, respectivamente, entonces se desea
maximizar la función de utilidad mensual
maximizar : P = 10x1 + 24x2
Se escriben las restricciones (1) y (2) como ecuaciones, se tiene
sujeto a : x1 + 2x2 120 (1)
x1 + 2x2 + s1 = 120 (3)
x1 + 4x2 180 (2)
x1 + 4x2 + s2 = 180 (4)
x1 ; x2 0
donde s1 y s2 son variables de holgura. En la ecuación (3), x1 + 2x2 es el número de horas que se utiliza
la máquina A. Como hay disponibles 120 horas para A, entonces s1 es el número de horas que no se utilizan
para la producción. Es decir, s1 representa para A la capacidad no usada (horas). Del mismo modo, s2
representa la capacidad no utilizada para B. Al resolver este problema por el método simplex, se encuentra
que2la tabla …nal es 3
x1 x2 s1 s2 P R
6 7
6 7
6 x1 1 0 2 1 0 60 7
6 7
6 1 1 7
6 x2 0 1 0 30 7
4 2 2 5
P 0 0 8 2 1 1320
Ahora se verá la situación desde un punto de vista diferente. Suponga que la compañía desea rentar sus
máquinas A y B. ¿Cuál es la renta mensual mínima que debe cobrar?
Así, la utilidad máxima mensual es de $1320, que ocurre cuando x1 = 60 y x2 = 30. Ciertamente, si el
cobro es muy alto, nadie le rentaría las máquinas. Por otra parte,si el cobro es muy bajo, no le convendría
rentarlas en absoluto. Es obvio que la renta mínima debe ser de $1320. Es decir, el mínimo que la compañía
debe cobrar es la utilidad que podría tener si ella misma utilizara las máquinas. Podemos llegar a este costo
de renta mínimo de manera directa, al resolver un problema de programación lineal.
49
 Sea F el costo de la renta mensual. Para determinar F , se supone que la compañía asigna valores monetar-
ios a cada hora de capacidad en las máquinas A y B. Sean estos valores y1 y y2 dólares, respectivamente, donde
Máq A Máq B Util/und 120y1 y para la B es 180y2 . Por lo
Manual 1h 1h 10$ producir una podadora manual es 1
y1 ; y 2 0. Entonces el valor mensual de la máquina A es
Electrico 2h 4h $24 compañía puede recibir por produc
Hs disp 120h 180h destina el tiempo de la máquina a
Del mismo modo, el valor total del tiempo de máquina para producir una podadora eléctrica debe ser al
menos de $24: 2y1 + 4y2 24: Por lo tanto, la compañía necesita
minimizar F = 120y1 + 180y2
Para minimizar F , se maximiza F . Como las restricciones (5) y (6) tienen la forma
sujeta a:y1 + 1y2 10 (5)
a1 + y1 + a2 y2 b, donde b 0, se considerará un problema arti…cial. Si r1 y r2 son variables de
2y1 + 4y2 24 (6)
excedencia, y t1 y t2 son variables arti…ciales, entonces se quiere maximizar
y1 ; y 2 0
W = F M t1 M t2 :
y las y, r y t son no negativas. La tabla simplex …nal para este problema (donde se han eliminado las
y1 + y2 r1 + t1 = 10
columnas de las variables arti…ciales y W ha sido cambiada a F ) es
2y1 + 4y2 r2 + t2 = 24
Como el valor máximo de F es 1320, el valor mínimo de F es ( 1320) $13
anticipó). Esto ocurre cuando y1 = 8 y y2 = 2. Por lo tanto, se ha determinado
de un problema de programación lineal (maximización de utilidad), al encontrar
óptimo de otro problema de programación lineal (minimización del costo de la r
Los valores y1 = 8 y y2 = 2 podrían haberse anticipado a partir de la tabla …nal
de maximización. En (4), el indicador 8 en la columna s1 signi…ca que en el nive
2 3
x1 x2 s1 s2 P R
6 7
6 7
6 x1 1 0 2 1 0 60 7
6 7(4)
6 1 1 7
6 x2 0 1 0 30 7
4 2 2 5
P 0 0 8 2 1 1320
producción, si s1 aumenta una unidad, entonces la utilidad P disminuye en 8. Esto es, 1 hora de
capacidad sin uso de A disminuye la utilidad máxima en $8. Entonces, una hora de capacidad de A tiene un
valor monetario de $8. Se dice que el precio sombra de 1 hora de capacidad de A es de $8. Ahora, recuerde
que y1 en el problema de la renta es el valor de 1 hora de capacidad de A. Así, y1 debe ser igual a 8 en la
solución óptima para ese problema. De manera similar, como el indicador en la columna s2 es 2, el precio
sombra de 1 hora de capacidad de B es de $2, que es el valor de y2 en la solución óptima del problema de la
renta.
Ahora se analizará la estructura de los dos problemas de programación lineal:

50
 Observe que en (7) las desigualdades son todas , pero en (8) son todas . Los coe…cientes de la función
objetivo del problema de minimización son los términos constantes en (7). Los términos constantes en (8)
son los coe…cientes de la función objetivo del problema de maximización. Los coe…cientes de y1 en (8) son
los coe…cientes de x1 y x2 en la primera restricción de (7); los coe…cientes de y2 en (8) son los de x1 y x2 en
la segunda restricción de (7). El problema de minimización es llamado el dual del problema de maximización
y viceversa.
En general, es posible asociar cualquier problema de programación lineal con otro problema de pro-
gramación lineal llamado su dual. El problema dado se llama primal. Si el primal es un problema de
maximización, entonces su dual es de minimización. De manera similar, si el problema primal implica mini-
mización, su dual implica maximización.

PROBLEMAS DE MINIMIZACIÓN Y EL DUAL

El dual de un problema de programación lineal
PPL DU AL P P L
Problema de prog. lineal Estandar

,
DU AL

M in : W = b Y M ax : Z = C X
s:a : AY C s:a : AT X b
Y 0 X 0
# de restricciones en el primer ppl=# de incognitas en el segundo (dual)
Resultado: MinW=MaxZ.
Ejemplos :
Hallar el dual del problema de programación lineal dado.
51
1)
M inimizar : W = 2y1 + 4y2 M inimizar : W = 2y1 + 4y2
M aximizar : Z = 3x1 + 2x2 + 4x3
sujeto a: 1y1 2y2 3 sujeto a: y1 2y2 3
sujeto a: x1 + x2 x3 2 !
Dual 1y1 + 1y2 2 y1 + y2 2
2x1 + x2 + 5x3 4
1y1 + 5y2 4 y1 + 5y2 4
x1 ; x2 ; x3 0
y1 ; y 2 0 y1 ; y 2 0
M axZ = minW
M aximizar : K = 11y1 + 14y2
M inimizar : H = 4x1 + 2x2 + 7x3 M inimizar : H = 4x1 + 2x2 + 7x3
sujeto a: 4y1 8y2 4
sujeto a: 4x1 3x2 + 5x3 11 por ( 1) 4x1 + 3x2 5x3 11 !
2) Dual 3y1 + 6y2 2
8x1 + 6x2 + 11x3 14 8x1 + 6x2 + 11x3 14
5y1 + 11y2 7
x1 ; x2 ; x3 0 x1 ; x2 ; x3 0
y1 ; y 2 0
M inH = M axK
3) Tarea Hallar el dual
M inimizar : H = 6a + 2b 5c + d 4e + 11f
sujeto a: 2a 3b + 4d 3
multiplicar por ( 1) 5a + 3b 8e + 6f 15
multiplicar por ( 1) 4d + 2a 8f 2
multiplicar por ( 1) 3e b+f 3
a; b; c; d; e; f 0
M aximizar : L = 3p + 15q + 12r 3s
M inimizar : H = 6a + 2b 5c + d 4e + 11f sujeto a: 2p + 5q 2r 6
sujeto a: 2a 3b + 4d 3 3p 3q + s 2
5a 3b + 8e 6f 15 ! 4s 5
DU AL
2a + 4d + 8f 2 4p + 4r 1
4c + 3e + b f 3 8q + 3s 4
a; b; c; d; e; f 0 6q + 8r s 11
p; q; r; s 0
M inH = M axL
Ejemplo dualizar
M inimizar : F = 2x1 + 10x2 15x3 + 2x4
sujeto a: 4x1 + 2x2 5x3 + x4 3
mult ( 1) 5x1 + 7x2 2x3 + 5x4 7
4x1 5x3 2
mult ( 1) 4x2 5x3 + 9x4 8
mult ( 1) 9x1 5x3 + 7x4 6
x1 ; x2 ; x3 ; x4 0
Cuantas variables tiene el dual?? tantas como restricciones = 5
52
 M inimizar : F = 2x1 + 10x2 15x3 + 2x4
M aximizar : G = 3y1 + 7y2 + 2y3 + 8y4 + 6y5
sujeto a: 4x1 + 2x2 5x3 + x4 3
sujeto a: 4y1 + 5y2 + 4y3 + 0y4 9y5 2
5x1 7x2 + 2x3 5x4 7
! 2y1 7y2 + 0y3 4y4 + 0y5 10
4x1 5x3 2 DU AL
5y1 + 2y2 5y3 + 5y4 + 5y5 15
4x2 + 5x3 9x4 8
y1 5y2 + 0y3 9y4 7y5 2
9x1 + 5x3 7x4 6
y1 ; y 2 ; y 3 ; y 4 ; y 5 0
x1 ; x2 ; x3 ; x4 0
M inimizar : Z = x1 + 8x2 + 5x3
sujeto a: x1 + x2 + x3 8
2)Resolver con el dual y simplex
x1 + 2x2 + x3 2
x1 ; x2 ; x3 0
Variables en el dual=#de restriciiones 2. 2
M aximizar VE COC OP ERACION ES
6
6
W = 8y1 + 2y2 s.a: y1 y2 + s1 = 1 6 y1 y2 s1 s2 s3 W R
6
6
! 1y1 1y2 1 y1 + 2y2 + s2 = 8 6 V S s1 1 1 1 0 0 0 1 1F
DU AL SEA 6
6
1y1 + 2y2 8 y1 + 1y2 + s3 = 5 6 s2 1 2 0 1 0 0 8 8 F2 ! F1 + F2
6
6
1y1 + 1y2 5 8y1 2y2 + W = 0 6 s3 1 1 0 0 1 0 5 5 F3 ! F1 + F3
4
y1 ; y 2 0 W 8 2 0 0 0 1 0 F4 ! 8F1 + F4
2 3
VE COC OP ERACION ES
6 7
6 7
6 y1 y2 s1 s2 s3 W R 7
6 7
6 7
6 y1 1 1 1 0 0 0 1 F1 ! 21 F3 + F1 7
6 7
6 7 3 7
6 s2 0 3 1 1 0 0 7 F2 ! 2 F3 + F2 7
6 3 7
6 7
6 VS s3 0 2 1 0 1 0 4 2F F3 ! 12 F3 7
4 5
W 0 10 8 0 0 1 8 F4 ! 5F3 + F4
2 3
COC
6 7 Solución del primal
6 7
6 y1 y2 s1 s2 s3 W R 7
6 7 Zmin = Wmax = 28
6 1 1 7
6 y1 1 0 0 0 3 7
6 2 2 7 x = indicador de s = 3
6 1 3 7 1 1
6 s2 0 0 1 0 1 7
6 2 2 7 x = indicador de s = 0
6 1 1 7 2 2
6 y2 0 1 0 0 2 7
4 2 2 5 x3 = indicador de s3 = 5
W 0 0 3 0 5 1 28
Dualizar y resolver el dual con simplex:
M inimizar
Z = 2x1 + 2x2 + 5x3 s.a:
1) x1 x2 + 2x3 2
x1 + 2x2 + x3 3
x1 ; x2 ; x3 0
53
 2
M aximizar VE COC OP ERACIO
6
6
W = 2y1 + 3y2 s.a: y1 y2 + s1 = 2 6 y1 y2 s1 s2 s2 W R
6
6
! y1 y2 2 y1 + 2y2 + s2 = 2 !6 s1 1 1 1 0 0 0 2 no F1 ! 12 F2 +
Dual SEA Simplex 6
6
y1 + 2y2 2 2y1 + y2 + s3 = 5 6 VS s2 1 2 0 1 0 0 2 1F F2 ! 12 F
6
6 1
2y1 + y2 5 2y1 3y2 + W = 0 6 s3 2 1 0 0 1 0 5 5 F3 ! 2 F2
4
y1 ; y 2 0 W 2 3 0 0 0 1 0 F4 ! 32 F2 +
2 3
VE COC OP ERACION ES
6 7
6 7
6 y1 y2 s1 s2 s2 W R 7
6 7
6 1 1 1 7
6 s1 0 1 0 0 3 6 F1 ! 5 F3 + F1 7
6 2 2 7
6 1 1 7
6 y2 1 0 0 0 1 no F2 ! 51 F3 + F2 7
6 2 2 7
6 5 1 8 7
6 VS s3 2 0 0 1 0 4 F3 ! 25 F3 7
4 2 5 5
7 3
W 2 0 0 2 0 1 3 F4 ! 57 F3 + F4
2 3
COC OP F in
6 7
6 7
6 y1 y2 s1 s2 s3 W R 7 Solucion del original
6 7
6 3 1 11 7
6 s1 0 0 1 0 7 M inZ = M axW = 43
6 5 5 5 7 5
6 2 1 9 7
6 y2 0 1 0 0 7 x1 = indicador de s1 = 0
6 5 5 5 7
6 1 2 8 7
6 y1 1 0 0 0 7 x2 = indicador de s2 = 54
4 5 5 5 5
4 7 43
W 0 0 0 5 5 1 5 x3 = indicador de s3 = 57
M aximizar
M inimizar Arreglar:M inimizar
W = 2y1 + 4y2 s.a:
Z = 2x1 + x2 + x3 s.a: Z = 2x1 + x2 + x3 s.a:
! 2y1 y2 2
4) 2x1 x2 x3 2 por ( 1) 2x1 + x2 + x3 2 Dual
y1 y2 1
x1 x2 + 2x3 4 x1 x2 + 2x3 4
y1 + 2y2 1
x1 ; x2 ; x3 0 x1 ; x2 ; x3 0
y1 ; y 2 0
2 3
VE COC OP ERACION ES
6 7
6 7
6 y1 y2 s1 s2 s2 W R 7
6 7
6 7
!6 s1 2 1 1 0 0 0 2 F1 ! 21 F3 + F1 7
Simplex 6
6
7
7
6 s2 1 1 0 1 0 0 1 F2 ! 12 F3 + F2 7
6 7
6 7
6 VS s3 1 2 0 0 1 0 1 r F3 ! 12 F3 7
4 5
W 2 4 0 0 0 1 0 F4 ! 2F3 + F4
2 3
COC OP
6 7
6 7
6 y1 y2 s1 s2 s3 W R 7
6 7
6 3 1 5 7
6 s1 0 1 0 0 7
6 2 2 2 7
6 3 1 3 7
6 s2 0 0 1 0 7
6 2 2 2 7
6 1 1 1 7
6 y2 1 0 0 0 r 7
4 2 2 2 5
W 4 0 0 0 2 1 2
54
 F in
M inZ = M axW = 2
x1 = s1 = 0
x2 = s2 = 0
x3 = s3 = 2
Problemas
4) Plantear y resolver:
P lantear y hallar el dual

V ariables : x1 = # de dispositivos tipo 1 a fabricar

x2 = # de dispositivos tipo 2 a fabricar,
x3 = # de dispositivos tipo 3 a fabricar, U=utilidad total
M ax : U = 30x1 + 20x2 + 20x3 :::
30x1 + 15x2 + 10x3 300
20x1 + 30x2 + 20x3 400
40x1 + 30x2 + 25x3 600
Dual en casa de tarea
M in : W = x1 + x2 + x3
x1 + x2 + x3
x1 + x2 + x3
x1 + x2 + x3
5)Tres productos diferentes (A, B y C) que maneja una compañía tienen una demanda mínima de 1000,
55
500 y 250 unidades respectivamente. Por otra parte, se conoce que los costos de producción correspondiente
a cada producto son de $100, $125 y $124, además que debido a regulaciones externas, la producción del
producto A debe ser al menos el doble de la producción conjunta de B y C. Establezca las condiciones para
minimizar los costos, satisfaciendo las demandas dadas y halle el costo mínimo.
Planteamiento
V ariables : x1 = # de unidades del producto A a fabricar
x2 = # de unidades del producto B a fabricar,
x3 = # de unidades del producto C a fabricar
Min:C=costo total C = 100x1 + 125x2 + 124x3
AQUII

56