• Author / Uploaded
• Carlos Guanipa

• Categories
• Programación lineal
• Optimización combinatoria
• Análisis
• Algoritmos y Estructuras de Datos
• Análisis de sistemas

Citation preview

UNIVERSIDAD NACIONAL EXPERIMENTAL “FRANCISCO DE MIRANDA” AREA DE TECNOLOGIA DEPARTAMENTO DE GERENCIA UNIDAD CURRICULAR: INVESTIGACION DE OPERACIONES

TEMA 3. Métodos de Solución para Modelos de Programación Lineal

DOCENTE: ING. ROSA AMAYA

Los métodos a utilizar para resolver Modelos de Programación Lineal (MPL) son:

El Método Grafico El Método Simplex V.B.

X1

X2

h1

h2

A1

VALOR RAZON

Z

-202

-99

0

100

0

-600

h1

1

-1

1

0

0

1

1

A1

2

1

0

-1

1

6

3

Z

0

-301

202

100

0

-398

X1

1

-1

1

0

0

1

X

A1

0

3

-2

-1

1

4

1,33

Z

0

0

1,33

-0,33

100,33

3,33

X1

1

0

0,33

-0,33

0,33

2,33

X

X2

0

1

-0,67

-0,33

0,33

1,33

X

METODO GRAFICO Definición Es un método para resolver MPL con solo dos (2) variables de decisión, para

modelos con tres (3) o mas variables es impráctico o imposible.

Características • Es un método sencillo y fácil de manejar. • Es útil para ilustrar muchos de los elementos importantes de un MPL. • Sirve como base para el Método Simplex.

METODOLOGIA PARA LA APLICACIÓN DEL METODO GRAFICO • Trace un eje de coordenadas cartesianas. • Grafique las desigualdades dadas por el problema. • Identifique que lado satisface cada desigualdad. • Encuentre el área de soluciones factibles.

• Identifique la solución optima usando la función objetivo

METODOLOGIA PARA LA APLICACIÓN DEL METODO GRAFICO. Ejemplo Max Z = 5x1 + 5x2

Sujeta a las Restricciones: 12x1 + 8x2 ≤ 96 6x1 + 12x2 ≤ 72

x1

≥ 2

x1 , x2 ≥ 0

Condición de No Negatividad

METODOLOGIA PARA LA APLICACIÓN DEL METODO GRAFICO Convierta las desigualdades en igualdades y proceda a graficar: x1 ≥ 2

6x1 + 12x2 ≤ 72

x1 = 2 / x2 = 0

x1 = 0 / x2 = 6

x1= 0 / x2 = 12

x2 = 0 / x1 = 12

x2 = 0 / x1 = 8

12x1 + 8x2 ≤ 96

METODOLOGIA PARA LA APLICACIÓN DEL METODO GRAFICO Encuentre la solución optima:  METODO I: Grafique z y traslade paralelamente hacia el lado de mejora. Z = 20; 20 = 5x1 + 5x2 Z = 40; 40 = 5x1 = 5x2 METODO II: Evalúe cada punto extremo en la función objetivo Puntos x1 x2 Z

B C D

A

Z = 20

Z = 40

A

2

0

10

B

2

5

35

C

6

3

45

D

8

0

40

METODO SIMPLEX Definición y características Este método se basa en un proceso iterativo que comienza en un vértice

(normalmente el origen) y se va trasladando de vértice en vértice hasta encontrar la solución optima (de haberla). Esta diseñado de tal forma que con cada iteración se mejora el valor de la función objetivo.

Existen dos (2) variantes de este método:

Primal: se emplea cuando en la estandarización del modelo solo es necesaria la introducción de variables de holgura. Técnica de la M: se utiliza cuando en la estandarización del modelo se

deben emplear variables artificiales que permitan encontrar una solución inicial para el problema.

METODOLOGIA PARA LA APLICACIÓN DEL METODO SIMPLEX FASE I: ENCONTRAR LA SOLUCION INICIAL BASICA FACTIBLE (SIBF) Estandarice el modelo

La función objetivo puede ser de maximizar o minimizar. Todos los valores del lado derecho de las restricciones son no negativos.

Todas las restricciones son igualdades. Todas las variables son no negativas Encuentre la solución inicial En un modelo con M ecuaciones y N variables, se tiene que N ≥ M. M determina el numero de Variables Básicas (VB)

N – M, se utiliza para encontrar el numero de Variables No Básicas (VNB) Construya la tabla “0”

Las VB deben aparecer como renglones y en el primer renglón va Z. En las columnas, todas las variables (VB + VNB), el valor del lado derecho y la razón.

METODOLOGIA PARA LA APLICACIÓN DEL METODO SIMPLEX FASE II: ENCUENTRE LA SOLUCION OPTIMA Identifique la variable de entrada (VE) Si es maximizar (minimizar) es la VNB con el coeficiente mas negativo (mas positivo)

en la ecuación objetivo. Encuentre la variable de salida (VS)

VB con la menor razón (≥ 0) Realice el cambio de base Para la VE, aplicar: Nueva Ecuación Pivote = Ecuación Pivote / Elemento Pivote Para las demás variables y para Z, usar:

Nueva Fila = Vieja Fila – (coeficiente de la columna de entrada de la variable correspondiente * Nueva Ecuación Pivote)

Aplique la Regla de Optimalidad, maximizar (minimizar) coeficientes en Z ≥ 0 (Z ≤ 0)

