Comuncacion interna de la computadora

Tema 4. El método SIMPLEX para programación lineal

4.1. Método del Simplex. Representación gráfica.
4.2. Método del Simplex. Metodología de aplicación.
4.3. Infactibilidad, soluciones óptimas alternativas y no acotación.
4.4. Situaciones especiales:
Variables Artificiales.
4.4.1. Método de las Penalizaciones
4.4.2. Método de las dos fases o de doble etapa.
4.4.3. Método de la matrizinversa o simplex revisado.

1

4.1. Método del Simplex. Representación gráfica.
Se verá en clase.

4.2. Método del Simplex. Metodología de aplicación.
ESQUEMA GENERAL
Para resolver un problema de P.L. por el método del simplex se sigue un proceso
iterativo que consta de varias etapas, que vamos a describir al mismo tiempo lo
vamos a ir aplicando al ejemplo siguiente:
MAX
Z =4X1+5X2+3X3+3X4
Sujeto a las restricciones:
3X1 + 2X2 + 3X3 + 4 X4 ≤ 18
2X1 + 3X2 + X3 + 2 X4 ≤ 16
2X1 + 4X2 + 2X3 + 1 X4 ≤ 15
Que, una vez ajustadas quedan:
3X1 + 2X2 + 3X3 + 4 X4 +Xc1 =18
2X1 + 3X2 + X3 + 2 X4 + Xc2 = 16
2X1 + 4X2 + 2X3 + 1 X4 + Xc3 = 15
ETAPA 1.Consiste en buscar una solución básica posible (SBP), que en nuestro caso será la que
consiste en anular las cuatro variables reales, yobtener en el sistema de ecuaciones
las no anuladas, es decir:
X1 = X2 = X3 = X4 = 0, Xc1 =18, Xc2 = 16, Xc3 = 15
ETAPA 2.Se calculan todos los coeficientes con esta SBP (en este primer caso iguales a los del
sistema), que quedan según el cuadro siguiente:
Cj

5

3

3

0

0

0

bi

Cj

4
X1

X2

X3

X4

Xc1

Xc2

Xc3

0

Xc1

18

3

2

3

4

10

0

0

Xc2

16

2

3

1

2

0

1

0

0

Xc3

15

2

4

2

1

0

0

1

Zj

0

0

0

0

0

0

0

0

Wi

-4

-5

-3

-3

0

0

0

ETAPA 3.Se comprueba si todas las Wi son ≥ 0, en este no lo son W1, W2, W3 y W4 .
Si lo hubieran sido, estaríamos en la solución.
2

ETAPA 4.Se elige una variable (vector, proceso), queentre en la base aumentando el valor de
la función; en principio puede ser cualquiera que, en la etapa 3, su Wi sea < 0; se
recomienda elegir la de mayor valor absoluto Wi , puesto que es la que más
aporta a la función por unidad introducida; en nuestro caso sería la X2 .
ETAPA 5.Se determina el elemento de la variable a salir de la SBP, que debe ser una en la que
el elemento de su líneasituado en la columna de la variable a introducir sea positivo
y, entre las que cumplan esta condición, aquella en que el cociente entre el
elemento de los términos independientes y el, ya citado, de la columna de la
variable a introducir sea el mínimo.
En nuestro caso Xc3 , ya que b3/
El elemento

ij

C3,2

=15/4 2/4 ).
Etapa 5
Se determina que debe salir de la base Xc1, por ser 42/14 =,se emplean los Métodos de la “DOBLE
ETAPA” o de las “PENALIZACIONES” para obtener una 1ª S.B.P.
En ambos métodos se comienza por crear unas variables ficticias (Vi), que se añaden a
las restricciones que no tienen una variable fácilmente despejable, con las que se
puede obtener una SBP ficticia.

Variables Artificiales.
Como veremos posteriormente, en la fase inicial del método del métodosimétrico y
del simplex se necesita disponer de una solución básica factible siendo además
conveniente que ésta se pueda encontrar de una manera rápida. Hemos visto
algunos ejemplos en que mediante la introducción de variables de holgura esto era
sencillo; hay situaciones en que esto no es así.
Sea

2 x1+ x2 ≤ 8
4 x1 + 3 x2 ≥ 14
-Al añadir variables de holgura s1 y t1 tenemos
2x1 + x2 +s1 =8
4 x1 +3x 2 –t1 =14

Si hacemos x1 =x2=0, es s 1 =8 y t1 = —14, que no constituye una solución básica
factible (inicial), ya que todas las variables de un programa lineal en forma estándar
deben ser no negativas. Es claro, que mediante una inspección visual no es fácil la
búsqueda al menos en un tiempo breve de tal solución, incluso en problemas
pequeños. Para remediarlo, se han...