Método Simplex

1
 Método Simplex
La programación lineal puede manejar problemas que impliquen solo dos variables de decisión.

El método simplex proporciona una técnica eficiente que se puede aplicar para resolver
LPP de cualquier magnitud - que involucran dos o más variables de decisión

3. En esta técnica, la función objetivo se utiliza para controlar el desarrollo de cada uno.
solución factible al problema.

4. Si existe una solución óptima al problema, se encuentra en los puntos de esquina del
región factible determinada por las restricciones del sistema.

5. El método símplex selecciona la solución óptima de entre el conjunto de soluciones factibles para
el problema por búsqueda iterativa.

6. Al utilizar la técnica simplex, podemos considerar un número mínimo de factibles

soluciones para obtener un óptimo.
Simplex Method
Solución básica: Si hay 'm' restricciones de igualdad y (m+n) número de variables.
(m <n), un comienzo para la solución óptima se realiza estableciendo 'n' desconocido igual a cero
y resolviendo para las ecuaciones 'm' en los 'm' desconocidos restantes, siempre que exista solución
y es único.

'n' variables cero se llaman variables no básicas y las restantes 'm' variables son
variables básicas llamadas

Solución Básica Factible: La solución produce todas las variables básicas no negativas.
Solución factible–Satisface todas las restricciones
Degeneración y no degeneración Solución básica factible–Una solución básica factible
se dice que es no degenerado si tiene exactamente 'm' Xj positivos (distintos de cero).
Si una o más de las 'm' variables básicas son cero, se llama degenerada.
(el problema no generará una nueva solución)
Pasos (procedimiento de iteración) en el Método Símplex

1. Formular el problema en un modelo matemático con función objetivo, restricciones

y variables de no negatividad
2. Configura la tabla simplex inicial con variables de holgura o exceso
3. Determine las variables de decisión que deberán incluirse en la solución
4. Determina qué variables reemplazar
5. Calcular nuevos valores de fila para ingresar variables
6. Revise las filas restantes

Repite los pasos 3 a 6 hasta que se obtenga la solución óptima.

Ejemplo 1
Un fabricante de artículos de madera produce mesas y sillas que requieren dos tipos de
insumos, es decir, madera y mano de obra,

Cada mesa requiere 2 unidades de madera y 4 unidades de trabajo

Cada silla requiere 3 unidades de madera y 3 unidades de trabajo
La ganancia de cada mesa es de Rs 40 y la ganancia de cada silla es de Rs 35
Los recursos totales disponibles para la fabricación de mesas y sillas son 60 unidades de madera y 96
unidades de trabajo.
El fabricante quiere maximizar su beneficio distribuyendo sus recursos para cada mesa
y silla.
Formule el problema matemáticamente y resuélvalo utilizando el método simplex.
 Ejemplo-1, Interpretación de los valores en el problema y solución
Deja que las mesas sean X1y las sillas sean X2

maximizar ganancias Z = 40X1+ 35X2

Rs. 40 de beneficio por mesa Rs. 35 de ganancia por silla

sujeto a la restricción de materia prima 2X1+ 3X2 60 La madera total disponible es de 60 unidades

Se requieren 2 unidades de madera por mesa Se requieren 3 unidades de madera por silla.

X1, X2≥0
El total de horas de trabajo disponibles es de 96 horas
Restricción de horas de trabajo 4X1+ 3X2 96
X1mesa y X2las sillas son
Se requieren 4 unidades de trabajo por mesa Se requieren 3 unidades de trabajo por silla. no negativo
Interpretación de elementos en la tabla Simplex

Deja S1ser variable holgada para la madera y S2ser variable de holgura para horas de trabajo

Z = 40X1+35X2+0S1+0S2 2X1+ 3X2+ S1= 60

40 35 4X1+ 3X 0 2+ S2=
0 96
Horas de trabajo a 0 Rs. por hora

kgs de madera a 0 Rs por kg

Estamos añadiendo S1y

