M TODO SIMPLEX

Investigación Operativa 1
Capítulo 4: Método simplex

Contenido
• Forma estándar de programación lineal.
• Características del algoritmo simplex.
• Método simplex para resolver problemas de
maximización.
• Método simplex para resolver problemas de
minimización.
• Casos especiales en el método simplex.
• Variables sin restricción de signo.
2

Introducción (1)
• El método gráfico es eficientepara dos variables.
• Pero muchos problemas de PL son complejos para aplicar
el método gráfico.
• El método simplex:
 Examina los puntos de esquina como en el método gráfico;
 Sistemáticamente examina los puntos de esquina, usando
álgebra, hasta encontrar una solución óptima;
 Hace esta búsqueda de manera iterativa.

3

Introducción (2)
• El método simplex:
 Provee la solución óptima a lasvariables Xi y la máxima utilidad
(o mínimo costo).
 Provee información económica importante.

• Comprender como el método simplex funciona es
importante para
 Poder utilizar la computadora con éxito, e
 Interpretar cabalmente los resultados impresos de PL.

4

Forma estándar de programación lineal
• Antes de poder utilizar el algoritmo simplex para resolver
un problema de PL, éste se debeconvertir en un
problema donde todas las restricciones sean ecuaciones y
todas las variables sean no negativas.
• Un problema de PL así convertido se dice que está en
forma estándar.

5

Forma estándar de programación lineal
Max Z = c1 X1 + c2 X2 + … + cn Xn
Sujeta a
a11 X1 + a12 X2 + … + a1n Xn = b1
a21 X1 + a22 X2 + … + a2n Xn = b2
….

….

…

…

…

am1X1 + am2X2 + … + amn Xn = bm
Con Xj ≥ 0 (j = 1, 2,…, n)
6

Características del algoritmo símplex (1)
Variables básicas y no básicas
• Considere un sistema Ax = b de m ecuaciones lineales y n
variables (suponga n ≥ m).
• Una solución básica para Ax = b es obtenida haciendo n m variables iguales a cero (variables no básicas), y
resolviendo para el resto de las m variables. Así, se asume
que al hacer las n - m variables iguales a cero se llega avalores únicos para las m variables restantes (variables
básicas).

7

Características del algoritmo símplex (2)
Cualquier solución básica en la cual todas las variables son
no negativas es llamada una solución básica factible.

AX

a11X1 + a12X2 + ... + a1nXn  b1
a21X1 + a22X2 + ... + a2nXn  b2
...
am1X1 + am2X2 + ... + amnXn  bm

b

8

Características del algoritmo símplex (3)
El siguienteteorema explica porque la solución básica
factible es de gran importancia para la programación lineal.
Teorema
La región factible para cualquier problema de programación
lineal es un conjunto convexo.
Así, un punto en la región factible de un problema de PL es
un punto extremo si y sólo si es una solución básica factible.

9

Método símplex para resolver problemas
de maximización
Horas requeridaspara producir 1 unidad
Departamento

Mesas

Sillas

Carpintería
Pintura y barnizado

4
2

3
1

Utilidad (UM por unidad)

7.00

5.00

Disponibilidad
(horas/semana)
240
100

10

Empresa maderera
Variables de decisión
X1 = número de mesas producidas y vendidas por semana
X2 = número de sillas producidas y vendidas por semana
Formulación matemática
F.O. Max Z = 7 X1 + 5 X2
Sujeta a
4 X1 + 3 X2 ≤ 240(Restricción de carpintería)
2 X1 + 1 X2 ≤ 100 (Restricción de pintura y
barnizado)
Con X1, X2 ≥ 0 (condiciones de no negatividad)
11

Conversión de las restricciones a
ecuaciones (1)
Convertir cada restricción de desigualdad en una ecuación.
•Las restricciones menor que o igual a (≤) son convertidas a
ecuaciones por adición de una variable de holgura a cada
restricción.
•Para el problema se definenlas variables de holgura como:
 X3 = horas no utilizadas en el departamento de pintura
y barnizado
 X4 = horas no utilizadas en el departamento de
carpintería
12

Conversión de las restricciones a
ecuaciones (2)
• Las variables de holgura son no negativas.
 X3 , X 4 ≥ 0
• Las restricciones ahora son escritas como ecuaciones.
 2 X1 + 1 X2 + 1 X3 = 100
 4 X1 + 3 X2 + 1 X4 = 240
• Las...