27
 El método Simplex Ya se ha comentado la propiedad de que todos los programas lineales alcanzan un óptimo, si éste existe, en una de sus soluciones básicas factibles (vértice del espacio de soluciones factibles). Además el número de tales soluciones básicas es siempre finito. Por tanto, un método de resolución de este tipo de problemas es la construcción de todas las soluciones básicas factibles y la selección de aquella que minimice la función objetivo. Por supuesto, este método resulta claramente ineficiente cuando se trabaja con  problemas con gran número de variables de decisión (como ocurre en los casos que normalmente aparecen en situaciones reales). La idea del método Simplex, ideado por G.B. Dantzing en 1947, consiste en llegar a encontrar esa solución básica óptima sin necesidad de construirlas todas, únicamente seleccionando un subconjunto de ellas que converja a la solución. De una forma muy resumida el método Simplex consiste en: 1. Debe p arti rse de una sol ución bási ca fac tible ini cial. 2. Si dic ha soluci ón básica no es óp tima, entonces e ncontrar otra que haga que el valor de la función objetivo disminuya, o por lo menos que no aumente. 3. Repetir el pa so anterior hasta encontrar u na solu ción básica fac tible q ue sea óptima. Al ser el número de soluciones básicas finito, si en cada paso se consigue una reducción del valor óptimo, ninguna de ellas podrá repetirse y de esta manera en un número finito de pasos se encontrará un óptimo del problema (si es finito). Dos aspectos a tener en cuenta sobre este método son: Es necesario disponer de un test de optimalidad que permita reconocer cuando una solución básica factible es óptima, sin necesidad de conocer el resto de soluciones básicas. Se necesita también un sistema efectivo de paso de una solución básica a otra, mejorando el valor de la función objetivo. Geométricamente, el método Simplex se puede interpretar de la manera siguiente:  partiendo de uno de los vértices del poliedro, ir desplazándose a uno de los vértices adyacentes mejorando el valor de la función objetivo hasta encontrar el óptimo Para el resto de la exposición sobre los fundamentos matemáticos del método Simplex se hará la suposición de que todas las soluciones básicas del programa son no degeneradas (hipótesis de no degeneración). No obstante, el no verificarse esta hipótesis no altera la validez de las conclusiones a las que se llegará.

El método Simplex

Embed Size (px)

Citation preview

Page 1: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 1/27

 

El método Simplex

Ya se ha comentado la propiedad de que todos los programas lineales alcanzan unóptimo, si éste existe, en una de sus soluciones básicas factibles (vértice del espacio desoluciones factibles). Además el número de tales soluciones básicas es siempre finito.Por tanto, un método de resolución de este tipo de problemas es la construcción de todaslas soluciones básicas factibles y la selección de aquella que minimice la funciónobjetivo. Por supuesto, este método resulta claramente ineficiente cuando se trabaja con

 problemas con gran número de variables de decisión (como ocurre en los casos quenormalmente aparecen en situaciones reales).

La idea del método Simplex, ideado por G.B. Dantzing en 1947, consiste en llegar aencontrar esa solución básica óptima sin necesidad de construirlas todas, únicamenteseleccionando un subconjunto de ellas que converja a la solución. De una forma muyresumida el método Simplex consiste en:

1. Debe partirse de una solución básica factible inicial.2. Si dicha solución básica no es óptima, entonces encontrar otra que haga que el

valor de la función objetivo disminuya, o por lo menos que no aumente.3. Repetir el paso anterior hasta encontrar una solución básica factible que sea

óptima.

Al ser el número de soluciones básicas finito, si en cada paso se consigue una reduccióndel valor óptimo, ninguna de ellas podrá repetirse y de esta manera en un número finitode pasos se encontrará un óptimo del problema (si es finito). Dos aspectos a tener encuenta sobre este método son:

• Es necesario disponer de un test de optimalidad que permita reconocer cuandouna solución básica factible es óptima, sin necesidad de conocer el resto desoluciones básicas.

• Se necesita también un sistema efectivo de paso de una solución básica a otra,mejorando el valor de la función objetivo.

Geométricamente, el método Simplex se puede interpretar de la manera siguiente: partiendo de uno de los vértices del poliedro, ir desplazándose a uno de los vérticesadyacentes mejorando el valor de la función objetivo hasta encontrar el óptimo

Para el resto de la exposición sobre los fundamentos matemáticos del método Simplexse hará la suposición de que todas las soluciones básicas del programa son nodegeneradas (hipótesis de no degeneración). No obstante, el no verificarse esta hipótesisno altera la validez de las conclusiones a las que se llegará.

Page 2: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 2/27

 

EL METODO SIMPLEX PARA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL

Es un procedimiento iterativo que permite ir mejorandola solución a cada paso. El proceso concluye cuando no

es posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vérticecualquiera, el método consiste en buscar sucesivamenteotro vértice que mejore al anterior. La búsqueda se hacesiempre a través de los lados del polígono (o de lasaristas del poliedro, si el número de variables es mayor).Cómo el número de vértices (y de aristas) es finito,siempre se podrá encontrar la solución.

El método del simplex se basa en la siguientepropiedad: si la función objetivo, f , no toma su valor máximo en el vértice A, entonces hay una arista queparte de A, a lo largo de la cual f aumenta.

 

El método del simplex fuecreado en 1947 por el

matemático GeorgeDantzig .

El método del simplex seutiliza, sobre todo, pararesolver problemas de

programación lineal en losque intervienen tres o más

variables.

El álgebra matricial y elproceso de eliminación de

Gauss-Jordan para

resolver un sistema deecuaciones lineales

constituyen la base delmétodo simplex. 

Con miras a conocer la metodología que se aplica en el Método SIMPLEX,vamos a resolver el siguiente problema:

Maximizar Z= f(x,y)= 3x +

2y 

