Resolucion De Un Problema De Programacion Lineal

En general, un problema de programación lineal puede tener una, infinitas o ninguna solución. El procedimiento para resolver un problema de programación lineal será el siguiente: (1) Deducir la función objetivo y ver si tenemos que maximizarla o minimizarla. (2) Obtener las restricciones a las que está sometida la función objetivo. (3) Calcular la región factible. (4) Obtener los vértices de la región factible (soluciones factibles). (5) Sustituir las coordenadas de los vértices de la región factible en la función objetivo para ver cual o cuales de ellos hacen máxima o mínima la función objetivo. (6) Tendremos tres casos: Si uno y solo uno de los vértices hace máxima o mínima la función objetivo tendremos que el problema tiene solución única y ésta estará formada por las coordenadas del vértice. Si dos vértices hacen máxima o mínima la función objetivo tendremos que el problema tiene infinitas soluciones y éstas serán las que se encuentran en el segmento que tiene por extremos los dos vértices. Si tenemos que la región factible es el conjunto vacío entonces el problema no tiene solución. Ejemplo: Maximizar g(x, y) = 3x + 3y sujeta a las restricciones:

x+y≥5 y≤x+3 3y – x ≥ - 1 y + 2x ≤ 16 4y – x ≤ 22 Los pasos (1) y (2) ya nos los da el problema. (3) Procedemos a calcular la región factible:

y + 2x = 16 x+y = 5

y = x+3 C D

B

4y – x = 22

Región factible

E

A

3y – x = -1

(4) Obtenemos los vértices de la región factible: Vértice A: x+y=5

→ 4y = 4 → y = 1 → x = 4 → A = (4, 1)

3y – x = -1 x+y=5 Vértice B: y=x+3

→ x + x + 3 = 5 → 2x = 2 → x = 1 → y = 4 → B = (1, 4)

x+y=5 y=x+3

Vértice C: y=x+3

→ 4(x + 3) – x =22→3x =10 → x = 10/3 → y=19/3→C= (10/3,19/3)

4y – x = 22 y=x+3

Vértice D: y + 2x = 16

→ 4(16 – 2x) – x =22→42 = 9x→x = 14/3 4y – x = 22

→ y + 2•14/3 = 16 → y + 2x = 16 → y = 16 – 28/3→ y =20/3 → D = (14/3, 20/3)

Vértice E: y + 2x = 16

→ 3(16 – 2x) – x = - 1→ 49 = 7x → x = 7 3y – x = -1 y + 2x = 16

→ y + 2•7 = 16 → → y = 16 - 14→y = 2 → E = (7, 2)

(5) Sustituimos las coordenadas de los vértices de la región factible en la función objetivo para ver cual o cuales de ellos hacen máxima la función objetivo: Vértice A = (4, 1) → F(A) = 3•4 + 3•1 = 12 + 3 = 15 Vértice B = (1, 4) → F(B) = 3•1 + 3•4 = 3 + 12 = 15 Vértice C= (10/3, 19/3) → F(C) = 3•10/3 + 3•19/3 = 10 + 19 = 29 Vértice D = (14/3, 20/3) → F(D) = 3•14/3 + 3•20/3 = 14 + 20 = 34 Vértice E = (7, 2) → F(E) = 3•7 + 3•2 = 21 + 6 = 27 (6) Tendremos que el máximo se alcanza en el vértice D por tanto la solución será que x = 14/3 e y = 20/3.