Resolver Mediante El Método Simplex El Siguiente Problema

8/17/2019 Resolver Mediante El Método Simplex El Siguiente Problema

1/8

Resolver mediante el método simplex 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. Realizar un cambio de variables y normalizar el signo de los términosindependientes.

Se realiza un cambio en la nomenclatura de las variables. Establecindose lacorres!ondencia siguiente:

o x !asa a ser "1

o y !asa a ser "#

$omo los trminos inde!endientes de todas las restricciones son !ositivosno es necesario %acer nada. En caso contrario %abr&a 'ue multi!licar !or ()1(en ambos lados de la inecuaci*n +teniendo en cuenta 'ue esta o!eraci*ntambin afecta al ti!o de restricci*n.

Normalizar las restricciones.

Se convierten las inecuaciones en ecuaciones agregando variables deholgura, exceso y artificiales seg-n la tabla siguiente:

Tipo de desigualdad Tipo de variable que aparece

≥ ) exceso artificial

/ artificial

%olgura

En este caso se introduce una variable de %olgura +" , "2 y "3 en cadauna de las restricciones del ti!o , !ara convertirlas en igualdades, resultandoel sistema de ecuaciones lineales:

#4"1 "# " / 15

#4"1 4"# "2 / 2#

4"1 "# "3 / #2

Igualar la función obetivo a cero.

6 ) 4"1 ) "# ) 04" ) 04"2 ) 04"3 / 0


2/8

!scribir la tabla inicial del método "implex.

7a tabla inicial del mtodo Sim!lex est8 com!uesta !or todos los coeficientesde las variables de decisi*n del !roblema original y las de %olgura, exceso yartificiales agregadas en el !aso # +en las columnas, siendo 9 0 el trminoinde!endiente y el resto de variables 9 i coinciden con "i, y las restricciones

+en las filas. 7a columna $b contiene los coeficientes de las variables 'ue seencuentran en la base.

7a !rimera fila est8 formada !or los coeficientes de la funci*n objetivo,mientras 'ue la -ltima fila contiene el valor la funci*n objetivo y los costesreducidos 6 j ) $ j.

7a -ltima fila se calcula como sigue: 6 j / +$bi49 j !ara i / 1..m, donde si j/ 0, 90 / bi y $0 / 0, y en caso contrario 9 j / aij. ;un'ue al tratarse de la!rimera tabla del mtodo Sim!lex y ser todos los $b nulos se !uede sim!lificar el c8lculo, y !or esta vez dis!oner 6 j / )$ j.

Tabla I . Iteración n# $

# 0 0 0

%ase &b '( '$ ') '* '+ ',

9 0 15 # 1 1 0 0

92 0 2# # 0 1 0

93 0 #2 * 1 0 0 1

- 0 ) )# 0 0 0

&ondición de parada.

Si el objetivo es la maximizaci*n, cuando en la -ltima fila +fila indicadora noexiste ning-n valor negativo entre los costes reducidos +columnas 91 enadelante se alcanza la condici*n de !arada.

En tal caso se llega al final del algoritmo ya 'ue no existe !osibilidad demejora. El valor de 6 +columna 90 es la soluci*n *!tima del !roblema.


3/8

Se determina en !rimer lugar la variable 'ue entra en la base. 9ara ello seescoge la columna cuyo valor en la fila 6 sea el menor de entre todos losnegativos. En este caso ser&a la variable "1 +91 de coeficiente ).

Si existiesen dos o m8s coeficientes iguales 'ue cum!lan la condici*nanterior +caso de em!ate, entonces se o!tar8 !or a'uella variable 'ue sea

b8sica.

7a columna de la variable 'ue entra en la base se llama colu!a "ivote +en color verde.

>na vez obtenida la variable 'ue entra en la base, se !rocede a determinacual ser8 la variable 'ue sale de la misma. 7a decisi*n se toma en base a unsencillo c8lculo: dividir cada trmino inde!endiente +columna 90 entre elelemento corres!ondiente de la columna !ivote, siem!re 'ue ambos elementossean estrictamente !ositivos +mayores 'ue cero. Se escoge la fila cuyoresultado %aya resultado m&nimo.

