Archivo Unidad II Método Símplex

Mtodos Cuantitativos (990502)

Unidad II: Mtodo Smplex

PCE Ingeniera Comercial

Universidad de Concepcin

Educacin Continua

Campus Los ngeles

2015

Esencia del Mtodo Smplex

IEl mtodo smplex consiste en un procedimiento algebraico con fuertes

fundamentos geomtricos.

IEstos fundamentos geomtricos son la base intuitiva para entender

cmo funciona el mtodo smplex y entender su gran poder de utilidad.

ICon la nalidad de entender la losofa del mtodo smplex, recor-

daremos el problema de maximizacin de la utilidad de la compaa

Reddy Mikks.


Recordemos el modelo de programacin lineal para el problema de Reddy

Mikks:

Maximizar Z = 5x1

+ 4x2

sujeta a

6x

1

+ 4x2

24 (1)x

1

+ 2x2

6 (2)x1

+ x2

1 (3)x

2

2 (4)x

1

0 (5)x

2

0 (6)


Cuya representacin grca es la siguiente:


Y para la cual la solucin grca viene dada por:


ICada una de las rectas gracadas anteriormente se conoce como fron-

tera de restriccin.

ICada frontera de restriccin marca el lmite de lo que permite la re-

striccin correspondiente.

ILos puntos de interseccin entre las fronteras de restriccin se conocen

como soluciones en los vrtices.

ILos puntos que se encuentran en los vrtices de la regin factible se

llaman soluciones factibles en los vrtices (soluciones FEV). Para el

caso de Reddy Mikks, las soluciones FEV son:

(0, 0) , (4, 0) , (3, 1.5) , (2, 2) , (1, 2) , (0, 1)

ILos puntos de interseccin entre las fronteras de restriccin que no

forman parte de la regin factible se conocen como soluciones no

factibles en los vrtices. Para Reddy Mikks son:

(6, 0) ,

(8

3

, 2

),

(4

3

,7

3

), (2, 3) , (0, 3) , (0, 6)


IEn un problema de PL con n variables de decisin, dos soluciones

FEV se dicen adyacentes entre s cuando comparten n 1 fronterasde restriccin. As, dos soluciones FEV adyacentes estn conectadas

por un segmento de recta formado por las fronteras de restriccin

compartidas.

ILa importancia de analizar las soluciones FEV adyacentes radica en la

siguiente propiedad general conocida como Prueba de Optimalidad:

En cualquier problema de programacin lineal que posea al menos una

solucin ptima, si una solucin FEV no tiene soluciones FEV adyacentes

que sean mejores (segn el valor de Z), entonces esa debe ser una solucin

ptima.


Solucin FEV Sus Soluciones FEV adyacentes

(0, 0) (4, 0) y (0, 1)(4, 0) (0, 0) y (3, 1.5)(3, 1.5) (4, 0) y (2, 2)(2, 2) (3, 1.5) y (1, 2)(1, 2) (2, 2) y (0, 1)(0, 1) (1, 2) y (0, 0)

Mtodo Smplex versin geomtrica

A continuacin se presenta el mtodo smplex desde un punto de vista

geomtrico para el caso de Reddy Mikks.

IPaso inicial : Elegir (0, 0) como la solucin FEV para someterla a laprueba de optimalidad.

IPrueba de optimalidad : La solucin FEV (0, 0) arroja un valorZ = 0, mientras que sus soluciones FEV adyacentes arrojan valoresZ = 20 para (4, 0) y Z = 4 para (0, 1). Se concluye que (0, 0) no esuna solucin ptima.

IIteracin 1: Muvase a una solucin adyacente mejor (con mayor

valor de Z ). En este caso a la solucin FEV (4, 0).

IPrueba de optimalidad : Ya sabemos que la solucin FEV (4, 0)arroja un valor Z = 20. Adems, sus soluciones FEV adyacentesarrojan valores Z = 0 para (0, 0) y Z = 21 para (3, 1.5). Luego, (4, 0)no es una solucin ptima.

Mtodo Smplex versin geomtrica

