7/17/2019 metodo simplex2

http://slidepdf.com/reader/full/metodo-simplex2 1/5

Es un procedimiento iterativo que permite ir mejorando la solucióna cada paso. El proceso concluye cuando no es posible seguirmejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera,el método consiste en buscar sucesivamente otro vértice que

mejore al anterior. La bsqueda se hace siempre a través de loslados del pol!gono "o de las aristas del poliedro, si el nmero devariables es mayor#. $ómo el nmero de vértices "y de aristas# esfinito, siempre se podrá encontrar la solución.

El método del simple% se basa en la siguiente propiedad& si lafunción objetivo, f , no toma su valor má%imo en el vértice ',entonces hay una arista que parte de ', a lo largo de lacual f aumenta.

El método del simple% fue creadoen ()*+ por el matemático eorge-antig .

El método del simple% se utilia,

sobre todo, para resolver problemas de programación linealen los que intervienen tres o más

variables.

El álgebra matricial y el proceso deeliminación de auss/0ordan pararesolver un sistema de ecuaciones

lineales constituyen la base delmétodo simple%.

 

1amos a resolver mediante el método del simple% el siguiente problema&  

2a%imiar  Z= f(x,y)= 3x + 2y 

sujeto a& 2x + y 18 

  2x + 3y 42 

  3x + y 24

  % 3 , y 3

4e consideran las siguientes fases&

1. Convertir las desigualdades en igualdades

4e introduce una variable de holgura por cada una de las restricciones, para convertirlas 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 

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes delas igualdades obtenidas, una fila para cada restricción y la ltima fila con los coeficientes de la

función objetivo& 

