Curso: Métodos Cuantitativos Periodo 2021-1

Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

Programación Lineal Entera

1. Ejemplo Bienes Raíces
Eastborne Realty tiene $2 millones disponibles para la compra de una nueva propiedad
para alquiler. Después de una investigación inicial, Eastborne redujo las alternativas de
inversión a viviendas urbanas y edificios de departamentos. Cada vivienda puede
comprarse por $282,000 y hay cinco disponibles. Cada edificio de departamentos puede
comprarse por $400,000 y el desarrollador construirá tantos edificios como Eastborne
quiera comprar. El gerente de propiedades de Eastborne puede dedicar hasta 140 horas
por mes a estas nuevas propiedades; se espera que cada vivienda requiera 4 horas por
mes y cada edificio de departamentos, 40 horas por mes. Se estima que el flujo de
efectivo anual, después de deducir los pagos hipotecarios y los gastos de operación, sea
de $10,000 por vivienda y $l5,000 por edificio de departamentos. Al propietario de
Eastborne le gustaría determinar el número de viviendas y de edificios de
departamentos a comprar para maximizar el flujo de efectivo anual.
Variables:

T = número de viviendas

A = número de edificios de departamentos

La función objetivo para el flujo de efectivo (en miles de dólares) es: Max 10T + 15A

Restricciones:

28T + 400A <= 2 000 Fondos disponibles (miles de dólares)

4T + 40A <= 140 Tiempo del administrador (horas)

T <= 5 Viviendas disponibles

En este caso, la compra de una fracción de edificio o vivienda no es posible

T y A >= 0 y enteros

Solución gráfica

1
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

Tomado de Andreson, 2011

Tomado de Andreson, 2011

2
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

2. Elaboración del presupuesto de capital

Ice-Cold Refrigerator Company considera invertir en varios proyectos que tienen
requerimientos variables de capital durante los próximos cuatro años. Como se enfrenta
a un capital limitado cada año, a la gerencia le gustaría seleccionar los proyectos más
rentables. El valor presente neto estimado para cada proyecto1, los requerimientos de
capital y el capital disponible durante el periodo de cuatro años se muestran en la tabla
debajo

Las cuatro variables de decisión 0-1 son las siguientes:

P = 1 si se acepta el proyecto de expansión de la planta; 0 si se rechaza

W = 1 si se acepta el proyecto de expansión de almacenes; 0 si se rechaza

M = 1 si se acepta el proyecto de maquinaria; 0 si se rechaza
R = 1 si se acepta el proyecto de investigación de productos nuevos; 0 si se rechaza
FO: Max 90P + 40W + 10M + 37R
15P + 10W + 10M + 15R <= 40 (capital disponible para el año 1)

20P + 15W + 10R <= 50 (capital disponible para el año 2)

20P + 20W + 10R <= 40 (capital disponible para el año 3)
15P + 5W + 4M + 10R <= 35 (capital disponible para el año 4)
P, W, M, R = 0, 1
Respuesta (Solver):

P=W=M=1

R= 0

K usado en año 1: 35,000 (Holgura 5,000)

K usado en año 2: 35,000 (Holgura 15,000)

3
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

K usado en año 3: 40,000 (Holgura 0)

K usado en año 4: 24,000 (Holgura 11,000)

Revisar que pasa cuando se corre el programa sin restricciones

3. Costo fijo
RMC utiliza tres materias primas para producir tres productos: un aditivo para
combustible, una base para solvente y un líquido limpiador de alfombras. Se utilizan las
siguientes variables de decisión:
F = toneladas producidas de aditivo para combustible
S = toneladas producidas de base para solvente
C = toneladas producidas de limpiador de alfombras
Las contribuciones a las utilidades son $40 por tonelada para el aditivo para combustible,
$30 por tonelada para la base para solvente y $50 por tonelada para el limpiador de
alfombras.
Cada tonelada de aditivo para combustible es una mezcla de 0.4 ton de material 1 y 0.6
ton de material 3. Cada tonelada de base para solvente requiere 0.5 ton de material 1,
0.2 ton de material 2 y 0.3 ton de material 3. Cada tonelada de limpiador de alfombras
es una mezcla de 0.6 ton de material 1, 0.1 ton de material 2 y 0.3 ton de material 3.
RMC tiene 20 ton de material 1, 5 ton de material 2 y 21 ton de material 3, y está
interesada en determinar las cantidades óptimas de producción para el siguiente
periodo de planeación.
FO: Max (Utilidad) 40F + 30S + 50C

Restricciones:

0.4F + 0.5S + 0.6C <= 20 (Material 1)

0.2S + 0.1C <= 5 (Material 2)

0.6F + 0.3S + 0.3C <= 21 (Material 3)

F, S y C >= 0
Respuesta (Solver): F= 27.5, S= 0 y C= 15 con Utilidad máxima de 1,850

4
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

Que sucede si añadimos el costo fijo para cada materia prima.

Es decir, el costo fijo aplica solo si el producto es fabricado

SF = 1 si se produce el aditivo para combustible; 0 si no se produce

SS = 1 si se produce la base para solvente; 0 si no se produce

SC = 1 si se produce el limpiador de alfombras; 0 si no se produce