IIteracin 2: Muvase a una solucin adyacente mejor (con mayor

valor de Z ). En este caso a la solucin FEV (3, 1.5).

IPrueba de optimalidad : Sus soluciones FEV adyacentes arrojan

valores Z = 20 para (4, 0) y Z = 18 para (2, 2). Luego, (3, 1.5) esuna solucin ptima y se detienen las iteraciones.

Mtodo Smplex Tabular

La versin algebraica del mtodo smplex necesita transformar las restric-

ciones en forma de desigualdad en igualdades. Esto se logra mediante la

introduccin de variables de holgura al modelo. Para ejemplicar esto,

supongamos que queremos resolver el siguiente problema presentado en su

forma original:

Maximizar Z = 3x1

+ 5x2

sujeta a

x

1

42x

2

123x

1

+ 2x2

18x

1

, x2

0


Debemos transforma las desigualdades en igualdades, introduciendo las

variables de holgura x

3

, x4

y x

5

, de este modo el modelo queda en la

siguiente forma aumentada:

Maximizar Z = 3x1

+ 5x2

sujeta a

x

1

+ x3

= 4

2x

2

+ x4

= 12

3x

1

+ 2x2

+ x5

= 18

x

j

0, para j = 1, 2, 3, 4, 5


Ahora bien, se introduce una nueva terminiloga para la forma aumentada.

IUna solucin aumentada es una solucin de las variables de decisin

que se le agreg los valores correspondientes de las variables de hol-

gura.

IUna solucin bsica es una solucin en un vrtice (o de esquina) pero

aumentada.

IUna solucin bsica factible (BF) es una solucin FEV aumentada.

INotemos que si hacemos la resta: nmero total de variables menos

nmero de ecuaciones, se obtiene la cantidad de grados de libertad del

modelo. Esto es, la cantidad de variables a las que podemos asignarles

el valor 0 y as poder despejar las restantes. Las variables asociadas

a los grados de libertad se llaman variables bsicas, en tanto que las

restantes se conocen como variables no bsicas.


ITodas las ideas anteriores se conjugan en una tabla llamada tabla

smplex, la cual es una abreviacin tabular del mtodo smplex.

IEl punto de vista geomtrico del mtodo smplex se transforma en un

punto de vista algebraico al transformar la forma original del modelo

en la forma aumentada.

ILa tabla smplex slo muestra los pasos fundamentales del mtodo

smplex algebraico; sin embargo, su utilizacin sigue siendo un poco

engorrosa.

IA continuacin se presenta la tabla smplex y su explicacin para el

problema de optimizacin propuesto anteriormente.

Tabla Smplex

Paso inicial : Introducimos las variables de holgura y seleccionamos las

variables de decisin como las variables no bsicas iniciales (es decir, iguales

a cero) y las variables de holgura como las variables bsicas iniciales. En el

ejemplo: Esta seleccin conduce a la tabla smplex inicial que se muestra

en la siguiente tabla, por lo que la solucin BF inicial es (0, 0, 4, 12, 18).

Prueba de optimalidad: La solucin BF es ptima si y slo si todos

los coecientes de la la (0) son no negativos (mayores o iguales a 0).

Si esto es as, entonces el proceso se detiene; de otro modo, se prosigue

con la primera iteracin para obtener la siguiente solucin BF, que incluye

cambiar una variable no bsica a bsica y viceversa, y despus despejar

la nueva solucin. En el ejemplo: Igual que Z = 3x1

+ 5x2

indica que al

aumentar x

1

o x

2

el valor de Z aumenta, de manera que la solucin BF

actual no es ptima, se llega a la misma conclusin a partir de la ecuacin

Z 3x1

5x2

= 0. Los coecientes 3 y 5 se muestran en la la (0) dela tabla siguiente.

Tabla Smplex

Table : Tabla smplex inicial

Tabla Smplex

Iteracin 1

IPaso 1: Se determina la variable bsica entrante seleccionando la

variable (que de modo automtico es no bsica) con el coeciente

negativo que tiene el mayor valor absoluto (es decir, el coeciente

ms negativo) de la ecuacin (0). Se pone un recuadro alrededor de

