taller de inves 2

8/16/2019 Taller de Inves 2

1/16

TALLER 2 INVESTIGACION DE OPERACIONES

METODO SIMPLEX

PRESENTADO A:

RENEMBER NIÑO

PRESENTADO POR:

STEFANY ARNEDO MORA

THALIA MORELO ALVAREZ

NASSIR BRANGO ALVAREZ

INGENIERÍA DE SISTEMAS VI

UNIVERSIDAD DE CARTAGENA.

FACULTAD DE CIENCIAS E INGENIERÍA.

LORICA, CORDOBA


2/16

201

1! Paso:

Encontramos las siguientes restricciones con las cuales llevaremos acabo el ejercicio.

6X1 + 4X2 ≤ 24

X1 + 2X2 ≤ 6

-X1 + X2 ≤ 1

X2 ≤ 2

X1, X2 ≥

2! Paso:!onvertir las inecuaciones en ecuaciones. "ncor#orar variable $e%olgura.&1, &2, &', &4

Ejem#lo:

( -)X1 * 4X2 + &1 + &2 +&' +&4

( + 6X1 + 4X2 + 1&1 + &2 +&' +&4 24

( + 1X1 + 2X2 + &1 + 1&2 +&' +&4 6

( - 1X1 + 1X2 + &1 + &2 +1&' +&4 1

( + X + 1X2 + &1 + &2 +&' +1&4 2

"! Paso:%ora #asamos a construir la tabla sim#le b/sica.En la cual se utili0a la columna la o rengl3n PIVOTE# cuan$o %ala o rengl3n #ivote se convierten los $atos a uno 15

E789&"!

( X1 2 &1 &2 &' &4&;!"

( -) -4

&E&1 6 4 1 4

la#ivote

&2 1 2 1 6

&' -1 1 1 1

M$%&'&($) Z* X1


3/16

&4 1 1 2 columna#ivote

+! Paso:

Para obtener la nueva soluci3n b/sica se utili0an alguno $e los $osti#os

a5 8eem#la0ar la variable $e sali$a en la columna b/sica con lavariable $e entra$a.

b5 ueva la #ivote la #ivote actual < elemento #ivote.

osotras trabajamos con la o#ci3n b5 la cual su =3rmula es:ueva la la actual5 * coeciente $e la columna #ivote5 X nuevala #ivote5.

>ue$a as?:

a5 ueva la 1 la s1 actual < 6

1


4/16

1 1 25 * 5 @ 1 2


5/16

S+ 2 X2 2 C 1 2

Por lo tanto s2 sale $e la soluci3n b/sica, el nuevo $e valor $e 2 es

1.). El incremento corres#on$iente en 0 es

2

3

x2

2

3 1.) 1.

a cual $a la nueva 0 2 + 1 21.

a soluci3n 3#tima #ue$e leerse en la tabla sim#le $e la siguientemanera.

$)&$/ 3/3/4&5&6-

$)&$/78&'7

R/47'/-3$4&7-/5

X1 ' #ro$ucir ' tonela$as $iarias $e #inturas #araeteriores

X2 32

#ro$ucir 1.) tonela$as $iarias $e #intura interior

Z 21 la utili$a$ $iaria es $e D21.

on$e:

X1 '

X2 3

2

( )X1 + 4 X2

( )'5 + 4 3

2 5

( 1) + 6

( 21


6/16

R/57/) '/3&$-/ / '9737 5&'8/% / 5&;&/-/8)7/'$:

M$%&'&($) Z = f(x,y) = 3x + 2y 5;


7/16

!omo los tFrminos in$e#en$ientes $e to$as las restriccionesson #ositivos no es necesario %acer na$a. En caso contrario%abr?a Aue multi#licar #or G-1G en ambos la$os $e la inecuaci3ntenien$o en cuenta Aue esta o#eraci3n tambiFn a=ecta al ti#o$e restricci3n5.

N7)'$&($) $5 )/5)&44&7-/5.

&e convierten las inecuaciones en ecuacionesagregan$o variables de holgura, exceso artifciales segBn latabla siguiente:

T&87 3/ 3/5&;$3$3 T&87 3/ $)&$/ >;/ $8$)/4/? - eceso + articial* + articial

@ + %olgura

En este caso se intro$uce una variable $e %olgura X', X4 X)5en ca$a una $e las restricciones $el ti#o ≤, #ara convertirlas enigual$a$es, resultan$o el sistema $e ecuaciones lineales:

2X1 X2 X" * 12X1 "X2 X+ * +2"X1 X2 X * 2+

I;$$) $ ;-4&6- 7