S2función objetivo porque, si sobra madera o mano de obra, eso
se añadirá a nuestro objetivo de lucro.

Partamos de la suposición de que no hay costo para el material sobrante y la mano de obra sobrante.

Al final de la solución, si S1 o S2 quedan sobrantes, se considerarán tantas unidades como

unidades sobrantes de insumos.
 Tabla de simplex inicial

Cbi Cj Relación de solución

Variables básicas

Zj
Cj - Zj

Nota: Cj = Coefficient of objective function

Cbi = Coefficient of basic variables
ZJ = (suma del costo de las variables básicas multiplicado por los coeficientes de las variables de restricción)

Para todos los problemas de maximización, Cj–Zj debería ser 0

Cj - Zj = Beneficio neto (el costo debe ser negativo)

Tabla simplex inicial
2X1+ 3X2+ S1= 60 ZJ =

Función objetivo Z = 40X1+35X2+0S1+0S2 4X1 + 3X2+ S2= 96

Cbi Cj 40 35 0 0 Solución Proporción

Variables básicas
X1 X2 S1 S2

0 S1 2 3 1 0 60

0 S2 4 3 0 1 96

Zj

Cj - Zj

Cj = Coeficiente de la función objetivo El costo de las variables de holgura S1y S2son cero
Cbi = Coefficient of basic variables
 Interpretación de los elementos en la tabla Simplex
2X1 + 3X2+ S1 = 60
Z = 40X1+35X2+0S1+0S2 4X1+ 3X2+ S2= 96
Cbi Cj 40 35 0 0 Solución Proporción

Variables básicas
X1 X2 S1S2

0 S1 2 3 1 0 60

0 S2 4 3 0 1 96

Zj 0 0 0 0 0

Cj - Zj
40 35 0 0

ZJ =
 Cbi Cj 40 35 0 0 Relación de solución

Variables básicas X1 X2 S1S2

(BV)

0 S1 3 1 0 60
2 60 /2= 30

S2 4 3 0 1 96
0 96/4 = 24

Zj
0 0 0 0 0
Cj - Zj
40 35 0 0

Tenemos más ganancias de mesas, podemos usar todos los recursos solo para hacer mesas. Por lo tanto, selecciona mesa como
un producto para trabajar (es decir, columna clave)
¿Cuántas mesas y sillas se pueden hacer con la madera y el trabajo disponibles?
necesitamos 2 unidades de madera por mesa, tenemos 60 unidades de madera, es decir, podemos hacer 60/2–30 mesas
 Cbi Cj 40 35 0 0 Relación de solución

Variables básicas X1 X2 S1S2

(BV)

0 S1 3 1 0 60 60 / 2 = 30
2

0 S2 4 3 0 1 100 96/4 = 24

Zj 0 0 0 0 0

Cj - Zj 40 35 0 0

necesitamos 4 horas de trabajo /mesa tenemos 96 unidades de trabajo es decir podemos hacer 96/4–24 mesas
Aunque tenemos madera para 30 mesas, solo podemos hacer 24 mesas debido a la limitación de mano de obra.
por lo tanto selecciona el valor más bajo 24 (S2o mano de obra) para calcular la mejor mezcla de productos (seleccionar S2trabajo como fila clave
 entrando variable

Cbi Cj 40 35 0 0 Relación de solución

Variables básicas X1 X2 S1S2

(BV)

0 S1 2 3 1 0 60 60 /2= 30
4
40 S2 3 0 1 100 96/4 = 24

0 0 0 0 0
Zj variable de salida
40 35 0 0
Cj - Zj

Hemos seleccionado trabajar en la mesa consumiendo todas las horas de trabajo al hacer slack S2= 0
por lo tanto, podemos reemplazar S2con X1
 Cbi Cj 40 35 0 0 Relación de solución

Variables básicas X1 X2 S1S2

(BV)

0 S1 3 1 0 60
2

40 X1 4 3 0 1 96 96/4 = 24

Zj
0 0 0 0 0

Cj - Zj 0 0
40 35

Divide los coeficientes de la fila clave por el elemento clave (en este caso el tiempo requerido por tabla)
(4/4), (3/4), (0/4), (1/4) y (96/4) (estamos dividiendo el tiempo requerido por mesa a través de
productos, para ver si queda una hora, cuántos otros productos se pueden hacer))
 Cbi Cj 40 35 0 0 Relación de solución

