Invertigación de Operaciones 1: El Método Simplex

El Método Simplex es una herramienta algebraica que, por medio de una serie de repetidos pasos, se acerca progresivamente a una solución óptima. En teoría el Método simplex logra resolver problemas que posea cualquier número de variables y restricciones.

Se recomienda que cuando hay más de 4 variables se utilice la computadora. Pero para conocer como se construyen las ecuaciones para el programa e interpretar los resultados se explicará de forma manual el método.

Las inecuaciones originales pueden ser transformadas algebraica mente de acuerdo las propiedades siguientes:

1. Cada variable básica aparece en una y sólo una ecuación en la que el coeficiente  es +1.
2. En el segundo miembro de las ecuaciones sólo hay términos constantes no negativos.

Ahora se demostrará como se puede modificar un conjunto de inecuaciones que no satisfacen las 2 propiedades anteriores. Por ejemplo, considere el siguiente planteamiento de inecuaciones que contienen restricciones ≤, ≥, =, así como segundos miembros positivos y negativos:

Maximizar: F(A, C) = 12 A + 20 B + 8 C (Utilidad)

Sujeto a:

Inecuación 1: 3 A – 2 C ≥ -2

Inecuación 2:-4 A – B + 12 C ≥ 4

Inecuación 3: – A + 3 C ≤ – 6

Inecuación 4: 3 A + 4 B – 6 C = -12

Inecuación 5: B  + 9 C = 31

A, B, C ≥ 0

Este sistema de ecuaciones originales no satisface las propiedades

Lo primero que habría que hacer es multiplicar por (-1) las in-ecuaciones 1, 3 y 4 para transformar el término de la derecha a positivo.

-3 A + 2 C ≤ 2

-4 A – B + 12 C ≥ 4

A – 3 C ≥  6

-3 A – 4 B + 6 C = 12

B  + 9 C = 31

A, B, C ≥ 0

Lo segundo es adicionar las variables artificiales de acuerdo al cuadro 1:

Cuadro 1. Variables artificiales según la desigualdad o igualdad correspondiente.

Quedando un nuevo problema distinto al original pero equivalente a éste solo cuando todas las 4 variables artificiales tengan el valor cero. Las inecuaciones se transforman a igualdad de la siguiente manera:

Maximizar: F(A, C) = 12 A + 20 B + 8 C – Ma1 – Ma2-Ma3- Ma4

Sujeto a:

Ecuación 1: -3 A         +  2 C + S1                                         =   2

Ecuación 2:-4 A – B   + 12 C          – S2        + a1                  =   4

Ecuación 3:    A            – 3 C                 -S3         +a2             =   6

Ecuación 4: -3 A – 4 B + 6 C                                     +a3           = 12

Ecuación 5:              B + 9 C                                           +a4 = 31

A, B, C ≥ 0

S1, S2, S3, a1, a2, a3, a4 ≥ 0

El cuadro 2 siguiente se completa con los coeficientes de las ecuaciones anteriores y se colocan las variables artificiales quedaría de la siguiente manera:

Cuadro 2. Matriz de las ecuaciones 1 al 5.

El cálculo de Zj para el primer dato sería: Zj = -3*0 + (-4) * (-M)+1*(-M)+(-3)*(-M)+0*(-M) donde Zj al multiplicar signo quedaría: Zj= 4M-M+3M  obteniéndose: Zj= 6M

El cálculo de Zj para el segundo dato sería: Zj =0*0 + (-1) * (-M)+0*(-M)+(-4)*(-M)+ 1*(-M) donde Zj al multiplicar signo quedaría: Zj= M+4M-M  obteniéndose: Zj= 4M

El cálculo de Zj para el tercer dato sería: Zj =2*0 + (12) * (-M) + (-3)*(-M)+(6)*(-M)+ 9*(-M) donde Zj al multiplicar signo quedaría: Zj= -12M+3M-6M-9M  obteniéndose: Zj=-24M.

El cálculo de Zj para el cuarto dato sería: Zj =1*0 + (0) * (-M)+0*(-M)+(0)*(-M)+ 0*(-M) entonces Zj = 0

El cálculo de Zj para el Quinto dato sería: Zj =0*0 + (-1) * (-M)+0*(-M) + (0)*(-M)+ 0*(-M) entonces Zj = M