8/16

T$$ I . I/)$4&6- - 1

' 2

B$5/ C P0 P1 P2 P" P+ P

P' 1J 2 1 1

P4 42 2 ' 1

P) 24 " 1 1

Z -' -2

C7-3&4&6- 3/ 8$)$3$.

&i el objetivo es la maimi0aci3n, cuan$o en la Bltima la lain$ica$ora5 no eiste ningBn valor negativo entre los costesre$uci$os columnas P1 en a$elante5 se alcan0a la con$ici3n $e#ara$a.

En tal caso se llega al nal $el algoritmo a Aue no eiste#osibili$a$ $e mejora. El valor $e ( columna P5 es la soluci3n3#tima $el #roblema.

tro caso #osible es Aue en la columna $e la variable entrante ala base to$os los valores son negativos o nulos. Esto in$ica Aue

el #roblema no se encuentra acota$o su soluci3n siem#reresultar/ mejorable. nte esta situaci3n no es necesariocontinuar iteran$o in$eni$amente tambiFn se #ue$e $ar #ornali0a$o el algoritmo.

e no ser as?, se ejecutan los siguientes #asos $e =ormaiterativa.

E/44&6- 3/ $ $)&$/ /-)$-/ = 5$&/-/ 3/ $$5/.

&e $etermina en #rimer lugar la variable Aue entra en la base.Para ello se escoge la columna cuo valor en la la ( sea elmenor $e entre to$os los negativos. En este caso ser?a lavariable X1 P15 $e coeciente -'.

&i eistiesen $os o m/s coecientes iguales Aue cum#lan lacon$ici3n anterior caso $e em#ate5, entonces se o#tar/ #oraAuella variable Aue sea b/sica.

a columna $e la variable Aue entra en la base sellama columna pivote en color /)3/5.


9/16

;na ve0 obteni$a la variable Aue entra en la base, se #roce$e a$etermina cual ser/ la variable Aue sale $e la misma. a$ecisi3n se toma en base a un sencillo c/lculo: $ivi$ir ca$atFrmino in$e#en$iente columna P5 entre el elementocorres#on$iente $e la columna #ivote, siem#re Aue ambos

elementos sean estrictamente #ositivos maores Aue cero5. &eescoge la la cuo resulta$o %aa resulta$o m?nimo.

&i %ubiera algBn elemento menor o igual a cero no se reali0a$ic%o cociente. En caso $e Aue to$os los elementos $e lacolumna #ivote =ueran $e Fsta con$ici3n se %abr?a cum#li$o lacon$ici3n $e #ara$a el #roblema ten$r?a una soluci3n noacota$a.

En este ejem#lo: 1J


10/16

!on esto se normali0a el elemento #ivote su valor #asa a ser1, mientras Aue el resto $e elementos $e la columna #ivote seanulan an/logo al mFto$o $e Nauss-Oor$an5.

&e muestran a continuaci3n los c/lculos #ara la la P4:

nterior la P4 42 2 ' 1

- - - - - -

nterior Elemento ila en !olumnaPivote

2 2 2 2 2 2

ueva la #ivote J 1 1


11/16

o Q. ctuali0an$o nuevamente los valores $e la tabla seobtiene:

T$$ III. I/)$4&6- - "

' 2 B$5/ C P0 P1 P2 P" P+ P

P2 2 6 1 ' -2

P4 12 -Q 1 +

P1 ' 6 1 -1 1

Z ' ' -1

;na nueva com#robaci3n $e la con$ici3n $e #ara$arevela Aue entre los elementos $e la la in$ica$ora vuelvea %aber uno negativo, -1. &ignica Aue aBn no se %allega$o a la soluci3n 3#tima %a Aue seguir iteran$o#asos 6 Q5:

o 6.1. a variable Aue entra en la base es X) P)5, #or ser lavariable Aue corres#on$e al coeciente -1.

o 6.2. &e escoge la variable Aue sale calculan$o el cocienteentre los tFrminos $e la columna $e tFrminos

in$e#en$ientes los tFrminos corres#on$ientes $e lanueva columna #ivote: 6


12/16

&e observa Aue en la Bltima la to$os los coecientes son#ositivos cum#liFn$ose, #or tanto la con$ici3n $e #ara$a.

a soluci3n 3#tima viene $a$a #or el valor $e ( en la columna$e los tFrminos in$e#en$ientes P5, en este ejem#lo: ''. En la

misma columna se #ue$e ver el #unto $on$e se alcan0a,observan$o las las corres#on$ientes a las variables $e$ecisi3n Aue %an entra$o en la base: X1 ' X2 12.

