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 mg

Vitamina 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 el nú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>2400

10x+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 muestra que 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 inicial simplex

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 obtener el 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 empate), entonces se se optará por aquella variable que sea básica.

La columna de la variable que entra en la base se llama columna pivote (En color verde).

B. Una vez obtenida la variable

...