El cálculo de Zj para el Sexto dato sería: Zj =0*0 + (0)*(-M)+(-1)*(-M) + (0)*(-M)+ 0*(-M) entonces Zj = M

El cálculo de Zj para el Séptimo dato sería: Zj =0*0 + (1)*(-M)+(0)*(-M) + (0)*(-M)+ 0*(-M) entonces Zj = – M. Los términos de Zj para octavo, noveno y decimo será Zj= -M.

Cj-Zj en el primer término será: Cj – Zj = El primer coeficiente de función objetivo menos primer término de Zj  por lo que la respuesta será: Cj-Zj = 12 – 6M.

En el segundo término: Cj – Zj = 20-4M; Tercer Término: Cj – Zj = 8+24M; Cuarto Término: Cj – Zj = 0, quinto término: Cj-Zj= -M, sexto término: Cj-Zj= -M, séptimo al décimo termino serán de: Cj – Zj = 0

En el cuadro 3 se escoge Cj – Zj=8+ 24 M como columna pivote (sombreada de amarillo) por ser el mayor de todos los valores de Cj-Zj.

Se divide cada valor ($) entre la columna pivote, obteniendo: 2/2, 4/12, 6/3, 12/6, 31/9, de estos valores se escoge el menor que sería 4/12 esta sería la fila pivote a la que se sombrea con canela. La intersección entre fila y columna se encuentra el pivote que es 12 (ver cuadro 3).

Luego la fila pivote se divide toda entre el pivote o sea -4/12, -1/12, 12/12, 0/12, -1/12, 0/12, 1/12, 0/12, 0/12, 0/12.

Cuadro 3. Selección del pivote

Dato Nuevo = dato antiguo – Producto de las esquinas opuestas/Pivote

El nuevo dato del reglón S1 y de la columna A se calcula con la formula:

Para encontrar el primer valor en la casilla (S1, A): -3 – 2(-4)/12 = -3+2/3 = -7/3

Para la casilla (a3, S2) se tiene el nuevo dato sería: 0 – (-1)(6)/12 = 1/2

Con esto se puede establecer que se aplica la regla del pivote para obtener todos los nuevos datos de las posiciones restantes en el cuerpo principal de la nueva tabla.

En el cuadro 4 se observan los nuevos datos:

Cuadro 4. Matriz con nuevos datos

La solución de este ejemplo 1 no es factible por lo que solo se hizo para practicar

Otro ejemplo:

Para el periodo siguiente la máquina A tiene disponible 100 horas y la máquina B 80 horas. La contribución del producto 1 es $10 por 100 unidades y la del producto 2 es $5 por 100 unidades.

Un fabricante tiene dos producto 1 y 2, ambos elaborados en dos pasos por las máquinas A y B. Los tiempos de proceso por cada 100 unidades son los siguientes:

Productos	Máquina en horas
	A	B
1	4	5
2	5	2

Cuadro 6: Ejemplo 2

El fabricante se encuentra en un mercado en auge y puede vender todo lo que sea posible producir de ambos producto en el periodo próximo. Se quiere determinar las cantidades del producto 1 y 2 que se debe producir para maximizar su contribución.

Solución Simplex:

Formulación del ejercicio:

Productos	Máquina en horas		Contribución, $
	A	B
1	4	5	10
2	5	2	5
Disponibilidad	100	80

Cuadro 7. Formulación del ejemplo 2

Se puede expresar el ejemplo con las siguientes restricciones:

Máquina A: 4X1 + 5X2 ≤ 100

Máquina B: 5X1 + 2 X2 ≤ 80

La contribución total que se desea hacer lo más grande posible, dependen solo de las cantidades de los 2 productos que se fabriquen, enunciando la función objetivo:

Maximizar: Z = 10 X1 + 5X2

Por las desigualdades se hacen las equivalencias siguientes:

Máquina A: 4X1 + 5 X2 + S1 = 100

Máquina B: 5X1 + 2 X2 + S2 =   80

Estas ecuaciones se re acomodan en el cuadro de la siguiente manera:

Cuadro 8. Matriz Simplex inicial

