Programación Lineal

Elementos de un modelo de programación

lineal.

• Variables. Son las cantidades o aspectos del proceso que el decisor está
buscando controlar
• Función objetivo. Es la representación matemática de las metas del
decisor.
• Restricciones. Son los enunciados matemáticos que describen la
tecnología o la realidad del procedimiento que se está modelando y de
cómo la tecnología utiliza los recursos disponibles.
 Hipótesis específicas:

• 1ª. Linealidad. Todas las relaciones matemáticas que expresan a la función

objetivo y las restricciones deben ser funciones lineales.
• 2ª. Se utilizan variables continuas.
• 3ª. Existe sólo una función objetivo.
• 4ª. Se supone al modelo lineal como determinista.
 Representación matemática del modelo.

• El modelo de programación lineal se puede representar de la siguiente forma:

Maximizar o minimizar
𝑧 = 𝑐1𝑥1 + 𝑐2𝑥2 + … + 𝑐𝑛𝑥𝑛
• Sujeto a las siguientes restricciones
𝑎11𝑥1 + 𝑎12𝑥2 + … + 𝑎1𝑛𝑥𝑛 ≤=≥ 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 + … + 𝑎2𝑛𝑥𝑛 ≤=≥ 𝑏2
restricciones de tecnología
…
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + … + 𝑎𝑚𝑛𝑥𝑛 ≤=≥ 𝑏𝑚

𝑥1 ≥ 0; 𝑥2 ≥ 0, … , 𝑥𝑛 ≥ 0 restricciones de no negatividad
 ≤

• Estas restricciones se aplican generalmente a la utilización de recursos y

el uso de un recurso no debe exceder de la cantidad disponible.
 =

• Estas restricciones se describen como un conjunto de condiciones que se

deben satisfacer con exactitud.
 ≥

• Se utilizan generalmente para describir los requerimientos mínimos.

 Restricciones de no negatividad 𝑥𝑛 ≥ 0.

• Se requiere que las variables de decisión no tengan valores negativos.

Cuando se construye un modelo de programación lineal, se debe proceder en
las siguientes etapas:
1. Identificar a las variables.
2. Determinar la función objetivo.
3. Formular las restricciones de la siguiente forma:
a. Detectar los requerimientos y la disponibilidad del recurso.
b. Determinar la tecnología del procedimiento (𝑎𝑚𝑛).
 Un problema de dieta:

• Es un problema típico de programación lineal. Como se sabe por experiencia, las

dietas se seleccionan para cumplir con una serie de criterios. Cada persona necesita
cantidades diarias de calorías, vitaminas, proteínas, minerales, etc. También se
tienen preferencias por los tipos de comida y las marcas. La dieta óptima será la
que cumpla todas las necesidades a un costo mínimo.
• Para simplificar el problema se supone que existen sólo tres restricciones, la
cantidad diaria de tres vitaminas. También se supone que sólo se están
considerando dos tipos de alimentos. Así el problema consiste en decidir cuánto
comprar de cada alimento para satisfacer las tres restricciones y minimizar el costo.
 Un problema de dieta:

• Supóngase que el alimento A y el alimento B son los dos tipos bajo

consideración. El alimento A cuesta 12 centavos/onza y el alimento B cuesta
8 centavos/onza. Se quiere minimizar el costo total de los alimentos al
mismo tiempo que satisfacer las tres restricciones vitamínicas. Se desean,
por lo menos, 30 unidades de la vitamina W, 50 unidades de la vitamina X y
60 unidades de la vitamina Y. Cada onza del alimento A proporciona 2
unidades de la vitamina W, 4 unidades de la vitamina X y 7 unidades de la
vitamina Y. El alimento B proporciona 3, 3 y 6 unidades de W, X y Y, por onza,
respectivamente. ¿Cuántas onzas de cada alimento deben comprarse?
 Un problema de mezclas:
• Este es otro tipo de problema de PL. Aquí el problema es encontrar la
combinación de ingredientes con el menor costo y que satisfaga las
especificaciones del producto final. Ejemplos de esto ocurren al refinar
gasolinas, en las preparaciones químicas y en las mezclas de concreto.
• Supóngase que una compañía que da servicios de limpieza prepara sus
propias soluciones mezclando dos ingredientes. Hace esto para obtener una
solución que tiene lo que considera una combinación apropiada de fosfatos
y cloruros. Un ingrediente tiene 5% de fosfatos y 2% de cloruro y cuesta 25
centavos/onza. El otro ingrediente tiene 7% de fosfato y 1% de cloruro y
cuesta 20 centavos/onza. La firma necesita que la mezcla final tenga no más
del 6% de fosfatos y 1 1/2% de cloruro.
 Un problema de inversión:

