Metallica

Programación Lineal:Problema de Asignación

Programación de Metas

Teoría de la dualidad

Tarea IV
BELTRÁN LLORENTE MARIA FERNANDA
DEL VALLE ARMAS MICHELLE 
GONZALEZ RICO DIANA VIRGINIA

http://www.youtube.com/watch?v=nfXvw52Kv1w

Unidad 3 Método Simplex Participación 8 Método de las dos fases

Min z =2x1+ 3x2
½ x1+ ¼ x2 ≤ 4
x1+3x2≥20
x1+ x2 = 10
x1,x2 ≥ 0

Agregando las variables artificiales nos queda:

Min z =2x1+ 3x2+Ma1+Ma2
½ x1+ ¼ x2 +x3= 4
x1+3x2-x4+a1=20
x1+ x2 + a2= 10
x1,x2,x3,x4≥ 0  a1,a2≥ 0

FASE 1:

Min g =a1+a2
½ x1+ ¼ x2 +x3= 4
x1+3x2-x4+a1=20
x1+ x2 + a2= 10
x1,x2,x3,x4≥ 0  a1,a2≥ 0

	x1	x2	x3	x4	a1	a2	sol
wj-cj	2	4	0	-1	0	0	30
zj-cj	-2	-3	0	0	0	0	0
x3	0.50	0.25	1	0	0	0	4
a1	1	3	0	-1	1	0	20
a2	1	1	0	0	0	1	10

En esta primer tabla entra x2 por ser el de mayor coeficiente en w y sale a1 por ser la razón más pequeña

	x1	x2	x3	x4	a1	a2	sol
wj-cj	0.67	0	0	0.33	-1.33	0	3.33
zj-cj	-1	0	0	-1	1	0	20
x3	0.42	0	1	0.08	-0.08	0	2.33
x2	0.33	1	0	-0.33	0.33	0	6.67
a2	0.67	0	0	0.33	-0.33	1	3.33

En esta segunda tabla entra x1 y sale a2

	x1	x2	x3	x4	a1	a2	sol
wj-cj	0	0	0	0	-1	-1	0
zj-cj	0	0	0	-0.50	0.50	1.50	25
x3	0	0	1	-0.13	-0.29	-0.63	0.25
x2	0	1	0	-0.50	0.17	-0.50	5
x1	1	0	0	0.50	-0.50	1.50	5

En esta tabla se observa que en w=0 al igual que a1 y a2 por lo tanto se pasa a la Fase II eliminando las columnas y fila en rojo.

FASE II

	x1	x2	x3	x4	sol
zj-cj	0	0	0	-0.50	25
x3	0	0	1	-0.13	0.25
x2	0	1	0	-0.50	5
x1	1	0	0	0.50	5

Como podemos observar no hay variable de entrada por tanto llegamos a la solución

SOLUCIÓN
x1=5
x2=5
x3=.25
x4=0
Z=25

Unidad 3 Método Simplex Participación 7 Método de la M Grande

Min z = x1 + x2
x1 + x2 = 2
2x1 + 2x2 = 4
x1, x2 ≥ 0

Pasando a la Forma Ampliada nos queda:


Min z = x1 + x2+Ma1+Ma2
x1 + x2 + a1= 2
2x1 + 2x2 + a2= 4
x1, x2 ≥ 0  a1, a2 ≥ 0

Ahora encontraremos la solución:

	x1	x2	a1	a2	sol
zj-cj	-1	-1	-M	-M	0
a1	1	1	1	0	2
a2	2	2	0	1	4

En esta primer tabla tendremos que convertir en vectores unitarios las variables base a1 y a2.

	x1	x2	a1	a2	sol
zj-cj	3M-1	2M-1	0	0	6M
a1	1	1	1	0	2
a2	2	2	0	1	4

En esta tabla observamos que X1 será la variable de entrada ya que es el del valor más positivo por ser caso de minimización y de salida es a1.

	x1	x2	a1	a2	sol
zj-cj	0	-M	-3M+1	0	2
x1	1	1	1	0	2
a2	0	0	-2	1	0

En esta tabla ya se encuentra la solución óptima ya que las variables artificiales valen cero y ya no hay variable de entrada para escoger.

SOLUCIÓN
x1=2
X2=0
Z=2