Programación Lineal

Ej. 7 Suponga que el número mínimo de autobuses requerido en la i-ésima hora del día es bi, i=1,2,3,...,24. Cada autobús trabaja 6 horas consecutivas. Si el número de autobuses en el período i excede el mínimo requerido bi, se incurre en un costo por exceso, ci, por autobús-hora. Formule el problema como un problema de P.L. de tal manera que se minimice el exceso del costo total originado. [2]

Sol. Si se definen las variables de decisión como: xi= Número de autobuses que comienza en la hora i, luego la función objetivo se podrá plantear como:

y plantear las restricciones funcionales y de no negatividad como:

Solución a problemas de Programación Lineal P.L.

Un procedimiento general algebraico para resolver problemas de P.L. es el conocido con el nombre de método Simples desarrollado por George Dantzig en 1947.

Método gráfico o geométrico (2 variables): Tómese como ejemplo inicial el Ej. 1 [1]

Max Z=3x1+5x2

Sujeto a:

x1  4

2x2 12

3x1+2x218

y

x10, x20.

Una frontera de restricción es el límite permitido por una restricción, en el caso de dos variables es una recta, en tres un plano, etc. Una solución en vértice es la intercepción de dos fronteras de restricción, una solución en un vértice que pertenece al espacio de soluciones se llama solución factible en vértice (FVE), para un problema de P.L. con n variables de decisión, cada una de sus soluciones en los vértices se encuentra en la intercepción de por lo menos n fronteras de restricción. FEV adyacentes son aquellas que comparten n-1 fronteras de restricción. Dos soluciones FEV están conectadas por un segmento de recta (pertenecientes a las fronteras de restricción) llamado orilla o arista de la región factible. Del ejemplo tenemos las siguientes soluciones FEV y sus correspondientes soluciones FEV adyacentes:

Soluciones FEV Soluciones FEV adyacentes

(0,0) (0,6) y (4,0)

(0,6) (2,6) y (0,0)

(2,6) (4,3) y (0,6)

(4,3) (4,0) y (2,6)

(4,0) (0,0) y (4,3)

Tabla 10, Soluciones FEV Ej. 1

Prueba de optimalidad: Si una solución FEV no tiene soluciones FEV adyacentes que sean mejores bajo la perspectiva de Z, entonces ésa debe ser una solución Optima.

Solución geométrica.

Inicialización: Elija (0,0) como SFEV inicial

Prueba de optimalidad: pruebe la existencia de soluciones adyacentes que mejoren el valor de Z.

En caso de existir una mejor solución itere

1. Muévase sobre la arista que más aumenta (disminuye) el valor de Z.

2. Deténgase en la frontera de restricción.

3. Tome ese nuevo punto como solución de inicio.

En caso contrario la Solución FEV es la solución

...