Profesor: Carlos Garca Palacios 1

SESIN N 14

PROGRAMACIN LINEAL ENTERA En esta sesin se estudia una clase de problemas que se modelan como programas

lineales con el requerimiento adicional de que una o ms variables deben ser

nmeros enteros. Estos problemas se conocen como programas lineales enteros. Si todas las variables deben ser enteros, tenemos un programa lineal slo con

enteros. Si algunas de las variables, pero no todas, deben ser enteros, se habla de

un programa lineal entero mixto. En muchas aplicaciones de la programacin lineal

entera, se requiere que una o ms variables enteras sean iguales a 0 o 1. Estas

variables se llaman variables 0-1 o binarias. Si todas las variables son 0-1, tenemos un programa lineal con enteros 0-1. Si se necesita que todas las variables sean

enteras, tenemos un programa lineal slo con enteros. A continuacin se presenta un modelo de programacin lineal de dos variables slo con enteros:

Si omitimos la frase y enteras de la ltima lnea de este modelo, tenemos el

conocido programa lineal de dos variables. El programa lineal que resulta de omitir

los requerimientos de enteros se llama relajacin PL del programa lineal entero.

Si se requiere que algunas de las variables, pero no necesariamente todas, sean

enteros, tenemos un programa lineal entero mixto. A continuacin se presenta un programa lineal entero mixto de dos variables:

Profesor: Carlos Garca Palacios 2

CASO PRCTICO:

Eastborne Realty tiene $2 millones disponibles para la compra de una nueva

propiedad para alquiler. Despus de una investigacin inicial, Eastborne redujo las

alternativas de inversin 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, despus de deducir los pagos hipotecarios y los gastos de operacin, sea de

$10,000 por vivienda y $l5,000 por edificio de departamentos. Al propietario de

Eastborne le gustara determinar el nmero de viviendas y de edificios de

departamentos a comprar para maximizar el flujo de efectivo anual.

Comenzamos por definir las variables de decisin como sigue:

T = nmero de viviendas

A = nmero de edificios de departamentos

La funcin objetivo para el flujo de efectivo (en miles de dlares) es

Max 10T + 15A

Tres restricciones deben cumplirse:

+ Fondos disponibles + Tiempo del gerente Casas urbanas disponibles

Profesor: Carlos Garca Palacios 3

Utilizando el procedimiento de solucin grfica, la solucin de programacin lineal

ptima se tiene: T = 2.479 viviendas y A = 3.252 edificios de departamentos. El valor

ptimo de la funcin objetivo es 73.574, lo cual indica un flujo de efectivo anual de

$73,574. Por desgracia, Eastborne no puede comprar nmeros fraccionarios de

viviendas y edificios de departamentos; es necesario hacer otro anlisis. Redondeo para obtener una solucin con enteros En muchos casos, una solucin no entera puede redondearse para obtener una

solucin aceptable con enteros. Por ejemplo, una solucin de programacin lineal

para un problema de programacin de la produccin podra exigir producir de

15,132.4 cajas de cereal. La solucin con enteros redondeada de 15,132 cajas

Profesor: Carlos Garca Palacios 4

quiz, tendra un impacto mnimo en el valor de la funcin objetivo y en la factibilidad

de la solucin. El redondeo sera un enfoque sensible. De hecho, siempre que el

redondeo tiene un impacto mnimo sobre la funcin objetivo y las restricciones, la

mayora de los administradores o gerentes lo considera aceptable.

Una solucin casi ptima est bien. Sin embargo, el redondeo no siempre es una

buena estrategia. Cuando las variables de decisin adoptan valores pequeos que

tienen un impacto importante en el valor de la funcin objetivo o en la factibilidad, se

necesita una solucin con enteros ptima. Retomemos el problema de Eastborne

Realty y examinemos el impacto del redondeo. La solucin ptima de la relajacin

PL para Eastborne Realty dio como resultado T = 2.479 viviendas y A = 3.252

edificios de departamentos. Como cada vivienda cuesta $282,000 y cada edificio

$400,000, puede esperarse que el redondeo a una solucin con enteros tenga un

impacto econmico significativo en el problema.

Suponga que redondeamos la solucin para la relajacin PL para obtener una

solucin con enteros T = 2 y A = 3, con un valor de la funcin objetivo de 10(2) +

15(3) = 65. El flujo de efectivo anual de $65,000 es considerablemente menor que el

de $73,574, proporcionado por la solucin para la relajacin PL. Existen otras

posibilidades de redondeo? La exploracin de otras alternativas de redondeo

muestra que la solucin con enteros T = 3 y A = 3 no es factible porque requiere ms

fondos que los $2,000,000 que Eastborne tiene disponibles. La solucin de

redondeo de T = 2 y A =4 tampoco es factible por la misma razn. En este punto el

redondeo ha conducido a dos viviendas y tres edificios de departamentos con un

flujo de efectivo anual de $65,000 como la mejor solucin con enteros factible para el

problema. Por desgracia no sabemos si sta es la mejor solucin con enteros para el

problema. El redondeo a una solucin con enteros es un mtodo de prueba y error.

Para cada solucin redondeada debe evaluarse la factibilidad, as como su impacto

en el valor de la funcin objetivo. Incluso en casos donde una solucin redondeada

es factible, no tenemos garanta de que hemos encontrado la solucin con enteros

ptima. En breve se ver que la

solucin redondeada (T = 2 y A = 3) no es ptima para Eastborne Realty.

Profesor: Carlos Garca Palacios 5

Solucin grfica del problema slo con enteros La fi gura 2 muestra los cambios en el procedimiento de solucin grfica de la

programacin lineal requeridos para resolver el problema de programacin lineal

entera de Eastborne Realty. Primero, la grfica de la regin factible se traza

exactamente como en la relajacin PL del problema. Luego, debido a que la solucin

ptima debe tener valores enteros, identificamos las soluciones enteras factibles con

los puntos mostrados en la fi gura 2. Por ltimo, en vez de mover la recta de la

funcin objetivo al mejor punto extremo en la regin factible, la movemos en una

direccin que mejora lo ms lejos posible hasta alcanzar el punto (punto entero

factible) que proporciona el mejor valor de la funcin objetivo. Al observar la fi gura

11.2, vemos que la solucin con enteros ptima ocurre en T = 4 viviendas y A = 2

edificios de departamentos. El valor de la funcin objetivo es 10(4) +15(2) = 70,

proporcionando un flujo de efectivo anual de $70,000. Esta solucin es

considerablemente preferible que la mejor solucin encontrada por medio del

redondeo: T =2, A = 3 con un flujo de efectivo anual de $65,000. Por tanto, el

redondeo no habra sido la mejor estrategia para Eastborne Realty.

Profesor: Carlos Garca Palacios 6

PROGRAMACIN LINEAL ENTERA