Modelos de programacion lineal

INDICE

MODELOS DE PROGRAMACION LINEAL 3

PROBLEMAS 3

Problema 1 3

Problema 2 4

PROGRAMACION LINEAL SIMPLEX 5

PROGRAMACION LINEAL ENTERA 6

Definición 6

Programación Entera: Ejemplos 6

Programación Entera Pura 7

Programación Entera Mixta 7

Programación Entera Binaria 8

PROGRAMACIÓN LINEAL CON ENTEROS 8

Ejemplos 9

CONCLUSIONES 15

CONCLUSIÓN 15

BIBLIOGRAFÍA 15

1. MODELOS DE PROGRAMACIÓN LINEAL

Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.

Problema 1

Para representar y – x < 2, representa la recta y – x = 2. Después, para decidir a cuál de los dos semiplanos corresponde la inecuación, toma un punto cualquiera exterior a la recta y comprueba si sus coordenadas verifican o no la desigualdad.

Análogamente, representa:

y – x < 2 + x + 5y > 10 x + 2y < 16 2x + y < 20

Representa el recinto formado por las siguientes condiciones:

y – x < 2

x + 5y > 10

x+2y < 16

2x + y < 20

Problema 2

2x + y > 20

2x – y < 20

2. PROGRAMACION LINEAL SIMPLEX

servicio Mesas X1 Sillas X2 Cantidad disponible de rec.

Planta 1 2 2 16

Planta 2 1 5 15

Planta 3 5 1 17

ganancia 30 40

Máximo 30X1+40X2

2X1+2X2<16

X1+5X2<15

5X1+X2<17

GRAFICO

3. PROGRAMACION LINEAL ENTERA

3.1. DEFINICION

Un modelo de programación entera es un modelo que contiene restricciones y una función objetivo idénticas a las formuladas por planeación lineal. La única diferencia es que una o más de las variables de decisión tienen que tomar un valor entero en la solución final.

Los modelos de programación entera son una extensión de los modelos lineales en los que algunas variables toman valores enteros.

Con frecuencia las variables enteras solo toman valores en 0-1, ya que este tipo de variables permiten representar condiciones lógicas.

Este tipo de modelos permite representar sistemas mucho más complejos.

A cambio, la resolución de los mismos se complica excesivamente. No se puede utilizar la suavidad de las funciones para inferir el comportamiento de las mismas cerca del óptimo.

Problemas con unas solas decenas de variables pueden ser casi imposibles de resolver.

3.2. PROGRAMACIÓN ENTERA: EJEMPLOS

En general, un problema de Programación Lineal Entera puede surgir por varios motivos:

Directos: las variables que se utilizan son cuantitativas y enteras.

Codificados: Se utilizan variables enteras para representar el cumplimiento o no de ciertas condiciones (normalmente son variables 0 − 1).

Transformados: Las variables enteras aparecen para facilitar la modelización de algunas condiciones (implicaciones, disyunciones, etc.)

Existen tres tipos de modelos de programación:

• Pura

• Mixta

• Binaria

3.3. PROGRAMACIÓN ENTERA PURA

Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisión tengan valores enteros.

Todas las variables de decisión tienen valores enteros

X Si I = {1, . . . , n} ⇒ Programación Lineal Entera Pura.

Min 6x1 + 5x2 + 4x3

S.a. 108x1 + 92x2 + 58x3 >= 576

7x1 + 18x2 + 22x3 >= 83

x1, x2, x3 ><0 y enteros

Es un modelo entero puro. Sin las restricciones adicionales de que x1, x2, x3 sean enteras (o sea las condiciones de integralidad) sería un problema de programación lineal.

3.4. PROGRAMACION ENTERA MIXTA

Algunas de las variables de decisión

...