Capı́tulo 2

Modelos de Programación
Lineal

2.1 Introducción

Pocas disciplinas de la matemática han tenido un desarrollo tan vertigi-

noso en sus aspectos teóricos y aplicados como la Programación Lineal. Sus
orı́genes se remontan a los problemas de la planificación económica en la
antigüa Unión Soviética, donde Kantorovich publicó un artı́culo al respecto
en 1939, que fue desenterrado y conocido en Occidente hasta 1959. Durante
la segunda guerra mundial, el ejército norteaméricano lo utilizó para resolver
problemas de la dieta y aprovisionamiento de sus tropas. Sin embargo, no
fue sino hasta 1947, cuando George Dantzig formuló el problema de progra-
mación lineal como lo conocemos actualmente, y fue el mismo Dantzig en
1952, quien éxitosamente desarrolló el método simplex para resolver dicho
problema. La importancia práctica y teórica de tal algorı́tmo fue tal que
desde entonces y hasta la fecha se le adoptó como el método que se enseñaba
en las Universidades. Sin el método simplex no es posible concebir la solución
de una gran cantidad de problemas de Programación Lineal. Después de
este año y hasta 1979, los especialistas en programación lineal se dedicaron
a diseñar versiones del método simplex para problemas particulares de pro-
gramación lineal. El éxito del método simplex sin duda alguna se debió al
nacimiento y desarrollo paralelos que tuvieron las primeras computadoras
digitales. No en balde, uno de los primeros códigos para computadora fue
para implantar el método simplex. Desde entonces, prácticamente ninguna

9
10 Programación Lineal: López M.

firma de equipos computacionales ha olvidado incluir dentro de su software

de promoción el método simplex. Tampoco es extraño que Von Neumann,
uno de los matemáticos con quién la Programación Lineal está en deuda
debido a sus contribuciones teóricas, sea también un nombre común en los
orı́genes e historia de la computación moderna. Por si esto fuera poco, el
origen e impacto de la programación lineal lo encontramos también en las
matemáticas teóricas. Entre otras cosas, puede demostrarse que el problema
de programación lineal es equivalente al de resolver un sistema de desigual-
dades lineales. Los escasos artı́culos y libros publicados al respecto antes
de 1947 fueron la causa de que la programación lineal no surgiera antes de
ese año. Después de 1947 el problema de programación lineal se formuló
como el de encontrar las soluciones básicas factibles, que geométricamente,
coinciden con los vértices del poliedro definido por las restricciones en la
forma estándar del problema de programación lineal. A partir de entonces
en la antigüa Unión Soviética hubo una avalancha de publicaciones para dar
respuesta a este problema. Estos intentos no fueron infructuosos y en 1979
el matemático soviético Kachian publicó un artı́culo en el que daba a cono-
cer el método elipsoidal, de complejidad computacional de tipo polinomial,
que teóricamente es más eficiente para resolver el problema de programación
lineal pero que en la práctica no supera al método simplex. Sin embargo, en
1983 cuando el matemático indú N. Karmarkar publicó su método proyectivo
se produjo una verdadera conmoción no sólo en el ámbito de la Programación
Lineal, sino también en el de la computación teórica y otras ramas de las
matemáticas. Su algorı́tmo es no sólo más eficiente teóricamente que los
de Dantzig y Kachian, sino también en forma práctica, por lo menos es lo
que reporta él mismo para problemas de programación lineal en gran es-
cala. Desde entonces se ha desatado una verdadera fiebre de publicaciones
en el mundo entero para cuestionar, enriquecer o competir con el método
proyectivo, dando lugar ası́ al estudio de los métodos interiores. Al cabo
de los años, lo cierto es que la Programación Lineal, con sus métodos, sus
diversos algoritmos y software asociado, ası́ como sus implicaciones teóricas,
ha llegado para ocupar un lugar en la ciencia y en la vida moderna que casi
nadie pone en duda en el mundo entero. Al respecto, el relato que hace G.
Dantzig acerca del surgimiento y desarrollo de la Programación Lineal, y del
cual está incluida una traducción en el el apéndice que se encuentra al final
de las presentes notas, debiera ser leı́do por todos aquellos que quieran tener
un panorama más completo de lo que ha sido y es la Programación Lineal.
MODELOS DE PROGRAMACION LINEAL 11

