UNIDAD 3: METODO
SIMPLEX
3.1 SOLUCION
GRAFICA
3.2 SOLUCION
TABULAR
3.3 VARIABLES
DE HOLGURA Y ARTIFICIAL
EL METODO SIMPLEX:
Transición del método grafico al método Simplex
Como
ya vimos el método gráfico indica que la solución óptima, de un programa
lineal, siempre está asociada a un punto esquina del espacio de soluciones
factibles. Este resultado es la clave del Método Simplex algebraico, y
en general para resolver cualquier modelo de programación lineal.
La
transición de la solución del punto esquina geométrico, hasta el método
simplex, implica un procedimiento de computo que determina en forma algebraica
los puntos esquinas. Esto se logra convirtiendo primero a todas las restricciones del modelo, de
desigualdades a ecuaciones (el modelo en forma estándar), para luego manipular
esas ecuaciones en forma sistemática.
Una propiedad general del método Simplex es
que resuelve la programación lineal en iteraciones. Cada iteración desplaza la
solución a un nuevo punto esquina, que
tiene potencial de mejorar el valor de la función objetivo. El proceso termina cuando
ya no se pueden tener mejoras. El método simplex implica cálculos voluminosos y
tediosos, lo que hace que la computadora sea una herramienta esencial para
resolver los problemas de programación lineal. Por consiguiente las reglas
computacionales del método simplex se adaptan para facilitar el cálculo.
Transición de la solución gráfica a la solución algebraica.
Las ideas contenidas en la solución gráfica,
de un modelo de programación lineal, son la base para desarrollar el método
algebraico simplex. El siguiente esquema muestra el paralelismo entre los dos
métodos.
|
Método Grafico
|
Método Algebraico.
|
|
1.
Se grafíca todas las restricciones, incluyendo las de
no negatividad.
2.
El espacio de soluciones consiste en una infinidad de
puntos factibles.
3.
Identifica puntos factibles de esquina del espacio de
soluciones.
4.
Los candidatos a la solución óptima corresponden a una
cantidad finita de puntos de esquina.
5.
Se usa la función objetivo para determinar el punto
esquina óptimo entre todos los candidatos.
|
1.
Se representa el espacio de soluciones con m ecuación y n
variables, y restringe a todas las variables a valores no negativos; m≤n.
(forma estándar del modelo)
2.
El sistema tiene infinidad de soluciones factibles.
3.
Determina las soluciones básicas factibles de las
ecuaciones.
4.
Los candidatos a solución óptima corresponden a una
cantidad finita de soluciones básicas factibles.
5.
Se usa la función objetivo para determinar la solución
básica factible óptima, entre todas las candidatas.
|
En el método gráfico, el espacio de
soluciones se delimita con los ¨semis-espacios¨
que representan las restricciones y en el método simplex, el espacio de
soluciones se representa con m ecuaciones
lineales simultaneas y n variables
no negativas.
En la representación algebraica, la cantidad m de ecuaciones siempre es menor, o igual a la cantidad de
variables n.
Si m =
n y las ecuaciones son consistentes, el sistema solo tiene una solución
(Solución Única); pero si m<n
(esto representa la mayor parte de los programas lineales), entonces el sistema
de ecuaciones producirá una infinidad de soluciones.
Ya establecimos como se representa el espacio
de soluciones de un programa lineal, en forma algebraica, entonces, las
candidatas para la solución óptima, que son los puntos esquinas, se determinan
con las ecuaciones lineales simultáneas como sigue:
En un conjunto de mxn ecuaciones, m<n se iguala a cero n-m variables,
y a continuación se despejan las n
variables restantes, de las m
ecuaciones; la solución resultante, si es única, debe corresponder a un punto
esquina del espacio de soluciones. En el siguiente ejemplo desarrollaremos el
procedimiento.
