Home

Índice 1-BREVE HISTÓRIA SOBRE A PROGRAMAÇÃO

1. Uma fun o f c ncava num conjunto convexo X c R se para quaisquer dois pontos x e x pertencentes a X e um escalar tal que 0O lt hA lt 1 for v lido 41 3 PROGRAMA O LINEAR PL el t 2 x 1x gt 1 2 f x A f x a figura seguinte ilustra uma fun o real de vari vel real c ncava SUA A xyt AX JX2 1 A f X AJ X2 Hx 1 A xit Axo Figura 3 3 Ilustra o de uma fun o c ncava Recordamos em seguida algumas preposi es importantes para o estudo que ser feito da resolu o de problemas de programa o PL na sua formula o can nica Preposi o 3 1 Qualquer fun o que cont nua num conjunto X c R fechado e limitado limitada em X Preposi o 3 2 Qualquer fun o que cont nua num conjunto X c R fechado e limitado tem um valor m ximo e m nimo em X Recordamos em seguida os conceitos combina o convexa hiperplano e hiper espa o limitado por um hiperplano 42 3 PROGRAMA O LINEAR PL Uma combina o linear de um conjunto finito de pontos x xmideR dada por gt 4CiX chamada combina o convexa se os escalares c gt 0 e Xc 1 Dado um conjunto X c R o inv lucro do conjunto X definido pela uni o de todas as combina es lineares convexas de pontos dos subconjuntos finitos de X O conjunto de pontos definido por H d w x xeR dx w designado por hiperplano sendo d um vector pe
2. o estiver de zero mais pr ximo se est da solu o ptima O m todo para o algoritmo da condi o envolve altera es de x x de forma a que as seguintes condi es se verifiquem 1 O n mero de condi o de um arco nunca aumenta 2 O n mero da condi o reduzido necessariamente em algum arco ap s um n mero de itera es finito O algoritmo da condi o tem duas fases a fase primal que introduz altera es nos fluxos dos arcos e a fase dual que introduz altera es nas vari veis duais ditas tamb m 122 5 ALGORITMO DA CONDI O potenciais dos n s Ambas as fases tem como objectivo reduzir o n mero de condi o i e algoritmo da condi o faz itera es nas duas fases a primal e a dual at que se verifique a condi o de paragens K 0 5 3 Fase primal Durante a fase primal as vari veis duais 7 mant m se fixas Os fluxos que s o alterados pertencem aos arcos de um ciclo que ser escolhido convenientemente como ser lt esclarecido mais frente Seja C s1 e S2 So S3 jap lt Sn Ejn Sri S Spy um ciclo simples no grafo N A e seja a sequ ncia de orienta o indicada por O C OC o n mero da orienta o do arco i e A j o vector coluna da matriz A corresponde a esse arco o somat rio dos produtos do n mero de orienta o de cada arco pelo respectivo vector A ji nulo O C A j 0 pela Preposi o 4 4 Seja y dado por o C sed
3. tr nsito algo a electricidade na rede el ctrica a mensagem na rede telef nica o ser 2 INTRODU O MATEM TICA humano bens ou res duos nas redes rodovi ria e ferrovi ria Este tr nsito tem que ser decidido e claro deve ser o mais racional e eficiente poss vel Para que a decis o seja eficiente em redes de tamanho consider vel necess rio recorrer modela o matem tica da estrutura da rede para o suporte da decis o racional e ao desenvolvimento de algoritmos para o tratamento de problemas em redes Uma rede envolve o conceito de grafo que uma representa o gr fica de dados e da liga o existente entre esse dados A representa o gr fica tem vantagens na constru o do modelo matem tico para a resolu o do problema Muitas reas do conhecimento como por exemplo a matem tica as engenharias em geral e a gest o usam a teoria de grafos para descrever diversas situa es dentro do seu mbito Uma rede uma estrutura caracterizada por tr s tipos de objectos constituintes da rede que s o os arcos os n s e as etiquetas associadas com os n s ou com os arcos Os arcos podem ser considerados como abstrac es de meios unidireccionais como por exemplo meios f sicos para o transporte de mercadorias Os n s podem ser considerados como abstrac es interpretados como locais de injec o de fluxo ou terminais de recep o do fluxo As etiquetas s o dados associados com os objectos arcos ou n s
4. 1 5 1 3 K 0 C3 Trg C3 1 5 3 1 K 0 C4 Tga Tra 64 0 5 5 0 K 0 es frej Tray s 0 0 0 0 K 0 C6 Tie Trio 0 5 M M 5 lt 2 Voltar ao passo 1 do ALG 5 1 ALG 5 1 Passo 1 Determinar candidatos para a rvore y4 e e y 4 Como y U Y3 b seguir para o passo 2 Passo 2 Juntar rvore um novo arco e e Como e ey gt Ary A min A U x min 2 20 2 A A N fi 3te A eu Como F 6 T 6 q N seguir para o passo 1 151 5 ALGORITMO DA CONDI O Passo 1 Determinar candidatos para a rvore y ey tes Como y Uw O seguir para o passo 2 Passo 2 Juntar rvore um novo arco e e5 Como e E Y gt Ari 44 min A x min 2 2 2 A N fi 3 4te A fes es Como F 6 T 6 c N seguir para o passo 3 Passo 3 Calcular os Fluxos O ciclo C f4 e 1 64 3 64 e est representado na Figura 5 8 como ce lt 0 os fluxos dos arcos do ciclo vir o alterados de A 2 e tomam os valores x x x x x x 8 4 4 2 0 0 Voltar ao passo 1 do ALG 5 3 Figura 5 8 Ciclo C ALG 5 3 Passo 1 Encontrar um arco fora da Condi o 152 5 ALGORITMO DA CONDI O De acordo com os novos fluxos e os ltimos lucros reduzidos os n meros de condi o s o os seguintes x 8 0 0 gt K 0 gt na condi o x 4 amp 2 3 gt K 0 gt na condi o x 4 amp 1 gt K 1
5. do arco e encontra se o ciclo pretendido O algoritmo para a fase primal iniciado com a escolha de um arco fora da condi o seja esse arco indicado por e ALG 5 1 Fase Primal A Passo 0 Iniciar Se cs lt 0 ent o N fT s e Ars X caso contr rio s A N F s e Arpe U xX Atribuir ao conjunto dos arcos da rvore o S A conjunto vazio A 4 Passo 1 Determinar os arcos para a rvore Seja Y e e 6 6 20 x lt u P eN eTEN e va feie 46 0 lt 0x gt 0 Fl eN eT eN isto y o conjunto dos arcos diferentes do arco e cujo lucro reduzido c gt 0 tendo fluxo menor que o fluxo m ximo e que n o partem dos n s pertencentes rvore mas terminam num n pertencente rvore e y O 126 5 ALGORITMO DA CONDI O conjunto dos arcos diferentes do arco e cujo lucro reduzido cj lt 0 tendo fluxo maior que zero e que partem dos n s pertencentes rvore mas chegam aos n s n o pertencentes rvore Se wy Uw 4 conclui se que n o existe possibilidade de construir o ciclo pretendido ent o segue se para o algoritmo da fase dual Passo 2 Juntar rvore um novo arco Seleccionar um e ey Uw Se e EY fazer A pe MIA ro Up Xk Se e E Y3 fazer Ar Min Apk Xk Actualizar o conjunto dos n s e dos arcos A N NU fF k T k e A AU fe Se F s T s c N seguir para o passo 3 A caso contr rio seguir p
6. fora da condi o x 2 c4 0 gt K 0 gt na condi o x 0 cs 0 gt K 0 gt na condi o Xs 0 co M 4 gt K 0 na condi o f K 1 j Arco e est fora da condi o seguir para a fase primal ALG 5 1 Passo 0 Iniciar A Como c gt 0 ent o N F 3 2 Ap A uU x 1 e o conjunto dos A arcos A Passo 1 Determinar candidatos para a rvore Y1 Y b como y Uw seguir para a fase dual ALG 5 2 Passo 1 Determinar os arcos incidentes na rvore y 4ewy e 65 Passo 2 Determinar a altera o m xima possivel 4 minJ 3 1 J 1 Passo 3 Reduzir as vari veis duais me l l 2 153 5 ALGORITMO DA CONDI O E para os potenciais vem 7 z ma n 0 2 5 0 tomando os lucros reduzidos os valores C4 Tia Tra 04 0 5 5 0 K 0 s Tys Tr C5 0 0 0 0 K 0 C6 ne Tr Cs 0 5 M M 5 K 0 6 K Como c 0 e fica na condi o voltar ao passo 1 do ALG 5 3 ALG 5 3 Passo 1 Encontrar um arco fora da Condi o De acordo com os novos fluxos e os ltimos lucros reduzidos os n meros de condi o s o os seguintes X 8 ci 1 gt K 0 gt na condi o x 4 0 2 gt K 0 gt na condi o x 4 63 0 gt K 0 gt na condi o x 2 0 0 gt K 0 gt na condi o x 0 c5 0 gt K 0 gt na condi o x 0 c6 M gt K 0 na
7. s restri es 10 x 8 0 x x 16 0 lt x lt 10 0 lt x lt 10 A fun o lagrange pode ser escrita como L m Uis H2 X1 gt X23 i 2 16 x x 1 10 x 09 H 10 x 8 u X ent o a fun o dual ser L x x 0 09 x Pelo que o problema dual min X sa x x 16 0 lt x lt 10 0 lt x lt 10 Este exemplo particular confirma a afirma o que o problema dual do problema dual o problema primal Exemplo 3 9 Considere o problema do exemplo 3 4 usando a proposi o 3 10 determine as vari veis duais ptimas Exemplo 3 8 Mostre que o problema dual do problema dual do problema de programa o linear o problema de programa o linear Seja o problema primal o PLD m x rb pu sa c TA 4U2 gt 20 u gt 0 T1 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES a fun o de lagrange L r p x n b Ax u u x 0 ex resolvendo o subproblema dual tem se b Ax 0 e u x 6 0 sendo x gt 0 ea fun o dual L x ex ent o o problema dual o problema de programa o linear Exemplo 3 9 Considere o problema do exemplo 3 4 usando a proposi o 3 10 determine as vari veis duais ptimas A solu o ptima x x x x I0 10 4 1 A ltima coordenada tem que ser necessariamente n o b sica e seja considera a pen ltima tamb m b sica embora seja degenerada Portanto x x x J 4 1 e x x x 10 10 o 1 gt cB 0 d E a tr ri
8. K 0 na condi o x 4 6 3 gt K 0 na condi o x l c4 4 gt K 1 fora da condi o 4 Ao existem dois arcos fora da condi o e e e escolhendo um qualquer seja e para o arco escolhido para e passar fase primal ALG 5 1 Passo 0 Iniciar Como c lt 0 ent o N T 4 3 Ar X gt A 1 e o conjunto dos arcos A 0 133 5 ALGORITMO DA CONDI O Passo 1 Determinar arcos da rvore Determinar os arcos dos conjuntos y y3 Yi te ej ep ci 20 x lt U F j eNeT j eN fe e W lejie e cj lt 0 x gt 0 F eNeT j eNH 6 como Y U Y 4 seguir para o passo 2 Passo 2 Juntar rvore um novo arco Y Uy fe como s existe um arco este ser o escolhido e e e E Y gt A pk Ap A mintA ro U R min 1 2 0 1 As A A N NU F 2 T2 3 2 e A AU e e esta rvore apresentada na Figura 5 32 Como 4F 4 T 4 z N voltar ao passo 1 Passo 1 Determinar da rvore y e ey 4 como y UY 4 seguir para o passo 2 Passo 2 Juntar rvore um novo arco eee ey gt A minfl 4 0 1 N NU4F I T0 8 230 41 3 2 A e A e e e U e e e Como F 4 T 4 cN seguir para o passo 3 Passo 3 Calcular os Fluxos O ciclo 1 e 2 e 3 e 1 como c4 lt 0 os fluxos ser o alterados de A 1 se o sentido do arco igual ao do ciclo o fluxo ser aumentado Arg A l tid
9. M TODO SIMPLEX PARA PROGRAMA O EM REDES Passo 4 Actualiza o da rvore e das Vari veis Duais y3 feat Y4 b Assim B N Em 4 X x X2 xs a a x3 x4 Passo 1 Avalia o na Itera o 2 com x1 x2 x3 x4 xs 1 1 4 0 0 Para e3 m m3 c3 1 1 3 1 gt ea Para e4 n1 T3 c4 1 1 10 8 gt gy e e4g y2 Assim ex e3 e 1 Passo 2 Atribui o do Passo P 1 e1 2 e 3 A min 0 A min 4 1 2 1 1 A minfo 1 4 1 Passo 3 Actualiza o dos Fluxos x 4 1 1 3 x 1 1 1 1 2 x2 1 1 1 1 2 Passo 4 Actualiza o da rvore e das Vari veis Duais y3 0 y4 e2 Assim Em z X x x Xs x x4 Passo 1 Avalia o na Itera o 3 com x x2 x3 x4 xs 2 2 3 0 0 Para e2 m2 T3 c2 0 2 1 1 gt gw ou yo Para e4 T m3 c4 1 2 10 7 gt gy e ego Conclu mos assim que o ptimo foi atingido O m todo primal simplex num grafo um m todo expedito n o s para utiliza o did ctica em c lculo manual mas tamb m para uma implementa o eficiente em computador recorrendo a t cnicas computacionais adequadas quer para armazenamento de dados quer para processamento eficiente do c digo ditas de tecnologia de implementa o Esta tecnologia envolve o desenvolvimento de estruturas de base de dados juntamente com algoritmos
10. Portanto B I e sejam feitas as tentativas Primeira tentativa x x 0 0 logo x x x 16 4 que n o admiss vel ponto A da Figura 3 4 Segunda tentativa x x 0 10 logo x x x 6 14 n o admiss vel ponto B da Figura 3 4 Terceira tentativa x x 10 0 logo x x x 6 6 n o admiss vel ponto C da Figura 3 4 Quarta tentativa x x 10 10 logo x x x 4 4 n o admiss vel ponto D da Figura 3 4 Como se esgotou as tentativas para obter solu es b sicas admiss veis com esta base resta escolher uma nova base B Seja o vector das coordenadas n o b sicas x x x ent o x x x Jea matriz A partida em era io 1 Portanto B i h e sejam feitas as tentativas Primeira tentativa x x 0 0 logo x x x 16 20 que n o admiss vel ponto E da Figura 3 4 62 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Segunda tentativa x x 0 4 logo x x x 20 24 n o admiss vel ponto F da Figura 3 4 Terceira tentativa x x J 10 0 logo x x x 6 0 admiss vel ponto G da Figura 3 4 Pelo que o vector x x uma solu o b sica admiss vel Caso n o fosse havia que fazer outra escolha para as coordenadas n o b sicas ou escolher uma nova base B O algoritmo come a com a seguinte solu o b sica admiss vel x x x J 6 0 x x x 10 0 a que corresponde a solu o x x x x J
11. Trg C3 0 0 3 3 Ca npa Tr 04 0 0 5 5 Cs Tys Trg s 0 0 0 0 C6 TE 6 Tr 6 C 0 0 M M E os n meros de condi o x 0 c 1 K 0 gt na condi o x 0 co 1 K 0 na condi o x 0 c3 3 K 0 na condi o UUU x 0 c4 5 K 0 gt na condi o x 10 cs 0 K 0 gt na condi o x 10 ce M_ gt K 10 fora da condi o 6 Kj 10 143 5 ALGORITMO DA CONDI O Arco e est fora da condi o seguir para a fase primal ALG 5 1 Passo 0 Iniciar A Como Ge lt 0 ent o N T 6 B Ang A x 10 e A 6 Passo 1 Determinar candidatos para a rvore Como y U y 4 seguir para a fase dual ALG 5 2 Passo 1 Determinar os arcos incidentes na rvore Y fez 63 64 86 ley Passo 2 Determinar a altera o m xima poss vel 3 p min 1 5 gt M 1 Passo 3 Reduzir as vari veis duais n 0 1 1 o vector dos potenciais 7 m ma n 0 O 1 o calcular os lucros reduzidos C6 Two Tr C6 0 1 M M 1 Voltar ao passo 1 do ALG 5 1 144 5 ALGORITMO DA CONDI O ALG 5 1 Passo 1 Determinar candidatos para a rvore y fe bey 4 Como y U y Z 4 seguir para o passo 2 Passo 2 Juntar rvore um novo arco e e Como e ey gt Art A min A u x min i0 4 4 A A N f2 3 e A fe Como F 6 T 6 Z N volta
12. caso contr rio os fluxos x ou as vari veis duais 7 ou ambos s o alterados Se um arco j satisfaz a 5 7 ent o e dito estar na condi o caso contr rio e est fora da condi o As v rias condi es que podem ocorrer s o ilustradas no Quadro 5 1 Quadro 5 1 Condi es poss veis de um arco e c lt 0 c 0 c gt 0 x u Fora da condi o Na condi o Na condi o 0 lt x lt u Fora da condi o Na condi o Fora da condi o x 0 Na condi o Na condi o Fora da condi o Observe se que das nove condi es poss veis cinco delas apresentam e na condi o Para cada uma das nove condi es definido um n mero de condi o como se apresenta no Quadro 5 2 121 5 ALGORITMO DA CONDI O Quadro 5 2 Condi es poss veis de um arco e c lt 0 c 0 c gt 0 X U Xj 0 0 0 lt x lt uj X 0 u X x 0 0 0 U X Note se que os n meros de condi o s o todos n o negativos e s o as altera es de fluxo necess rio para que o arco esteja em condi o Na primeira coluna o fluxo no arco tem que decrescer na segunda indiferente enquanto que na terceira tem que ser incrementado Seja K o n mero de condi o do arco ej O n mero de condi o da solu o corrente x 7 definido por DK ejeA Uma solu o cujo n mero de condi o zero resolve o problema PLR ou seja quanto mais pr ximo o n mero de condi
13. ctricas entre albufeiras consecutivas at ao mar considerando que o mar o fim da cascata reser i L central i Figura 2 7 Albufeiras e central hidroel ctrico para a cascata Numa cascata h drica a gest o de curto prazo do aproveitamento hidroel ctrico decide o volume de gua armazenado nas albufeiras e o turbinado ou descarregado em cada 24 2 INTRODU O MATEM TICA per odo tipicamente de uma hora durante o horizonte temporal tipicamente de uma dia at uma semana correspondendo este dom nio ao ciclo di ria at ao semanal dos diagramas de carga As equa es de balan o de gua numa albufeira e em cada per odo determinam um n da rede considerando uma albufeira i no per odo k a equa o de balan o de gua k 1 k k k ok k k Vi r t tSu Vi tti s Caso k seja a segunda hora a equa o determina o n indicado na Figura 2 8 lt 4 Figura 2 8 N para a equa o do balan o da gua na segunda hora O lado esquerdo da igualdade o valor que toma o volume de gua dispon vel na albufeira i para ser gerido no per odo k igual ao que transita anterior k 1 mais o requisito r aflu ncia natural ou um valor pr especificado albufeira i no periodo k e mais o volume que prov m da albufeira de montante i 1 turbinado ou descarregado no per odo k i e considerando o tempo de transito entre albufeiras para o volume turbinado ou descarregado nulo O lado dir
14. e4 l e1 2 e 4 num grafo pr prio 89 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Vamos ilustrar o que se afirma no Corol rio 4 5 atrav s de um exemplo Considere o ciclo C indicado na Figura 4 4 Ent o o conjunto das colunas associados aos arcos do ciclo s o 1 1l 1 J 1 J J 1 e s o linearmente dependente visto que 1 1 1 0 1 1 1 1110 Oi C 4 02 C E O3 C 04C 1 b 1 F HD 0 1 1 1 11 10 Observe que se multiplicar aos elementos da sequ ncia de orienta o por um n mero real a rela o anterior matem se Um grafo G N A diz se ac clico se n o existe um ciclo usando os elementos do conjunto N e A Um grafo G N A diz se conexo ou ligado se para qualquer par distinto de n s i j de N podemos formar usando os elementos dos conjuntos N e A um caminho que ligue esses n s i e se para qualquer par distinto de n s for ligado por pelo menos um caminho Uma rvore por defini o um grafo ac clico conexo Dado um grafo G N A uma rvore N A com A c A uma rvore geradora tamb m dita de abrangente ou total de G por defini o de grafo gerador de G Estas defini es s o ilustradas na Figura 4 5 90 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES O 4 a D o o 4 d Figura 4 5 Exemplos de rvores e rvores geradoras a Grafo G b Subgrafos de G que s o rvores mas n o s o
15. ieJ Por contradi o vamos provar que pelo menos um ponto extremo de Q x ptimo Seja cx z recordar que z o m nimo da fun o objectivo cx em Q Para qualquer x tal que i J ent o c x 2 z Seja k e J tal que cx gt z vir z x c dx pe e x d ex Zaw x gt gt d ex Dea gt d z Zee iz Fdz z O que uma contradi o i e para qualquer ie J cx 2 4 46 3 PROGRAMA O LINEAR PL Da prova desta preposi o pode tamb m concluir que se existem dois pontos extremos ptimos ent o um ponto que perten a combina o convexa desses dois pontos tamb m ptimo Em geral se existirem v rios pontos extremos ptimos os pontos que perten am combina o convexa desses pontos s o ptimos Tamb m se conclui que pelo facto de existir um ponto extremo que ptimo ent o os pontos ptimos n o podem ser pontos interiores ao conjunto Q a n o ser que todos os ponto de Q sejam ptimos Seja ent o A uma matriz mxn com m lt n e caracter stica rank A m Ent o atrav s de uma permuta de colunas da matriz A a matriz pode ser particionada na seguinte forma A B N onde B uma matriz quadrada n o singular Seguindo a mesma organiza o de forma a tornar os produtos matriciais e as igualdades e desigualdades compat veis com a parti o podem escrever se os vectores x e u de acordo com a parti o i e vamos rescrever as seguintes igualdades e desigua
16. lt 10 0 lt x lt 4 0 lt x lt 4 0 lt x lt ll 0 lt x lt ll Problemas duais max 167 x 10u 10u 4u 14u sa l n m u 20 l n T u 20 T u 20 T u 20 His Has H33 M4 Z0 max 167 x 10u 10u 4u 14u sa l r m 4 20 l m n W 20 Tm u 20 T u 20 His H2 H34 20 81 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES 7 Considere o problema de programa o linear min x sa x x 1 0 lt x x lt 10 Resolver o problema dual pelo algoritmo do simplex Solu o Problema dual max m l1l0 u u t l gt S ste nO ptimo nu 0 Ti u 20 Ho 0 HiH 20 8 Considere o problema de programa o linear anterior determine a sua solu o usando a preposi o 3 10 Solu o x 1 0 9 Considere o problema de programa o linear 7 e o seu dual obtido em 8 mostre de pelo sistema de Karush Kuhn Tucker que as solu es obtidas para estes problemas s o as ptimas 82 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Este cap tulo apresenta uma especializa o sobre o algoritmo primal simplex para o problema de programa o linear em rede Esta especializa o quando usada permite que o m todo primal simplex possa ser resolvido directamente sobre a rede do problema Esta especializa o tamb m conhecido por algoritmo gr fico do simplex Neste cap tulo exclusivame
17. ndice 1 BREVE HIST RIA SOBRE A PROGRAMA O LINEAR ceseeeneeneees 1 2 INTRODU O MATEM TICA nssssssssessseseseseeesssssssssssssssssssssssssssesesesrststorororereeeeeee 5 2 1 Nota es e cConven eES ssseseecceessescseccecessesossccecceeesssscseccoceseesosececcesessssosecceeessssoseceeee 5 2 2 Programa o linear em redes seesssesssesssecssocssooesoosssseesseessocssoosssosssseessesssoosssossos 7 2 3 Exemplos de modelos em programa o linear sesssesssessseessoossoossosssssesssesssooee 15 2 3 1 Produ o distribui o da pol meros seeesoossooessossssesssoessoossoossoosssoesssesssooe 15 2 3 2 Problema das dietas seosseosseossoossoossssesssesssecssoossoosssossssesssesssoossoossosssssesssesssoses 22 2 3 3 Financiamento de projectos seessoesssesssesssecssoossoosssossssessseessoossoossoossssesssesesooee 23 2 3 4 Planeamento em aproveitamentos hidroel ctricos curto prazo modelo LP 24 2 3 5 Planeamento em aproveitamentos de biogas curto prazo modelo LP 32 3 PROGRAMA O LINEAR PL seesseesseessesseossesseesscesscsseossesscesseosscsseossesseesseesseesee 36 3 1 Propriedades do espa o vectorial euclidiano oessoesssessseessoossoossosssssesssesssooee 39 3 2 Caracteriza o do dom nio das solu es poss veis ssessseessoossooesoossssesssesssooee 45 3 3 M todo primal simplex se ssessseossooesosesssesssesssecssoossoossoossssessseessoossoosssos
18. o Objectivo Determine d uma direc o admiss vel de melhoria do valor da fun o objectivo no ponto y Se d n o existe ent o o algoritmo termina e o ponto corrente y o ponto solu o Caso contr rio o algoritmo prossegue para o passo 2 Passo 2 Obten o de um novo ponto Procurar o tal que k k ek cly a d mint e y ad y a de Q Isto vamos procurar o passo a para a transla o de y segundo vector d de modo que y a d pertence ainda ao conjunto Q das solu es poss veis e que seja a melhor solu o para o problema de pesquisa em linha segundo esta direc o Encontrado a actualizamos o ponto para 51 3 PROGRAMA O LINEAR PL k 1 k y y a d nova solu o corrente e incrementamos o contador de itera es k de um k k 1 O algoritmo prossegue para o passo 1 O m todo primal simplex pois uma especializa o do m todo geral da direc o admiss vel em que y para cada k um ponto extremo do dom nio das solu es poss veis o poliedro Q Por isso frequentemente o m todo simplex chamado m todo do ponto extremo A direc o d ter de ser seleccionada de modo que a solu o encontrada no Passo 2 resulte num novo ponto extremo Dada uma solu o b sica poss vel para o problema PL considere a parti o das matrizes e a parti o de c x e u de forma compat vel em componentes b sicos e n o b sicos A B N c c x x x e u
19. rio ci disponibilidade d e percentagem ai dos componentes j 1 2 n tem que originam a quantidade s de ra o alimentar tendo as percentagem do componente j que ser compreendida no intervalo Lp Pj S Determinar a quantidade de cada produto x na mistura que corresponde ao menor custo total da ra o O problema de programa o linear para obter o menor custo tem como fun o objectivo o custo total da mistura sendo as restri es a satisfazer a quantidade s de ra o percentagem do componente j compreendidas no intervalo respectivo e finalmente a 22 2 INTRODU O MATEM TICA limita o da disponibilidade dos alimentos O problema de programa o linear para o problema das dietas ent o descrito como m min c x i 1 s a m X S i l m sp lt a x Ssp j 1 2 sn i l 0 lt x lt d LE OAE i Outro problema semelhante a este problema de encontrar a ra o com maior quantidade para um dos elementos mas cujo custo seja inferior a um determinado valor Fica ou cuidado do leitor escrever a formula o para este ltimo problema 2 3 3 Financiamento de projectos Os projectos 1 1 n t m valor actual l quido v e requerem respectivamente para o financiamento o capital a podendo ser financiados totalmente ao em parte O capital total dispon vel para financiar os projectos b pretende se determinar quanto deve ser financiado cada um dos projectos de forma a
20. rvore chamado uma rvore com raiz Os arcos raiz s o representados nos desenhos por um arco incidente num nico n saindo do n visto que o respectivo elemento associado com a matriz A aumentada tem valor igual unidade A Figura 4 6 ilustra um grafo com raiz e uma sua rvore com raiz Preposi o 4 15 Seja A a matriz de incid ncia dos n s nos arcos para um grafo pr prio com raiz G N A com a raiz no n k Se Q o conjunto dos vectores que s o as colunas da matriz b sica para A e ent o EeN e T N com Ler A j eS2 uma rvore geradora de G 100 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Prova Seja Q uma matriz b sica para A e Pela Preposi o 4 14 a matriz aumentada A e tem a caracter stica igual ao n mero de linhas Pela Preposi o 4 12 A SAk A n o tem a caracter stica igual ao n mero de linhas ent o e eS Seja n o n mero de n s de G Ent o dever corresponder a n 1 colunas linearmente independentes de A Pela Preposi o 4 13 T uma rvore geradora de G 4 Estamos agora aptos a efectuar a caracteriza o da base para o problema PLR Preposi o 4 16 Seja A a matriz de incid ncia dos n s nos arcos para um grafo pr prio conexo e com raiz no n k O conjunto das colunas de A correspondente a uma rvore RR Kt E Es k geradora de G mais e uma matriz b sica para A e Prova A prova uma consequ ncia imediata das
21. rvores geradoras c Subgrafos de G que s o rvores geradoras d Subgrafos de G que n o s o rvores Seguidamente sem prova enunciam se um conjunto de preposi es importantes que nos d o alternativas para a defini o de rvore e propriedades dos grafos e das rvores 91 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Preposi o 4 6 Para um grafo T N A com pelo menos um n as afirma es seguintes s o equivalentes 1 T uma rvore 2 T tem apenas para qualquer par distinto de n s p q de N um nico caminho que liga p a q 3 T tem menos um arco que o n mero de n s e conexo 4 T tem menos um arco que o n mero de n s e ac clico Dado um grafo G grau do n i D i o n mero de arcos de G incidentes no n i Por exemplo o grau do n 3 do grafo da Figura 4 5 a 3 Um n de uma rvore cujo grau igual a 1 chamado um ponto extremo da rvore Semigrau interior exterior de um n o n mero de arcos que incidem para o interior exterior do n Preposi o 4 7 A soma dos graus de todos os n s de um grafo igual a duas vezes o n mero de arcos do grafo i e Xien D i 2 A Prova Qualquer arco incidente em dois n s contribui portanto duas vezes para o resultado da soma dos graus dos n s 4 92 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Preposi o 4 8 Uma rvore com pelo menos dois n s tem pelo menos dois ponto
22. s de Julho Existem diversos clientes os quais foram agrupados em cinco regi es Existe aqui j uma primeira decis o que foi tomada anteriormente que a forma o de regi es de clientes ou seja construir pontos de procura que aglomeram clientes Claro que ao n vel de transporte os clientes localizados numa cidade s o potencialmente aglomerados num ponto de qualquer modo considere que essa decis o j foi tomada e que o director de produ o tem que respeitar o que se entendeu pontos de procura que aglomeram clientes 15 2 INTRODU O MATEM TICA A procura de pol mero para o m s de Julho para cada uma das regi es indicada no Quadro 2 1 As f bricas da Poliremos est o localizadas em Dresden na Alemanha Lie na Fran a Mil o na It lia e Aveiro em Portugal Quadro 2 1 Procura para Julho Pedidos para Julho Ton 2840 2800 2600 2820 2750 Regi o de Vendas NI BIOT Dadas as diferen as existentes nas v rias f bricas as capacidades e os custos de produ o s o distintos de f brica para f brica e s o indicadas no Quadro 2 2 Quadro 2 2 Capacidade de produ o e custo para Julho F brica Pa s RS Custo E GERE Dresden Alemanha 4000 2100 Lille Fran a 4500 2000 Mil o It lia 2700 1600 Aveiro Portugal 3000 1700 O custo de transporte por tonelada e a respectiva capacidade de transporte entre cada uma das quatro f brica
23. 0 1 pelo que 7 c 0 sendou c se x u caso contr rio u 0 1 e Consequentemente ne 1100 m o 3 J 00 78 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Exerc cios do Cap tulo 3 1 Considere os seguintes problemas de programa o linear min 10 x min 10 a x sa 10 x lt 16 sa 10 u x lt 16 a 10 x gt 1 10 0 x gt 1 a 0 lt x lt 10 0 lt x lt 30 com aceR 140 Resolva os problemas pelo algoritmo do simplex Solu o x 0 x 0 Observe que o segundo problema equivalente ao primeiro basta fazer a seguinte transforma o de vari vel x x a 2 Considere os seguintes problemas de programa o linear min Xx x min X Q X sa X x lt 16 sa X x lt 16 Xi RR E ta GRE a 0 lt x lt 10 0 lt x lt 10 0 lt x lt 10 0 lt x lt 10 com aeR 0 Resolva os problemas pelo algoritmo do simplex Compare a solu o destes problemas com os anteriores justificando os resultado obtidos Solu o x 10 0 x 10 0 Como 0 lt x lt 10 e c 1 ent o x 10 admiss vel e o menor valor da fun o objectivo obtido com este valor fixando x 10 nos problemas anteriores derivam os problemas indicados em 1 79 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES 3 Considere os seguintes problemas de programa o linear min x X min x X sa x x lt l6 sa x x lt 16 x x 2 1 Rs Di 2 1 0 lt x lt 10 0 lt x lt 10 0 lt x lt 10 0 lt x lt 10 Resolva os pr
24. Dados para do aproveitamento hidroel ctrico E reser 1 reser 2 reser 3 v 9 9 13 5 26 4 v 7 9 10 8 21 1 vf 7 9 10 8 22 1 v 4 5 10 T 121 164 181 t hm h 1 404 1 188 1 512 kom E a o Eita 1 3 5 0 0 0 0 148 2 0 0 0 0 0 0 16 8 3 0 0 0 0 0 0 15 8 30 2 INTRODU O MATEM TICA Ainda seria f cil concluir que na primeira albufeira h aflu ncia de gua excessiva i e 3 tem que se descarregar 0 096 hm na primeira hora Como proceder para tomar as melhores decis es em cada hora Um processo de tentativa e erro permite concluir que o melhor lucro de 23011 e que o quadro de solu o o seguinte Quadro 2 12 Solu o para o planeamento kin vw t s bo Vo ty So V db o 79 10 8 21 1 11 3 5 9 9 1 4 0 1 0 0 11 2 1 1 0 0 0 0 22 2 0 0 0 0 21 0 0 8 5 1 4 0 0 0 0 11 4 1 2 0 0 0 0 21 9 1 5 0 0 3 0 0 7 9 0 6 0 0 0 0 10 8 1 2 0 0 0 0 22 1 1 0 0 0 f 79 108 22 1 t em percentagem do m ximo volume de gua turbinado k t ty ty 1 100 0 94 6 0 0 2 100 0 100 0 100 0 3 42 5 100 0 65 3 No entanto para obter esta solu o j mais significativo o disp ndio de tempo e a dificuldade de antever a solu o ptima Embora ap
25. K 0 C4 Tpu Tr 0 0 4 5 1 K 0 Cs Tys Ty 5 0 0 0 0 K 0 C6 TH Tr Cs 0 4 M M 4 K 6 X Kj 6 Voltar ao passo 1 do ALG 5 1 ALG 5 1 Passo 1 Determinar candidatos para a rvore y fe pey 4 Como y U Y b seguir para o passo 2 Passo 2 Juntar rvore um novo arco ep Como e ey gt Ap A min A u x min 6 5 5 A N 12 3 e A fe Como F 6 T 6 q N voltar para o passo 1 Passo 1 Determinar candidatos para a rvore y feibey 4 Como y Uy seguir para o passo 2 Passo 2 Juntar rvore um novo arco e e Como e ey S Arf A min A u x min 5 8 4 4 A N 1 2 3e A fe e Como F 6 T 6 N seguir para o passo 1 148 5 ALGORITMO DA CONDI O Passo 1 Determinar candidatos para a rvore y Q ey tes Como y U Y b seguir para o passo 2 Passo 2 Juntar rvore um novo arco e e Como e E Y gt Ar A min A x min 4 6 4 A A N fi 2 3 4he A fe z L Como fE 6 T 6 c N seguir para o passo 3 Passo 3 Calcular os Fluxos O ciclo C f 4 e l ej 2 e3 3 6 4 e est representado na Figura 5 7 como Ce lt 0 os fluxos dos arcos do ciclo vir o alterados de A 4 e tomam os valores x x x x xs x 8 4 4 0 2 2 Voltar ao passo 1 do ALG 2 3 0 Figura 5 7 Ciclo C 149 5 ALGORITMO DA CONDI O ALG 5 3 Pa
26. Os n s s o geralmente ligados por arcos podendo corresponder com a realidade de um qualquer meio f sico de transporte Assim os arcos podem representar linhas el ctricas ruas ou estradas numa rede urbana de transportes tubagens numa rede de distribui o de gua linhas telef nicas numa rede de comunica es etc No estudo que ser feito as considera es ser o limitadas a redes com um n mero finito de n s e arcos e sem la os No entanto se existir a necessidade de considerar la os eles podem ser introduzidos considerando o la o substitu do por dois arcos e um n entre eles Para 2 INTRODU O MATEM TICA uma rede com 1 n s e J arcos ser admitida uma ordem para os n s e para os arcos atrav s de uma qualquer enumera o para os n s de 1 Tis e para os arcos de 1 sT f Uma rede ilustrada por um grafo orientado sobre o qual se escrevem as etiquetas Os n s ilustrados por c rculos e os arcos ilustrados por linhas orientadas ligando dois n s A orienta o do arco indicada por uma seta colocada sobre o respectivo o arco A Figura 2 1 ilustra a forma como se representa o grafo usando uma representa o sagital Figura 2 1 Ilustra o de uma rede Observe que poss vel mais do que um arco a ligar os mesmos dois n s com a mesma orienta o Por exemplo na Figura 2 1 ambos os arcos 1 e 2 saem do n 1 e entram ambos no n 2 A rede em termos matem ticos pode ser descrita por uma m
27. PROGRAMA O EM REDES Note que qualquer grafo G um subgrafo do grafo G e ainda mais um subgrafo gerador de G Ainda note que um subgrafo gerador do grafo G pode n o conter nenhum arco de G Uma sequ ncia finita de n s sj e arcos ese Si Siri Sir1 Si de um grafo G escrita como P sr ea 82 CjO 83 CB gt Sns Ein Sn 1 tendo pelo menos um arco define um trajecto de s para Sn Um trajecto um caminho no grafo G se os elementos mpares s o n s distintos de G os elementos pares s o arcos de G e cada arco ee Si Sir1 Sit Si Um caminho o percurso que liga o primeiro ao ltimo elemento da sequ ncia que o define No grafo da Figura 4 1 por exemplo P um caminho P T 5 l ls 7 4 es 3 5 1 5 l 4 1 4 4 3 3 cuja representa o se ilustra na Figura 4 3 Figura 4 3 Ilustra o do caminho P 86 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Preposi o 4 1 Todos os arcos de um caminho s o distintos Prova Se dois arcos de um caminho forem id nticos os n s desse caminho n o podem ser distintos portanto n o satisfaz a defini o Um ciclo num grafo G um trajecto que come a num n e acaba no mesmo n sendo indicado pela sequ ncia C s1 e S2 j2 Sn Ejm Sn 1 tendo pelo menos dois arcos Um ciclo simples num grafo G se a subsequ ncia si e S2 E2 S3 CG Sn um caminho em G e ejm E Sn Sn 1 Sn 1 S
28. Preposi es 4 14 e 4 15 4 Temos assim uma preposi o que faz uma caracteriza o para uma base do problema PLR Seguidamente apresentamos um teorema que caracteriza uma propriedade alg brica para a matriz b sica de um problema PLR Estas duas propriedades em conjunto proporcionam a especializa o do algoritmo primal simplex para o problema PLR Conv m recordar que uma matriz triangular n o singular uma matriz quadrada com valores diferentes de zero na diagonal principal e zeros acima da diagonal principal ou aquela que levada a ter esta forma pelo troca de linhas e colunas A pr xima 101 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES proposi o mostra que a matriz b sica para um problema PLR associado a um grafo pr prio triangular Preposi o 4 17 Seja A a matriz de incid ncia dos n s nos arcos para um grafo pr prio G conexo e com raiz no n 1 Se B uma matriz b sica de A e ent o B triangular Prova Seja T N A uma rvore com raiz determinada pela matriz b sica B e seja n o n mero de n s de T Como G um grafo pr prio n gt 2 Pela Preposi o 4 8 T tem pelo menos dois pontos extremos Seja n um ponto extremo de T que n o n raiz Se eja O arco em T incidente em ni ent o a linha n de B tem s um elemento n o nulo igual se o arco est orientado do n n para outro n ou igual 1 se o arco est orientado de outro n para n n Assim reordenan
29. a aK ser reduzido a zero j 155 6 C DIGO LSNNO CASCATA H DRICA 6 C DIGO LSNNO CASCATA H DRICA Neste cap tulo no mbito da programa o matem tica em redes abordado o problema da simula o computacional da gest o racional de albufeiras em cascata num horizonte de curto prazo e para suporte computacional usada a aplica o inform tica LSNNO Large Scale Nonlinear Network Optimization O LSNNO foi desenvolvido no departamento de matem tica ND de la Paix B lgica e que est dispon vel em linguagem Fortran na Internet juntamente com um manual do utilizador No entanto o manual do utilizador n o est em word pelo que se anexa uma vers o deste manual no fim deste cap tulo 6 1 Simula o da Gest o de cascatas h dricas Uma empresa de sistemas de energia el ctrica deve ter a preocupa o de decidir com racionalidade a gest o dos recursos que gere i e o parque de recursos que o seu sistema a gerir com o qual obt m os proveitos que justificam e asseguram a sua exist ncia O objectivo a atingir na produ o da energia el ctrica e a maximiza o do lucro obtido com a venda da energia el ctrica dentro das condicionantes quer 156 6 C DIGO LSNNO CASCATA H DRICA regulamentadas quer t cnicas A venda de energia el ctrica pode ser realizada quer directamente aos consumidores por contratos bilaterais quer num mercado de energia el ctrica onde a empresa tem que caract
30. apropriados execu o dos v rios passos do m todo que n o s o abordados no mbito deste texto Para iniciar o algoritmo do simplex 114 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES necess rio conhecer uma solu o b sica poss vel Esta solu o nem sempre f cil de ser encontrada Em seguida ser descrita uma t cnica til para determinar uma solu o b sica poss vel para iniciar o algoritmo do simplex 4 4 Solu o b sica poss vel inicial O passo inicializa o do Algoritmo 4 3 exige encontrar uma solu o b sica poss vel com a qual se inicia o algoritmo O m todo de all artificial star um m todo sistem tico que permite encontrar uma solu o b sica poss vel com a qual se inicia o algoritmo Neste m todo somente os arcos adicionadas chamados arcos artificiais tem fluxo n o nulo Os arcos da rede determinada pelo problema t m fluxos nulos Para apresentar o m todo considere uma rede associada a um problema PLR com T n s O m todo all artificial start envolve o aumento da rede pelo acr scimo de um novo n I 1 com requisito nulo Na rede original para cada n fonte i com requisito r positivo adicionamos um arco artificial do n i para I 1 com custo unit rio de transporte nulo e capacidade infinita O fluxo neste arco igual a r satisfazendo a lei de conserva o do fluxo no n i Na rede original para cada n k com requisito rg negativo procura adici
31. condi o 6 K 0 j Todos os arcos est o na condi o de optimalidade sendo os fluxos e os potenciais finais os seguintes x X X X X x 8 4420 0 Ty Ty Ty m4 2 5 0 3 154 5 ALGORITMO DA CONDI O Assim o problema dado resolvido utilizando o algoritmo da condi o Em anexos a este cap tulo apresenta se em anexo 1 a listagem do programa de computador desenvolvido no mbito deste trabalho em anexo 2 os resultados dados pelo programa da resolu o do problema dado e em anexo 3 a resolu o de um segundo problema para teste do programa 5 7 Converg ncia do Algoritmo da Condi o Para provar que este algoritmo converge num n mero finito de itera es assume se que r u x e 7 s o vectores cujas coordenadas s o inteiros Assim cada vez que se obt m um avan o e uma altera o do fluxo na fase primal o n mero da condi o de e reduzido pelo menos de 1 Cada vez que se alteram as vari veis duais na fase dual ou a rvore desenvolvida na fase primal seguinte tem pelo menos mais um n e um arco ou o n mero da condi o do sistema reduzido de pelo menos 1 Por aplica o repetida das fases primal e dual sobre um arco fora da condi o n o ser poss vel desenvolver a rvore indefinidamente Uma rvore geradora para o grafo pode ser produzida na fase primal A rvore geradora juntamente com e permite construir um ciclo Ent o ap s um n mero finito de passos
32. era N M sujeito a aX apXx tanxy xa b agXtasX tankn xao b AX FAX Ann P Xnm by 0 lt x lt u j 1 2 N N 1 UNEM ou ainda min m x z C X C X CNXy CnaXyna E CNMXNM sujeito a AX FAX H t A NX TA naXna tal NMX NM b AX aAoX tawNXy tdonaXna F s NIMX NM b AX aAypXo FAMNXN TAmnaXna T AM N MX NM by 0 lt x lt u j 1 2 N N 1 N M com Gar aaa a Oy aa Me o MEE Sendo m M n mero de restri es n N M n mero de vari veis incluindo as principais e auxiliares Atendendo a que min z m x z poderemos optar por um dos operadores no caso vamos optar pelo de minimiza o O problema de PL estudado neste texto est na seguinte forma can nica 37 3 PROGRAMA O LINEAR PL minz CX C X C X sujeito a agX tapXx ta x b aX hag a X b a aX Pa Posta bn 0 lt x lt u 1 2 n Ou na forma matricial como se segue min cx s a Ax b 0 lt x lt u Em que A uma matriz m x n com m lt n dos coeficientes das equa es associadas s restri es x um vector com n coordenadas que s o as vari veis de decis o 0 e u vectores colunas em que as coordenadas s o os valores limite das vari veis de decis o e vector linha dos coeficientes da fun o objectivo b vector coluna dos valores impostos para requisitos determinados pelas restri es Nesta forma can nica o problema PL por s
33. ltimo elemento ser elm Alo Lo mX lyo gt O gradiente ser VELM X ig 0X9 delm elm as derivadas parciais s o 0 elm A 1750 77 Lo M Xo lyo OX g 2 AX 83m OX A matriz hessiana do ltimo elemento elm elm 2 OXig H ELM elm Oelm EMO SOM O elemento da matriz hessiana n o nulo dado por 2 0 elm E OX 80X9 Nota sobre o c digo LSNNO Da leitura do manual de utilizar do c digo LSNNO verifica se que o mesmo foi desenvolvido com vista obten o de solu es ptimas para problemas em que o operador de optimiza o a minimiza o do tipo min f x sa Ax r 0 lt x lt u 172 6 C DIGO LSNNO CASCATA H DRICA logo h necessidade de recorrer da seguinte igualdade max f x min f x sa sa xeF xeF a fun o objectivo n o o lucro mas sim o sim trico do lucro idem para o vector gradiente e para a matriz hessiana Al m disto como o volume de gua armazenado numa albufeira tem um limite inferior n o necessariamente nulo as restri es do nosso problema s o do tipo o que obriga a uma transla o do vector das vari veis do tipo x xH para que as restri es se possam escrever como Ax r 0 lt x lt u sendo r r Al u L l e a fun o objectivo ser escrita como f x I 6 7 Dados para um caso exemplo Na simula o computacional usaram se os seguintes dados para as tr s albufeiras consid
34. maximizar o valor actual l quido do investimento de capital investido nos projectos O problema de programa o linear para obter o financiamento ptimo Caso o financiamento seja na globalidade a vari vel de decis o tem que ser inteira 23 2 INTRODU O MATEM TICA 2 3 4 Planeamento em aproveitamentos hidroel ctricos curto prazo modelo LP Numa aproveitamento hidroel ctrico a optimiza o da gest o dos recursos consiste em decidir com racionalidade a gest o da gua dispon vel sujeita a condicionantes que s o impostas quer pelo equipamento condicionantes t cnicas quer por raz es ecol gicas e de seguran a condicionantes pol ticas As vari veis ligadas aos tr nsitos de volume de guas est o relacionadas pelas equa es de balan o da gua complicando o problema Consequentemente para atingir racionalidade na gest o necess rio a considera o de vari veis e restri es que ultrapassam a capacidade humana mental de decidir sem um suporte racional auxiliar para descrever o comportamento do aproveitamento hidroel ctrico Assim o recurso simula o computacional do modelo matem tico do aproveitamento hidroel ctrico a gerir e a t cnicas de optimiza o permite gerar um sistema de informa o para o suporte tomada das decis es Considere a figura seguinte que representa um aproveitamento hidroel ctrico em cascata gen rico com as albufeiras i 1 2 n e admita que existem centrais hidroel
35. novamente o exemplo 4 1 Por comodidade este problema ilustrado na Figura 5 2 A vari vel x foi omitida da rede uma vez que a soma das tr s restri es de igualdade implica x 0 Na apresenta o feita no cap tulo 4 3 a coluna associada com x foi necess ria para assegurar que a caracter stica da matriz das incid ncias dos n s nos arcos fosse igual ao n mero de linhas desta matriz O algoritmo da condi o n o necessita de tal pressuposto por isso x pode ser retirado da formula o do problema ri 0 a5 10 10 Figura 5 2 exemplo de rede para o algoritmo da condi o Ainda por comodidade antes de iniciar a resolu o vamos recordar o enunciado do problema min x x 3x 10x s a X X poi 5 Xx X X gt X X 5 com as seguintes restri es de n o negatividade 0 lt x lt 4 0 lt x lt 2 0 lt x lt 4 0 lt X lt 10 132 5 ALGORITMO DA CONDI O ALG 5 3 Passo 0 Iniciar Fazer x x x x 0 0 41 Pelr m m 5 0 1 Passo 1 Encontrar um arco fora da Condi o Determinar os lucros reduzidos de cada arco ci Tr 1 Tr 1 Q 5 0 1 4 C2 Teo Tr O 0 1 1 0 3 c3 Tp Z Trg 70 5 1 3 C4 Nefa Z Tr 4 C 5 1 10 4 Usando o quadro 5 2 determinar o n mero de condi o de cada arco e usando o quadro 5 1 averiguar se est na condi o ou n o x 0 4 gt K 4 fora da condi o x 0 2 0 gt
36. o linear restri es de igualdade para impor os volumes finais de gua armazenados nos reservat rios max YAD pt k 1 i s a parai 1 2 k 1 2 K k 1 k k Ko ak k k vi f tii S V t S Este problema de programa o linear e um problema em redes cuja formula o do tipo max TX sa Ax r problema para a gest o da cascata no curto prazo 0 lt x lt u O vector x dos fluxos um vector cujas coordenadas s o os volumes de gua quer em tr nsito turbinado ou descarregado quer os volumes de gua armazenados nas albufeiras A fun o objectivo uma fun o linear do volume de gua turbinado visto 27 2 INTRODU O MATEM TICA que a produ o de energia el ctrica na central hidroel ctrica i proporcional ao caudal turbinado nessa central no per odo k Considere o seguinte caso uma empresa gere um aproveitamento hidroel ctrico O director de produ o decide o n vel de produ o de cada uma das tr s centrais de uma cascata com tr s albufeiras que termina no mar O director de produ o est a planear tomar as melhores decis es para um horizonte temporal com tr s horas O volume m ximo m nimo inicial e final requerido em cada albufeira o factor de efici ncia da convers o o m ximo caudal e as aflu ncias s albufeiras estimadas para as respectivas centrais e os pre os para a energia el ctrica s o os indicados no quadro seguinte Quadro 2 7 Dados para do aproveitamen
37. s a obten o desta uma an lise da solu o recorrendo rede apresentada na Figura 2 9 permite concordar com os valores apresentados Neste exemplo os requisitos para os n s passam a ser os indicados seguidamente no Quadro 2 13 Quadro 2 13 Requisitos dos n s aflu ncia r 3 5hm N do N Requisito N do N Requisito 1 10 4 6 0 0 2 10 8 7 0 0 3 21 1 8 0 0 4 0 0 9 0 0 5 0 0 10 43 3 31 2 INTRODU O MATEM TICA 2 3 5 Planeamento em aproveitamentos de biogas curto prazo modelo LP Em aterros sanit rios o biog s produzido uma mistura cujo principais gases s o o metano 40 a 60 di xido de carbono 20 a 40 e nitrog nio 2 a 20 A produ o de biog s varia ao longo dos anos medida que se processa a decomposi o dos res duos O metano sob o ponto de vista do efeito de estufa um g s cerca de vinte e uma vezes mais prejudicial que o di xido de carbono Portanto mesmo que n o seja aproveitado deve ser queimado O aproveitamento energ tico do biog s para a convers o para energia el ctrica conduz valoriza o econ mica proveniente da venda da energia el ctrica com pre os melhores que os das fontes convencionais e representa um benef cio ambiental A Gest o de Curto Prazo para convers o da energia do biog s para a forma de energia el ctrica consiste em estabelecer um plano poss vel para o funcionamento das unidades podendo serem toma
38. se ainda h algum arco fora da condi o 137 5 ALGORITMO DA CONDI O ALG 5 3 Passo 1 Encontrar um arco fora da Condi o De acordo com os lucros reduzidos calculados no passo 3 do ALG 5 2 os n meros de condi o de cada arco s o agora x 2 a gt K 25 fora da condi o x 2 2 0 gt K 0 nacondi o x 3 6 0 gt K 0 na condi o x 0 4 7 K 0 na condi o t k 2 j 1 J O arco e cont nua fora da condi o portanto e e seguir para a fase primal ALG 5 1 Passo 0 Iniciar Como c gt 0 ent o N FOX l Arq U X gt 4A 2 e o conjunto dos A arcos A Passo 1 Determinar candidatos para a rvore y b y e como y U Y3 4 seguir para o passo 2 Passo 2 Juntar rvore um novo arco YUY 6 e 63 e E Y gt Arg A minlAs x min 3 3 A A N MU 1 3 fi 3je A fe Como A T q N voltar para o passo 1 Passo 1 Determinar candidatos para a rvore Y UY 4 seguir para a fase dual 138 5 ALGORITMO DA CONDI O ALG 5 2 Passo 1 Determinar os arcos incidentes na rvore y bey fe Passo 2 Determinar a altera o m xima possivel 4 minflc 1 Passo 3 Reduzir as vari veis duais n 1 0 2 1 1 T T 0 1 1 2 As novas vari veis duais s o 7 z Ta 1 O 2 e os lucros reduzidos Ci Tr Tr 1 c 1 0 1 0 C2 TH Z Tr TC 0 2
39. t m sido criadas para evitar a entrada em ciclo Est fora do objectivo deste texto a abordagem destas t cnicas Note se que os dados necess rios implementa o do algoritmo primal simplex s o os dados originais do problema de programa o linear i e e u b e A Mais ainda B usado tanto na avalia o como na determina o do passo S alterada se for necess rio actualizar B no passo 4 do algoritmo Para exemplificar o uso deste algoritmo considere os seguintes exemplos 60 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Exemplo 3 1 max x X s a x x 216 HR 24 0 lt x lt 10 0 lt x lt 10 Ser necess rio escrever este problema na forma can nica introduzindo duas vari veis de desvio uma para cada uma das restri es de desigualdade Sejam estas vari veis indicadas por x e x os seus valores m ximos tem que verificar respectivamente as desigualdades X gt max X x 16 s a 0 lt x lt 10 0 lt x lt 10 x 24 O problema equivalente ao seguinte min x x sa x x x 16 XX X 4 0 lt x lt 10 0 lt x lt 10 0 lt x lt 4 0 lt x lt 6 Ser ent o necess rio duas coordenadas b sicas e duas n o b sicas 61 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Passo 0 Inicia o Consideremos por escolha o vector das coordenadas n o b sicas x x x ent o x x x Je a matriz A partida em Ra E 0 E x 1 cd 0 l1 1 1
40. tempo k Vi Vi Volume m nimo e volume m ximo permitido na albufeira 1 Si S Caudal m nimo e caudal m ximo que poss vel entornar na albufeira i t t Caudal m nimo e caudal m ximo que poss vel turbinar na albufeira 1 As limita es consideradas s o v lt v lt vi intervalo de varia o do volume admiss vel na albufeira i k AE s Ssi lt s intervalo de varia o do caudal descarregado na albufeira i t lt t lt ti intervalo de varia o dos caudal turbinado na albufeira 1 Na p gina seguinte na Figura 6 3 est representada a rede para o aproveitamento h drico em cascata em estudo A rede descreve o aproveitamento hidroel ctrico em cascata composto por tr s albufeiras O horizonte de explora o uma semana com per odos de uma hora isto 168 horas de explora o 160 6 C DIGO LSNNO CASCATA H DRICA N raiz A A gt gt gt gt gt gt A A gt gt gt gt gt gt A A gt gt gt gt gt gt A A gt gt gt gt gt gt A A gt gt gt gt gt gt Figura 6 3 Rede para o problema com tr s albufeiras em cascata 161 6 C DIGO LSNNO CASCATA H DRICA Com a poss vel excep o da central de cabe a cada central recebe a gua que prov m da albufeira de montante e envia a gua para jusante Caso se justifique a gua pode ser descarregada directamente para jusante i e sem originar produ o de energia el c
41. vel para os arcos ej com F j eNeT eN N dada no quadro 5 5 as zonas em ambos os quadros sem indica o de valores correspondem a situa es que n o podem ocorrer na fase dual visto que correspondem a situa es de expans o da rvore da fase primal i e correspondem a ter se WU 0 128 5 ALGORITMO DA CONDI O Quadro 5 4 Redu o poss vel em 17 c lt o0 c 0 c gt 0 Xj uUj Cj oo fo 0 Quadro 5 5 Redu o poss vel em x c lt 0 c 0 c gt 0 A A O algoritmo da fase dual iniciado com a rvore T N A obtida na fase primal 129 5 ALGORITMO DA CONDI O ALG 5 2 Fase Dual Passo 1 Determinar os arcos incidentes em T Seja Y e T j e N F eN e cj lt o e y e T eN F eN ec gt o A isto y o conjunto dos arcos que terminam nos n s pertencentes a N mas A partem de n s n o pertencentes a N e t m lucro reduzido c lt 0 e y o A conjunto dos arcos que chegam a n s n o pertencentes a N mas partem de n s A pertencentes a N e t m lucro reduzido cj gt 0 Passo 2 Determinar a altera o m xima poss vel Fazer 0 min eyy IC o menor dos m dulos dos lucros reduzidos c dos arcos pertencentes uni o dos conjuntos y3 y4 Passo 3 Reduzir as vari veis duais Fazer A n m 0 paratodosos ie N Note que um arco e ey UNw para o qual
42. x n X 4 Qualquer ponto x que n o interno nem externo do conjunto X c R dito ponto da fronteira de X Um ponto extremo de um conjunto convexo um ponto da fronteira desse conjunto mas nem todos os pontos da fronteira s o extremos como ilustra a figura seguinte Pontos da fronteira todos os pontos que limitam a figura Conjunto Convexo Pontos extremos os v rtices da figura pontos A B C D E 0 X Figura 3 1 Ilustra o do conceito de ponto extremo 40 3 PROGRAMA O LINEAR PL Um conjunto dito aberto se todos os pontos do conjunto s o internos ao conjunto Um conjunto dito fechado se os pontos da fronteira do conjunto pertencem ao conjunto Um conjunto X c R dito limitado se existe algum e gt 0 tal que o conjunto X est inclu do no conjunto B 0 isto existe B 0 tal que X c B 0 Uma fun o f no conjunto X c R cont nua se f x existe para qualquer x c X e se para qualquer ce gt 0 e x eX 36 gt 0 tal que e x t x lt e sempre que xelxnB x ER Uma fun o f convexa num conjunto convexo X c R se para quaisquer dois pontos X e X pertencentes a X e um escalar tal que O lt h lt 1 for v lido f 1 A x A x lt 1 2 f x A f x a figura seguinte ilustra uma fun o real de vari vel real convexa JX 1 A S x Af X2 JX JIL A Xrt AX 1 J A xrt AX Figura 3 2 Ilustra o de uma fun o convexa
43. 1 1 TEA Tr 3 c l 2 3 0 Cs Tr 4 Tr 4 c 1 2 10 7 Como c1 0 1 ent o e e fica na condi o voltar ao passo 1 do ALG 5 3 ALG 5 3 Passo 1 Encontrar um arco fora da Condi o De acordo com os lucros reduzidos calculados no passo anterior os n meros de condi o de cada arco s o agora X 2 ca 0 gt K 2 gt na condi o x 2 amp 1 gt K 0 na condi o x 3 64 0 gt K 0 na condi o x 0 4 7 gt K 0 na condi o Krat Todos os arcos est o na condi o Terminar com a conclus o de que o ptimo foi alcan ado 139 5 ALGORITMO DA CONDI O Para iniciar o algoritmo da condi o pelo m todo do n e arcos artificiais a que proceder de acordo com 1 Acrescentar um n artificial rvore cujo requisito igual soma dos requisitos dos outros n s 2 Criar arcos artificiais dos n s com requisito positivo para o n artificial e criar arcos artificiais dos n s com requisito negativo para o n artificial 3 Considerar os arcos criados em 2 que chegam ao n artificial com um custo zero e capacidade de transporte infinita o e os outros arcos criados igualmente em 2 que partem do n artificial com custo infinito e capacidade de transporte infinita 50 00 4 Transferir os fluxos pelos arcos fict cios atribuindo aos fluxos dos arcos do problema original o valor zero Esta inicia o corresponde a uma expans o da re
44. 2 troca com a N 1 resultando as seguintes parti es para o vector x B B B B N x x x xl x x x x x x pelo que se tem N B x 4 0 x 1 10 A parti o para a matriz A 1 0 0 B 1 1 l1 le N 0 0 0 1 0 1 0 sendo agora B 0 0 1 1 1 1 E voltamos ao passo 1 O vector x da 1 itera o x x x x x J 1 4 0 0 68 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Itera o 2 Passo 1 Avalia o Calcular o vector dos custos reduzidos 1 0 0 1 c c B N 3 10 1 1 0 x 0 0 1 x 0 o 1 8 pe 1 1 1 1 obtemos y 4 e y 1 e a uni o yU y logo k 1 Como k pertence a y ser 1 Passo 2 Atribui o do Passo Determinar y 1 0 0 1 1 y B N l 0 0 1 x 0 1 Ed 1 1 0 de onde resulta A A min 4 1 1 2 1 1 1 e A min 4 A uN minfo 1 4 1 Passo 3 Actualiza o Teremos xN x 4 I 1 3 x x x x l 1 0 1 1 x l 1 0 2 2 0 Como A 1 e u u 4 logo A ur segue se para o passo 4 69 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Passo 4 Substitui o Determinando os conjuntos y e y obtemos W 4e va 2 cuja uni o y Uy 2 Pelo que j 2 Fazemos agora a troca das colunas B 2 e N 1 resultando assim as seguintes parti es x x x x 2 3 0 e x x x 2 0 1 1 0 0 1 B 1 0 1 N 1 0 sendo 0 l 0 1 1 1 0 1 B 0 0 i 1 1 1 O vector x na 2 itera
45. 3 1 1 3 2 3 3 t EA t t j S v Yv y v i v y 1 2 3 V V V 2 2 2 gt gt gt fr 3 3 4 i k 1 F Vv a 1 1 2 2 3 3 ta e ta a t S r a k 1 v y v y v y 1 z 3 V V V 3 3 3 gt gt gt r tr t3 t 4 1 2 2 3 3 S S t s t y y v vy v y N raiz Mar gt Fim de Cascata Figura 6 6 Vari veis pertencentes a cada elemento da fun o objectivo Agrupando as vari veis de cada elemento da fun o objectivo obtemos o seguinte elm x 84H eim E elm a Elm X sk X3 Ci ea Ci aa Elm XX Elm X X 7 elm X5 X 169 6 C DIGO LSNNO CASCATA H DRICA Em conclus o os elementos associados s duas primeiras albufeiras em geral os elementos associados a todas as albufeiras menos a ltima s o compostos por tr s vari veis com a seguinte determina o dos ndices A primeira vari vel tem o ndice igual ao do elemento A segunda tem o ndice dado pela soma do ndice do elemento mais o n mero de per odos do horizonte temporal em estudo A ltima vari vel tem o ndice igual ao do elemento somado com o produto entre o n mero de per odos de funcionamento e o n mero de albufeiras do sistema h drico em estudo Para os elementos associados ltima albufeira a lei a determina o dos ndices id ntica mas s o compostos por duas vari veis com a seguinte determina o dos ndices A primeira vari vel tem o ndice igual ao do elemento A ltima
46. 4 Seja A a matriz de incid ncia dos n s nos arcos para o grafo G N A pr prio e conexo com n n s Seja T N uma rvore geradora de G Ent o Q A j eje YUfe uma base para o espa o R k x i y Prova A prova consiste em mostrar que os versores fe i 1 n s o combina es lineares dos vectores de Q O vector e uma combina o trivial Seja p k epe 1 n Como T uma rvore geradora de G pela Preposi o 4 6 existe um nico caminho P s ej S2 e Sq us P j S13 em que T liga os n s p e k Pela Preposi o 4 3 sabe se que k gt O PAG e et Consequentemente e gt 0 P A ji portanto e uma combina o linear dos vectores de Q Pelo que fica provado que Q uma base para R 4 Assim conseguimos aumentando a rede que a matriz das restri es passe a ter caracter stica igual ao n mero de linhas Este elemento que foi introduzido um arco que nasce num n mas n o termina em nenhum outro n 99 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES 2 2 e E E 4 4 a b Figura 4 6 Conceito de ra zes a Grafo com raiz b rvore com raiz Quando nos referimos a um grafo associado com este problema de PLR aumentado o arco associado vari vel a dito arco raiz e no k um n com raiz Mais ainda o grafo correspondente chamado um grafo com raiz e um grafo com raiz que seja uma
47. 9 0 3 2600 10 4000 4 2820 11 4500 5 2750 12 2700 6 0 13 3000 7 0 14 390 Quadro 2 5 Especifica es dos arcos N do N N Custo Capac N do N N Custo Capac Arco De Para Unit Arco Arco De Para Unit Arco 1 6 1 800 0 15 8 5 400 300 2 6 2 600 2000 16 9 1 0 0 3 6 3 300 2000 17 9 2 400 1000 4 6 4 200 2000 18 9 3 400 1000 5 6 5 400 500 19 9 4 300 1000 6 7 1 200 3000 20 9 5 100 2000 7 7 2 400 2000 21 10 6 2100 4000 8 7 3 500 1000 22 11 7 2000 4500 9 7 4 900 200 23 12 8 1600 2700 10 7 5 0 0 24 13 9 1700 3000 11 8 1 500 1000 25 10 14 0 00 12 8 2 200 2000 26 11 14 0 00 13 8 3 200 1000 27 12 14 0 00 14 8 4 200 1000 28 13 14 0 00 No n in cio de produ o injectado o fluxo que ser igual capacidade m xima de produ o da f brica mas como nem toda a capacidade necessitara de ser utilizada para o m s de Julho surge um outro n para onde ser localizado o excesso de capacidade de produ o sendo o custo de transporte nos arcos que ligam este n nulo 19 2 INTRODU O MATEM TICA Os dados e a estrutura para o sistema de produ o distribui o apresentado no Quadro 2 5 Note que o excesso de capacidade de produ o concretizado na representa o do grafo por o n extra n mero 14 que liga as quatro f bricas atrav s de arcos de custo zero e capacida
48. A O EM REDES Na figura 3 5 ilustrado o conjunto das vari veis admiss veis Q para este exemplo 20 X1 X2 1 6 0 15 10 X1 X2 20 ptimo Figura 3 5 Ilustra o do conjunto das vari veis admiss veis Na figura 3 5 os pontos A B C D E F s o seis dos pontos que correspondem a solu es b sicas para este problema No entanto s os quatro pontos A B C D correspondem a solu es b sicas admiss veis para este problema Caso se escreva o problema na formula can nica existem como mostra o exemplo 3 1 quatro vari veis e duas restri es de igualdade sendo o n mero m ximo solu es b sicas de 24 mas s 4 s o solu es b sicas admiss veis Observe que no exemplo 3 1 existia o mesmo n mero m ximo de solu es b sicas mas s existia uma solu o b sica admiss vel visto que o conjunto das solu es admiss veis singular A solu o ptima para o exemplo 3 2 corresponde ao ponto solu o b sica admiss vel indicado por C 10 10 sendo o valor ptimo para a fun o objectivo igual a 20 como se verifica pela observa o da Figura 3 5 65 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Exemplo 3 3 min x x 3x 10x sa x X X 5 X X x 0 X X gt X 5 0 lt x lt 4 0 lt x lt 2 0 lt x lt 4 0 lt x lt 10 0 lt x lt 1 Ser ent o necess rio ter tr s coordenadas b sicas e duas n o b sicas Passo 0 Inicia o Consideremos po
49. Este planeamento simples de efectuar sem o recurso a um sistema de suporte EA 5 r 3 A r decis o visto que o que se pretende planear a gest o de 1 hm de aflu ncia de gua primeira albufeira de forma a que este seja armazenado no fim das tr s horas na ltima albufeira como o pre o da energia mais favor vel na segunda hora a solu o ptima 29 2 INTRODU O MATEM TICA deve contemplar que o m ximo volume de gua poss vel seja turbina na segunda hora nas duas primeiras albufeiras sendo o lucro total de 4788 Quadro 2 10 Solu o para o planeamento kin Wo bos kR vo ty 8 b Va td 8 o 79 108 121 1 11 1 0 8 9 0 0 0 0 0 0 10 8 0 0 0 0 0 0 21 1 0 0 0 0 21 0 0 7 9 1 0 0 0 0 0 10 8 1 0 0 0 0 0 22 1 0 0 0 0 31 0 0 7 9 0 0 0 0 0 0 10 8 0 0 0 0 0 0 22 1 0 0 0 0 f 7 9 10 8 22 1 t em percentagem do m ximo volume de gua turbinado k t ti t 1 0 00 0 00 0 00 2 71 20 84 18 0 00 3 0 00 0 00 0 00 Caso o horizonte temporal seja maior ou existam mais aflu ncias j n o seria t o f cil encontrar a solu o ptima por tentativa Por exemplo considere que os dados para o planeamento eram os do Quadro 2 11 Quadro 2 11
50. I0 6 O 0 Itera o 1 Passo 1 Avalia o Calcular o vector dos custos reduzidos O aa 1 o f q c cB N 1 OQ Ox PM o logo cN c B N 2 0 Pelo que y bey 6 YU p ent o o algoritmo termina e o ponto corrente ptimo No Quadro 3 1 seguinte indicada a evolu o do vector x deste o passo O at ultima itera o Quadro 3 1 Evolu o do vector x durante o processo iterativo itera o x X X X4 0 N10 P6 o O 10 6 0 0 63 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Na figura 3 4 ilustrado o conjunto das vari veis admiss veis para este exemplo X1 X2 1 6 X1 X2 gt 16 20 Figura 3 4 Ilustra o do conjunto das vari veis admiss veis O conjunto das vari veis admiss veis singular i e Q 10 6 Consequentemente justifica a dificuldade em encontrar a solu o b sica admiss vel inicial visto que como existem quatro vari veis e duas restri es de igualdade o n mero bases poss veis n o 4 r 2 r r superior a k 6 cada base est associada a 2 solu es b sicas Portanto o n mero m ximo de solu es b sicas admiss veis n o superior 6x4 mas s existe uma solu o b sica admiss vel para este problema Exemplo 3 2 Resolu o gr fica max X x sa X x 216 xX x 2 1 restri es de desigualdade 0 lt x lt 10 0 lt x lt 10 64 4 M TODO SIMPLEX PARA PROGRAM
51. J arcos ordenando respectivamente de 1 I e de 1 J Este grafo pode ser descrito por dois conjuntos o conjunto dos n s N e o conjunto dos arcos A Um grafo G fica descrito pelo par ordenado N A Seja A a matriz das incid ncias dos n s nos arcos associada rede Para cada arco j identificam se os n s de partida e de chegada do arco atrav s da fun o n de onde prov m o arco d A gt N se Ajrl d D i e da fun o n para onde vai o arco T A gt N se Ag E d j k 84 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Ent o o arco j descrito como o par ordenado de n s F j T j i e AC N As fun es F j e TG para a rede da Figura 4 1 s o apresentadas no Quadro 4 1 Quadro 4 1 Fun es de e para grafo da Figura 4 1 N mero do Arco De N Para N j dy PQ 1 1 5 2 1 2 3 2 4 4 2 3 5 4 3 6 3 4 7 4 1 8 5 2 Um grafo dito de pr prio se tiver um n mero de n s N superior ou igual a 2 e um n mero de arcos FA superiores ou iguais a um Dado um grafo G N A G N A um subgrafo de G se N CN e A c A Um subgrafo G N A de G N A um subgrafo gerador de G se N N Esta defini o ilustradas na Figura 4 2 o Grafo O io si gay ae a ENT GR de o A SANSZ Subgrafo Subgrafo Figura 4 2 Ilustra o de um grafo e subgrafos geradores do grafo 85 4 M TODO SIMPLEX PARA
52. a rvore geradora Preposi o 4 12 Seja A a matriz de incid ncia dos n s nos arcos do grafo pr prio G que conexo e tem n n s Ent o a caracter stica de A igual a n 1 Prova Pela Preposi o 4 11 G tem uma rvore geradora T Pela Preposi o 4 6 T tem n 1 arcos Pela Preposi o 4 10 A j ec AJ s o linearmente independentes Assim a caracter stica de A pelo menos n 1 Como 1A 0 a caracter stica de A inferior a n Ent o a caracter stica de A n 1 4 Preposi o 4 15 Seja A a matriz de incid ncia dos n s nos arcos do grafo pr prio G N A com n n s Seja um subconjunto de A tal que A J eje linearmente independente e tem n 1 arcos Ent o T N A uma rvore Prova O Corol rio 4 5 implica que um ciclo n o pode ser formado a partir de T visto que A j GEA linearmente independente Como T tem menos um arco que o n mero de n s e ac clico T uma rvore pela Preposi o 4 6 4 4 2 Caracteriza o de uma rede Na nossa defini o do problema PL normalizado a matriz das restri es A tem uma caracter stica igual ao n mero de linhas Pela Preposi o 4 12 a matriz da incid ncia 97 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES dos n s nos arcos para o problema PR tem uma caracter stica igual ao n mero de linhas menos um Logo n o se pode aplicar ao problema em redes o m todo do Simplex usando directamente a formula o anterior Ex
53. a impondo a introdu o de vari veis inteiras No entanto para exemplo de aplica o ser admitido que o grupo motogerador tem que estar em funcionamento durante o horizonte temporal considerado Portanto n o necess rio introduzir vari veis inteiras O problema de programa o linear para este planeamento ser escrito como max DMD Sidi keK iel s a para jeJ keK eneN Cik E SCP lt cr i Ajk E lt x X ELE ieB keK 33 2 INTRODU O MATEM TICA Considere um aproveitamento de biog s com um motogerador com a pot ncia el ctrica m xima de 800 kW sendo o horizonte temporal de um dia dividido em per odos de decis o de uma hora Considere as seguintes restri es manter o aproveitamento em convers o durante as 24 horas satisfazer o consumo de energia el ctrica pr prio indicado nas colunas d do Quadro 2 11 exportando a restante energia para venda de acordo com os pre os respeitar a previs o de 4000 unidades de volume dispon vel de biog s durante as 24 horas devendo utilizar em cada hora uma quantidade n o inferior a 60 e n o superior a 300 unidades de volume sendo a emiss o poluente total no fim das 24 horas n o superior a 3500 unidades de massa Ainda considere os seguintes dados que caracterizam respectivamente o consumo de biog s com a opera o da unidade e o n vel de emiss o poluente a 10 B 0 35 a 45 b 0 2 Os pre os para a energia el ctrica est o indicados n
54. a 2 hora 3 hora Ao mo M io mx bo Mx EN mo Lo m X lao M3X6 A Ki Mho Lo m xX Lo M X Ak 170 Lo m X Llo MX AA 170 E m X6 lso My Xi Iho im m Xs bo M Xg 1 Aig n E a Tar Sha Z xis lho is m Xg lyo R Xi mo 77 o m X Lo Nesta fase da leitura conveniente ler o manual LSNNO A Fortran Subroutine for Large Scale Nonlinear Network Optimization Problems User s Guide no subcap tulo 6 7 e simular o exemplo que est descrito nele visto que ajuda a compreender a introdu o de dados no c digo O fun o objectivo uma forma quadr tica indefinida como facilmente se prova pelo facto do tra o da matriz hessiana ser nulo pelo que este problema deveria ser tratado como uma problema que necessita dos m todos de optimiza o global No entanto pode usar se este c digo se for iniciado convenientemente e averiguado os resultados obtidos Para a introdu o da fun o objectivo no c digo necess rio decompor estas em termos aditivos ditos elementos com um n mero reduzido de vari veis para que o c digo tenha um desempenho mais eficaz Para obter as vari veis dos elementos da fun o objectivo a introduzir no 168 6 C DIGO LSNNO CASCATA H DRICA ficheiro elpr f vai se proceder an lise da distribui o dos ndices das vari veis no grafo seguinte 3 1 yi Y gt 113 gt 13 gt r
55. a literatura cient fica quer como 1 BREVE HIST RIA SOBRE A PROGRAMA O LINEAR problema de transporte de Hitchcock quer como problema de transporte de Hitchcock Koopmans Em 1956 Alex Orden prop s a generaliza o do modelo de transporte em que eram permitidos pontos de transbordo de carga Esta formula o conhecida hoje como um problema de transbordo sem limite de capacidade Ao mesmo tempo o problema de fluxos m ximos e o problema do fluxo do custo m nimo em rede foi formulado e investigado pela famosa equipa de Lester Ford e Delbert Fulkerson Entre 1950 a 1965 muita actividade foi dirigida para o desenvolvimento de algoritmos para modelos de programa o linear em rede Os algoritmos desenvolvidos podem ser classificados em duas classes como se segue 1 Especializa o do M todo Simplex 2 M todo Primal Dual A especializa o primal simplex come ou com o trabalho de Dantzig e atingiu o apogeu com o documento de Ellis Johnson Os fundamentos para o documento de Johnson podem ser encontrados basicamente em dois livros um de Dantzig e outro de Charnes e Cooper O m todo primal dual originado com o algoritmo h ngaro de Harold Kuhn para o problema de atribui o conclu do com o algoritmo da condi o de Delbert Fulkerson em 1961 1 BREVE HIST RIA SOBRE A PROGRAMA O LINEAR Muita da actividade de investiga o envolveu uma eficiente implementa o das t cnicas b sicas a particulari
56. alquer ponto do poliedro pode ser representado como uma combina o convexa dos pontos extremos desse poliedro Feita esta abordagem de conceitos para apresentar o m todo simplex vamos fazer a caracteriza o do dom nio das solu es poss veis e a identifica o neste conjunto das solu es b sicas poss veis das quais ser pelos menos uma ptima 44 3 PROGRAMA O LINEAR PL 3 2 Caracteriza o do dom nio das solu es poss veis Nesta sec o estudaremos a caracteriza o do dom nio das solu es poss veis e dentro destas solu es estudaremos as solu es b sicas poss veis com o objectivo de determinar a melhor i e estudaremos como seleccionar entre a infinidade de solu es poss veis do problema aquelas que s o solu es b sicas e dentro destas pelo menos uma ptima Esta a abordagem do m todo que ser apresentado posteriormente dito de m todo do Simplex O dom nio das solu es poss veis para a PL descrito como se segue Q x Ax b 0 lt x lt u Neste estudo assumimos que o problema tem pelo menos uma solu o poss vel i e Qz q Esta hip tese n o restritiva uma vez que tanto para problemas PL como de programa o em redes podemos introduzir vari veis artificiais que tornam o conjunto de solu es Q n o vazio claro num espa o de maior dimens o 1 e com maior n mero de vari veis Partindo da hip tese de que o problema tem solu es poss veis Q 4 vamos mostra
57. amento suportado por um problema de programa o linear necessita de dados que s o estimados atendendo ao facto do horizonte temporal ser de curto prazo o problema geralmente tratado em mbito deterministico i e os valores m dios s o considerados 35 3 PROGRAMA O LINEAR PL 3 PROGRAMA O LINEAR PL O problema de programa o linear PL expresso em programa o matem tica pela minimiza o ou maximiza o de uma fun o linear que se designa por fun o objectivo sujeita a restri es normalmente expressas na forma de inequa es O problema PL ser formulado como se segue min m x z C X C X CNXyN sujeito a aX tap X a Xy e lt b aX 85X tax 2 lt b dr t auNnXyn lt by 0 lt x lt u 1 1 2 N restri es de n o negatividade O uso de restri es de igualdade mais conveniente para o estudo da metodologia que ser apresentada neste texto para solu o do problema PL Por isso conv m converter as inequa es que expressam as restri es em equa es introduzindo no problema novas vari veis tamb m n o negativas designadas por vari veis auxiliares ou de desvio Esta convers o conduz a uma formula o do problema que se convencionou chamar forma can nica ou normalizada 36 3 PROGRAMA O LINEAR PL O problema na forma can nica descrito como se segue min m x z c x c x cyXxy 0Xp 0x N 1
58. ara o passo 1 Passo 3 Calcular os fluxos Se es lt 0 aumentar o fluxo no ciclo de Apg caso contr rio aumentar o fluxo no ciclo de Arq S 5 4 Fase dual Se a fase primal termina com a conclus o de que n o existe ciclo ent o alteram se as vari veis duais de modo a n o aumentar o n mero de condi o isto mantendo os fluxos dos arcos e ajustando as vari veis duais de forma conveniente A A Seja a rvore com que terminou a fase primal indicada por T N A Na fase dual A reduz se cada uma das vari veis duais associadas com um n em N de um valor 0 onde 127 5 ALGORITMO DA CONDI O A ser determinado pelo algoritmo seguinte Seja e A Ent o ap s a redu o das vari veis duais t m se Portanto Te TT C Tr Tr Cr Assim reduzindo o valor de cada vari vel dual corresponde a n s em T n o afecta o n mero de condi es do arcos de T Os nicos arcos cujos n meros de condi o s o A afectados por esta altera o s o aqueles que s o incidentes num n pertencente N e A num outro n pertencente N N O objectivo da fase dual determinar o valor da redu o O para as vari veis duais associadas com os n s de T de tal modo que nenhum n mero de condi o dos arcos sofra aumento e pelo menos um seja reduzido A altera o poss vel para um arco ej com T j EN e F j EN N dada no quadro A 5 4 enquanto que as altera es poss
59. as colunas pre o do Quadro 2 14 A solu o ptima est tamb m indicada no Quadro 2 14 Quadro 2 14 Solu o para o planeamento h d fuel emi Pre oo p h d fuel emi pre oo p 1 21 60 74 0 080 143 10 13 20 290 205 0 105 800 82 2 20 60 74 0 080 143 10 14 21 290 205 0 122 800 95 3 20 60 74 0 080 143 10 15 23 290 205 0 122 800 95 4 19 60 74 0 080 143 10 16 24 290 205 0 122 800 95 5 19 60 74 0 080 143 10 17 24 254 184 0 105 696 71 6 18 60 74 0 080 143 10 18 25 290 205 0 122 800 95 7 17 60 74 0 080 143 10 19 25 290 205 0 122 800 95 8 17 60 74 0 080 143 10 20 24 211 160 0 105 575 58 9 17 60 74 0 080 143 10 21 24 211 160 0 105 575 58 10 18 60 74 0 080 143 10 22 23 211 160 0 105 575 58 11 18 60 74 0 080 143 10 23 22 211 160 0 105 575 58 12 19 290 205 0 105 800 82 24 21 211 160 0 105 575 58 total 950 1014 12371 191 total 4000 3229 10743 1107 34 2 INTRODU O MATEM TICA E pre o E consumo E exporta o Figura 2 10 Pre os consumo de metano energia el ctrica exportada Observe que este plane
60. ativos das albufeiras em rela o ao mar Estes n veis ser o calculados em fun o dos volumes de gua armazenados nas albufeiras sendo consideradas respectivamente as seguintes express es para a altura de queda e n vel da gua nos reservat rios k k k k k k k hj l l sendo l l m vi e lg la tM aV 6 4 i l com los M ER 163 6 C DIGO LSNNO CASCATA H DRICA A figura seguinte ilustra a conven o utilizada para os indicies e as vari veis que determinam a produ o das centrais hidroel ctricas Figura 6 4 Representa o da altura de queda til para uma albufeira 6 5 Equa es de balan o Outras restri es do problema s o as equa es de balan o que imp e a condi o de os n s n o terem capacidade de armazenamento A soma de todos os fluxos dos arcos sobre uma superf cie fechada que encerra um n tem que ser igual a zero ou seja n n n n n n n Vi r tia S V t S 6 5 6 6 Constru o dos ficheiros para a aplica o LSNNO Como aplica o inform tica para suporte da solu o deste problema decisonal de gest o de curto prazo de um aproveitamento hidroel ctrico em cascata composto por tr s albufeiras sugere se o Software designado por LSNNO Large Scale Nonlinear 164 6 C DIGO LSNNO CASCATA H DRICA Network Optimization desenvolvido no departamento de matem tica ND de la Paix B lgica e que est dispon vel no site da Internet com o
61. atriz cuja dimens o o n mero de n s pelo n mero de arcos I xJ sendo os seus elementos definidos da seguinte forma 1 se do n i sai o arco j A 9 1 se no n ientra o arco j O caso contr rio 2 INTRODU O MATEM TICA A matriz A acima definida chamada a matriz de incid ncia dos n s nos arcos A matriz de incid ncia dos n s nos arcos correspondente rede da Figura 2 1 a seguinte arcos i 2 3 4 5 6 T 11 1 1 1 sos 2 1 41 1 1 3 1 1 4 1 1 l 1 Como cada arco s incidente em dois n s uma propriedade que caracteriza esta matriz que cada coluna tem exactamente dois elementos n o nulos um igual a 1 no n de onde sa o fluxo para o arco e outro igual a 1 no n onde entra o fluxo do arco Qualquer matriz independentemente da sua origem que tenha esta propriedade ser chamada matriz de incid ncia dos n s nos arcos visto que pode ser representada por uma rede A cada arco j da rede est associado uma vari vel de decis o x definindo a quantidade de fluxo atrav s do arco j sendo o vector cuja dimens o J e as coordenadas s o os fluxos nos arcos indicado por x O custo unit rio de transporte do fluxo do arco j indicada por cj tendo o vector e dos custos unit rios dimens o J e coordenadas dadas pelos custos unit rios A capacidade do arco j em termos de fluxo m ximo indicada por uj tendo vector dos fluxos m ximos u dimens o J e coordenadas dadas pelos os
62. das decis es em est dios de uma hora durante um horizonte temporal de um dia a uma semana A gest o desta fonte de energia no curto prazo tem que considerar a varia o dos pre os e a emiss o de metano estimada recorrendo ao hist rico e ou particularmente numa fase de projecto ao modelo LandGEM da USEPA http www epa gov utilizado na Europa O comportamento do jogo dos mecanismo t cnico econ mico neste tipo de aproveitamento pode ser modelizado por um problema de programa o matem tica linear A fun o objectivo o proveito econ mico total obtido ao longo do horizonte temporal calculado por DM pi dy keK iel sendo p a pot ncia el ctrica na unidade i no est dio k e d a pot ncia el ctrica associada ao consumo pr prio de energia el ctrico energia n o exportada no est dio k 32 2 INTRODU O MATEM TICA O consumo do biog s e o n vel de emiss o poluente de uma unidade calculado respectivamente por Cop dx Ba Pi Ei p ax Pi As restri es podem ser limita es no consumo de biog s em cada est dio a emiss o poluente limitada ao longo do horizonte temporal para um conjunto de unidades Ci lt D Caps CR jelkeK icA jk req k p req Es ES SEMpPSE ne N ieB keK Ainda podem ser imposi es no n vel de pot ncia das unidades se a unidade estiver em funcionamento pot ncia compreendida entre um valor m nimo e o valor m ximo de pot ncia poss vel caso contr rio nul
63. de de transporte ilimitada O director de produ o pode tamb m considerar que a capacidade de transporte nestes arcos limitada e igual a capacidade de produ o das respectivas f bricas ou at considerar que capacidade de transporte qualquer n mero superior ao excesso de capacidade de produ o Figura 2 6 Produ o e distribui o na Poliremos Na Figura 2 6 e nos Quadros 2 6 e 2 7 apresentada outra op o poss vel para o director de produ o ilustrar a rede deste problema Esta variedade de ilustra o de um problema corresponde a uma variedade na sua formula o que de facto pode ser encarada como 20 2 INTRODU O MATEM TICA uma arte visto que n o sistem tica deixando alguma margem de liberdade que deve ser convenientemente explorada Nesta ltima op o o director de produ o considera s um n para cada f brica e aglomera o custo de produ o da f brica com o custo de transporte para cada uma das regi es criando arcos com custo unit rio igual ao custo de produ o mais o custo de transporte por tonelada de pol mero de cada f brica para cada uma das regi es correspondendo a uma simplifica o na formula o do problema No entanto perde em descri o do processo de produ o e distribui o visto que agora s existe um arco na rede que est associados aos dois processos O valor do fluxo m ximo num arco que substitui outros o m nimo entre os fluxos m ximos dos a
64. de do problema original A rede expandida representada na Figura 5 4 e os c lculos s o indicados de seguida para os dois primeiros passos do algoritmo da condi o i 10 10 e5 e6 10 00 0 00 Figura 5 4 rvore para o exemplo n 4 artificial 140 5 ALGORITMO DA CONDI O Seja M um n mero positivo mas muito grande Big M method ou considere no que se segue que M gt 00 ALG 5 3 Passo 0 Iniciar Fluxos x gt RC X X x 0 0 0 0 5 5 Potenciais t mo z z l0 0 0 0 Passo 1 Encontrar um arco fora da Condi o Lucros reduzidos de cada arco ci Nia Z Tra T C 0 0 1 1 c2 Nel Z Tr O 0 0 1 1 C3 Teo Trg 03 0 0 3 3 C4 Tp Tra 0 0 0 10 10 cs Tres Tr s Os 0 0 0 0 C6 Tre Tre T C6 0 0 M M Os n meros de condi o s o x 0 c 1 gt K 0 na condi o xX 0 c2 1 K 0 na condi o x 0 c3 3 gt K 0 gt na condi o x 0 c4 10 gt K 0 gt na condi o x 5 cs 0 gt K 0 na condi o x 5 c M gt K 5 gt fora da condi o f K 5 j l J 141 5 ALGORITMO DA CONDI O O arco e fora da condi o e o algoritmo continua Observe que pelo facto dos potenciais dos n s serem nulos os lucros reduzidos s o o sim trico dos custos unit rios de transporte nos arcos sendo estes custos n o negativos s o arco com custo unit rio infinito est fora de condi o S
65. desde a selec o do primeiro arco candidato at selec o do arco candidato que tenha o maior valor absoluto de lucro reduzido mr j Tro cjl Na maior parte das estrat gias de avalia o o ficheiro dos arcos gerido de forma cronol gica isto numa pesquisa anterior o ltimo elemento observado foi o localizado na posi o k ent o a pr xima em pesquisa come a na posi o k 1 Sempre que o fim do ficheiro alcan ado a pesquisa continua na posi o 1 O m todo simplex termina quando a pesquisa atrav s do ficheiro dos arcos n o consegue encontrar um arco candidato que por uma altera o de fluxo melhora o valor corrente da fun o objectivo 117 5 ALGORITMO DA CONDI O 5 ALGORITMO DA CONDI O PARA A PROGRAMA O EM REDES Neste cap tulo ser apresentado outro m todo conhecido por Algoritmo da Condi o para a resolu o do problema de PLR O problema PLR em estudo est escrito na seguinte formula o can nica min cx sa Ax rI PR 0 lt x lt u Onde A a matriz de incid ncias dos n s nos arcos e Ir i e a soma dos fluxos que entram nos n s igual soma dos fluxos que saem dos n s Ainda neste algoritmo assume se que u gt 0 O Algoritmo da Condi o foi desenvolvido como se disse no cap tulo 1 por Delbert Fulkerson em 1961 Contrariamente ao primal simplex o algoritmo da condi o n o mais uma especializa o de um m todo geral Este algoritmo foi desenvolvido e
66. do as linhas e colunas da matriz b sica tomando para a primeira linha e para a primeira coluna a linha correspondente ao n n e a coluna correspondente ao arco eja podemos representar B da seguinte maneira eji ES 1 1 0 ln m sS i 1 te i B Seja T N n A eja Pela Preposi o 4 9 T uma rvore com n 1 arcos Se n l 1 ent o B triangular visto que a ltima coluna de B corresponde ao vector e Se n 1 gt 1 ent o de novo pela Preposi o 4 8 T tem pelo menos dois pontos 1 r r extremos Considere de novo o processo seja n um ponto extremo de T que n o n 102 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Tiha E r raiz e seja e o 0 arco em T incidente em nz Ent o a linha n de B tem s um elemento n o nulo como anteriormente igual a 1 ou 1 Assim tomando respectivamente para a segunda linha e para a segunda coluna a linha correspondente ao n n e a coluna correspondente ao arco ejo podemos representar B da seguinte maneira e ej2 r r E i n n pESESSESSSaNE Sos dococcccccccel i EAA T f n no S I i te RES SERES 7 ooa g Ea t B Figura 4 7 Processo para transformar a matriz B numa matriz triangular Em cada repeti o deste processo introduzido na matriz reordenada uma nova linha e coluna repetindo o processo o n mero de vezes igual ao n mero de n s do grafo B transformada por reordena o das linhas e co
67. do n i e chega ao n j Portanto ACNxN O arco i j incidente nos v rtices i e j O arco i j um arco de sa da do n i e um arco de chegada do n j O n j diz se adjacente ao n 1 se existir o arco i j Dois arcos s o adjacentes se forem ambos incidentes no mesmo n A lista de adjac ncia dos arcos de um n 1 indicada por A i o conjunto de arcos que saem do n i isto A i i j A je N A lista de adjac ncia de n s de um n i indicada por V i o conjunto de n s adjacentes ao n 1 isto V M fje N 1 eA Claro que o A i igual ao FV i e dado pelo o n mero de arcos que saem do n 1 Um grafo diz se completo se entre quaisquer dois v rtices existir uma arco A densidade de um grafo a raz o entre o n mero de arcos de grafo e o n mero de arcos do grafo completo com o mesma n mero de n s Dado um grafo G N A N A um subgrafo de G se N CN e A CA Uma rede um grafo cujos arcos t m r tulas i e existem valores num ricos associados por exemplo custos unit rio de transporte num arco capacidades m xima de um arco Assim rede um terno ordenado R N A L sendo N A um grafo e L o conjunto dos valores num ricos associados aos arcos 2 2 Programa o linear em redes O nome programa o em redes faz lembra de imediato a rede el ctrica a rede telef nica a rede rodovi ria a rede ferrovi ria etc Em todas estas redes existe em
68. e eCtalquee e YE E 0 caso contr rio O vector y tem como coordenadas diferentes de zero os n meros de orienta es dos arcos da rede relativamente a um ciclo C caso um arco n o perten a a este ciclo a coordenada respectiva nula Ou seja se o arco da rede e for tamb m arco do ciclo C ent o y o c orienta o do arco no ciclo caso contr rio y 0 Logo A y 0 Como ilustra o considere a rede na Figura 5 1 123 5 ALGORITMO DA CONDI O Figura 5 1 Exemplo de uma rede Considere o ciclo C f l Eis 2 er A Er 3 Ez 1 a orienta o dos arcos do ciclo o c fi 1 1 1 sendo y 1 1 0 1 1 A matriz de incid ncias dos n s nos arcos dada por l l 1 l l A 1 1 l 1 1 e 1 0 l l 1 0 A 1 l l 0 0 xX 7 1 1 l 1 0 1 1 1 0 Considere o vector dos fluxos x poss vel Seja A gt 0 dado um ciclo e o correspondente vector das orienta es y Xx x Ay satisfaz Ax r A transforma o de fluxo 124 5 ALGORITMO DA CONDI O x x Ay no ciclo C diz se que aumenta o fluxo A No entanto conv m salientar que tal aumento corresponde para um arco e cuja orienta o y 1 a uma diminui o de valor A no seu fluxo A Considere K o n mero de condi o para o arco e com fluxo x e K o n mero de E A condi o para o arco e com fluxo Xx Dado o vector dos fluxos x a fase primal tenta A encontrar um ciclo de modo que para x
69. e t m valor m ximo e a respectiva coordenada do vector do custo reduzido e B N DUB No ptimo se a coordenada do vector de custo reduzido for negativa a respectiva vari vel n o b sica tem que estar no valor m ximo caso contr rio existe hip tese de melhoria da fun o objectivo por aumento desta vari vel Ainda se uma coordenada do vector custo reduzido for positiva a respectiva vari vel n o b sica tem que estar no valor nulo caso contr rio existe hip tese de melhoria da fun o objectivo por diminui o desta vari vel A condi o de uni o y UY 4 termina o algoritmo e o ponto ptimo o ponto corrente x x x Caso contr rio o algoritmo prossegue com a selec o de um k ey U y sendo k um ndice que identifica uma vari vel n o b sica que por altera o do seu valor permite uma melhoria do valor da fun o objectivo Ent o o ser determinado por e L se key Hi se key O significado deste 6 indicar se a coordenada n o b sica k vai ser incrementada ao decrementada como se constata no passo 3 seguinte de actualiza o Caso 8 1 a coordenada n o b sica k vai ser incrementada Caso 1 a coordenada n o b sica k vai ser decrementada 57 3 PROGRAMA O LINEAR PL Passo 2 Determina o do Passo A coordenada n o b sica k vai ser actualizada de acordo com xp a logo o m ximo valor que pode tomar a u As coordenadas b sicas s o actual
70. e5 1 Eua 6 3 66 4 e est representado na Figura 5 6 como Ce lt 0 4 4 K x x x x x 4 4 0 0 6 6 Voltar ao passo 1 do ALG 5 3 0 Figura 5 6 Ciclo C 146 ALG 5 3 5 ALGORITMO DA CONDI O Passo 1 Encontrar um arco fora da Condi o De acordo com os novos fluxos e os ltimos lucros reduzidos os n meros de condi o s o os seguintes x 4 x 4 x 0 x 0 x 6 X 6 Arco e ALG 5 1 c2 0 3 cs 0 c1 0 K 0 gt na condi o K 0 gt na condi o K 0 na condi o K 0 na condi o b Ly UU K 0 na condi o ce M 2 gt K 6 gt fora da condi o 6 Kj 6 est fora da condi o seguir para a fase primal A Passo 0 Iniciar Como ce lt 0 ent o N T 6 3 Agy 4 x 6 e0 conjunto dos arcos A 4 Passo 1 Determinar candidatos para a rvore y wy 4 Como y Uwy 0 seguir para a fase dual ALG 5 2 Passo 1 Determinar os arcos incidentes na rvore Wa es e4 Es jey Passo 2 Determinar a altera o m xima possivel p min 2 Es bd 3 M 2 J 2 147 5 ALGORITMO DA CONDI O Passo 3 Reduzir as vari veis duais T3 2 2 4 E para os potenciais vem 7 z ma nm 0 1 4 O tomando os lucros reduzidos os valores Ci Te Tr C 0 1 1 0 K 0 C2 Tp Tro C 1 4 1 2 K 0 c3 Tio Trg 03 1 4 3 0
71. eguidamente ser feita de novo a resolu o do problema anterior alterando os requisitos dos n s e usando o m todo de inicia o por n e arcos artificiais pelo que fica ao cuidado do leitor a continua o desta resolu o 5 6 Exemplo de iniciar o algoritmo da condi o por n e arcos artificiais Uma empresa pretende proceder ao planeamento de uma subcontrata o para transporte de 10 geradores constru dos na f brica de Lisboa n 1 para um cliente localizado em Luanda n 3 existindo a alternativa de enviar os transformadores para a frica do Sul n 2 e da para Luanda O grafo da rede para o problema representado na Figura 5 5 sendo o n 2 o n de transbordo situado na frica do Sul e o n 4 um n fict cio para iniciar a solu o do problema com uma solu o b sica admiss vel pelo m todo dos arcos e n artificial para o algoritmo da condi o es i e5 0 0 2 0 Figura 5 5 Grafo do problema 142 5 ALGORITMO DA CONDI O Problema na forma can nica min x X 3x 5x s a x x x 10 X x 0 X Ry X 10 X x 0 0 lt x lt 8 0 lt x lt 4 0 lt x lt 5 0 lt x lt 20 ALG 5 3 Passo 0 Iniciar Potenciais n z m 0 0 0 Fluxos x x x x x x l 0 0 0 0 10 10 Passo 1 Encontrar um arco fora da Condi o Lucros reduzidos de cada arco Ci Tgi Tra 7C 0 0 1 c2 Treo Tr 6 0 0 1 1 C3 Tio
72. eis x 0 ur as condi es que nos permitem escolher direc o admiss vel de melhoria da fun o objectivo s o dadas por ei ix 0 e BIN lt 0 e x u e e e B N gt 0 54 3 PROGRAMA O LINEAR PL Agora s falta descrever como estabelecer a metodologia para o passo 2 do algoritmo anterior obten o de uma nova solu o Como j conhecido a direc o admiss vel de melhoria da fun o objectivo no ponto x determinada por l se x 0 de sendo N N l se x u falta determinar um transla o do ponto corrente segundo o vector da direc o admiss vel de melhoria da fun o objectivo O problema a resolver para estabelecer a metodologia para o passo 2 tem s uma vari vel de decis o a amplitude do passo e ent o descrito como se apresenta de seguida min Bop De eSBN a e e BN x a 5 sa 0 lt x ad lt u 0 lt x B N i c lt u ou seja eliminando a presen a das constantes na fun o objectivo min e e BN a a gt 0 sa 0 lt x ad lt u 3 11 0 lt x B N 0u6 lt u 3 12 de salientar que devido linearidade da fun o elx qualquer incremento em a resulta num decr scimo no valor da fun o objectivo Assim interessa nos fazer a o maior poss vel desde que satisfa a 3 11 e 3 12 Se d D ent o se nos deslocarmos segundo a direc o d pode eventualmente acontecer que alguma vari vel x assuma valores fora dos li
73. eito da igualdade o volume de gua dispon vel na albufeira i para ser gerido no periodo k igual ao volume que transita para a hora k 1 mais o turbinado e o descarregado para a albufeira de jusante no per odo k 25 2 INTRODU O MATEM TICA Na Figura 2 9 est representada a rede para um aproveitamento h drico em cascata com tr s albufeiras que ser considerado neste exemplo Com o fim de ilustrar o exemplo ser considerado um horizonte s com tr s horas Esta rede uma expans o temporal da arboresc ncia relativa primeira hora gt gt gt v v v y v v gt gt gt v vy v y v vy gt gt gt v v v v v v N raiz Mar gt Fim de Cascata Figura 2 9 Expans o temporal da arboresc ncia da primeira hora at a terceira hora A fun o objectivo determinada pela soma do lucro obtido com a explora o de cada central hidroel ctrica Para obter um modelo linear ser considerada como hip tese que a queda til permanece constante durante o horizonte temporal Assim a express o do lucro para a central i no per odo k escrita como lucro A p com pi pit 2 26 2 INTRODU O MATEM TICA sendo o valor econ mico da energia el ctrica pre o unit rio no per odo k Para obviar a que no fim do horizonte o volume de gua armazenado seja o m nimo normal impor cotas finais dos reservat rios ditas cotas objectivo que corresponde a introduzir no problema de programa
74. el em certas situa es um per odo inferior quer para obter uma melhor gest o do aproveitamento quer para considerar tempos de transito da gua entre albufeiras que necessitem de reduzir a amplitude do per odo Neste problema existem condicionantes determinadas pelas limita es f sicas das albufeiras das turbinas e condicionantes determinadas quer por raz es de seguran a das albufeiras quer por quest es ambientais Os dados que caracterizam a capacidade produtiva dos recursos ao longo do horizonte temporal s o o volume inicial da gua armazenado nas albufeiras e as s ries de aflu ncias aos reservat rios ao longo dos per odos do horizonte temporal 6 3 Limites para as vari veis Os volumes m ximos e m nimos das albufeiras s o determinados por raz es quer ecol gicas quer de seguran a cujo o estudo n o objectivo desta simula o Figura 6 2 Volume m ximo e m nimo de uma albufeira n vel da gua numa albufeira 159 6 C DIGO LSNNO CASCATA H DRICA Consequentemente os volumes m ximos e os volumes m nimos para as albufeiras s o considerados dados do problema Nas express es indicadas de seguida o ndice superior corresponde ao per odo e o inferior corresponde albufeira Quando o ndice superior for nulo per odo zero corresponde a valores de iniciais das vari veis Dados v Volume inicial na albufeira i k A a gt a Aflu ncia albufeira i no intervalo de
75. er um problema de minimiza o permite que a fun o objectivo seja interpretada como um custo Cada coordenada do vector c um coeficiente de custo associado respectiva coordenada do vector x No texto seguinte ser estudado os procedimentos a seguir para a resolu o de um problemas de programa o linear PL que esteja formulado de acordo com forma can nica Iniciaremos com alguns t picos matem ticos importantes para o estudo do problema PL apresentando de seguida o m todo simplex 38 3 PROGRAMA O LINEAR PL 3 1 Propriedades do espa o vectorial euclidiano Neste subcap tulo ser recordado algumas no es fundamentais Denomina se R ao espa o Euclidiano n dimensional cuja norma ou comprimento do vector xeR calculada por x Jx x x Um vector cuja norma x 1 dito vector unit rio Consideremos dois pontos distintos x e x do espa o R e o conjunto de escalares A cR o conjunto de combina es lineares dos pontos x e x usando os escalares do conjunto A definem o conjunto T dos pontos x que obedecem a D x x 1 1 x x AEA Se A R ent o o conjunto T define uma linha que passa pelos pontos x e x na direc o do primeiro ponto para o segundo Se A A 0 lt A o conjunto T define uma semi recta fechada em x e com direc o definida pelo vector x x Se A 1 0 lt A lt 1 o conjunto I define um segmento de recta fechado com os pontos extremos x e
76. eradas que s o uma aproxima o dos dados para as albufeiras de Miranda Picote e Bemposta Volumes m nimos e m ximos permitidos nas albufeiras em 10fm Miranda 173 6 C DIGO LSNNO CASCATA H DRICA Picote V 14 Bemposta V 233 V 0 Caudais m nimos e m ximos que poss vel entornar nas albufeiras em 10fm Miranda Picote Bemposta Caudais m ximos que poss vel turbinar nas albufeiras em m Miranda T 23 400 Picote T 19800 Bemposta T 25200 Requisitos Aflu ncias verificadas nas albufeiras em cada hora em m Albufeira Ph 2 h 3 h i 167 h 168 h Miranda 9 2x10 0 0 no 0 0 Picote 4x10 0 0 T 0 0 Bemposta 5x10 0 0 oe 0 0 6 8 Manual do utilizador do LSNNO O Fortran Subroutine for Large Scale Nonlinear Network Optimization Problems User s Guide est o s dispon veis em LaTeX no ficheiro Isnno tex com o objectivo de permitir uma leitura o Users Guide of LSNNO anexado nas folhas seguintes 174
77. erizar a sua oferta tamb m de acordo com a regulamenta o para o mercado O objectivo de atingir a maximiza o do lucro obtido com a venda da energia el ctrica salvaguarda a viabilidade da empresa e a sua competitividade num mercado competitivo de energia el ctrica Num aproveitamento hidroel ctrico a optimiza o da gest o dos recursos consiste em decidir a gest o da gua que est dispon vel Esta optimiza o sujeita a condicionantes que s o impostas quer pelo equipamento condicionantes t cnicas quer por raz es ecol gicas e de seguran a condicionantes pol ticas Envolve a determina o do volume de gua a turbinar mais proveitoso em cada per odo tendo em conta o valor pago pela energia produzida nesses per odos que vari vel durante o per odo A dificuldade em tomar as decis es mais adequadas cresce quando a empresa de produ o de energia el ctrica tem que gerir mais de que um aproveitamento h drico e esses aproveitamentos s o em cascata As vari veis ligadas aos tr nsitos de volume de guas ficam relacionadas pelas equa es de balan o das guas complicando o problema e o gestor tem que recorrer a sistemas de suporte tomada de decis o para conseguir ter uma gest o adequada que atinja o melhor proveito O recurso simula o computacional do modelo matem tico do sistema a gerir e a t cnicas de optimiza o permitem gerar um sistema de informa o para o suporte das decis es racionais d
78. fluxos m ximos nos arcos A cada n est associado um requisito do n o requisito do n i indicado por ri tendo o vector dos requisitos r dimens o I e coordenadas dadas pelos requisitos de cada n Se r gt 0 o n 1 de fornecimento ou oferta com uma oferta igual a ri i e injectado fluxo na rede por este n Se ri lt O o n i de consumo ou procura com um consumo igual a Iril i e retirado fluxo da rede por este n Se r 0 10 2 INTRODU O MATEM TICA o n 1 um n de transbordo i e n o injectado nem retirado fluxo da rede neste n Em formula o matem tica o problema da minimiza o do custo do fluxo da rede representado da seguinte forma min ex s a PR Ax r NP 0 lt x lt u Onde A a matriz de incid ncia dos n s nos arcos e s a sigla abreviatura de sujeito a Diversos casos particulares da programa o linear em rede PR Programa o em Redes NP Network Programming mereceram estudos particulares que originaram c digos mais eficientes para a sua resolu o em compara o com a utiliza o de c digos mais gen ricos Uma classifica o desses casos apresentada de seguida 1 Problema de transbordo com capacidade n o limitada Este problema uma particulariza o do programa o linear em rede na qual uj para todo j 1 e n o existe uma limita o de fluxo m ximo dos arcos 2 Problema de transporte com capacidade li
79. fun o objectivo tem o menor valor 1 e tem um crit rio de optimilidade que termina o algoritmo Como o n mero de pontos extremos de Q finito o m todo do simplex um algoritmo perfeito na verdadeira acep o da palavra terminando ap s um n mero de itera es fixo 3 3 M todo primal simplex O m todo primal simplex pode ser considerado como um caso particular dos algoritmos conhecidos por m todo da direc o admiss vel de melhoria do valor da fun o objectivo Uma direc o d diz se admiss vel no ponto y poss vel se existir t gt O tal que y o d admiss vel para qualquer O lt a lt 7 como t gt 0 Para o problema de minimiza o uma direc o d designa se por direc o admiss vel de melhoria do valor da fun o objectivo no ponto y se d uma direc o admiss vel e a derivada direccional da fun o objectivo ex segundo d no ponto y negativa o que significa que segundo esta direc o existe um intervalo onde a fun o objectivo 50 3 PROGRAMA O LINEAR PL decresce Dadas as defini es acima o m todo geral da direc o admiss vel pode ser descrito como se segue Algoritmo ALG 3 1 M todo Geral da Direc o Admiss vel Passo 0 Inicia o Considere um ponto y solu o poss vel para o problema PL inicie a zero o ndice k da itera o i e fa a a atribui o k lt 0 Passo 1 Determina o de uma Direc o Admiss vel de melhoria do valor da Fun
80. ge n u e tais que TA c u A x u u 0 x1 0e p20 e20 71 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Prova Considere o problema de programa o linear escrito como um problema de maximiza o como se segue max X min ex s a s a Ax b 0 Ax b 0 u x gt 0 u x gt 20 x gt 20 x gt 0 A fun o de lagrange ser escrita como L x n p cx n Ax b u x dx 3 13 As condi es de acordo com o teorema de Karush Kuhn Tucker s o KK T 1 Ax be0 lt x lt u KKT 2 3p 20 talque u u x 0 Ax 0 KKT3 c 7A n A 0 o que prova o teorema Ou seja resolver o sistema de Karush Kuhn Tucker Ax b x u u 0 0 lt x lt u x1 0 TA C u u gt 0 12 gt 0 em ordem a x x u matematicamente equivalente a resolver o problema PL Este sistema ser usado no estudo da programa o em redes para obter o algoritmo da condi o 72 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Exemplo 3 5 Considere o problema do exemplo 3 4 verifique usando o sistema de Karush Kuhn Tucker que o ponto ptimo obtido por resolu o gr fica ptimo O problema ser escrito como min x xX sa x x x 16 X X X 1 0 lt x lt 10 0 lt x lt 10 0 lt x lt 4 0 lt x lt ll Cuja solu o ptima foi obtida na Figura 3 3 x x x x I0 10 4 1 Caro que as condi es de admissibilidade K K T l Ax be 0 lt x lt u s o satisfeitas As condi es K K T 2 obr
81. igam a que 0 e que u 0 Portanto basta determinar Hj Hos H3 Z0 e m m ER tais que m A p c logo m 0 n H 1 n u 1e m u 0 Pelo que tem que ser n 120 p m le 7 4u 20 Consequentemente s o solu o do sistema de Karush Kuhn Tucker os seguintes vectores x x Xx x J 10 10 4 1 Im mo 0 0 u to to mal 1 10 0 A l 0 0 O0 O Observe que a condi o necess ria para ter uma solu o do sistema de Karush Kuhn Tucker escolher um x tal que 1 lt 7m lt 0 Outra solu o poss vel seria fazer m 1 7 0 u u H Hl 0 0 1 0 73 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES 3 5 Teoria da dualidade Associado ao problema de programa o linear que no contexto da teoria da dualidade tamb m dito de problema primal existe o problema dual Considere a fun o de lagrange 3 11 o subproblema dual ser descrito pelo seguinte problema sem restri es max L x 7 u sendo L x m u A c 7A u x ab pu eu A2 gt O A solu o do subproblema dual tem que satisfazer condi o VL x m u A 0 i e e 7A u 0 7A u c A Portanto o problema dual escrito como min nb uu s a TA u c u gt 0 O problema dual tem algumas propriedades muito teis sob o ponto de vista da programa o em redes O problema primal e o seu dual podem ser escritos como min cx m x br up sa Ax b PL sa nA p lt c PLD 0 lt x lt u Prima
82. igma usado para indicar a fun o sinal de um n mero definida por 1 se x gt 0 o x 0 se x 0 1 se x lt 0 Ser o ainda empregues outras nota es matem ticas que ser o apresentadas ao longo do texto quando forem requeridas No que se refere aos conceitos de grafo e de rede que surgem em numerosos ramos da ci ncia onde t m existido contribui es pr prias no contexto destes ramos da ci ncia para a evolu o do estudo de problemas de fluxo em redes que a forma mais simples de modelar matematicamente muitos problemas desses ramos utilizando o conceito de rede No entanto as perspectivas de cada ramo s o n o convergentes sendo facto que a literatura da teoria de grafos e de redes n o possui uniformiza o existindo diversidade variedade de conven es e nota o Por isso neste ponto ser feita informalmente uma descri o mais exaustiva do conceito de grafo dirigido para fixar a linguagem que ser usada neste texto Um grafo constitu da por dois conjuntos finitos O conjunto dos n s v rtices ou nodos indicado por N O conjunto das arcos arestas ou ramos indicado por A Assim um grafo G indicado 2 INTRODU O MATEM TICA como um par ordenado G N A e de ordem n se A n Cada arco representada por um par ordenado de n s i jJ com i je i je N em que i o n de onde prov m o arco o n da cauda e j e o n para onde se dirige o arco ou o n cabe a diz se que arco i j sai
83. ionar um icey Uy sendo i o ndice de uma coluna da matriz B substituir na matriz B e a coluna B i pela coluna N k e na matriz N a coluna N k pela B 1 O algoritmo prossegue para o passo 1 Se A gt 0 para cada itera o a converg ncia num n mero finito de itera es garantida Pois o n mero de v rtices do poliedro finito e em cada itera o selecciona se um v rtice a que corresponde um melhor valor da fun o objectivo 59 3 PROGRAMA O LINEAR PL Uma caracter stica importante deste algoritmo a de convergir para uma solu o ptima mesmo que a hip tese de n o degener ncia n o se verifique A n o verifica o desta hip tese s implica numa prova do algoritmo com maior elabora o matem tica Se A 0 simplesmente dever ser feita uma nova parti o de A de modo a obter uma nova matriz B e continuar com aplica o do algoritmo A nova matriz B corresponde ao mesmo ponto extremo de modo a que nenhum progresso feito no sentido de melhorar o valor da fun o objectivo A nica dificuldade que poder suceder ao fim de algumas itera es a mesma matriz B reaparecer com A 0 Neste caso o algoritmo repete as itera es por isso diz se que o m todo entrou em ciclo cycling Felizmente s o raras as situa es em que os problemas lineares reais entram em ciclo Contudo quando isso acontece pequenas altera es no c digo evitam a entrada em ciclo Algumas t cnicas simples
84. istem duas maneiras de proceder para aplicar o m todo do Simplex ambas reformulando o problema PR de modo que a matriz das restri es tenha uma caracter stica igual ao n mero de linhas full row rank 1 podemos fazer desaparecer uma linha da matriz de incid ncias dos n s nos arcos ou 2 podemos adicionar uma coluna linearmente independente i e adicionar uma nova vari vel que ter de ter o limite superior igual a zero Assim consegue se que a nova matriz das restri es tenha caracter stica igual ao n mero de linhas Nesta abordagem para o problema PLR escolhemos a ltima maneira de proceder Consideremos a seguinte formula o para o PLR min ex s a Axtae r PR 0 lt x lt u 0 lt a lt 0 Onde A a matriz de incid ncia dos n s nos arcos e k um inteiro n o superior ao n mero de n s n Como a est restringido a zero qualquer ptimo este PLR ser ptimo para o problema PLR original Observe que o coeficiente desta vari vel na fun o objectivo nulo No entanto o coeficiente n o necessita de ser nulo visto que o valor que toma a vari vel nulo No subcap tulo 4 3 esta observa o corresponde a afirmar que os potenciais dos n s s o definidos a menos de uma constante aditiva 98 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES E k r Mostraremos que existe um conjunto de n colunas da matriz A e que uma base para o espa o euclidiano n dimensional Preposi o 4 1
85. izadas de acordo com B 1 x B N k a fazendo y B N k x a y tem que se verificar 0 lt x ady lt u isto 0 lt x7 a o y y su B j Ent o se o o y o m ximo valor que a pode tomar dado por Ea yj Se uu x o y o m ximo valor que a pode tomar dado por y Finalmente h que escolher um a que esteja de acordo com o que se escreveu anteriormente Pelo que o passo 2 consiste em calcular y B N k B e A min F A 0 u xi min 4 o0 SI lt lt I lt HAEA ETA J Finalmente calcular o passo A mintA A U Passo 3 Actualiza o O valor da coordenada de x correspondente coluna k da matriz n o b sica actualizado de acordo com x xi A 58 3 PROGRAMA O LINEAR PL e as coordenadas b sicas s o actualizadas de acordo com x amp x Ady Se A ur i e A igual ao valor m ximo da coordenada n o b sica k o algoritmo prossegue para o passo 1 Caso contr rio prossegue com o passo 4 Passo 4 Substitui o e actualiza o da base Consideremos os conjuntos y j oly 8 e x 0 e y j oly 8 e x uB Em que wy o conjunto dos ndices das vari veis b sicas que tiveram decremento no seu valor no passo 3 tendo ap s esse passo valor nulo e y o conjunto dos ndices das vari veis b sicas que tiveram incremento no seu valor no passo 3 tendo ap s esse passo valor m ximo Selecc
86. junto dos arcos q implica que G uma rvore sendo ela pr pria uma rvore geradora de si mesmo Se n gt 2 seja m o maior inteiro tal que exista um subgrafo de G que uma rvore e tem m n s Qualquer subgrafo de G com um n uma rvore ent o m gt 1 Ser mostrado que se for m lt n resulta uma contradi o Pela defini o de m existe um subgrafo de G indicado por T N IN que uma rvore que tem m n s Como tem m lt n n s N N 4 Seja L o conjunto dos arcos de A incidentes num n de N e noutro de N N O conjunto L 4 visto que caso contr rio o grafo G n o seria conexo Dado um arco ejeL seja j pertence a N No n onde o arco 1 incide e seja T N A onde N U j e A Ute Por constru o T um subgrafo de G que uma rvore e tem m 1 n s Isto contradiz a defini o de m Logo tem que ser m n portanto existe sempre a rvore geradora de um grafo G 4 As Preposi es 4 10 e 4 11 mostram que para um dado grafo G com a correspondente matriz de incid ncias dos n s nos arcos A existe uma rvore geradora de G indicada por T tal que as colunas de A correspondentes aos arcos de T s o linearmente independentes 96 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Mostremos agora em primeiro lugar que a caracter stica de A igual ao n mero de n s menos um e em segundo lugar que o conjunto m ximo das colunas linearmente independentes de A corresponde a um
87. l u gt 0 Dual No contexto da teoria da dualidade x o vector das vari veis primais e 7 u O vector das vari veis duais A hip tese de o dom nio das solu es poss veis para a PL n o ser vazio implica que os problemas s o equivalentes isto o valor ptimo do problema primal igual ao valor ptimo do problema dual Esta equival ncia traduzida pelas seguintes proposi es 74 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Preposi o 3 10 Seja x uma solu o ptima para o PL e seja m u uma solu o ptima para o PLD Ent o cx bm up Preposi o 3 11 Seja x solu o ptima para o PL B a matriz b sica e ec o vector cujas componentes s o as componentes de c correspondentes s coordenadas b sicas A j c u Sejam n c B e iso UE o ent o n u solu o ptima para o PLD Prova Para provar este teorema simplificando o formalismo ser admitido que a solu o ptima do problema primal n o degenerada hip tese de n o degener ncia i e 0 lt x lt u Assim sendo p 0 ent o como n B NJ u u e eS 4 pela condi o a que o subproblema dual tem que satisfazer ser nB c e maN u c a Portanto n B e como pela condi o anterior K K T 2 ur e A n o podem ser ambos diferentes de zero facilmente se tem o resultado pretendido 4 A rela o entre o problema primal e o respectivo dual obedece ai
88. ldades matriciais Ax boBx 4 Nx b As coordenadas do vector x ligadas com as colunas da matriz B i e x s o chamadas a E oi E P A N pa vari veis b sicas e as restantes ligadas com as colunas da matriz N i e x s o chamadas vari veis n o b sicas Uma solu o b sica poss vel tamb m dita de b sica admiss vel do problema de PL por defini o uma solu o tal que x x e Q e x o ul para todo o i Por outras palavras cada vari vel n o b sica ou tem valor igual a zero ou tem valor igual ao seu valor m ximo para a vari vel do problema a que esta associada 47 3 PROGRAMA O LINEAR PL Vamos demonstrar agora que um ponto extremo de Q uma solu o b sica poss vel do problema PL ou seja v lida a seguinte preposi o Preposi o 3 8 Um ponto extremo de Q uma solu o b sica admiss vel do problema PL Prova Seja x um ponto extremo de Q E sejam as coordenadas deste ponto x ordenadas da seguinte forma 0 lt x lt u para i l kex ef0u para i k 1 n ou seja primeiramente s o escolhidas na ordena o as vari veis que n o t m valor igual aos extremos e em seguida as que t m valor igual aos extremos As colunas de A s o reordenadas de modo a corresponder a esta ordem das coordenadas de x Vamos supor por hip tese que as primeiras k colunas de A s o linearmente dependentes e em consequ ncia vamos provar uma contradi o o que permi
89. lunas na forma triangular 4 Observe que o ltimo n e arco que escolhido pela reordena o o n raiz e o arco raiz visto que o arco raiz incidente s num n Conv m recordar que uma matriz triangular permite uma invers o r pida com menos opera es Assim determinada a matriz b sica B para um problema PLR ap s a 103 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES reordena o das linhas e colunas obtendo a forma triangular B mais facilmente a A D 1 obten o d s express es onde existe B A Preposi o 4 17 n o s mostra que a matriz b sica de um problema PLR triangular mas tamb m permite construir um algoritmo para determinar uma reordena o das linhas e das colunas que transforma a matriz b sica de um problema PLR numa matriz na forma triangular ALGORITMO 4 1 Algoritmo da transforma o para a forma triangular Passo 0 Iniciar Dada a matriz B o problema PLR com grafo G Sejam T N A uma rvore geradora para G com n de n s e raiz no n k Iniciar o ndice de itera o 1 1 Passo 1 Encontrar um ponto extremo que n o seja n com raiz Seja r k um ponto extremo de T e seja es um arco de T incidente em r Passo 2 Inserir a linha r e a coluna sem B Sei lt n 1 segue para o passo 4 Passo 3 Reduzir a rvore podar a rvore Fazer T N r A es ei lt lt i 1 voltar ao passo 1 Passo 4 Inserir o n com raiz e
90. minadas un voca visto que o grafo da rvore com raiz conexo e n o tem ciclos Os conjuntos dos arcos escolhidos para altera o de fluxo passam a ser descrito em fun o n como se segue yi t e x 0 e cj Try rro lt 03 V2 t amp j X uj e cj nro Tr gt 05 109 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES As componentes de c B N podem ainda ser determinadas de outra modo Para isso seja B a base e Tg a correspondente rvore A componente i do vector e BN determinada por c BING Seja A k NG e seja y B A k note que exe Te ent o e B NJ igual a e2y Portanto para determinar y h que resolver o sistema B y A k e 0 4 3 Como B triangular y pode ser obtido facilmente usando a arvore Tg para resolver o sistema de equa es Seja P s1 eji S2 j2 Sn Cjn Sn 1 O nico caminho em Tg ligando o n F k ao n T k Ent o pela Preposi o 4 3 SO P AG e er Ent o c B N i c y igual a 2a 0 P 4 4 Qualquer uma destas metodologias pode ser usada contudo a primeira tem sido adoptada pela maior parte dos grupos que se dedicam ao desenvolvimento de c digos para problemas lineares em rede A equa o 4 3 serve para determinar y B A k cujas coordenadas s o ent o determinadas pela sequ ncia de orienta o dos arcos no caminho P 4 5 O P se e e EP Ya a 0 caso contr rio Como O P 1 o c lculo de A e A passa a se
91. mitada Este problema uma particulariza o do programa o linear em rede na qual um n ou e de oferta ou de procura Ainda os arcos s o dirigidos dos n s de oferta para os n s de procura A Figura 2 2 ilustra um problema deste tipo em que existem tr s n s de oferta e cinco de procura 11 2 INTRODU O MATEM TICA 3 Problema de Transporte Este problema um caso especial problema de transporte com capacidade limitada no qual uj para todo j Portanto a Figura 2 2 tamb m serve para ilustra o do problema de transporte n s de procura n s de Figura 2 2 Problema de transporte 4 Problema de afecta o Este problema consiste em associar entidades uma a uma da forma mais vantajosa As entidades podem ser tarefas indiv duos m quinas etc Exemplos associar pessoas a fun es carros a pessoas fun es a m quinas Este problema um caso especial do problema de transporte no qual todos os requisitos s o iguais a 1 i e rij 1 para i 1 1 12 2 INTRODU O MATEM TICA 5 Problema do fluxo m ximo Este problema consiste em encontrar uma solu o admiss vel que envie a m xima quantidade de fluxo de um n origem para um n destino satisfazendo as restri es de capacidade dos arcos da rede Por exemplo determinar o n mero m ximo de pessoas que podem ser transportadas por uma rede a rea de transportes entre duas localiza es ou o volume m ximo de pet
92. mites 0 lt x lt u A primeira vari vel para a qual isto ocorra designaremos por vari vel de bloqueio Seja 55 3 PROGRAMA O LINEAR PL a m x a 0 lt x ad lt u a gt 0 a m x a 0 lt x B N i a d lt u a gt 0 Supondo amp lt a ent o a vari vel de bloqueio a coordenada n o b sica correspondente direc o d de e as vari veis b sicas continuam a ser b sicas Se a gt ent o adicionando a x o incremento a d for amos alguma vari vel b sica ou a ser igual ao seu valor m nimo ou a ser igual ao seu valor m ximo Tal obriga a refazer a parti o da matriz A visto que esta vari vel b sica passa a n o b sica e a vari vel n o b sica corresponde direc o d passa a b sica Obtemos assim uma nova solu o b sica poss vel Com a formula o apresentada podemos construir o algoritmo primal simplex para os problemas de programa o linear como se apresenta em seguida ALG 3 2 Algoritmo Primal Simplex Passo 0 Inicia o Seja x x uma solu o b sica poss vel associada com parti o A B N Passo 1 Avalia o Seja Y i x 0 e e c B7 N lt 0 y lioan u e e e B N gt 0 56 3 PROGRAMA O LINEAR PL Em que y o conjunto dos das vari veis n o b sicas que t m valor nulo e a respectiva coordenada do vector do custo reduzido G e BN lt 0ey o conjunto dos ndices das vari veis n o b sicas qu
93. n sendo sn Sn 1 Ejam Gja Um exemplo ilustrativo de um ciclo simples no grafo ilustrado na Figura 4 1 C 2 es 5 l l 2 2 Preposi o 4 2 Os arcos de um ciclo simples s o distintos Prova Suponhamos um ciclo com n arcos visto que a subsequ ncia s jls 2 Ej2s 0 Sn 1 jn 1s Sn um caminho os primeiros n l arcos t m de ser distintos pela Preposi o 4 1 A subsequ ncia s2 Cj 3 Cj3 Sn Cjn Sn 1 tamb m satisfaz a defini o de caminho assim os ltimos n 1 arcos s o distintos Visto que C tem n arcos a nica possibilidade de duplica o o ltimo arco e n ser igual ao primeiro e 1 por isso se imp e que tal duplica o n o se pode verificar na defini o de ciclo simples 87 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Na continua o do texto s ser utilizada o conceito de ciclo simples pelo que se escrever s ciclo ficando subentendido que se trata de ciclo simples O comprimento de um caminho ou ciclo definido pelo n mero de arcos desse caminho ou ciclo Para qualquer caminho ou ciclo P com comprimento n definimos a sequ ncia de orienta o O P dos arcos no caminho ou ciclo como sendo a sequ ncia cujas elementos s o oP 1 se es Sin P 1 se eiy Si Si Para o caminho 5 e1 1 e7 4 es 3 da Figura 4 3 O P 1 1 1 Preposi o 4 3 Seja a sequ ncia finita P s1 eja S2 Cj Sn Cn Sn 1 UM caminho
94. na rede da Figura 2 1 o problema programa o ent o descrito pela rede ilustrada na Figura 2 4 rij 03 o ci uj ts 03 Figura 2 4 Problema do caminho mais curto Na solu o ptima a unidade de fluxo ir percorrer o caminho mais curto entre os n s s e t Caso a unidade de fluxo se fraccionar em quantidades iguais que fluir o 14 2 INTRODU O MATEM TICA atrav s de mais do que um arco existir o caminhos alternativos cujo percurso igual distancia mais curta 2 3 Exemplos de modelos em programa o linear A programa o linear tem uma parte que arte e outra que ci ncia Enquanto que o processo de constru o da estrutura proveniente de enunciado de um problema real permitindo a an lise do problema real pode ser encarado como uma arte existindo v rias maneiras de proceder a arte guia na direc o da mais conveniente O desenvolvimento dos algoritmos para resolu o dos problemas de programa o linear uma ci ncia Exemplos pr ticos que ilustram a constru o de um problema de programa o linear s o apresentados em seguida 2 3 1 Produ o distribui o da pol meros A Pol meros uma empresa de pol meros europeia O director de produ o decide o n vel de produ o de cada uma das quatro f bricas na Europa O plano de produ o distribui o feito com dois meses de antecipa o O director de produ o est a trabalhar nos pedidos para o m
95. nda ao teorema da complementaridade Este teorema significa que a uma restri o n o activa do problema primal corresponde uma vari vel dual nula e a uma restri o n o activa do problema dual corresponde uma vari vel primal nula O teorema da complementaridade resulta directamente da aplica o das condi es de Karush Kuhn Tucker ao problema primal ou ao problema dual 75 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Exemplo 3 6 Escreva usando o formalismo desenvolvido o problema dual do seguinte problema primal min x sa x x 16 0 lt x lt 10 0 lt x lt 10 como c c 0 0 A 1 1 e u u 10 10 ent o ser max 167 10 u u max 167 10 u sa n l 1 u mI lt l 0 sa m u lt 1 m m 2 0 0 ou seja T mu lt 0 420 H 20 Exemplo 3 7 Determine usando a teoria da dualidade o problema dual do seguinte problema primal max 167 10 u H sa l r u 20 u T 20 HZ0 H 20 Sejam os multiplicadores de lagrange para as restri es indicados respectivamente por X X3 ent o a fun o de lagrange ser L m Hj H55X1 x 0 0 167 10 u Ho x Xo u 7 H U O subproblema dual ser max L r u 1 X X2 j A solu o do subproblema dual tem que satisfazer condi o VL 7 U X X 0 0 0 Pelo que ser 76 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES l6 x x 0 10 x 6 0 e sendo x x 0 0 20 o que equivalente
96. nha i e da coluna j da matriz A indicado por A j O vector cujas coordenadas s o os elementos da coluna j da matriz A indicado por A j Determinadas constantes inteiras indicando valores m ximos s o indicadas por letras mai sculas do alfabeto latino com uma barra por cima como por exemplo K Letras min sculas do alfabeto latino e letras do alfabeto grego a cheio s o usadas para indicar vectores O s mbolo e indica um vector cuja coordenada i igual a 1 e todas as outras coordenadas s o iguais a 0 enquanto que o s mbolo 1 indica um vector com todas as 2 INTRODU O MATEM TICA coordenadas iguais a 1 A coordenada i do vector e indicada por ci O conjunto vazio indicado por 4 Ser adoptado o ponto de vista de que os vectores pertencentes a um espa o vectorial com dimens o igual a n n o s o necessariamente nem vectores linha Ixn matrizes nem vectores coluna nx matrizes sendo considerados de modo que as dimens es fiquem compat veis com a multiplica o isto um vector tratado como um vector linha quando aparece esquerda de outro vector ou de uma matriz e como um vector coluna quando aparece direita Assim o produto interno de dois vectores a e b indicado simplesmente por ab Portanto no contexto matricial e da forma que for mais conveniente um vector ser inserido como uma linha ou como uma coluna Um Superscripts usualmente indica membros de uma classe em vez de expoentes S
97. no passo 2 da fase dual tinha ck 0 depois do passo 3 ter um lucro reduzido cx 0 Por este motivo se cs 0 e a fase primal for repetida a rvore anterior de novo obtida com a adi o do arco e e de um novo n que um ponto extremo Se cs 0 ent o e estar na condi o tem 130 5 ALGORITMO DA CONDI O consequentemente que determinar se um outro arco fora de condi o antes de voltar fase primal 5 5 Algoritmo da condi o O algoritmo da condi o pode agora ser apresentado da seguinte forma ALG 5 3 Algoritmo da Condi o Passo 0 Iniciar Seja x uma vector dos fluxos que seja uma solu o poss vel Uma solu o poss vel pode ser sempre obtida usando vari veis artificiais como se disse em 4 4 Seja n um vector de vari veis duais Passo 1 Encontrar um arco fora da condi o Seja e um arco fora da condi o Se todos os arcos est o na condi o terminar concluindo que x um ptimo Passo 2 Chamar a Fase Primal Executar o algoritmo ALG 5 1 com o arco e arco fora da condi o Se o algoritmo ALG 5 1 terminar com a conclus o de que n o existe ciclo avan ar para o passo 3 caso contr rio voltar ao passo 1 131 5 ALGORITMO DA CONDI O Passo 3 Fase Dual Executar o algoritmo ALG 5 2 com a rvore desenvolvida no passo 2 Se e est fora da condi o voltar para o passo 2 caso contr rio voltar para o passo 1 Considere
98. nte considerado nulo o potencial do n raiz No entanto observe que os potenciais s o definidos a menos de uma constante aditiva que o potencial no n raiz Portanto concluindo para uma base B dk Raras B associada rvore Tg com o n raiz k resolver em ordem a 7 o sistema q B conduz a Tm 0 Tag Top C para e pertencente a Ta O algoritmo seguinte determina as coordenadas do vector 7 usando a conclus o anterior 108 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES ALGORITMO 4 2 Para determina o as vari veis duais Passo 0 Iniciar Seja Tg N A a rvore com raiz no n k associada base B Fazer n 0 N k eNU N k Passo 1 Encontrar um arco com n para onde se dirige n o pertencente a N Seja ec A tal que p eN e d j eN Se tal arco n o existir seguir para o passo 3 Passo 2 Calcular o potencial do n para onde se dirige o arco Fazer Tpi Cj Tag Nte N U pO NY lt N fp j seguir para o passo 1 E 4 a L Passo 3 Encontrar um Arco com n de onde prov m o arco n o pertencente a N Seja e e A tal que d eN e p eN Se tal arco n o existir o algoritmo termina Passo 4 Calcular o potencial do n para onde se dirige o arco Fazer Tag Cj t Tpi Ne NUIT NY lt NO TC seguir para o passo 1 Assim considerando que a vari vel dual para o n raiz nula todas as vari veis duais ficam deter
99. nte para as demonstra es considere que a rede n o tem arcos que partem de um n para o mesmo n ditos la os nem tem arcos m ltiplos em paralelo Esta hip tese apenas uma conveni ncia de exposi o a n o condiciona os resultados que ser o apresentados nem a aplicabilidade do algoritmo visto que se h um la o no n i pode ser substitu do por dois arcos i k e k i onde k um novo n se h dois arcos orientados do n i para o n j um deles pode ser substitu do por dois arcos i k e k j onde k um novo n Por exemplo para for ar a verifica o desta considera o na rede da Figura 2 1 o arco 1 2 substitu do pelos arcos 1 5 e 5 2 e introduzido um novo n n mero 5 como ilustra a Figura 4 1 Figura 4 1 Rede que resulta da rede da Figura 2 1 mas sem arcos em paralelo 83 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES A correspondente matriz de incid ncias dos n s nos arcos passa a ser a seguinte ar os j 2 3 4 5 6 7 8 nos l l 1 1 1 l l 1 2 A l1 Il l 3 1 1 l l 4 1 1 5 Note que as colunas de A s o distintas Portanto existe uma correspond ncia biunivoca entre aos arcos da rede e as colunas da matriz A 4 1 Resultados da teoria dos grafos Este subcap tulo apresenta os resultados da teoria dos grafos que v o ser utilizados na especializa o do algoritmo primal simplex para a programa o linear em rede Considere uma grafo com I n s e
100. nto de direc es D fe e e espa o n o b sico No estudo do algoritmo primal simplex limitaremos a nossa aten o s direc es deste conjunto D com o objectivo de obter sempre uma solu o b sica poss vel O vector e uma direc o admiss vel se x lt u i e a vari vel de decis o n o imo K ini A PEETI i y r b sica x inferior ao valor m ximo admiss vel e e ser uma direc o admiss vel se x gt 0 ie a vari vel de decis o n o b sica x superior ao valor m nimo admiss vel 53 3 PROGRAMA O LINEAR PL Recorrendo derivada direccional no espa o n o b sico mostraremos como escolher uma direc o admiss vel de melhoria do valor da fun o objectivo A derivada de g x segundo v no ponto y por defini o calculada como D gly tim 80 t e y t50 t recorrendo ao gradiente a f rmula para o c lculo desta derivada direccional seguinte D g y Ve y v Assim para o problema 3 8 a 3 10 elx e B b e c B7N x portanto Ve y e e B N independente do ponto em que calculado como seria de esperar A procura de uma direc o admiss vel de entre as direc es do conjunto D para melhorar o valor da fun o objectivo ser segundo o vector e direc o admiss vel de melhoria da fun o objectivo se x lt u e e eBN lt 0 ou segundo e se x lt u e e e BN gt 0 Para s solu es b sicas poss v
101. num grafo pr prio G e seja A a matriz de incid ncia dos n s nos arcos Ent o gt 0 P AG e e 4 1 Prova Sejai 1 n Caso 1 Suponhamos eja si Si 1 ent o O P A G 1 e e7 e e m Caso 2 Suponhamos ej Si 1 si ent o Oi P AG 1 e e e e Portanto em qualquer caso O P AG e e Assim pela propriedade telesc pica da adi o 4 1 verifica se 4 Propriedade telesc pica da adi o ONPJAGn e e OAP A j e e OXPAGa e e OAP A jn e e gt P AG e e 88 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Preposi o 4 4 Seja C s1 e 1 S2 Cj Sn Cj Sn 1 UM ciclo num grafo pr prio G e seja A a matriz de incid ncias dos n s nos arcos Ent o Prova i n i n 1 N Sa Da OU AGO Di OOAG e e Pela Preposi o 4 3 So o Agj e e Ent o EO C A j e es e n ss es Como C um ciclo S1 Sn 1 logo Foro A jj 0 Corol rio 4 5 Se C s1 e S2 eo Sn jm Sn 1 um ciclo num grafo pr prio Ge A a matriz de incid ncias dos n s nos arcos ent o A 1 1 n um sistema de vectores linearmente dependente 1 el e i a ZN m OAC 1 SEEL O4 C 1 e4 e2 e4 i N e2 l 4 OMC o es es l a b Figura 4 4 Exemplo de um ciclo num grafo pr prio a Grafo pr prio b Ciclo simples C 4 es 3
102. o um subgrafo da rvore T pela Preposi o 4 6 T ac clico Por A constru o T tem menos um arco do que o n mero de n s Portanto pela Preposi o 4 6 T uma rvore 4 Estamos agora aptos a apresentar um resultado importante sobre os arcos de uma rvore e as correspondentes colunas na matriz de incid ncias dos n s nos arcos Conv m recordar que assumimos que a rede n o contem arcos m ltiplos Assim existe uma correspond ncia biun voca entre os arcos do um grafo e as colunas da matriz de incid ncias dos n s nos arcos Isto a um arco e de A corresponde uma coluna j da matriz de incid ncias dos n s nos arcos A e vice versa Preposi o 4 10 Seja A a matriz de incid ncias dos n s nos arcos para um grafo pr prio G e seja T N A um subgrafo de G que uma rvore com pelo menos dois n s Ent o tA ee AJ linearmente independente i e as colunas da matriz A associadas r pA aos arcos da rvore s o linearmente independentes 2 Diz se que o sistema de vectores A i 1 2 n linearmente independente se n o existe uma s rie aiti n 0 tal que Fa amp A 0 94 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Prova Seja m o n mero de n s da rvore T Suponhamos m 2 Ent o pela Preposi o 4 6 A cont m um arco ej atendendo a que A j eD e 0 a preposi o verifica se para m 2 Suponhamos m gt 2 Seja n o maior dos inteiros tal que pa
103. o x x X x X 2 2 3 0 0 E voltamos ao passo 1 Itera o 3 Passo 1 Avalia o 1 0 1 0 e c BIN 1 I0 1 3 0 x 0 0 1 x 1 0 1 1 1 1 1 c c B N 1 7 70 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES obtemos y b e y 4 e a uni o y UY 4 terminando o algoritmo e sendo a solu o corrente DX X Xx x 2 2 3 0 0 a ptima O quadro seguinte apresenta a evolu o do vector x durante o processo iterativo Quadro 3 2 Evolu o do vector x durante o processo iterativo itera o x X X X4 X 0 B 0 N 0 N 4 B 1 B 0 1 1 1 4 0 0 B B N N B baod 1 1 4 0 0 2 2 2 3 0 0 B N B N B pao 2 2 3 0 0 3 4 Condi es de Karush Kuhn Tucker para a programa o linear Este subcap tulo apresenta um conjunto de condi es para o problema de programa o linear conhecidas como condi es de Karush Kuhn Tucker Estas condi es s o condi es necess rias para a identifica o do ptimo mas para este problema visto que a fun o objectivo uma fun o linear e o conjunto das vari veis de decis o admiss veis convexo s o tamb m suficientes para a identifica o de uma solu o ptima Estas condi es s o as apresentadas na proposi o seguinte Preposi o 3 9 Seja x tal que Ax be 0 lt x lt u Ent o x um ptimo para o problema de programa o linear sse s se existirem vectores multiplicadores de lagran
104. o arco raiz 104 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Como exemplo de aplica o deste algoritmo considere o problema do exemplo 3 1 min x x 3x 10x sa x X X 5 X X x 0 Ro X 5 as restri es de n o negatividade s o as seguintes 0 lt x lt 4 0 lt x lt 2 0 lt x lt 4 0 lt x lt 10 0 lt x lt 1 O grafo com raiz ilustrado na Figura 4 8 Existem tr s rvores geradoras poss veis para o grafo G do exemplo 3 1 As rvores geradoras com raiz e as matrizes b sicas j na forma triangular s o ilustradas na Figura 4 9 n raiz Figura 4 8 Rede do exemplo 3 1 com raiz A representa o de rvore geradora com raiz associadas com uma matriz b sica do problema PLR torna poss vel e f cil a transforma o para a forma triangular 105 e4 a el c 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES e4 2 1 el n s 0 0 3 1 0 1 1 1 2 b e2 n s 0 1 1 0 3 1 2 d e3 el n s 1 0 0 3 1 1 01 1 0 1 1 2 D Figura 4 9 rvores geradoras com raiz para o grafo da Figura 4 8 e matriz B 106 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES 4 3 Especializa o primal simplex Considere que a matriz b sica B j est na forma triangular Conv m recordar o passo do algoritmo primal simplex que necessita da invers o da base B para saber se uma vari vel n o b sica x escolhida para uma opera o de altera
105. o d gual ao d lo o fl tad 134 5 ALGORITMO DA CONDI O caso contr rio ser diminu do o novo vector dos fluxos x X X xaJ 1 4 0 Regressar ao passo 1 do ALG 5 3 para encontrar um arco fora da condi o n2 0 2 0 Fora de e2 e1 A tai Condi o 5 T n3 1 zl 2 13 1 ni O es 83 1 At 3 O e3 OBa b Fora de Condi o a n3 1 A3 e Figura 5 3 Arvores associadas a fases do exemplo ALG 5 3 Passo 1 Encontrar um arco fora da Condi o Os lucros reduzidos s o os mesmos que foram calculados anteriormente Os n meros de condi o de cada arco s o agora x 1 0 4 gt K 3 fora da condi o x l 2 0 gt K 0 na condi o x 4 amp 3 3 gt K 0 na condi o x 0 c4 4 gt K 0 gt na condi o 4 K 3 Agora s existe o arco e fora da condi o obviamente e e passar fase primal 135 5 ALGORITMO DA CONDI O ALG 5 1 Passo 0 Iniciar Como c gt 0 ent o N F 1 1 Ar U X gt 4 3 e o conjunto dos A arcos A Passo 1 Determinar candidatos para a rvore y UY seguir para a fase dual ALG 5 2 Passo 1 Determinar os arcos incidentes na rvore Determinar y e y4 ws fe T eN F eN ec lt 0 0 e Ww te T j g N F j e N ecj gt 0 fe e Passo 2 Determinar a altera o m xima possivel b min c c3 min 4 3 3 Passo 3 Reduzir as vari veis d
106. o de fluxo a componente i correspondente do vector c c B N indicada por c c B N tem que ser calculada ver passol do ALG 3 2 Algoritmo Primal Simplex A invers o da base B necess ria para o calculo do vector c B N Seja 7 c B observe que esta denomina o est de acordo com a Preposi o 3 11 As coordenadas do vector m os Ti s s o chamados de vari veis duais ou potenciais dos n s Portanto x a solu o do sistema das equa es lineares n B c Como B triangular x pode ser obtido por substitui o de tr s para a frente resolvendo primeiro em ordem ltima componente e depois por substitui o at a primeira componente ei e4 e2 e3 a n s 1 1 1 4 1 2 1 1 4 3 1 1 115 Figura 4 10 rvore geradora com raiz 107 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES E f cil usar a rvore com raiz associada com B indicada seguidamente por Tp na obten o das componentes do vector m Como exemplo considere a rvore geradora com raiz com a correspondente base ilustrada na Figura 4 10 O sistema de equa es para a rvore geradora Tp 7 B tem a forma triangular ilustrada na Figura 4 11 Figura 4 11 Sistema de equa es x B c Obviamente que c nulo ou um valor qualquer indeterminado pelo que j se afirmou no subcap tulo anterior O sistema de equa es pode ser resolvido por substitui o de tr s para a frente come ando com 15 c geralme
107. o deste problema o director de produ o pode por abstrac o considerar que cada uma das quatro f bricas um n por onde se injecta fluxo na rede 17 2 INTRODU O MATEM TICA Clientes F bricas Arco 21 Excesso de Capacidade de Produ o Arco 28 Arco 24 Aveiro Arco 20 Figura 2 5 Produ o e distribui o na Pol meros No entanto como quer obter o plano de produ o e transporte tem que considerar que em cada fabrica existe um percurso que corresponde produ o dos pol meros Portanto este percurso cujo custo unit rio o custo de produ o da tonelada de pol mero ser descrito por um arco que liga um n que pode ser considerado como o in cio de produ o com o n que pode ser considerado como o fim de produ o da f brica A rede ser constitu da como se indica na Figura 2 5 sendo os n s n mero 1 a 5 os n s clientes as regi es que o director de produ o tem que considerar 6 a 9 os n s fim de produ o para f bricas 10 a 13 os n s de in cio de produ o para f bricas No entanto estes ltimos n s tem um significado que deriva do facto dos seus requisitos serem iguais capacidade m xima de produ o das respectivas f bricas como est indicado no Quadro 2 4 18 2 INTRODU O MATEM TICA Quadro 2 4 Requisitos dos n s Figura 2 5 N do N Requisito N do N Requisito 1 2840 8 0 2 2800
108. o sistema a gerir Estes sistemas de informa o de gest o s o obviamente de grande interesse para a viabilidade da empresa e a sua competitividade no mercado de energia el ctrica Actualmente n o se pode conceber a explora o dos recursos de forma eficiente sem o uso deste tipo de simula o computacional 157 6 C DIGO LSNNO CASCATA H DRICA 6 2 Gest o de uma cascatas h dricas no curto prazo r O estudo que apresentado aborda um aproveitamento h drico com albufeiras em cascata que um problema bem adaptado para ser tratado por programa o matem tica em redes cuja formula o do tipo max f x sa Ax r problema para a gest o da cascata no curto prazo 0 lt x lt u Onde a fun o objectivo pode ser uma fun o n o linear e os fluxos s o os volumes de gua quer em tr nsito quer armazenados nas albufeiras Seja a configura o para o problema a do seguinte aproveitamento h drico em cascata Figura 6 1 Configura o do aproveitamento h drico em cascata Tipicamente o problema da gest o racional de albufeiras em cascata num horizonte de curto prazo considera as decis es tomadas em per odos hor rios durante um horizonte 158 6 C DIGO LSNNO CASCATA H DRICA temporal de alguns dias at uma semana Portanto o horizonte de decis o do ciclo di ria at ao semanal do uso de energia el ctrica por parte dos consumidores que considerado neste problema No entanto justific v
109. oblemas pelo algoritmo do simplex Solu o x 10 6 x 0 1 4 Considere os seguintes problemas de programa o linear min X X X X min X X X X sa x X x lt 16 sa x X x lt 16 Rae Go x Ea X X X 2 1 0 lt x lt 10 0 lt x lt 10 0 lt x lt 10 0 lt x lt 10 0 lt x lt 4 0 lt x lt 4 0 lt x lt 11 0 lt x lt 11 Escrevas os problemas na forma can nica Solu o min X X X X min X X X X sa X X X x 16 sa x x x x 16 XX X x 1 X X X X _l 0 lt x lt 10 0 lt x lt 10 0 lt x lt 10 0 lt x lt 10 0 lt x lt 4 0 lt x lt 4 0 lt x lt 11 sx lt 11 0 lt x lt 20 0 lt x lt 20 0 lt x lt 22 0 lt x lt 22 80 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES 5 Considere os problemas de programa o linear anteriores resolva os problemas pelo algoritmo do simplex Solu o x 10 0 00 6 11 x 100 006 11 Observe que no primeiro problema na segunda restri o adicionado x no segundo subtra do x Como x 0 no ptimo do primeiro problema as solu es s o iguais visto que somar ou subtrair um valor nulo indiferente 6 Considere os problemas de programa o linear anteriores escreva os problemas duais respectivos Solu o Problemas na forma can nica min X X min X X sa x x x 16 sa x x x 16 XX x 1 X X x 1 0 lt x lt 10 0 lt x lt 10 0 lt x lt 10 0 lt x
110. onamos um arco artificial de I para k com custo unit rio de transporte e capacidade infinitos O fluxo neste arco ser igual a rx satisfazendo a lei de conserva o do fluxo no n k Como os custos unit rios de transporte dos ltimos arcos artificiais s o infinitos qualquer solu o sem fluxo nestes arcos ser melhor que uma solu o que contemple fluxo n o nulo neles Portanto fica assegurado que se existir um ponto ptimo o fluxo nos arcos artificiais tem que ser nulo Esta formula o corresponde ao que tradicionalmente se chama em literatura de programa o linear 115 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES m todo Big M i e m todo do grande M visto que o infinito em computa o tem que ser simulado por um n mero grande Um exemplo do m todo all artificial start apresentado na Figura 4 14 Note se que o n 5 serve apenas como um destino fict cio com uma procura nula Figura 4 14 Exemplo de all artificial start a Rede original b Rede aumentada com o n e os arcos artificiais c Arvore geradora 116 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES 4 5 Estrat gias de avalia o Um arco e pode ter uma altera o de fluxo favor vel se eeyiuy ver Passo 1 do Algoritmo 4 3 A estrat gia de avalia o selecciona entre v rios arcos dentro do conjunto yitNy gt O arco n o b sico cujo fluxo ser alterado As estrat gias usadas vai
111. produ o de energia el ctrica e altura de queda sendo obtidas as equa es seguintes 166 Albufeira 1 Albufeira 2 Albufeira 3 6 C DIGO LSNNO CASCATA H DRICA Ihora 2 hora 3 hora di Z pi 3 pi rs hi DO 2 h 3s 3 h Pi Who Pi ti Mho tM Pi ti Mho hi Lo mv ly m v hj Vo mvi ly mov h Lo F mvi ly mv Ap 2p p pa t 17 mh p imo h p t n mah h lo E mov Ly m v h La je mv lyo mv h lo m v3 ho mv Ap Xp Z p3 A tmo h P A mo h P HOM h h lo my Ly m v h Lo E mv Ly mv h lo m v Lo myi Albufeira 2 Albufeira 1 Albufeira 3 Na ltima albufeira 3 o n vel constante i e tem se m 0 Ap s substitui o obtemos os seguintes elementos pertencentes fun o objectivo hora 2 hora 3 hora A ti Imo Lo mv E mv At bno 7 ho mvi ly mov Xt Ino 7 Lo mv ly m v5 At DA M Lo mov lo mv At DA y is mv l mv Xt In 7 Es mv l mv At EM 77 o mv la ft Imo 7 lo mv Lo ts Imo 7 A mv Lo 167 Albufeira 1 Albufeira 2 Albufeira 3 6 C DIGO LSNNO CASCATA H DRICA Substituindo nestas express es os caudais de gua turbinada t descarregados s e os volumes das albufeiras v por vari veis x de acordo com a Figura 6 5 obtemos as seguintes express es Quadro 6 1 Express es para a fun o objectivo hor
112. que os algoritmos de programa o linear sejam eficientes e favor veis para a resolu o de um larga variedade de problemas envolvendo quest es de decis o em v rios dom nios Por exemplo no planeamento da distribui o e produ o de produtos no planeamento de curto prazo em aproveitamento hidroel ctricos nas decis es ligadas s pol ticas micro econ micas e macro econ micas de governa o dos pa ses na utiliza o como subrotinas para suporte de tarefas especificas em c digos de programa o n o linear Ainda s o aspectos positivos a considerar o facto da programa o linear ser uma teoria de optimiza o significativamente completa de existirem c digos para computadores podendo suportar problemas de muito grande dimens o O problema de optimizar uma fun o linear sujeita a restri es lineares teve as sua origem com os estudos de Fourier sobre sistemas lineares de inequa es em 1826 No 1 BREVE HIST RIA SOBRE A PROGRAMA O LINEAR entanto s em 1939 Kantorovich faz notar a import ncia pr tica destes problemas tendo criado um algoritmo para a sua solu o Num documento cujo objectivo era expor conceitos Kantorovich apresentou exemplos para a aplica o da programa o linear sendo a ideia fundamental de cada exemplo a obten o da maior produ o poss vel com base numa utiliza o ptima dos recursos dispon veis Um desses exemplos envolvia a distribui o de fluxos de carga distribu dos a
113. r leo numa rede de oleodutos ou de energia electricidade numa rede el ctrica Em geral s o dados dois n s de uma rede s n de oferta e t n procura Os arcos da rede t m capacidade uj paraj 1 J O problema consiste em encontrar o fluxo m ximo satisfazendo as restri es de capacidade 0 lt x lt u que pode ser enviado atrav s da rede do n s para o n t Este problema um caso especial do problema PR no qual r 0 e s um arco tem custo n o nulo Para exemplificar suponha que se pretende determinar o fluxo m ximo entre os n s 1 e 4 da rede da Figura 2 1 rij 03 o so ci ui 0 u4 03 Figura 2 3 Problema de maximiza o do fluxo entre n s 13 2 INTRODU O MATEM TICA Aumenta se a rede com um arco fict cio de retorno n mero de ordena o do arco 8 do n 4 para o n 1 sendo ug ecg 1 e sendo r 0 parai 1 4ec 0 para j 1 7 A rede para este problema ilustrada na Figura 2 3 6 Problema do caminho mais curto Este problema consiste em encontrar o caminho mais curto entre dois n s s e t de uma dada rede cujos arcos t m custos c gt 0 para j 1 J Estes custos podem identificar se com o valor da dist ncia a percorrer quando se opta pelo trajecto determinado pelo respectivo arco Este caso corresponde a fazer r 1 r l e os outros requisitos s o iguais a zero Supondo que se pretende encontrar o caminho mais curto entre os n s 1 e 3
114. r escolha o vector das coordenadas n o b sicas x x x eseja x x5 0 4 ent o x x x x eamatriz A particionada em 1 1 0 0 B 1 0 N 0 0 l1 0 sendo 1 0 0 B 0 0 l 1 1 1 o vector das coordenadas b sicas B B B B x x x x 0 1 0 Pelo que o vector x x uma solu o b sica admiss vel Caso n o fosse havia que fazer outra escolha para as coordenadas n o b sicas O algoritmo come a com a seguinte solu o corrente x x x x x 0 0 4 1 0 66 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Itera o 1 Passo 1 Avalia o Calcular o vector dos custos reduzidos 1 0 0 0 ec c B N 1 3 1 10 0 x 0 0 cede x 1 0 1 1 1 1 1 donde c e B7N 8 7 Pelo que y m e y b logo y Uy 4 sendo k 1 como k pertence a y 0 1 Passo 2 Atribui o do Passo Determinar o vector y 1 0 0 0 1 y B N 1 0 0 1 x 1 1 1 1 1 0 De onde resulta A 1 a 604 e A minfa A u Jominf 4 2 1 Passo 3 Actualiza o Teremos xN x 0 1 1 1 e x x x x 0 1 0 1 1 x 1 1 0 J I 0 0 Como A 1 eu u 2 logo A u segue se para o passo 4 67 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Passo 4 Substitui o Determinar os conjuntos y3 e y4 Wa 2 e V h Pelo que y UY 2 vem necessariamente j 2 uma vez que s h este valor se houve se v rios escolhia se um de entre eles Ent o as colunas B
115. r feito atrav s de A m x 0 e A mn UjXji O 110 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Considere a rvore geradora com raiz da Figura 4 10 O arco ex 2 4 um arco n o pertence rvore O caminho P 2 e2 3 e3 5 ea 4 tem a sequ ncia de orienta o O P 1 1 1 O ciclo formado para o c lculo das coordenadas de y ilustrado na Figura 4 12 Figura 4 12 Ciclo formado por 2 4 O algoritmo primal simplex num grafo descrito pelos passos que de seguida s o indicados ALGORITMO 4 3 M todo Primal Simplex num Grafo Passo 0 Inicializa o Seja x x uma solu o b sica poss vel sendo rvore Tp Calcular x usando o Algoritmo 4 2 Passo 1 Avalia o Seja y o conjunto dos arcos n o b sicos com fluxo igual a zero e Tro Tri Cj gt 0 i e y ej xj 0 e nro nro cj gt 0 e y2 o conjunto dos arcos n o b sicos com fluxo igual ao seu m ximo e TFG TT Cj lt 0 i e yo fe Xj Uj TFE TTG Cj lt 0 111 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Se yiUy gt 4 o algoritmo termina sendo x x um ponto ptimo caso contr rio seleccionar eke y1 e fazer 5 1 se e EY hn se e ey Passo 2 Atribui o do passo Seja P s1 j1 S2 j2 Sn Cjn Sn 1 O passo em Tp que liga F k a T k Fazer A ma Xjis 0 A wmn UjiXji 0 e A min A Ao uk Passo 3 Actuali
116. r para o passo 1 Passo 1 Determinar candidatos para a rvore Y1 Y 4 Como y U y 4 seguir para a fase dual ALG 5 2 Passo 1 Determinar os arcos incidentes na rvore Ng RI jey 0 Passo 2 Determinar a altera o m xima poss vel 4 minf 1 M 11 SE J Passo 3 Reduzir as vari veis duais T l 1 2 e m 0 1 l1 E para os potenciais vem It mo za z 0 1 2 0 tomando os lucros reduzidos os valores Ci Tp Ty 0 1 1 0 K 0 C2 Tp Tro C 1 2 1 0 K 0 C3 Tpi Tr C3 1 2 3 2 K 0 C4 Ta Tr C4 0 2 5 3 K 0 C5 Mgs Tr s Cs 0 0 0 0 C6 T p o Tre C6 0 2 M M 2 K 10 6 K 10 ji j Voltar ao passo 1 do ALG 5 1 145 5 ALGORITMO DA CONDI O ALG 5 1 Passo 1 Determinar candidatos para a rvore y fe be y p Como y U y p seguir para o passo 2 Passo 2 Juntar rvore um novo arco e Como e E Y gt Apk 4 min A u x min 4 8 4 A A N 1 2 3e A fe e Como F 6 T 6 2 N voltar para o passo 1 Passo 1 Determinar candidatos para a rvore y1 be y e Como y U Yo 4 seguir para o passo 2 Passo 2 Juntar rvore um novo arco ex e Como e E Y gt Ar A minlA x min 4 10 4 A A N 1 2 3 4Je A fe e e Como F 6 T 6 c N seguir para o passo 3 Passo 3 Calcular os Fluxos O ciclo C 4
117. r que existe um ponto extremo de Q que ptimo Preposi o 3 7 Existe um ponto extremo de Q que ptimo para o problema PL Prova Primeiro vamos provar que o dom nio das solu es poss veis Q um poliedro finito Para isso considere se o conjunto de restri es para o problema escrito na forma matricial A x b o qual pode ser reescrito na forma Ax lt b 3 1 Ax gt b 6 1 De igual modo 0 lt x lt u restri es de n o negatividade pode ser reescrito na forma x lt u 3 2 45 3 PROGRAMA O LINEAR PL De acordo com o exposto anteriormente 3 1 e 3 2 definem a intercep o de semi hiperespa os fechados sendo Q a intersec o desses semi espa os conclui se que O um politopo Ainda atendendo a 3 2 o conjunto Q limitado ficando assim provado que Q um poliedro A fun o objectivo e x linear portanto cont nua em Q Pelas preposi es anteriores 3 1a 3 2 ex limitada e toma um valor m nimo que designaremos por z num ponto x e Q Pela hip tese Q 4 e pelas preposi es 3 3 a 3 5 o conjunto Q tem um n mero finito n o nulo de v rtices que designaremos pelos elementos do conjunto x a sendo Q o inv lucro convexo desses v rtices Ent o existe um vector d e R tal que Re d x onde od ed20 i 1 11 Seja o conjunto e J i d gt 0 i e o conjunto dos ndices i para os quais d n o nulo e J Ent o x d x com bo d 1 ieJ
118. r simultaneamente atendendo a 5 3 e 5 4 e a que u gt 0 119 5 ALGORITMO DA CONDI O Considere os casos Caso 1 Para um arco j com c lt 0 por 5 2 e 5 5 gt 0 Logo 5 4 n o ser satisfeito se x 0 para o arco j 5 2 a 5 5 verificam se se A Ci u 0 e x 0 Caso 2 Para um arco j com c gt 0 por 5 2 e 5 5 u gt 0 Logo 5 3 n o ser satisfeito se x u para o arco j 5 2 a 5 5 verificam se se uj cj 0 e x u Cj Caso 3 Para um arco por 5 2 e 5 5 verificam se se u 0 visto que gt 0 e u gt 0 n o podem se verificar simultaneamente As condi es de ptimo anteriores escrevem se como Ax r 5 6 c lt 0 quando x 0 para o arco j c 0 quando0 lt xX Su 5 7 cj gt 0 quandox u Com Cj Eri Ei S Se x 7 satisfazem 5 6 e 5 7 x um ptimo para a PLR 120 5 ALGORITMO DA CONDI O 5 2 Metodologia para o algoritmo O algoritmo da condi o come a por iniciar o vector 7 vector cujas coordenadas s o as vari veis duais tamb m conhecidas por potenciais dos n s e o vector dos fluxos x satisfazendo Ax r 0O lt x lt u tal como o Algoritmo do Simplex necessita de uma solu o b sica admiss vel inicial Os fluxos podem ser obtidos de forma sistem tica pelo m todo dos arcos e n artificiais como j se disse em 4 4 Se os fluxos satisfazem 5 6 e 5 7 o algoritmo termina com a conclus o que o vector x corrente um ptimo
119. ra todos os subgrafos T N de G que s o rvores com k n s sendo 2 lt k lt n A j eje linearmente independente Pelo par grafo anterior sabemos que n gt 2 assumindo por hip tese que n lt m conduz a uma contradi o Pela defini o de n dever haver uma rvore T N com n 1 n s para a qual A j eje linearmente dependente Logo tem de existir um conjunto de constantes v eje com algum elemento n o nulo tal que XicA vj AG 0 Seja L o conjunto de pontos extremos da rvore T Pela Preposi o 5 8 L 4 e seja p um ponto qualquer de L sendo ey o arco incidente em p Seja T N A onde N p e ASA te Pela Preposi o 5 9 T uma rvore Como o n p incidente no arco ew de Apj O para todos os ge A Assim para a componente p eje V Ap j5 VwAp w Feje aV ApVywAp w 0 Como Apwe t 1 seja vy 0 Ent o Xica vj A j 0 e v eje A n o s o todos zeros Portanto A j ee A linearmente dependente Mas T uma rvore com n n s isto contradiz a defini o de n Consequentemente n m portanto todos os subgrafos de G que s o rvores com dois ou mais n s t m a propriedade dos A j ee A serem linearmente independente Preposi o 4 11 Todo o grafo conexo G N A com N tem um subgrafo que uma rvore geradora 95 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Prova Seja G conexo e seja n o n mero de n s de G Sen 1 ent o o con
120. rcos que foram substitu dos por esse arco Embora nada tenha sido dito o n n mero 14 na primeira op o ou o n n mero 10 na segunda op o pode efectivamente ser tamb m representativos de um n de armaz m i e de facto se o director de produ o n o t m a liberdade de definir o n vel de produ o de cada f brica visto que ambas t m que produzir a capacidade m xima ent o a produ o n o requerida pelos clientes dirigida para um armaz m Quadro 2 6 Requisitos dos n s Figura 2 6 N do N Requisito N do N Requisito 1 2840 6 4000 2 2800 7 4500 3 2600 8 2700 4 2820 9 3000 5 2750 10 390 21 2 INTRODU O MATEM TICA Quadro 2 7 Especifica es dos arcos Figura 2 6 N do N N Custo Capac N do N N Custo Capac Arco De Para Unit Arco Arco De Para Unit Arco 1 6 1 2900 0 13 8 3 1800 1000 2 6 2 2700 2000 14 8 4 1800 1000 3 6 3 2400 2000 15 8 5 2000 300 4 6 4 2300 2000 16 9 1 0 0 5 6 5 2500 500 17 9 2 2100 1000 6 7 1 2200 3000 18 9 3 2100 1000 7 7 2 2400 2000 19 9 4 2000 1000 8 7 3 2500 1000 20 9 5 1800 2000 9 7 4 2900 200 21 6 10 0 00 10 7 5 0 0 22 7 10 0 00 11 8 1 2100 1000 23 8 10 0 o0 12 8 2 1800 2000 24 9 10 0 00 2 3 2 Problema das dietas Os alimentos 1 1 m com custo unit
121. rtencente a R normal ao hiperplano xe R um ponto do espa o e w um escalar Desenvolvendo d x w tem se dx d x d xX W pelo que w est relacionado com a distancia do hiperplano origem Associados com a defini o de um hiperplano H d w existem dois conjuntos denominados semi hiperespa os fechados definidos por H d w x ixeR dx lt w semi hiperespa o fechado inferior e Hy a w x ixeR dx gt w semi hiperespa o fechado superior Um politopo por defini o a intersec o de um n mero finito de semi espa os fechados E um poliedro por defini o um politopo limitado Esta defini o merece uma observa o i e n o concordante o seu uso alguns definem estes dois conceitos 43 3 PROGRAMA O LINEAR PL ao contr rio do que se fez aqui levantando inconvenientes e obrigando a esclarece o que se entende pelos conceitos no texto Um ponto extremo de um politopo designa se v rtice Uma aresta um segmento de recta fechado que limita um politopo Estes conceitos s o utilizados para enunciar as seguintes preposi es sobre poliedros e politopos Preposi o 3 3 O n mero de v rtices e arestas de um poliedro finito Preposi o 3 4 O n mero de v rtices de um poliedro n o vazio diferente de zero Preposi o 3 5 O inv lucro convexo dos v rtices de um politopo n o vazio o politopo Preposi o 3 6 Num poliedro convexo fechado qu
122. s vel Prova Se existe uma solu o poss vel ent o o poliedro Q 4 Logo pela preposi o 3 7 existe um ponto extremo de Q que um ponto ptimo para o problema PL Pela preposi o 3 8 um ponto extremo uma solu o b sica poss vel 4 A preposi o 3 9 conhecida como teorema fundamental da programa o linear A preposi o 3 9 permite limitar o estudo para a escolha da solu o ptima do problema PL s solu es b sicas poss veis visto que pela preposi o 3 7 uma delas ptima O n mero m ximo de bases poss veis para um problema com m restri es de igualdade linearmente independentes e n vari veis n o superior a nj n m m n m 49 3 PROGRAMA O LINEAR PL Com cada base est associado um n mero de solu es b sicas nem todas necessariamente admiss veis igual a m Portanto como sabemos que as solu es b sicas poss veis s o os pontos extremos do politopo Q e s o em n mero finito resulta que se soubermos determinar as solu es b sicas poss veis podemos por for a bruta encontrar a ptima For a bruta aqui significa determinar todos os pontos extremos de Q o que apresenta uma inefic cia consider vel Posteriormente escolhendo o ponto para o qual a fun o objectivo tem o menor valor fica identificado o ponto ptimo O m todo do simplex faz melhor vai progredir de forma racional entre pontos extremos de Q at concluir que encontrou o ponto para o qual a
123. s e as cinco regi es de venda s o indicados no Quadro 2 3 16 2 INTRODU O MATEM TICA Por exemplo o custo de produ o de uma tonelada de pol mero na f brica de Aveiro de 1700 o custo transporte de uma tonelada de pol mero fabricado em Aveiro para ser vendido na regi o 3 de 400 Ent o o custo total de produ o e transporte de uma tonelada de pol mero de Aveiro para ser distribu do na regi o 3 de 1700 400 2100 Quadro 2 3 Custo e capacidade de transporte para Julho F bricas Regi o de Dresden Lille Mil o Aveiro Vendas Custo Capac Custo Capac Custo Capac Custo Capac Ton Ton Ton Ton 1 800 0 200 3000 500 1000 0 0 2 600 2000 400 2000 200 2000 400 1000 3 300 2000 500 1000 200 1000 400 1000 4 200 2000 900 200 200 1000 300 1000 5 400 500 0 0 400 300 100 2000 No Quadro 2 3 os valores nulos correspondem a situa o a onde n o possivel meios de transporte para o m s de Julho sempre que o m ximo fluxo de um arco seja nulo o custo unit rio desse arco pode tomar qualquer valor que n o vai influenciar a decis o O problema do director de produ o fazer a programa o da produ o e da distribui o de cada uma das quatro f bricas para as regi es de procura dos pol meros de modo a que a soma do custo de produ o mais transporte seja m nima Para a resolu
124. s extremos Prova Seja T N A uma rvore com o n mero de n s m gt 2 Qualquer n de T incidente em pelo menos um arco sen o T n o seria conexo Assim o grau de cada n pelo menos 1 Pela Preposi o 4 6 T tem m 1 arcos Assumindo que T tem menos de dois pontos extremos resultam as contradi es Caso 1 Admita que T n o tem pontos extremos Ent o para cada ieN D 1 gt 2 Assim XienD 1 gt 2m gt 2 m 1 o que contradiz a Preposi o 4 7 Caso 2 Admita que T tem s um ponto extremo Seja j esse ponto extremo portanto D j 1 e para cada um dos restantes n s ieN j D 1 gt 2 Ent o o DienD i DO Zien DCG gt 1 2 m 1 2 m 1 o que contradiz a Preposi o 4 7 Portanto T tem pelo menos dois pontos extremos 4 A segunda rvore mostrada na Figura 4 5 c tem dois pontos extremos respectivamente No entanto uma rvore pode ter mais do que dois pontos extremos Por exemplo a primeira rvore mostrada na Figura 4 5 c tem tr s pontos extremos f cil concluir que retirando um arco e um ponto extremo a uma rvore resulta um subgrafo que tamb m uma rvore Portanto v lida a seguinte preposi o 93 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Preposi o 4 9 Seja T N A uma rvore com o n mero de n s m gt 2 Seja i um ponto extremo de T e seja e o arco incidente no n i de T Se N N fi e A fe ent o T N uma rvore Prova Com
125. seguinte endere o http www fp mes anl gov otc Guide SoftwareGuide Blurbs Isnno html o software pode ser obtido em ftp ftp bilkent edu tr pub IEOR Opt Network LSNNO uma rotina para resolver problemas de optimiza o n o linear com restri es lineares em rede desenvolvida em Standart ANSI Fortran Para utilizar este c digo LSNNO necess rio alterar em conformidade com os dados do problema as seguintes sub rotinas que est o dentro do pacote fornecido pelo autor exmain f elfnct f elpr f els f rhs f xlower f xupper f range f O manual do utilizador para este c digo anexado no fim deste do cap tulo sendo conveniente uma primeira leitura do manual LSNNO A Fortran Subroutine for Large Scale Nonlinear Network Optimization Problems User s Guide antes da apresenta o que se segue do problema Para compreender a introdu o dos dados neste c digo considere se apenas tr s per odos no horizonte temporal A rede para a cascata h drico ent o a apresentada na figura seguinte 165 6 C DIGO LSNNO CASCATA H DRICA gt gt gt h y v y v y gt gt gt y y v y v y gt gt gt v v v v v v N raiz Mar gt Fim de Cascata Figura 6 5 Rede para o problema com tr s periodos no horizonte As express es matem ticas que definem a fun o objectivo para as diferentes horas de funcionamento e para as tr s albufeiras s o obtidas usando as express es do lucro
126. specificamente para o problema PLR Alguns estudos computacionais t m sido efectuadas com o objectivo de comparar o desempenho do Algoritmo Simplex para problemas em rede com o do Algoritmo da Condi o mas ainda se mant m d vidas sobre qual dos algoritmos superior 118 5 ALGORITMO DA CONDI O 5 1 Condi es de ptimo Este subcap tulo apresenta um conjunto de condi es permitem terminar o algoritmo da condi o com a conclus o de que o ptimo foi identificado Estas condi es s o uma especializa o das condi es de Karush Kuhn Tucker apresentadas no cap tulo 3 4 Considere N A o grafo associada ao problema PLR as condi es de Karush Kuhn Tucker para o problema podem ser apresentadas pelo seguinte sistema de Karush Kuhn Tucker Ax r 0 lt x lt u 5 1 Te Tr C M A para todo 5 2 x u u 0 para todo e A 5 3 x j 0 para todo ej A 5 4 e 4 20 20 para todo e A 5 5 Caso seja obtido um conjunto de vectores x m u que satisfa am as condi es 5 1 a 5 5 ent o x ptimo para o problema PLR visto que este problema um problema de programa o matem tica convexo A Cj Tyi Tr associado o nome de lucro reduzido o seu sim trico o custo reduzido Os vectores u e podem ser eliminados do sistema de Karush Kuhn Tucker acima apresentado introduzido em sua substitui o o lucro reduzido visto que gt 0 e gt 0 n o podem se verifica
127. sso 1 Encontrar um arco fora da Condi o De acordo com os novos fluxos e os ltimos lucros reduzidos os n meros de condi o s o os seguintes x 8 c1 8 gt K 0 na condi o x 4 amp 2 2 gt K 0 gt na condi o x 4 amp 3 0 gt K 0 gt na condi o AE EE gt K 0 gt na condi o x 2 cs 0 gt K 0 gt na condi o X 2 ce M 4 K 25 fora da condi o Ar 2 Arco e est fora da condi o seguir para a fase primal ALG 5 1 Passo 0 Iniciar A Como ce lt 0 ent o N T 6 3 Aro A X 2 e o conjunto dos arcos A A 0 Passo 1 Determinar candidatos para a rvore W fes ey 4 como y UY amp seguir para o passo 2 Passo 2 Juntar rvore um novo arco e Como e E Y gt Apk A E min A u x min 2 1 1 A N 12 3 e A fe Como F 6 T 6 q N voltar para o passo 1 Passo 1 Determinar candidatos para a rvore Y1 Y b como y Uw 4 seguir para a fase dual 150 5 ALGORITMO DA CONDI O ALG 5 2 Passo 1 Determinar os arcos incidentes na rvore Va Ou eje y Passo 2 Determinar a altera o m xima poss vel b min 1 M 4 1 i Passo 3 Reduzir as vari veis duais m 4 1 5 E para os potenciais vem 7 np z m 0 1 5 O tomando os lucros reduzidos os valores Ci npa Tra 6 0 1 1 0 K 0 C2 Tp Tro ZC
128. sssesssesssooss 50 3 4 Condi es de Karush Kuhn Tucker para a programa o linear 71 3 5 Teoria da dualidade ssisssisssssseissssissossssssoossssssorsssosooosi sssinisss ontos stesse onise o sesoses aes 74 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES cesese 83 4 1 Resultados da teoria dos grafos ssesssesssesssecssoossooesoossssesssecssoossoossosssssesssesssooes 84 4 2 Caracteriza o de uma rede sssecccccsesssscccocececsssscsocececeesscoccececeessossccocceessssesosecee 97 4 3 Especializa o primal simplex ssesssesssesssocssoossoosssseessesssoossoossosssssesssesssoossoossos 107 4 4 Solu o b sica poss vel inicial ssessseossooesoossoosesssesssesssoossoosssosssoesssesssoossooseos 115 4 5 Estrat gias de avalia Os ssssssssssscssssesssssossssssssossossssssssssssossossoo ssssssssos sos eos sssess 117 5 ALGORITMO DA CONDI O PARA A PROGRAMA O EM REDES 118 5 1 Condi es de ptimo seeessoessoesssesssecssoessoossosssssesssesssoossoosssssessesssoessoossssssssssssee 119 5 2 Metodologia para o algoritmo sesesoosssossssesssesssesesoossoossosssssesssocssoossossssossssee 121 5 3 Fase prial sssssisnsesssssssscoieor eseese sesso usssa sasos iso ris eraoo assita es rossore ssis riiseg trii 123 SF il EITO E 1 EAEE E E EEA 127 5 5 Algoritmo da condi o ssoessoesssessseessocssoosssossssesssecssoossoossssssssesssocssoossssssssssssee 131 5 6 E
129. te concluir que essas colunas formam um sistema de vectores linearmente independentes Atendendo hip tese existem escalares nem todos nulos tal que gt A i 0 i 1 Seja 0 E JU xi o miny p e q min Ixisk A 1 lt i lt k Seleccionando e tal que O lt e lt min o a Ent o O lt x teA lt u para 1 lt i lt k 3 3 Seja uo vector n dimensional dado por AA 0 0 e seja X X EM e x x eu por 3 3 0 lt x lt u e 0 lt x lt u 48 3 PROGRAMA O LINEAR PL Mais ainda devido hip tese de depend ncia linear e ao facto de u 0 para i2k 1 Aps u A i 0 Ent o Ax Ax b e Ax Ax b Como u 0 x ex s o solu es poss veis sendo diferentes entre si e diferentes de x 1 1 e a E como x a Bo os tal contradiz a hip tese de que x um ponto extremo e prova que as primeiras k colunas de A n o podem ser linearmente dependentes Ainda como m a caracter stica da matriz A e sendo k lt m ent o B constitu do pelas primeiras k colunas de A e pelas m k colunas de A que constituem um sistema de m colunas linearmente independentes Esta selec o sempre poss vel visto que a caracter stica de A igual a m por hip tese 4 Preposi o 3 9 Dado um problema de PL se existe uma solu o poss vel ent o existe uma solu o b sica poss vel Se existe uma solu o ptima poss vel ent o existe uma solu o ptima b sica pos
130. to hidroel ctrico ea reser 1 reser 2 reser 3 v 9 9 13 5 26 4 v 7 9 10 8 21 1 vf 7 9 10 8 22 1 V 4 5 10 mw 121 03 164 14 181 09 t hm 1 404 1 188 1 512 ie a a ao Ra l 1 0 0 0 0 0 14 8 2 0 0 0 0 0 0 168 3 0 0 0 0 0 0 15 8 Os quadros que cont m os requisitos dos n s e especifica o dos arcos s o respectivamente o Quadro 2 8 e o Quadro 2 9 seguidamente indicados 28 2 INTRODU O MATEM TICA Quadro 2 8 Requisitos dos n s Figura 2 9 N do N Requisito N do N Requisito 1 8 9 6 0 0 2 10 8 7 0 0 3 21 1 8 0 0 4 0 0 9 0 0 5 0 0 10 40 8 a pato 9 N X Lucro ERAS n Oea 5 N k Lucro Capas Rs De Para Unit Aca De Para Unit 1 1 2 0 4 0 9 9 14 5 2758 0 0 1 188 2 2 3 0 4 0 9 9 15 6 9 2593 0 0 1 512 3 3 10 0 4 0 9 9 16 7 10 2680 0 0 1 404 4 4 5 0 5 0 13 5 17 8 10 3042 0 0 1 188 5 5 6 0 5 0 13 5 18 9 10 2861 0 0 1 512 6 6 10 0 5 0 13 5 19 1 4 0 0 0 7 7 8 O 10 0 26 4 20 2 3 0 0 0 8 9 0 10 0 26 4 21 3 6 0 0 0 9 9 10 0 10 0 26 4 22 4 7 0 0 0 10 l 4 1791 0 0 1 404 23 5 8 0 0 0 11 2 3 2033 0 0 1 188 24 6 9 0 0 0 12 3 6 1912 0 0 1 512 25 7 10 0 0 0 13 4 7 2429 0 0 1 404 26 8 10 0 0 0 27 9 10 0 0 0
131. trav s de ve culos de transporte usando diferentes rotas em redes rodovi rias de forma a satisfazer os requisitos e as restri es de capacidade das rotas minimizando o consumo de combust vel Infelizmente durante v rios anos o trabalho de Kantorovich n o s foi insuficientemente conhecido na Europa de Leste mas tamb m foi totalmente desconhecido na Europa Ocidental Este amplo trabalho que aborta a discuss o do fluxo de tr fego ptimo na antiga URSS foi efectuado por Kantorovich e Gavurin O conhecimento sobre este trabalho chegou s ao ocidente depois de 1950 O problema de optimizar uma fun o linear sujeita a restri es lineares tem o seu auge com George Dantzig na d cada de 1940 consultor de matem tica do US Air Force Comptroller e com o pr mio Nobel da Economia George Stigler que formulou o problema das dietas como um problema de mistura de componentes Dantzig n o s formula o problema de programa o linear mas tamb m cria o Algoritmo do Simplex para a sua solu o em 1947 Ainda em 1947 Koopmans mostra que a programa o linear um modelo apropriado para a an lise da teoria econ mica cl ssica Entretanto nos EUA Frank L Hitchcock apresentou o que hoje a formula o base do problema de transporte Independentemente o professor Koopmans formulou o mesmo problema em liga o com o seu trabalho efectuado na Combined Shipping Adjustement Board Por isso o problema de transporte referido n
132. trica na central 6 4 Fun o objectivo A fun o objectivo que mede o m rito das decis es tomadas a soma dos lucros obtidos na explora o das centrais hidroel ctricas sendo a express o do lucro para uma central i dada por k pk 6 1 177i lucro ip h em que o pre o unit rio da energia el ctrica para a albufeira i no per odo k No que respeita produ o de energia el ctrica p h t esta depende n o s do caudal de gua turbinada como tamb m da altura de queda til existente entre as duas albufeiras de montante e de jusante A figura seguinte representa algumas curvas que s o aproxima es lineares das curvas t picas para p h t Figura 6 3 Aproxima o linear das curvas de p h t 162 6 C DIGO LSNNO CASCATA H DRICA Assim resulta que s o consideradas as express es do tipo seguinte para a determina o da produ o pi ti Mio n hi i l 2 3 6 2 Nioo N ER Considerando todos os aproveitamentos h dricos ou sejam todas as tr s albufeiras obtemos a seguinte fun o objectivo 2 Opi A5p3 45p3 6 3 caso o valor unit rio da energia el ctrica nas centrais produtoras seja o mesmo a fun o objectivo a seguinte n k k k k EA pi p Ps k 1 Na equa o 6 2 a produ o p ser relacionada com o caudal de gua turbinada t e a altura de queda h pela seguinte rela o pi z ti Mio n hj onde o valor de h depende dos n veis rel
133. u u O problema PL ser escrito como se segue min ePx elx 3 4 Bx Nx b 3 5 0 lt x lt u 3 6 0 lt x lt u 3 7 E E B Nesta forma o problema PL permite interpretar que cada coordenada do vector c um i S er po B coeficiente de custo associado respectiva vari vel b sica coordenada do vector x e N z a que cada coordenada do vector c um coeficiente de custo associado respectiva ps N vari vel n o b sica coordenada do vector x Como B por hip tese um matriz n o singular por 3 5 resulta x B b Nx 52 3 PROGRAMA O LINEAR PL Substituindo este resultado em 3 4 e 3 6 obtemos o seguinte problema equivalente min eB b e c B N x 3 8 sa 0 lt B b B Nx lt u 3 9 0 lt x lt u 3 10 Nesta forma houve no problema PL uma redu o do n mero de vari veis visto que nesta forma as vari veis de decis o s o s as n o b sicas O vector dos coeficientes das vari veis n o b sicas c c B N dito de vector dos custos reduzidos Hip tese Assumimos para simplificar o estudo que 0 lt B b B Nx lt u Tal corresponde a assumir o que frequentemente se designa por hip tese da n o degener ncia corresponde a afirmar que as coordenadas b sicas n o se encontram com os valores limites como tem que acontecer com as coordenadas n o b sicas 1 2 e 2 no n m Consideremos o conju
134. uais A t 7 0 5 3 2 on 1 o nico pertencente ao conjunto N As novas vari veis duais s o n n m 2 0 1 E os lucros reduzidos v m Ci Tr Tr 1 Q 2 0 1 1 c2 Ml Z Mr 2 O 0 1 1 cs Tr 3 Tr 3 C 2 1 3 C4 Tra Mra T C4 2 1 10 7 Como e est fora da condi o voltar ao passo O do ALG 5 1 fase primal 136 5 ALGORITMO DA CONDI O ALG 5 1 Passo 0 Iniciar N fl A 4 1 Ao Passo 1 Determinar candidatos para a rvore yi y 3 como y Uy O seguir para o passo 2 Passo 2 Juntar rvore um novo arco WUw te s logo e e e EY gt Ars A mintA 6 x mint3 4 3 N 1 u 3 1 3 e A e esta rvore apresentada na Figura 5 3b Como A F 1 T 1 q N seguir para o passo 1 Passo 1 Determinar candidatos para a rvore yi e Y 4 como y Uw amp seguir para o passo 2 Passo 2 Juntar rvore um novo arco e 6 6ew gt A minfl 3 J 1 N NUSF TO 11 3 U 2 3 01 2 3 6eA AU fe fe A esta rvore apresentada na Figura 5 3c Como fF 1 T Cc N seguir para o passo 3 Passo 3 O ciclo 2 3 e 1 e 2 como c gt 0 os fluxos ser o alterados de Art Ap 1 se o sentido do arco igual ao do ciclo o fluxo ser aumentado caso contr rio ser diminu do e tomar o os valores x Xy X x4 2 2 o 0 Realizado o ciclo regressar ao passo 1 do ALG 5 3 verificar
135. vari vel tem o ndice igual ao do elemento somado com o produto entre o n mero de per odos de funcionamento e o n mero de albufeiras do sistema h drico em estudo Al m da fun o objectivo conveniente introduzir no c digo o gradiente desta fun o Ainda a matriz hessiana da fun o objectivo pode ser introduzida ou caso contr rio ser estimada pelo c digo sendo dadas op es ao utilizador para a metodologia de estima o que sugerimos seja testado pelo leitor o uso dessa estimativa com o fim de tira conclus es As formulas para o c lculo do gradiente e da matriz hessiana s o 170 6 C DIGO LSNNO CASCATA H DRICA seguidamente indicados a t tulo de exemplo para o primeiro elemento e para o ltimo do problema em estudo A express o do primeiro elemento da fun o objectivo dada por elm AX mo Lo mx la M xX Gradiente do primeiro elemento da fun o objectivo VELM 2 elm elm O elm Xo OX 0X Sendo as derivadas parciais 0 elm A nio n lio m x l m x OX 1 aa A XoNim OX ji i Ax onm 0X A matriz hessiana do primeiro elemento da fun o objectivo elm elm delm Ox Kox Oxp x elm elm delm HELM xx Ox amp elm elm 3 elm 0Xx40X io Ox 0X ox Os elementos da matriz hessiana n o nulos s o dados por 2 l 2 o elm a 0 elm ns X 10X0 OX 40X io 171 6 C DIGO LSNNO CASCATA H DRICA Para o
136. x Este segmento de recta indicado por x x Um ponto xe X um ponto extremo do conjunto convexo X se n o pertence a qualquer segmento de recta que una dois outros pontos distintos quaisquer de X ou dito de outra maneira um ponto extremo de X n o pode ser obtido pela combina o convexa de quaisquer outros dois pontos distintos de X Um conjunto XcR um conjunto convexo se para quaisquer pontos x e x pertencentes a X o conjunto dos pontos do segmento de recta fechado de extremos x e x um subconjunto de X 39 3 PROGRAMA O LINEAR PL O termo fechado semi recta fechada segmento de recta fechado significa que os pontos extremos tamb m pertencem ao conjunto dos pontos Se nas defini es de A expressas acima substituirmos o s mbolo lt por lt usa se a designa o de abertos semi recta aberta segmento de recta aberto ou seja os pontos extremos n o pertencem ao conjunto de pontos considerados Dado um ponto x R e um escalar e gt 0 o conjunto dos pontos xe R cuja dist ncia ao ponto x inferior a s e que se indica da forma B x e xeR x x lt e denominado bola aberta com centro x eraio Um ponto x dito interno ao conjunto X c R se existir uma bola aberta de centro em x e raio e inclu da em X isto se existir e gt O tal que B x c X Um ponto x dito externo ao conjunto X c R se existir uma bola aberta de centro em x e raio s tal que B
137. x Ay Kx lt K para todo o arco e e A Km lt K para pelo menos um arco e Por outras palavras tentar encontrar um ciclo de modo que um aumento do fluxo nesse ciclo n o aumente o n mero de condi es de nenhum arco e diminua o n mero de condi es de pelo menos um No quadro 5 3 s o apresentadas as altera es de fluxo poss veis para os arcos num ciclo Quadro 5 3 Altera es de fluxo poss veis para o arco e s lt C C P z lt j C 0 Al A N nhuma Altera o Admitida A o is aa p B re o Nenhuma Altera o Admitida Aumentar de uj xj Aumentar de uj xj O m todo usado na fase primal do algoritmo a seguinte Dado qualquer arco fora de condi o e encontrar um ciclo que inclua e e permita de acordo com o Quadro 5 3 um aumento de fluxo no ciclo Suponha que para o arco seleccionado fora de condi o 125 5 ALGORITMO DA CONDI O cs gt 0 O m todo para verificar se existe um ciclo que inclua e e permita de acordo com o Quadro 5 3 um aumento de fluxo no ciclo consiste na obten o de uma rvore do grafo designada por T e com o n raiz no n F s Esta rvore ser de modo que se o n ie T um aumento de fluxo ser apenas permitido no nico caminho que na rvore T ligue o n i ao n raiz Se T s e T o ciclo o nico caminho na rvore T vai do n T s ao n F s fechando pelo e usando este caminho e retornando se a T s atrav s
138. xemplo de iniciar o algoritmo da condi o por n e arcos artificiais 142 5 7 Converg ncia do Algoritmo da Condi o ssescoesessoesooesosssesoossocssessoseoessessose 155 6 C DIGO LSNNO CASCATA H DRICA sessssssesesseesssecesssecesssecossecoossecoosseessssees 156 6 1 Simula o da Gest o de cascatas h dricas ssscsececssssescocceceessssocoocceesessosocecee 156 6 2 Gest o de uma cascatas h dricas no curto prazo cccc secs rerssrrerese 158 6 3 Limites para as VARI VEIS uaasse pac seriretasiierepi sein esnio os rostnten cretino pera taco nto cenapes dca 159 6 4 Fun o 0DJCCNVO ga sciecisascadia espuenicaneiteteiectentobitndato onecnino soies ssec soss seess soosse 162 6 5 Equa es de balan o e seeessoesssesssessseessoossoossoossssesssecssoossoossssessseessocssoossssssssssssee 164 6 6 Constru o dos ficheiros para a aplica o LSNNO sessssesssesssesssoossoossssssssssssee 164 6 7 Dados para um caso exemplo e ssesssesssoossoossosesssesssosesoossoossossesoesssocssoossossssssessee 173 6 8 Manual do utilizador do LSNNO ccecereeressesererecorersesssssserecesersessssssssoos 174 1 BREVE HIST RIA SOBRE A PROGRAMA O LINEAR I BREVE HIST RIA SOBRE A PROGRAMA O LINEAR A programa o linear surgiu como um dos mais importantes ramos da programa o matem tica com uma vasta aplica o pr tica Inova es da ltima metade do s culo passado fizeram com
139. za o dos Fluxos Fazer x xx A 6 Para todos os arcos e pertencentes ao caminho P fazer xy Xki A O P Se A ux seguir para o passo 1 Passo 4 Actualiza o da rvore e das Vari veis Duais Seja y3 ej x 0 onde O P 8 e y4 ej x Uj onde O P 63 Seleccionar um qualquer emeysu ya Substitui ex por em em Tp e actualizar as vari veis duais pelo Algoritmo 4 2 seguir para o passo 1 Como exemplo de aplica o deste algoritmo considere de novo o Exemplo 3 1 que ser agora resolvido usando o Algoritmo 4 3 Passo 0 Inicializa o Seja x x2 x3 x4 xs J 0 0 4 1 0 sendo x x x4 xsje x x2 x3 Passo 1 Avalia o na Itera o 1 Para e2 T2 T3 c2 0 9 1 8 gt aew Para e3 T1 T3 c3 1 9 3 7 gt egy e egy Assim y e2 W2 0 logo ex e2e 1 112 4 M TODO SIMPLEX PARA PROGRAMA O EM REDES Passo 2 Atribui o do Passo A min x4 00 min 1 00 1 Ao min u x1 0 min 4 0 001 4 A min A A2 us min 1 4 2 1 Passo 3 Actualiza o dos Fluxos x2 0 I 1 1 x1 0 1 D1 1 x4 1 1 1 1 0 x u 2 a b d e Figura 4 13 rvores e ciclos para a resolu o do Exemplo 3 1 a rvore para a itera o 1 b Ciclo para a itera o 1 c rvore para a itera o 2 d Ciclo para a itera o 2 e rvore para a itera o 3 113 4
140. za o dos c digos programa o linear em rede acrescentou vantagens no desempenho comparativo dos procedimentos para a resolu o de problemas de programa o linear em rede O primeiro problema de tamanho consider vel resolvido pelo Algoritmo do Simplex foi o das dietas de Stigler com nove equa es e setenta e sete vari veis n o negativas gastando 120 Horas Homem nas calculadoras de secret ria existentes na altura e menos de um segundo nos actuais computadores pessoais Em 1975 a Academia Real de Ci ncia atribuiu o pr mio Nobel da Ci ncia em Economia a Kantorovich e Koopmans pelas a suas contribui es para a teoria da aloca o de recursos considerando a contribui o de Dantzig mais no mbito matem tico n o havendo pr mio para o ramo cient fico da matem tica n o atribuiu pr mio a Dantizg No entanto Dantizg permanecer para a hist ria da constru o da programa o linear como um dos arquitectos fundamentais 2 INTRODU O MATEM TICA 2 INTRODU O MATEM TICA 2 1 Nota es e conven es Ao longo deste texto as matrizes s o indicadas por letras mai sculas do alfabeto latino a cheio Os grafos ou conjuntos de n s e arcos dos grafos s o indicados por letras mai sculas do alfabeto latino O s mbolo I indica a matriz identidade com dimens o apropriada para o contexto das opera es matriciais onde est inserida Uma matriz com todos os elementos nulos indicada por 0 O elemento da li

Índice 1-BREVE HISTÓRIA SOBRE A PROGRAMAÇÃO

Contents

Download Pdf Manuals

Related Search

Related Contents

&Iacute;ndice 1-BREVE HIST&Oacute;RIA SOBRE A PROGRAMA&Ccedil;&Atilde;O

Contents

Download Pdf Manuals

Related Search

Related Contents

Índice 1-BREVE HISTÓRIA SOBRE A PROGRAMAÇÃO