Ciencia » Programación Mixta Entera Lineal

Definición de Programación Mixta Entera Lineal

La Investigación Operativa trabaja el modelado y resolución de una gran variedad de problemas que requieren optimizar (maximizar o minimizar) el valor de una función, llamada función objetivo, dependiente de una o varias variables, sujeto a un conjunto de restricciones.

Estos problemas se dividen en diferentes categorías de acuerdo al tipo de variables y características de la función objetivo y restricciones. Estas restricciones pueden ser del tipo de igualdad, desigualdad o ambas.

Los problemas lineales, esto es, los problemas en los cuales tanto la función objetivo como las restricciones son lineales en las variables, ocupan un lugar destacado dentro de los problemas de investigación operativa, ya que en general son más fácil de resolver que los no lineales. Dentro de los problemas lineales, existen las siguientes clasificaciones de acuerdo al tipo de variables se presenten:

- Si las variables son continuas estamos en presencia de un problema de Programación Lineal (LP). Esquemáticamente, estos problemas se modelan de la forma

O de manera equivalente:

También es usual representarlo de forma matricial, resultando:

donde

- Si las variables son enteras, es decir, sólo pueden tomar valores enteros, se trata de un problema de Programación Lineal Entera (IP). Esquemáticamente un problema IP es de la forma

donde a es un vector de 1 x n,

x es un vector de n x 1,

C es una matriz de m x n,

b es un vector de m x 1.

En particular, si las variables sólo pueden tomar los valores 0 o 1, el problema se denomina de Programación Binaria (BIP):

donde a es un vector de 1 x n,

y es un vector de n x 1,

C es una matriz de m x n,

b es un vector de m x 1.

- Si en el modelo se cuenta tanto con variables continuas como enteras, estamos en presencia de un problema de Programación Lineal Mixta Entera (Mixed Integer Linear Programming en inglés y sus siglas son MILP). Esquemáticamente un problema MILP se modela de la forma

donde:

a es un vector de 1xn,

k es un vector de 1xp,

x es un vector de nx1,

y es un vector de px1,

C matriz de mxn,

D matriz de mxp,

b vector de mx1.

Problemas clásicos

Problema de asignación

El problema de asignación plantea la situación en que se tienen n trabajos y n máquinas (también pueden ser clases/profesores, rutas/buses, etc.) donde cada trabajo

debe ser asignado a una única máquina

y el costo de asignar i a j es cij. El objetivo consiste en encontrar la asignación con mínimo costo.

Modelado del problema:

Este es un problema de Programación Binaria BIP. Se introduce la variable binaria

y luego, el modelado resulta de la siguiente forma:

Cabe remarcar que este modelo asigna exactamente una tarea a cada máquina. Si se elimina la primera restricción, podrían asignarse varios trabajos, o incluso todos, a una misma máquina.

El problema de localización de fábrica (facility location)

En este tipo de problemas, se debe decidir sobre la instalación de hasta n plantas para satisfacer la demanda de m clientes donde cada planta tiene una capacidad ai y un costo fijo de instalación fi, i = 1,…,n. El costo por unidad de material enviado desde la planta i al cliente j es cij, para i = 1,…,n; j = 1,…,m; y la demanda del cliente j es dj.

Modelado del problema:

Lo que se debe decidir es cuáles plantas instalar y cuánto material se enviará de las plantas instaladas a cada cliente de modo que se satisfagan las demandas. Por lo tanto, se definen las variables:

Luego, el modelo del problema resulta:

 
 
Autor: Regina Meyer, Lic. en Matemática Aplicada. | Sitio: Definición ABC | Título: Programación Mixta Entera Lineal | Fecha: Jul. 2021 | URL: https://www.definicionabc.com/ciencia/programacion-mixta-entera-lineal.php
 
 
Temas en Programación Mixta Entera Lineal

Redes Sociales