es%acien$o el cambio $e variables se obtiene ' e 12.

maximizar z=2 x1+3 x

2

x1+3 x

2≤ 6

3 x1+2 x2 ≤ 6

x1

, x2

≥ 0

Para resolver #or el mFto$o sim#le %a Aue %acer el $es#eje $e lastres #rimeras ecuaciones, es $ecir $e su =orma can3nica a la =ormaest/n$ar.

z−2 x1−3 x

2=0

x1+3 x2+s1=6

3 x1+2 x

2+s

2=6

7enien$o las ecuaciones en su =orma est/n$ar #roce$eremos aconstruir la tabla sim#le.

7abla sim#le0 x1 x2 s1 s2 Rsol

1 -2 -' 1 ' 1 6 ' 2 1 6

Para encontrar la columna #ivote utili0aremos, la columna x2 , a

Aue como estamos maimi0an$o se utili0a el menor elemento el cuales -'.

Para #o$er encontrar el rengl3n #ivote utili0aremos, los coecientes

Aue est/n $ebajo $e x

2=−3

lo #asamos a $ivi$ir con lassoluciones, es $ecir con 8, entonces tenemos Aue:


13/16

6

3=2,

6

2=3

Entonces notamos Aue 2 es menor #or lo tanto sala $e la $ivisi3n

6

3 , lo Aue Auiere $ecir Aue el rengl3n #ivote es el rengl3n 2.

es#uFs tomaremos el elemento #ivote el cual es ', lo convertiremosen 1, #ara eso %acemos la o#eraci3n, la cual es multi#licar to$o el

rengl3n #ivote #or1

3 , #ara no alterar la matri0 o tabla sim#le.

0 1 " 1 0 x

1

3

0 13

1 1

3

2

!onversi3n

%ora %a Aue volver , to$os los elementos Aue estFn en los

etremos verticales $el elemento #ivote, el cual es 1

0

1

3 1 1

3 0 2 x

3

1 -2 -'

* 1 -1 0 1 6 conversi3n

%ora volvernos , los el elemento $el rengl3n '.

0 13

1 13

0 2 x−2

' 2 1 6

* 73

0 −2

3

1 2 conversi3n

8em#la0aremos los valores en la tabla sim#le.

7abla sim#le


14/16

( x1

x2

s1

s2

Rsol

1 -1 1 6 1

3

1 13

2

73

−23

1 2

Ra tenemos una siguiente matri0, a Aue las variables $e $ecisi3n

nos $amos cuenta Aue x1=−1 #or lo tanto to$os los valores $e

x1

y x2 , $eben ser ≥ , entonces utili0aremos el valor m/s negativo

#ara %allar la columna #ivote.

Entonces la columna x1, es la solumna #ivote, #or lo tanto

$ebemos $eterminar el rnglo #ivote #ara eso, tomamos los valores

Aue est/n #or $ebajo $e x1 , lo $ivi$iremos entre las soluciones, es

$ecir 8.

2

(13 )=6 y

2

(73 )=0.857

Por lo tanto a #o$emos $i=erenciar el $ivisor menor saber a AuF

rengl3n #ertenece, la cual es el rengl3n '.

−23

1 2

7abla sim#le

0 x1 x2 s1 s2 Rsol

1 -1 1 6

1

3

1 1

3

2


15/16

73

%ora, vamos a re#etir los #asos anteriores, convertiremos en 1 el

elemento #ivote, lo cual es7

3 #ara eso multi#licamos el rengl3n

', #or3

7

0 73

0 −23

1 2 x

3

7

0 1 0 −521

3

7

.J)Q

!onversi3n

%ora convertiremos en , los etremos verticales $e la columna

#ivote:

0 1 0

−5

21

3

7 0. x1

1 -1 1 6

* 1 0 0.761 37

6.J)

Q

!onversi3n

0 1 0 −5

21

3

7

0.

x−

1

3

13

1 13

2

* 0 0.41 -.14

2

1.Q1

4

!onversi3n

8em#la0an$o los $atos $e los renglones 1 2: tenemos:


16/16

7abla sim#le0 x

1 x

2 s

1 s

2 Rsol

1 .Q61 37

6.J)Q

.41 -.142

1.Q14

1 −521

3

7

.J)Q

Para concluir tenemos Aue:

z=8.857

x 1=0.857

x2=1.714

8em#la0an$o en la =unci3n objetivo:

z=2 x1+3 x

2→ z=2 ( 0.857)+3 ( 1.714)

S7;4&6-:

z=1.714+5.142=6.857

taller de inves 2

Documents