la columna abajo de este coeciente y se le da el nombre de columna

pivote. En el ejemplo: El coeciente ms negativo es 5 para x2

(5 > 3), de manera que x2

debe convertirse en variable bsica. Este

cambio se indica en la tabla siguiente.

IPaso 2: Se determina la variable bsica que sale con la prueba del

cociente mnimo.

Tabla Smplex

Prueba del cociente mnimo:

1. Elegir los coecientes estrictamente positivos ( mayores que 0) de la

columna pivote.

2. Dividir el elemento del lado derecho de cada la por el respectivo

elemento de la columna pivote (salvo divisiones por 0).

3. Identicar la la que tiene el menor de estos cocientes.

4. La variable bsica de ese rengln es la variable bsica que sale; sustit-

tuirla con la variable bsica entrante en la columna de la variable

bsica de la siguiente tabla.

Tabla Smplex

Table : Prueba del cociente mnimo para identicar la primera variable bsica

saliente.

Tabla Smplex

IDibujar un recuadro en este rengln que se llama rengln pivote. El

nmero que se encuentra encerrado por ambos recuadros se llama

nmero pivote.

IEn el ejemplo: Los clculos de la prueba del cociente mnimo se

muestran a la derecha de la tabla anterior. La la (2) es el rengln

pivote, mientras que x

4

es la variable bsica que sale. En la siguiente

tabla smplex, la variable x

2

sustituye a la variable x

4

como la nueva

variable bsica del rengln (2).

Tabla Smplex

IPaso 3: Se despeja la nueva solucin BF mediante operaciones el-

ementales con renglones (multiplicacin o divisin de un rengln por

una constante diferente de cero; suma o resta de un mltiplo de un

rengln con otro) para construir una nueva tabla smplex en la forma

apropiada de eliminacin gaussiana (nivelacin), abajo de la tabla ac-

tual, y despus se regresa a la prueba de optimalidad. Las operaciones

elementales con renglones que deben realizarse son:

IDividir el rengln pivote por el nmero pivote. Use este nuevo rengln

pivote en los dos pasos siguientes.

IEn las las (incluso la la 0) que tengan un coeciente negativo en la

columna pivote, se suma a esta la el producto del valor absoluto de

este coeciente por el nuevo rengln pivote.

IEn el caso de las las que tienen un coeciente positivo en la columna

pivote, se les resta el producto de este coeciente por el nuevo rengln

pivote.

Las dos tablas siguientes ilustran dicho procedimiento.

Tabla Smplex

Table : Construccin del nuevo rengln pivote.

Tabla Smplex

Table : Paso 3 de la iteracin 1.

Tabla Smplex

IAs, la nueva solucin BF es (0, 6, 4, 0, 6), con Z = 30. Despus seregresa a la prueba de optimalidad para vericar si la nueva solucin

BF es ptima. Como la nueva la (0) todava tiene un coeciente

negativo (3 para x1

), la solucin no es ptima, y se necesita por lo

menos una iteracin ms.

IEn la segunda iteracin, se deben repetir exactamente los mismos

pasos de la iteracin 1 y aplicar la prueba de optimalidad.

Tabla Smplex

Table : Prueba del cociente mnimo para la iteracin 2.

Tabla Smplex

Table : Iteracin 2 completa.

Tabla Smplex

En la ltima tabla se tiene ahora el conjunto de tablas smplex completo.

La nueva solucin BF es (2, 6, 2, 0, 0), con Z = 36. Al hacer la pruebade optimalidad se encuentra que la solucin es ptima porque no hay

coecientes negativos en la la (0), de manera que el algoritmo termina.

En consecuencia, la solucin ptima del problema es x

1

= 2 y x2

= 6.

Lectura Complementaria

Para complementar los conceptos tericos revisados en clases, deben re-

alizar las siguientes lecturas:

IDel Hillier & Lieberman, el captulo 4 hasta la pgina 123.

IDel Taha, el captulo 3 hasta la pgina 108.

Documents

Archivo Unidad II Método Símplex