Variables básicas X1 X2 S1S2

(BV)

0 S1 3 1 0 60 60 / 2 = 30
2

40 X1 4/4 3 0 1 100 96/4 = 24

Zj

Cj - Zj

Valor antiguo (-) 2 unidades de madera ( - ) 2 X4 horas de trabajo /4 = 0

 Cbi Cj 40 35 0 0 Proporción de solución

Variables básicas X1 X2 S1S2

(BV)

0 S1 3 1 0 60 60 / 2 = 30
2

40 X1 4/4 3 0 1 100 96/4 = 24

Zj

Cj - Zj

Valor antiguo (-) 3 unidades de madera (-)

3 - 2x3 /4 = 3/2 = 1.5

Para la segunda fila, aplica la fórmula; valor antiguo - {(valor de la columna clave correspondiente) x (clave correspondiente}
valor de fila)} / elemento clave
X1= 2 - 2 X4/4 = 0 Zj
X2= 3 - 2x3 /4 = 3/2 X1 = (0x0)+(40x1) = 40 ; X2= (0 x3/2)+(40x3/4) = 30
S1= 1- 2 x 0 /4 = 1
S2= 0 - 2x1/4 = -1/2 S1= ( 0x1) + (40x0) = 0 ; S2( 0x-1/2) + (40x1/4) = 10
solución = 60–2 x96/4 = 12 Solución (0x12) + (40 x24) = 960

Valor antiguo (-)

Solución I
Cbi Cj 40 35 0 0 Ratio de Solución

Variables básicas X1 X2 S1S2

(BV)

0 S1 0 3/2 1 -1/2 12 60 / 2 = 30

40 X1 1 3/4 0 1/4 24 96/4 = 24

Zj 40 30 0 10 960

Cj - Zj
 Cbi Cj 40 35 0 0 Solución Razón
Variables básicas X1 X2 S1 S2
(BV)

0 S1 0 3/2 1-1/2 12 60 /2= 30

40 X1 1 3/4 01/4 24 96/4 = 24
Zj 40 30 0 10 960

Cj - Zj
Tasas de sustitución o cambios en S2Desde una unidad de X1requiere cuatro horas, solución en
la tabla utiliza todas las 96 horas.

Si se dispone de una unidad de S2, es decir, una hora, para otros propósitos, entonces ¼ de unidades de X1
tendría que ser abandonado.

Ya que una unidad de X1se requieren 2 kg de madera, una hora de S2reduce la salida de X1por ¼
unidades, ¼ x 2 = ½ de madera no utilizada (-1/2)
Solución I
Cbi Cj 40 35 0 0 Razón de solución

Variables básicas X1 X2 S1S2

(BV)

0 S1 0 3/2 1 -1/2 12 60 /2= 30

40 X1 1 3/4 0 1/4 24 96/4 = 24

Zj 960
40 30 0 10
Cj - Zj 0 5 0 -10

0
Para todos los problemas de maximización, Cj–Zj debería ser
X1= 24, X2= 0, S1= 12, S2= 0 y los ingresos totales = 960
 Cbi Cj 40 35 0 0 Solución Proporción
Variables básicas X1 X2 S1 S2
(BV)

0 S1 0 3/2 1 -1/2 12 60 /2= 30