FO ahora:

Max 40F + 30S + 50C – 200 SF – 50 SS – 400 SC

Restricciones adicionales por capacidad de producción:

F <= 50SF

S<= 25SS

C <= 40SC

Entonces, restricciones ahora:

0.4F + 0.5S + 0.6C <= 20 (Material 1)

0.2S + 0.1C <= 5 (Material 2)

0.6F + 0.3S + 0.3C <= 21 (Material 3)

F - 50SF <= 0 (F Max)

S -25SS <= 0 (S Max)
C -50SC <=0 (C Max)

F, S y C >= 0, SF, SS y SC = 0 o 1

5
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

Diseño de un sistema de distribución

Martin-Beck Company opera una planta en St. Louis con una capacidad anual de 30,000
unidades. El producto se envía a centros de distribución regionales localizados en Boston,
Atlanta y Houston. Debido a que se espera un incremento en la demanda, Martin-Beck
planea aumentar su capacidad al construir una planta nueva en una o más de las
ciudades siguientes: Detroit, Toledo, Denver o Kansas City. El costo fijo anual estimado
y la capacidad anual para las plantas propuestas son los siguiente

El grupo de planeación a largo plazo de la empresa elaboró los siguientes pronósticos de la

demanda anual esperada en los centros de distribución:

Los costos de envío de cada planta a cada centro de distribución son los siguientes:

6
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

7
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

A diferencia de problemas anteriores, ahora podemos decidir también si se abre o no

una o más plantas.

Y1 = 1 si se construye la planta de Detroit; 0 si no se construye.

Y2 = 1 si se construye la planta de Toledo; 0 si no se construye.
Y3 = 1 si se construye la planta de Denver; 0 si no se construye.
Y4 = 1 si se construye la planta de Kansas City; 0 si no se construye.
Ojo, Saint Louis ya existe

Además,
Xij = las unidades enviadas en miles desde la planta i hasta el centro de distribución j.
i = 1,2,3,4,5 y j= 1,2,3
Entonces, el costo de transporte anual serán:
5𝑥11 + 2𝑋12 + 3𝑋13 + 4𝑋21 + 3𝑋22 + 4𝑋23 + 9𝑋31 + 7𝑋32 + 5𝑋33 + 10𝑋41 + 4𝑋42
+ 2𝑋43 + 8𝑋51 + 4𝑋52 + 3𝑋53

Además, los costos fijos de operación de la plana nueva (en miles de USD) son:

175 y1 + 300 y2 + 375 y3 + 500 y4

FO (Explicar)
Restricciones de capacidad

Capacidad de planta de Detroit

𝑋11 + 𝑋12 + 𝑋13 ≤ 10𝑌1 Ó 𝑋11 + 𝑋12 + 𝑋13 − 10𝑌1 ≤ 0

Para las demás plantas:

𝑋21 + 𝑋22 + 𝑋23 − 20𝑌2 ≤ 0

𝑋31 + 𝑋32 + 𝑋33 − 30𝑌3 ≤ 0

𝑋41 + 𝑋42 + 𝑋43 − 40𝑌4 ≤ 0

𝑋51 + 𝑋52 + 𝑋53 ≤ 0 (Ya existe)

8
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

Finalmente, las restricciones para la demanda:

𝑋11 + 𝑋21 + 𝑋31 + 𝑋41 + 𝑋51 = 30

𝑋12 + 𝑋22 + 𝑋32 + 𝑋42 + 𝑋52 = 20
𝑋13 + 𝑋23 + 𝑋33 + 𝑋43 + 𝑋53 = 20
Que pasa si no queremos que dos plantas se construyan a la vez?

Ejem:

Y1 + Y2 <= 1

En este caso solo una de las dos podrá realizarse.

Otros casos prácticos

Ubicación de sucursales bancarias

El departamento de planeación a largo plazo de Ohio Trust Company considera ampliar

sus operaciones en una región de 20 condados en el noreste de Ohio. En la actualidad,
Ohio Trust no cuenta con una sede social en ninguno de los 20 condados. Según las leyes
bancarias de Ohio, si un banco establece su sede social en cualquiera de los condados,
pueden establecerse sucursales bancarias en ese condado y en cualquier otro adyacente.
No obstante, para establecer una sede social, Ohio Trust debe obtener la aprobación
para un banco nuevo del superintendente de bancos del estado o comprar un banco
existente.

Como paso inicial en su planeación, a Ohio Trust le gustaría determinar el número

mínimo de sedes sociales necesarias para hacer negocios en toda la región de 20
condados

9
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

Xi = 1 si se establece sede social; 0 en caso contrario.

FO: X1+X2+X3……………….+X20

Minimizar
El banco puede ubicar sucursales en un condado si éste contiene una sede social o es adyacente
a otro con una sede social. Por tanto, el programa lineal necesita una restricción para cada
condado. Por ejemplo, la restricción para el condado de Ashtabula es

X1+X2+X12+X16 >= 1 (Ashtabula)

X1+X2+X3+X12 >= 1 (Lake)

10
Curso: Métodos Cuantitativos Periodo 2021-1
Tema: Programación Lineal Entera Profesor: Yussef Mori Wissar

11