Programación Lineal

Programación Lineal

Ejercicio

Un nutricionista asesora a un individuo que sufre una deficiencia de hierro y vitamina B, y le indica que debe ingerir al menos 2400 mg de vitamina B-1 (tiamina) y 1500 mg de vitamina B-2 (riboflavina) durante cierto período de tiempo. Existen dos píldoras de vitaminas disponibles, la marca A y la marca B. Cada píldora de la marca A contiene 40 mg de hierro,10 mg de vitamina B-1, 5 mg de vitamina B-2 y cuesta 6 centavos. Cada píldora de la marca B contiene 10 mg de hierro, 15 mg de vitamina B-1 y de vitamina B-2, y cuesta 8 centavos (tabla 2). 
¿Cuáles combinaciones de píldoras debe comprar el paciente para cubrir sus requerimientos de hierro y vitamina al menor costo?


Marca A
Marca B
Requerimientos mínimos
Hierro
40 mg
10 mg
2400 mgVitamina B-1
10 mg
15 mg
2100 mg
Vitamina B-2
5 mg
15 mg
1500 mg
Costo por píldora (US$)
0,06
0,08
 


Solución
Sea x el número de píldoras de la marca A e y el número de píldoras de la marca B por comprar. El costo C, medido en centavos, está dado por
C = 6x+ 8y
Que representa la función objetivo por minimizar.
La cantidad de hierro contenida en x píldoras de la marca A e y elnúmero de píldoras de la marca B está dada por 40x+10y  mg, y esto debe ser mayor o igual a 2400 mg. Esto se traduce en la desigualdad.
40x+10y>2400 
Consideraciones similares con los requisitos mínimos de vitaminas B-1 y B-2 conducen a las desigualdades: 
10x+15y>2100
5x+15y>1500 
Respectivamente. Así el problema en este caso consiste en minimizar C=6x+8y sujeta a 
40x+10y>240010x+15y>2100
5x+15y>1500
X>0, y>0   
El conjunto factible S definido por el sistema de restricciones aparece en la figura. Los vértices del conjunto factible S son A(0,240); B(30,120); C(120; 60) y D(300,0).



Los valores de la función objetivo C en estos vértices en la tabla que sigue
Vértice
C=6x + 8y
A (0,240)
1920
B(30,120)
1140
C(120,60)
1200
D(300,0)
1800
La tabla muestraque el mínimo de la función objetivo C=6x+8y ocurre en el vértice B(30,120) y tiene un valor de 1140. Así el paciente debe adquirir 30 píldoras de la marca A y 120 de la marca B, con un costo mínimo de $11,40. 


Método Simplex

Ejercicio
Resolver mediante el método simplex el siguiente problema:
Maximizar
Z = f(x,y) = 3x + 2y
sujeto a:
2x + y ≤ 18
 
2x + 3y ≤ 42
 
3x + y ≤ 24
 
x ≥0 , y ≥ 0
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + r = 18
2x + 3y + s = 42
3x +y + t = 24
2. Igualar la función objetivo a cero
- 3x - 2y + Z = 0
3. Escribir la tabla inicialsimplex
En las columnas aparecerán todas las variables básicas del problema y las variables de holgura/exceso. En las filas se observan, para cada restricción las variables de holgura con sus coeficientes de las igualdades obtenidas, y la última fila con los los valores resultantes de sustituir el valor de cada variable en la función objetivo, y de operar tal como se explicó en la teoría para obtenerel resto de valores de la fila:
Tabla I . Iteración nº 1
 
 
 
3
2
0
0
0
Base
Cb
P0
P1
P2
P3
P4
P5
P3
0
18
2
1
1
0
0
P4
0
42
2
3
0
1
0
P5
0
24
3
1
0
0
1
Z
 
0
-3
-2
0
0
0
4. Condición de parada
Cuando en la fila Z no existe ningún valor negativo, se ha alcanzado la solución óptima del problema. En tal caso, se ha llegado al final del algoritmo.De no ser así, se ejecutan los siguientes pasos.
5. Condición de entrada y salida de la base
A. Primero debemos saber la variable que entra en la base. Para ello escogemos la columna de aquel valor que en la fila Z sea el menor de los negativos. En este caso sería la variable x (P1) de coeficiente - 3.

 Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de...