2.2 Modelos Clásicos

2.2.1 Problema de la Dieta

Una versión simplificada del problema de la dieta que Dantzig resolvió

[10] consiste en lo siguiente: Cuando una persona que come en la calle,
digamos un estudiante, desea saber cuánto es lo que debe gastar en su ali-
mentación para obtener los 2000 kcal. de energı́a, los 55 g. de proteinas
y los 800 mg. de calcio que su organismo requiere todos los dı́as (el hierro
y vitaminas que ella necesita supondremos por razones de simplicidad en
nuestro modelo, que los obtiene en pı́ldoras, aún cuando los nutriólogos
no lo considerarán lo más apropiado). Nuestro estudiante encuentra en el
mercado seis alimentos que son fuentes baratas de los nutrientes conforme a
la siguiente tabla:

alimento energı́a proteinas calcio cantidad precio

Avena 110 4 2 28g. $3.00
Pollo 205 32 12 100g. $8.00
Huevos 160 13 54 2u. $6.00
Leche entera 160 8 285 237cc. $5.00
Pastel de fresa 420 4 22 170 $7.00
Puerco con frijoles 260 14 80 260g. $10.00

El estudiante observa que existen diversas maneras de hacer su menú.

Por ejemplo, 8 raciones de puerco con frijoles cubrirı́an todas sus necesidades
nutritivas por $80 diariamente. Pero todo el mundo sabe que 2.08 Kg. dia-
riamente es demasiado puerco y demasiados frijoles, ası́ que el estudiante
toma la sabia decisión de no consumir más que dos raciones por dı́a. Otro
tanto hace con los demás alimentos: De este modo, decide consumir a lo
sumo 4 raciones diarias de avena,3 raciones de pollo, 2 raciones de huevo, 8
raciones de leche entera, y 2 raciones de pastel de fresa.

El estudiante descubre que existen otras formas en las que podrı́a hacer
su menú. Por ejemplo, adquiriendo 2 raciones de pastel de fresa y 6 de leche,
con lo cual el costo diario de su alimentación serı́a sólamente de $42. Como
buen estudiante, sus recursos no son muy abundantes y decide analizar las
distintas combinaciones posibles para ver con cuál menú obtiene el costo
12 Programación Lineal: López M.

mı́nimo. Pronto descubre que su número es demasiado grande y por lo

tanto, es una tarea demasiado complicada, razón por la cual opta por buscar
la asesorı́a de un matemático que le recomienda formular un modelo para su
problema, para lo cual le sugiere que empiece por denotar por x1 el número
de raciones de avena, x2 para el de pollo, etc. Esto significa que el número
de raciones de su deseado menú deben satisfacer.

0 ≤ x1 ≤ 4, 0 ≤ x2 ≤ 3, 0 ≤ x3 ≤ 2
0 ≤ x4 ≤ 8, 0 ≤ x5 ≤ 2, 0 ≤ x6 ≤ 2

Ahora los requerimientos de energı́a deben satisfacer las siguientes de-

sigualdades:

110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 ≥ 2000

4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 ≥ 55
2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 ≥ 800

Finalmente, el costo del menú es:

3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6

Resumiendo lo anterior, nuestro estudiante necesita un modelo del si-

guiente tipo:

min 3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6

sujeto a
110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 ≥ 2000
4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 ≥ 55
2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 ≥ 800
0 ≤ x1 ≤ 4, 0 ≤ x2 ≤ 3,
0 ≤ x3 ≤ 2, 0 ≤ x4 ≤ 8,
0 ≤ x5 ≤ 2, 0 ≤ x6 ≤ 2
(2.1)

Al cual se le conoce como el Problema de la Dieta.

MODELOS DE PROGRAMACION LINEAL 13

2.2.2 Problema de Corte de Existencias