sujeto a: 2x + y 18 

  2x + 3y 42 

  3x + y 24

  x 0 , y 0

Se consideran las siguientes fases:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones, paraconvertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2x + y + h = 18 2x + 3y + s =42 3x +y + d = 24

2. Igualar la función objetivo a cero

- 3x - 2y + Z = 0  

Page 3: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 3/27

 

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables del problema y, en las filas, los

coeficientes de las igualdades obtenidas, una fila para cada restricción y laúltima fila con los coeficientes de la función objetivo:

Tabla I . Iteración nº 1

Base Variable de decisión Variable de holgura Valores solución

   x y h s d    

h 2 1 1 0 0 18

s 2 3 0 1 0 42

d  3 1 0 0 1 24

Z  -3 -2 0 0 0 0

4. Encontrar la variable de decisión que entra en la base y la variable deholgura que sale de la base

A. Para escoger la variable de decisión que entra en la base, nos fijamosen la última fila, la de los coeficientes de la función objetivo y escogemosla variable con el coeficiente negativo mayor (en valor absoluto).En nuestro caso, la variable x de coeficiente - 3.

Si existiesen dos o más coeficientes iguales que cumplan la condición

anterior, entonces se elige uno cualquiera de ellos.

Si en la última fila no existiese ningún coeficiente negativo, significa quese ha alcanzado la solución óptima. Por tanto, lo que va a determinar elfinal del proceso de aplicación del método del simplex, es que en laúltima fila no haya elementos negativos.

La columna de la variable que entra en la base se llama columna pivote(En color azulado).

B. Para encontrar la variable de holgura que tiene que salir de la base, sedivide cada término de la última columna (valores solución) por eltérmino correspondiente de la columna pivote, siempre que estos últimossean mayores que cero. En nuestro caso:

18/2 [=9] , 42/2 [=21] y 24/3 [=8]

Si hubiese algún elemento menor o igual que cero no se hace dichocociente. En el caso de que todos los elementos fuesen menores oiguales a cero, entonces tendríamos una solución no acotada y no sepuede seguir.

El término de la columna pivote que en la división anterior dé lugar almenor cociente positivo, el 3, ya 8 es el menor, indica la fila de la

Page 4: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 4/27

 

variable de holgura que sale de la base, d . Esta fila se llama fila pivote(En color azulado).

Si al calcular los cocientes, dos o más son iguales, indica que cualquierade las variables correspondientes pueden salir de la base.

C. En la intersección de la fila pivote y columna pivote tenemos el elementopivote operacional, 3. 

5. Encontrar los coeficientes de la nueva tabla.

Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de lafila d por el pivote operacional, 3, que es el que hay que convertir en 1.

A continuación mediante la reducción gaussiana hacemos ceros los restantes

términos de su columna, con lo que obtenemos los nuevos coeficientes de lasotras filas incluyendo los de la función objetivo Z .

También se puede hacer utilizando el siguiente esquema:

Fila del pivote:

Nueva fila del pivote= (Vieja fila del pivote) : (Pivote) 

Resto de las filas:

Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de lavariable entrante) X (Nueva fila del pivote) 

Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x en laTabla II):

Vieja fila de s 2 3 0 1 0 42  - - - - - -Coeficiente 2 2 2 2 2 2  x x x x x x

Nueva fila pivote 1 1/3 0 0 1/3 8  = = = = = =Nueva fila de s 0 7/3 0 1 -2/3 26

 

Tabla II . Iteración nº 2

Base Variable de decisión Variable de holgura Valores solución

   x y h s d    h 0 1/3 1 0 -2/3 2

Page 5: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 5/27

 

s 0 7/3 0 1 -2/3 26

 x  1 1/3 0 0 1/3 8

Z  0 -1 0 0 1 24

Como en los elementos de la última fila hay uno negativo, -1, significa que nohemos llegado todavía a la solución óptima. Hay que repetir el proceso:

A. La variable que entra en la base es y , por ser la variable quecorresponde al coeficiente -1 

B. Para calcular la variable que sale, dividimos los términos de la últimacolumna entre los términos correspondientes de la nueva columnapivote:2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8]y como el menor cociente positivo es 6, tenemos que la variable deholgura que sale es h.

C. El elemento pivote, que ahora hay que hacer 1, es 1/3. 

Operando de forma análoga a la anterior obtenemos la tabla:

Tabla III . Iteración nº 3

Base Variable de decisión Variable de holgura Valores solución

   x y h s d    

y  0 1 3 0 -2 6

s 0 0 -7 0 4 12

 x  1 0 -1 0 1 6

Z  0 0 3 0 -1 30

Como en los elementos de la última fila hay uno negativo, -1, significa que nohemos llegado todavía a la solución óptima. Hay que repetir el proceso:

A. La variable que entra en la base es d , por ser la variable quecorresponde al coeficiente -1 

B. Para calcular la variable que sale, dividimos los términos de la últimacolumna entre los términos correspondientes de la nueva columnapivote:

6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6]y como el menor cociente positivo es 3, tenemos que la variable deholgura que sale es s.

C. El elemento pivote, que ahora hay que hacer 1, es 4. 

Obtenemos la tabla:

Tabla IV . Final del proceso

Base Variable de decisión Variable de holgura Valores solución   x y h s d    

Page 6: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 6/27

 

y  0 1 -1/2 0 0 12

d  0 0 -7/4 0 1 3

 x  1 0 -3/4 0 0 3

Z  0 0 5/4 0 0 33

Como todos los coeficientes de la fila de la función objetivo son positivos,hemos llegado a la solución óptima.

Los solución óptima viene dada por el valor de Z en la columna de los valoressolución, en nuestro caso: 33. En la misma columna se puede observar elvértice donde se alcanza, observando las filas correspondientes a las variablesde decisión que han entrado en la base: D(3,12) 

* Si en el problema de maximizar apareciesen como restricciones inecuaciones

