Programacion entera

PROGRAMACIÓN ENTERA.

INTRODUCCIÓN

Los problemas de programación lineal en que se requiere que algunas o todas las variables tomen valores enteros, son de “programación entera”. La programación entera ha llegado a ser un área muy especializada de la ciencia de la administración.

Parte del problema de la programación entera radica en la diferencia que existe entre la programación lineal yla entera, en la programación lineal se maximiza o minimiza una función sobre una región de factibilidad convexa, mientras que al utilizar los métodos de programación entera se maximiza una función sobre una región de factibilidad que generalmente no es convexa. De tal manera que la programación entera tiene mas complicaciones que la programación lineal.

La Programación Lineal es unprocedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.

Consiste en optimizar (minimizar o maximizar) una función lineal, que denominaremos función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante unsistema de inecuaciones lineales.

El propósito de este trabajo es observar de una manera práctica y objetiva, la aplicación de la programación entera en la resolución de un problema de maximización de utilidades.



DEFINICIÓN DEL PROBLEMA
Un productor de cables de luz se encarga de realizar dos distintos tipos de cable, el tipo A que le da unautilidad de 30.00 Pesos y el tipo B que le da 20.00 Pesos de utilidad. Este productor cuenta mensualmente con 900 metros de cable de corriente del cual cada tipo de cable ocupa 150 metros.
Estos cables también ocupan plástico protector del mismo, el cable A ocupa un total de 300 metros al mes y el tipo B usa 200 metros mensualmente y la cantidad de plástico disponible mensual es de 1000 metros.El productor quiere maximizar su utilidad teniendo en cuenta las restricciones que tiene en cuanto a recursos.


FORMULACIÓN DEL MODELO
Con base en los datos que se presentan anteriormente se realizará el formulación del modelo, la cual queda de la siguiente manera.
Máx. Z = 5X1 + 2X2
2X1 + 2X2 ≤ 9
3X1 + x2 ≤ 11
X1, X2 ≥ 0
X1, X2 enteros







DESARROLLODEL MODELO

Encontraremos la tabla óptima de un problema entero.
El problema se tiene que plantear primero de la forma estándar
Z - 5X1 - 2X2 = 0
S.A:
2 X1 +2 X2 + S1 = 9
3 X1 + X2 + S2 = 11
X1, X2, S1, S2 ≥ 0

BASE | Z | X1 | X2 | S1 | S2 | Sol. |
Z | 1 | -5 | -2 | 0 | 0 | 0 |
S1 | 0 | 2 | 2 | 1 | 0 | 9 |
S2 | 0 | 3 | 1 | 0 | 1 | 11 |

BASE | Z | X1 | X2 | S1 |S2 | Sol. |
Z | 1 | 0 | -1/3 | 0 | 5/3 | 55/3 |
S1 | 0 | 0 | 4/3 | 1 | -2/3 | 5/3 |
X1 | 0 | 1 | 1/3 | 0 | 1/3 | 11/3 |

TABLA ÓPTIMA

BASE | Z | X1 | X2 | S1 | S2 | Sol. |
Z | 1 | 0 | 0 | ¼ | 3/2 | 18.75 |
X2 | 0 | 0 | 1 | ¾ | -1/2 | 1.25 |
X1 | 0 | 1 | 0 | -1/4 | 1/2 | 3.25 |

Como X1 y X2 no son enteras se debe hacer un corte
Z + 0.25 S1 + 1.5 S2 = 18.75
(0.25 – 0)S1 +(1.5 – 1) S2 ≥ 18.75 – 18
0.25 S1 + 0.5 S2 ≥ 0.75
En este método se tiene que agregar una variable superflua que consideraremos cono S3
Base | Z | X1 | X2 | S1 | S2 | S3 | Sol. |
Z | 1 | 0 | 0 | 0.25 | 1.5 | 0 | 18.75 |
X2 | 0 | 0 | 1 | 0.75 | -0.5 | 0 | 1.25 |
X1 | 0 | 1 | 0 | -0.25 | 0.5 | 0 | 3.25 |
S3 | 0 | 0 | 0 | -0.25 | -1.5 | 1 | -0.75 |

DUAL SIMPLEX
Base | Z | X1 | X2 |S1 | S2 | S3 | Sol. |
Z | 1 | 0 | 0 | 0 | 1 | 1 | 18 |
X2 | 0 | 0 | 1 | 0 | -2 | 3 | -1 |
X1 | 0 | 1 | 0 | 0 | 1 | -1 | 4 |
S1 | 0 | 0 | 0 | 0 | 2 | -4 | 3 |

Base | Z | X1 | X2 | S1 | S2 | S3 | Sol. |
Z | 1 | 0 | 1/2 | 0 | 0 | -5/2 | 17.5 |
S2 | 0 | 0 | -1/2 | 0 | 1 | -3/2 | 0.50 |
X1 | 0 | 1 | 1/2 | 0 | 0 | 1/2 | 3.5 |
S1 | 0 | 0 | 1 | 1 | 0 | -1 | 2 |



Siguiendo...