Un fabricante de láminas metálicas produce rollos de ancho y longitud

fijos w y l, respectivamente. Un cliente solicita un enorme pedido de bi
láminas de ancho fijo w y longitudes variables li , con i = 1, . . . , m. El
fabricante tiene como propósito cubrir el pedido del cliente haciendo mı́nimo
el gasto de rollos de lámina, puesto que los pedazos de esta, para él son
desperdicios. Ası́ las cosas, piensa que dada una lámina de longitud l, existen
muchas maneras de cortarla. Cada una de estas maneras le llamaremos un
patrón de corte. El j-ésimo patrón de corte lo representaremos por el vector
aj , cuya i-ésima componente aij es un número no negativo que denota el
número de láminas de longitud lj en el patrón j-ésimo. Por ejemplo, si
tenemos láminas estándar cuya longitud es de 24 metros y las láminas que
se necesitan son de longitudes 3, 2.5, 4 y 3.5 metros, algunos de sus patrones
de corte tı́picos son:

       
2 4 0 0
       
 0   0   0   4 
a1 =   , a2 =   , a3 =   , a4 =   (2.2)
 0   3   0   2 
3 0 5 0

Observamos que el vector aj representa un patrón de corte si y sólo sı́

∑n
i aij li ≤ l y cada aij es un entero no negativo y además, el número de
patrones de corte es finito. Si xj representa el número de rollos de lámina
cortados de acuerdo al patrón j-ésimo, podemos formular nuestro problema
como sigue:
∑n
min j=1 xj

∑n
sujeto a j=1 aij xj ≥ bi
(2.3)
xj ≥ 0, (j = 1, . . . , n)
xj entero

La principal dificultad en la solución de este problema es que el número

de patrones de corte es muy grande y computacionalmente tampoco es muy
recomendable enumerar de antemano cada patrón de corte y su columna
asociada aj . Si eliminamos la restricción de integralidad en las variables xi ,
14 Programación Lineal: López M.

tendremos clasificado a nuestro problema como uno de programación lineal,

en tanto que si conservamos tal restricción, a nuestro problema lo podremos
clasificar como un problema de programación entera.

2.2.3 Problema de Mezclas

Ahora tenemos un fabricante de mezclas artificiales para endulzar ali-

mentos, quien dispone de b1 y b2 kilógramos de sacarina y dextrosa, res-
pectivamente para preparar sus nuevos productos Dulce1 y Dulce2. Cada
kilógramo de Dulce1 debe contener 0.4 kg. de dextrosa y 0.2 [Link] sacarina,
en tanto que cada kilógramo de Dulce2 deberá contener 0.3 kg. de dex-
trosa y 0.4 kg. de sacarina. La ganancia que obtiene el fabricante con cada
kilógramo de Dulce1 es de 20 centavos, mientras que por cada kilógramo de
Dulce 2 obtiene una ganancia de 30 centavos. La pregunta que se hace el
fabricante es cuáles deben ser las cantidades que debe producir de uno y otro
producto para obtener la ganancia máxima.

Solución:
Denotemos con x y y el número de kilógramos de Dulce1 y Dulce2, res-
pectivamente, que se pueden hacer. Para estas cantidades, el número de
kilógramos de dextrosa que se requieren es

.4x + .3y

De modo que tenemos que se debe cumplir la condición

.4x + .3y ≤ b1

Análogamente, para la sacarina obtenemos la condición

.2x + .4y ≤ b2

Obviamente requerimos que x ≥ 0 y y ≥ 0. La ganancia total en pesos

que se intenta maximizar es

z = 20x + 30y
MODELOS DE PROGRAMACION LINEAL 15

De este modo, hemos llegado a la formulación del problema mediante el

siguiente modelo matemático:

maximizar z = 20x + 30x

sujeto a las restricciones
.4x + .3y ≤ b1 (2.4)
.2x + .4y ≤ b2
x, y ≥ 0

2.2.4 Problema del Transporte

Otro modelo de Programación Lineal clásico es el Problema del Trans-

