Investigacion de operaciones

2.2 PROGRAMACION LINEAL: METODOS DE SOLUCION

1. METODO GRAFICO

2. METODO SIMPLEX - ALGEBRAICO

3. METODO SIMPLEX - TABULAR

4. METODO SIMPLEX - MATRICIAL

1

2.2.1 METODO GRAFICO (modelos con 2 variables) 1. TRAZAR EN UN PLANO LAS RESTRICCIONES 2. IDENTIFICAR LA REGION FACTIBLE 3. TRAZAR LA DIRECCIóN DE MAX ASCENSO 4. IDENTIFICAR EL PUNTO OPTIMO NOTAS: - En modelos con 2 variables:- Una restricción de exacta igualdad se representa por una recta - Una restricción “mayor igual” ó “menor igual” divide el espacio de soluciones en dos semiplanos - La Región factible es el conjunto de puntos que satisfacen todas las restricciones - Los Vértices ocurren en la intersección de 2 ó mas restricciones - Los Vértices siempre estan localizados en la frontera de la region factible - Todafunción lineal f(x1,x2,. . .) se puede expresar como el producto escalar del vector de coeficientes c = (c 1, c2, … ) y el vector de variables de decisión x = (x1, x2, … ). Es decir f(x1,x2) = c1x1 + c2x2 = c⋅ x - La dirección de max ascenso sobre la función objetivo f es la dirección del vector c - El punto óptimo es aquel en la región factible asociado con el vector que tiene la mayorproyección sobre el vector c. - De existir, una solucion óptima de un modelo de PL siempre ocurre en un vértice de la región factible.

2

METODO GRAFICO

Ejemplo: Máx X1 + 2X2 sa. 4X1 + 2X2 ≤ 16 3X1 + 3X2 ≥ 18 X2 ≥ 3 X1, X2 ≥ 0

a) Determinar la solución óptima b) Deteminar las restricciones activas y las inactivas c) En el punto óptimo, determinar los valores de holgura y excedente para cadarestricción d) Determinar las restricciones redundantes e) Determinar la solución óptima si la F.O. fuese Min f) Determinar la solución óptima si además la 2da restricción cambia a 3X1 + 6X2 ≥ 18 g) Determinar la solución óptima si además la 1ra restricción cambia a X1 + X2 ≤ 2

3

Modelo en forma estándar Máx X1 + 2X2 sa. 4X1 + 2X2 + S1 3X1 + 3X2 X2 X1, X2 , S1, S2 ,S3 ≥ 0 § La solución básicade un sistema de ecuaciones lineales de n por m, si existe, es una solución en la que se forza a que (n-m) variables tomen valor igual a cero. § A las (n-m) variables forzadas a tomar valor igual a cero se les llama variables no básicas. § El valor de las variables restantes resulta de resolver el sistema de ecuaciones lineales. A estas variables se les llama variables básicas. § El máximo númerode soluciones BASICAS es igual al número de parejas que se pueden formar con 5 variables:
5   2  

= 16 - S2 - S3 = 18 =3

=

5! = 10 2! (5 − 2)!

Solución Básica No. X1 1 2 3 4 5 6 7 8 9 10

X2 0 0 0 0 0

Variables S1 0

Función objetivo Z S2 S3 No factible 0 0

0 0 0

0 0 0 0 0 0 0 0 0

No factible No factible No factible No factible No factible No factible

42.2.2 ANÁLISIS POSTERIOR A LA RESOLUCIÓN Una vez resuelto un modelo de PL se debe distinguir entre:

RESTRICCIONES ACTIVAS Son aquellas que se cumplen con exacta igualdad en la solución óptima

RESTRICCIONES INACTIVAS Son aquellas que tiene holgura o excedente

Las restricciones activas son las que impiden el obtener una solución mejor que la solución óptima ya encontrada

RESTRICCIONESREDUNDANTES Son aquellas que de no estar presentes en el modelo, no modificarían la región factible ni la solución óptima.

5

MÉTODO GRÁFICO con 3 variables

X3

5 3

1

2 X1 4

X2

6

2.2.3 CASOS ESPECIALES

1. MULTIPLES OPTIMOS (óptimos alternos) Una restricción es paralela a la función objetivo Máx -3X1 + 6X2 sa. 5X1 + 7X2 ≤ 35 -X1 + 2X2 ≤ 2

X1, X2 ≥ 0

2. SOLUCIONOPTIMA ILIMITADA (no acotada) La región factible se extiende sin límites en alguna dirección Máx 2X1 + X2 sa. X1 - X2 2X1 - X2

≤ 10 ≤ 40

X1, X2 ≥ 0 2X1 - 1.5 X2 ? )

(y si la función objetivo fuese Máx

3. NO EXISTE SOLUCION (inconsistencia) No existe región factible Máx 3X1 + 2X2 sa. 2X1 + X2 ≤ 2 3X1 + 4X2 ≥ 12

X1, X2 ≥ 0

7

2.2.4 ANÁLISIS GRÁFICO a1 x1 + a2 x2 ≤ b
b a - 1 x1...