de la forma: ax + by c; multiplicándolas por - 1 se transforman eninecuaciones de la forma - ax - by - c y estamos en el caso anterior  

* Si en lugar de maximizar se trata de un problema de minimizar se sigue elmismo proceso, pero cambiando el sentido del criterio, es decir, para entrar enla base se elige la variable cuyo valor, en la fila de la función objetivo, sea elmayor de los positivos y se finalizan las iteraciones cuando todos loscoeficientes de la fila de la función objetivo son negativos

Interpretación geométrica del método delsimplex

Las sucesivas tablas que hemos construido van proporcionando el valor de lafunción objetivo en los distintos vértices, ajustándose, a la vez, los coeficientesde las variables iniciales y de holgura.

En la primera iteración (Tabla I) han permanecido todos los coeficientesiguales, se ha calculado el valor de la función objetivo en el vértice A(0,0),siendo este 0.

A continuación se desplaza por la arista AB, calculando el valor de f , hastallegar a B.Este paso aporta la Tabla II.En esta segunda iteración se ha calculado el valor quecorresponde al vértice B(8,0): Z=f(8,0) = 24

Sigue por la arista BC, hasta llegar a C, donde se para ydespliega los datos de la Tabla III.En esta tercera iteración se ha calculado el valor quecorresponde al vértice C(6,6) : Z=f(6,6)=30.

Page 7: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 7/27

 

Continua haciendo cálculos a través de la arista CD, hasta llegar al vértice D.Los datos que se reflejan son los de la Tabla IV.Concluye con esta tabla, advirtiendo que ha terminado (antes ha comprobadoque la solución no mejora al desplazarse por la arista DE)El valor máximo de la función objetivo es 33, y corresponde a x = 3 e y = 12

(vértice D).

Si calculas el valor de la función objetivo en el vértice E(0,14), su valor nosupera el valor 33.

El método Simplex Tabular

Page 8: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 8/27

 

La resolución de programas lineales mediante el método Simplex implica la realizaciónde gran cantidad de cálculos, sobre todo cuando el número de variables y/o restriccioneses relativamente elevado. Sin embargo, estos cálculos no son complejos y puedenrealizarse en modo sistemático utilizando una forma tabular. Así surgen las conocidascomo tablas del Simplex, que no son más que una forma de organizar los cálculos.

Sobre las tablas del Simplex comentar que su interés es totalmente pedagógico, ya queen los casos reales la magnitud de los problemas que suelen aparecer hace que nadie lasutilize de forma directa para resolverlos. En tales casos, ha de recurrirse al uso delcomputador.

Para aplicar el método Simplex en forma de tabla a un problema de la forma:

min cx

 Ax= b con b >= 0

x >= 0

en primer lugar se construye la tabla siguiente:

c1 c2 ... cn

cb1

cb2

.

.

.

cbm

xb1

xb2

.

.

.

xbm

b1

b2

.

.

.

bm

a11 a12 ... a1n

a21 a22 ... a2n

... ... ... ...

... ... ... ...

... ... ... ...

am1 am2 ... amn

v y1 y2 ... ym

z1 z2 ... zm

Tabla del Simplex

Donde:

• v es el producto escalar de los vectores(cb1,cb2,...,cbm)y (b1,b2,...,bm)  

• yk es el producto escalar de los vectores(cb1,cb2,...,cbm)y (a1k,a2k,...,amk)para

k=1,2,...m.

• zk=ck-yk para k=1,2,...,m.

Observar la forma en que se construye esta tabla:

• En la primera fila de la tabla se colocan los coeficientes de las variables en la función objetivo.

• En las tres primeras columnas aparecen los coeficientes de las variables básicas en la función objetivo, las variables

 básicas iniciales y el vector de términos independientes de las restricciones, respectivamente.

• La parte central de la tabla está formada por la matriz de coeficientes A .

• Los elementos de la penúltima fila son los productos escalares del vector de la primera columna con los vectores de la

tabla que quedan encima de cada uno de esos elementos.

• Finalmente, en la última fila aparece la diferencia de las f ilas primera y penúltima.

IMPORTANTE: 

 Las variables básicas iniciales deben tener una matriz de base asociada igual a la

identidad. En muchas ocasiones, al introducir las variables de holgura en lasrestricciones se genera una matriz básica identidad, que puede ser utilizada como base

inicial del algoritmo. En los casos en los que ésto no ocurra existen técnicas para

Page 9: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 9/27

 

obtener una submatriz identidad, como puede ser por ejemplo el uso de variables

artificiales. 

Cada tabla del Simplex está asociada a una solución básica factible. De forma que, una

vez construida la tabla inicial, deben establecerse las reglas que permitan obtener lastablas asociadas a las siguientes soluciones básicas, así como saber la solución básicaque lleva asociada cada tabla. Además es necesario saber cuando una tabla correspondea la solución óptima, esto último se consigue analizando los signos de la última fila dela tabla:

Si todos los elementos de la última fila de la tabla son mayores o iguales que cero, el 

óptimo ha sido alcanzado.

Cuando alguno de los elementos de la última fila es negativo, el valor óptimo puedemejorarse y por tanto debe construirse una nueva tabla de la manera siguiente:

• Se selecciona de la última fila el elemento negativo de mayor valor absoluto. La variable correspondiente al índice del

zi seleccionado es la que pasará a ser básica.

• Para saber a que variable básica sustituye, se dividen los valores de la tercera columna entre los valores positivos de la

columna de A seleccionada en el paso anterior (la que corresponde al elemento negativo de mayor valor absoluto). En

caso de no existir valores positivos, puede asegurarse que el problema no tiene óptimo finito.

• De todos los cocientes calculados se selecciona el mínimo, el elemento de la matriz A que ha servido para construir ese

valor mínimo es el que actuará como pivot y la variable de la segunda columna de la tabla en la posición de la fila del pivot es la que deja de ser básica.

