emat 3. eletodom del simplex. -...

Tema 3. El m�etodo del Simplex.

Ma Luisa Carpente Rodr��guez

Departamento de Matem�aticas

M.L. Carpente (Departamento de Matem�aticas) El m�etodo del Simplex 2008 1 / 28

Objetivos

1 Conocer el funcionamiento de los algoritmos dise~nados: el Simplex.

2 Conocer y manejar correctamente alg�un tipo de software para resolver

este tipo de problemas.

3 Interpretar correctamente las soluciones.


Calendario previsto

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

T

P

Tema 3

Semanas


1 Problemas de programaci�on lineal en forma est�andar

2 Repaso de notaci�on y nociones b�asicas para la resoluci�on de sistemas de

ecuaciones lineales

3 De�niciones b�asicas: soluci�on factible, variables b�asicas y no b�asicas,

sistema can�onico, soluci�on b�asica y soluci�on factible b�asica

4 Esquema b�asico de funcionamiento del m�etodo del Simplex.

De�niciones b�asicas: bene�cios relativos y pivotaje

5 El m�etodo del Simplex por tablas: criterio de entrada, criterio de salida

(regla de la m��nima proporci�on)y elemento pivote


Forma est�andar

La forma est�andar de un PPL com m restricciones y n variables se escribe:

max(�omin)z = c1x1 + c2x2 + � � �+ cnxn

s:a: a11x1 + a12x2 + � � �+ a1nxn = b1

a21x1 + a22x2 + � � �+ a2nxn = b2

� � � � � � � � � � � �

am1x1 + am2x2 + � � �+ amnxn = bm

x1; x2; : : : ; xn � 0

donde b1; b2; : : : ; bm � 0


Forma est�andar

En notaci�on matricial

La forma est�andar de un PPL com m restricciones y n variables se escribe:

max(�omin) z = cx

s:a: Ax = b

x � 0

donde

A (m � n): es la matriz de coe�cientes

x (n � 1): es el vector soluci�on, de actividades o de decisiones

b (m � 1): es el vector de restricciones o de recursos

c (1� n): es el vector de costes o de bene�cios


Forma est�andar

Cualquier PPL se puede pasar a forma est�andar:

Para convertir las desigualdades en igualdades se introducen las

variables de holgura

Ejemplo

Si se tiene x1 + x2 � 8 pasa a ser x1 + x2 + x3 = 8 con x3 � 0

Si se tiene x1 + x2 � 8 pasa a ser x1 + x2 � x3 = 8 con x3 � 0


Forma est�andar

Si alg�un bj es negativo se multiplica toda la restricci�on por �1

Si un xi es � 0, se introduce una variable � 0, xk , tal que xi = �xk

Si una variable xi es no restringida (puede tomar cualquier valor), se

introducen dos variables � 0, xk xl , tal que xi = �xk � xl


Forma est�andar

Ejemplo

Sea el siguiente PPL:

maxz = 5x1 � 2x2 + 3x3

s:a: x1 + x2 + x3 � 7

x1 � 2x2 + x3 � 2

3x1 � x2 � 2x3 = �5

x1 � 0

x2 � 0


Forma est�andar

La forma est�andar del PPL es:

maxz = 5x1 + 2x�2 + 3x+3 � 3x�3s:a: x1 � x

�

2 + x+3 � x

�

3 + x4 = 7

x1 + x�

2 + x+3 � x

�

3 � x5 = 2

�3x1 � x�

2 + 2x+3 � 2x�3 = 5

x1 � 0

x�

2 � 0

x+3 � 0

x�

3 � 0

x4; x5 � 0


Forma est�andar

Dado el PPL est�andar

max(�omin) z = cx

s:a: Ax = b

x � 0

se tiene que:

Una soluci�on factible es un vector no negativo x tal que Ax = b

La regi�on factible,S , es es conjunto de todas las soluciones factibles

S = fx=Ax = b; x � 0g

Si S = ; entonces el problema se dice no factible


Forma est�andar

Una soluci�on �optima es un vector xo tal que es una soluci�on factible y

maximiza (o minimiza) la funci�on del objetivo, es decir cxo = maxcx

(o cxo = mincx )

