Introduccion a la programacion lineal Maxi-Mini Cap.7

TEMA: INTRODUCCION A LA PROGRAMACION LINEAL
MAXIMIZACION Y MIMIZACION

Objetivo:
Rresolver un problema de maximización aplicando método simplex y excel solver.

INVESTIGACION DE OPERACIONES

Es el conjunto de métodos y procedimientos que tienen como objetivo optimizar la asignación de los recursos y hacer más eficientes los procesos.

Programación Lineal. Método simplex en problemas de MAXIMIZACION
La Programación Lineal fue desarrollada por George B. Danzig al final de la década de 1940, y se aplica cuando se desea maximizar o minimizar una función sujeta a ciertas restricciones o condiciones.

Supuestos de un problema de programación lineal:
1. Todas las variables de un sistema de PL son de primer grado.
2. Existe una función objetivo que se debe maximizar o minimizar.
3. Las restricciones del sistema de PL se deducen de las condiciones dadas en el problema.
4. En la solución de un problema de PL, el valor de las variables es siempre positivo.

Función objetivo.
Es la función que se desea maximizar o minimizar en un problema de PL. En general, existen infinitas soluciones, pero el objetivo es encontrar la solución óptima que es la que da el valor máximo o mínimo de la función objetivo.

Métodos de solución de un problema de PL
1. Método gráfico. Su limitación (y desventaja) es que sólo se pueden resolver sistemas con dos variables.
2. Método simplex. Permite resolver sistemas con n variables.
3. Usando programas de computación como Excel Solver, Lindo, QBS y otros.

Ejemplo. Una empresa fabrica tres tipos de muebles: sillas, mecedoras y sofás. Cada uno requiere de madera, plástico y aluminio en su proceso de elaboración. La empresa tiene disponibles 400 unidades de madera, 500 unidades de plástico y 1450 unidades de aluminio. Cada silla, mecedora y sofá se vende en $7, $8 y $12 respectivamente. Suponiendo que todos los muebles se venden, cuántas unidades de cada tipo se deben vender para que el ingreso sea máximo.

Paso 1. Definir las variables. Las variables corresponden a la pregunta del problema.
Sea X1 = Cantidad de sillas.
X2 = Cantidad de mecedoras.
X3 = Cantidad de sofás.

Paso 2. Plantear la función objetivo Z.
FO: Maximizar el ingreso Z = 7X1 + 8X2 + 12X3

Paso 3. Plantear restricciones.

Las restricciones se plantean para los recursos. Para plantear las restricciones, es conveniente, cuando sea posible, hacer una tabla con los datos del problema.

Tipo de mueble Madera Plástico Aluminio Precio unitario
Silla 1 unidad 1 unidad 2 unidades $7
Mecedora 1 1 3 $8
Sofá 1 2 5 $12
Disponible 400 500 1450

Restricciones:
Para madera: X1 + X2 + X3  400
Para plástico: X1 + X2 + 2X3  500
Para aluminio: 2X1 + 3X2 + 5X3  1450
De no negatividad: X1  0, X2  0, X3  0

Paso 4. Transformar el sistema de inecuaciones (desigualdades), en igualdades.

Para expresar una desigualdad “menor o igual que” (), en igualdad, se agrega una variable de holgura S en cada desigualdad. Al final de las igualdades, se agrega la función objetivo igual a cero.

X1 + X2 + X3 + S1 = 400
X1 + X2 + 2X3 + S2 = 500
2X1 + 3X2 + 5X3 + S3 = 1450
- 7X1 – 8X2 – 12X3 + Z = 0


Paso 5. Plantear matriz de coeficientes.
Variables estructurales Variables de holgura

X1 X2 X3 S1 S2 S3 Z
S1 1 1 1 1 0 0 0 400
S2 1 1 2 0 1 0 0 500
S3 2 3 5 0 0 1 0 1450
Z - 7 - 8 -12 0 0 0 1 0

Indicador más negativo (determina VE)
Variable entrante o variable que entra, VE. Está determinada por el indicador más negativo. En este caso la variable entrante es X3.
Variable saliente o variable que sale, VS. Está determinada por el cociente positivo más pequeño que se obtiene al dividir los términos independientes entre los coeficientes de la columna de la variable que entra.

Pivote. Es el coeficiente que se encuentra en la intersección de la columna de la variable que entra con la fila de la variable que sale. El pivote debe ser siempre 1.