Ejemplo Modelo: Max Z = 5x1 + 2x2 Sujeta a las Restricciones: 12x1 + 8x2 ≤ 12 6x1 + 12x2 ≤ 72 x1, x2 ≥ 0

Solución Inicial

M = Nro. de VB N – M = Nro. de VNB VNB:

FASE I: ENCONTRAR SIBF

2 VB 2 VNB VNB:

X1 = 0

h1 = 96

X2 = 0

h2 = 72

Estandarización 12x1 + 8x2 + h1 = 96 6x1 + 12x2 + h2 = 72 x1, x2, h1, h2 ≥ 0 N = 4 variables

M = 2 ecuaciones

SIBF Z – 5x1 – 2x2 + 0h1 + 0h2 = 0

Ejemplo Z – 5x1 – 2x2 + 0h1 + 0h2 = 0

Construir tabla “0”

12x1 + 8x2 + h1 = 96 6x1 + 12x2 + h2 = 72 x1, x2, h1, h2 ≥ 0

VB

X1

X1

h1

h2

Valor

Razon

Z

-5

-2

0

0

0

-

h1

12

8

1

0

96

96/12 = 8

h2

6

12

0

1

72

72/6 = 12

Ejemplo

 Tabla “0” VB

X1

X1

h1

h2

Valor

Z

0

4/3

5/12

0

40

X1

1

2/3

1/12

0

8

h2

0

8

- 1/2

1

24

Solución: X1 = 8 / X2 = 0 h1 = 0 / h2 = 24 Z = 40

TIPOS DE SOLUCIONES DE UN MPL

Múltiples Soluciones:

V.B.

X1

X2

h1

h2

h3

h4

A1

A2

VALOR

Z

-4000900

-2000900

10000

0

0

10000

0

0

-9000000

RAZON

A1

400

100

-1

0

0

0

1

0

800

2

h2

100

100

0

1

0

0

0

0

500

5

h3

100

0

0

0

1

0

0

0

300

3

A2

0

100

0

0

0

-1

0

1

100

X

-998200

Z

0

-1000675

-2,25

0

0

10000

10002,25

0

X1

1

0,25

-0,0025

0

0

0

0,0025

0

2

h2

0

75

0,25

1

0

0

-0,25

0

300

4

h3

0

-25

0,25

0

1

0

-0,25

0

100

X

A2

0

100

0

0

0

-1

0

1

100

1

Z

0

0

-2,25

0

0

-6,75

10002,25

10006,75

2475

X1

1

0

-0,0025

0

0

0,0025

0,0025

-0,0025

1,75

700

h2

0

0

0,25

1

0

0,75

-0,25

-0,75

225

300

h3

0

0

0,25

0

1

-0,25

-0,25

0,25

125

X

X2

0

1

0

0

0

-0,01

0

0,01

1

X

4500

Z

0

0

0

9

0

0

10000

10000

X1

1

0

-0,0033

-0,0033

0

0

0,0033

0

1

h4

0

0

0,3333

1,3333

0

1

-0,3333

-1

300

h3

0

0

0,33

0,33

1

0

-0,33

0

200

X2

0

1

0,0033

0,0133

0

0

-0,0033

0

4

8

TIPOS DE SOLUCIONES DE UN MPL

Área no Acotada:

V.B.

X1

X2

h1

h2

A1

VALOR

RAZON

Z

-202

-99

0

100

0

-600

h1

1

-1

1

0

0

1

1

A1

2

1

0

-1

1

6

3

Z

0

-301

202

100

0

-398

X1

1

-1

1

0

0

1

X

A1

0

3

-2

-1

1

4

1,33

Z

0

0

1,33

-0,33

100,33

3,33

X1

1

0

0,33

-0,33

0,33

2,33

X

X2

0

1

-0,67

-0,33

0,33

1,33

X

TIPOS DE SOLUCIONES DE UN MPL

Solución Infactible:

V.B.

X1

X2

h1

h2

h3

h4

A1

A2

VALOR

Z

-1003

-1002

0

0

1000

1000

0

0

-50000

RAZON

h1

0,025

0,017

1

0

0

0

0

0

1

40

h2

0,02

0,02

0

1

0

0

0

0

1

50

A1

1

0

0

0

-1

0

1

0

30

30

A2

0

1

0

0

0

-1

0

1

20

X

Z

0

-1002

0

0

-3

1000

1003

0

-19910

h1

0

0,017

1

0

0,025

0

-0,025

0

0,25

14,71

h2

0

0,02

0

1

0,02

0

-0,02

0

0,4

20

X1

1

0

0

0

-1

0

1

0

30

X

A2

0

1

0

0

0

-1

0

1

20

20

Z

0

0

58937,64

0

1469,94

1000

-469,94

0

-5170,58

X2

0

1

58,824

0

1471

0

-1,471

0

14,706

X

h2

0

0

-1,176

1

-0,009

0

0,009

0

0,106

11,78

X1

1

0

0

0

-1

0

1

0

30

30

A2

0

0

-58,824

0

-1,471

-1

1,471

1

5,294

3,60

-3478,8

Z

0

0

40135,34

0

1000

680,44

0

319,56

X2

0

1

0

0

0

-1

0

1

20

h2

0

0

-0,8

1

0

0,0068

0

-0,0068

0,072

X1

1

0

40

0

0

0,68

0

-0,68

26,4

A1

0

0

-40

0

-1

-0,68

1

0,68

3,6

BIBLOGRAFIA RECOMENDADA