PROGRAMACIÓN LINEAL Como Modelo de Optimización

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 10

PROGRAMACIÓN LINEAL como modelo de optimización

El enfoque de la Investigación Operativa como construcción de modelos constituye una


herramienta que nos sirve para lograr una visión bien estructurada de la realidad. Así, el
propósito del modelo es proporcionar un medio para analizar el comportamiento de las
componentes de un sistema con el fin de optimizar su desempeño. La ventaja que tiene el
sacar un modelo que represente una situación real es que nos permite analizar tal situación sin
interferir en la operación que se realiza, ya que el modelo es como si fuera "un espejo" de lo
que ocurre.

Los modelos más importantes para la Investigación Operativa son los modelos simbólicos o
matemáticos, que emplean un conjunto de símbolos y funciones para representar las variables
de decisión y sus relaciones para describir el comportamiento del sistema. El uso de las
matemáticas para representar el modelo, el cual es una representación aproximada de la
realidad, nos permite aprovechar las computadoras de alta velocidad y técnicas de solución
con matemáticas avanzadas.

Un modelo matemático comprende principalmente tres conjuntos básicos de elementos. Estos


son: 1) variables y parámetros de decisión, 2) restricciones y 3) función objetivo.

Variables y parámetros de decisión. Las variables de decisión son las incógnitas (o decisiones)
que deben determinarse resolviendo el modelo. Los parámetros son los valores conocidos que
relacionan las variables de decisión con las restricciones y función objetivo. Los parámetros del
modelo pueden ser determinísticos o probabilísticos.

Restricciones. Para tener en cuenta las limitaciones tecnológicas, económicas y otras del
sistema, el modelo debe incluir restricciones (implícitas o explícitas) que restrinjan las variables
de decisión a un rango de valores factibles.

Función objetivo. La función objetivo define la medida de efectividad del sistema como una
función matemática de las variables de decisión.

La solución óptima será aquella que produzca el mejor valor de la función objetivo, sujeta a las
restricciones, o sea, cumpliendo con ellas.

Concepto de optimización
Una característica importante es que la Investigación Operativa y, en este caso, el modelo de
Programación Lineal, intenta encontrar la mejor solución, o la solución óptima, al problema
objeto de estudio. En lugar de contentarse con sólo mejorar el estado de las cosas, la meta es
identificar el mejor curso de acción posible. Ya mencionamos a la programación lineal como
método dentro de los procesos de decisión de certidumbre. Puede ser a través de:

a) Método gráfico (práctico, cuando actúan sólo dos variables en la función a optimizar)

b) Método analítico (llamado SIMPLEX). Este método se puede aplicar también en funciones de
2 variables, pero cobra mucha utilidad en funciones más complejas, donde el método gráfico
ya no es practicable.

En el tema 4, que nos concierne en este momento, vamos a encarar la solución gráfica de un
problema de programación lineal.

Para la solución gráfica de programas lineales con dos variables, lo que se tiene que hacer es
trazar un eje de coordenadas cartesianas, para graficar las desigualdades dadas por el
problema, después encontrar el Área de Soluciones Factibles y proceder a graficar la función
objetivo para conocer el valor óptimo (maximizar o minimizar) que será la solución del
problema.

EJEMPLO

Un fabricante está tratando de decidir sobre las cantidades de producción para dos artículos:
armarios y cajoneras. Se cuenta con 96 unidades de material y con 72 horas de mano de obra.
Cada armario requiere 12 unidades de material y 6 horas de mano de obra. Por otra parte, las
cajoneras usan 8 unidades de material cada una y requieren 12 horas de mano de obra c/u. El
margen de contribución es el mismo para los dos productos: $5.00 por unidad. El fabricante
prometió construir por lo menos dos armarios.

Paso 1: formulación del problema.

El primer paso para resolver el problema es expresarlo en términos matemáticos en el formato


general de PL. ¿Cuál es el objetivo? Es maximizar la contribución a la ganancia. Cada unidad
producida contribuirá con $5 en la ganancia. Ahora puede escribirse la función objetivo:

Maximizar Z = 5x1 + 5x2

donde: x1 = número de armarios producidos


x2 = número de cajoneras producidas
Cuáles son las restricciones o limitaciones del problema? Existen tres restricciones. Primero, el
material está limitado a 96 unidades (puede ser que el proveedor no da abasto, u otros
motivos que restringen la libertad de elección del fabricante). Cada armario se lleva 12
unidades de material y cada cajonera usa 8 unidades. La primera restricción es, entonces:
12x1 + 8x2 = 96

La segunda restricción es el total de horas de mano de obra. Un armario se lleva 6 horas, una
cajonera 12 horas y se dispone de un total de 72 horas. Así:

6x1 + 12x2 = 72

Existe una limitación más. El fabricante prometió producir por lo menos dos armarios. Esto
puede expresarse como: x1 ≥ 2

Por último, las restricciones de no negatividad son: x1 ≥ 0, x2 ≥ 0

Poniendo todo junto el modelo se tiene:

Maximizar Z = 5x1 + 5x2


Restricciones: 12x1 + 8x2 = 96
6x1 + 12x2 = 72
x1 ≥ 2
x1 ≥ 0, x2 ≥ 0

Paso 2: gráfica de las restricciones.

El siguiente paso en el método gráfico es dibujar todas las restricciones en una gráfica. Esto
puede hacerse en cualquier orden. Se trata de dibujar inecuaciones de la misma forma en que
hemos aprendido en matemática. Al dejar en un solo gráfico todas las inecuaciones formadas
por las restricciones de nuestro problema tendremos un gráfico como el siguiente:

Cualquier solución que esté en la frontera o dentro del área sombreada cumplirá con todas las
restricciones. Ahora se utilizará la función objetivo para seleccionar la solución óptima.

Paso 3: obtención de la solución óptima: líneas de indiferencia.

Para encontrar la solución óptima, se grafica la función objetivo en la misma gráfica de las
restricciones. La función objetivo en este problema es Z = 5x1 + 5x2. Como todavía no se conoce
el máximo valor factible de Z, no puede trazarse el óptimo de la función objetivo. No obstante,
es posible suponer algunos valores para Z y graficar las líneas resultantes. En la siguiente figura
se muestran las líneas para Z = 25 y Z = 50:
Las líneas de este tipo se llaman líneas de indiferencia, porque cualquier punto sobre una línea
dada da la misma ganancia total. Nótese que la distancia perpendicular del origen a la línea
aumenta al aumentar el valor de Z. También, todas las líneas de indiferencia son paralelas
entre sí. Estas propiedades gráficas pueden usarse para resolver el problema.

En la siguiente figura, se ilustran todas las restricciones y las dos líneas de indiferencia
supuestas. En la gráfica puede observarse que la línea de indiferencia para Z = 50 está
completamente fuera de la región factible. Para Z = 25, parte de la línea cae dentro de la
región factible. Por tanto, existe alguna combinación de x1 y x2 que satisface todas las
restricciones y otorga ganancias más altas que 25 y menores a 50.

Imaginando que la línea de indiferencia Z = 25 se mueve hacia la línea Z = 50, de las


propiedades de la gráfica que se hicieron notar antes, el punto óptimo estará sobre la línea de
indiferencia más lejana al origen pero que todavía toque la región factible. Esto se muestra en
la siguiente figura:
Con el punto óptimo localizado gráficamente, la única tarea que queda es encontrar las
coordenadas del punto. Nótese que el punto óptimo está en la intersección de las líneas de
restricción para materiales y horas de mano de obra. Las coordenadas de este punto se
pueden encontrar resolviendo el sistema de ecuaciones que forman estas dos restricciones
utilizando cualquiera de los métodos de solución (suma y resta, sustitución o igualación). Las
coordenadas de este punto resultan ser (6, 3), es decir, 6 armarios y 3 cajoneras. La sustitución
de este punto en la función objetivo da la ganancia máxima:

Z = 5(6) + 5(3) = $45

Como podrán apreciar, resulta indispensable repasar cómo se grafican inecuaciones y cómo se
resuelve un sistema de ecuaciones de 2x2 para llegar satisfactoriamente a resolver ejercicios
de programación lineal por el método gráfico.

Uso del método gráfico para minimización.

Consideremos un Problema de PL en el cual el objetivo es minimizar costos. La solución del


problema de minimización sigue el mismo procedimiento que la de problemas de
maximización. La única diferencia es que ahora se quiere el menor valor posible para la función
objetivo. Supóngase que se tiene el siguiente problema:

Ejemplo: Problema de dieta.

Un comprador está tratando de seleccionar la combinación más barata de dos


alimentos, que debe cumplir con ciertas necesidades diarias de vitaminas. Los requerimientos
vitamínicos son por lo menos 40 unidades de vitamina W, 50 unidades de vitamina X y 49
unidades de vitamina Y. Cada onza del alimento A proporciona 4 unidades de vitamina W, 10
unidades de vitamina X y 7 unidades de vitamina Y; cada onza del alimento B proporciona 10
unidades de W, 5 unidades de X y 7 unidades de Y. El alimento A cuesta 5 pesos/kilogramo y el
alimento B cuesta 8 pesos/kilogramo.

Paso 1: formulación del problema

La meta en este problema es encontrar la manera menos costosa para satisfacer las
necesidades vitamínicas. Las dos alternativas disponibles son los alimentos A y B.
Matemáticamente la función objetivo es:
Minimizar Z = 5A + 8B
Las restricciones son los requerimientos mínimos de las tres vitaminas. Éstas son:

4A + 10B ≥ 40 vitamina W

10A + 5B ≥ 50 vitamina X

7A + 7B ≥ 49 vitamina Y

A ≥ 0, B ≥ 0 no negatividad

Paso 2: gráfica de las restricciones.

Paso 3: localización de la solución óptima.

En la siguiente figura se muestra la frontera extrema más dos líneas de indiferencia, las de Z =
40 pesos y Z = 60 pesos. La frontera extrema está formada por los puntos a, b, c y d, puesto
que éstos son los puntos de intersección factibles más cercanos al origen.
Gráficamente, el objetivo de minimizar el valor de Z significa ajustar una línea de indiferencia
tan cerca del origen como sea posible. En la figura anterior puede observarse que existen
muchas soluciones posibles para Z = 60, pero ninguna para Z = 40. Imaginando mover la línea Z
= 60 hacia el origen, el último punto de contacto con la frontera extrema será el punto b.
Entonces, el punto b es la solución óptima.

En la figura anterior se observa que el punto b es la intersección de dos líneas:

1) 4A + 10B = 40

(2) 7A + 7B = 49

Resolviendo el sistema de ecuaciones, la solución menos costosa es 5 kilogramos de alimento


A y 2 kilogramos de alimento B. El costo total de esta combinación es:

Z = 5A + 8B = 5(5) + 8(2) = 25 + 16 = 41 pesos

Para no estar buscando gráficamente el mínimo de la función objetivo (lo que nos dio el punto
b), se puede utilizar un método de prueba y error. Pero hay que buscar la solución de cada
sistema de ecuaciones que se va formando en los puntos d, c, b y a. Luego reemplazar las
respectivas soluciones en la función objetivo y elegir la que nos da un valor menor de Z
(minimización)

Resultados de prueba y error

Punto Coordenadas Z = 5A + 8B

a A = 10, B = 0 50

b A = 5, B = 2 41

c A =3, B = 4 47

d A = 0, B = 10 80

Programación lineal

1. Optimizar las siguientes funciones, sujetas a las restricciones que se indican en


cada caso:
Z = 4 X + 3 Y (Max) Z=5X+8Y (Max) C=2X+3Y (Mín)

6 X + 16 Y  48000 6 X + 5 Y  30 -3 X + 4 Y  12

12 X + 6 Y  42000 Y 1 3 X - Y  15

9 X + 9 Y  36000 -2 X + 2 Y  6 3 X + 2 Y  24

X0;Y0 X0;Y0 X0;Y0

Z=3X+Y (Máx) Z=8X–3Y (Mín) C=2X+Y (Mín)

2X+Y 8 - X + 3 Y  21 3X+Y 3

2 X + 3 Y  12 X+Y 5 4X+3Y 6

X0;Y0 X0;Y0 X+2Y 2

X0;Y0

2. Un fabricante produce dos tipos de parrillas para asar carne, Tipo I y Tipo II.
Durante el proceso de producción las parrillas requieren del uso de dos máquinas
A y B. El número de horas que se requieren en cada una de ellas se señala en la
tabla que aparece a continuación. Si puede utilizarse cada una de las máquinas 24
horas al día, y las utilidades para la Tipo I y la Tipo II son de $4 y $6,
respectivamente, ¿qué cantidad de cada tipo se debe fabricar diariamente para
maximizar las utilidades? ¿Cuál es la utilidad máxima?

Máquina A Máquina B

Tipo I 2h 4h

Tipo II 4h 2h

3. Una dieta debe contener cuando menos 16 unidades de carbohidratos y 20


unidades de proteína. El alimento A contiene 2 unidades de carbohidratos y 4 de
proteína; el B contiene 2 unidades de carbohidratos y 1 de proteína. Si el alimento
A cuesta u$s 1.20 por unidad y B cuesta u$s 0.80 por unidad, ¿cuántas unidades
de cada alimento deben adquirirse para minimizar los costos? ¿Cuál es el costo
mínimo?
4. Un granjero va a comprar fertilizante que contiene tres ingredientes nutritivos: A, B
y C. Los requisitos mínimos semanales son de 80 unidades de A, 120 de B y 240
de C. Existen dos marcas usuales de fertilizante en el mercado. La marca I cuesta
$4 el costal, contiene 2 unidades de A, 6 de B y 4 de C. La marca II cuesta $5 el
costal y contiene 2 unidades de A, 2 de B y 12 de C. ¿Cuántos costales de cada
marca debe comprar el granjero cada semana para minimizar los costos y
satisfacer los requisitos nutritivos?

5. Una compañía extrae minerales de una reserva. El número de libras de los


minerales A y B que se pueden extraer de cada tonelada de las reservas I y II se
presentan en la tabla que aparece a continuación, junto con los costos por
toneladas de éstas. Si la compañía debe fabricar cuando menos 3000 libras de A y
2500 de B, ¿cuántas toneladas de cada reserva se deben procesar para minimizar
los costos? ¿Cuál es el costo mínimo?

Reserva I Reserva II

Mineral A 100 lb 200 lb

Mineral B 200 lb 50 lb

Costo por tonelada $50 $60

7. Una industria produce autos y ciclomotores. La siguiente tabla indica las


restricciones y los requerimientos de mano de obra, materia prima y maquinaria.
También figura en la tabla el beneficio que se obtiene al vender una unidad de
cada producto. Determinar cuántos ciclomotores y cuántos autos conviene producir
para obtener el mayor beneficio.

Autos Ciclomotores Disponibilidad

Mano de obra 5 6 15000

Materia prima 10 20 20000

Maquinaria 4 4 6000

Beneficio 3 4

8. Un chacarero tiene a sus disposición 200 hectáreas de tierra, 160 días-hombre


para cultivarlo y $1100 para invertir. Desea sembrar dos cultivos, soja y maíz. La
soja requiere 1 día-hombre por hectárea y produce un beneficio de $40 por
hectárea; el maíz requiere 4 días-hombre por hectárea y produce un beneficio de
$120 por hectárea. La soja requiere una inversión de $10 por hectárea y el maíz
requiere $20 por hectárea. Se desea saber cuántas hectáreas de cada cultivo
habrá que plantar para obtener el máximo beneficio.
9. Una fábrica de ollas pone a la venta una batería de cocina en dos presentaciones,
una económica y otra de lujo. El gasto que tendrá en materiales es de $20 para la
económica y de $80 para la de lujo. El gasto para la mano de obra es de $50 para
la económica y $80 para la de lujo. La fábrica dispone de $160000 para materiales
y $240000 para el pago del personal. Si la ganancia que arroja cada batería de
cocina económica es de $30 y la de lujo es de $60, ¿cuántas baterías de cada tipo
debe fabricar para maximizar las ganancias?

10. Una fábrica textil puede producir hasta 4800 metros de tela por día. Produce telas
de dos colores: blanca y roja. Debido a la escasez de colorante, no puede fabricar
más que 3000 metros de tela roja por día, y el mercado exige que la cantidad de
tela blanca sea a lo sumo el doble de la roja. La tela blanca deja un beneficio de
$0,50 el metro y la roja de $0,60. ¿Cuál es la cantidad que le conviene fabricar de
cada una para que la ganancia sea máxima?

También podría gustarte