X1 X2 X3 S1 S2 S3 Z
S1 ½ 1/2 0 1 -1/2 0 0 150
X3 ½ 1/2 1 0 1/2 0 0 250
S3 -1/2 1/2 0 0 -5/2 1 0 200
Z - 1 - 2 0 0 6 0 1 3000

X1 X2 X3 S1 S2 S3 Z
X2 1 1 0 2 -1 0 0 300
X3 0 0 1 -1 1 0 0 100
S3 -1 0 0 -1 -2 1 0 50
Z 1 0 0 4 4 0 1 3600

Respuesta.

El ingreso máximo es de $3600 que se obtiene elaborando
X1 = 0 sillas, X2 = 300 mecedoras y X3 = 100 sofás.
S3 = 50 significa que del recurso aluminio, sobraron 50 unidades.

Objetivo.

Resolver un problema de minimización aplicando método simplex, el dual y excel solver.

Método simplex en problemas de MINIMIZACION

Ejemplo
Un agricultor compra fertilizantes que contienen tres nutrientes:
A, B y C. Las necesidades mínimas son 160 unidades de A, 200 de B y 80 de C. En el mercado existen dos marcas de fertilizantes: Especial y Normal. Cada bolsa de Especial tiene un costo de $4 y contiene 3 unidades de A, 5 de B y 1 unidad de C.
Cada bolsa de Normal, tiene un costo de $3 y contiene 2 unidades de cada nutriente. Si el agricultor desea minimizar el costo manteniendo el requerimiento de nutrientes, ¿cuántas bolsas de cada marca debe comprar?

Paso 1. Definir variables.
Sea X1 = Cantidad de bolsas de Especial.
X2 = Cantidad de bolsas de Normal.


Paso 2. Determinar la función objetivo Z

FO: Minimizar el costo Z = 4X1 + 3X2
Minimizar Z = Maximizar – Z
De donde – Z = W = - 4X1 – 3X2 – Mt1 – Mt2 – Mt3

Paso 3. Plantear restricciones

Bolsa Nutriente A Nutriente B Nutriente C Costo/bolsa
Especial 3 unidades 5 unidades 1 unidad $4
Normal 2 2 2 $3
Requerido 160 unid. 200 unid. 80 unid.
Restricciones:
De nutriente A: 3X1 + 2X2  160
De nutriente B: 5X1 + 2X2  200
De nutriente C: X1 + 2X2  80
De no negatividad: X1  0, X2  0

Paso 4. Transformar desigualdades en igualdades
Para transformar una desigualdad “mayor o igual que” () en igualdad, se debe agregar una variable de holgura negativa -s y una variable artificial t.

3X1 + 2X2 – S1 + t1 = 160
5X1 + 2X2 – S2 + t2 = 200
X1 + 2X2 – S3 + t3 = 80
4X1 + 3X2 + Mt1 + Mt2 + Mt3 + W = 0


Paso 5. Matriz de coeficientes

X1 X2 S1 S2 S3 t1 t2 t3 W
t1 3 2 -1 0 0 1 0 0 0 160
t2 5 2 0 -1 0 0 1 0 0 200
t3 1 2 0 0 -1 0 0 1 0 80
W 4 3 0 0 0 M M M 1 0
W -9M+4 -6M+3 M M M 0 0 0 1 -440M

EL DUAL. Al problema inicialmente dado, se le llama PRIMAL. Todo primal tiene su DUAL. Si el primal es de maximización, su dual es de minimización y viceversa.
El valor óptimo de la función objetivo del dual es igual al valor óptimo de la función objetivo del primal.

Para plantear el dual:
1. Si el primal es de minimización, el dual es de maximización.
2. Las desigualdades cambian de sentido.
3. Todas las variables del dual son diferentes a las del primal para evitar confusiones.
4. Los coeficientes de la función objetivo del dual, son los términos independientes de las restricciones del primal.
5. Los coeficientes de las restricciones del dual son los coeficientes (en columna) de X1, X2, etc., del primal.
6. Los términos independientes del dual, son los coeficientes de la función objetivo del primal.

EL DUAL

FO: Maximizar D = 160Y1 + 200Y2 + 80Y3
Sujeta a las restricciones: 3Y1 + 5Y2 + Y3  4
2Y1 + 2Y2 + 2Y3  3
Y1, Y2, Y3  0
Transformando las desigualdades en igualdades
3Y1 + 5Y2 + Y3 + h1 = 4
2Y1 + 2Y2 + 2Y3 + h2 = 3
-160Y1 - 200Y2 – 80Y3 + D = 0
Y1 Y2 Y3 h1 h2 D
h1 3 5 1 1 0 0 4
h2 2 2 2 0 1 0 3
D -160 -200 -80 0 0 1 0

