Programacion lineal

Programación lineal
El hecho de que la función objetivo del problema sea lineal y el espacio de soluciones factibles sea intersección de hiperplanos y semiespacios, implica, entre otras cosas, quetodo programa lineal es convexo, por lo que se cumplen automáticamente todos los resultados de la programación convexa vistos hasta ahora. Destacar, por tanto, tres propiedades de los programaslineales heredadas de los programas convexos:
* Todo óptimo es global.
* Las condiciones necesarias de primer orden (condiciones de Lagrange o Kuhn-Tucker) son además suficientes.
* Losprogramas lineales no son estrictamente convexos, por lo tanto no se tiene garantizada la unicidad de solución. Sin embargo, si existen dos soluciones distintas, también es solución cualquiercombinación lineal convexa de ellas.
Desde un punto de vista práctico, algunas de las ventajas de los programas lineales con respecto a los no lineales son las siguientes:
* Resultan más fáciles dedefinir y formular.
* Permiten trabajar de manera eficiente con mayor número de variables de decisión.
* Se adaptan mejor al tratamiento algorítmico con computadores, aprovechando larapidez de cálculo de éstos.
Las principales características de esta formulación de problemas lineales son:
* Se trata de minimizar una función lineal homogénea.
* Todas las restricciones sonde igualdad, siendo el término independiente mayor o igual que cero.
* Las variables de decisión solo pueden tomar valores no negativos.
Todo programa lineal, independientemente de la forma enla que esté dado, puede plantearse en la forma estándar; para ello es necesario efectuar una serie de manipulaciones sobre el programa.
* En primer lugar, ya se ha comentado el hecho de quemaximizar una función es equivalente a minimizar su opuesta. La primera manipulación es por tanto convertir el problema a uno de minimización.
* Si la función objetivo fuera de la forma...