40 X1 1 3/4 01/4 24 96/4 = 24
Zj 960
40 30 0 10
Cj - Zj 0 05 -10
Tasas de sustitución o cambios en S1:0 correspondiente a X1implica que reducir un kg
la madera no tiene efecto en la producción de X1
Dado que se han utilizado todas las horas de trabajo, poner a disposición 1 kg de madera no causará ninguna
cambio en la salida (12 kg de madera está disponible sin usar)
Tasas de sustitución o cambios en X2Adición de una unidad de X2reemplazaría ¾ unidad de
producto X1
X2requiere 3 horas de trabajo, implica que renunciamos a ¾ unidades de X1

Añadiendo una unidad de X2reemplazaría 3/2 kg de madera (2 x ¾ = 3/2) o liberado de X1

 Cbi Cj 40 35 0 0 Solución Proporción
Variables básicas X1 X2 S1 S2
(BV)

0 S1 0 3/2 1 -1/2 12 60 /2= 30

40 X1 1 3/4 01/4 24 96/4 = 24
Zj 960
40 30 0 10
Cj - Zj 0 5 0 -10

Tasas de sustitución o cambios en X1Adición de una unidad de X1reemplazaría, una unidad de

el mismo producto.
Adición de X1y reemplazando por X1implica ningún cambio en el requisito de madera, es
cero.

Las tasas positivas indican disminución y negativa / liberación de material o mano de obra
 Cbi Cj 40 35 0 0 Solución Proporción
Variables básicas X1 X2 S1 S2
(BV)

0 S1 0 3/2 1 -1/2 12 60 /2= 30

40 X1 1 3/4 01/4 24 96/4 = 24
Zj 960
40 30 0 10
Cj - Zj 0 5 0 -10
cambios en Cj - Zj
Zj representa la pérdida de ganancias que resulta de la adición de una unidad variable
encabezando una columna en particular.
Zj = 40, 30, 0 and 10
Adición de una unidad de X1causas la reducción de una unidad del mismo producto y un 0
cambio en S1
Reducción de una unidad de X1resultaría en una pérdida de Rs. 40
Por lo tanto, para X1,el valor es igual a 40.
 Cbi Cj 40 35 0 0 Solución Ratio
Variables básicas X1 X2 S1 S2
(BV)

0 S1 0 3/2 1 -1/2 12 60 /2= 30

40 X1 1 3/4 01/4 24 96/4 = 24
Zj 960
40 30 0 10
Cj - Zj 0 5 0 -10
cambios en Cj - Zj
Adición de una unidad de X2resulta en dos cambios.
a. S1se reduce en 3/2 unidades y
b. X1se reduce en ¾ unidades
Dado que la ganancia por unidad de S1es nulo, los cambios en S1no causará cambios en el beneficio
Desde la ganancia de X1Una reducción de Rs.40 de 3/4 unidades resultaría en una pérdida de 40 x ¾ = 30
Para S1adición de una unidad de S1causa una sustitución de 1 unidad de lo mismo y ninguno de
X1por lo tanto, la pérdida de beneficios es cero
 Cbi Cj 40 35 0 0 Solución Relación
Variables básicas X1 X2 S1 S2
(BV)

0 S1 0 3/2 1 -1/2 12 60 /2= 30

40 X1 1 3/4 01/4 24 96/4 = 24
Zj 960
40 30 0 10
Cj - Zj 0 5 0 -10
cambios en Cj - Zj
Añadiendo una unidad de S2produce dos cambios
a. Liberación de 1/2 unidades de madera (S1) y
b. Consumir ¼ horas de trabajo de X1eso causaría una reducción de 40 x ¼ = 10 (pérdida de Rs. 10)
Para X2el beneficio unitario es de Rs. 35, mientras que la pérdida de beneficio es de Rs. 30
Cambio neto en la ganancia resultante de la adición de una unidad de X2,¿Es 35-30 Rs.5?
Para S1el cambio neto es cero mientras que para S2,agregar una unidad en la solución implicaría una pérdida neta
de Rs 10
Un valor positivo en (Cj–Zj) indica que el valor de la función objetivo puede ser incrementado.
 Cbi Cj 40 35 0 0 Solución Proporción
Variables básicas X1 X2 S1 S2
(BV)

