Programacion Lineal-Metodo Simplex

Programación Lineal: El Método Simplex g p
Características
• Es un método algebraico sistemático que examina los vértices de un conjunto restringido de PL en busca de una solución óptima. b s d s l ió ó ti • Está diseñado de manera que la Función Objetivo no d disminuya en un modelo de M d l d Maximización y ó generalmente aumentará a cada vértice sucesivo de la secuencia.
1

ProgramaciónLineal: El Método Simplex g p
• Cada vértice del conjunto restringido de PL puede ser representado en forma algebraica como una clase particular de solución del d l conjunto d ecuaciones li j de i lineales. l Ejemplo Un fabricante de muebles que únicamente elabora dos productos, escritorios y sillas, tiene cuatro departamentos:
2


Programación Lineal: El Método Simplex g p
Tiempo disponible(hrs.) 120 90 70 50 Tiempo requerido Sillas (hrs./silla) 1 1 1 0 Escritorios (hrs./escrit.) 2 1 0 1

Depto. Corte Armado Tapicería Cubiertas

La contribución al costo fijo y a la utilidad de cada silla es de $20 y la de cada escritorio $50 $50.
3


Programación Lineal: El Método Simplex g p
Variables de Decisión X1 = Cantidad de Sillas a Fabricar X2 = Cantidad de Escritorios a FabricarMax Z = 20X1 + 50X2 Sujeto a X + 2X ≤ 1 0 120
1 2

( (corte) ) (armado) (tapicería) (cubiertas)
4

X1 + X2 ≤ 90 X1 ≤ 70 X2 ≤ 50 X1, X2 ≥ 0


Programación Lineal: El Método Simplex g p
Solución Básica Agregar Variables de holgura “Si” a cada restricción ≤ para convertir en “ecuaciones” ecuaciones X1 + 2X2 + S1 X1 + X2 X1 X2 + S2 + S3 = 120 = 90 = 70 + S4 = 50

Sistema d 4 ecuacionescon 6 variables Si t de i i bl
5


Programación Lineal: El Método Simplex g p

• Igualando a cero dos de las variables se obtiene un sistema cuadrado, el cual tiene una sola solución a la que se le denomina “Solución Básica”. • A las variables que se igualan a cero se les llama “variables “ i bl s no-Básicas”. Bási s”

6


Programación Lineal: El Método Simplex g p
X1 + 2X2 + S1 X1 +X2 X1 X2 • Por ejemplo S1 = 0 S3 = 0


= 120 + S2 + S3 = 90 = 70 + S4 = 50

X1 = 70 X2 = 25

S2 = - 5 S4 = 25
7

Programación Lineal: El Método Simplex g p
Podemos igualar a cero otro cualquier par de variables y obtendremos otra “Solución Básica” ¿Cuantas “Soluciones Básicas” podemos formar?

6 2

6! = = 15 2!(4!)

8


Programación Lineal: El Método Simplex g p
SoluciónBásica Factible • Es una solución Básica cuyas variables son todas no-Negativas”. t d s “n N ti s” • Asociado con cada “Solución Básica Factible” de l s d las ecuaciones originales está i s i i l s stá “Un Vértice “ único del conjunto restringido. • El “Algoritmo Si l ” i “Al it Simplex” investiga ti entre las “Soluciones Básicas Factibles” p para encontrar una “Solución Óptima”. p
9Programación Lineal: El Método Simplex g p
X2 80 X1 + X2 ≤ 90 X1 ≤ 70
C

60 40 20

B

X2 ≤ 50

D

Región Factible
| | | | | | |

E F

X1 + 2X2 ≤ 120

A

|

|

|

|

|

20

40

60

80

100

120

X1
10

MC. Carlos Lacavex Eguiarte

Programación Lineal: El Método Simplex g p
La Tabla Inicial El Algoritmo Simplex parte de una “Solución Básica Factible” en la quetodas las q Variables Reales (tales como X1 y X2) se igualan a cero. X1 = 0 X2 = 0 X1 + 2X2 + S1 X1 + X2 X1 X2
MC. Carlos Lacavex Eguiarte

= 120 + S2 + S3 = 90 = 70 + S4 = 50

S1 =120 S2 = 90 S3 =70 S4 = 50
11

Programación Lineal: El Método Simplex g p
En forma Tabular
V.B. Corte Armado A d Tapicería Cubiertas S1 S2 S3 S4 X1 1 1 1 0 X2 2 1 0 1 S1 1 0 0 0 S2 0 1 0 0 S3 0 0 1 0 S4 0 0 01 Valor 120 90 70 50

¿Cuál ¿C ál es el vértice que representa esta tabla? l é ti t t t bl ?
12
MC. Carlos Lacavex Eguiarte

Programación Lineal: El Método Simplex g p
X2 80 X1 + X2 ≤ 90 X1 ≤ 70
C

60 40 20

B

X2 ≤ 50

D

Región Factible
| | | | | | |

E F

X1 + 2X2 ≤ 120

A

|

|

|

|

|

20

40

60

80

100

120

X1
13

MC. Carlos...