SESIN 2.

INTRODUCCIN A LA PROGRAMACION LINEAL

Objetivos:
Al finalizar la sesin el alumno podr diferenciar los elementos de un modelo de programacin
lineal y formular dichos modelos a partir de la descripcin de un problema.
La programacin lineal utiliza un modelo matemtico para describir el problema. El adjetivo
lineal significa que todas las funciones matemticas del modelo deben ser funciones lineales. En
este caso, la palabra programacin no se refiere aqu a trminos computacionales; en esencia es
sinnimo de planeacin. Por lo tanto, la programacin lineal involucra la planeacin de las
actividades para obtener un resultado ptimo; esto es, el resultado que mejor alcance la meta
especificada de acuerdo con el modelo matemtico entre todas las alternativas factibles
(Hillier y Lieberman 2006).
Elementos de un modelo de programacin lineal
Podemos definir a:
Z = valor de la medida global de efectividad.
xj = nivel de la actividad j (para j = 1, 2,, n).
cj = incremento en Z que se obtiene al aumentar una unidad en el nivel de la actividad j.
bi = cantidad de recurso i disponible para asignar a las actividades (para i = 1, 2,,m).
aij = cantidad del recurso i consumido por cada unidad de la actividad j.
En forma general, un problema de programacin lineal (PL), es tratar de encontrar los valores x1,
x2, ,xn, que maximizan la funcin objetivo (FO) relacin lineal entre estas.
Maximizar
Z = c1x1 + c2x2 + + cnxn

FO

Sujeta a las restricciones

a11x1 + a12x2 + a1nxn b1
a21x1 + a22x2 + a2nxn b2
am1x1 + am2x2 + amnxn bm

Restricciones

y
x1 0, x2 0, xn 0.

Condicin de
no negatividad

Otras formas

Minimizar en lugar de maximizar la funcin objetivo.

| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

-8-

Restricciones con desigualdad en sentido mayor o igual

Restricciones en forma de ecuacin
Variables de decisin sin la restriccin de no negatividad

Ejercicios sugeridos
1.1.
Una fbrica ha descontinuado la produccin de una lnea de productos no rentables.
Esto ha creado un considerable exceso de capacidad de produccin. La Gerencia est
considerando utilizar este exceso de capacidad para fabricar uno o ms productos de los tres
productos llamados producto 1, producto 2 y producto 3. La capacidad disponible en las
mquinas que podran limitar la produccin es la siguiente:
Mquina
Mquina 1
Mquina 2
Mquina 3

Tiempo Disponible (Horas/semana)

150
100
50

El nmero de horas-mquina requerido por unidad de producto es la siguiente:

Mquina

Producto 1

Producto 2

Producto 3

Mquina 1
Mquina 2
Mquina 3

8
4
2

2
3
-

3
1

El Departamento de Ventas indica que las ventas potenciales para los productos 1 y 2 son
superiores a la mxima produccin obtenible y que el potencial de ventas para el producto 3 es
de 20 unidades por semana.
Las utilidades unitarias seran de $20.00, $6.00 y $8.00 para los productos 1, 2 y 3
respectivamente.
Formule el modelo de programacin lineal para determinar cuantas unidades de cada artculo
debe producir la firma, a fin de maximizar sus beneficios.
1.2.
Uno de los problemas tpicos de la programacin lineal es el problema de la dieta. El
objetivo es determinar las cantidades de ciertos alimentos que deben ser ingeridos para
satisfacer ciertos requerimientos nutricionales a un costo mnimo. Suponga que solo se
considera la leche, la carne y los huevos y las vitaminas A, C y D. Asuma que la cantidad de
miligramos de cada una de estas vitaminas, contenida en una unidad de cada alimento es la
siguiente:

| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

-9-

Vitamina

Botella de leche

Libra de carne

Docena de huevos

A
C
D
Costo

1 mg
10 mg
10 mg
$1.00

1 mg
10 mg
100 mg
$1.10

10 mg
10 mg
10 mg
$0.50

Requerimientos
mnimos diarios
1 mg
50 mg
10 mg

Formule el modelo de Programacin Lineal para este problema.