5abla 6 . 6teración n7 (

8ase 1ariable de decisión 1ariable de holgura 1alores solución

   x y h s d   

h 9 ( ( 3 3 (:

7/17/2019 metodo simplex2

http://slidepdf.com/reader/full/metodo-simplex2 2/5

s 9 ; 3 ( 3 *9

d  3 ( 3 3 ( 9*

Z  /; /9 3 3 3 3

4. Encontrar la variable de decisión que entra en la base la variable de !olgura que sale

de la base

A. Para escoger la variable de decisión que entra en la base, nos fijamos en la ltima fila,

la de los coeficientes de la función objetivo y escogemos la variable con el coeficientenegativo mayor "en valor absoluto#.  En nuestro caso, la variable x  de coeficiente / ;.

  4i e%istiesen dos o más coeficientes iguales que cumplan la condición anterior,entonces se elige uno cualquiera de ellos.

  4i en la ltima fila no e%istiese ningn coeficiente negativo, significa que se haalcanado la solución óptima. Por tanto, lo que va a determinar el final del proceso de

aplicación del método del simple%, es que en la ltima fila no haya elementosnegativos.

La columna de la variable que entra en la base se llama colu!a "ivo#e "En

color  verde#. 

B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada

término de la ltima columna "valores solución# por el término correspondiente de lacolumna pivote, siempre que estos ltimos sean mayores que cero. En nuestro caso&  (:<9 =>)? , *9<9 =>9(? y 9*<; =>:?

 4i hubiese algn elemento menor o igual que cero no se hace dicho cociente. En elcaso de que todos los elementos fuesen menores o iguales a cero, entoncestendr!amos una solución no acotada y no se puede seguir.

  El término de la columna pivote que en la división anterior dé lugar al menor cocientepositivo, el ;, ya : es el menor, indica la fila de la variable de holgura que sale de labase, d . Esta fila se llama fila "ivo#e "En color verde#.

  4i al calcular los cocientes, dos o más son iguales, indica que cualquiera de las

variables correspondientes pueden salir de la base. 

C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote

operacional, 3.

". Encontrar los coeficientes de la nueva tabla.

Los nuevos coeficientes de x  se obtienen dividiendo todos los coeficientes de la fila d  por elpivote operacional, ;, que es el que hay que convertir en (.

 ' continuación mediante la reducción gaussiana hacemos ceros los restantes términos de sucolumna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la

función objetivo Z . 

7/17/2019 metodo simplex2

http://slidepdf.com/reader/full/metodo-simplex2 3/5

5ambién se puede hacer utiliando el siguiente esquema&

@ila del pivote&

#ueva fila del pivote$ %&ieja fila del pivote' ( %)ivote'

Aesto de las filas&

#ueva fila$ %&ieja fila' * %Coeficiente de la vieja fila en la columna de la variable entrante'

+ %#ueva fila del pivote'

1eámoslo con un ejemplo una ve calculada la fila del pivote "fila de % en la 5abla 66#&  

1ieja fila de s 9 ; 3 ( 3 *9

  / / / / / /

$oeficiente 9 9 9 9 9 9

  % % % % % %Bueva fila pivote ( (<; 3 3 (<; :

  > > > > > >

Bueva fila de s 3 +<; 3 ( /9<; 9C

 

5abla 66 . 6teración n7 9

8ase 1ariable de decisión 1ariable de holgura 1alores solución

   x y h s d   

h 3 1,3 ( 3 /9<; 9s 3 +<; 3 ( /9<; 9C

 x  ( (<; 3 3 (<; :

Z  3 /( 3 3 ( 9*

$omo en los elementos de la ltima fila hay uno negativo, /(, significa que no hemos llegadotodav!a a la solución óptima. Day que repetir el proceso&

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

/(

B. Para calcular la variable que sale, dividimos los términos de la ltima columna entre lostérminos correspondientes de la nueva columna pivote&

9&(<; =>C? , 9C&+<; =>+:<+? y :&(<; =>:? 

y como el menor cociente positivo es C, tenemos que la variable de holgura que salees h.

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

perando de forma análoga a la anterior obtenemos la tabla& 

5abla 666 . 6teración n7 ;

8ase 1ariable de decisión 1ariable de holgura 1alores solución

7/17/2019 metodo simplex2

http://slidepdf.com/reader/full/metodo-simplex2 4/5

   x y h s d   

y  3 ( ; 3 /9 C

s 3 3 /+ 3 4 (9

 x  ( 3 /( 3 ( C

Z  3 3 ; 3 /( ;3

$omo en los elementos de la ltima fila hay uno negativo, /(, significa que no hemos llegadotodav!a a la solución óptima. Day que repetir el proceso&

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

/(

B. Para calcular la variable que sale, dividimos los términos de la ltima columna entre los

términos correspondientes de la nueva columna pivote&

C<"/9# =>/;? , (9<* =>;?, y C&( =>C?  

y como el menor cociente positivo es ;, tenemos que la variable de holgura que sale

es s.

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

btenemos la tabla& 

5abla 61 . @inal del proceso

8ase 1ariable de decisión 1ariable de holgura 1alores solución

   x y h s d   

y  3 ( /(<9 3 3 12

d  3 3 /+<* 3 ( ; x  ( 3 /;<* 3 3 3

Z  3 3 F<* 3 0 33

$omo todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a lasolución óptima.

Los solución óptima viene dada por el valor de G en la columna de los valores solución, ennuestro caso& 33. En la misma columna se puede observar el vértice donde se alcana,observando las filas correspondientes a las variables de decisión que han entrado en la

base& -%312' 

H 4i en el problema de ma%imiar apareciesen como restricciones inecuaciones de la forma&

a% I by cJ multiplicándolas por / ( se transforman en inecuaciones de la forma / a% / by/ c y estamos en el caso anterior 

H 4i en lugar de ma%imiar se trata de un problema de minimiar se sigue el mismo proceso,pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variablecuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalian lasiteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos

7/17/2019 metodo simplex2

http://slidepdf.com/reader/full/metodo-simplex2 5/5

  Interpretación geom/trica del m/todo del simplex

Las sucesivas tablas que hemos construido van proporcionando el valor de la función objetivoen los distintos vértices, ajustándose, a la ve, los coeficientes de las variables iniciales y deholgura.

En la primera iteración "5abla 6# han permanecido todos los coeficientes iguales, se hacalculado el valor de la función objetivo en el vértice '"3,3#, siendo este 3.

 ' continuación se desplaa por la arista '8, calculando el valor de f , hasta llegar a 8.

Este paso aporta la 5abla 66. 

En esta segunda iteración se ha calculado el valor que corresponde al vértice 8":,3#& G>f":,3# >9*

4igue por la arista 8$, hasta llegar a $, donde se para y despliega los

datos de la 5abla 666. 

En esta tercera iteración se ha calculado el valor que corresponde alvértice $"C,C# & G>f"C,C#>;3.

$ontinua haciendo cálculos a través de la arista $-, hasta llegar al

vértice -. Los datos que se reflejan son los de la  5abla 61. 

$oncluye con esta tabla, advirtiendo que ha terminado "antes ha

comprobado que la solución no mejora al desplaarse por la arista -E#  

El valor má%imo de la función objetivo es ;;, y corresponde a % > ; e y > (9 "vértice -#.

4i calculas el valor de la función objetivo en el vértice E"3,(*#, su valor no supera el valor ;;.