El valor �optimo de un PPL es el valor del objetivo correspondiente a

la soluci�on �optima (zo = cxo)


Sistemas de ecuaciones

Los sistemas de ecuaciones lineales pueden resolverse por el m�etodo

de eliminaci�on de Gauss-Jordan.

Si un sistema de ecuaciones tiene m�as inc�ognitas que ecuaciones,

entonces tiene m�as de una soluci�on. A la colecci�on de todas las

posibles soluciones se le llama conjunto soluci�on.

Dos sistema de ecuaciones se dicen equivalentes si ambos sistemas

tienen el mismo conjunto soluci�on.



Sea el sistema

x1 � 2x2 + x3 � 4x4 + 5x5 = 2

x1 � x2 � x3 � 3x4 � x5 = 4

Si en el sistema anterior cambiamos la segunda ecuaci�on sum�andole

la primera cambiada de signo, eliminamos la variable x1

x1 � 2x2 + x3 � x4 + 5x5 = 2

x2 � 2x3 + x4 � 3x5 = 2



Eliminamos ahora x2 de la primera ecuaci�on

x1 � 3x3 � 2x4 � 4x5 = 6

x2 � 2x3 + x4 � 3x5 = 2

Si hacemos

x3 = x4 = x5 = 0

se obtiene

x1 = 6

x2 = 2


De�niciones b�asicas

Una variable es b�asica si aparece en una �unica ecuaci�on del sistema

con coe�ciente 1. Las variables que no cumplen esto, se dicen no

b�asicas.

Un sistema de ecuaciones se llama can�onico si en cada ecuaci�on

aparece una variable b�asica.

Un pivotaje es una sucesi�on de operaciones elementales que reduce un

sistema de ecuaciones dado a uno equivalente.


De�niciones b�asicas

Una soluci�on es b�asica si se obtiene de hacer las variables no b�asicas

cero y se calcula el valor de las b�asicas en cada ecuaci�on.

Una soluci�on es factible b�asica si es b�asica y los valores de las

variables b�asicas son no negativos.

Dado un PPL con n variables y m restricciones, el n�umero de

soluciones b�asicas est�a acotado por�nm

�


Principios del Simplex

Introducci�on

George Dantzig

Nacido en Oreg�on en 1914, hijo de inmigrantes de origen ruso, estudia

matem�aticas en la Universidad de Maryland. Poco despu�es de doctorarse

por la Universidad de Berkeley, en 1947, formula el enunciado est�andar de

un problema general de Programaci�on Lineal y desarrolla el m�etodo del

Simplex.



Una de las primeras aplicaciones del Simplex fue la resoluci�on del

llamado \puente a�ereo de Berl��n". A mediados de 1948, en plena

guerra fr��a, la URSS bloque�o las comunicaciones terrestres con Berl��n.

Utilizando la Programaci�on Lineal, se dise~n�o un plan de

abastecimiento a�ereo que en pocos meses consigui�o igualar a los

anteriores suministros realizados por carretera y ferrocarril.

En 1951 el ordenador SEAC (Standards Eastern Automatic

Computer) resolv��a problemas con 48 restricciones y 72 variables.

En 1963 el IBM 7090 resolv��a problemas con 1024 restricciones y 10

a~nos m�as tarde otro IBM, el modelo 360, era ya capaz de utilizar

32000 restricciones.




Es un procedimiento iterativo para resolver PPLs en forma est�andar.

1 Empezar obteniendo una soluci�on factible b�asica inicial (poniendo el

sistema de ecuaciones en forma can�onica).

2 Mejorar dicha soluci�on si es posible. En ese caso el Simplex ya

dejar�a de considerar todas aquellas soluciones factibles b�asicas cuya

funci�on del objetivo sea peor que la actual.

3 Repetir el paso 2 hasta encontrar la mejor soluci�on factible b�asica.



Sea el problema:

maxz = 5x1 � 2x2 � 3x3 � x4 + x5

s:a: x1 + 2x2 + 2x3 + x4 = 8

3x1 + 4x2 + x3 + x5 = 7

xi � 0

La siguiente es una soluci�on factible b�asica:

x1 = x2 = x3 = 0

x4 = 8

