Programacion entera

A continuación se hablara sobre programación entera en el cual el método simplex supone que todas las variables son continuas generalmente da soluciones no enteras. Cuando las variables de decisión no pueden dividirse la solución del simplex no puede usarse en forma directa. El redondeo de una solución optima es peligroso, ya que no es obvio el hecho que la solución resulte ser optimo o siquiera posible.

Programación entera

Es el nombre que recibe un conjunto de técnicas que pueden usarse para encontrar la mejor solución entera posible para un problema de pl. Un modelo de programación entera es aquel que contiene restricciones y una función objetivo idénticas a las formuladas en programación lineal, la única diferencia en que una o más variables de decisión deben tomar valor entero en la solución final.

CLASIFICACIÓN:

Existen tres tipos de modelos por programación entera

A) PURA: Son modelos similares a los de programación entera

Forma General:

Max (Min ) = A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn

Sujeto a : A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi

No negatividad : Xi >= 0 y Entero

B) BINARIA : Estos modelos lineales , las variables sólo toman valores 0 y 1 , son usadas para uso probabilístico Donde 0 se rechaza la opción y 1 se acepta la opción

Forma General :

Max (Min ) = A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn

Sujeto a : y1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad : yi >= 0 v 1

C) MIXTA : En estos tipos de modelos , integra las variables puras y las mixtas

Max (Min ) = A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn+A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn

Sujeto a :

A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi

y1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad :

Xi >= 0 y Enteros

Xi >= 0 v 1

MODELOS ENTEROS PUROS

Son aquellos modelos en los que todas las variables son enteras incluyendo variables de holgura o de exceso.

Ejemplo de modelo:

Ejemplo de planteamiento: El problema de transporte

Un planteamiento que genera un entero puro puede ser el siguiente:

Una empresa fabrica tres tipos de tenis: de lujo, normal y económico. Las contribuciones a las utilidades son $270, $200 y $230 respectivamente. Las necesidades en el departamento de ensamble en minutos son 1, 2 y 3 respectivamente. El departamento de paquetería para cada tipo de tenis es: 2, 2 y 3 minutos respectivamente. Se tienen 1000 minutos en el depto de ensamble y 1200 minutos en el depto de paquetería.

Para la resulución de este tipo de modelos tenemos:

-Método de Plano de Corte

- Algoritmo Fraccional de Gomory

- Algoritmo Entero Puro de Gomory

- Método de Ramificación y Acotamiento

- Algoritmo de Land – Doig.

MODELO ENTERO MIXTO

Se tendrán tanto variables continuas como variables enteras.

Ejemplo

...