Programacion Lineal

Fundamentos de Investigaci´on de Operaciones
Investigaci´on de Operaciones 1
Formulaci´
on de Modelos de Programac´
on Lineal
25 de julio de 2003

La Programaci´
on Lineal (LP) es una herramienta para resolver problemas de optimizaci´
on que se
caracterizan por tener como funci´
on objetivo y restricciones combinaciones lineales de las variables de
decisi´
on. La principal ventaja radica en queexiste un algoritmo eficiente (SIMPLEX) para resolver
este tipo de modelos.

1.

Conceptos B´
asicos
Consideremos el siguiente ejemplo para describir los t´erminos presentes en todo problema de LP.

Ejemplo 1.
Una muebler´ıa produce mesas y sillas de madera. Cada mesa es vendida en $27000 y requiere $10000
en materiales, adem´
as, el costo de unitario por mano de obra se estima en $14000. En elcaso de
las sillas, su precio de venta es de $21000 y los costos son de $9000 y $10000, en materiales y mano
de obra respectivamente. La fabricaci´
on de cada producto requiere de dos tipos de labores: carpinter´ıa
y terminaciones. Una mesa requiere de 1 hora de carpinter´ıa y 2 horas de terminaciones. Una silla
requiere de 1 hora de carpinter´ıa y 1 hora de terminaciones.
Cada semana, la muebler´ıapuede obtener todos los materiales que desee, sin embargo, se pueden
dedicar hasta 100 horas a las terminaciones y hasta 80 horas a la carpinter´ıa. La demanda por mesas
no est´
a limitada, mientras que la demanda semanal m´
axima por sillas es de 40.
La muebler´ıa desea maximizar sus utilidades (ingresos - costos). Formule un modelo matem´
atico que
permita maximizar las utilidades.

1.1.Variables de Decisi´
on

Se debe comenzar definiendo las variables de decisi´
on relevantes. En un modelo de programaci´on
lineal las variables de decisi´on deben ser capaces de describir completamente las decisiones que puedan
ser tomadas y todas las variantes que existan.
Antes de definir las variables de decisi´on es importante definir las unidades involucradas en el problema.
En este caso, se hablade unidades de sillas y mesas, de horas de trabajo por unidad y de demanda
semanal. De acuerdo a ello, una buena opci´on para definir las variables de decisi´on consiste en asociar
las variables al n´
umero de unidades de sillas y mesas a producir por semana. Por lo tanto, podemos
definir:
x1 = n´
umero de mesas producidas por semana.
(1.1)
x2 = n´
umero de sillas producidas por semana.

1Segundo Semestre 2003

1.2.

Programaci´
on Lineal

Funci´
on Objetivo

En un problema de LP, se debe tomar la decisi´on de maximizar (usualmente las utilidades)
o de minimizar (usualmente los costos) cierta funci´on de las variables de decisi´on. La funci´on a
maximizar o minimizar se denomina funci´
on objetivo. Antes de formular el modelo matem´atico
conviene resumir los datos del problema (Cuadro1.1).
Venta

Materiales

Mano de Obra

$

$

$

un.
27000
21000
–

Mesa
Silla
Disponibilidad

un.
10000
9000
–

un.
14000
10000
–

Carpinter´ıa
hr.
un.
1
1
80

Terminaciones
hr.
un.
2
1
100

Dda. M´axima
un.
sem.
–
40
–

Cuadro 1.1: Resumen Ejemplo 1
En el ejemplo, los costos e ingresos no dependen del valor de x1 o de x2 , por lo tanto basta
concentrarse en maximizar la diferencia entre:
ingresossemanales

costos de
materiales

−

−

costos por
mano de obra

(1.2)

Luego, se debe expresar los t´erminos anteriores en funci´on de las variables de decisi´on x 1 y x2 .
Supondremos que todas las sillas y mesas fabricadas son vendidas (respentando las condiciones
de mercado del enunciado). As´ı:
ingresos
semanales

=
=
=

ingresos
por mesas
$
mesa

mesas
semana

27000x1

ingresos
por sillas

++
+

$
silla

sillas
semana

(1.3)

21000x2

Similarmente:
costos por
materiales
costos por
mano de obra

= 10000x1 +

9000x2
(1.4)

= 14000x1 + 10000x2

Por lo tanto la funci´on a maximizar queda (en miles):
(27x1 + 21x2 ) − (10x1 + 9x2 ) − (14x1 + 10x2 ) = 3x1 + 2x2

(1.5)

Otra opci´on para construir la funci´on objetivo consiste en calcular previamente los ingresos netos
o utilidades de cada...