• Esta es otra forma del problema de mezclas. Supóngase que se acaba de

recibir una herencia de $10,000 de un tío lejano y que se quiere invertir este
dinero para maximizar el rendimiento sobre la inversión. Se decide invertir
tanto en acciones como en bonos. Para estar seguros, se piensa que las
acciones deben ser no más del 25% del total y debe ser, por lo menos, el
10%. Existe un bono que resulta en particular interesante y se quiere invertir
en él por lo menos $4000. Se estima que la tasa anual de rendimiento en
bonos es el 8% y en acciones el 10%. ¿Cuánto debe invertirse en acciones y
cuánto en bonos?
• Un carnicero está preparando la oferta de carne del día. Existen dos clase de carne,
la Clase 1 y la Clase 2. La decisión es determinar cuántas bandejas de cada clase
elaborar. No existe restricción de que sean enteras; se puede tener 3 ½ de bandeja
o cualquier número fraccional. El beneficio se incrementa en $6 por cada bandeja
de Clase 1 que se tenga, y $4 por cada bandeja de Clase 2. Si no hubiera
restricciones, el carnicero desearía hacer bastante de ambas carnes; el beneficio
entonces sería muy grande. Las restricciones que debe considerar son:
• Restricción 1: El carnicero no puede vender más de seis bandejas por día.
• Restricción 2: Él y su personal solamente tiene disponibles 9 horas. Les toma dos
horas preparar una bandeja de Clase 1 y una hora una bandeja de Clase 2.
• Restricción 3: El carnicero tiene solamente 16 pies de espacio para preparar su
carne. Cada bandeja de Clase 1 requiere dos pies de espacio. Cada bandeja de Clase
2 requiere tres pies.
• La Compañía Cecilia fabrica tres clases de lentes para cámara: baja, mediana
y alta clases. El procedimiento de producción involucra tres operaciones:
formación de los lentes, donde el vidrio fundido se transforma en lentes
crudos; la inspección, un sistema complejo donde las propiedades de los
lentes se determinan y se clasifican según su clase y, el acabado, donde un
procedimiento automatizado corta y pule los lentes.
• Los datos del tiempo de producción, costo e ingresos para la compañía se
resumen en las siguientes tablas.
• El problema es decidir el número de cada tipo de lentes que deberán
producirse en una hora de tal manera que se maximice el beneficio horario.
 Datos de producción para la compañía Cecilia (minutos por lente)
Graduación de los lentes: Formación de los lentes: Inspección: Acabado:
Baja: 2.25 3 1.5
Media: 2.50 6 2.5
Alta 3.00 12 5.0

Datos de Costo e Ingreso para la compañía Cecilia

Graduación de los Costo de Costo de Costo Total Precio de venta
lentes: Manufactura Materiales
Baja: $ 18.00 $6.50 $ 24.50 40.00
Media: 32.50 8.00 40.50 60.00
Alta 54.00 12.50 66.50 100.00
• Una compañía maderera fabrica tres clases de madera. El procedimiento de
producción consiste en tres operaciones: barnizado, pegado y acabado. Una
hoja de Clase 1 requiere 0.2 horas de barnizado, 0.025 horas de pegado y
0.04 horas de acabado. Una hoja de Clase 2 requiere 0.05 horas de
barnizado, 0.05 de pegado y 0.02 de acabado. Una hoja de Clase 3 requiere
0.1 de barnizado, 0.3 horas de pegado y 0.2 horas de acabado. Se tienen
disponibles 90, 40 y 60 horas para cada operación. La contribución al
beneficio de una hoja Clase 1 es $1.25, de Clase 2 $1.50 y de Clase 3 $2.25.
Formule un modelo lineal para determinar el número de láminas de cada
clase que debe producir de tal manera que se maximice el beneficio.
• Un procedimiento de manufactura utiliza dos recursos en la elaboración de
tres productos. La tecnología del procedimiento es: el Producto 1 requiere 7
libras del Recurso 1 y 5 cajas del Recurso 2; el Producto 2 requiere cuatro
libras del Recurso 1 y tres cajas del Recurso 2; el Producto 3 requiere tres
libras del Recurso 1 y dos cajas del Recurso 2. Existen 100 libras de Recurso 1
y 150 cajas de Recurso 2. Formule un modelo de programación lineal de tal
manera que se maximicen los beneficios de la línea de producción cuando
las contribuciones de los productos son $10, $10 y $7.50 respectivamente.
 Método Gráfico para la Solución de
Problemas de Programación Lineal.

• Este método solamente es utilizado cuando el modelo de Programación

Lineal se encuentra compuesto por 2 (dos) incógnitas: 𝑥1 y 𝑥2:
 1. Dado el modelo

