Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

IDO - Clase 4 - Solución de problemas de Programación Lineal: método simplex

No description
by

Edgar Guzman

on 15 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of IDO - Clase 4 - Solución de problemas de Programación Lineal: método simplex

Solución de problemas de Programación Lineal: método simplex
Esencia del método simplex
Cada
frontera de restricción
es una recta que marca el límite de lo que permite la restricción correspondiente

Los puntos de intersección son las
soluciones en los vértices
del problema
Los cinco puntos que se encuentran en los vértices de la región factible —(0, 0), (0, 6), (2, 6), (4, 3) y (4, 0)— son las soluciones factibles en los vértices (
soluciones FEV
).
En cualquier problema de programación lineal con n variables de decisión, dos soluciones FEV son adyacentes entre sí cuando comparten n - 1 fronteras de restricción. Dos soluciones FEV adyacentes están conectadas por un segmento de recta que se encuentra en estas mismas fronteras
de restricción compartidas. Dicho segmento de recta recibe el nombre de arista de la región
factible.
Solución de ejemplo
Paso inicial: Elija (0, 0) como la solución FEV inicial para examinarla.
Prueba de optimalidad: Concluya que (0, 0)
no
es una solución óptima.
Iteración 1
: Muévase a una solución FEV adyacente mejor, (0, 6), y realice los siguientes tres pasos.

Entre las dos aristas de la región factible que salen de (0, 0), elija desplazarse a lo largo de la arista que aumenta el valor de x2. (Con una función objetivo Z = 3x1 + 5x2, cuando aumenta el valor de x2 el valor de Z crece más rápido que si aumentara el valor de x1.)
Obtenga la intersección del nuevo conjunto de fronteras de restricción: (0, 6). (Las ecuaciones de estas fronteras de restricción, x1 = 0 y 2x2 = 12, conducen de inmediato a esta solución.)
Deténgase al llegar a la primera frontera de restricción: 2x2 = 12. [Si va más lejos en la dirección seleccionada en el paso 1, saldrá de la región factible; por ejemplo, cuando se desplaza hasta la segunda frontera de restricción en esa dirección se llega a (0, 9), que es una solución no factible en un vértice.]
Solución de ejemplo
Prueba de optimalidad: Concluya que (0, 6) no es una solución óptima.
Iteración 2: Muévase a una mejor solución FEV (2, 6), mediante la realización de los siguientes
pasos:

En las dos aristas de la región factible que salen de (0, 6) elija moverse a lo largo de la que va hacia la derecha.
Determine la intersección del nuevo conjunto de fronteras de restricción: (2, 6). (Las ecuaciones de estas fronteras de restricción, 3x1 + 2x2 = 18 y 2x2 = 12, conducen de inmediato a esta solución.)
Deténgase al encontrar la primera nueva frontera de restricción en esa dirección: 3x1 + 2x2 = 12. (Si se mueve más lejos en la dirección elegida en el paso 1, saldrá de la región factible.)
Solución de ejemplo
Prueba de optimalidad: Concluya que (2, 6) es una solución óptima y deténgase.
Conceptos clave para la solución
Concepto de solución 1
El método símplex analiza sólo las soluciones FEV. Para cualquier
problema con al menos una solución óptima, la ubicación de una de ellas sólo requiere encontrar una mejor solución FEV.
Concepto de solución 2
El método símplex es un algoritmo iterativo
Concepto de solución 3
Siempre que es posible, en el paso inicial del método símplex se elige el origen (todas las variables de decisión iguales a cero) como la solución FEV inicial. Cuando se tienen demasiadas variables de decisión para encontrar una solución FEV inicial en una gráfi ca, esta elección elimina la necesidad de usar procedimientos algebraicos para obtenerla.
Concepto de solución 4
Dada una solución FEV, en términos de cómputo, es más rápido reunir información sobre sus soluciones FEV adyacentes que sobre otras soluciones FEV.
Por lo tanto, cada vez que el método símplex realiza una iteración para moverse de la solución FEV actual a una mejor, siempre escoge una solución FEV adyacente a la actual. No considera otras soluciones FEV. En consecuencia, toda la trayectoria que sigue hasta
alcanzar una solución óptima es a lo largo de las aristas de la región factible.
Concepto de solución 5
Después de identificar la solución FEV actual, el método símplex
examina cada una de las aristas de la región factible que salen de esta solución. Estas aristas conducen a una solución FEV adyacente en el otro punto extremo, pero el método símplex ni siquiera se toma la molestia de obtener la solución FEV adyacente. Sólo identifica la tasa de mejoramiento de Z que se obtendría al moverse por esa arista. Entre las aristas con una tasa positiva de mejoramiento de Z, selecciona moverse por aquella con la
tasa más grande de mejoramiento de Z. La iteración termina cuando se obtiene primero la solución FEV al fi nal de esta arista y después se reetiqueta esta solución FEV adyacente como la solución FEV actual para pasar a la prueba de optimalidad y (si es necesario) a la siguiente iteración.
Concepto de solución 6
El concepto de solución 5 describe la manera en que el método símplex examina cada arista de la región factible que sale de la solución FEV actual. A través de este examen de una arista es sencillo identificar la tasa de mejoramiento de Z que se obtendría al moverse por ella hasta la solución FEV adyacente en el otro extremo. Una tasa positiva de mejoramiento de Z implica que la solución FEV adyacente es mejor que la actual, mientras que una tasa negativa de mejoramiento de Z indica que la solución FEV adyacente es peor. Por lo tanto, la prueba de optimalidad consiste sólo en verificar si alguna de las aristas conduce a una tasa positiva de mejoramiento de Z. Si ninguna lo
hace, la solución FEV actual es óptima.
Full transcript