Y1 Y2 Y3 h1 h2 D
Y2 3/5 1 1/5 1/5 0 0 4/5
h2 4/5 0 8/5 -2/5 1 0 7/5
D -40 0 -40 40 0 1 160

Indicador más negativo (determina VE)
Cuando en una tabla simplex, varios indicadores tienen el mismo valor más negativo, se selecciona cualquiera de los indicadores para obtener la variable entrante. Del mismo modo, puede haber varios cocientes que “empaten” como los más pequeños. Puede seleccionarse cualquiera de estos cocientes para obtener la variable que sale.

Y1 Y2 Y3 h1 h2 D
Y1 1 5/3 1/3 1/3 0 0 4/3
h2 0 -4/3 4/3 -2/3 1 0 1/3
D 0 200/3 -80/3 160/3 0 1 640/3

Y1 Y2 Y3 h1 h2 D
Y1 1 2 0 1/2 -1/4 0 5/4
Y3 0 -1 -1/2 3/4 0 ¼
D 0 40 0 40 20 1 220

Respuesta: Costo mínimo = $220,
Comprando: X1 = h1 = 40 bolsas de Excel
X2 = h2 = 20 bolsas de Normal.

En la tabla solución del dual:
El valor de las variables de holgura del primal obtenidos en la fila de la función objetivo del dual, son las variables estructurales del primal.
El valor de las variables estructurales del dual obtenidos en la fila de la función objetivo del dual, son las variables de holgura del primal.

SOLUCIÓN DE UN PROBLEMA DE PROGRAMACION LINEAL CON SOLVER

Función Objetivo: Maximizar el ingreso Z = 7X1 + 8X2 + 12X3
Sujeta a las restricciones:
R1: X1 + X2 + X3  400
R2: X1 + X2 + 2X3  500
R3: 2X1 + 3X2 + 5X3  1450
X1, X2, X3  0
En hoja de Excel colocar los datos de la forma siguiente:

A B C D E F
1 Silla Mecedora Sofá
2 Variable X1 X2 X3
3 Cantidad 0 0 0
4 Ingreso 7 8 12 0 Disponible
5 R1 1 1 1 0 400
6 R2 1 1 2 0 500
7 R3 2 3 5 0 1450

Colocar cursor en celda objetivo E4. Hacer clic en fx (en parte superior), aparece menú de funciones. En Matemática y funciones trigonométricas buscar sumaproducto y Aceptar. Aparece tabla de matrices. En matriz 1 marcar de B3 a D3 (los ceros). Colocar cursor en matriz 2. Marcar de B4 a D4. Aceptar.

Colocar cursor en celda E5. Seleccionar fx aparece menú de funciones, seleccionar sumaproducto. Aceptar. Aparece tabla de matrices. En matriz 1, marcar de B3 a D3 (los ceros). Colocar cursor en matriz 2. Marcar de B5 a D5. Aceptar.

Colocar cursor en celda E6. Seleccionar fx, escoger sumaproducto y aceptar. En matriz 1 marcar de B3 a D3. Colocar cursor en matriz 2. Marcar de B6 a D6. Aceptar.

Colocar cursor en celda E7. Seleccionar fx, escoger suma producto. Aceptar. En matriz 1, marcar de B3 a D3. Colocar cursor en matriz 2 y marcar de B7 a D7. Aceptar.

Seleccionar herramientas de excel y escoger solver. Aparece cuadro de diálogo. En celda objetivo marcar celda E4. En valor de celda objetivo seleccionar máximo.

En cambiando celdas marcar de B3 a D3. Colocar cursor en ventana de restricciones y agregar. Aparece referencia de celdas, marcar de B3 a D3. Seleccionar desiguadad mayor o igual que ( = ) y poner número cero en la ventanita de la derecha. Agregar.

Colocar cursor en E5 y marcar desde E5 hasta E7 porque todas las desigualdades son iguales. Seleccionar la desigualdad menor o igual que = , colocar cursor en celda F5 y marcar desde F5 hasta F7. Aceptar. En la ventana de restricciones, aparecen las restricciones que se acaban de anotar. Seleccionar opciones y marcar modelo lineal y asumir no negativos. Aceptar y resolver. En este momento, en la fila 3 de cantidad los ceros habrán cambiado a 0 de X1 sillas, 300 de X2 mecedoras y 100 de X3 sofás. En la celda objetivo deberá aparecer 3600 como ingreso máximo.

Si las desigualdades no fueran iguales, las restricciones deben ingresarse una por una.