Problema de programación lineal

Ejemplo de un problema de programación lineal en que la función objetivo debe maximizarse. Considérese el siguiente problema de producción con dos variables:
El granjero Lopez tiene 480 hectáreas en la que se puede sembrar ya sea trigo o maíz. El calcula que tiene 800 horas de trabajo disponible durante la estación crucial del verano. Dados márgenes de utilidad y los requerimientos laboralesmostrados a la derecha, ¿Cuántas hectáreas de cada uno debe plantar para maximizar su utilidad?¿Cuál es ésta utilidad máxima? | Maiz: Utilidad: $40 por hrs. Trabajo: 2hs  por hrs. Trigo: Utilidad:  $30 por hrs. Trabajo: 1hs  por hrs. |
Solución: Como primer paso para la formulación matemática de este problema, se tabula la información dada (Tabla 1). Si llamamos x a las hectáreas de maíz e y alas hectáreas de trigo. Entonces la ganancia total P, en dólares, está dada por:
P=40x+30y
Que es la función objetivo por maximizar.
  | Maíz | Trigo | Elementos disponibles |
Horas | 2 | 1 |   |
Hectáreas | 1 | 1 | 800 |
Utilidad por unidad | $40 | $30 | 480 |
La cantidad total de tiempo par hectáreas para sembrar maíz y trigo está dada por 2x+y horas que no debe exceder las 800 horasdisponibles para el trabajo. Así se tiene la desigualdad:
2x+y800  
En forma análoga, la cantidad de hectáreas disponibles está dada por x+y, y ésta no puede exceder las hectáreas disponibles para el trabajo, lo que conduce a la desigualdad.
Por último, si no queremos tener pérdidas, x y y no pueden ser negativa, de modo que 
x0
y0  
En resumen, el problema en cuestión consiste enmaximizar la función objetivo P=40x+30y 
sujeta a las desigualdades
2x+y800
x+y480
x0
y0
 
Solución Gráfica
Los problemas de programación lineal en dos variables tienen interpretaciones geométricas relativamente sencillas; por ejemplo, el sistema de restricciones lineales asociado con un problema de programación lineal bidimensional- si no es inconsistente- define una región plana cuyafrontera está formada por segmentos de recta o semirrectas, por lo tanto es posible analizar tales problemas en forma gráfica.
Si consideremos el problema del granjero López, es decir, de maximizar P = 40x+ 30y sujeta a 
2x+y800
x+y480
                                                        x0, y0 (7)
 El sistema de desigualdades (7)define la región plana S que aparece en la figura 5. Cada punto de S es un candidato para resolver este problema y se conoce

como solución factible. El conjunto S se conoce como conjunto factible. El objetivo es encontrar – entre todos los puntos del conjunto S- el punto o los puntos que optimicen la función objetivo P. Tal solución factible es una solución óptima y constituyen la solución delproblema de programación lineal en cuestión.
Como ya se ha observado, cada punto P(x,y) en S es un candidato para la solución óptima del problema en cuestión, por ejemplo, es fácil ver que el punto (200, 150) está en S y, por lo tanto, entra en la competencia. El valor de la función objetivo P en el punto (200,150) está dado por P=40(200)+30(150)=12.500 . Ahora si se pudiera calcular el valor de Pcorrespondiente a cada punto de S, entonces el punto (o los puntos) en S que proporcione el valor máximo de P formará el conjunto solución buscado. Por desgracia, en la mayoría de los problemas, la cantidad de candidatos es demasiado grande o, como en este problema, es infinita. Así este método no es adecuado.
Es mejor cambiar de punto de vista: en vez de buscar el valor de la función objetivo Pen un punto factible, se asignará un valor a la función P y se buscarán los puntos factibles que correspondieran a un valor dado de P. Para esto supóngase que se asigna a P el valor 6000. Entonces la función objetivo se convierte en 40x+ 30y = 6.000,una ecuación lineal en x e y; por lo tanto, tiene como gráfica una línea recta L1 en el plano.  
Está claro que a cada punto del segmento de...