1.3.
Un manufacturero produce una lnea de productos para el hogar fabricados de lmina de
metal. Para ilustrar su problema de planificacin de la produccin, suponga que fabrica
nicamente cuatro productos y que su sistema de produccin consiste de cinco centros de
produccin: trazado, troquelado, ensamble, acabado (impresin y pintura) y empaque. Para un
determinado mes, se desea decidir que cantidad de cada producto debe ser
manufacturado y para auxiliarse en esta decisin se han obtenido los datos mostrados en las
tablas que se muestran. Por otro lado, se conoce que solamente se tendr disponible 2,000 pies2
de lmina de metal para ser utilizados en la fabricacin de los productos 2 y 4 durante el mes. El
producto 2 requiere de 2.0 pies2 por unidad y el producto 4 requiere 1.2 pies2 por unidad.
Formule este problema como un problema de programacin lineal, a fin de maximizar la
contribucin del beneficio total.
Departamento
Trazado
Troquelado
Ensamble
Acabado
Empaque

Producto
1
2
3
4

Tasas de produccin en horas por unidad

Producto 1
Producto 2
Producto 3
Producto 4
0.03
0.15
0.05
0.10
0.06
0.12
0.10
0.05
0.10
0.05
0.12
0.04
0.20
0.03
0.12
0.02
0.06
0.02
0.05

Precio Neto de
Venta / Unidad
$10.00
$25.00
$16.00
$20.00

Costo Variable
por Unidad
$6.00
$15.00
$11.00
$14.00

Horas prod.
Disponibles
400
400
500
450
400

Potencial de Ventas
Mnimo
Mximo
1 ,000
6,000
500
500
3,000
100
1,000

1.4.
El Departamento de publicidad de Almacenes Hawai y Cia (AHC) tiene que planear para
el prximo mes una estrategia de publicidad para el lanzamiento de una nueva lnea de
televisores a color. La meta de la AHC es llegar al menos al 40% de las familias de ingresos
medios. Para esto, tiene en consideracin dos medios diferentes: a Anunciarse en la cadena de
TV Honolulu - TV a Anunciarse en el peridico Honolulu - Times.
| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

- 10 -

La publicidad por TV. llega al 2% de las familias de ingresos altos y al 3% de las familias de
ingresos medios (por comercial).
La publicidad en el peridico llega al 3% de las familias de ingresos altos y al 6% de las familias
de ingresos medios (por anuncio).
La publicidad en el peridico tiene un costo de $500.00 por anuncio y la publicidad por TV tiene
un costo de; $2,000.00 por comercial. La meta de la AAHC es obtener al menos una
presentacin como mnimo al 36% de las familias de ingresos altos y al 60% de las
Familias de ingresos medios, minimizando los costos de publicidad.
Asumiendo que una persona que est considerando el anuncio y el comercial como una
exposicin doble (una exposicin mayor que el 100% es posible) construya un modelo de
Programacin Lineal para el problema de la AHC:
1.5.
Un gerente de personal debe elaborar un programa de vigilancia para la empresa, de
modo que satisfaga los requerimientos de vigilantes que se muestran en la siguiente tabla.
Requerimientos de Vigilantes
HORARIO DE COBERTURA
MNIMO DE VIGILANTES
Medianoche 4:00 a.m.
5
4:00 a. m. - 8:00 a.m.
7
8:00 a.m. - 12:00m.
15
12:00m - 4:00 p.m.
7
4:00 p.m. - 8:00 p.m.
12
8:00 p.m. -medianoche
9
Los guardias de seguridad trabajan tumos de 8 horas; y todos los das hay 6 tumos, en la
siguiente tabla se dan los horarios de entrada y salida de cada turno.

Turno
1
2
3
4
5
6

Hora ros de entrada y salida

Hora Entrada
Hora Salida
Medianoche
8:00 a.m.
4:00 a.m.
Medioda
8:00 a.m.
4:00 p.m.
Medioda
8:00 p.m.
4:00 p.m.
Medianoche
8:00 p.m.
4:00 a.m.

El gerente de personal quiere determinar cuantos guardias debern trabajar en cada tumo, con el
objetivo de minimizar el # total de guardias que satisfagan los requerimientos de vigilancia.
Formule el modelo de programacin lineal.

| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

- 11 -

