viernes, 2 de mayo de 2014

Método Simplex

Unidad 4: Teoría de la Dualidad
Actividad 1: Programas Computacionales.



Programa


URL

Características

Ventajas

Desventajas

1.-          PHPSimplex


http://www.phpsimplex.com/simplex/simplex.htm?l=es
Es una herramienta online para resolver problemas de programación lineal.

Esta herramienta está pensada para ayudar a los estudiantes en su aprendizaje ya que no solo muestra los resultados finales sino también las operaciones intermedias.

Ofrece la solución directa para uso de profesionales.

Ofrece una interfaz amigable.

Manejo fácil e intuitivo.
Su uso es libre y gratuito.

Es capaz de resolver problemas mediante el método Simplex, el método de las Dos Fases, y el método Gráfico.

No cuenta con limitaciones en el número de variables de decisión ni en las restricciones de los problemas.

No es necesario instalar nada para poder usarlo.

Está disponible en varios idiomas.
No resuelve el Método de la M Grande.

Permite elegir que método quieres usar.
2.-
 JSimplex
http://soft.ingenieria-industrial.net/programacion_lineal.php
Resuelve problemas de Programación Lineal.
Resuelve el Método de la M Grande.

Si lo desea puede ver los cálculos intermedios y la explicación de cómo resolver el problema.


Fácil de usar.


No es necesario instalar nada para poder usarlo.


No deja elegir el método a usar.
3.-
 Herramienta Método Simplex
http://www.zweigmedia.com/MundoReal/simplex.html
Es bastante intuitivo.

La utilidad es bastante flexible con el ingreso.

Muestra todas las tablas y resultados.

Redondea los números decimales.
No son muy entendibles sus instrucciones y su forma de obtener algunas cosas importantes, como la variable de entrada.
4.- JSX
 JavaScript Simplex
http://destio.us.es/alumnos/jsxui/
Herramienta didáctica para alumnos y maestros.

Resuelve problemas de programación lineal.
Resuelve el Método Simplex, el Método de la M Grande, el Método de las Dos fases y el Método Gráfico.

Presenta graficados los problemas.
Se ha deducido que presenta algunos errores en el Método de la M Grande.
5.-
Simplex Algorithm Calculator.
http://www.mathstools.com/section/main/simplex_online_calculator?lang=es#.U2LS1vl5Ouo
Aplicacíon on line sobre el algoritmo del Simplex y el método de las dos fases. 
No está restringido en cuanto a la dimensión del problema y que la precisión en los cálculos es de 16 dígitos decimales.
No son muy entendibles las instrucciones de uso.

Ejercicio resuelto en el blog

     Unidad 4: Teoria de la Dualidad
     Participación 2: Modelos Duales

     Max z= x1+ 2x2 + 3x3
     s.a.
          X1- x2 + x3 ≥ 1                                    x1 = x4 - x5
         -X1+ x2 + x3 = 7                                   x3 = x6
          X1+ x2 ≤ 2
          X1 libre
          X2≥ 0
          X3 ≤ 0

Forma cónica de min con equivalencias:

Min z= -(x4 – x5) – 2x2 - 3x6
     s.a. 
          (x4 – x5) – x2 + x6 ≥ 1
          (x4 – x5) – x2 - x6 ≥ -7
          -(x4 – x5) + x2 + x6 ≥ 7
          -(x4 – x5) - x2 ≥ -2
          X2≥0                     
          X4≥0
          X5≥0                     
          X6≥0

Aplicar definición de la dualidad:

Max g = y1 – 7y2 + 7y3 – 2y2
     s.a.
          y1 + y2 - y3 – y≤ -1
         -y1 - y2 + y3 + y≤ 1
         -y1 - y2 + y3 – y≤ -2
         y1 - y2 + y3  ≤ -3
         y1 ≥ 0                   
         y2 ≥ 0
         y3 ≥ 0                   
         y4 ≥ 0

Llevar a la forma adecuada:

Min g = y1 + 7y2 - 2y3
      s.a
         y1 - y2 - y3 = 1
        -y1 + y2 - y3 ≤ -2
         y1 + y2 ≤ -3
         y1 ≥ 0
         y2 ≥ 0
         y3 ≥ 0

Ejercicio resuelto en el blog, haciendo uso del resumen

Unidad  4: Teoría de la Dualidad
Participación 1: Modelos Duales

Modelo Primal:

