Método Simplex
Es posible convertir un problema de programación lineal en un .
sistema de ecuaciones para su solución por el método simplex. Se facilita si
se imponen dos requerimientos a las restricciones:
1. Todas las restricciones son ecuaciones con lado derecho no
negativo.
2. Todas las variables son no negativas.
Además, para convertir una desigualdad ≤ en una igualdad se agrega una
variable de holgura al lado izquierdo de la restricción.
6x1 + 4x2 ≤ 24 6x1 + 4x2 + s1 = 24 s1 es variable de holgura
no negativa
Método Simplex
De manera similar, para convertir una desigualdad ≥ en una .
igualdad se agrega una variable de Superávit al lado izquierdo de la
restricción.
2x1 - 5x2 ≥ 73 2x1 - 5x2 - S2 = 73 S2 es variable de Superávit
no negativa
Si el lado derecho de la igualdad es negativo se multiplica toda la ecuación
por -1, para cumplir con la primera condición del método simplex.
4x1 - 7x2 = -216 -4x1 + 7x2 = 216
12x1 + 5x2 ≥ -16 -12x1 - 5x2 ≤ 16 -12x1 - 5x2 + s3 = 16
Método Simplex
TRANSICIÓN DE LA SOLUCIÓN GRÁFICA A LA ALGEBRAICA
El método simplex está basado en las ideas generadas por el método
gráfico.
Para obtener una conclusión algebraica a partir de la representación
gráfica hay que entender que, en todas las PL no triviales, la cantidad de
ecuaciones m siempre es menor que la de variables n, por lo que se
obtiene una cantidad infinita de soluciones.
En el espacio de soluciones algebraicas, las soluciones básicas
corresponden a los puntos de esquina en el espacio de soluciones gráficas.
Se determinan igualando n-m variables a cero y resolviendo las m
ecuaciones para las m variables restantes, siempre que la solución
resultante sea única.
Método Simplex
La cantidad máxima de puntos esquina es:
Método Simplex
Método Simplex
Ejemplo: Maximizar z = 2x1 + 3x2
sujeto a: 2x1 + x2 ≤ 4
x1 + 2x2 ≤ 5; x1,x2 ≥ 0
Primero convertimos las restricciones en un sistema de ecuaciones:
2x1 + x2 + s1 = 4
x1 + 2x2 + s2 = 5; x1,x2,s1,s2 ≥ 0
!
Tenemos m = 2 ecuaciones y n = 4 variables, de , si
! !
! ! !
sustituimos respuestas o puntos
! ! ! ! ! !
de esquina máximos.
Método Simplex
Entonces para resolver el sistema hay que establecer las .
n – m variables no básicas, las variables restantes se conocen como
variables básicas:
Método Simplex
Método Simplex
Condición de optimalidad. La variable de entrada en un problema de
maximización (minimización) es la variable no básica con el coeficiente
más negativo (positivo) en la fila z. Los vínculos se rompen
arbitrariamente. El óptimo se alcanza en la iteración en la cual los
coeficientes en la fila z son no negativos (no positivos).
Condición de factibilidad. Tanto en problemas de maximización como de
minimización, la variable de salida es la variable básica asociada con la
relación mínima no negativa con el denominador estrictamente positivo.
Los vínculos se rompen arbitrariamente.
Método Simplex
Para resolver problemas de maximización, la condición de optimalidad
indica seleccionar la variable de entrada como la variable no básica con el
coeficiente objetivo más negativo en la ecuación objetivo.
En problemas de minimización, la condición de optimalidad requiere
seleccionar la variable de entrada como la variable no básica con el
coeficiente objetivo más positivo en la ecuación objetivo. Esto obedece a
que máx (z) equivale a mín (-z).
En cuanto a la condición de factibilidad para seleccionar la variable de
salida, la regla no cambia.
Método Simplex
Operaciones de filas de Gauss-Jordan
1. Fila pivote
a. Reemplace la variable actual en la columna Básica con la
variable de entrada.
b. Nueva fila pivote = Fila pivote actual / Elemento pivote
2. Todas las demás filas, incluida la z
Nueva fila = (Fila actual) - (Su coeficiente en la columna pivote) x
(Nueva fila pivote).
Método Simplex
Pasos del método simplex
Paso 1. Determine la solución factible básica inicial.
Paso 2. Seleccione una variable de entrada utilizando la condición de
optimalidad.
Deténgase si no hay variable de entrada; la última condición es
óptima. De otro modo, prosiga con el paso 3.
Paso 3. Seleccione una variable de salida utilizando la condición de
factibilidad.
Paso 4. Aplique los cálculos de Gauss-Jordan para determinar la nueva
solución básica. Vaya al paso 2.
Método Simplex
Ejemplo:
Maximizar z = 5x1 + 4x2 sujeto a:
6x1 + 4x2 ≤ 24 6x1 + 4x2 + s1 = 24
x1 + 2x2 ≤ 6 x1 + 2x2 + s2 = 6
-x1 + x2 ≤ 1 -x1 + x2 + s3 = 1
x2 ≤ 2 x2 + s4 = 2
Incorporación de variables de holgura
Verificación de igualdad, lado derecho de la
ecuación no negativo .
Método Simplex
Maximizar z = 5x1 + 4x2 sujeto a:
6x1 + 4x2 ≤ 24 6x1 + 4x2 + s1 = 24
x1 + 2x2 ≤ 6 x1 + 2x2 + s2 = 6
-x1 + x2 ≤ 1 -x1 + x2 + s3 = 1
x2 ≤ 2 x2 + s4 = 2
La tabla inicial se representa de la siguiente manera:
Método Simplex
Variable de entrada (como el problema es
maximizar, buscamos la más negativa)
Variables básicas (solo en un renglón tiene
valor 1, en el resto tiene valor de 0).
Método Simplex
Para encontrar la variable de salida, dividir la columna solución .
entre la columna de la variable entrante, buscando el resultado mínimo
positivo
Método Simplex
A partir de esta decisión, se aplican los cálculos de Gauss – Jordan
necesarios
Método Simplex
Método Simplex
Método Simplex
Termina el proceso ya que no hay más variables negativas en la fila
de maximización.
Método Simplex
Resolverlo paso a paso en Tora y en Solver (Excel).
Maximizar z = 5x1 + 4x2
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
-x1 + x2 ≤ 1
x2 ≤ 2
Variables irrestrictas en signo
Existen variables que durante una restricción puede cambiar de signo,
dejando de garantizar la “no negatividad” de una variable.
Estas variables se conocen como “Irrestrictas en signo”, y para evitar este
tipo de problemas durante el desarrollo de un modelo se pueden sustituir
matemáticamente mediante:
Donde son no negativas.
Además, es importante tener en cuenta que ambas no pueden ser
positivas al mismo tiempo.
Variables irrestrictas en signo
Ejemplo con variables irrestrictas en signo:
Una compañía está planeando fabricar un producto para marzo, abril,
mayo y junio del próximo año. Las cantidades demandadas son 520, 720,
520 y 620 unidades, respectivamente. La compañía tiene una fuerza de
trabajo permanente de 10 empleados pero puede satisfacer las
necesidades de producción fluctuantes contratando y despidiendo
trabajadores temporales. Los costos adicionales de contratar y despedir un
trabajador temporal en cualquier mes son de $200 y $400,
respectivamente. Un trabajador de planta produce 12 unidades por mes; y
uno temporal, que no tiene la misma experiencia, produce 10. La
compañía puede producir más de lo necesario en cualquier mes y guardar
el excedente para el mes subsiguiente a un costo de retención de $50 por
unidad por mes. Desarrolle una política óptima de contratación y despido
durante el horizonte de planificación de 4 meses.
Variables irrestrictas en signo
Demandas por mes:
520 – 12(10) = 400 Unidades pendientes para Marzo
720 – 12(10) = 600 Unidades pendientes para Abril
520 – 12(10) = 400 Unidades pendientes para Mayo
620 – 12(10) = 500 Unidades pendientes para Junio
Variables irrestrictas en signo
Demandas por mes:
520 – 12(10) = 400 Unidades pendientes para Marzo
720 – 12(10) = 600 Unidades pendientes para Abril
520 – 12(10) = 400 Unidades pendientes para Mayo
620 – 12(10) = 500 Unidades pendientes para Junio
Número de empleados permanentes
Piezas producidas por mes por
empleado permanente
Demanda mensual del producto
Variables irrestrictas en signo
Variables:
xi = Cantidad neta de trabajadores temporales al inicio del mes i
después de cualquier contratación o despido
Si = Cantidad de trabajadores temporales contratados o despedidos
al inicio del mes i
Ii = Unidades del inventario final para el mes i
Existirán entonces: x1, x2, x3, x4, s1, s2, s3, s4, I1, I2, I3 (I4 no existe, por?)
Variables irrestrictas en signo
Una primera aproximación al modelo sería:
10 x1 = 400 + I1
I1 + 10 x2 = 600 + I2
I2 + 10 x3 = 400 + I3
I3 + 10 x4 = 500 .
x1 = s1
x2 = x1 + s2
x3 = x2 + s3
x4 = x3 + s4
Existirán entonces: x1, x2, x3, x4≥0 s1, s2, s3, s4 Irrestrictas en signo.
I1, I2, I3 ≥0 pueden contratar o despedir
temporales
Variables irrestrictas en signo
Obligando a las variables irrestrictas a volverse variables no
negativas tenemos:
10 x1 = 400 + I1
I1 + 10 x2 = 600 + I2
I2 + 10 x3 = 400 + I3
I3 + 10 x4 = 500 .
x1 =
x2 = x1 +
x3 = x2 +
x4 = x3 +
Existirán entonces: x1, x2, x3, x4 ,I1, I2, I3 ≥0
≥0
Variables irrestrictas en signo
Buscando el objetivo:
Se busca reducir los costos por todas las operaciones: el inventario, la
contratación de eventuales y el despido de eventuales.
Costos por mantener un inventario = 50(I1+ I2+ I3 )
Costos por contratación de eventuales =200(
Costos por despido de eventuales =400(
Entonces, uniendo todas las necesidades:
z = 50(I1+ I2+ I3 ) + 200( + 400(
Buscando no perder dinero, necesitamos minimizar “z”
Método Simplex
Método Simplex - Ejercicios
Método Simplex - Ejercicios
X Y S1 S2 S3 SOL.
S3
Método Simplex - Ejercicios
Método Simplex - Ejercicios