1.6.
Considere el problema de asignar cuatro diferentes combinaciones de trenes a cinco
rutas que son cubiertas por los mismos, cada combinacin difiere en el hecho de tener diferente
capacidad de cada vagn y la posibilidad de tener diferente numero de vagones, el cuadro
siguiente muestra la informacin de cada combinacin.
Tipo de
tren
1
2
3
4

Capacidad por
vagn
20
25
30
35

N de viajes por ruta

N de vagones
N de
por maquina
maquinas
1
2
3
4
5
8
3
1
4
2
6
6
2
3
2
2
4
4
4
2
2
4
4
2
1
5
3
3
Nmero de pasajeros demandantes 1500 2000 2200 3000

Los costos asociados a la operacin ms el costo de atencin de cada cliente se muestra a

continuacin:
Costo operativo de cada ruta ($)
1
2
3
4
1
800
900
1000
1200
2
700
800
900
1000
3
500
1000
1100
1200
4
1200
1100
900
700
Costo atencin por cliente
40
50
45
60
Tipo de tren

Formule el problema de programacin lineal para determinar la asignacin de las combinaciones

de trenes de diferentes rutas, de tal manera que se minimice el costo total.
1.7.
La planeacin global de la Conferencia de Kibbutzim se hace en su oficina de
coordinacin tcnica. Actualmente se esta planeando la produccin agrcola para el prximo ao.
La produccin esta limitada tanto por la cantidad de terreno disponible para regado como por la
cantidad de agua que la Comisin de Aguas asigne para regarlo, las tablas siguientes muestran
estos datos:
Kibbutz
1
2
3
Cosecha
Remolacha
Algodn
Sorgo

Terreno para
uso (acres)
400
600
300

Cantidad mxima
(acres)
600
500
325

Asignacin de
agua (pies3 acre)
600
800
375

Consumo de agua
(pies3-acre/acre)
3
2
1

Rendimiento Neto
($/Acre)
400
300
100

| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

- 12 -

El tipo de cosecha apropiada para la regin incluye remolacha, algodn y sorgo, que son las que
se estn considerando ao. Las cosechas difieren primordialmente por su rendimiento esperado
por acre y e su consumo de agua. Adems, el Ministerio de Agricultura ha establecido una
cantidad mxima de acres que la conferencia puede dedicar a esas cosechas.
Los tres Kibbutz que pertenecen a la conferencia estn de acuerdo en que cada uno de ellos
sembrara la misma proporcin de sus tierras regables disponibles. Cualquier combinacin de
estas cosechas se puede sembrar en cualquier de los Kibbuts.
El trabajo al que se enfrenta la oficina de coordinacin tcnica consiste en planear cuantos deben
ser asignadas para cada tipo de cosecha en cada Kibbuts, cumpliendo con las restricciones dadas.
El objetivo es maximizar el rendimiento neto total para la Confederacin Sur.
1.8.
Considere el problema de asignar tres diferentes tipos (tamao) de aeroplano a cuatro
rutas. La siguiente tabla de el mximo de capacidad (en numero de pasajeros) y el numero de
aeroplanos disponibles de cada tipo, el nmero de viajes diarios que cada aeroplano puede hacer
en una ruta dada, y el numero diario de pasajeros esperados para cada ruta.
Tipo de
aeroplano
1
2
3

Capacidad
(Pasajeros)

Numero de
aeroplanos

50
5
30
8
20
10
Numero diario de clientes

Numero de viajes en la
ruta
1
2
3
4
3
2
2
1
4
3
3
2
5
5
4
2
100 200 90 120

Los costos de operacin por viaje en las diferentes rutas, junto con la utilidad prdida
(penalidad) por no servir a un cliente se resume abajo.
Tipo de
aeroplano
1
2
3
Utilidad perdida
por cliente

Costo de operacin por viaje ($)

1
1000
800
600

2
1100
900
800

3
1200
1000
800

4
1500
1000
900

40

50

45

70

Formule el modelo de programacin lineal para determinar la asignacin de los aeroplanos a las
rutas que minimizaran el costo total del sistema.
1.9.
Un hombre de negocios tiene la opcin de invertir su dinero en dos planes. El plan A
garantiza que cada dlar invertido ganar $0.70 en el plazo de un ao, mientras que el plan B
| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

- 13 -