porte que consiste en lo siguiente: Ciertas cantidades a1 , a2 , ..., am de de-
terminados m productos se envian desde m localidades y se reciben en
b1 , b2 , ...bn cantidades en cada una de n localidades de destino. Asociados
con el envı́o de una unidad de producto del origen i al destino j hay un costo
de envı́o unitario ci . Se desea determinar las cantidades xij entre cada par
origen-destino (i = 1, . . . m, j = 1, . . . n.); cubriendo las necesidades de envı́o
de tal manera que el costo de transportacion sea mı́nimo.

Para formular este como un problema de Programacion Lineal podemos

establecer el siguiente arreglo:

x11 x12 ··· x1n a1

x21 x22 ··· x2n a2
.. .. .. .. ..
. . . . .
xm1 xm2 · · · xmn am
b1 b2 · · · bn

El i-ésimo renglón de este arreglo define la variable asociada con el i-

ésimo origen, mientras que la j-ésima columna del arreglo define las variables
asociadas con el j-ésimo destino. Es claro que en este arreglo la suma de
las variables que están en el i-ésimo renglón es ai , mientras que la suma de
las variables que están en la j-ésima columna es bj . El problema consiste en
encontrar variables no negativas xij que minimicen el costo de transportación
que es la suma ponderada
16 Programación Lineal: López M.

∑
n ∑
m
cij xij
j=1 i=1

De este modo el problema del transporte es:

∑n ∑m
min j=1 i=1 cij xij

sujeto a
∑n
j=1 xij = ai
∑m
i=1 xij = bj

xij ≥ 0, (i = 1, . . . , m., j = 1, . . . , n)

Para que los dos primeros renglones de restricciones sean consistentes, se

debe suponer que

∑
m ∑
n
ai = bj (2.5)
i=1 j=1

que equivale a suponer que la cantidad total enviada es igual a la cantidad

total recibida. El problema de transporte visto de esta manera es un pro-
blema de programación lineal en el que la matriz de las restricciones es de
tamaño (m + n) × mn y todas sus entradas son únicamente ceros y unos. La
forma de la matriz de transporte es como se ve a continuación, siendo ceros
las entradas de los espacios en blanco.
MODELOS DE PROGRAMACION LINEAL 17

x11 x12 · · · x1n x21 x22 · · · x2n · · · xm1 xm2 · · · xmn

1 1 ··· 1 0 0 ··· 0 ··· 0 0 ··· 0
0 0 ··· 0 1 1 ··· 1 ··· 0 0 ··· 0
.. .. .. ..
. . . .
0 0 ··· 0 0 0 ··· 0 ··· 1 1 ··· 1
1 0 ··· 0 1 0 ··· 0 ··· 1 0 ··· 0
0 1 ··· 0 0 1 ··· 0 ··· 0 1 ··· 0
.. .. .. ..
. . . .
0 0 ··· 1 0 0 ··· 1 ··· 0 0 ··· 1
(2.6)

2.2.5 Problema de Mezclas o Análisis de Actividad

En un aserradero de madera se cortan dos clases de tablas de los tron-

cos que recibe: unas son para construcción y otras para trabajos finos. Si
suponemos que le toma dos horas a la sierra cortar cada mil metros de tablas
para construcción y tres horas aplanar cada mil metros de este tipo de tablas.
Si suponemos que además le toma dos horas cortar cada mil metros de tablas
para trabajos finos, pero le toma cinco horas aplanar cada mil metros de este
tipo de tablas. El corte está disponible 8 horas al dı́a y el aplanado 15 ho-
ras. Si la ganancia por cada mil metros de tabla para construcción es de
N$100.00 y la ganancia por cada mil metros de tablas de pulido fino es de
N$120.00 ¿Cuántos metros de tabla de cada clase de madera debe cortarse
para obtener la mayor ganancia?

Solución: Si denotamos por x y y las cantidades de madera para trabajos