• Optimizar: (Maximizar o Minimizar)

𝑧 = 𝑐1 𝑥1 + 𝑐2 𝑥2
• Sujeto a:
𝑎11 𝑥1 + 𝑎12 𝑥2 ≤=≥ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 ≤=≥ 𝑏2
…
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 ≤=≥ 𝑏𝑚
𝑥1 , 𝑥2 ≥ 0
2. Tomar las restricciones por su parte
igualdad:

𝑎11 𝑥1 + 𝑎12 𝑥2 = 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 = 𝑏2
…
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 = 𝑏𝑚
3. Se representan gráficamente las igualdades
obtenidas
14
12
10
8
x2
6
4
2
0
0 2 4 6 8 10

x1

Restricción (1) Restricción (2)

4. Se identifica la zona de soluciones factibles
para el modelo.
14
12
Zona de
10
Factibilidad
8
x2
6
4
2
0
0 2 4 6 8 10

x1

Restricción (1) Restricción (2)

5. Se evalúa la función objetivo en los vértices de la zona
de factibilidad, el punto que optimice (maximice o
minimice) la función objetivo dará la solución óptima al
problema de programación lineal.
14
12 Vérti ce 1
10
Zona de
8
x2 Factibilidad
6
4
2
0
0 2 4 6 8 10

Vérti ce 3 x1 Vérti ce 2

Restricción (1) Restricción (2)

• Molly Bolt es una tenaz fabricante de escritorios y sillas de pacotilla. Por
cada escritorio requiere 4 horas de ensamblado y 9 de pintura. Por cada silla
4 horas de ensamblado y 3 de pintura. Para el próximo mes Molly ha
destinado 32 horas al ensamble y 36 para pintar. Grafique las combinaciones
de escritorios y de sillas que Molly puede fabricar y que satisfagan:
1. Su restricción de tiempo de ensamblado.
2. Su restricción en el tiempo de pintura
3. Ambas restricciones simultáneas.
• Molly gana $6 por escritorio y 5 por cada silla.
• Resolver por método gráfico los problemas de
a) Dieta
b) Mezclas e
c) Inversión
 El Algoritmo Simplex.

• Dado el problema de Programación Lineal

Maximizar
𝑧 = 10𝑥1 + 10 𝑥2
Sujeto a
2𝑥1 + 𝑥2 ≤ 10
𝑥1 + 2𝑥2 ≤ 10
𝑥1, 𝑥2 ≥ 0
• Este sistema de desigualdades se convierte en un sistema de ecuaciones
introduciendo variables de holgura en cada desigualdad (su valor numérico
es la diferencia entre el lado derecho y el lado izquierdo de la desigualdad).

2x1 + x2 + H1 = 10
x1 + 2x2 + H2 = 10

• quedando la función objetivo:

Maximizar
z = 10x1 + 10 x2 + 0H1 + 0H2
 Formación de la 1ª Matriz simplex.
• Convertidas las restricciones a igualdades se procede a llenar la tabla
simplex de la siguiente manera:
• La primera columna tendrá los nombres de las variables básicas (vb) para
cada restricción. La segunda contiene los términos independientes (Ti) de
cada restricción. Las demás columnas contendrán los coeficientes de cada
variable en cada restricción. La última columna mostrará el cociente del
término independiente entre la columna pivote (el algoritmo consiste en
eliminar variables básicas para introducir como variables básicas otras
variables). Se seleccionan como variables básicas para este caso a las
variables de holgura (o variables artificiales según el caso). El último renglón
de la tabla contendrá los coeficientes de z con signos contrarios.
 1ª Matriz
vb Ti x1 x2 H1 H2 Cociente

H1 10 2 1 1 0

H2 10 1 2 0 1

z 0 -10 -10 0 0

Ahora se elige la variable a introducir tomando en cuenta a la más

negativa en el renglón z.

Para determinar la variable a eliminar se dividen los términos

independientes entre los términos de la columna pivote.
 Columna
Pivote

vb Ti x1 x2 H1 H2 Cociente

H1 10 2 1 1 0

H2 10 1 2 0 1

z 0 -10 -10 0 0
 Columna 𝑻𝒊/𝑪𝒐𝒍𝒖𝒎𝒏𝒂 𝑷𝒊𝒗𝒐𝒕𝒆
Pivote

vb Ti x1 x2 H1 H2 Cociente
10
H1 10 2 1 1 0 =5
2
10
H2 10 1 2 0 1 = 10
1

z 0 -10 -10 0 0
 Columna 𝑻𝒊/𝑪𝒐𝒍𝒖𝒎𝒏𝒂 𝑷𝒊𝒗𝒐𝒕𝒆