garantiza que cada dlar invertido ganar $2.00 al cabo de dos aos. En el plan B solo se
permiten inversiones para periodos que son mltiplos de dos aos. Cmo invertira
$100,000.00 a fin de maximizar la ganancia al final de tres aos? Formule este problema como
un modelo de programacin lineal.
1.10. Un avin de carga tiene tres compartimentos para almacenar; delantero, central y
trasero. Estos compartimentos tienen un lmite de capacidad tanto en peso como en espacio. Los
datos se resumen a continuacin:
Compartimiento
Delantero
Central
Trasero

Capacidad de peso
(toneladas)
12
18
10

Capacidad de espacio
(pies cbicos)
7000
9000
5000

Para mantener el avin balanceado, el peso de la carga en los respectivos compartimientos debe
ser proporcional a su capacidad. Si tienen ofertas para los siguientes envos en un vuelo prximo
ya que se cuenta con espacio:
Carga Peso (toneladas)
1
20
2
16
3
25
4
13

Volumen (peso cbico/tonelada)

500
700
600
400

Ganancia ($/tonelada)
320
400
360
290

Se puede aceptar cualquier fraccin de esas cargas. El objetivo es determinar que cantidad de
cada carga debe aceptarse (si se acepta) y como distribuirla en los compartimentos para
maximizar la ganancia del vuelo.
1.11. Suponga que una refinera desea mezclar (suponer que no hay perdidas) 4 componentes
para obtener tres grados de gasolina A, B y C. El problema es determinar la mezcla de los cuatro
componentes que maximice el beneficio.
La disponibilidad y el costo de los cuatro componentes es el siguiente:
Componente
1
2
3
4

Mxima cantidad disponible

Costo por barril
(barril/da)
3,000
$3.00
2,000
$6.00
4,000
$4.00
1,000
$5.00

| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

- 14 -

Para mantener la calidad requerida para cada grado de gasolina es necesario especificar un cierto
porcentaje mximo o mnimo de los componentes en cada mezcla. Estos son dados abajo, junto
con el precio de venta de cada grado.
Grado
A
B
C

Especificacin
No mas de 30% de 1
No menos de 40% de 2
No mas de 50% de 3
No mas de 50% de 1
No menos de 10% de 2
No mas de 70% de 1

Precio de venta por barril

$5.50
$4.50
$3.50

Asuma que todos los otros flujos son fijos as que el beneficio a ser maximizado es el ingreso
total por ventas menos el costo total de los componentes.
Formule un modelo de programacin lineal para determinar la cantidad y mezcla de cada grado
de gasolina.
1.12.
Una compaa automotriz produce automviles y camiones. Cada vehiculo tiene que
pasar por un taller de pintura y por un taller de montaje de la carrocera. Si el taller de pintura
pintara solamente camiones, se podran pintar 40 camiones al da; si pintara solamente
automviles, se podran pintar 60 automviles diariamente. Si el taller de carrocera produjera
solamente camiones, podra fabricar 50 camiones al da. Cada camin aporta $300.00 a la
utilidad y cada automvil $200.
Utilice programacin lineal para formular el siguiente problema
1.13. El Distrito Metro es una dependencia que administra la distribucin de agua en una
cierta regin geogrfica grande. La regin es bastante rida, por lo que el distrito debe comprar y
traer agua desde fuera de ella. Las fuentes de esta agua importada son los ros Colombo, Sacrn y
Calorie. El distrito revende el agua a los usuarios de la regin. Sus clientes principales son los
departamentos de aguas de las ciudades de Berdoo, Los Devils, San Go y Hollyglass. Es posible
hacer llegar agua a cualquiera de estas ciudades desde cualquiera de los tres ros, con la
excepcin de que no hay forma de abastecer a Hollyglass con agua del ro Calorie. Sin embargo,
dada la distribucin geogrfica de los acueductos y las ciudades en la regin, lo que le cuesta al
distrito el abastecimiento depende tanto de la fuente como de la ciudad a la que abastece. En la
tabla siguiente se dan los costos variables por acre pie de agua (en dlares) para cada
combinacin de ro y ciudad. A pesar de estas variaciones, el precio que el distrito cobra por acre
pie es independiente de la fuente de agua y es el mismo para todas las ciudades.
La administracin del distrito tiene que resolver el problema de cmo asignar el agua disponible
durante el prximo verano. En la columna del lado derecho de la tabla se dan las cantidades
disponibles en los tres ros, en unidades de un milln de acres pie. El distrito se compromete a
proporcionar una cantidad mnima para cumplir con las necesidades esenciales de cada ciudad
(con la excepcin de San Go que tiene una fuente independiente de agua); estas necesidades
| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