0 S1 0 3/2 1 -1/2 12 12/3/2= 8

40 X1 1 3/4 0 1/4 24 24/3/4 =32
Zj 960
40 30 0 10
Cj - Zj 0 5 0 -10
 Cbi Cj 40 35 0 0 Solución Relación

Variables básicas X1 X2 S1 S2
(BV)

0 S1 0 3/2 1 -1/2 12
12/3/2 = 8
40 X1 1 3/4 0 1/4 24
24x4/3=32
Zj 960
40 30 0 10
Cj - Zj 0 5
0 -10

Los signos negativos son ganancias y los signos positivos son pérdidas o renuncias a otras actividades.

X1 1- ¾ x 0 / 3/2 = 1
S1 0–(¾ x 1) /3/2 = - 1/2
Valor antiguo - 1/4 - (¾ x - 1/2) / 3/2 = 0
S2
X2 3/4–(3/4x3/2) / 3/2= 0
 Cbi Cj 40 35 0 0 Solución Razón

Variables básicas X1 X2 S1 S2
(BV)

0 S1 0 3/2 1 -1/2 12
12/3/2 = 8
40 X1 1 3/4 0 1/4 24
24
Zj 960
40 30 0 10
Cj - Zj 0 5
0 -10

X1 1- ¾ x 0 / 3/2 = 1
S1 0–(¾ x 1) /3/2 = - 1/2 24 - (3/4 x 12) x 2/3 = 18

S2 1/4 - (¾ x - 1/2) / 3/2 = 1/2

X2 3/4 - (3/4x3/2) / 3/2 = 0
 Cbi Cj 40 35 0 0 Solución Proporción

Variables básicas X1 X2 S1 S2
(BV)

35 X2 0 1 2/3 - 1/3 8
12/3/2 = 8
40 X1 1 0 -1/2 1/2 18 24x4/3=32
Zj 40 35 10/3 25/3 1000

Cj - Zj 0 0
-10/3 -25/3

Los valores 0 y 1 bajo X1sugerir que una unidad de X1agregado a la mezcla actual requerirá reemplazar uno
unidad del mismo producto en la solución con 0 cambio necesario en el otro producto.
De manera similar para X2agregando un producto de X2no tendrá ningún cambio en X1
For S12/3 para X2y -1/2 para X1implica que liberar (quitar) un kg de madera significaría perder
2/3 unidades de X2y ganando ½ unidades de X1

Pérdida de 2/3 unidades de X2y ganancia de ½ unidades de X1resultaría en una pérdida neta de (35 x 2/3) - (40 x ½) = -10/3
 Cbi Cj 40 35 0 0 Solución Proporción

Variables básicas X1 X2 S1 S2
(BV)

35 X2 0 1 2/3 - 1/3 8

40 X1 1 0 -1/2 1/2 18

Zj 40 35 10/3 25/3 1000

Cj - Zj 0 0
-10/3 -25/3

Para S2the values - 1/3 for X2y 1/2 para X1indica que, liberar (remover) una hora de trabajo que
significa perder ½ unidades de X1y
ganando 1/3 horas X2
reducción de ½ horas de X1liberaría 4 x ½ = 2 horas de trabajo mientras agrega 1/3 horas para X2eso
consumiría 3 x 1/3 = 1 hora de trabajo

The changes shall cause a net reduction of Rs. 25/3 in profit

Una pérdida de 40 x ½ = 20 y una ganancia de 35 x 1/3 = 35/3 (20 - 35/3 = 25/3)
Ejemplo–1, Interpretación de los valores en el problema y solución
Deja que las mesas sean X1y las sillas sean X2

maximizar ganancias, Z = 40X1+ 35X2 Solución

X1= 18, X2= 8, Z =1.000
2X1+ 3X2 60
Z= 40(18) + 35(8) = 720 + 280 = 1,000
4X1+ 3X2 96
2(18)+3(8) = 36 + 24 = 60
X1, X2≥0 4(18) + 3(8) = 72 + 24 = 96