El máximo valor en Cj-Zj = 10 es la columna pivote. Se divide el valor entre cada dato de columna pivote obteniendo 2.5 y 1 de estos 2 valores se escoge el menor y esta será la fila pivote.

En el cuadro 8 se obtuvo como pivote el 5 que es la intersección entre la fila y la columna pivote. Ahora se traslada 10 X1 a la fila pivote al lado izquierdo; el 10 como coeficiente básico y X1 como variable básica.

Los datos nuevos serian:

(S1, X1) = 0   por ser columna pivote.

(S1, X2) = 5 – 2*4/5 = 17/5

(S1, S1) = 1 – 0*4/5 = 1

(S1, S2) = 0 – 4*1/5 = – 4/5

Toda la fila pivote se divide entre 5 obteniendo la matriz presentado en el cuadro 9:

Cuadro 9. Segundo resultado Matriz simplex del ejemplo 2.

La tercera iteración quedaría de la siguiente manera:

Cuadro 10. Tercer resultado Matriz simplex del ejemplo 2

Esta tercera iteración sería la solución porque el resultado de Cj – Zj es cero y negativo. Por lo que se puede concluir:

Se deben elaborar aproximadamente 10.59 y 11.76  en cientos para generar una contribución de $170.59

Analice y Resuelva con el método simplex

1. Una compañía fabrica tres productos x, y, Z con 3 materias primas p1, p2 y p3. Los 3 productos usan unidades de las 3 materias primas de acuerdo con la tabla siguiente:

Productos	Materias primas en unidades			Contribución
	p1	p2	p3
X	2	0	3	3
Y	3	2	2	5
Z	0	5	4	4
Disponibilidad, unid.	7	8	10

Determine la combinación óptima del producto.

2. Una compañía minera posee 2 minas que producen Au, después de moler las clasifican en Alto, medio, bajo. La compañía minera ha firmado contrato con un planta fundidora para abastecerla con 12 toneladas de mineral alto, 8 toneladas con mineral de grado medio y 24 toneladas de grado bajo por semana. A la compañía le cuesta $180 diario la operación de la primera mina y $150 la operación de la segunda mina. Sin embargo estas minas tienen distintas capacidades, en la operación de un día la primera mina produce 6 toneladas de mineral de alto grado, 2 tonelada de grado medio,  y 4 tonelada de grado bajo. Mientras que la segunda mina produce diariamente 2 tonelada de alto grado, 2 tonelada de grado medio y 12 de grado bajo. ¿Cuántos días por semana debe funcionar cada mina para satisfacer en forma económica los pedidos de la compañía? Resuelva el problema con el método grafico y método simplex.

2. En cierta ocasión Lucrecia invito a 50 enemigos  a cenar. El platillo iba a ser un veneno. En esos días solo había 2 venenos en el mercado, el veneno X y el veneno y. Antes de preparar el menú la talentosa joven consideró algunas restricciones de su plan.

a)    Si utilizaba mas de ½ libra de veneno, los invitados lo descubrirían y no comerían.

b)    La hechicera privada de Lucrecia le proporciono , algunos números mágicos en esta copla:

Dos X y una Y si menos de ½ pobre de ti.

c)    El veneno X matará a 80 personas y el veneno Y a 150 personas por libra.

d)    El veneno X cuesta 100 monedas de oro /libra y el veneno Y cuesta 350 monedas de oro/libra.

Después de elaborar un menú que disimulara el sabor, Lucrecia encontró que le faltaban monedas de oro. Si Lucrecia no tenía cuidado no podría volver a planificar otra orgía de envenenamiento ese mes. Por lo tanto llamo a su alquimista, un hombre de mucho conocimiento  y le confió el problema.

Ayude al alquimista a resolver el problema, si fracasa recibirá como castigo una invitación a la comida del mes próximo.

3. Un herrero con 100 kg. de acero y 150 kgs. de aluminio quiere hacer bicicletas de paseo y de montaña que quiere vender, respectivamente a 2000 y 1500 Córdobas cada una para sacar el máximo beneficio. Para la de paseo empleará 1 kg. De acero y 3 kgs de aluminio, y para la de montaña 2 kg. de ambos metales. ¿Cuántas bicicletas de paseo y de montaña venderá?

Ver el siguiente tema sobre método simplex