finos y para construcción, que se van a cortar al dı́a, respectivamente. Las
unidades de x y y podemos suponer que son en cientos de metros. El número
de horas requeridas para el corte diariamente es 2x + 2y. Puesto que sólo
se cuenta con 8 horas disponibles diariamente, entonces se debe cumplir la
desigualdad

2x + 2y ≤ 8
18 Programación Lineal: López M.

Análogamente, el número requerido para el aplanado es 5x + 3y y x y y

deben cumplir la desigualdad

5x + 3y ≤ 15

Naturalmente, también debemos tener

x ≥ 0, y y ≥ 0

La ganancia en nuevos pesos que se desea maximizar está dada por

z = 120x + 100y

De este modo, nuestro modelo matemático consiste en encontrar x y y

tales que

max z = 120x + 100y

sujeto a las restricciones
2x + 2y ≤ 8
(2.7)
5x + 3y ≤ 15
x≥0
y≥0
MODELOS DE PROGRAMACION LINEAL 19

2.3 Ejercicios

1. En una granja se proporcionan dietas a los pollos para engordarlos,

con una composición mı́nima de 15 unidades de una sustancia A y
18 de una sustancia B. En el mercado solo se encuentran dos clases
de compuestos: el tipo X con una composición de 2 unidades de A y
6 unidades de B, mientras que el tipo Y tiene una composición de 5
unidades de A y 3 de B. El precio del tipo X es de $150.00 y el del tipo
Y es de $200.00. ¿Qué cantidades de cada tipo se deberán comprar
con un costo total mı́nimo?

2. (Problema de Adquisión de Equipos). Un fabricante de cajas está

considerando la posibilidad de adquirir 2 tipos de máquinas plegado-
ras de cartón: Modelo A y Modelo B. El modelo A puede plegar 30
cajas por minuto y requiere de un operador, mientras que el modelo
B puede plegar 50 cajas por minuto y requiere de 2 operadores. Si
además suponemos que el fabricante debe plegar al menos 320 cajas
por minuto y no dispone más que de 12 empleados para la operación de
plegamiento. La máquina modelo A cuesta $15,000 y la máquina mo-
delo B cuesta $20,000. Cuántas máquinas de cada tipo debe adquirir
para minimizar el costo?

3. Un fabricante de muebles tiene tres plantas que necesitan semanal-

mente 600, 700 y 800 toneladas de madera. El fabricante puede com-
prar la madera de tres compañı́as madereras. Los primeros dos fabri-
cantes madereros tienen prácticamente producción ilimitada y debido a
compromisos, la tercera solo puede enviar 500 toneladas semanalmente.
El primer fabricante utiliza ferrocarril para transportar la madera y
no existe lı́mite de tonelaje para la madera que puede enviar a las
plantas muebleras. Por otro lado, los dos restantes compañı́as usan
camiones que limitan a 200 toneladas la madera que puede ser enviada
a las plantas muebleras. La siguiente tabla proporciona el costo de
transportación por tonelada de las compañı́as madereras a las plantas
muebleras:
20 Programación Lineal: López M.

Planta mueblera
Compañı́a 1 2 3
maderera
1 $200 $250 $300
2 $500 $600 $550 0
3 $450 $550 $600

4. Al inicio de perı́odo escolar una compañı́a papelera que dispone de

600 cuadernos, 500 carpetas y 400 bolı́grafos piensa lanzar ofertas
de paquetes de este material escolar: en el primer paquete pondrá
2 cuadernos, 1 carpeta y 2 bolı́grafos, en el segundo paquete pondrá 3
cuadernos, 1 carpeta y un bolı́grafo. Los precios del primer y segundo
paquete son $40.00 y $50.00, respectivamente. ¿Cuántos paquetes de
cada tipo le conviene a la compañı́a poner a la venta para obtener la
máxima ganancia?

5. Un fabricante de acero produce cuatro tipo de I vigas: Pequeñas, Me-

dianas, Grandes y Extra Grandes. Estas vigas pueden producirse en
cualquiera de tres tipos de máquinas: A,B y C. La longitud de las I
vigas que pueden ser producidas por hora en cada una de las máquinas
está dada por la siguiente tabla:

Máquina
I Viga A B C
Pequeña 300 600 800
Mediana 250 400 700
Grande 200 350 600
Extra Grande 100 200 300

Suponga que cada máquina puede ser utilizada hasta 50 horas a la

semana y que el costo de operación por hora de cada una de estas
máquinas es de $300.00, $500.00 y $800.00 respectivamente. Suponga
además que semanalmente se requieren I vigas con tamaño de 3,500,
3,000, 2,000 y 1,600 metros, respectivamente. Formule el problema de
programar las máquinas como un problema de programación lineal.

6. El departamento de servicios de un almacén proporciona servicios de

reparación para la mercancı́a vendida. Durante una semana 5 televi-
sores, 12 radios y 18 licuadoras fueron devueltas para reparación. Dos
MODELOS DE PROGRAMACION LINEAL 21

mecánicos son contratados temporalmente para ayudar en dicho depar-

tamento. En una jornada de 8 horas Juan puede reparar 1 televisor,
3 radios o 3 licuadoras, mientras que Pedro puede reparar 1 televisor,
2 radios o 2 licuadoras en el mismo tiempo. Si Juan gana 250 pe-
sos diarios y Pedro 150 pesos diarios, ¿por cuántas horas deberán ser
contratados de manera que los costos de reparación sean mı́nimos?
7. Considere una planta productora de cemento cuya producción anual es
de 2 millones de toneladas de cemento. La contaminación atmosférica
que produce dicha planta es enorme, por lo cual está obligada a usar
dispositivos anticontaminantes. Sus hornos están equipados con colec-
tores mecánicos para el control de la contaminación del aire. La planta
aún ası́, produce 5 kilógramos de polvo por tonelada producida. Exis-
ten dos tipos de precipitadores electrostáticos que se pueden instalar
para controlar las emisiones de polvo. Un tipo es el de 4-campos que
reduce las emisiones en 1.5 kilógramos por tonelada y su uso cuesta
$.15 por tonelada. El otro tipo es de 5-campos y reduce las emisiones
en 2.5 kilógramos por tonelada y cuesta $.2 por tonelada. La SEDUE
reclama que las emisiones de partı́culas contaminantes deben reducirse
por lo menos a un 84 por ciento ¿Cuántas toneladas de cemento deben
producirse usando cada uno de los nuevos procesos de control para
minimizar el costo de los controles y cumplir con los requerimientos de
la SEDUE? (Sugerencia: Denote con x y y las partes de la producción
que se procesarán usando colectores 4-campos y 5-campos, respectiva-
mente).
8. Raúl piensa invertir $5,000 durante los próximos cinco años. Al prin-
cipio de cada año él puede hacer depósitos de dinero por uno o dos
años. El banco paga un interés de 20% por depósitos anuales y de 42%
en total por depósitos bianuales. Además el banco ofrece certificados
por tres años al principio del segundo año. Estos certificados producen
un interés total de 65%. Si Raúl reinvierte su dinero disponible a-
nualmente, formule un problema de programación lineal para mostrar
cómo puede maximizar él su dinero en efectivo al final del quinto año.
Sugerencia: Defina una variable para cada una de las cantidades que
Raúl invertirá al principio de cada uno de los cinco años en depósitos
anuales, bianuales o en certificados a tres años.
9. Supóngase que poseemos una instalación fabril que se puede engra-
nar en n diferentes actividades de producción, cada una de las cuáles
22 Programación Lineal: López M.

produce diversas cantidades de m mercancı́as. Cada actividad puede

operarse en cualquier nivel xj > 0. El costo de la j-ésima activi-
dad cuando es operada en el nivel unitario es de cj pesos y la pro-
ducción de la i-ésima mercancı́a es de aij unidades. Si le asignamos los
números b1 , b2 , . . . , bm a los requerimientos de salida de las mercancı́as
y suponiendo linealidad en la producción de mercancı́as, formule un
modelo de programación lineal para este problema, si se trata de cono-
cer los niveles de producción xj para los cuáles el costo de producción
sea mı́nimo.