- 15 -

mnimas se muestran en el rengln correspondiente de la tabla. El rengln de pedido indica que

Los Devils no quiere ms agua que la que cubre sus necesidades mnimas, pero Berdoo comprara hasta 20 ms, San Go, hasta 30 ms y Hollyglass comprara toda la que pudiera obtener.
La administracin desea asignar toda el agua disponible de los tres ros de manera que por lo
menos se cumpla con las necesidades mnimas de cada ciudad y que se minimice el costo total.
Formule el problema.
Rio

Ciudad

Recursos

Berdoo Los Devils San Go Hollyglass

Ro Colombo

16

13

22

17

50

Ro Sacrn

14

13

19

15

60

Ro Calorie

19

20

23

50

Mn. necesario

30

70

10

Pedido

50

70

30

(en millones de acres-pie)

1.14. Guy Chung, superintendente de los edificios y del terreno circundante de la Universidad
Gtica, ha planeado aplicar fertilizante al csped del rea cuadrangular a principios de la
primavera. Ese prado necesita por lo menos las cantidades de nitrgeno, fsforo y potasio que
figuran en la siguiente tabla.
Mineral Peso mnimo (libras)
Nitrgeno
10
Fsforo
7
Potasio
5
Hay tres tipos de fertilizante comercial disponibles; los anlisis y precios por 1,000 libras se en
listan en la siguiente tabla. Guy puede comprar cualquier cantidad de cualquiera de los
fertilizantes que quiera y combinarlos antes de aplicarlos al csped. Formule un modelo de PL
que determine la cantidad de cada fertilizante que debe comprar para satisfacer los
requerimientos con un costo mnimo.
Contenido de
Contenido de
Contenido de
Fertilizante
Nitrgeno
Fsforo (libras) Potasio (libras)
(libras)
A
25
10
5
B
10
5
10
C
5
10
5
Caractersticas de los fertilizantes (por cada 1,000 libras)

Precio
($)
10
8
7

1.15. Una compaa ha sido contratada para realizar cinco trabajos. Estos trabajos se pueden
efectuar en seis de sus plantas de manufactura. Debido a la magnitud de los trabajos, no es
factible asignar ms de un trabajo a una planta particular. Asimismo, el segundo trabajo no se
| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

- 16 -

puede asignar a la tercera planta. A continuacin se dan los costos estimados, en miles de
dlares, para efectuar los trabajos en las distancias plantas
Planta
Trabajo
1
2
3
4
5

1
50
66
81
40
62

2
55
70
78
42
55

3
42
72
38
58

4
57
68
80
45
60

5
48
75
85
46
56

6
52
63
78
42
65

a) Formule el problema de asignar los trabajos a las plantas de tal forma que el costo total sea
mnimo.
Trabajos citados
Castillo, Enrique, Antonio J. Conejo, Pablo Pedregal, Ricardo Garca, y Natalia Alguacil.
Formulacin y Resolucin de Modelos de Programacin Matemtica en Ingeniera y Ciencia.
2002.
Cordova, Victor. Aplicacin de la investigacin de operaciones en problemas de salud
ocupacional. Boletin Cientifico Asociacion Chilena de Seguridad, 2000: 45-49.
Daellenbach, Hans G., John A. George, y Donald C. McNickle. Introduccin a las tecnicas de
Investigacin de Operaciones. Mexico D.F: CECSA, 1987.
Hillier, Frederick, y Gerald Lieberman. Introduccion a la Investigacion de Operaciones. Mexico
D.F: McGraw-Hill, 2006.
Rajgopal, Jayant. Principios y Aplicaciones de la Investigacin de Operaciones. En Maynard
Manual del Ingeniero Industrial. Mexico D.F: McGraw-Hill, 2005.
Winston, Wayne L. Investigacin de Operaciones. Aplicaciones y Algoritmos . Mexico D.F:
Thomson, 2005.

| SESIN 2. INTRODUCCIN A LA PROGRAMACION LINEAL

- 17 -