4677_3. material informatico sesion 14-programacion lineal entera
Post on 14-Jan-2016
673 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
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
top related