• Mediante transformaciones elementales de filas sobre el bloque central de la tabla (el bloque de fondo amarillo en la

tabla) se llega a transformar en 1 el pivot y anular los restantes elementos de la correspondiente columna. Las únicastransformaciones que son permitidas son:

o Multiplicar por constantes la fila que contiene el pivot.

o Sumar o restar a una fila un múltiplo de la fila que contiene el pivot.

• Intercambiar las variables básicas en la segunda columna al mismo tiempo que se modifica el correspondiente elemento

de la primera columna.

• Calcular los nuevos valores de las dos últimas filas de la tabla de acuerdo a las instrucciones ya indicadas.

Se repiten todos estos procesos y se van transformando las tablas hasta que el test de parada sea positivo (todos los elementos de la última fila mayores o iguales que cero) encuyo caso se tiene:

• El óptimo se alcanza en el punto cuyas coordenadas son nulas excepto las correspondientes a las variables básicas, cuyos

valores aparecen en la tercera columna de la tabla óptima.

• El valor de la función en el óptimo es el que aparece en el último elemento de esa misma columna

Todas las tablas que se van obteniendo tienen dos características en común: loselementos de la tercera columna son todos ellos mayores o iguales que cero, salvo elúltimo (el que indica el valor de la función objetivo) que pudiera ser negativo. Por otrolado, las columnas de A asociadas a las variables básicas siempre forman una matriz

identidad.

Analizando más en profundidar cada una de las etapas expuestas, se puede comprobar lacorrespondencia con el método Simplex enunciado de una forma más teóricaanteriormente. Por supuesto, la mejor manera de comprender la resolución mediantetablas es con ejemplos particulares; a continuación se exponen dos de estos ejemplos.

Page 10: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 10/27

 

Ejemplo:Programa lineal Tabla Inicial

min 2x1-x2

-x1+x2+x3=2

2x1+x2+x4=6

x1,x2,x3,x4 >= 0

2 -1 0 0

00 x3

x4

26

-1 1 1 02 1 0 1

0 0 0 0 0

2 -1 0 0

Se toman como variables básicas x3 y x4 porque llevan asociadas como matriz de base

la identidad.

El elemento señalado en color rojo en la tabla es el que actuará como pivot, ha sidodeterminado teniendo en cuenta que en la última fila de la tabla solo hay un elemento

negativo; tras esto se debe calcular min{2/1,6/1}, dicho mínimo se obtiene a partir del pivot.

La posición del pivot dentro de la tabla indica:

• La variable x3 dejará de ser básica.

• La variable que la sustituye es x2 

Para construir la siguiente tabla, han de realizarse operaciones elementales sobre lasfilas del bloque central hasta conseguir que el pivot sea 1 y los restantes elementos de su

columna sean 0. En este caso el pivot ya tiene el valor 1, para anular el otro elemento dela columna basta restar a la segunda fila la primera. Tras estas manipulaciones, se

sustituye la variable x3 por x2 y el valor 0 de la primera columna de la tabla por c2=-1.

A continuación se realizan las operaciones que definen los elementos de las dos últimasfilas de la tabla para completar la segunda tabla del algoritmo.

Segunda Tabla

2 -1 0 0

-1

0

x2

x4

2

4

-1 1 1 0

3 0 -1 1

-2 1 -1 -1 01 0 1 0

Como puede observarse, la última fila de la tabla está formada por elementos mayores oiguales que cero todos ellos, lo que significa que se ha alcanzado un óptimo. Enconcreto, el óptimo se alcanza sobre el punto

x1=0 x2=2 x3=0 x4=4

El valor óptimo es además -2 (último elemento de la tercera columna de la tabla).

Page 11: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 11/27

 

Ejemplo:Programa lineal Formulación estándar

min -x1-x2

-x1+x2 <= 2

x1+2x2 <= 6

2x1+x2 <= 6

x1,x2 >= 0

min -x1-x2

-x1+x2+x3 = 2

x1+2x2+x4 = 6

2x1+x2+x5 = 6

x1,x2,x3,x4,x5 >= 0

Las variables x3, x4 y x5 tienen como matriz de base a la identidad, de forma que pueden

tomarse como variables básicas iniciales. Aplicando el algoritmo Simplex, en tres tablasse obtiene el óptimo:

Tabla Inicial Segunda Tabla

-1 -1 0 0

0

0

0

0

x3

x4

x5

2

6

6

-1 1 1 0

0

1 2 0 1

0

 2 1 0 0

1

00 0 0 0

0

-1 -1 0 0

0

-1 -1 0 0 0

0

0

-1

x3

x4

x1

5

3

3

0 3/2 1 0 1/2

0 3/2 0 1 -1/2

1 1/2 0 0 1/2

-3-1 -1/2 0 0

-1/2

0 -1/2 0 0

1/2

Tercera Tabla Optimo-1 -1 0 0 0

0

-1

-1

x3

x2

x1

2

2

2

0 0 1 -1 1

0 1 0 2/3

-1/3

1 0 0 -1/3

2/3

-4-1 -1 0 -1/3

-1/3

0 0 0 1/3

1/3

x1=2

x2=2

x3=2

x4=0

x5=0

Valor óptimo = -4

Cada tabla del Simplex lleva asociado un punto cuyas coordenadas se obtienen en latercera columna para sus variables básicas y son nulas el resto. En la siguiente figura seencuentra representado el espacio de soluciones factibles del problema, indicándoseademás los vértices correspondientes a cada una de las tres tablas obtenidas.

Uso de variables artificiales

 No siempre es posible en la tabla del Simplex disponer de un conjunto de vectores que,convenientemente ordenados, formen la matriz identidad. Una forma de conseguirlo esañadir unas nuevas variables al problema que se conocen como variables artificiales.

Una vez que el problema lineal se encuentra en su forma estándar (introduciendo si esnecesario las variables de holgura), se suman estas variables artificiales a las

