Programacion entera para modelos lineales

Programacion entera para modelos lineales

INTRODUCCIÓN

Un problema de optimización o programación matemática consiste en maximizar o minimizar una función real dado un dominio definido. De forma general, la optimización se basa en el descubrimiento de los «mejores valores» de alguna función objetivo (FO), existiendo una variedad de diferentes tipos de funciones objetivo y diferentes tipos de dominios. Al procedimiento o algoritmo matemático mediante el cual se resuelve un problema formado por una función objetivo lineal y un sistema de ecuaciones o inecuaciones lineales se le llama programación lineal.

Existen casos de modelos lineales en los que por razones físicas se necesita que el valor óptimo de la FO sea resultado de valores enteros para todas las variables de decisión, el algoritmo capaz de resolver este problema se conoce como «programación lineal entera pura» (PLEP). El hecho de conocer las variables de decisión que den solución a un modelo de programación lineal, no significa necesariamente encontrarse cerca de las variables que den solución a la PLEP del modelo. La aproximación al valor entero más cercano de las variables de decisión no siempre conduce a la solución óptima del modelo y en otros casos provoca la violación de algunas de las restricciones. Para demostrar lo expresado se presentan los siguientes ejemplos:

Ejemplo (1)

[pic 1]

[pic 2]

[pic 3]

[pic 4]

[pic 5]

Donde la ecuación (1) es la FO que, en este caso, se busca su máximo valor (ver figura 1).[pic 6]

Las ecuaciones (2), (3), (4) y (5) son las restricciones del dominio, es decir, delimitan lo que se llama el espacio factible, que se ilustra en la figura 1.

Como muestra dicha figura 1 la solución óptima de la PL en este ejemplo es Z(x,y)=5,2 para [x=0,4; y=1,2]. Una aproximación de las variables a sus valores enteros más cercanos sería [x=0; y=1] resultando en Z(x,y)=3. Sin embargo, véase que el punto [x=1; y=0] tiene Z(x,y)=4 lo que prueba que dicha aproximación no garantiza la solución del modelo de PLEP .

Ejemplo (2)

[pic 7]

[pic 8]

[pic 9]

[pic 10]

La solución óptima en este ejemplo es Z(x,y)=[128/3] para [x=2; y=8/3]. Una aproximación de las variables a sus valores enteros más cercanos queda [x=2; y=3] la cual se encuentra fuera del dominio del modelo incumpliendo con una de las restricciones, ver figura 2.

                [pic 11]

Por estas razones para obtener la solución óptima como resultado de variables enteras (PLEP) ha surgido la necesidad de complementar algoritmos utilizados en la PL con estrategias de PLEP. Una de las más eficaces estrategias es el método de ramificación y acotación (branch and bound). Este artículo propone una función programada en MATLAB capaz de resolver modelos de PLEP utilizando dicho método como base matemática.

Dicha herramienta, además de agilizar el proceso manual, extiende sus objetivos a ofrecer notables ventajas sobre otras estrategias [1].

PROGRAMACIÓN ENTERA BINARIA

La programación entera binaria es un método perteneciente a la programación lineal, por lo que su base es un algoritmo matemático que tiene como finalidad resolver un problema indeterminado formulado a través de ecuaciones lineales, optimizando así una función objetivo también lineal que generalmente se refiere a costo o a tiempo.

La programación binaria se utiliza en problemas de asignación o de toma de decisiones enfocadas a hacer o no una tarea, entre sus campo de aplicación más comunes se encuentra el despacho de envíos, el diseño de redes, la elección de un sitio, el diseño de redes, la ubicación del personal y la programación de actividades, que es la aplicación objeto de estudios en este documento [2].

Problema de Inclusión de Costos Fijos en Programación Entera.

La estructura de cobro utilizadas en general por las compañías de servicios donde el cliente debe pagar un valor fijo sólo por su utilización (independiente del nivel de consumo y/o eventualmente acotado a un máximo permitido) y un valor variable proporcional al consumo, son una práctica común en el esquema de fijación de precios. Esto suele ser el caso de las compañías de luz, agua, gas, teléfono, entre otras, donde el sólo hecho de tener una red operativa genera costos para la empresa los cuales son traspasados en parte o en su totalidad a los usuarios en un cargo fijo o de mantención más un cargo variable por consumo [3].

 El artículo que presentamos a continuación busca, desde la perspectiva del cliente, minimizar el pago asociado a una compra de insumos médicos a través de un modelo de Programación Entera, lo que constituye un problema de inclusión de costos fijos. Cabe destacar que la complejidad del problema es menor y dado los datos se podría resolver por simple inspección, no obstante, nuestro interés es mostrar un marco de análisis pertinente a este tipo de problemas.

PROGRAMACION ENTERA BINARIA DE COSTO FIJO.

ENUNCIADO.[pic 12]

El departamento de seguridad y salud a cargo (Ing. Adrian Bravo e Ing. Cesar Ramírez) del Hospital Teodoro Maldonado Carbo se encuentra en la necesidad de adquirir 10.000 Kit de protección personal para los profesionales de la salud, cada Kit contiene 1 Mascarilla N95, 1 par de Guantes de látex, 1 protector facial de acetato, 1 traje anti fluidos, 1 par de cubre zapatos quirúrgicos.

Se recibió la proforma de 3 proveedores.

• El proveedor 1 nos detalla que el costo por cada kit de protección nos cuesta $40, adicional nos hace un recargo de $5000 por concepto de entrega.
• El proveedor 2 nos detalla que el costo por cada kit de protección nos cuesta $30, adicional nos hace un recargo de $4000 por concepto de entrega.
• El proveedor 3 nos detalla que el costo por cada kit de protección nos cuesta $20, adicional nos hace un recargo de $6000 por concepto de entrega.

Nos menciona el vendedor 1 solo tiene en stock 4.000.

Nos menciona el vendedor 2 solo tiene en stock 8.000.

...