x5 = 7

z = �1



El cambio neto en el valor de z para un incremento unitario de una

variable se denomina bene�cio relativo y se denotar�a por �c .

Calculamos el bene�cio relativo de x1 (se mantiene x2 = x3 = 0). Si

x1 = 1 entonces:

x4 = 7

x5 = 4

z = 2

Luego aumentar el valor de x1 en una unidad hace que el objetivo aumente

en 2� (�1) = 3 unidades (�c1 = 3). Sabemos que la anterior soluci�on

factible b�asica no es �optima. Haciendo el mismo razonamiento obtenemos

�c2 = 0 y �c3 = 4.



Una soluci�on b�asica adyacente a una SB espec��ca di�ere de la

soluci�on b�asica considerada en una �unica variable b�asica.

En el ejemplo anterior, si incluimos en la base la variable que ten��a el

mejor bene�cio relativo, x3, el m�aximo valor que puede tomar �esta lo

condicionan las restricciones:

2x3 + x4 = 8

x3 + x5 = 7

Como x4; x5 � 0 se tiene

x4 = 8� 2x3 � 0) x3 � 4

x5 = 7� x3 � 0) x3 � 7

Por tanto, x3 � 4 y la variable x4 se anula, pasando a no ser b�asica. La

soluci�on obtenida as�� es adyacente de la primera SFB.



El m�etodo del Simplex para un problema de maximizaci�on

1 Empezar con una SBF del sistema en forma can�onica.

2 Comprobar si esa soluci�on es �optima, calculando los bene�cios

relativos de las variables no b�asicas. Si todos son � 0, la soluci�on

actual es �optima y se �naliza. En otro caso, seguir.

3 Seleccionar la variable no b�asica con el mayor bene�cio relativo. Esta

variable entrar�a en la base.

4 Determinar la variable que sale de la base por la regla de la m��nima

proporci�on: las restricciones en las que la variable no b�asica

seleccionada tiene coe�ciente positivo, restringen el crecimiento de la

variable al cociente entre la constante de la derecha y el valor del

coe�ciente positivo (los ceros o negativos no limitan el crecimiento de

la variable).

5 Resolver el nuevo sistema y volver a 2.


El Simplex por tablas

Veremos el Simplex por tablas en el problema:

maxz = 5x1 � 2x2 � 3x3 � x4 + x5

s:a: x1 + 2x2 + 2x3 + x4 = 8

3x1 + 4x2 + x3 + x5 = 7

xi � 0

5 2 3 -1 1

1 2 2 1 0

3 4 1 0 1

-1

1

8

7

3 0 4 0 0 -1

Coeficientes del objetivo

Var

iabl

es b

ásic

as

b

zBeneficios relativos

A



Para calcular los bene�cios relativos:

�ci = ci � cBPi

donde cB son los coe�cientes en el objetivo de las variables b�asica y

Pi es la columna en la tabla de la variable xi .

Tras un pivotaje:I Nueva �la pivote = �la antigua pivote divida por el valor del pivote.I Nueva �la = �la antigua-(coe�ciente de la columna pivote)�(nueva

�la pivote)



5 2 3 -1 1

1 2 2 1 0

3 4 1 0 1

-1

1

8

7

3 0 4 0 0 -1TA

BLA

1

5 2 3 -1 1

1/2 1 1 1/2 0

5/2 3 0 -1/2 1

3

1

4

3

1 4 0 -2 0 15

TAB

LA 2

5 2 3 -1 1

0 2/5 1 3/5 -1/5

1 6/5 0 -1/5 2/5

3

5

17/5

6/5

0 -26/5 0 -9/5 -2/5 81/5

TAB

LA 3

Óptima



Observaciones

Si en la tabla �optima alguna variable no b�asica tiene bene�cio relativo

cero, entonces hay �optimos alternativos.

Si el problema es de minimizaci�on:I Se cambia de signo la funci�on del objetivo y se resuelve como uno de

maximizaci�on.I Se utiliza el algoritmo descrito, variando que la variable no b�asica que

entra es la de menor bene�cio relativo y �nalizando cuando todos losbene�cios relativos sean no negativos.


emat 3. eletodom del simplex. -...

Documents