Page 12: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 12/27

 

restricciones necesarias para poder obtener una matriz básica igual a la identidad.Lógicamente para que estas variables introducidas no afecten a la solución del

 problema, lo deseable es que dejen de ser básicas rápidamente y de esta manera seanulen. La forma de conseguirlo es añadiéndolas a la función objetivo con uncoeficiente muy alto positivo (se le puede representar por M). De esta manera, para

minimizar la función objetivo deben anularse estas variables, con lo que en alguna delas iteraciones del método Simplex las variables artificiales dejan de ser básicas y a

 partir de ese momento puede prescindirse de ellas.

El siguiente ejemplo trata de ilustrar la forma de utilizar las variables artificiales paraobtener una solución básica inicial con matriz de base igual a la identidad.

Ejemplo:Programa lineal Formulación estándar

min  x1-x2

x1+2x2 >= 6

2x1+x2 <= 6

4x1+x2= = 4

x1,x2 >= 0

min  x1-x2

x1+2x2-x3 = 6

2x1+x2+x4 = 6

4x1+x2= = 4

x1,x2,x3,x4 >= 0

De la matriz A del problema no se puede obtener una submatriz igual a la identidad.

Podría por tanto, recurrirse a introducir dos variables artificiales x5 y x6. Observar como

se introducen esas variables en la función objetivo con un coeficiente M que se supone

muy grande. Además al añadir esas variables a la primera y tercera restricción se

consigue, tomando como variables básicas x5, x4 y x6, una matriz básica igual a laidentidad. Por la propia construcción, en el óptimo las variables artificiales se anularány por tanto las restricciones no se verán afectadas por la modificación que suponeañadirlas.

El problema tras introducir las variables artificiales sería:

min  x1-x2+Mx5+Mx6

x1+2x2-x3+x5 = 6

2x1+x2+x4 = 6

4x1

+x2

+x6

= = 4x1,x2,x3,x4,x5,x6 >= 0

Y aplicando el método Simplex se obtiene el óptimo tras cuatro tablas:

Tabla Inicial

1 -1 0 0 M M

M

0

M

x5

x4

x6

6

6

4

1 2 -1 0 1 0

2 1 0 1 0 0

  4 1 0 0 0 1

10M 5M 3M -M 0 M M1-5M -1-3M M 0 0 0

Page 13: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 13/27

 

Para un valor muy grande de M los dos primeros elementos de la última fila de la tabla

son negativos y de ellos es el primero el que tiene mayor valor absoluto, es por tanto enla primera columna en la que se busca el pivot.

Tras efectuar las correspondientes transformaciones, las sucesivas tablas son:

Segunda Tabla

1 -1 0 0 M M

M

0

1

x5

x4

x1

5

4

1

0 7/4 -1 0 1

-1/4

0 1/2 0 1 0

-1/2

1 1/4 0 0 0

1/4

5M+11 (7M+1)/4 -M 0 M (-

M+1)/4

0 (-7M-5)/4 M 0 0 (5M-

1)/4

Obsérvese como una de las variables artificiales ha dejado de ser básica.

Tercera Tabla

1 -1 0 0 M

M

-1

0

1

x2

x4

x1

20/7

18/7

2/7

0 1 -4/7 0 4/7

-1/7

0 0 2/7 1 -2/7

-3/7

1 0 1/7 0 -1/7

2/7

-18/71 -1 5/7 0 -5/7

3/7

0 0 -5/7 0 M+5/7

M-3/7

En la tercera tabla ya han desaparecido de la lista de variables básicas las dosartificiales. A partir de este momento puede prescindirse de las dos últimas columnas dela tabla, de forma que la siguiente tabla sería:

Cuarta Tabla

1 -1 0 0

-1

0

0

x2

x4

x3

4

2

2

4 1 0 0

-2 0 0 1

7 0 1 0

-4 -4 -1 0 0

5 0 0 0

Al no existir ningún valor negativo en la última fila, el óptimo ha sido encontrado en el punto correspondiente a:

x1=0 x2=4 x3=2 x4=2

Page 14: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 14/27

 

siendo el valor óptimo del problema -4.

Page 15: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 15/27

 

Introducción. La PL es una técnica mediante la cual se toman decisiones, reduciendo el problema bajoestudio a un modelo matemático general, el cual debe ser resuelto por métodoscuantitativos.

En desarrollo de este capítulo se aplicarán la solución de dichos modelos aplicandodiversas técnicas como: el método gráfico, método simplex, método matricial, técnicade la gran M.

Además se desarrollara la aplicación de variables artificiales y obtención de soluciones para identificar a que tipo de clasificación pertenecen. Por medio de dichos modelos desolución se podrá obtener las solución adecuada para cada problema y facilitar la tomade decisiones.

Método gráfico. 

El método gráfico se utiliza para la solución de problemas de PL, representandogeométricamente a las restricciones, condiciones técnicas y el objetivo.

El modelo se puede resolver en forma gráfica si sólo tiene dos variables. Para modeloscon tres o más variables, el método gráfico es impráctico o imposible.

Cuando los ejes son relacionados con las variables del problema, el método es llamadométodo gráfico en actividad. Cuando se relacionan las restricciones tecnológicas sedenomina método gráfico en recursos.

Los pasos necesarios para realizar el método son nueve:1. graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfagantodas las restricciones en forma simultánea.2. Las restricciones de no negatividad Xi>= 0 confían todos los valores posibles.3. El espacio encerrado por las restricciones restantes se determinan sustituyendo en

 primer término <= por (=) para cada restricción, con lo cual se produce la ecuación deuna línea recta.4. trazar cada línea recta en el plano y la región en cual se encuentra cada restriccióncuando se considera la desigualdad lo indica la dirección de la flecha situada sobre lalínea recta asociada.