Pivote

vb Ti x1 x2 H1 H2 Cociente

H1 10 2 1 1 0 5

H2 10 1 2 0 1 10

z 0 -10 -10 0 0

La variable básica a eliminar será la que tenga el cociente menor.

 𝑪𝒐𝒍𝒖𝒎𝒏𝒂 𝑻𝒊/𝑪𝒐𝒍𝒖𝒎𝒏𝒂 𝑷𝒊𝒗𝒐𝒕𝒆
𝑷𝒊𝒗𝒐𝒕𝒆

vb Ti x1 x2 H1 H2 Cociente
𝑹𝒆𝒏𝒈𝒍ó𝒏
H1 10 2 1 1 0 5
𝒑𝒊𝒗𝒐𝒕𝒆
H2 10 1 2 0 1 10

z 0 -10 -10 0 0

• La intersección de la columna y el renglón pivote se llama pivote o número pivote.

• Sale 𝐻1 y entra 𝑥1 .
 Formación de la 2ª. Matriz.
vb Ti x1 x2 H1 H2 Cociente

x1

H2

• Se calculan los nuevos elementos de la tabla de la siguiente manera:

Nuevo renglón pivote (renglón 𝑥1):
𝑁𝑅𝑃 = 𝑅𝑒𝑛𝑔𝑙ó𝑛 𝑝𝑖𝑣𝑜𝑡𝑒 𝑎𝑛𝑡𝑒𝑟𝑖𝑜𝑟 / 𝑁ú𝑚𝑒𝑟𝑜 𝑝𝑖𝑣𝑜𝑡𝑒
𝑁𝑅𝑃 = 𝑅𝑃𝐴/𝑃𝑖𝑣𝑜𝑡𝑒
10,2,1,1,0
𝑁𝑅𝑃 = 2
= 5,1,1/2,1/2,0
 Formación de la 2ª. Matriz.
vb Ti x1 x2 H1 H2 Cociente

x1 5 1 ½ ½ 0
H2

• Los demás renglones se calculan como:

Nuevo renglón:
𝑁𝑅 = 𝑅𝑒𝑛𝑔𝑙ó𝑛 𝑎𝑛𝑡𝑒𝑟𝑖𝑜𝑟 − 𝑁ú𝑚𝑒𝑟𝑜 𝑒𝑛 𝑐𝑜𝑙𝑢𝑚𝑛𝑎 𝑝𝑖𝑣𝑜𝑡𝑒 (𝑁𝑢𝑒𝑣𝑜 𝑟𝑒𝑛𝑔𝑙ó𝑛 𝑝𝑖𝑣𝑜𝑡𝑒)
𝑁𝑅 = 𝑅𝐴 − (𝑁𝐶𝑃)(𝑁𝑅𝑃)
1 1 1 1 3 1
𝑁𝑅𝐻2 = 10,1,2,0,1 − 1 5,1, , , 0 = 10,1,2,0,1 − 5,1, , , 0 = (5,1, , − , 1)
2 2 2 2 2 2
 Formación de la 2ª. Matriz.
vb Ti x1 x2 H1 H2 Cociente

x1 5 1 ½ ½ 0
H2 5 1 3/2 −1/2 1
z

1 1
𝑁𝑅𝑍 = 0, −10, −10,0,0 − −10 5,1, , , 0
2 2
= 0, −10, −10,0,0 − −50, −10, −5, −5,0 = (50,0, −5,5,0)
 Formación de la 2ª. Matriz.
vb Ti x1 x2 H1 H2 Cociente

x1 5 1 ½ ½ 0
H2 5 1 3/2 −1/2 1
z 50 0 −5 5 0

• Se analiza el renglón “z”, si todos sus valores son no negativos se tiene la

solución óptima definida en Ti, si no, se forma una nueva matriz hasta hallar
la solución óptima.
• Como aún hay un valor negativo en el renglón “z” se procede a una nueva
iteración.
 Formación de la 2ª. Matriz.
vb Ti x1 x2 H1 H2 Cociente

x1 5 1 ½ ½ 0 10

H2 5 1 3/2 −1/2 1 10/3

z 50 0 −5 5 0

• Sale la variable 𝐻2 y entra la variable 𝑥2.

 Matriz final y solución óptima
vb Ti X1 x2 H1 H2 Cociente

x1 10/3 1 0 2/3 1/3

x2 10/3 0 1 −1/3 2/3
z 200/3 0 0 10/3 10/3

• Solución óptima:
𝒁𝒎á𝒙𝒊𝒎𝒂 = 𝟐𝟎𝟎/𝟑
𝒙𝟏 = 𝟏𝟎/𝟑
𝒙𝟐 = 𝟏𝟎/𝟑