Slide - Teorema de Weierstrass - Pesquisa Operacional 2 - 2023-2

25/10/2023 1 Pesquisa Operacional II Pesquisa Operacional II 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 1 Pesquisa Operacional II Problema do Fluxo de Custo Mínimo 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 2 1 2 25/10/2023 2 Pesquisa Operacional II • Um novo produto está sendo produzido em duas fábricas e deve ser enviado para dois armazéns. • A rede de distribuição disponível para o transporte deste produto é mostrada na figura a seguir, onde F1 e F2 são fábricas, W1 e W2 são armazéns e DC é um centro de distribuição. • Dados: • Produção • Demanda • Custos unitários e capacidades das rotas Quanto enviar por cada rota de com o objetivo é minimizar o custo total do frete? 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 3 Pesquisa Operacional II Problema do Fluxo de Custo Mínimo • Abrange uma grande gama de aplicações. • Formulado como um problema de Programação Linear • Pode ser resolvido de forma eficiente pelo Método Simplex de Redes 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 4 3 4 25/10/2023 3 Pesquisa Operacional II • Rede direcionada e conectada. • Pelo menos um nó de suprimento e um nó de demanda. • Nós restantes são de chamados de nós de transbordo. • O fluxo através de um arco é permitido apenas na direção indicada • O fluxo máximo através de um arco é dado pela sua capacidade • Um par de arcos em direções opostas indica a possibilidade de fluxo nas duas direções • A rede possui arcos com capacidade suficiente para que todo o fluxo gerado nos nós de suprimento atinja todos os nós de demanda. • O custo do fluxo através de cada arco é proporcional ao valor desse fluxo. O custo unitário do fluxo nos arcos é conhecido. • Objetivo: minimizar o custo total de envio da oferta disponível através da rede para atender à demanda. 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 5 Pesquisa Operacional II Problema do fluxo de custo mínimo Tipo de Aplicação Nós de Suprimentos Nós de Transbordo Nós de Demanda 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 6 5 6 50 unidades / Fi \ US$ 900/unidade = WI )30 unidades produzidas \ A ._/ necessarias ae lw i on™ ¢ Variaveis de decisdo: N%, / \ ° xij = fluxo doarcoi > j NG. | \ Nw | \ XN | | * Temos também: Ss __sUSS 200/ USS 300 * cij = custo unitario no arcoi > j US$ 200/unidade | 10 unidades no méximo | DC | unidade unidade IA * uj; = capacidade do arcoi > j ey BG, ° b; = fluxo liquido do néi \A yY Wy \ | SY eo, — \ S/ tein, \ w/ o,N@ \ | se % Nae \ / A MN \ / / ty / L. # I, la Se e pb: >ié 5 j di vatiion pes 7 sya ) 80 mnidades b; > 0 > iéumné de suprimento produzidas \._/ \ / necessarias se : = * bj <0 >iéumné de demanda ¢ bj = 0 >i éumné de transbordo Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 vi 7 50 unidades fe FI ' US$ 900/unidade «if! wi ) 30 unidades produzidas \_ k \. / necessarias Ea acelll< gr \ tj ji \ %, | NG | | Ge _ US$ 200/ | US$ 300) US$ 200/unidade | 10 unidades no maximo DC ) unidade | unidade e/ ‘ \ Sy \ we OG, 4 ney | | non SY yd, | Sr %, NA \ | ray] , — Sy eG, \ Minimizar Z = CijXij Sy ty NG, \ ij*ij / N \ | . = J aX \ i=1 j=1 J SN / y 4 %\ / aN wT S.Q.: 40 unidades{ py | { 60 unidades , = J { W2 } : produzidas \ necessarias — 2 n n ) Xij xj; = bj, para todo noi j=1 j=1 0 <x; < uy, para todo arco i>j Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 8 8 25/10/2023 * Propriedade de solucdes viaveis: Uma condicdo necessdria para que um problema de fluxo de custo minimo tenha quaisquer solucées vidveis 6 que: n i=1 * Ou seja, o fluxo total gerado nos nos de suprimentos é igual ao fluxo total sendo nos nds de demanda. * Caso essa propriedade nao seja atendida: ° Se an bj >0 * Um né de demanda ficticio deve ser adicionado para absorver 0 excesso de oferta (com custos c;; = 0 adicionados de cada no de suprimento para este nd) * Se an b; <0 * Um né de suprimento ficticio deve ser adicionado para gerar o fluxo para o excesso de demanda (com custos cj; = 0. a partir deste no para cada no de demanda). Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 9 9 50 unidades USS 900/unidade 3 unidades wmigieiiae Fi 0 oui nw ¢ bp Minimizar Z = ; ; CijXij ae i=1 j=1 ey S.a.: % s USS 200/ USS 300, n n USS 200/unidade | 10 unidades no méximo DC unidade unidade he e Yu — Ya = b;,paratodo noi & Gb, ima i ey yy, S Ne 0 < xij < uj, para todo arco i>j ’ “iy ‘\ 40 unidades (2 2 ) 60 unidades produzidas ~ | necessérias ba = [50] [-30] On Cap = 9 © 2 () (UaB = 10) 1 3 o (ucg = 80) o Diogo Ferreira de Lima Silva (TEP) Pesquig [40] [—60] 10 10 25/10/2023 n n Minimizar Z = ; ; CijXij Exercicio: modele esse problema do fluxo de custo i=1 j=1 minimo. S.a.: n n ; Xi - 7 = b;,paratodo noi j=1 j=1 0 < xij S uj, para todo arco i>j ba = [50] [-30] ©) 2——+(0) 2 ©) (ugg = 10) 1 3 (ucg = 80) Diogo Ferreira de Lima Silva (TEP) Pesquig [40] [—60] il 11 Minimize Z= 2Xap + 4xac tH 9xap a 3XBc net 3XpE - 2Xep, nn : Minimizar Z = > deux subject to LiL, 0 i=1 j=1 Xap + Xac + Xap = 50 S.Q.: —NXAB + XBc = 40 n n — — kpoFX = 0 ., AC BC CE ; Xi - > Xj, = bj, para todo noi — Xap + Xpe — Xep = —30 = = — Xce — Xpe + Xep = —60 0<.x,; < u;;,para todo arcoi>j XAp = 10, XcE = 80, all Nij =O), ba = [50] [-30] ©) 2——+(0) 2 ©) (ugg = 10) 1 3 o (ucg = 80) o Diogo Ferreira de Lima Silva (TEP) Pesquig [40] [—60] a2 12 25/10/2023 13 Problema dos Transportes (71) 80 464 [75] O—— a SS [-65] * Nos de suprimentos sao as origens. Z Sa 0 + ¢ Nos de demanda sao os destinos. ss a x oe [100] (3) * Ndo ha no de transbordo. (ws) [-85] * Cada arco é direcionado de um no de suprimento para um no de demanda. * Temos: * cj paracada x;; © uyjp=o Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 me 14 7 25/10/2023 Problema da Designacdo * Mesma nocao do problema dos transportes... NOm ee * Os fatores adicionais sdo que: (a) on 1. Ontmero de nés de suprimento é igual ao LL numero de nés de demanda ° > ° 2. b; = 1 para cada no de suprimento <> 3. b; =—1 para cada no de demanda. * ‘ Zio ~*~ Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 15 15 Problema do Caminho Mais Curto * Um no de suprimento com um suprimento igual a 1 é fornecido para a origem * Um no de demanda com uma demanda igual a 1 é fornecido para o destino * Os nds restantes sdo de transbordo * Cada aresta do grafo ndo direcionado é substituida por um par de arcos direcionados em diregdes opostas. * Excecdes impostas aos nds de origem e destino. * As distancia tornam-se custos unitarios cj; ou C;j. e Ui = 00 Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 16 16 8 25/10/2023 ay “Re, 2 2 7 ~ 5-4) (o 2 B : (Dy ‘ . 3 j 4 | : c E Y 4 ae Todos uj; = %, valores cj Sao dados préximos aos arcos. [0] s “ Ab = > ~ 2 oy ms fr D “SIRE box . ()-—_ —) ; ; a [0] [0] Diogo Ferreira de Lima Silva (TEP) 17 Problema do Fluxo Maximo * Ja ha um nd de suprimento, um nd de demanda e capacidades nos arcos. * Adaptacdo: 1. Configure c;; = 0 para todos os arcos existentes. 2. Selecione F, um limite superior seguro sobre o fluxo vidvel maximo pela rede e designe esse valor como suprimento e demanda, respectivamente, aos nés de suprimento (b; = F) e ao nd de demanda (b; = —F). 3. Adicionar um arco que vai diretamente do né de suprimento para o nd de demanda e atribua a ele um custo unitario grande (cjj = M) bem como uma capacidade ilimitada (uj; = ©). Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 aR} 18 9 25/10/2023 10 Pesquisa Operacional II 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 19 Pesquisa Operacional II Voltando ao Exemplo Inicial 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 20 19 20 Minimize Z = 2Xap + 4x4c + 9X4p + 3Xpc + XCE + 3XDE + 2XeEp, nn : Minimizar Z = > deux subject to LZ ijxij i=1 j=1 Xap + Xac + Xap = 50 S.Q.: —NXAB + XBc . = " n n = > Je Xx = ne AC BC CE ; xij — > Xj, = bj, para todo noi — Xap + Xpe — Xep = —30 1 1 — Xce — Xpe + Xep = —60 0 < xij S uj, para todo arco i>j and XAp = 10, XcE = 80, all Nij =O), ba = [50] [-30] ©) — = 2 (©) (ugg = 10) 1 3 (ucg = 80) Diogo Ferreira de Lima Silva (TEP) Pesquig [40] [—60] yal 21 n n ¢ Para cada nd, temos uma restrigdo de Fluxo Minimizar Z = ; ; CijXij i=1 j=1 * Porém, sabemos da propriedade do problema que: S.d.: n n Yb = 0 >. xy — Ya = be para todo n6 i ieV j=l j=l . . . . 0 < xij S uj, para todo arco i>j ¢ Uma restrigdo pode ser escrita como o negativo do somatorio das n — 1 outras. Minimize Z = 2xapt 4Xac + Wap + 3XBC + XE + 3XpE + 2X~p. . subject to * Temos um grau de liberdade! J Xap + X4c + Xap = 50 * Se tivermos apenas essas restrigdes funcionais, teremos —XAB + XBC = 40 exatamente n — 1 variaveis basicas! ~ Nac — Xe + Xce = 0 — Xap + Xpe — Xep = —30 —XCE— Xpe + Xep = —60 and Xap = 10, Xce = 80, all xj; = 0. Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 ved 22 25/10/2023 12 Pesquisa Operacional II Método Simplex de Rede 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 23 Pesquisa Operacional II Simplex de Rede • Versão altamente otimizada do método Simplex para a resolução do problema do Fluxo de Custo Mínimo. • Assim como no Simplex, a partir de uma solução básica viável (BV), as iterações incluem: • Testar otimalidade • Encontrar a variável que entra e a variável que sai da base • Testar a nova solução BV... 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 24 23 24 25/10/2023 13 Pesquisa Operacional II Simplex de Rede • Versão altamente otimizada do método Simplex para a resolução do problema do Fluxo de Custo Mínimo. • Assim como no Simplex, a partir de uma solução básica viável (BV), realiza-se uma série de iterações • Porém, nenhuma tabela Simplex é necessária. 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 25 Pesquisa Operacional II Simplex de Rede • Estende o método simplex de transporte para tratar também outros tipos de problemas do fluxo de custo mínimo. • Veremos uma versão simplificada. • Serão omitidos alguns detalhes do algoritmo, como as formas mais eficientes de encontrar: • Solução BV inicial • Decisão sobre entrada na base 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 26 25 26 25/10/2023 Técnica do Limite Superior Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 way 27 J . . . . Técnica dos Limite Superior * E comum em problemas de PL que parte ou todas as variaveis x; individuais tenham restrigoes de limite superior xj < uj * Se tratarmos essas restrig¢des como funcionais, o tempo de processamento aumenta bastante. * Restrigdes funcionais exigem mais do que restrigdes de ndo negatividade. * A técnica do limite superior impede esse aumento de tempo de processamento, eliminando as restricdes de limite superior das restricdes funcionais e tratando-as em separado, basicamente como restri¢des de nado negatividade. Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 v2) 28 14 25/10/2023 J . . . . Técnica dos Limite Superior * Observe que uma variavel de decisdo x; com limite superior (x; < uj) pode ser substituida por: j= Uj Vj * Onde y; seria considerada como a nova variavel de decisdo (complementar de x;). Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 29 29 J . . . . Técnica dos Limite Superior * Observe que uma variavel de decisdo x; com limite superior (x; < uj) pode ser substituida por: j= Uj Vj * Onde y; seria considerada como a nova variavel de decisdo (complementar de x;). * A variavel de decisdo deixa de ser o quanto estamos acima de zero (x;) e passa a ser 0 quanto estamos abaixo de u,, valor dado por yj. Yj = Uj Xj Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 30 30 15 25/10/2023 J . . . . Técnica dos Limite Superior * Como 0 < x; < uj, temos que: 0 < yj S uj Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 he 31 J . . . . Técnica dos Limite Superior ¢ A qualquer momento no método Simplex, podemos: 1. Usar x;, em que 0< xj Su 2. Substituir x; poru; — yj,em que0 < y; < uj. * Técnica do Limite Superior: * Comece escolhendo a opcao 1. * Sempre que x; = 0, use a op¢do 1, de modo que x; seja ndo basica. * Sempre que x; = uj, use a op¢ao 2, de forma que y; = 0 seja nao basica. * Mude de alternativa quando o valor do outro ponto extremo de x; for atingido. Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 32 32 16 25/10/2023 17 Pesquisa Operacional II • Lembre-se de que o método simplex seleciona como variável básica que sai aquela que se tornaria inviável primeiro, tornando-se negativa à medida que a variável básica que entra é aumentada. • A modificação agora feita é considerar nessa seleção, além da não negatividade, o limite superior das variáveis na base, à medida que a variável básica que entra é incrementada. 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 33 Pesquisa Operacional II Técnica do Limite Superior no Simplex de Rede 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 34 33 34 25/10/2023 J . . . . Técnica dos Limite Superior * Usada para lidar eficientemente com as restri¢des de capacidade do arco x;; < uj;. * Essas restri¢des funcionais sao tratadas como de nao-negatividade. Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 35 35 J . . . . Técnica dos Limite Superior * Assim, os limites superiores sdo considerados apenas quando a variavel basica de saida é determinada. 1. Avariavel basica de entrada 6 aumentada a partir do zero 2. Avaridvel basica de saida é a primeira que atinge: * Seu limite inferior (0) ou * Seu limite superior (u;;). Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 36 36 18 25/10/2023 7 . . . ° Técnica dos Limite Superior * Uma VB em seu limite superior x;; = ujj é substituida por x;; = uj; — Vij. * Entdo, yj; = 0 torna-se a VNB (VB que saiu da base). * oarcoi > j ésubstituido com o arco reverso j > i * Capacidade = uj; (a quantidade maxima do fluxo x;; que pode ser cancelado) * Custo unitario = —c;; (cada unidade de fluxo cancelado economiza c;;) * Subtraimos uj; de bj e somamos uj; a b; * Quando y;; se torna uma variavel basica, seu valor pode ser pensado como um fluxo na dire¢do j > i, cancelando aquela quantidade do fluxo previamente atribuido (x;; = ujj) do né i para o nd j. Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 37 37 ba = [50] [-30] o 20) 2 a . (ugg = 10) Digamos que em um determinado momento, a I variavel x4, atingiu seu limite superior e 3 we luce = 80) precisara sair da base [40] [-60] [40] 8g [~30] * Alteragdes: () “AD D ) 1. Substituir x,2 = 10 por x4g = 10 — yap A 2. Inverter o arco 4 [0] | \ 3. Cpa = —Cap aul) = | “ Cc 2| |3 4. ba = ba — Upp (Ug, = 10) \ } 5. bp = bp + UsB ; ieee ¥ UcE = (B E YY / [50] [60] Diogo Ferreira de Lima Silva (TEP) Pesquisa Operacional II 25/10/2023 ct) 38 19 25/10/2023 20 Pesquisa Operacional II Fonte • Hillier, Frederick S.; Lieberman, Gerald J.. Introdução à Pesquisa Operacional. 9ª Edição. Porto Alegre: AMGH, 2012. 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 39 Pesquisa Operacional II Pesquisa Operacional II 25/10/2023 Diogo Ferreira de Lima Silva (TEP) 40 39 40