5. Cada punto contenido o situado en la frontera del espacio de soluciones satisfacentodas las restricciones y por consiguiente, representa un punto factible.6. Aunque hay un número infinito de puntos factibles en el espacio de soluciones, lasolución óptima puede determinarse al observar la dirección en la cual aumenta lafunción objetivo.7. Las líneas paralelas que representan la función objetivo se trazan mediante laasignación de valores arbitrarios a fin de determinar la pendiente y la dirección en lacual crece o decrece el valor de la función objetivo.

Ejemplo.Maximizar Z = 3X1 + 2X2

restricciones : X1 + 2X2 <=6 (1)2X1 + X2 <=8 (2)

Page 16: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 16/27

 

-X1 + X2 <=1 (3)X2 <= 2 (4)

X1 >= 0 (5)X2 >= 0 (6)

Convirtiendo las restricciones a igualdad y representandolas gráficamente se tiene:

X1 + 2X2 = 6 (1)2X1 + X2 = 8 (2)-X1 + X2 = 1 (3)

X2 = 2 (4)X1 = 0 (5)

X2 = 0 (6)

Figura 1 Espacio de solución presentada con WinQsb

Figura 2 Determinación de solución

Page 17: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 17/27

 

soluciones

Maximizar Z = 3X1 + 2X2

Punto (X1, X2) ZA (0, 0) 0B (4, 0) 12C (3.3, 1.3) 12.6

( óptima )D (2, 3) 12E (1, 3) 9F (0, 2) 4

Tabla 2. Solución Método Gráfico

 Para obtener la solución gráfica, después de haber obtenido el espacio de solución y graficada la función objetivo el factor clave consiste en decidir la dirección de mejora

de la función objetivo. 

MÉTODO SIMPLEX. (Dantzig 1940) 

regresar 

En la solución gráfica observamos que la solución óptima está asociada siempre con un punto extremo del espacio de soluciones. El método simplex está basadofundamentalmente en este concepto.

Careciendo de la ventaja visual asociada con la representación gráfica del espacio desoluciones, el método simplex emplea un proceso interativo que principia en un puntoextremo factible, normalmente el origen, y se desplaza sistemáticamente de un punto

extremo factible a otro, hasta que se llega por último al punto óptimo.

Existen reglas que rigen la selección del siguiente punto extremo del método simplex:1. El siguiente punto extremo debe ser adyacente al actual.2. La solución no puede regresar nunca a un punto extremo considerado con laanterioridad.

El algoritmo simplex da inicio en el origen, que suele llamarse solución inicial. Despuésse desplaza a un punto extremo adyacente. La elección específica de uno a otro puntodepende de los coeficientes de la función objetivo hasta encontrar el punto óptimo.Al aplicar la condición de optimidad a la tabla inicial seleccionamos a Xi como la

variable que entra. En este punto la variable que sale debe ser una de las variablesartificiales.

Page 18: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 18/27

 

Los pasos del algoritmo simplex son ( 10 ) :

1. Determinar una solución básica factible inicial.2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima y sólosi todos los coeficientes de la ecuación son no negativos ( >= 0 ). Si es así, el proceso

termina; de otra manera se lleva a cabo otra interacción para obtener la nueva solución básica factible inicial.3. Condición de factibilidad.- Para todos los problemas de maximización yminimización, variable que sale es la variable básica que tiene la razón más pequeña(positiva). Una coincidencia se anula arbitrariamente.4. Seleccionar las variables de holgura como las variables básicas de inicio.5. Selecciona una variable que entra de entre las variables no básicas actuales que,cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Sino existe la solución básica es la óptima, si existe pasar al paso siguiente.6. Realizar el paso iterativo.a) Se determina la variable básica entrante mediante la elección de la variable con el

coeficiente negativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarcala columna correspondiente a este coeficiente y se le da el nombre de columna pivote.

 b) Se determina la variable básica que sale; para esta, se toma cada coeficiente positivo(>0) de la columna enmarcada, se divide el lado derecho de cada renglón entre estoscoeficientes, se identifica la ecuación con el menor cociente y se selecciona la variable

 básica para esta ecuación.c) Se determina la nueva solución básica factible construyendo una nueva tabla en laforma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar elcoeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo elrenglón entre el número pivote, entonces

renglón pivote nuevo = renglón pivote antiguonúmero pivote

 para completar la primera iteración es necesario seguir usando la eliminación de Gauss para obtener coeficientes de 0 para la nueva variable básica Xj en los otros renglones, para realizar este cambio se utiliza la siguiente fórmula:

renglón nuevo = renglón antiguo - ( coeficiente de la columna pivote X renglón pivotenuevo)

cuando el coeficiente es negativo se utiliza la fórmula:

renglón nuevo = renglón antiguo + (coeficiente de la columna pivote X renglón pivotenuevo)

TABLA SIMPLEX como se capturaría la solución básica factible inicial en el siguiente ejemplo:

sea:

Page 19: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 19/27

 

Maximizar Z = 2X1+4X2sujeto a:

2X1+ X2<= 230X1+ 2X2<= 250

X2<= 120todas las X1,X2>=0

BASE Z X1 X2 S1 S2 S3 SOLUCIÓN RAZÓN

Z 0 -2 -4 0 0 0 0 0

S1 0 2 1 1 0 0 230 230/1

S2 0 1 2 0 1 0 250 250/2

S3 0 0 1 0 0 1 120 120/1

Seleccione la variable que entra y la variable que sale de la base:

Entra X2 y sale S3, se desarrolla la nueva tabla solución y se continua el procesoiterativo hasta encontrar la solución optima si es que está existe.

Tabla Optima:

BASE Z X1 X2 S1 S2 S3 SOLUCIÓN RAZÓN

Z 0 0 0 0 2 0 500

S1 0 0 0 1 -2 3 90

X1 0 1 0 0 1 -2 10

X2 0 0 1 0 0 1 120

