METODO SIMPLEX
F.O:
𝑀𝑎𝑥𝑍 = 𝑐𝑋𝑖
s.a;
𝐴𝑥𝑖 <= 𝑏
𝑥𝑖 >= 0 ; 𝑖 = 1, 2, 3,.... 𝑛
F.O.(Funcion objetiva)
𝑀𝑎𝑥𝑍 = 𝑥1 + 𝑥2
Reglas para la funcion objetiva
-La funcion objetiva es unica
Max Z=Min-Z o Min Z=Max-Z
𝑀𝑖𝑛 − 𝑍 = − 𝑥1 − 𝑥2
-Las restricciones pueden ser enésimas
-Las variables también son enésimas tanto en la F.O como en las restricciones
-Para hacer por el método simplex, las restricciones siempre deben ser menor igual (<=)
s.a (sujeto a:)
𝑥1 + 2𝑥2 <= 80 R1
3𝑥1 + 2𝑥2 <= 120 R2
𝑥1, 𝑥2 >= 0 CNN
F.O.
𝑀𝑎𝑥𝑍 = 5𝑥1 + 10𝑥2
s.a:
𝑥1 + 2𝑥2 <= 80 R1
3𝑥1 + 2𝑥2 <= 120 R2
𝑥1, 𝑥2 >= 0 CNN (condición de no negatividad)
Por el método simplex, estandarizando tenemos:
𝑆𝑖 = 𝑉𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝑑𝑒 ℎ𝑜𝑙𝑔𝑢𝑟𝑎
F.O.
𝑀𝑎𝑥𝑍 = 𝑥1 + 𝑥2 + 0𝑆1 + 0𝑆2
𝑀𝑎𝑥1 * 𝑍− 𝑥1 − 𝑥2 − 0𝑆1 − 0𝑆2 = 0
s.a:
𝑥1 + 2𝑥2 + 𝑠1 = 80 R1
3𝑥1 + 2𝑥2 + 𝑠2 = 120 R2
𝑥1, 𝑥2, 𝑠1, 𝑠2 >= 0 CNN
-Para iniciar y continuar el ejercicio debemos buscar el más negativo de la fila Z
-Tenemos que buscar un pivote en la columna elegida
-Min(columna solución/[la columna donde se encuentra el valor más negativo (>0)])
Min(80/1, 120/3)=Min(80,40)=40
z x1 x2 s1 s2 sol.
z 1 -1 -1 0 0 0
s1 0 1 2 1 0 80
s2 0 3 2 0 1 120
F2=(⅓)F2
Para columna x2:
-1 - (-1/3)*2=-⅓
2 - (1/3)*2=4/3
Para columna s2:
0 - (-1/3)*1=⅓
Para columna solución:
80 - (1/3)*120=40
Para s1:
0-(-1/3)*0=0
1-(1/3)*0=1
z x1 x2 s1 s2 sol.
z 1 0 -1/3 0 1/3 40
s1 0 0 4/3 1 -1/3 40
x1 0 1 2/3 0 1/3 40
Min(40/(4/3), 40/(2/3))=Min(30, 60)=30
F1=3/4F1
z x1 x2 s1 s2 sol.
z 1 0 0 1/4 1/4 50
x2 0 0 1 3/4 -1/4 30
x1 0 1 0 -1/2 1/2 20
s1=0
s2=0
X1=20
x2=30
MaxZ=20+30=50
𝑥1 + 2𝑥2 + 𝑠1 = 80 R1
3𝑥1 + 2𝑥2 + 𝑠2 = 120 R2
La solución óptima es z=50, x1=20, x2=30
En las restricciones:
Simplex: Las restricciones siempre deben ser (<=)
Para penalizacion y Dualidad: No importa que restricción sea, puede ser (<=, >=, =)
(<=) : Se adiciona una variable de holgura 𝑆𝑖
(>=) : Se resta una variable holgura 𝑆𝑖 y se adiciona una variable artificial 𝑅𝑖
( = ) : Se adiciona una variable artificial 𝑅𝑖
DOS FASES Y PENALIZACIÓN
EJ2)EXAMEN PRIMER PARCIAL 1-2022
1.- Por navidad, un comerciante ha decidido realizar dos tipos de lotes navideños, para ello
dispones de 200 jamones y 300 botellas de vino. Los lotes de tipo A constan de dos jamones y
dos botellas de vino, y el lote tipo B consta de un jamón y 3 botellas de vino. Si el beneficio por
cada lote del tipo A es de 30Bs y por cada lote de tipo B es de 15 Bs . ¿Cuántos lotes de cada
tipo debe preparar para conseguir un beneficio máximo? Resuelva en forma gráfica y
compruebe por algún método conocido(simplex).
<=200
<=300
lote A → x1 lote B → x2 total
jamón 2 1 200
vino 2 3 300
costos 30 15
ProblemaProgramacionLineal(PPL)
1) Objetivo
Conseguir un beneficio máximo
2) Actividades
x1: Lotes de tipo A por unidad
x2: Lotes de tipo B por unidad
3) Función objetiva
MaxZ=30x1+15x2
4) restricciones
2x1+ x2 <=200 R1
2x1+3x2 <=300 R2
5) condición de no negatividad
x1, x2 >=0 CNN
Resolviendo por el método gráfico:
Para R1 Para R2
2x1 + x2 = 200 2x1 + 3x2 = 300
0 200 0 100
150 0
100 0
x2=y=f(x)=200-2x1 x2=y=f(x)=(300-2x1)/3
Para F.O.
30x1+15x2=0 →x1=0 y x2=0
→x1=100 y x2=-200
Para graficar decimos que x1=x, x2=y
2x1 + x2 = 200 (1)
2x1 + 3x2 = 300 (2)
de 1): x2=200-2x1 (3)
3) en 2): 2x1+3(200-2x1)=300
2x1+600-6x1=300
-4x1=-300
x1=75 en (3) x2=200-2(75)
x2=50
x1=75, x2=50
Maxz=30(75)+15(50)=3000 solucion optimo
MaxZ=30(100)+0=3000 solucion optimo
Maxz=0+15(100)=1500 solucion factible
MÉTODO DE (DOS FASES)
Para Dualidad: No importa que restricción sea, puede ser (<=, >=, =)
(<=) : Se adiciona una variable de holgura 𝑆𝑖
(>=) : Se resta una variable superflua 𝑆𝑖 y se adiciona una variable artificial 𝑅𝑖
( = ) : Se adiciona una variable artificial 𝑅𝑖
M
Ej3) Resolver por el método de Dos Fases
f.o:
Max Z=3x1+4x2
s.a
x1 + 6x2 >=5
2x1 + 5x2 >=2
x1, x2 >=0
Estandarizando tenemos:
Para maximizacion, las var artificiales restan en la funcion objetiva
Para minimizacion, las var artificiales suman en la funcion objetiva
Todas las demas var tienen coeficiente cero.
MaxZ=-R1-R2
MinZ=R1+R2 →Max-Z =-R1-R2
f.o.
MaxZ=-R1-R2
MaxZ+R1+R2=0
s.a
x1+6x2 -x3+0x4 x5+0x6 = 5
2x1+5x2+0x3- x4+ 0x5+x6 = 2
x1, x2, x3, x4, x5, x6 >= 0 cnn
primera fase
z x1 x2 s1 s2 r1 r2 sol.
z 1 0 0 0 0 1 1 0
0 1 6 -1 0 1 0 5
0 2 5 0 -1 0 1 2
Z=Z-f1-f2
z x1 x2 s1 s2 r1 r2 sol.
z 1 -3 -11 1 1 0 0 -7
r1 0 1 6 -1 0 1 0 5
r2 0 2 5 0 -1 0 1 2
Min(5/5, ⅖ )=⅖
f2=⅕ f2
z x1 x2 s1 s2 r1 r2 sol.
z 1 7/5 0 1 -6/5 0 11/5 -13/5
r1 0 -7/5 0 -1 6/5 1 -6/5 13/5
x2 0 2/5 1 0 -1/5 0 1/5 2/5
Min[(13/5)/(6/5)]=13/6
f1=⅚ f1
z x1 x2 s1 s2 r1 r2 sol.
z 1 0 0 0 0 1 1 0
s2 0 -7/6 0 -5/6 1 5/6 -1 13/6
x2 0 1/6 1 -1/6 0 1/6 0 5/6
Segunda fase
Max Z=3x1+4x2
Max Z-3x1-4x2=0
z x1 x2 s1 s2 sol.
z 1 -3 -4 0 0 0
s2 0 -7/6 0 -5/6 1 13/6
x2 0 1/6 1 -1/6 0 5/6
Z=Z+4f2
z x1 x2 s1 s2 sol.
z 1 -7/3 0 -2/3 0 10/3
s2 0 -7/6 0 -5/6 1 13/6
x2 0 1/6 1 -1/6 0 5/6
f2=6f2
z x1 x2 s1 s2 sol.
z 1 0 14 -3 0 15
s2 0 0 7 -2 1 8
x1 0 1 6 -1 0 5
MaxZ=3 (5)+ 4 (0)=15
Tiene solución no acotada.
x1=5,x2=0,s1=0,s2=8
s.a
5=5
2(5)+0-8 = 2
MÉTODO DE PENALIZACIÓN
Para Penalización: No importa que restricción sea, puede ser (<=, >=, =)
Para las restricciones:
(<=) : Se adiciona una variable de holgura 𝑆𝑖
(>=) : Se resta una variable superflua 𝑆𝑖 y se adiciona una variable artificial 𝑅𝑖
( = ) : Se adiciona una variable artificial 𝑅𝑖
Para la función objetiva:
Para maximizacion, las var artificiales restan en la función objetiva (-MR)
Para minimización, las var artificiales suman en la función objetiva (+MR)
Las variables artificiales están acompañadas de un número M(se denota M
ya que puede ser un número muy grande)
f.o:
MaxZ=6x1+4x2
s.a
8x1+3x2=5 R1
5x1-2x2=-3 //-1 R2
6x1+9x2=7 R3
x1,x2>=0 cnn
Por el método de penalización:
Estandarizando tenemos:
f.o
MaxZ-6x1-4x2+Mx3+Mx4+Mx5=0
s.a
8x1 +3x2+x3 =5
-5x1+2x2 +x4 =3
6x1 +9x2 +x5 =7
x1,x2>=0 var básicas
x3,x4,x5>=0 var artificiales
z x1 x2 x3 x4 x5 sol
z 1 -6 -4 M M M 0
x3 0 8 3 1 0 0 5
x4 0 -5 2 0 1 0 3
x5 0 6 9 0 0 1 7
Z=Z-Mf1-Mf2-Mf3
z x1 x2 x3 x4 x5 sol
z 1 -6-9M -4-14M 0 0 0 -15M
x3 0 8 3 1 0 0 5
x4 0 -5 2 0 1 0 3
x5 0 6 9 0 0 1 7
Min(5/3, 3/2, 7/9)=7/9
f3=1/9f3
z x1 x2 x3 x4 x5 sol
z 1 -10/3 +M/3 0 0 0 (4+14M)/9 (-37M+28)/9
x3 0 6 0 1 0 -1/3 8/3
x4 0 -19/3 0 0 1 -2/9 13/9
x2 0 2/3 1 0 0 1/9 7/9
EJ6)
F.O
MinZ=4x1+2x2
s.a:
5x1+3x2>=4
x1+ x2<=2
x1, x2>=0
Estandarizando tenemos:
MinZ=4x1+2x2+Mx5
Max-Z=-4x1-2x2-Mx5
Max-Z+4x1+2x2+Mx5=0
s.a
5x1+3x2 -x3+x5 =4
x1 + x2 +x4 =2
x1,x2>=0 var. básicas
x3>=0 var superflua
x5>=0 var artificial
x4>=0 var de holgura
5x1+3x2 -x3+x5 =4
x1 + x2 +x4 =2
-z x1 x2 x3 x4 x5 sol
-z 1 4 2 0 0 M 0
x5 0 5 3 -1 0 1 4
x4 0 1 1 0 1 0 2
z=z-Mf1
-z x1 x2 x3 x4 x5 sol
-z -1 4-5M 2-3M M 0 0 -4M
x1 0 5 3 -1 0 1 4
x4 0 1 1 0 1 0 2
Min(⅘, 2/1)=⅘
f1=1/5f1
-z x1 x2 x3 x4 x5 sol
-z 1 0 -2/5 4/5 0 5m-4/5 -16/5
x5 0 1 3/5 -1/5 0 1/5 4/5
x4 0 0 2/5 1/5 1 -1/5 6/5
Min(4/3, 3)=4/3
f2=5/3f2
-z x1 x2 x3 x4 x5 sol
-z 1 2/3 0 2/3 0 m-(⅔) -8/3
x5 0 5/3 1 -1/3 0 1/3 4/3
x4 0 -2/3 0 1/3 1 -1/3 2/3
Max-Z=-8/3
MinZ=8/3
MÉTODO DEL SIMPLEX DUAL
-Trabaja con restricciones (<=) a un número negativo
-Si tenemos restricciones (>=, =) se debe convertir a (<=)
Para la restricción (=):
Se divide en dos restricciones, una que es (<=) y otra que es (>=)
Para restricciones (>=)
Se debe multiplicar por (-1), haciendo la restricción (<=)
EJ6)
f.o:
Max Z=3x1+4x2
s.a
x1 + 6x2 >=5 R1
2x1 + 5x2 >=2 R2
x1, x2 >=0
Por el método simplex dual tenemos:
f.o:
MaxZ-3x1-4x2=0
s.a
-x1 - 6x2 + x3<=-5
-2x1 - 5x2 +x4<=-2 R2
x1, x2 >=0 var básicas
x3, x4 var holguras
z x1 x2 x3 x4 sol
z 1 -3 -4 0 0 0
x3 0 -1 -6 1 0 -5
x4 0 -2 -5 0 1 -2
Min(variables que no esten en la base de la fila z/fila con sol más negativa)
La única restricción es que no sea división entre cero
Min(|-3/-1|, |-4/-6|)=Min(3,2/3)=⅔
f1=-1/6f1
z x1 x2 x3 x4 sol
z 1 -7/3 0 -2/3 0 10/3
x2 0 1/6 1 -⅙ 0 5/6
x4 0 -7/6 0 -5/6 1 13/6
Maxz=10/3, x1=0, x2=⅚, x4=13/6
MaxZ=3(0)+4(5/6)=10/3
s.a
-0 - 6(⅚) + 0<=-5
-0 - 5(5/6) +13/6<=-2 R2
Resultado por dos fases = Resultado por penalización
Método dual simplex trabaja de distinta forma por tanto tendrá diferente resultado.
DUALIDAD (MODELO DUAL)
Se llama así porque tiene el modelo primal y el modelo dual
MaxZ MinG
MinZ MaxG
restr i<=b var i>=0
restr i=b var i IS
restr i>=b var i<=0
var i>=0 restr i>=b
var i IS(irrestricta de signo) restr i=b
var i<=0 restr i<=b
Max → ←Min
f.o normal MinG = 60y1+10y2+My5+My6
MaxZ=5x1+2x2 s.a
s.a 6 y1 + 5y2 -y3+y5=5
6x1+10y2 (<=, =, >=) 60 10y1 +2y2 -y4+y6=2
5x1+2x2 (<=, =, >=) 10
x1>=0 y1,y2=0 Irrestricta en el Signo
x1=0 y3,y4<=0
x1<=0 y5,y6>=0
x1=0 Irrestricta en el signo y7=0
2.2 Resuelva el problema dual del ejercicio 2.1
Modelo primal
𝑀ì𝑛 𝑍 = 2𝑥1 + 𝑥2
S.a.
3𝑥1 + 𝑥2 ≥ 3
4𝑥1 + 3𝑥2 ≥ 6
𝑥1 + 2𝑥2 ≥ 3
𝑥1 , 𝑥2 ≥ 0
Aplicando el dual se obtiene:
𝑀à𝑥 𝐺 = 3𝑦1 + 6𝑦2 + 3𝑦3
S.a.
3𝑦1 + 4𝑦2 + 𝑦3 ≤ 2
𝑦1 + 3𝑦2 + 2𝑦3 ≤ 1
𝑦1 ≥ 0, 𝑦2 ≥ 0 , 𝑦3 ≥ 0
PARA EL PRIMAL
PARA EL DUAL
EJ7) MODELO DUAL
Modelo primal:
Min Z=3x1+4x2
s.a
6x1+8x2 >= 48
-3x1+6x2 <= 18
x1, x2 >= 0
Modelo Dual:
MaxG=48y1+18y2
s.a
6y1-3y2 <= 3
8y1+6y2 <= 4
y1>=0, y2<=0 cnn
cv
y2<=0 //-1
-y2>=0
y3=-y2, y2=-y3
y3>=0
realizando el cv:
MaxG=48y1-18y3
s.a
6y1+3y3 <= 3
8y1-6y3 <= 4
y1>=0, y3>=0 cnn
MODELO PRIMAL
MODELO DUAL
EJERCICIOS DE DUAL SIMPLEX
MinZ=3x1+4x2
s.a
-6x1-8x2<=-48
-3x1+6x2<=18
x1,x2>=0
Estandarizamos:
Max-Z+3x1+4x2=0
s.a
-6x1-8x2 +x3 = -48
-3x1+6x2 +x4= 18
x1,x2>=0 var basicas
x3,x4>=0 var de holgura
z x1 x2 x3 x4 sol
z -1 3 4 0 0 0
x3 0 -6 -8 1 0 -48
x4 0 -3 6 0 1 18
Min{fila z, var que no esten en la base / Fila-columna sol con valor mas negativo}
Min{|-½|, |-½|}=Min{½,½ }=½
f1=-1/8f1
3-(4/-8)*-6=3-(24/8)=3*8/8-24/8=0
-3-(6/-8)*-6=-3-36/8=-24-36=60/8=30/4=15/2
18-(6/-8)*-48=18-(36)=-18
z x2 x3 x4 sol
x1
z -1 0 0 1/2 0 -24
x2 0 3/4 1 -1/8 0 6
x4 0 -15/2 0 3/4 1 -18
Min{0, |2/3|}=0
f2=-2/15f2
Max-Z=-3(0)-4(6)=-24
z x1 x2 x3 x4 sol
z -1 0 0 1/2 0 -24
x2 0 0 1 -1/5 1/10 21/5
x1 0 1 0 -1/10 -2/15 12/5
Max-z=-3(12/5)-4(21/5)=-24
PROBLEMAS DE APLICACIÓN
1) Con el comienzo del curso se van a lanzar unas ofertas de material escolar. Unos
almacenes quieren ofrecer 600 cuadernos, 500 carpetas y 400 bolígrafos para la oferta,
empaquetándolo de dos formas distintas; en el primer bloque pondrá 2 cuadernos, 1 carpeta
y 2 bolígrafos; en el segundo bloque, pondrán 3 cuadernos, 1 carpeta y 1 bolígrafo. Los
precios de cada paquete serán 6.5 y 7 €, respectivamente. ¿Cuántos paquetes le conviene
poner de cada tipo para obtener el máximo beneficio?
Max Z=Cx, c=vector de costos y precios
s.a
Ax<=b b=vector de recursos y/o disponibilidades
x>=0 x=variables
x1→bloque1 x2→bloque2 total
cuaderno 2 3 600
carpetas 1 1 500
boligrafos 2 1 400
precios 13/2 7
1. OBJETIVO
Maximizar el beneficio de las ventas de los bloques
2. ACTIVIDADES
x1: cantidad de paquetes de bloque 1
x2: cantidad de paquetes de bloque 2
3. FUNCIÓN OBJETIVA
MaxZ=13/2x1+7x2
4. RESTRICCIONES
2x1+3x2<=600 R1
x1+ x2<=500 R2
2x1+ x2<=400 R3
5. CNN
x1,x2>=0
Por el método gráfico:
Para R1: Para R2: Para R3:
2x1 + 3x2=600 x1+x2=500 2x1 + x2 = 400
0 200 0 500 0 400
500 0 200 0
300 0
f(x)=y=x2=(600-2x)/3 f(x)=500-x f(x)=400-2x
solucion 1: solucion 2: solucion 3:
MaxZ=13/2(0)+7(200)=1400 MaxZ=13/2(200)+7(0)=1300
Para la recta de Z:
13/2x1+7x2=0 //*2
13x1+14x2=0 → x1=0 y x2=0
→x1=700/13 y x2=-50
Para R1 y R3:
2x1+3x2<=600 (1)
2x1+ x2<=400 (2)
x1=150 y x2=100
MaxZ=13/2(150)+7(100)=1675
:El máximo beneficio que se puede hallar es de 1675 $
2) En una granja de pollos se da una dieta, para engordar, con una composición mínima de
15 unidades de una sustancia A y otras 15 de una sustancia B. En el mercado sólo se
encuentran dos clases de compuestos: el tipo X con una composición de una unidad de A y
5 de B, y el otro tipo, Y, con una composición de cinco unidades de A y una de B. El precio
del tipo X es de 10 euros y del tipo Y es de 30 €. ¿Qué cantidades se han de comprar de
cada tipo para cubrir las necesidades con un coste mínimo?
tipo X tipo Y
sustancia A 1 5 15
sustancia B 5 1 15
10 30
x1: cantidad de compuesto del tipo X
x2: cantidad de compuesto del tipo Y
Min Z=10x1+30x2
s.a
x1 + 5x2 => 15
5x1 + x2 => 15
x1,x2>=0
Para R1 Para R2
x2=(15-x1)/5 x2=15-5x1
x1 + 5x2=15 5x1 + x2 = 15
0 3 0 15
15 0 3 0
solucion 1 solucion 2
Minz=10(15)+30(0)=150 Minz=10(0)+30(15)=450
Para R1 y R2
x1=5/2
x2=5/2
Minz=10(5/2)+30(5/2)=100
