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 serelacionaban 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 deprogramació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 deprogramació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 deprogramació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 condicionesdel 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.

Unasubclase 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 debemosrelacionarnos 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 lasrestricciones 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ónlineal 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...