Solución: Z = $500fabricandoX1=10X2=120Sobrante deS1 = 90Tipo de solución: Optima Múltiple 

Solución de problemas en donde la solución continua no sea aplicable 

regresar  

Page 20: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 20/27

 

Uso de paquetes computacionales en la solución e interpretación delos resultados

Puedes bajar el tutorial de WinQsb+

Tutorial WinQsb+

regresar  

WinQsb+: Software de apoyo para resolver los modelos de programación lineal.

 Interpretación de los resultados: Veamos la salida de un modelo que involucra la planeación de la producción, en donde se desean construir mesas y sillas el recursodisponible es 30 m2 de madera por semana, 48 horas por semana; la demanda de las

sillas es de 5 unidades y la de mesas de 10 unidades, la utilidad que se obtiene por lasmesas es de $10 y por las sillas de $8, ademas para construir la mesa se ocupa losiguiente: 4.5 m2 de madera por unidad, 6 horas por unidad. Para la silla se ocupan: 1.5m2 de madera por unidad y 3 horas por cada unidad fabricada.Con esta información se desarrolla el modelo siguiente:

Max Z = 10X1+8X2 s.a.4.5X1+1.5X2 <= 306.0X1+3.0X2 <= 48toda X1,X2 >=0

 El reporte final de este modelo es el siguiente (por WinQsb) 

DecisionVariable

SolutionValue

Unit Cost or Profit cjTotal

ContributionReduced

CostBasisStatus

AllowableMin cj

AllowableMax cj

X1 0 10.0000 0 -6.0000 at bound -M 16.0000

X2 16.0000 8.0000 128.0000 0 basic 5.0000 M

Objetive Function (Max) = 128.0000

ConstraintLeft Hand

SideDirection

Rigth HandSide

Slack or Surplas

ShadowPrice

AllowableMin. RHS

AllowableMax. RHS

C1 24.0000 <= 30.0000 6.0000 0 24.0000 MC2 48.0000 <= 48.0000 0 2.6667 0 60.0000

INTERPRETACIÓN DE LA SALIDA:

 Información de la Función Objetivo: 

Decision Variable (Variable de Decisión): Son las variables que se han definido en laformulación del problema en este caso representan al producto X1 = mesas y X2=sillas.

Page 21: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 21/27

 

Solution Value (Valor de la solución): Cantidad de mesas y sillas a fabricar, el problemase resuelve y nos indica que para obtener la mejor solución en términos de la utilidad, senecesitan fabricar 16 sillas y no fabricar mesas.

Unit Cost or Profit (costo por unidad, Utilidad por unidad): Cantidad de pesos que

vamos a ganar por cada mesa y por cada silla ($10 y $8 respectivamente.

Total Contribution (contribución total): Es la cantidad en pesos que resulta almultiplicar la utilidad de cada producto por la cantidad que se va a fabricar, ejemplo alfabricar 16 sillas y multiplicarlo por $/silla 8, la contribución es de $128.0000, así alsumar la contribución por concepto de las mesas nos arroja una aportación de $0.0000,esto resulta de hacer la operación de ($/mesa10) (0mesas)= $0.0000, finalmente la sumade 128.0000+0.0000 = $128.0000, esto es lo que se conoce como el valor de ObjetiveFunction Max.

Reduced Cost (Costo reducido): esto nos indica el dinero que hemos dejado de ganar 

 por cada unidad no fabricada. en este caso debemos de aumentar a mas de $6.0000 lautilidad de la mesa para que sea atractiva la fabricación de mesas.

Basis Status (estado de la base): Indica si la variable es básica o no básica, en esteejemplo la variable X1 (mesas) resulta ser no básica, esto es que no forma parte de lasolución óptima, la variable X2 (sillas) es una variable básica, ya que forma parte de lasolución.

Allowed Min cj (rango mínimo del cj): esta es la mínima utilidad que puedo obtener sinque la base actual cambie. (-M)

Allowed Max cj (rango mínimo del cj): esta es la máxima utilidad que puedo obtener sin que la base actual cambie. (16.0000)

los valores que aparecen son para el producto Mesa.

 Interpretación de las Restricciones: 

Constraint (Restricción): Son las restricciones que forman parte del problema, se tienendos restricciones (C1 y C2) la restricción de la madera y la de horas hombre.

Left hand side (valor al lado izquierdo): esto nos indica el consumo de recurso, de30.000 m2 de madera se consumieron 24.000 m2.

Direction (dirección): es la dirección de la restricción (<=,>= o =)

Rigth hand side (valor lado derecho): es el recurso disponible actualmente 30 m 2 

Slack or Surplas (holguras): nos indican un faltante o bien un sobrante

Shadow Price (precio sombra): nos indica la solución Dual, esto es que el 2.6667 indicaque cada hra-hombre se debe ofrecer como mínimo en $/hr 2.6667.

Page 22: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 22/27

 

Allowed Min RHS (rango mínimo del bj): esta es la mínima cantidad de recurso que sedebe de mantener sin que la base actual cambie. (0 hrs-hombre)

Allowed Max RHS (rango mínimo del bj): esta es la máxima cantidad de recurso que sedebe de mantener sin que la base actual cambie (60.0000 hrs-hombre)

Page 23: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 23/27

 

ALGORITMO SIMPLEX PARA PROBLEMAS DE MINIMIZACIÓN.VERSIÓN ALGEBRAICA.

PASO 1 Seleccionar una SBF inicial con base B.

PASO 2 Calcular los valores de las variables básicasb B x B

1−=Calcular el valor de la Función Objetivo

b Bc z   B

1−=

PASO 3 Calcular, para todas las variables no básicas, los valores de

 j j B j j ca Bcc z  −=− −1

.Tomar 

 j j I  j

k k  c z maxc z  N 

−=−∈

Si0≤− k k  c z 

[1]

se verifica el criterio de optimalidad simplex (  N  j j  I  jc z  ∈∀≤− 0) y el algoritmo

termina. La SBF actual es óptima. Si la expresión [1] fuera nula entonces dichasituación corresponde a infinitas soluciones óptimas alternativas.

Si la condición [1] no se verifica pasar al PASO 4. La variable k  xentra en la base.

PASO 4 Para determinar la variable de salida de la base (denominadavariable de bloqueo), se plantea el sistema de ecuaciones

k  B  x yb x ⋅−= [2]siendo

   

 

 

 

 ==

   

 

 

 

 

== −−

mk 

m  y

 y

a B y

b

b

b Bb

1

1

1

1 ,

Ahora, la variable k  xentra en la base y la variable de bloqueo r  B x

sale de ella. El índicer se determina mediante el siguiente criterio de la razón mínima

>=≤≤

0:1

ik 

ik 

i

mirk 

r   y

 y

bMinimo

 y

b

.

Si dicho valor  rk 

 y

b

no existe entonces el problema tiene solución no acotada y elalgoritmo se detiene.Se pasa al PASO 5.

PASO 5 Se modifica la composición de la matriz básica B, en la que k a 

reemplaza a r  Ba.

Se modifica el conjunto de índices  N  I  .Se vuelve al PASO 2.

Page 24: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 24/27

 

PROGRAMACION LINEAL

TRABAJO PRACTICO Nº 3: METODO SIMPLEX

 

1) Considerar las siguientes restricciones de un problema

