Unidad II
METODOS DE
PROGRAMACION LINEAL
METODO GRAFICO
Solución gráfica del problema lineal
X2
X1
Espacio de soluciones
METODO SIMPLEX
El método simplex para resolver el problema de programación
lineal, requiere que el problema sea presentado en la forma
estándar.
FORMA ESTANDAR
-Función objetivo maximizando
-Lados derechos no negativos
-Restricciones en igualdades
-Variables no negativas
METODO SIMPLEX
FORMA ESTANDAR
MAX Z= C1X1+C2X2+…+CnXn
S.a.
a11X1 + a12X2+ . . . + a1nXn =b1
a21X1 + a22X2+ . . . + a2nXn =b2
. . .
. . .
. . .
am1X1 + am2X2+ . . . + amnXn =bm
Xi ≥0 ( i=1, 2, …, n)
METODO SIMPLEX
Al ejecutar el algoritmo del simplex , la función objetivo
Z=C1X1+C2X2+…+CnXn
se escribe como:
Z-C1X1-C2X2-…-CnXn=0
METODO DE LAS DOS FASES
•FASE I
•FASE II
METODO DE LAS DOS FASES
EJEMPLO 1
Min Z = 4x1 + x2
s.a.
3x1 + x2 =3
4x1 + 3x2 ≥ 6
X1 + 2x2 ≤ 4
x1, x2 ≥ 0
FASE I
1.- Restricciones → igualdades
3x1 + x2 =3 → 3x1 + x2 + A1 = 3
4x1 + 3x2 ≥ 6 → 4x1 + 3x2 - H2 + A2 = 6
X1 + 2x2 ≤ 4 → X1 + 2x2 + H3 = 4
base
FASE I
2.- Sumar la minimización de las variables artificiales
Min A = A1 + A2
[Link] conteniendo variables artificiales
3x1 + x2 + A1 = 3
4x1 + 3x2 - H2 + A2 = 6
2.2. Despejar las variables artificiales
A1 = 3 - 3x1 - x2
A2 = 6 - 4x1 - 3x2 + H2
FASE I
2.3.- Sustituir los valores de A1 y A2 en la minimización
Min A = A1 + A2
Min A = ( 3 - 3x1 - x2 )+ ( 6 - 4x1 - 3x2 + H2)
Min A = 9 - 7x1 - 4x2 + H2
Min A 7x1 + 4x2 - H2 = 9
3.- Introducir en la tabla
Base x1 x2 H2 A1 A2 H3 SM
A1 3 1 0 1 0 0 3
Restricciones A2 4 3 -1 0 1 0 6
H3 1 2 0 0 0 1 4
A 7 4 -1 0 0 0 9
Entra el valor mas
Min A grande de los
positivos
FASE I
Base x1 x2 H2 A1 A2 H3 SM
A1 3 1 0 1 0 0 3 1
A2 4 3 -1 0 1 0 6 1.5
H3 1 2 0 0 0 1 4 4
A 7 4 -1 0 0 0 9
R.P. X1 1 1/3 0 1/3 0 0 1
A2
H3
A
FASE I
Base x1 x2 H2 A1 A2 H3 SM
R.P. X1 1 1/3 0 1/3 0 0 1 3
A2 0 5/3 -1 -4/3 1 0 2 1.1
H3 0 5/3 0 -1/3 0 1 3 1.3
A 0 5/3 -1 -7/3 0 0 2
X1 1 0 1/5 3/5 -1/5 0 3/5
R.P. X2 0 1 -3/5 -4/5 3/5 0 6/5
H3 0 0 1 1 -1 1 1
A 0 0 0 -1 -1 0 0
Si todos son 0 entonces el problema tiene un
espacio de soluciones factible, pasar a la fase II.
Si existen + el problema no tiene solución
FASE II
1.- Formar restricciones con los valores de la tabla
sin tomar en cuenta las variables artificiales
Base x1 x2 H2 A1 A2 H3 SM
X1 1 0 1/5 3/5 -1/5 0 3/5
X2 0 1 -3/5 -4/5 3/5 0 6/5
H3 0 0 1 1 -1 1 1
A 0 0 0 -1 -1 0 0
x1 + 1/5H2 = 3/5
x2 - 3/5 H2 = 6/5
H2 + H3 =1
FASE II
2.- Despejar x1 y x2 de las restricciones
x1 + 1/5H2 = 3/5 x1 = 3/5 - 1/5H2
x2 - 3/5 H2 = 6/5 x2 = 6/5 + 3/5 H2
3.- Tomar la F.O. original y sustituir los valores de las x
Min Z = 4x1 + x2
Min Z = 4(3/5 - 1/5H2 ) + (6/5 + 3/5 H2 )
Min Z = 12/5 - 4/5H2 + 6/5 + 3/5 H2
Min Z = 18/5 - 1/5H2 Min Z + 1/5H2 = 18/5
4.- Formar la tabla con las restricciones y la F.O. de la
fase II
Base x1 x2 H2 H3 SM
X1 1 0 1/5 0 3/5 3
Fase I X2 0 1 -3/5 0 6/5 -
H3 0 0 1 1 1 1 sale
Z 0 0 1/5 0 18/5
Fase II
entra
Base x1 x2 H2 H3 SM
X1 1 0 0 -1/5 2/5
X2 0 1 0 3/5 9/5
H2 0 0 1 1 1
Z 0 0 0 -1/5 17/5
Para cuando son ceros y negativos
METODO DE LAS DOS FASES
EJEMPLO 2
Min Z = 3x1 + 4x2 + 8x3
s.a.
2x1 + x2 ≥ 6
2x2 + 4x3 ≥ 8
METODO DE LA M
EJEMPLO MAX
MAX Z = 3x1 + 5x2 + 8x3
s.a.
2x1 + 5x2 ≥ 30
3x1 + 4x2 + x3 = 36
x1, x2 , x3 ≥ 0
METODO DE LA M
FORMA ESTANDAR
2x1 + 5x2 - H1 + A1 = 30
3x1 + 4x2 + x3 + A2 = 36
MAX Z = 3x1 + 5x2 + 8x3 - MA1 - MA2
MAX Z - 3x1 - 5x2 - 8x3 + MA1 + MA2 = 0
METODO DE LA M
Base X1 X2 X3 H1 A1 A2 SM SALE
A1 2 5 0 -1 1 0 30
A2 3 4 1 0 0 1 36
-Z -3-5M -5-9M -8-M M 0 0 -66M
ENTRA
Base X1 X2 X3 H1 A1 A2 SM
R.P. X2 2/5 1 0 -1/5 1/5 0 6
SALE
A2 7/5 0 1 4/5 -4/5 1 36
-Z -1- 0 -8-M -1- 1+9/5 0 30-
7/5M 4/5M M 12M
ENTRA
METODO DE LA M
Base X1 X2 X3 H1 A1 A2 SM
X2 0 1 -2/7 -3/7 3/7 -2/7 18/7
SALE
X1 1 0 5/7 4/7 -4/7 5/7 60/7
-Z 0 0 -51/7 -3/7 3/7+ 5/7+ 270/7
M M
ENTRA
Base X1 X2 X3 H1 A1 A2 SM
X2 2/5 1 0 -1/5 1/5 0 6
X3 7/5 0 1 4/5 -4/5 1 12
-Z 51/5 0 0 27/5 - 8+M 126
27/5+
M
METODO DE LA M
EJEMPLO MIN
MIN Z = x1 + 2x2 + x3
s.a.
600x1 + 500x2 + 1000x3 ≥ 3000
500x1 + 100x2 + 100x3 ≤ 2000
x1, x2 , x3 ≥ 0
METODO DE LA M
FORMA ESTANDAR
600x1 + 500x2 + 1000x3 - H1 + A1 = 3000
500x1 + 100x2 + 100x3 + H2 = 2000
MIN Z = x1 + 2x2 + x3 + MA1
(-1)(MIN Z = x1 + 2x2 + x3 + MA1 )
MAX - Z = - x1 - 2x2 - x3 - MA1
MAX – Z - x1 - 2x2 - x3 + MA1 = 0
METODO DE LA M
Base X1 X2 X3 H1 A1 H2 SM SALE
A1 600 500 1000 -1 1 0 3000
H2 500 100 100 0 0 1 2000
-Z 1-600M 2-500M 1-1000M M 0 0 -3000M
ENTRA
Base X1 X2 X3 H1 A1 A2 SM
X3 3/5 ½ 0 -1/1000 1/1000 0 3
H2 440 50 1 1/10 -1/10 1 1700
-Z 2/5 3/2 0 1/1000 - 0 -3
1/1000+M