Si %ubiera alg-n elemento menor o igual a cero no se realiza dic%ocociente. En caso de 'ue todos los elementos de la columna !ivote fueran desta condici*n se %abr&a cum!lido la condici*n de !arada y el !roblema tendr&auna soluci*n no acotada +ver teor&a del mtodo Sim!lex.

En este ejem!lo: 15?# @/AB , 2#?# @/#1B y #2? @/5B

El trmino de la columna !ivote 'ue en la divisi*n anterior dio lugar almenor cociente !ositivo indica la fila de la variable de %olgura 'ue sale de labase. En este caso resulta ser "3 +93, de coeficiente . Esta fila se llama fila

"ivote +en color verde.

Si al calcular los cocientes, dos o m8s resultados cum!len la condici*n!ara elegir el elemento saliente de la base +caso de em!ate, se escogea'uella 'ue no sea variable b8sica +siem!re 'ue sea es !osible.

7a intersecci*n de la fila "ivote y colu!a "ivote marca el elee!to !ivote,en este caso el .

ctualizar la tabla.

7os nuevos coeficientes de la tabla se calculan de la siguiente manera:

o En la fila del elemento !ivote cada nuevo elemento se calcula como:

#uevo $lee!to %ila &ivote = '!terior $lee!to %ila &ivote &ivote

o En el resto de las filas cada elemento se calcula:

#uevo $lee!to %ila = '!terior $lee!to %ila ('!terior $lee!to %ilae! *olu!a &ivote #uevo $lee!to %ila &ivote)

http://www.phpsimplex.com/teoria_metodo_simplex.htmhttp://www.phpsimplex.com/teoria_metodo_simplex.htm


4/8

$on esto se normaliza el elemento !ivote y su valor !asa a ser 1, mientras'ue el resto de elementos de la columna !ivote se anulan +an8logo al mtodode Causs)Dordan.

Se muestran a continuaci*n los c8lculos !ara la fila 92:

;nterior fila 92 2# # 0 1 0 ) ) ) ) ) )

;nterior Elemento ila en $olumna 9ivote # # # # # #

x x x x x x

Fueva fila !ivote 5 1 1? 0 0 1?

/ / / / / /

Fueva fila 92 #G 0 H? 0 1 )#?

7a tabla corres!ondiente a esta segunda iteraci*n es:

Tabla II . Iteración n# )

# 0 0 0

%ase &b '( '$ ') '* '+ ',

9 0 # 0 $/* 1 0 )#?

92 0 #G 0 H? 0 1 )#?

91 5 1 1? 0 0 1?

- #2 0 )1 0 0 1

;l com!robar la condici*n de !arada se observa 'ue no se cum!le ya'ue entre los elementos de la -ltima fila %ay uno negativo, )1. Se contin-a iterandonuevamente los !asos G y H.

o G.1. 7a variable 'ue entra en la base es "# +9#, !or ser la variable 'ue

corres!onde a la columna donde se encuentra el coeficiente )1.

o G.#. 9ara calcular la variable 'ue sale, se dividen los trminos de la

columna 90 entre los trminos corres!ondientes de la nueva columna !ivote: # ? 1?@/GB , #G ? H? @/H5?HB y 5 ? 1? @/#2B. $omo el menor cociente !ositivo es G, la variable'ue sale de la base es " +9.

o G.. El elemento !ivote es 1?.

o H. ;ctualizando nuevamente los valores de la tabla se obtiene:

Tabla III . Iteración n# *

# 0 0 0

%ase &b '( '$ ') '* '+ '


5/8

Tabla III . Iteración n# *

9# # G 0 1 0 )#

92 0 1# 0 0 )H 1 +

91

G 1 0 )1 0 1- 0 0 0 0 )1

>na nueva com!robaci*n de la condici*n de !arada revela 'ue entre

los elementos de la fila indicadora vuelve a %aber uno negativo, )1. Significa 'ue aunno se %a llegado a la soluci*n *!tima y %ay 'ue seguir iterando +!asos G y H:

o G.1. 7a variable 'ue entra en la base es "3 +93, !or ser la variable 'ue

corres!onde al coeficiente )1.

o G.#. Se escoge la variable 'ue sale calculando el cociente entre los

trminos de la columna de trminos inde!endientes y los trminos corres!ondientesde la nueva columna !ivote: G?+)# @/)B , 1#?2 @/B, y G?1 @/GB. En esta ocasi*n es"2 +92.

o G.. El elemento !ivote es 2.

o H. =es!us de actualizar todas las filas, se obtiene la tabla siguiente:

Tabla I0 . Iteración n# +

# 0 0 0

%ase &b '( '$ ') '* '+ '

9# # $) 0 1 )1?# 1?# 0

93 0 0 0 )H?2 1?2 1

91 * 1 0 ?2 )1?2 0

- ** 0 0 3?2 1?2 0

1in del algoritmo.Se observa 'ue en la -ltima fila todos los coeficientes

son !ositivos cum!lindose, !or tanto la condici*n de !arada.

7a soluci*n *!tima viene dada !or el valor de 6 en la columna de los trminosinde!endientes +90, en este ejem!lo: . En la misma columna se !uede ver el !unto donde se alcanza, observando las filas corres!ondientes a lasvariables de decisi*n 'ue %an entrado en la base: "1 / y "# / 1#.

=es%aciendo el cambio de variables se obtiene x / e y / 1#.

"e propone alimentar el ganado de una grana con la dieta m2seconómica posible. 3ic4a dieta debe contener cuatro tipos de nutrientes


6/8


7/8

=eterminar la funci*n objetivo:

• Minimizar 6 / 0.#4"1 0.054"#

An fabricante desea despac4ar varias unidades de un artBculo a tres

tiendas T$5 T)5 y T*. 3ispone de dos almacenes desde donde realizar el envBo5 y %. !n el primero dispone de , unidades de este artBculo y en el segundo$(. 7a demanda de cada tienda es de =5 ,5 y ) unidades respectivamente. 7osgastos de transporte de un artBculo desde cada almacén a cada tienda est2nexpresados en la tabla:

T$ T) T*

1 # 2

% # 1

>&ómo 4a de realizar el transporte para que sea lo m2s económicoposible@=eterminar las variables de decisi*n y ex!resarlas algebraicamente. Eneste caso:

• "i: n-mero de unidades trans!ortadas desde cada almacn a cada tienda

• "1: n-mero de unidades trans!ortadas desde el almacn ; %asta la tienda K1

• "#: n-mero de unidades trans!ortadas desde el almacn ; %asta la tienda K#

• ": n-mero de unidades trans!ortadas desde el almacn ; %asta la tienda K

• "2: n-mero de unidades trans!ortadas desde el almacn J %asta la tienda K1

• "3: n-mero de unidades trans!ortadas desde el almacn J %asta la tienda K#

• "G: n-mero de unidades trans!ortadas desde el almacn J %asta la tienda K

=eterminar las restricciones y ex!resarlas como ecuaciones o inecuacionesde!endientes de las variables de decisi*n. =ic%as restricciones se deducen de ladis!onibilidad de unidades 'ue %ay en cada almacn as& como de la demanda decada tienda:

• =is!onibilidad en el almacn ;: "1 "# " / 3

• =is!onibilidad en el almacn J: "2 "3 "G / 10

• =emanda de la tienda K1: "1 "2 / 5


8/8

• =emanda de la tienda K#: "# "3 / 3

• =emanda de la tienda K: " "G / #

Ex!resar todas las condiciones im!l&citamente establecidas !or la naturaleza

de las variables: 'ue no !uedan ser negativas, 'ue sean enteras, 'ue solo !uedantomar determinados valores, ... En este caso las restricciones son 'ue la cantidadde unidades no !uede ser negativa y debe ser adem8s un n-mero entero:

• "i ≥ 0

• "i son enteros

=eterminar la funci*n objetivo:

• Minimizar 6 / "1 #4"# 24" 4"2 #4"3 "G

Documents

Resolver Mediante El Método Simplex El Siguiente Problema