lineal:

 x1+ 2x2 ≤ 6

x1- x2 ≤ 4

x2 ≤ 4

x1, x2 ≥ 0 

a) Graficar la región factible.

b) Identificar los puntos extremos y en cada uno de ellos

las variables básicas y no básicas.

c)Suponer que en el espacio (x1,x2 )el algoritmo se mueve

del punto extremo (4,0)

t

al punto extremo (14/3, 2/3)

t

.Especificar cuál es la variable que entró y cuál la que

salió.

 

2) Resolver usando Simplex en forma de tabla.

 

a)Max x= x1- 2x2+ x3 b) Max x= 3x1+ 2x2

Suj.a: x1+ x2+ x3 ≤ 12 Suj.a: 2x1- 3x2 ≤2

2x1+ x2- x3 ≤ 6 -x1+ x2 ≤ 5

-x1+ 3x2  ≤ 9 xi≥ 0, i=1,2xi≥ 0, i=1,2,3

 

3)  A continuación se muestran la tabla inicial y la tabla

actual de un P.L. Calcular los valores de las incógnitas

de a a l.

 

Tabla inicial 

z x1 x2 x3 x4 x5 LD

1 a 1 -2 0 0 0

0 b c d 1 0 6

0 -1 3 e 0 1 1 

Tabla actual

z x1 x2 x3 x4 x5 LD

1 0 7 j k l 9

0 g 2 -1 1/2 0 f

0 h i 1 1/2 1 4

 

4) Una dietética dispone de 150 kg. de nuez, 100 kg. de

avellana y 50 kg. de almendras. Puede vender tres tipos de

mezclas de estos productos : una mezcla barata que consiste

de 80% de nuez, 10% de avellana y 10% de almendras, una

Page 25: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 25/27

 

mezcla para fiesta que consiste de 50% de nuez, 30% de

avellana y 20% de almendras, y una mezcla de lujo 20% de

nuez, 50% de avellana y 30% de almendras. Si la lata de 12

kg. de la mezcla barata, la mezcla para fiesta y la mezcla

de lujo se pueden vender en $0,9, $1,1 y $1,3

respectivamente, que se debe producir para maximizar laganancia de la dietética ?.

 

5) Considerar el siguiente problema :

 

Max x= -x1- 2x2+ x3 

Suj. a: 2x1+ x2+ x3 ≤ 6

2x2- x3 ≥ -3xi ≥ 0, i=1,2,3

 

a) Obtener la solución optima por el método simplex. En

cada iteración identificar B-1 , cB.B-1.

b) En optimalidad determinar ∂x1 /∂x3, ∂z/∂x5 ,∂ xB/∂ xn ,

donde x5 es la variable de holgura de la segunda

restricción. Interpretar estos valores.

c) Cual es la rapidez de incremento del objetivo como

funcion del lado derecho de la primera y segunda

restricción respectivamente?.

d) Suponer que b1 se cambia de 6 a 6+∆ . Calcular el rango

de ∆ que mantendría la solución optima y factible

hallada en (a).

 6) Considere el siguiente tableau simplex para un problema

de minimización (las restricciones son del tipo y x3, x4

y x5 son las variables de holgura)

 

z x1 x2 x3 x4 x5 LD

1 0 a 0 b 0 f  

0 1 -2 0 1 0 c

0 0 -1 1 2 0 d

0 0 0 0 3 1 e

 Suponga que a < 0, b 0 y c, d, e 0.

 

a.Encuentre B-1.

b. Encuentre B.

c.Es el tableau óptimo?

d.Dé el tableau original.

e.A partir del tableau identifique y dé su

interpretación.

Ahora suponga que a > 0, b 0 y c, d, e 0.

f.Es el nuevo tableau óptimo?g.Sea a=3 y f = - 8. Dé una solución factible con z= -200.

 

Page 26: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 26/27

 

 

7) Resuelva el siguiente problema de programación lineal

por el método simplex en cada iteración identifique B y B-

1.

 

8) Considerar el siguiente problema lineal :

Minimizar cx, sujeto a : Ax ≤ b, x ≥ 0

donde c es un vector distinto de cero. Dado x0/ A x0<b y x0

> 0 Demostrar que x0 no puede ser una solución optima.

Page 27: El método Simplex

5/13/2018 El método Simplex - slidepdf.com

http://slidepdf.com/reader/full/el-metodo-simplex-55a74fd6d31a3 27/27