Visita al Museo Memoria y Tolerancia

Visita al Museo Memoria y Tolerancia

En la Explanada del Museo

En el Interior del Museo

Video correspondiente a la Tarea 3.

Tarea 3:

Video de un Problema de Programación Lineal

URL de nuestro video: 

http://www.youtube.com/watch?v=APD4XpVqdbQ&feature=youtube_gdata

URL del Guión del Video

URL del Guión del Video

Que tal: Esta es la URL de nuestro Documento referente al guión del video.

URL: https://docs.google.com/document/d/1n2H8hxIYlphB1wrOkWsRsN5bp0kqw9IzeNb7j9seaPI/edit

Modelos: Primal y Dual.

“Modelo Primal y Modelo Dual”

Instrucciones: Resolver ambos Modelos en un Programa Computacional y comparar Resultados. Incluir Grafica para el Modelo Dual.

El Primal:

Min  z=2x₁+3x₂+5x₃+2x₄+3x₅

S.A: 

 x₁  +x₂+2x₃+x₄+3x₅ ≥4

2x₁-2x₂+3x₃+x₄+ x₅ ≥ 3

x_i ≥0

Solución:

Variables de Decisión: SOLUCIÓN ÓPTIMA
x1	1
x2	0
x3	0
x4	0
x5	1

F.O. Min z=

5

CUMPLIMIENTO DE RESTRICCIONES
S.A.	4	>=	4
	3	>=	3

Para la solución se empleo Microsoft Excell 2010 ®

El Dual:

Max g=4y₁+3y₂

S.A: 

  y₁+2y₂≤2

  y₁ -2y₂≤3

2y₁+3y₂≤5

  y₁  +y₂≤2

3y₁  +y₂≤3

Y_i ≥ 0

Solución:

Variables SOLUCIÓN ÓPTIMA
y1	0.8
y2	0.6

F.O. Max  g=

5

CUMPLIMIENTO DE RESTRICCIONES
S.A.	2	<=	2
	-0.4	<=	3
	3.4	<=	5
	1.4	<=	2
	3	<=	3

Para la solución se empleo Microsoft Excell 2010 ®

Gráfica:

Gráfica Elaborada con Wolfram Mathematica 8.0 ®

Como observamos tanto z como g valen 5, debido al teorema Fundamental de Dualidad que nos dice que si la Solución del Modelo Primal es Óptima entonces la del Dual también será Óptima y además z=g.

Simplex Revisado

*Método Simplex Revisado*

Max  z=5x₁+3x₂+x₃

S.A:

  x₁+  x₂+3x₃ ≤6

5x₁+3x₂+6x₃  ≤15

  x₁, x₂, x₃ ≥0

FORMA ESTÁNDAR:

Max  z=5x₁+3x₂+x₃

S.A:

  x₁+  x₂+3x₃+x₄           =6

5x₁+3x₂+6x₃         +x₅  =15

  x_i ≥0       i=1,…,5

FORMA MATRICIAL:

Ahora, siguiendo el Algoritmo de Simplex Revisado tenemos los siguientes pasos:

1.- Solución Inicial

2.- Variable de Entrada

3.- Variable de Salida

4.- Sacar Nueva Solución

2.- Variable de Entrada

Como observamos no hay variable de entrada de acuerdo al criterio de la variable de entrada en el caso de Máximización(en el z_j-c_j, buscar el valor mas negativo). Por lo tanto:

SOLUCIÓN ÓPTIMA:

x1=3	x2=0	x3=0	x4=3	x5=0
Z=15

Dos Fases

*Método de las Dos Fases*

Min z=2x₁+3x₂

S.A:

1/2x₁+1/4x₂   ≤4

    x₁+   3x₂   ≥20

    x₁+     x₂  =10

    x₁, x₂ ≥0

FORMA AMPLIADA:

Min z=2x₁+3x₂

S.A:

1/2x₁+1/4x₂+x₃                         =4

    x₁+   3x₂         -x₄₊ a₁          =20

    x₁+     x_{2                        +} a₂ =10

   

x_i ≥0   i=1,..,4

    a_i ≥0   i=1,2

PRIMERA FASE:

F.O.   Min  w= a₁+ a₂

S.A:

1/2x₁+1/4x₂+x₃                         =4

    x₁+   3x₂         -x₄₊ a₁          =20

    x₁+     x_{2                        +} a₁ =10

Para esta Primera fase tengo 6 variables y 3 restricciones, por lo tanto, tengo 3 variables básicas y 3 variables no básicas.

SOLUCIÓN INICIAL:

x1=0	x2=0	x3=4	x4=0	a1=20	a2=10
w=30

Construyendo la Primer Tabla:

Haciendo vectores unitarios a los correspondientes de las variables básicas:

Ahora buscamos que nuestra w valga cero para poder pasar a la siguiente fase:

Seguimos haciendo Gauss-Jordan hasta que las todas las variables artificiales salgan de la base y w valga cero.

Como observamos nuestras variables artificiales (a₁, a2) ya salieron de la base y w=0, por lo tanto podemos pasar a la siguiente fase quitando de la Tabla Óptima las columnas de las variables artificiales y el renglón de w_j-c_j.

SEGUNDA FASE:

Como observamos, el Problema Original pide Minimizar la Función Objetivo y de acuerdo al criterio de la variable de entrada para el caso de Minimización  (se busca la más Positiva en el z_j-c_j), ya no hay variable de entrada, y por lo tanto decimos que la tabla arroja directamente la Solución Óptima del Modelo Original, que es:

SOLUCIÓN ÓPTIMA:

x1=5	x2=5	x3=1/4	x4=0
Z=25