Programacion Lineal

Teórico Nº 6

PROGRAMACION LINEAL.
Contenidos

6. Programación lineal: Introducción. Una aplicación. Restricciones estructurales y restricciones de no negatividad.
Algunas aplicaciones de la programación lineal: Modelo de la dieta balanceada. Modelos de transporte. Modelos de elaboración de presupuesto de capital. Modelos de mezclado.
Soluciones gráfica: Gráficas de desigualdades lineales.Sistemas de desigualdades lineales. Área de soluciones factibles. Incorporación de la función objetiva. Soluciones de punto en la esquina. Otras soluciones óptimas. Ausencia de solución factible. Soluciones no acotadas.

Programación lineal

Inecuaciones lineales.

Para dibujar la desigualdad lineal:
3x - 4y ≤ 12,
Primero se dibuja la recta 3x - 4y = 12.
[pic]

Después, se elijeel origen (0, 0) como el punto de prueba (pues no está en la recta). Sustituyendo x = 0, y = 0 en la desigualdad, obtenemos
3(0) - 4(0) ≤ 12

Como 0 ≤12, entonces(0, 0) sí está en el conjunto solución. Dejamos claro esta región, mientras sombreamos la región no solución para ocultarla.
[pic]
Ejercicio 1

Representa en el plano las siguientes inecuaciones lineales.
x +5 y > 10

x+2y < 16

2x + y [pic]

Región factible
La región factible determinada por un conjunto de desigualdades lineales es el conjunto de puntos que satisfacen a la vez todas las desigualdades.
Se deben dibujar las regiones determinadas por cada desigualdad recordando en cada caso sombrear la parte del plano que corresponda. La región sombreada es la región factible.

Ejemplo
La regiónfactible determinada por el siguiente conjunto de desigualdades es la región sombreada clarita. (Incluyendo su frontera).
3x - 4y ≤ 12,
x + 2y ≥ 4
x ≥ 1
y ≥ 0.
[pic]

Ejercicio 2

Representa el recinto formado por las siguientes condiciones:
y – x [pic]2 ; x + 5y [pic] 10 ; x + 2y [pic]16 ; 2x + y [pic]20

Ejercicio 3

Representa el recintoformado por las siguientes condiciones:

2x –y 0 ; -2 [pic]y < 5

La programación lineal es una técnica que permite resolver problemas de planificación que posibilitan maximizar ganancias o minimizar costos; teniendo en cuenta los límites o restricciones que presenta el problema.

Método gráfico
El método gráfico para solucionar a un problema de programación lineal es el siguiente:A. Dibuje la región factible de las restricciones.
B. Calcule las coordenadas de los puntos extremos (puntos de esquina).
C. Sustituya las coordenadas de los puntos de esquina en la función objetiva para ver cuál da el valor óptimo. Este punto da la solución del problema de programación lineal.
D. Si la región factible no es acotada, este método puede ser erróneo: soluciones óptimassiempre existen cuando la región factible está acotada, pero pueden no existir en el caso no acotado. Si la región factible no es acotada, estamos minimizando una función objetiva cuyas coeficientes son no negativos, entonces existe una solución dado por este método.
Si en problema de programación lineal tiene una solución, entonces ésta debe aparecer en un vértice, o esquina, del conjuntofactible S asociado con el problema.
EJEMPLO 1:
Resolver mediante el método gráfico el siguiente problema:
|Maximizar |Z = f(x,y) = 3x + 2y |
|sujeto a: |2x + y ≤ 18 |
|  |2x + 3y ≤ 42 |
|  |3x + y ≤ 24 |
|  |x ≥ 0 , y ≥ 0 |

 
1. Inicialmente dibujamos el sistemade coordenadas asociando a un eje la variable x, y al otro la y, como se puede ver en la figura.

2. Marcamos en ellos una escala numérica apropiada de acuerdo con los recorridos de las variables en relación con las restricciones del problema. A continuación dibujamos las restricciones. Comenzando con la primera, dibujamos la recta que se obtiene al considerar la restricción como igualdad....