10. Una planta refinadora de petróleo produce cuatro tipos de gasolina

cruda: alcalina, catalı́tica, ”maya” e isopentano. Cada gasolina tiene
dos caracterı́sticas importantes que son su número de rendimiento PN
(que indica propiedades antiexplosivas) y su presión del vapor RVP
(que indica volatilidad). Estas dos caracterı́sticas, junto con los niveles
de producción por barriles diarios, son como sigue:

Tipo de Gasolina PN RVP Barriles Producidos

Alcalina 107 5 3814
Catalı́tica 93 8 2666 (2.8)
Maya 87 4 4016
Isopentano 108 21 1300

Estas gasolinas pueden venderse ya sea crudas en $4.83 por barril o

mezcladas en gasolina para avión (GasAv A y/o GasAv B). Los
estandares de calidad imponen ciertas restricciones en las gasolinas
para avión: estos requerimientos, junto con los precios de venta son
los siguientes:

Tipo de Gasolina PN RVP Precio por Barril

GasAv A al menos 100 a lo sumo 7 $6.45
GasAv B al menos 91 a lo sumo 7 $5.91
(2.9)

El PN y el RVP de cada mezcla son simplemente los promedios Pon-

derados de los PN y RVP de sus gasolinas constituyentes. Por ejem-
plo, la refinerı́a puede adoptar la siguiente estrategia: Mezclar 2666
MODELOS DE PROGRAMACION LINEAL 23

barriles de alcalina con 2666 de catalı́tica en 5332 barriles de GasAv

A con

(2666 × 107) + (2666 × 93)

PN = = 100 (2.10)
5332

(2666 × 5) + (2666 × 8)
RV P = = 6.5 (2.11)
5332

Mezclar 1148 barriles de alcalino, 4016 barriles de maya y 1024 barriles

de isopentano en 6188 barriles de GasAv B con

(1148 × 107) + (4016 × 87) + (1024 × 108)

PN = = 94.2 (2.12)
6188

(1148 × 5) + (4016 × 4) + (1024 × 21)

RV P = =7 (2.13)
6188

vende además 276 barriles de isopentano. Este plan de muestra

produce una ganancia total de

(5332 × 6.45) + (6188 × 5.91) + (276 × 4.83) = $72.296 (2.14)

La meta de la refinerı́a consiste en encontrar el plan que produzca la

mayor ganancia posible. ¡Formúlelo como un problema de Programa-
cion Lineal en forma estándar!
24 Programación Lineal: López M.
Bibliografı́a General

[1] Aho, A.V., Hopcroft, J., Ullman, J.: The Design and Analysis of Com-
puter Algorithms, Addison Wesley, 1976.

[2] Bazaraa, M., Jarvis, J., Sherali, H.: Linear Programming and Network
Flows, Second Edition, John Wiley and Sons, 1990, Singapore.

[3] Bazaraa, M., Jarvis, J., Sherali, H.: Programación Lineal y Flujo en
Redes, Editorial Limusa, México, 1990

[4] Bland, R.G.: New finite pivoting rules for the simplex method, Mathe-
matics of Operations Research 2 (1977).

[5] Calvillo, G.: Métodos de la Programación Lineal, V Coloquio del Depto.

de Matemáticas del CINVESTAV, Pátzcuaro, Mich., 1987.

[6] Chvàtal, V.: Linear Programming, Freeman and Co., 1983.

[7] Coxeter, H.S.M: Regular Polytopes, Dover Publications Inc., New York,
1973.

[8] Cruz Alvárez José Luis.: Solución al Problema del Transporte con
Técnicas de Programación Lineal, tesis de licenciatura en computación,
ECFM, UAP, 1995.

[9] Dantzig, G.: Linear Programming and Extensions, Princeton University

Press, Princeton, New York, 1963.

[10] Dantzig, George, Thapa Mukund: Linear Programming 1: Introduction,

Springer Series in Operations Research, Springer-Verlag, New York,
Berlin, Heidelberg, 1997.

25
26 Programación Lineal: López M.

[11] Dantzig, George: Remembranzas sobre el Origen de la Programación

Lineal, Operations Research Letters I, 1982, Traducción libre de G.
López Mayo, 1988.

[12] Garfinkel, R.S. and G.L. Nemhauser, Integer Programming, John Wiley
& Sons, Inc., New York, 1972

[13] Gass, Saul., Programación Lineal, CECSA, 1975

[14] Gomory R., Essentials of an Algorithm for Integer Solution to Linear

Programs, Bulletin of the American Mathematical Society, Vol. 64, 1958

[15] Gomory R., An Algorithm for Integer Solution to Linear Programming,

pp. 269-302. Princeton-IBM, Math. Research Project Technical Report
No. 1. Princeton N.J., 1958

[16] Gomory R., An Algorithm for the Mixed Integer Problem. RM-2597,
The RAND Corporation, Santa Mónica, 1960

[17] Gomory R., Essentials of an Algorithm for Integer Solution to Linear

Programs, Bulletin of the American Mathematical Society, Vol. 64, 1958

[18] Hadley, G.: Linear Programming, Addison Wesley Publishing Co., Mas-
sachusets, 1969.

[19] Klee, V. and Minty, G.: How Good is the simplex algorithm?,
Inequalities-III, O. Shisha, ed. New York, Academic Press.

[20] Kolman, B. and Beck, R.: Elementary Linear Programming with Ap-
plications, Academic Press, New York, 1981.

[21] Lemke, C.E. The Dual Method of Solving the Linear Programming Prob-
lem, Naval Research Logistics Quarterly, Vol. 1, No. 1, 1954.

[22] López Mayo G.: Invariantes Poliédricos y Teoremas de Representación

en Diferentes Geometrı́as, Tesis de Maestrı́a, IPN,. 1986.

[23] Luenberger, D.G.: Introduction to Linear and Nonlinear Programming

, Addison Wesley Publishing Co., 1972.

[24] McMullen, P. : The maximum number of faces a convex polytope, Math-

ematica 17, pp. 179-184, 1970
MODELOS DE PROGRAMACION LINEAL 27

[25] Pérez Munive, Ma. del Rosario, Manual de LINDO, Escuela de Ciencias
Fı́sico Matemáticas, UAP, 1990.

[26] Robles Mendoza Javier.: Adyacencia en Poliedros Convexos y una

Aplicación al Problema del Agente Viajero, tesis de licenciatura en
matemáticas, ECFM, UAP; 1991.

[27] Sánchez Martı́nez Sergio.: Algoritmo para Problemas de Transbordo me-

diante el uso de Bases Duales, tesis de licenciatura en computación,
FCC, UAP, 1997.

[28] Scrijver, A.: Theory of Linear and Integer Programming, Department

of Econometrics, Tiburg University and Centrum voor Wiskunde en
Informatica, Amsterdam, John Wiley and Sons, Chichester, 1986.

[29] Simmonard, M.A.: Programación Lineal, Editorial Cientı́fico Técnica,

La Habana, Cuba, 1972.

[30] Stoer, Joseph and Witzgall Cristoph: Convexity and Optimization in

Finite Dimensions I, Springer Verlag, New York, 1970.

[31] Tecpóyotl Torres Margarita.: Algoritmos para Encontrar los Vértices

de un Poliedro Convexo, tesis de licenciatura en matemáticas, ECFM,
UAP, 1992.

[32] Tucker, A.W, Dual Systems of Homogeneus linear equations in Linear

Inequalities and Related Systems, Princeton University Press.

[33] Von Neumann, J. and Morgestern, Theory of Games and Economic

Behavior, Princeton University Press, Princeton, N.J., 1947.

[34] Webb, K.W. The Mathematical Theory of Sensitivity, trabajo presen-

tado en la XVIII Convención Nacional de Operations Research of Amer-
ica, Detroit, Mich., octubre 12, 1960.

[35] Wolfe P. A technique for resolving degeneracy in Linear Programming

Journal of the Society for Industrial and Applied Mathematics II pp.
205-211 1963.