Programacion Lineal

Unidad 1: Programaci´
on lineal
1.1.

Problemas de programaci´
on lineal

Definici´
on 1 (Problema de programaci´
on lineal)
Un problema de programaci´on lineal (PPL) es el problema de determinar el valor m´aximo o
m´ınimo que toma una funci´on lineal, para los valores de las variables que satisfacen un conjunto
de igualdades o desigualdades lineales.
Notaci´
on
Un PPL se puede expresar demanera general mediante:
min (max) c1 x1 + · · · + cn xn
s.a.
a11 x1 + · · · +a1n xn (=, >, <, ≤, ≥)
..
..
..
..
.
.
.
.

b1
..
.

am1 x1 + · · · +amn xn (=, >, <, ≤, ≥) bm
x1 , · · ·
, xn
≥
0
aqu´ı se llaman:
c1 x1 + · · · + cn xn : funci´on objetivo
ai1 x1 + · · · + ain xn (=, >, <, ≤, ≥)bi : restricci´on i-´esima
c1 , . . . , cn : coeficientes de costo
x1 , . . . , xn : variables de decisi´on
a11 ,. . . , a1n , . . . , am1 , . . . , amn : coeficientes tecnol´ogicos
b1 , . . . , bm : requerimientos o disponibilidades
x1 , . . . , xn ≥ 0: condiciones de no negatividad

1.2.

Planteamiento de PPLs

1.2.1.

Recomendaciones para plantear PPLs

• Escriba un enunciado verbal de la funci´on objetivo y de cada restricci´on del problema.
• Defina las variables de decisi´on, observando el car´acterlineal que deben tener las restricciones
y la funci´on objetivo.
• Escriba la funci´on objetivo como funci´on lineal de las variables de decisi´on.
• Escriba cada restricci´on como una igualdad o desigualdad lineal de las variables de decisi´on.

1.2.2.

Ejemplos de planteamiento de PPLs

El problema de la mezcla alimenticia
Se desea determinar un programa para combinar n ingredientes (con´ındice asociado j, j =
1, . . . , n), los cuales contienen m nutrientes (con ´ındice asociado i, i = 1, . . . , m) , de tal manera

que se obtengan b unidades de una mezcla alimenticia a costo m´ınimo. El contenido de nutriente
i en cada unidad de la mezcla debe ser como m´ınimo li unidades y como m´aximo ui unidades. Se
sabe que hay disponibles dj unidades del ingrediente j. Adem´as son conocidos elcosto cj de una
unidad del ingrediente j, y la cantidad aij de unidades del nutriente i presentes en una unidad del
ingrediente j.
El modelo de la mezcla alimenticia
xj : unidades del ingrediente j a usar en la mezcla, j = 1, . . . , n
n

min

cj x j
j=1

s.a.
n

aij xj ≥ b li , i = 1, . . . , m
j=1
n

aij xj ≤ b ui , i = 1, . . . , m
j=1
n

xj = b
j=1

xj ≤ dj , j = 1, . . . , n
xj ≥ 0, j = 1, .. . , n
Un problema de programaci´
on de producci´
on e inventario
Una empresa desea determinar un programa que cubra n per´ıodos de tiempo, durante cada uno
de los cuales la demanda, la producci´on y el inventario se asumen constantes, de tal manera que
se satisfaga en cada per´ıodo una demanda conocida gi y se minimice el costo total de producci´on
e inventario. Se asume que la capacidad deproducci´on se limita a un m´aximo de b1 unidades por
per´ıodo y la capacidad de almacenamiento se limitada a b2 unidades por per´ıodo como m´aximo.
Adem´as se denotan:
• y0 : inventario al tiempo 0
• yT : inventario deseado despu´es de n per´ıodos
• ci1 : costo de almacenamiento de un art´ıculo durante el per´ıodo i
• ci2 : costo de producci´on de un art´ıculo durante el per´ıodo i
El modelo deprogramaci´
on de producci´
on e inventario
xi : art´ıculos a producir durante el per´ıodo i, i = 1, . . . , n
yi : inventario durante el per´ıodo i, . . . i = 1, . . . , n
n

min

(ci1 yi + ci2 xi )
i=1

s.a.

xi
xi

yn = yT
yi = yi−1 + xi − gi , i = 1, . . . , n
≤ b1 , i = 1, . . . , n
yi ≤ b2 , i = 1, . . . , n
, yi ≥ 0, i = 1, . . . , n

El problema de transporte
Consid´erense m lugaresllamados or´ıgenes donde hay disponibilidad de un cierto bien y n lugares
llamados destinos donde hay demanda del mismo bien. Se conocen la oferta ai del origen i, la
demanda bj del destino j, y los cij que son los costos unitarios de transporte del bien desde el
origen i hasta el destino j, i = 1, . . . m, j = 1, . . . , n. Bajo la condici´on que la oferta total es igual
a la demanda total, se debe...