Programacion Lineal Y Redes

Introducción

El problema general de programación lineal fue desarrollado inicialmente y aplicado en 1947 por George B. Dantzig, Marshall Wood y sus asociados del Departamento de la fuerza aérea de los Estados Unidos (existe también un reconocimiento al matemático y economista soviético L.V. Kantorovich, quien a principios de 1939, formuló y resolvió problemas de programación lineal que se relacionaban con la planeación y organización de la producción).

En esa época (1947) este grupo fue llamado para investigar la factibilidad de las matemáticas aplicadas y técnicas relacionadas con problemas de planeación y programación militar.

Estos cuestionamientos condujeron a la propuesta de Dantzig de ver las interrelaciones entre actividades de organizaciones grandes como tipos de modelos de programación lineal y al programa de optimización determinado por una minimización de una función lineal objetivo.

Estas ideas se desarrollaron en un grupo de investigación llamado SCOOP (Scientific Computation of Optimimum Programs). Su principal contribución fue el desarrollo y la aplicación formal de modelos de programación lineal.

Antes del enunciado inicial del problema general de programación lineal (1947) junto con el método simplex, existían un número de problemas (algunos no resueltos) que trataban con la optimización de una función lineal sujeta a restricciones lineales. Entre algunos de los problemas están:

Problema de transporte ( Hitchcock 1941 y de manera independiente Koopmans 1947 )

Dieta ( Stiegler 1945 )

La primera solución exitosa de un problema de programación lineal en una computadora de alta velocidad ocurrió en enero de 1952 ( Oficina Nacional de Estándares ).

Los problemas de programación están relacionados con el uso o asignación eficiente de recursos limitados para conseguir objetivos deseados. Se caracteriza por un número grande de soluciones que satisface las condiciones básicas de cada problema.

Una solución que satisface las condiciones del problema y la función objetivo se llama solución óptima.

Ejemplo:

Una compañía manufacturera que debe determinar la combinación de recursos disponibles que le permita manufacturar productos en una forma que satisfaga su programa de producción y que maximice su beneficio.

Condición básica.-

Limitación de recursos disponibles.

Programa de producción.

Objetivo.-

Maximizar ganancia.

Una subclase especial de problemas de programación son los problemas de programación lineal ( relaciones lineales : ) .

El enunciado de un problema de programación lineal incluye un conjunto de ecuaciones lineales que representan las condiciones del problema y de una función lineal que expresa el objetivo del problema.

Para resolver un problema de programación lineal debemos relacionarnos con las soluciones del conjunto de ecuaciones lineales asociado.

Ejemplo:

El sistema de ecuaciones tiene una solución única

tiene una infinidad de soluciones.

Para cada valor de x2 ( x1) hay un valor correspondiente de x1 ( x2 ).Si se restringen las variables a valores no negativos tenemos:

Siguen existiendo una infinidad de soluciones. La adición de las restricciones de no negatividad tiene como resultado una menor libertad de acción.

Los sistemas que tienen más variables que ecuaciones se llaman indeterminados y en general, estos sistemas no tienen solución o tienen una infinidad de soluciones .

Ejemplo:

Modelo general del problema de programación lineal

Cj j=1 , 2 , . . . , n => coeficientes de costo

Todo problema de programación lineal tiene:

- Ninguna solución en términos de los valores no negativos de las variables.

- Una solución no negativa que da un valor infinito a la función objetivo.

- Una solución no negativa que da un valor finito a la función objetivo.

Ejemplos de problemas de programación lineal

El problema de transporte.

Un fabricante desea enviar un número de unidades de cierto artículo desde varios almacenes a distintos destinos. Cada destino requiere cierto número de unidades del artículo y cada almacén puede proveer hasta cierta cantidad.

m = número de almacenes

n = número de destinos

ai = cantidad total de artículos disponibles para envío en el almacén i.

bj = requerimiento total del destino j.

xij = cantidad de artículos enviados desde el almacén i hacia el destino j.

Suposición.- Cantidad total disponible = total requerido

Con m = 2 y n = 3 tenemos:

Destinos

Almacenes 1 2 3

1 x11 x12 x13 a1

2 x21 x22 x23 a2

b1 b2 b3

x11 + x12 + x13 = a1 => Cantidad total enviada desde el almacén 1.

x12 + x22 = b2 => Cantidad total enviada al destino 2.

Ci = costo por envío de una unidad del almacén i al destino j ( relación lineal).

Se desea determinar cuántas unidades enviar de cada almacén a cada destino al menor costo. Se requiere que xij  0

Tenemos

...