UNIDAD II
El método simplex
Subtemas
2.1. Método gráfico.
2.2. Método simplex.
2.3. Procedimiento para resolver problemas con
variables artificiales.
2.4. Casos especiales de programación lineal.
2.5. Método dual simplex.
2.6. Relaciones primal dual.
2.7. Análisis de sensibilidad e interpretación de
resultados.
2.8. Uso de software.
Competencia específica a desarrollar
Conoce y aplica el concepto del
método simplex en casos reales.
Conoce y aplica el concepto del
método de la M Grande y/o doble fase
y su aplicación en modelos con
variables artificiales.
Conoce y aplica las diferentes formas
de relación primal-dual.
Conoce y aplica el método dual
simplex
Interpreta el análisis de sensibilidad en
la toma de decisiones.
Bibliografía
TAHA HAMDY A.
Investigación de operaciones.
Alfaomega. 5 Ed. 1995.
Muñoz Castorena Rodolfo Valentín
Investigación de Operaciones
Ed. McGraw-Hill
Método Gráfico
El método gráfico se utiliza para solucionar
problemas de programación lineal mediante
la representación geométrica de las
restricciones, condiciones técnicas y
objetivas.
El modelo puede resolverse en forma gráfica
si sólo posee dos variables.
Conceptos relacionados con el Método Gráfico
La región factible es el conjunto de puntos que
satisfacen a la vez todas las desigualdades.
La región factible puede estar acotada o no
acotada. Cuando está acotada, se representa
gráficamente como un polígono con un
número de lados menor o igual que el de
restricciones.
Se llama solución óptima a la que maximiza o
minimiza la función objetivo. Esta solución si es
única siempre se encuentra en un vértice
o punto extremo de la región factible.
Pasos para resolver un problema lineal por el
Método Gráfico
1. Convertir las inecuaciones o
desigualdades en ecuaciones o
igualdades (Restricciones).
2. Se toma la primera ecuación, se le da a
una de las variables el valor de cero y se
realice el despeje correspondiente (esto
con la intención de obtener el primer
punto de la recta).
3. En la misma ecuación, se le da a la otra
variable el valor de cero y se despeja (se
encuentra el segundo punto de la recta).
4. Se toma la segunda ecuación y se
repiten los pasos 2 y 3.
Pasos para resolver un problema lineal por el
Método Gráfico
5. Y continuamos así hasta terminar con
todas las ecuaciones existentes.
6. Ubicamos los puntos encontrados en el
plano cartesiano, de esta manera
encontramos la región factible (≤ se
acerca al origen, ≥ se aleja del origen).
7. Identificamos los puntos en donde se
intersectan dos rectas (ecuaciones).
8. Si no es posible determinar con
exactitud la coordenada de uno de los
puntos se resuelve mediante uno de los
métodos de sistemas de ecuaciones
(reducción, sustitución e igualación).
Pasos para resolver un problema lineal por el
Método Gráfico
9. Ahora sustituimos los puntos
encontrados en la función objetivo.
10. Verificamos cuál cumple con la
condición que plantea la función
objetivo.
11. Damos solución al problema plateado.
Comprobación de resultados
PHPSimplex es una herramienta online para
resolver problemas de programación lineal.
Su uso es libre y gratuito.
Entre a la siguiente dirección:
[Link]
PHPSimplex
Método Simplex
El Método Simplex es un método analítico
de solución de problemas de programación
lineal capaz de resolver modelos más
complejos que los resueltos mediante
el método gráfico sin restricción en el
número de variables.
El Método Simplex es un método iterativo
que permite ir mejorando la solución en
cada paso.
Método Simplex
Fue creado en el año de 1947 por el
estadounidense George Bernard Dantzig y el
ruso Leonid Vitalievich Kantorovich, con el
ánimo de crear un algoritmo capaz de
solucionar problemas de m restricciones
y n variables.
Pasos para resolver un problema por el Método
Simplex
Suponga que usted produce galletas y que
gana $6 por cada galleta cuadrada y $5 por
cada galleta redonda. El modelo se resume
de la siguiente manera:
Max Z = 6x1 + 5x2
Sujeto a : x1 + x2 ≤ 9
x1 - x2 ≥ 1
x1 , x2 ≥ 0
Pasos para resolver un problema por el Método
Simplex
1.- Convertir el problema a forma estándar, para
ello cambiamos de signo la función objetivo,
convertir las inecuaciones en ecuaciones
agregando además una variable de holgura con
signo positivo si es ≤ y otra con signo negativo si
es ≥).
Forma Original Forma Estándar
Max Z = 6x1 + 5x2 Max Z = - 6x1 - 5x2
Sujeto a : x1 + x2 ≤ 9 Sujeto a : x1 + x2 + s1 = 9
x1 - x2 ≥ 1 x1 - x2 - s 2 = 1
x1 , x2 ≥ 0 x1 , x2 , s1 , s2 ≥ 0
Pasos para resolver un problema por el Método
Simplex
2.- Introducir los valores del modelo de la forma estándar a la tabla símplex.
Forma Estándar
Max Z = - 6x1 - 5x2
Sujeto a : x1 + x2 + s1 = 9
x1 - x2 - s 2 = 1
x1 , x 2 , s 1 , s 2 ≥ 0
x1 x2 s1 s2 Solución
s1 1 1 1 0 9
s2 1 -1 0 -1 1
Z -6 -5 0 0 0
Pasos para resolver un problema por el Método
Simplex
3.- Elegir el valor del renglón de Z, el valor más negativo (más pequeño).
El valor de Z que se elija indicará la columna que se debe y se llamará columna pivote
columna de entrada.
Columna de entrada o pivote
Más negativo
Pasos para resolver un problema por el Método
Simplex
4.- Se determina la variable de salida mediante la división de la columna solución de
las restricciones entre la columna pivote o de entrada. Recuerde que este
procedimiento solo se aplica a las restricciones, no a la función objetivo Z.
9/1 = 9
1/1 = 1
Pasos para resolver un problema por el Método
Simplex
5.- De las divisiones, se elige el resultado cuyo valor positivo sea el más pequeño sin
tomar en cuenta valores negativos o ceros, de esta manera encontramos el renglón de
salida.
Renglón de salida
9/1 = 9
1/1 = 1
Pasos para resolver un problema por el Método
Simplex
6.- Encontramos el pivote, este se forma cuando la columna de entrada y el renglón
de salida se intersectan.
Renglón de salida Columna de entrada
Pivote
Pasos para resolver un problema por el Método
Simplex
7.- Es importante que el valor del pivote sea 1, sino fuera 1, se convierte dividiendo
todo el renglón entre el valor del pivote.
8.- Hacer ceros los demás valores de la columna de entrada o pivote además debe de
cambiarse el nombre de la restricción de s2 a x1.
Columna de entrada
Renglón de salida
x1
Pasos para resolver un problema por el Método
Simplex
9.- Se multiplica el renglón x1, por el inverso del valor que se hará cero y sumárselo al
renglón que desea convertir; es decir si queremos hacer cero al 1, multiplicamos al
renglón x1 por -1, que es el inverso de 1 y el resultado se lo sumamos a s1.
x1 x2 s1 s2 Solución
s1 10 1 1 0 9
x1 1 -1 0 -1 1
Z -6 -5 0 0 0
(-1) (1) =-1 + 1 = 0
Pasos para resolver un problema por el Método
Simplex
10.- Repita el mismo procedimiento en todo el renglón.
x1 x2 s1 s2 Solución
s1 0 12 11 01 89
x1 1 -1 0 -1 1
Z -6 -5 0 0 0
(-1) (-1) = 1+1 = 2 (-1) (0) = 0+1 = 1 (-1) (-1) = 1+0 = 1 (-1) (1) = -1+9 = 8
Pasos para resolver un problema por el Método
Simplex
11.- Una vez terminado el renglón s1, continuamos con el renglón Z, multiplicando al
renglón x1 por 6 ya que es su inverso de -6. Además, el renglón x1 es el que tiene el
pivote.
(6) (1) = 6+0 = 6
x1 x2 s1 s2 Solución
s1 0 2 1 1 8
x1 1 -1 0 -1 1
Z -60 -5
-11 00 -6
0 60
(6) (1) = 6-6 = 0 (6) (-1) = -6-5 = -11 (6) (0) = 0+0 = 0 (6) (-1) = -6+0 = -6
Pasos para resolver un problema por el Método
Simplex
12.- Si en el renglón Z aún existen valores negativos, repetir desde el paso 3, hasta que
el renglón Z no tenga valores negativos.
Pivote Columna de entrada Renglón de salida
x1 x2 s1 s2 Solución
s1 0 2 1 1 8 8/2 = 4
x1 1 -1 0 -1 1 1/-1 = -1
Z 0 -11 0 -6 6
Pasos para resolver un problema por el Método
Simplex
x1 x2 s1 s2 Solución
x2 0 2 1 1 8
x1 1 -1 0 -1 1
Z 0 -11 0 -6 6
Se debe convertir a 1 el pivote, para ello dividimos todo el renglón entre 2
x1 x2 s1 s2 Solución
x2 0
0/2=0 2/2=1
2 1
1/2=1/2 1
1/2=1/2 8
8/2=4
x1 1 -1 0 -1 1
Z 0 -11 0 -6 6
Pasos para resolver un problema por el Método
Simplex
x1 x2 s1 s2 Solución
x2 0 1 1/2 1/2 4
x1 1 -1 0 -1 1
Z 0 -11 0 -6 6
Ahora hay que hacer ceros los números que se encuentran debajo del pivote.
x1 x2 s1 s2 Solución
x2 0 1 1/2 1/2 4
x1 1 0 1/2 -1/2 5
Z 0 0 11/2 -1/2 50
Nuevamente verificamos que no existan números negativos en el renglón de Z, si
existen, repetimos el procedimiento desde el paso 3.
Pasos para resolver un problema por el Método
Simplex
Buscamos nuevamente el pivote.
Columna de entrada
Renglón de salida
x1 x2 s1 s2 Solución
x2 0 1 1/2 1/2 4 4 / 1/2 = 8
x1 1 0 1/2 -1/2 5 5 / -1/2 = -10
Z 0 0 11/2 -1/2 50
Pivote
Pasos para resolver un problema por el Método
Simplex
x1 x2 s1 s2 Solución
x2 0 1 1/2 1/2 4
x1 1 0 1/2 -1/2 5
Z 0 0 11/2 -1/2 50
x1 x2 s1 s2 Solución
s2 0 1 1/2 1/2 4
x1 1 0 1/2 -1/2 5
Z 0 0 11/2 -1/2 50
Pasos para resolver un problema por el Método
Simplex
x1 x2 s1 s2 Solución
s2 0 2 1 1 8
x1 1 1 1 0 9
Z 0 1 6 0 54
Nuevamente verificamos que no existan números negativos en el renglón de Z, como se
puede apreciar ya no existen valores negativos por lo tanto hasta aquí se detienen las
iteraciones
X1 = 9
X2 = 0
Z = 54
Como conclusión:
Debe fabricarse 9 galletas de tipo cuadrada y 0 de tipo redonda, para generar una
utilidad máxima de $ 54.00
Dualidad
El término de dualidad señala la existencia
de dos fenómenos o caracteres diferentes
en un mismo estado.
En investigación de operaciones todo
modelo de programación lineal está
asociado a otro modelo llamado dual; al
modelo de programación lineal también se
le conoce como modelo primal.
Las estructuras duales permiten:
Resolver problemas lineales que tienen
más restricciones que actividades.
Hacer interpretaciones económicas de
las soluciones óptimas de los problemas
de programación lineal.
Concebir nuevos algoritmos para
solucionar problemas de redes de
optimización.
Generar métodos como el dúal símplex
para realizar análisis de los programas de
programación lineal.
Dualidad
Para poder entender el concepto de dualidad debemos referirnos al tema matriz
transpuesta.
La matriz A transpuesta, se conoce con la simbología AT, es aquella en donde las
columnas se transforman en filas o viceversa.
Tome en cuenta que…
1. Si el primal es un problema de maximización, su dual será un problema de
minimización o viceversa.
2. Los coeficientes de la función objetivo del problema primal se convierten en los
coeficientes del vector de disponibilidad del problema dual.
3. Los coeficientes del vector de disponibilidad del problema original se convierten
en los coeficientes de la función objetivo del problema dual.
4. Los coeficientes de las restricciones del problema primal serán la matriz de
coeficientes del dual.
5. Los signos de desigualdad del problema dual son contrarios a los del primal.
6. Si el primal tiene M restricciones y N variables, el dual tendrá N restricciones y M
variables.
Ejemplo:
