46
CAPITULO III
PROGRAMACION LINEAL
PLANTEAMIENTO DE PROBLEMAS
Introducción.
La programación lineal es una parte de la programación matemática que tal y como su nombre lo
indica, maneja ecuaciones lineales, es decir, aquellas donde todas las variables que intervienen tienen como
exponente la unidad en todos sus términos.
En este capítulo vamos a ver la manera de plantear un problema dado, expresándolo en forma
matemática.
No se procederá a su resolución, únicamente a su planteamiento, el cual consistirá en convertir una
serie de datos e información concerniente al problema en ecuaciones matemáticas.
Definiciones.
Para facilitar la comprensión de la terminología usada, a continuación daremos algunas definiciones
útiles:
Función Objetivo.- Esta es una variable, normalmente simbolizada por la letra Z, la cual representa
aquello que se desea optimizar, por ejemplo, un costo que se pretende minimizar, o bien, una utilidad que
se busca maximizar.
Variables del Problema.- Son aquellas variables que no se conocen y que al momento de resolver el
problema, deberán quedar definidas de tal manera que logren la optimización de la función objetivo. A
estas variables también se les conoce como variables de decisión.
Coeficientes de la función objetivo.- Son cantidades constantes que aparecen en la ecuación de la función
objetivo multiplicando a las variables del problema.
Restricciones.- Son las limitaciones físicas o condiciones que debe cumplir el problema, por ejemplo,
cantidad disponible de materiales, tiempo, mano de obra, etc. También suele llamárseles restricciones
funcionales.
Restricciones no explícitas.- Son aquellas condiciones ocultas en el problema, las cuales no aparecen en la
información disponible, pero que deben de ser tomadas en cuenta tanto en el planteamiento como en la
resolución del mismo. Los ejemplos más frecuentes de este tipo de restricciones es la no negatividad de las
variables del problema o el que éstas deban ser números enteros.
Metodología.
Para plantear un problema pueden aplicarse los siguientes pasos:
Paso 1.- Definir las variables del problema. Este paso consiste en identificar dichas variables y
denotarlas por letras.
Paso 2.- Definir la función objetivo. Esto será identificar aquella variable a ser optimizada, la cual
representaremos como Z y expresar su ecuación matemática en función de las variables del problema y sus
coeficientes. En este paso deberá además establecerse si la optimización es una maximización o una
minimización.
Paso 3.- Definir las restricciones. Esto será el establecer una ecuación para cada restricción en función
de las variables del problema. Es frecuente que las ecuaciones de las restricciones sean desigualdades del
tipo mayor o igual que (>) y/o menor o igual que(<).
Es conveniente señalar aquí que no todas las variables del problema pueden aparecer en cada
restricción, esto dependerá del tipo particular de problema del que se trate.
Paso 4.- Definir las restricciones no explícitas. Consiste en identificar y expresar dichas restricciones en
el planteamiento del problema.
47
A continuación presentaremos varios ejemplos resueltos:
Ejemplo III.1.- Un expendio naturista prepara sus alimentos que vende al público basándose en 3
materias primas cuyos contenidos se presentan en la siguiente tabla:
Materia prima Costo, N$/kg % Azúcares % Grasas % Proteínas % Inertes
A 2.35 12 10 60 18
B 2.00 10 10 50 30
C 1.70 8 6 44 42
¿Cuánto deberán mezclar de cada una de las 3, si se desea minimizar el costo de preparar un kg de
alimento cuyo contenido de azúcar no sea menor al 10%, su contenido de grasa no mayor del 9.5% y su
contenido de proteínas no menor de 52%?
Solución: De acuerdo a la metodología descrita anteriormente, iremos al primer paso, es decir definir
las variables del problema.
Estas variables serán los contenidos necesarios de cada una de las 3 materias primas, las cuales
definiremos de la siguiente manera:
X1 = Fracción de kilogramo de la materia prima A
X2 = Fracción de kilogramo de la materia prima B
X3 = Fracción de kilogramo de la materia prima C
Con esto queda satisfecho el paso 1.
Prosiguiendo con el paso 2, definiremos la función objetivo Z que será el costo de un kg de alimento, el
cual deberá minimizarse y cuya ecuación en función de las variables X 1, X2, X3 será:
Min Z = 2.35 X1 + 2.00 X2 + 1.70 X3
Aquí los coeficientes de las variables son los costos unitarios de cada materia prima.
Al continuar con la metodología y de acuerdo al paso 3, hay limitaciones en cuanto al contenido de
azúcares, grasas y proteínas, por lo que habrá una restricción por cada limitante, éstas serán:
Contenido de Azúcares: 12 X1 + 10 X2 + 8 X3 > 10.0
Contenido de Grasas: 10 X1 + 10 X2 + 6 X3 < 9.5
Contenido de Proteínas: 60 X1 + 50 X2 + 44 X3 > 52.0
Además habrá una condición adicional, en cuanto a la sumatoria de las 3 variables X 1, X2 y X3 la cual
deberá ser la unidad, es decir:
X1 + X2 + X3 = 1
Finalmente al ir al paso 4, la única restricción no explícita será que las variables X 1, X2 y X3 deberán
ser no negativas, pues no tendría ningún sentido físico hablar de alguna X negativa, esto es:
X1, X2, X3, No negativas
Al agrupar las ecuaciones, dejaremos planteado el problema, el cual será:
Min Z = 2.35 X1 + 2.00 X2 + 1.70 X3
sujeta a las restricciones:
12 X1 + 10 X2 + 8 X3 > 10.0
10 X1 + 10 X2 + 6 X3 < 9.5
60 X1 + 50 X2 + 44X3 > 52.0
X1 + X 2 + X 3 = 1
Con X1, X2, X3, No negativas
Presentaremos otro ejemplo:
Ejemplo III.2.- Una fábrica de calzado dispone de 45 unidades de piel y 20 horas de tiempo para producir
2 tipos de bota, de las cuales el primer tipo requiere 6 unidades de piel y 2.5 hrs., vendiéndose a N$
140/par; mientras que el segundo tipo necesita 5 unidades de piel y 2 hrs., vendiéndose a N$ 115/par.
¿Cuántos pares de botas de cada tipo deberán fabricarse de forma que se maximicen los ingresos?.
48
Solución: Lo primero será definir las variables del problema, las cuales serán las cantidades a producir
de cada tipo de bota, es decir:
X1 = Cantidad a producir del primer tipo de bota, número de pares.
X2 = Cantidad a producir del segundo tipo de bota, número de pares.
Lo siguiente es definir la función objetivo Z, la cual será el ingreso por la venta de los 2 tipos de botas,
el que deberá maximizarse y cuya ecuación en función de las variables vendrá dada por:
Max Z = 140 X1 + 115 X2
Donde los coeficientes de las variables son los precios de venta de cada tipo de bota.
Ahora procederemos a definir las restricciones, las cuales serán dos en este caso, una para la cantidad
de piel y otra para el tiempo disponible, entonces tendremos:
Unidades de Piel : 6 X1 + 5 X2 < 45
Tiempo disponible hrs: 2.5 X1 + 2 X2 < 20
Aquí las 2 restricciones son del tipo menor o igual que ( < ) debido a que tanto las unidades de piel
como el tiempo disponible en horas tienen un máximo posible en 45 unidades y 20 horas respectivamente.
Finalmente definiremos las restricciones no explícitas las cuales son:
X1, X2, Enteras y No negativas
Las variables deben ser enteras ya que no tendría sentido hablar de una fracción de un par de botas, por
decir 0.33 pares de botas. La no negatividad de las variables es también obvia dado que tampoco habría
sentido al hablar de un número negativo de pares de botas.
Por lo tanto el planteamiento completo del problema quedará de la siguiente forma:
Max Z = 140 X1 + 115 X2
sujeta a las restricciones:
6 X1 + 5 X2 < 45
2.5 X1 + 2 X2 < 20
Con X1 y X2, Enteras y No negativas.
A continuación presentaremos otro ejemplo:
Ejemplo III.3.- La empresa Agropec está buscando producir un alimento para ganado a un costo mínimo.
Para esto cuenta con 3 productos como materias primas los cuales tienen las siguientes características:
Materia prima Costo, N$/kg % Vitaminas % Minerales % Proteínas
A1 4.50 12 30 18
A2 3.70 10 30 15
A3 3.00 8 25 15
¿Cómo deberá mezclar estas 3 materias primas para preparar 1 kilogramo del producto si éste deberá
contener por lo menos 11% de vitaminas, 28% de minerales y 17% de proteínas?
Solución: Primeramente definiremos las variables del problema, las cuales son para este caso las
cantidades de las materias primas A1, A2 y A3 a mezclar para preparar 1 kilogramo del producto, es decir:
X1 = Cantidad de la materia prima A1
X2 = Cantidad de la materia prima A2
X3 = Cantidad de la materia prima A3
Ahora definiremos la función objetivo Z, la cual será el costo de 1 kilogramo del producto, el cual
deberá ser minimizado, entonces:
Min Z = 4.50 X1 + 3.70 X2 + 3.00 X3
Siendo los costos unitarios de las materias primas los coeficientes de las variables.
El siguiente paso es definir las restricciones, de las cuales se tendrá una para el contenido mínimo de
vitaminas, otra para el de minerales y otra para el de proteínas, además de que la suma de las variables
debe ser la unidad (1 kilogramo), entonces tendremos:
Contenido de Vitaminas: 12 X1 + 10 X2 + 8 X3 > 11
49
Contenido de Minerales: 30 X1 + 30 X2 + 25 X3 > 28
Contenido de Proteínas: 18 X1 + 15 X2 + 15 X3 > 17
Sumatoria de las Variables: X1 + X2 + X3 = 1
Finalmente las restricciones no explícitas; las cuales en este caso únicamente son la no negatividad de
las variables.
Entonces al planteamiento completo del problema es:
Min Z = 4.50 X1 + 3.70 X2 + 3.00 X3
Sujeta a las restricciones:
12 X1 + 10 X2 + 8 X3 > 11
30 X1 + 30 X2 + 25 X3 > 28
18 X1 + 15 X2 + 15 X3 > 17
X1 + X2 + X3 = 1
Siendo X1, X2, X3, No negativas.
Ejemplo III.4.- Una fábrica de jabones está buscando un programa de producción que maximice sus
ingresos.
Tiene la opción de elaborar 3 diferentes tipos de jabones, los cuales requieren de horas-máquina, ácido
graso y sosa cáustica en las siguientes cantidades:
Tipo de jabón Precio, N$/u Horas-Máquina Acido Graso, grs Sosa Cáustica, grs
1 5.18 18 418 32
2 4.37 14 350 24
3 3.29 10 310 20
Si la fábrica dispone de 5000 horas-máquina, de 120 kilogramos de ácido graso y de 10 kilogramos de
sosa cáustica. ¿Cuántos jabones deberá producir de cada tipo?
Solución: En este caso las variables serán las unidades de cada tipo de jabón a ser producidas, o sea:
X1 = Unidades a producir del primer tipo de jabón.
X2 = Unidades a producir del segundo tipo de jabón.
X3 = Unidades a producir del tercer tipo de jabón.
Por su parte la función objetivo Z será el ingreso, el cual vendrá dado por:
Max Z = 5.18 X1 + 4.37 X2 + 3.29 X3
Siendo los precios unitarios los coeficientes de las variables.
Las restricciones serán las disponibilidades de Horas-Máquina, Acido Graso y Sosa Cáustica, es decir:
Horas Máquina: 18 X1 + 14 X2 + 10 X3 < 5,000
Acido Graso, grs: 418 X1 + 350 X2 + 310 X3 < 120,000
Sosa Cáustica, grs: 32 X1 + 24 X2 + 20 X3 < 10,000
Siendo X1, X2, X3, Enteras y No negativas.
Ejemplo III.5.- El dueño de un camión de 10 toneladas de capacidad de carga está planteándose la
pregunta de cómo cargar el camión de tal forma que se obtenga el máximo ingreso. En la siguiente tabla se
presentan las diferentes cargas posibles y el ingreso por concepto de flete que generarían:
Material Peso, kgs Ingreso, N$
Naranjas 2500 220
Pepinos 1800 170
Melones 2100 210
Sandías 1850 170
Nueces 1650 210
50
Zanahorias 2100 200
¿Cuál sería la manera de cargar el camión? Cabe aclarar que no puede llevarse algún material en
fracciones, es decir que se acarrea todo el material o nada del mismo.
Solución: Aquí las variables del problema serán una para cada tipo de material, entonces:
X1 = Variable de probabilidad de acarrear naranjas
X2 = Variable de probabilidad de acarrear pepinos
X3 = Variable de probabilidad de acarrear melones
X4 = Variable de probabilidad de acarrear sandías
X5 = Variable de probabilidad de acarrear nueces
X6 = Variable de probabilidad de acarrear zanahorias
La función objetivo Z la cual deberá maximizarse, será el ingreso total por el flete, el cual vendrá dado
por:
Max Z = 220 X1 + 170 X2 + 210 X3 + 170 X4 + 210 X5 + 200 X6
Las restricciones serán una para el peso total cargado al camión, es decir:
2500 X1 + 1800 X2 + 2100 X3 + 1850 X4 + 1650 X5 + 2100 X6 < 10,000
la cual es del tipo menor o igual que (<), dado que el camión no puede ser sobrecargado arriba de su
capacidad.
Además cada variable podrá tener un par de valores posibles: Ser cero o la unidad si se transporta de
ese tipo de material o no, esto lo ponemos para las restricciones en la forma siguiente:
X1 < 1
X2 < 1
X3 < 1
X4 < 1
X5 < 1
X6 < 1
con X1, X2 , X3 , X4, X5, X6, Enteras
En cuanto a las restricciones no explícitas, éstas implican la no negatividad de las variables y que éstas
deberán ser cero o la unidad.
De esta manera el planteamiento completo del problema quedará en la siguiente forma:
Max Z = 220 X1 + 170 X2 + 210 X3 + 170 X4 + 210 X5 + 200 X6
Sujeta a las restricciones:
2500 X1 + 1800 X2 + 2100 X3 + 1850 X4 + 1650 X5 + 2100 X6 < 10,000
X1 < 1
X2 < 1
X3 < 1
X4 < 1
X5 < 1
X6 < 1
Con las variables X1, X2, X3, X4, X5, X6, Enteras y No negativas.
51
PROBLEMAS PROPUESTOS.
III.1.- Un restaurante busca optimizar sus ingresos por la venta de postres, puede disponer de 4
diferentes tipos: natillas, gelatina, budín y dulce, los cuales requieren de azúcar y leche condensada en las
cantidades que se señalan en la siguiente tabla:
Postre Azúcar, grs Leche, mls Precio, N$/u
Natilla 60 120 3.50
Gelatina 70 135 3.60
Budín 90 170 4.00
Dulce 120 200 4.60
Si el restaurante dispone de una entrega de 10 kgs. de azúcar y 18 litros de leche condensada, ¿Cuánto
deberá preparar de cada tipo de postre?
III.2.- Una clínica de dietas busca minimizar sus costos al preparar un alimento balanceado. Para esto
cuenta con 3 productos como materias primas, los cuales tienen las siguientes especificaciones:
Materia Prima % Grasas % Azúcares Costo, N$/kg
1 20 17 3.00
2 18 15 3.30
3 15 15 3.50
Si el alimento balanceado debe contener como máximo 18.5 % de grasas y 16 % de azúcares. ¿Cómo
deberá mezclar la clínica sus materias primas para satisfacer esas condiciones a un costo mínimo?
III.3.- Un taller de herrería busca mejorar sus utilidades fabricando 2 tipos diferentes de puertas. El
taller cuenta con 150 kilogramos de fierro y 70 horas de tiempo disponible. La puerta tipo número 1
requiere de 10 kilogramos de fierro y 6 horas de tiempo dando una utilidad de N$ 180, mientras que el
segundo tipo necesita de 12 kilogramos de fierro y 7 horas de tiempo, con una utilidad de N$ 200.
¿Cuántas puertas de cada tipo deberá fabricar el taller de manera que maximice sus utilidades?
III.4.- La fábrica Química de Rioverde busca satisfacer las leyes ecológicas, para lo cual le han ofrecido
2 diferentes tipos de equipo anticontaminante. El primer equipo le proporciona un 70% de control y su
costo es de N$ 7,500.00, mientras que el segundo equipo le proporciona 80% de control y cuesta N$
8,500.00.
Si la empresa necesita instalar un total de 4 equipos anticontaminantes con un 75% de control global,
¿Cuántos equipos de cada tipo deberá adquirir, de modo que el costo de compra sea mínimo?
III.5.- Una carpintería cuenta con 100 metros cúbicos de madera y 40 horas de tiempo libre. Busca
fabricar 3 tipos diferentes de sillas, las cuales pueden venderse aceptablemente en el mercado, cada tipo
tiene los siguientes requerimientos y precios de venta:
Tipo de Silla Madera, m3 Tiempo, horas Precio, N$/u
1 2.5 1.20 15.20
2 2.0 1.00 13.00
3 2.2 1.05 13.50
¿Cuántas sillas de cada tipo deberá fabricar, de modo que pueda maximizar sus ingresos?
52
III.6.- Una fábrica de quesos debe elaborar éstos con un contenido de grasas no mayor del 20%, para lo
cual puede adquirir 2 tipos diferentes de leche: El primer tipo tiene un 25% de grasas y cuesta N$
1.20/litro, mientras que el segundo tipo contiene 16% de grasas y su costo es de N$ 1.70/litro. ¿Cómo
deberá mezclar estas leches para preparar queso a un costo mínimo?
III.7.- Un supermercado puede poner en sus estantes 3 nuevos productos, los cuales le ocuparían 3, 4 y
5 estantes respectivamente, y le proporcionarían 6, 7 y 8.5 N$ de ingresos adicionales respectivamente. Si
el supermercado cuenta con 80 estantes para colocar estos productos, ¿Cuántos productos de cada tipo
deberá colocar de tal modo que maximice sus ingresos adicionales?
III.8.- Un proveedor de materiales de construcción desea preparar grava que contenga por lo menos el
65% de material de 1/2", para esto cuenta con 3 tipos de materias primas, las cuales contienen 80, 60 y
58% de material de 1/2", con un costo de 10, 7 y 6.50 N$/tonelada respectivamente.
¿Cómo deberá mezclar estas 3 materias primas para preparar una tonelada de grava a un costo mínimo?
III.9.- Un constructor cuenta con 3 tipos diferentes de albañiles: MB, R y P los cuales pueden colocar
400, 300 y 250 ladrillos diarios devengando salarios de 35, 28 y 20 N$/día, respectivamente. Si el
constructor necesita colocar 3000 ladrillos diarios y cuenta con 4 albañiles tipo MB, 6 del tipo R y 8 del P.
¿Cómo asignaría 10 albañiles para colocar los 3000 ladrillos a un costo salarial mínimo?
III.10.- Una radiodifusora cuenta con 2 horas de tiempo libre para poder programar comerciales. Hay 3
tipos diferentes de comerciales, los cuales tomarían 2, 1.7 y 1.5 minutos cada uno, generando un ingreso de
18, 15 y 13 N$ respectivamente. ¿Cuántos comerciales de cada tipo deberá programar de manera que sus
ingresos por este concepto se maximicen?