Min w=4y1 + 2y2 – y3
     s.a
          y1 +2y2  ≤  8
          y1 - y2  + 2y3 =  8
          5y1 + 3y3 ≥ 5
          y1 ≤  0
          y2 ≥ 0
          y3 no restringida

Modelo Dual:

Max g = 8x1 + 8x2 + 5x3
     s.a.
          x1 + x2 + 5x3 ≥ 4
          2x1 - x2 ≤ 2
          2x2 + 3x3 = -1
          x1 ≤  0
          x2 no restringida
          x3  ≥ 0

Ejercicio resuelto en el blog

Unidad 3: Método Simplex  Participación 10: Método Simplex Revisado



















Hemos llegado a la solución óptima:
X1 = 3
X2 = 0
X3 = 0
X4 = 3
X5 = 0
             Z= 15


jueves, 1 de mayo de 2014

Ejercicio resuelto en el blog.

Unidad 3: Método SimplexParticipación 9: Método de las Dos Fases


Min z = 2x1 + 3x2
     s.a.
          1/2x1 + 1/4x2 ≤ 4
          x1 + 3x2 ≥ 20
          x1 + x2 = 10
          x1, x2 ≥ 0

Forma ampliada:
Min z = 2x1 + 3x2
      s.a.
           1/2x1 + 1/4x2 + x3 =4
           x1 + 3x2 – x4 + a1 = 20
          x1 + x2 + a2 = 10
           x1, x2, x3, x4 ≥ 0
           a1, a2 ≥ 0

Forma Fase 1:
Min w = a1 + a2  à  wJ – C
            w = a1 + a2 
            w - a1 - a2 = 0
     s.a.
          1/2x1 + 1/4x2 + x3 =4
           x1 + 3x2 – x4 + a1 = 20
          x1 + x2 + a2 = 10
           x1, x2, x3, x4 ≥ 0
           a1, a2 ≥ 0

Forma Fase 2:
Min z = 2x1 + 3x2
        z - 2x1 + 3x2 = 0

Tablas:

X1
X2
X3
X4
a1
a2
Solución
Razón
wJ - cJ
0
0
0
0
-1
-1
0
-----
zJ - cJ
-2
-3
0
0
0
0
0
-----
X3
1/2
1/4
1
0
0
0
4
-----
a1
1
3
0
-1
1
0
20
-----
a2
1
1
0
0
0
1
10
-----


X1
X2
X3
X4
a1
a2
Solución
Razón
wJ - cJ
1
1
0
0
-1
0
10
-----
zJ - cJ
-2
-3
0
0
0
0
0
-----
x3
1/2
1/4
1
0
0
0
4
-----
a1
1
3
0
-1
1
0
20
-----
a2
1
1
0
0
0
1
10
-----


X1
X2
X3
X4
a1
a2
Solución
Razón
wJ - cJ
2
4
0
-1
0
0
30
-----
zJ - cJ
-2
-3
0
0
0
0
0
-----
x3
1/2
1/4
1
0
0
0
4
16
a1
1
3
0
-1
1
0
20
6.6
a2
1
1
0
0
0
1
10
10


X1
X2
X3
X4
a1
a2
Solución
Razón
wJ - cJ
2/3
0
0
1/3
-4/3
0
10/3
-----
zJ - cJ
-1
0
0
-1
1
0
20
-----
x3
5/12
0
1
1/12
-1/12
0
7/3
5.6
x2
1/3
1
0
-1/3
-1/3
0
20/3
20
a2
-2/3
0
0
-1/3
1/3
-1
-10/3
5


X1
X2
X3
X4
a1
a2
Solución
Razón
wJ - cJ
0
0
0
0
-1
-1
0
-----
zJ - cJ
0
0
0
-1/2
1/2
3/2
25
-----
x3
0
0
1
-1/8
1/8
-5/8
1/4
-----
x2
0
1
0
-1/2
½
-1/2
5
-----
x1
1
0
0
1/2
-1/2
3/2
5
-----



X1
X2
X3
X4
Solución
Razón
zJ - cJ
0
0
0
-1/2
25
-----
x3
0
0
1
-1/8
1/4
-----
x2
0
1
0
-1/2
5
-----
x1
1
0
0
1/2
5
-----

Este problema tiene solución múltiple, y una de ellas es:
x1 = 5
x2 = 5
x3 = 1/4

               z= 25