Plano de Ensino de Programação Linear - Universidade Federal do ABC

Programacao Linear NA2MCTA01717SA Universidade Federal do ABC Centro de Matematica Computacao e Cognicao Mituhiro Fukuda 3o quadrimestre de 2022 versao 1122022 Plano de Ensino 1 Determinante de Matrizes 2 Inversa de Matrizes 3 Resolucao de Sistemas LinearesSistema de Equacoes Lineares 4 Conjuntos Convexos Poliedros e Politopos 5 Introducao a Programacao Matematica e Programacao Linear 6 Resolucao Grafica de um Problema de Otimizacao Linear 7 Metodo Simplex Tableau 8 Solucao Basica e Solucao Viavel Basica 9 Metodo Simplex 10 Metodo Simplex Revisado 11 Calculo da Solucao Viavel Basica Inicial 12 Teoria de Dualidade 13 Metodo Simplex Dual 14 Analise de Sensibilidade 15 Metodos PrimaisDuais de Pontos Interiores References 1 Pellegrini J C Programacao Linear e Rudimentos de Otimizacao Nao Linear notas de aula versao 202205091016 2 Matouˇsek J and Gartner B Understanding and Using Linear Programming Heidelberg Springer 2007 3 Bertsimas D and Tsitsiklis J N Introduction to Linear Optimization Belmont Massachusetts Athena Scientific 1997 4 Luenberger D G and Ye Y Linear and Nonlinear Programming 4th edition Springer 2015 1 5 Vanderbei R J Linear Programming 5th edition Springer 2020 6 Longaray A A Introducao a Pesquisa Operacional Saraiva 2013 7 Wright S J PrimalDual InteriorPoint Methods SIAM 1997 2 1 Determinante de Matrizes 11 Multiplicagao envolvendo matrizes e vetores Seja A R uma matriz m x n com elementos reais Ou seja a matriz A possui m linhas e n colunas onde todos os seus elementos a R sao ntimeros reais Seja b R um vetor real de dimensao n Entao a multiplicagao entre uma matriz e um vetor é definido como n S ayidy i1 ait 442 Ain by a21 a92 ag WD azb Ab il Gm1l GAm2 Amn bn n S Amidi i1 Dado uma matriz C R a multiplicacao das matrizes A e C é dada por 11 G12 t Bin C11 C12 Clp Gai 22 Aan Col C22 Cap AC Lo nn Qm1 Gm2 Amn Chl Cn2 Cnp n n n So aici S QuiCig S Q1iCip i1 i1 i1 n n n S aaicit S A2zCiQ S Q2iCip i1 i1 i1 n n n S am2iCil S AmiCi2 S AmiCip i1 i1 i1 2 3 O 2 13 3 2 1 4 5 32 0 22 1 1 0 2 2 3 2 0 1 38 12 Determinante de uma matriz 3 x 3 Para matrizes 3 x 3 podemos determinar o determinante de uma matriz A pela regra de Sarrus abe det d e f aeibgf dhc ceg bdi fha g h i QO 1 1 det 2 0 2 007120123001320721 0060014 20 0 3 7 Observagcao Note que determinantes sé podem ser calculados para matrizes quadradas ntiimero de linhas e colunas iguais 3 13 Determinante de uma matriz arbitraria Data uma matriz quadrada A R o seu determinante é definido como det A S sign71614202 non oESn onde S é 0 grupo simétrico formado por todos os mapas que fazem a permutacao de n elementos e sign é 0 sinal do mapa correspondente Ou seja 1 2 ws o E Sy ay 12 eee in onde o1 41 o2 2 an ine signo 1 o é uma permutagao par 1 o éuma permutacao fmpar 0 1 1 det 2 0 2 011422433 411423432 412421433 A12423431 413421432 413022431 0 3 7 00702312712041 23100 00140640 20 14 Foérmulas envolvendo determinantes Teorema 11 Sejam a1 2b R onde A a aq ay 6 uma matriz real n x n e um escalar a R Entao a det a aj aa b aj4i Gn adet A det a ag aj1 bajy1 ay b det a aj j aa Qi41 ndetA jf 12n j 4 c det a j1 Gj Gj41 Gj1 Gj Gj41 n detA 2f 12n iF J Esta regra vale também para as colunas em vez de linhas Teorema 12 Sejam AB eC matrizes com dimens6des compativeis Entao A B det oc det Adet C Além disso det AB det Adet B det A det A onde A é a matriz transporta de A 15 Exercicios 1 Calcule o determinante das matrizes correspondentes 3 2 1 4 9 3 2 2 2 A QO l 2 B 5 8 1 C 1 2 4 1 2 3 1 4 6 5 1 3 4 2 Calcule o determinante de 111 1 122 2 123 8 12 3 n 3 Sejam AB eR Mostre que vale a formula A B i AB AB de BA detA Bdet 2 Inversa de matrizes Definigao 21 Dada uma matriz nxn real A diremos que esta matriz é invertivel ou nao singular se det A 0 Propriedade 22 Dada a matriz n x n real A invertivel a sua inversa é dada por 1 xr AltA det A onde A e a matriz de cofatores de A definida por aij 1 mij my 0 determinante da matriz A com a linha e coluna 7 removidas A matriz A é a tinica que satisfaz AA AA I onde I é a matriz identidade com n linhas e n colunas 0 l1 6 4 6 S 1 4 det 2 0 2 i 1 89 8 m 9 0 3 7 7 2 2 2 0 3 Resolugao de Sistemas LinearesSistema de Equacoes Lineares Considere 0 seguinte sistema linear com n varidveis e m equacoes lineares ayy ygQ es Aint by ag ag9Q2 s Gantn bg 1 Amit Gm2Q2 Gmnn dm onde ajjb R i 12m 7 12n sao constantes e x R j 12m sao as variaveis Alternativamente podemos descrever o sistema linear com n varidveis e m equacoées lineares como Az b Podemos classificar os sistemas lineares da seguinte forma e Sistema Possivel e Determinado Existe uma unica solucaéo para o sistema Neste caso n in geral e Sistema Possivel e Indeterminado Existem infinitas solucdes para o sistema e Sistema Impossivel Nao existe solucao para o sistema 5 31 Método de eliminagao de GaussJordan Qt a 23 1 1 2 11 1100 a 2m 23 2 2 1 212010 2 3a 223 11 3 13 2 1001 Realizar operagoes elementares para que a matriz do lado esquerdo tornese uma matriz identidade Ou seja multiplicar uma linha da equacao por uma constante que nao seja zero ou somar a uma linha da equacao os valores de uma outra linha multiplicada por uma constante que nao seja zero Seja 4 a equacao resultante da operacao 1 x 1 Seja 5 a equagao resultante da operagao 2 1 x 2 Seja 6 a equagao resultante da operagao 3 1 x 5 m1 322 33 2 4 133 3 2 0 0 fro 323 6 04 2 3B 3 01 Seja 8 a equacgao resultante da operacao 5 x z Seja 7 a equacao resultante da operagao 4 5 x Seja 9 a equagao resultante da operagao 6 5 x 3 ry 3 0 7 103 0 7 3 0 373 8 9 00 8 8 3 4 1 Seja 12 a equacao resultante da operacgao 9 x 3 Seja 10 a equacao resultante da operacao 7 9 x Seja 11 a equagao resultante da operagao 8 9 x ry 1 10 1001 ee 8 v3 3 12 0013 2 3 Portanto a solugdo do sistema linear acima é 1 2 73 1 23 Executamos portanto 12 adigdessubtracoes 21 multiplicacgdes e 9 divisdes no total 2 1 l Agora considere a matriz A 1 2 1 que descreve o sistema linear do exemplo Utilizando 1 3 2 o Teorema 11 temos que 123 det A det I 1 ee e e 2 3 8 Logo det A 8 Quando substituimos o vetor do lado direito b do sistema linear de equac6es notamos que Z 1 Y é a solucao de Ay 0 5 3 0 3 0 Yo 3 éasolucgao de Ay 1 7 a 0 0 Yy3 5 éasolucao de Ay 0 3 1 6 o que nos leva a Ay1 y2 y3 I e portanto A1 y1 y2 y3 7 8 5 8 1 8 1 8 3 8 1 8 5 8 7 8 3 8 Portanto o metodo de eliminacao de GaussJordan alem de resolver o sistema de equacoes lineares calcula o determinante e o inverso da matriz envolvida 32 Metodo de eliminacao de Gauss Exemplo Considere o mesmo exemplo anterior 2x1 x2 x3 1 1 x1 2x2 x3 2 2 x1 3x2 2x3 11 3 2 1 1 1 1 2 1 2 1 3 2 11 Iremos executar operacoes elementares para que a matriz do lado esquerdo tornese uma matriz triangular superior Seja 4 a equacao resultante da operacao 2 1 1 2 Seja 5 a equacao resultante da operacao 3 1 1 2 2x1 x2 x3 1 1 3 2x2 1 2x3 3 2 4 7 2x2 3 2x3 23 2 5 2 1 1 1 0 3 2 1 2 3 2 0 7 2 3 2 23 2 Seja 6 a equacao resultante da operacao 5 4 7 3 2x1 x2 x3 1 1 3 2x2 1 2x3 3 2 4 8 3x3 8 6 2 1 1 1 0 3 2 1 2 3 2 0 0 8 3 8 A partir daqui executaremos a substituicao reversa x3 8 8 3 x2 3 2 1 2 3 3 2 2 x1 1 2 3 2 1 Logo obtemos a mesma a solucao do sistema linear x1 x2 x3 1 2 3 Executamos portanto 11 adicoessubtracoes 11 multiplicacoes e 6 divisoes no total Portanto supondose que os metodos de eliminacoes de GaussJordan e Gauss possam ser executados ate o final sem nenhum erro o numero de operacoes aritmeticas das 4 operacoes serao igual a Tabela 1 Concluımos que apesar dos dois metodos terem a mesma complexidade computacional o metodo de eliminacao de Gauss requer menos operacoes aritmeticas para um sistema de equacoes lineares 7 Table 1 Numero das 4 operac6es aritméticas dos métodos de eliminacgoes de GaussJordan e Gauss Po x GaussJordan 22 apr tn42 n n2n1 13 Gauss n2n3n5 n2n3n5 nn1 33 Escolha do piv6 Até agora supomos que as operacgoes aritméticas com digitos finitos possam ser executados sem erros de calculos que possam alterar os resultados 102 x 1 1 10 61 1 Ly tt 0 2 1 1 0 Agora considaremos que os calculos do método de eliminacgao de Gauss foram exectuados no software comercial MATLAB Seja 3 a equacao resultante da operagao 2 1 x we 10 ay r 1 1 lo 1 10 10 3 0 10 10 onde o ntmero grifado contém um erro de arredondamento A partir daqui executaremos a substituicgao reversa 10 m Tor Qy T017 0 E assim obteremos a solugéo 2172 01 o qual claramente nao satisfaz a equacao 2 Para evitarmos estas situacdes executamos a selecao do pivé Por exemplo podemos escolher o coeficiente elemento com o maior valor absoluto entre os elementos da matriz pivoteamento completo substituir as linhas e colunas da do sistema da matriz No nosso exemplo felizmente todos os coeficientes sao 1 e portanto podemos substituir a primeira linha com a segunda linha ey wQ 0 1 1 1 0 102 lrg 1 2 1 61d Utilizando novamente o software MATLAB com o método de eliminacao de Gauss temos 1 Seja 3 a equacao resultante da operagao 2 1 x io LY TQ 0 1 1 l1 0O lz 1 3 0 1 1 onde o ntmero grifado contém um erro de arredondamento Executando a substituicaéo reversa temos 1 x 1 01 Ly att 1 1 o qual resulta em 2172 11 que é bem préxima da solugao correta 8 34 Exercıcios 1 Considere o sistema linear Ax b para A 2 2 2 1 2 4 5 1 3 b 6 5 17 Resolva o sistema linear pelos metodos de eliminacoes de GaussJordan e Gauss Confirme que ambos obtem o mesmo resultado 2 Faca o mesmo para A 1 0 0 1 1 0 1 1 1 b 1 3 2 3 Resolva o seguinte sistema linear 3x1 4x2 2 5 7x1 x2 1 7 4 Resolva o seguinte sistema linear x1 8 5x2 3 5 8x1 13x2 5 4 Conjuntos Convexos Poliedros e Politopos 41 Conjuntos convexos Definicao 41 Um subconjunto C de Rn e convexo se x y C e α 0 1 αx 1 αy C A interpretacao geometrica desta definicao e que o segmento que liga os pontos x e y de C deve estar contido em C tambem Exemplos Definicao 42 Um subconjunto S de Rn e chamado de limitado se existe uma constante K 0 tal que o valor absoluto de todas as coordenadas de todos os elementos de S e menor ou igual a K Ou alternativamente quando nao existe nenhuma semirreta contida nele Definicao 43 Seja a Rn um vetor que nao seja nulo e b R Entao 9 a O conjunto R a x b 6 chamado de um hiperplano afim de R b O conjunto a R a x b é chamado de um semiespaco afim de R e x CR 2 22 1 6 um hiperplano afim em R e x R x 0 6 um semiespaco afim em R e x R x3 1 6 um hiperplano afim em R e 2 CR x 22 23 1 é um semiespaco afim em R Proposigao 44 a Um hiperplano afim é um conjunto convexo b Um semiespaco afim é um conjunto convexo c A intersecgéo de uma colecéo arbitraria de conjuntos convexos é um conjunto convexo Proof a Chamemos o hiperplano afim de H a R a x b e sejam yz H Queremos mostrar para qualquer escalar a R ay1az H Para isto basta mostrar que este novo vetor satisfaz a igualdade a ay 1 az aay 1 aaz ab 1 ab b como querfamos b Basta trocar a igualdade acima pela desigualdade c Seja Ciceq uma colegao artitrdria de conjuntos convexos e considere C MjcC Queremos provar que este conjunto é convexo Ou seja seja xy C Entaéo x y C para cada i A porque estes vetores pertencem 4 todos os conjuntos C Para um escalar arbitrario a R temos pela convexidade de C que ax lay Cj Logo aw 1 ay NicaC C como queriamos 1 Definigao 45 Dada um subconjunto S C R o seu envoltério convexo é definido como a intersecao de todos os conjuntos convexos que contem S 0 1 0 0 Considere os 4 vetores 0 0 1 0 em R O envoltdrio convexo destes vetores 0 0 0 1 é o tetraedro piramide que possui estes vetores como pontos extremos k Definicao 46 Dados 21 2x2 R e constantes escalares 1 A2Ax 0 tal que S i 10 i1 k vetor resultante S Aix chamado de combinagao convexa de 41 2 2 i1 0 1 0 0 Considere os 4 vetores no exemplo anterior 0 0 1 0 em R O vetor 4 0 0 0 1 7 é resultante de uma combinacaéo convexa destes vetores para y Ag A3 A4 Proposigao 47 Sejam C e C2 subconjuntos convexos de R e um escalar 3 R Entao 10 a O conjunto soma C1 C2 a 2 R a Ci x2 C2 6 um conjunto convexo b O conjunto resultante de um produto escalar BC Ga R a Cy é um conjunto convexo Proof a Considere dois vetores arbitrdrios pertencentes C Co x e y Entao existem 21y Cie L2Y C2 tais quex 241 2 ey y Yo Queremos mostrar que ax 1 ay Cy C2 para qualquer a R De fato temos ax 1 ay aa1 2 1ay yo aa Laag ay 1 ayg Cy C2 pois Cy e C2 sao conjuntos convexos b Sejam ay BC Caso 8 0 x y Oe teremos ax 1 ay BC para qualquer a R Suponhamos que 6 0 Neste caso 5 g C e teremos para qualquer a R aw lay abs 1 a 64 8 a8 1 a BC porque o que esta entre parénteses esta contido em C pela convexidade de Cj 1 42 Poliedros e politopos Definicgao 48 A interseccao de um ntimero finito de semiplanos é chamado de poliedro Portanto podemos representar um poliedro como P a R Aw b para AE R e DER Na definicéo de poliedro utilizamos uma notacao que é utilizada comumentemente em otimizacao matematica onde Ax b significa Aa b para 12m e 6 a ésima coordenada do vetor correspondente Definigao 49 Em particular um poliedro limitado é chamado de politopo Corolario 410 da Proposigaéo 44 Um poliedro e portanto um politopo também é um conjunto convexo Definigao 411 Dado um poliedro P um vector P é chamado de ponto extremo ou vértice de P se x nao é uma combinacao convexa de outros vetores pertencentes a P Em outras palavras nao existem vetores y e z distintos de x tais que x ay 1 az para a 01 43 Lema de Farkas Entre os resultados classicos em otimizacaéo matematica podemos citar o Lema de Farkas que iremos apresentar na versao simplificada sem provas Lema 412 Lema de Farkas Dados os vetores a R 12n b R considere 0 seguinte sistema de igualdades e desigualdades n a Soa b x20 612n i1 b ye R aiy 0 i 12 te by 0 Entao a possui uma solucéo b nao possuiu uma solucgéo Equivalentemente a nao possui uma solucao b possuiu uma solucao O Lema de Farkas é importante para provarmos por exemplo o teorema de dualidade Teorema 413 Teorema de Gordan Dados os vetores a R i 12n b R considere o seguinte sistema de igualdades e desigualdades n a S aja 0 0x9tn 0 i1 b yeER ay0 6 12n Entao a possui uma solucgao b nao possuiu uma solucao 11 2 A b ap a ot a vee ay ao 2 a s x a3 5 4 b Figure 1 Exemplo do Lema de Farkas para m 2 n 3 Lado esquerdo mostra um caso em que 0 caso a é satisfieito e o direito quando o caso b é satisfeito 44 Exercicios 1 Desenhe o poliedro x R 5a 2x2 262 252 ay 2 Determine os pontos extremos dos seguintes conjuntos a Um cubo em dimensao quatro 4 b Um simplex de dimensaéo quatro 2 R S x1 20 i1 Ly 242 43 4 3x1 3x2 23 3 c eR Ly orn 3 SY 321 39 3 6 x1 0 xr 0 x3 0 3 Faca um desenho de um caso particular para n 3 m 2 que ilustre o Teorema de Gordan 5 Introducgao a Programacgao Matematica e Programacgao Linear 51 Programagao matematica Por razoes histdéricas que se deve a4 invencgao do método simplex por George B Dantzig em 1947 esta area é conhecida como programacao matematica Porém pesquisadores modernos tem dado preferéncia ao termo otimizagao matematica cf Mathematical Optimization Society que mudou o nome a partir de 2011 No Brasil esta drea é conhecida como otimizagao Podemos dividir a otimizagao matematica em duas grandes dreas a otimizacgao continua e a otimizagao discretacombinatéria Ainda dentro da otimizagdéo continua temos a otimizagao es tocastica que tem ganhado importancia nos tltimos anos A otimizacgao matematica sempre foi uma area interdisciplinar presente em diversas Areas como matematica aplicada ciéncia da computacao economia engenharia de producao engenharia eletrénica etc Em particular a relevancia do aprendizado em maquina e ciéncia dos dados tem contribuido para o avanco da area nos anos recentes 52 Introdugao a otimizagcao linear Um tipico problema de otimizacao linear pode ser descrito como 12 minimizar c1x1 c2x2 cnxn sujeito a a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm x1 x2 xn 0 2 onde c1 c2 cn a11 a12 amn b1 b2 bm sao as entradas do problema que sao constantes numeros reais em geral e x1 x2 xn sao as variaveis que queremos determinar Alem disso as desigualdades podem ser substituidas por igualdades e viceversa 53 Modelagem de casos como problemas de otimizacao linear Exemplo 51 O Problema da Dieta Suponhamos que existam n diferentes tipos de comidas por exemplo porcoes de arroz feijao carnes hamburguers pizzas leite batatas fritas etc e m tipos de nutrientes o qual se sabe o valor nutricional por porcao vide Tabela 2 Table 2 Valor nutricional por tipo de comida comida 1 comida 2 comida n nutriente 1 a11 a12 a1n nutriente 2 a21 a22 a2n nutriente m am1 am2 amn Seja A Rmn a matriz com os elementos aij E sejam b1 b2 bm os valores nutricionais diarios necessarios para uma dieta ideal o que representaremos pelo vetor b Um problema que podemos pensar e tentar suprir os nutrientes diarios com o mınimo custo possıvel para cada tipo de comida i que pode custar ci por porcao que pode ser fracionaria tipo comida por quilo Esta porcao fracionaria pode ser representado pela variavel xi e assim teremos o problema 2 Exemplo 52 Problema de Producao 1 Um produtor de leite precisa planejar sua producao ao longo do ano Ha capacidade para produzir 900ℓ por mˆes sem pagamento de hora extra e 1100ℓ por mˆes pagando hora extra O custo de producao de 1ℓ de leite e 10 sem hora extra e 13 com hora extra O custo de armazenamento de 1ℓ de leite quando nao e vendido no mesmo mˆes e de 15 O produtor tem dados historicos com a demanda tıpica de cada mˆes Tabela 3 Table 3 Historico da demanda por mˆes de leite ℓ mˆes demanda ℓ mˆes demanda ℓ janeiro 500 julho 540 fevereiro 350 agosto 450 marco 550 setembro 400 abril 400 outubro 400 maio 600 novembro 400 junho 600 dezembro 500 As variaveis cujos valores precisamos determinar sao pi a producao no mˆes i ei a producao com horas extras no mˆes i ai a quantidade de leite produzido no mˆes i e armazenada para o mˆes seguinte 13 Como a demanda do ano todo nao deve variar muito o produtor precisa apenas minimizar o custo de producao dessa demanda dado por 12 12 11 10S pi 13S ef 15 S ai i1 i1 i1 As restricdes séo p 900 e e 200 que representa a capacidade de produgao por més Se a demanda em um més é z entaéo a sobra do més anterior mais a producao do mes atual menos o que é levado ao préximo més é igual a x pi teay 500 p2ttegaga 350 pi2tei2ai 500 JA temos agora o modelo completo que mostramos a seguir 12 12 11 minimizar 10 So pi 13 S e 15 S aj i1 i1 i1 sujeitoa p 900 i 1212 e 200 i 12 12 py e1 ay 500 po 2 ag a1 350 p3 e3 a3 ag 550 pa 4 a4 a3 400 Ds e5 a5 a4 600 pe eg ag a5 600 p7 e7 a7 a6 540 ps eg ag a7 450 pg 9 ag ag 400 Pio 10 A190 ag 400 pi 11 G11 G19 400 Pi2 12 a11 500 aji2 0 Di Ci UG 0 i 1212 54 Nomenclatura de um problema de otimizagao linear Considere o seguinte problema de otimizacao linear o qual chamamos que esta na forma can6nica mimimizar C c sujeito a Az b x0 onde A R cE R DER by ba 0m 0 Definigao 53 As n varidveis 71 222 sao chamadas de varidveis de decisao Definigao 54 A funcao fx e141 co2 4 Cyn nas varidveis 11 22Up 6 chamada de fungao objetivo Definigao 55 O valor da funcao objetivo cyx1 cog CynXn que denotaremos também pela letra C é chamado de valor da fungao objectivo 14 Definigao 56 As desigualdades 7 aj b j 12m ea 0 i 12n so chamadas de restrigoes Definigao 57 Um ponto 2122n que satisfaz todas as restrigdes do problema de otimizacgao linear 6 chamado de ponto viavel Definicgao 58 O conjunto de todos os pontos vidveis é chamado de regiao viadvel Definigao 59 Um ponto aj 23x2 que resolve o problema de otimizacgao linear é chamado de solugao é6tima Definigao 510 O valor da fungao objetivo C calculado para uma solugéo dtima ajv52 é chamado de valor 6timo 55 Exercicios 1 Um hospital precisa definir a escala dos enfermeiros durante a noite meianoite a 8 horas da manha A demanda de enfermeiros num determinado dia j é um ntimero inteiro d de enfermeiros jy 127 Cada enfermeiro trabalha 5 dias consecutivos na escala noturna Determine o numero minimo de enfermeiros necessarios para atender a demanda de uma semana 2 Uma empresa produz n produtos diferentes de m diferentes matériasprimas Seja b i 12m a quantidade existente da matériaprima 7 O produto j requer a unidades da matériaprima i e resulta em um lucro de c por unidade do produto 7 A empresa necessita determinar a quantidade da producao de cada produto para maximizar o lucro no periodo 6 Resolucao Grafica de um Problema de Otimizacgao Linear Existem varias formas de resolver um problema de otimizacao linear Dentre elas o método mais simples é através do método grafico que iremos apresentar a seguir Uma observacao importante 6 que como s6 podemos desenhar graficos em 2D ou 3D este método fica limitado a 2 varidveis ou no maximo 8 variaveis Os passos basicos para resolver um problema de otimizacao linear pelo método grafico pode ser resumido como Passo 1 Determine desenhe a regiao vidvel do problema Passo 2 Desenhar o vetor c correspondente a funcao objetivo Passo 3 Desenhar uma reta perpendicular ao vetor c correspondente a funcao objetivo Passo 4 Caso o problema seja de minimizagéo uma solucao étima serd o ponto vetor que corresponde ao ultimo ponto da regiao vidvel quando movemos a reta acima em direcéo oposta a c caso o problema seja de maximizacao sera o ultimo ponto da regiao vidvel quando movemos a reta acima na mesma direcao de c 61 Exemplos de resolugoes pelo método grafico para problemas de otimizacao linear Exemplo 1 problema com solugao 6tima minimizar 21 2 sujeito a 3 22 4 X1 3 X1X2 0 Cuja solugao étima é 1 72 21 Vide Figure 2 15 Figure 2 Exemplo de um problema de otimizacao linear com solucao otima Exemplo 2 problema inviavel minimizar x1 2x2 sujeito a x1 x2 1 2x1 x2 2 x1 x2 0 Figure 3 mostra um problema que nao tem solucao porque nao existe uma regiao viavel deveria ser a intersecao entre a regiao em verde claro e o primeiro quadrante o que claramente e um conjunto vazio Figure 3 Exemplo de um problema de otimizacao linear inviavel 16 Exemplo 3 problema viavel mas sem uma solucao finita minimizar x1 2x2 sujeito a 2x1 2x2 2 3x1 2x2 2 x1 x2 1 x1 x2 0 Figure 4 mostra um problema que tem uma regiao viavel mas que nao possui uma solucao finita Ou seja podemos diminuir o valor da funcao objetivo o quanto quisermos Figure 4 Exemplo de um problema de otimizacao linear sem solucao finita 62 As trˆes possibilidades de um problema de otimizacao linear Como vimos acima existem trˆes possibilidades De fato estas sao as unicas possibilidades que podemos esperar de um problema de otimizacao linear Regiao Viavel Solucao Otima Valor Otimo nao vazia existe uma solucao otima finito nao vazia inexistente infinito vazia inexistente nao definido 63 Exercıcios 1 Resolva o seguinte problema de otimizacao linear utilizando o metodo grafico minimizar 4x1 5x2 sujeito a 4x1 7x2 336 6x1 3x2 252 x1 x2 0 2 Resolva o seguinte problema de otimizacao linear utilizando o metodo grafico maximizar 2x1 7x2 sujeito a 2x1 4x2 16 4x1 3x2 24 x1 x2 0 17 7 Metodo Simplex Tableau 71 Introducao ao metodo simplex tableau Considere um problema de otimizacao linear na forma forma canˆonica minimizar C 5x1 3x2 sujeito a 10x1 12x2 60 2x1 x2 6 x1 x2 0 Nas proximas linhas iremos mencionar alguns conceitos que serao definidos formalmente quando o metodo simplex que utiliza operacoes envolvendo matrizes for apresentado 72 Solucao basica inicial Introduziremos o que chamamos de variaveis de folga no problema acima Definicao 71 Sejam xn1 xn2 xnm variaveis adicionais nao negativos que serao introduzidos nas restricoes do problema de otimizacao linear na forma canˆonica para que se tornem igualdades Estas variaveis sao chamadas de variaveis de folga Entao x3 e x4 serao as variavies de folga para o problema acima Organizaremos o sistema na seguinte forma x3 10x1 12x2 60 x4 2x1 x2 6 C 5x1 3x2 0 para chegarmos a um tableau variaveis termos basicas x1 x2 x3 x4 independentes x3 10 12 1 0 60 x4 2 1 0 1 6 C 5 3 0 0 0 o qual corresponde a solucao basica inicial x1 x2 x3 x4 0 0 60 6 e o valor da funcao objetivo C 0 73 Variavel basica variavel nao basica pivˆo A partir daqui iremos determinar a variavel nao basica x1 ou x2 que entra na base 34 e a variavel basica x3 ou x4 que sai da base A variavel nao basica que entra na base sera a variavel que corresponde a um coeficiente positivo na ultima linha do tableau No caso escolheremos o mais positivo 5 o que corresponde a variavel x1 Para determinar a variavel que sai da base iremos escolher a variavel correspondente ao menor valor dos quocientes entre os termos independentes e os coeficientes da variavel nao basica positivas que ira entrar na base No caso x1 Entao teremos 60 10 6 variavel x3 e 6 2 3 variavel x4 Portanto a variavel que corresponde ao valor 3 nas contas acima que e x4 sera a variavel que saira da base A linha correspondente a variavel que sai da base sera chamada de linha pivˆo E a coluna corre spondente a variavel que entra na base sera chamada de coluna pivˆo O coeficiente da linha pivˆo correspondente a coluna da variavel que entra na base coluna pivˆo sera chamado de pivˆo Vide numero 2 com um cırculo no tableau inicial 18 74 Pivoteamento Agora passaremos para a fase de iteracoes Primeiramente incluiremos a nova varidvel nao bdsica na base que se torna 31 e iremos dividir a linha piv6 pelo valor do pivé que sempre sera positivo CALP Coeficiente Antiga Linha Pivé CNLP Coeficiente Nova Linha Piv6 a 6 P Pivo para obtermos o seguinte tableau correspondente ao valor P2 varidveis termos basicas 71 2 23 24 independentes v3 ry 4 0 4 3 C Em seguida iremos recalcular as outras linhas utilizando a seguinte formula Linhat Antiga Linha 7 Coeficiente Coluna Pivo linha i x Coeficiente Nova Linha Pivo onde i corresponde a linha 7 exceto a linha pivo Por exemplo a para linha correspondente a varidvel x3 temos 10 10 x 1 0 1210 x 12 7 1 10 x 0 1 0 10 x 12 5 60 10 x 3 30 e para a linha corresponde a C temos 55x 1 0 3 5x 12 12 0 5 x 0 0 0 5 x 12 52 O 5 x 3 15 o que corresponde a varidveis termos basicas 21 2 23 4X4 independentes x3 0 M 1 5 30 ry 1 4 0 3 Cc 0 53 O 5 15 Logo a solucao basica depois da 1 iteracao é x1 2223 24 30300 eC 15 Como temos um coeficiente positivo 12 na ultima linha a coluna correspondente a varidvel x2 sera a varidvel nao badsica que entra na base atual 31 Para descobrirmos a varidvel bdsica que sai da base temos que calcular os quocientes entres os termos independentes e somente os coeficientes positivos da varidvel nao basica que entrard na base No caso x2 Entao teremos 30 3 7 varidvel x3 e 7 6 varidvel 2 2 Portanto a varidvel que corresponde ao valor 307 que é x3 sera a varidvel que saird da base O piv6 neste caso seré P7 A base agora sera 21 x2 e x1 serao as varidveis basicas e 73 e x4 serao as varidveis nao basicas Utilizemos entao a formula CNLPCALPP varidveis termos basicas 21 2 23 4X4 independentes w 0 OF 4 ZI C 19 Em seguida iremos recalcularemos as outras linhas utilizando a formula Li ALi CCPi CNLP Para a linha correspondente a variavel x1 temos 1 12 0 1 12 12 1 0 0 12 17 114 12 12 57 67 3 12 307 67 e para a linha corresponde a C temos 0 12 0 0 12 12 1 0 0 12 17 114 52 12 57 157 15 12 307 1207 o que corresponde a variaveis termos basicas x1 x2 x3 x4 independentes x2 0 1 1 7 5 7 30 7 x1 1 0 1 14 6 7 6 7 C 0 0 114 157 1207 Logo a solucao basica depois da 2a iteracao e x1 x2 x3 x4 67 307 0 0 e C 1207 A iteracoes terminam aqui porque todos os coeficientes da ultima linha sao nao positivos E x1 x2 67 307 sera a solucao otima do problema original removendose as variaveis de folga e 1207 sera o valor otimo 75 Resumo do metodo simplex tableau Considere o seguinte problema de otimizacao linear na forma canˆonica mimimizar C cT x sujeito a Ax b x 0 onde b1 b2 bm 0 Introduza as variaveis de folga xn1 xn2 xnm e considere o tableau com a solucao basica inicial variaveis termos basicas x1 xn xn1 xnm independentes xn1 a11 a1n 1 0 b1 xnm am1 amn 0 1 bm C c1 cn 0 0 0 A solucao basica inicial e x1 xn xn1 xnm 0 0 b1 bm o valor da funcao ob jetivo e igual a 0 e a base e n 1 n m Teste de Otimalidade Se todos os coeficientes da ultima linha forem nao positivos pare e considere a solucao o qual se atribui os valores na ultima coluna a direita do tableau para as variaveis que estao na primeira coluna a esquerda e 0 para as demais variaveis que corresponde a solucao basica otima A solucao otima do problema original e a solucao basica otima sem as variaveis de folga O valor otimo corresponde ao valor que esta no canto inferior direito do tableau Caso contrario continue com a iteracao Passo 1 Escolha da variavel nao basica que ENTRA na base se torna variavel basica Escolha um coeficiente da ultima linha que seja positivo digamos c e Entao a variavel correspon dente a esta coluna xe se tornara variavel basica Esta coluna e chamada de coluna pivˆo 20 Passo 2 Escolha da varidvel bdsica que SAI da base se torna varidvel nao basica Considere somente os coeficientes positivos da coluna pivo A varidvel basica que se tornara varidvel nao basica seré aquela que tiver o menor quociente entre o termo independente e o coeficiente positivo da coluna piv6 Denotemos esta varidvel como 2 e o pivé P sera o coeficiente correspondente a linha da varidvel x e a coluna da varidvel x elas sao chamadas de linha pivé e coluna piv6 respectivamente Passo 3 Pivoteamento calculo do novo tableau A nova linha correspondente a varidvel bdsica que entrou x pode ser obtido fazendo o calculo CALP Coeficiente Antiga Linha Pivé CNLP Coeficiente Nova Linha Piv6 P Pivo varidveis termos basicas 21 p In4z1 Lnm independentes Cc onde é o nimero correspondente As demais linhas podem ser calculadas utilizando a férmula Linhat Antiga Linha 7 Coeficiente Coluna Pivo linha i x Coeficiente Nova Linha Pivo onde i corresponde as demais linhas exceto a linha pivo varidveis termos basicas 21 p In4z1 Lnm independentes aan eae Le C oe Ok wee Faca o Teste de Otimalidade acima Caso o tableau acima for o final extraia a solucao basica étima As varidveis basicas teraéo o valor correspondentes na coluna termos independentes As demais varidveis varidveis nao basicas terao valor zero O valor da solucaéo 6tima seraé o valor que esta na ultima linha da coluna mais a direita 76 Exercicios Resolva os seguintes problemas de otimizacao linear pelo método simplex tableau 1 minimizar 202 6022 sujeitoa 52x 4x2 80 2x21 429 40 2x21 8x9 64 L1 2 0 21 2 minimizar d21 2 sujeito a 10 12 60 21 x2 6 L1 XQ 2 0 8 Solugao Basica e Solugao Viavel Basica 81 Revisao e introdugao Definigao 81 Dados os vetores aj a2 R dizemos que estes vetores sao linearmente inde m pendentes se qualquer que sejam a1 2p R tal que So aia 0 implica que ay ag i1 Ay 0 Suponha que p n Se chamarmos de A a matriz onde os vetores a1 2 R estao posicionados como linhas sabemos que estes p vetores sao linearmente independentes se e somente se existem p colunas de A que sao linearmente independentes Ou seja o posto de A é igual a p JA vimos que a forma candnica de um problema de otimizagao linear é dada por mimimizar a sujeito a Az b x0 onde A R GER BE R by by 0m 0 Iremos definir agora a forma padrao de um problema de otimizacao linear como sendo mimimizar cl x sujeitoa Axb 3 xz 0 onde A R ce R e bE R Note que neste caso as coordenadas do vetor b nao precisam ser nao negativas Assumiremos a partir de agora que o problema de otimizacao linear esta na forma padrao 82 Solugao basica e solugao vidvel basica Seja PaeER Agxvbx 0 4 o poliedro correspondente ao problema de otimizagéo linear na forma padrao 3 Definigao 82 Diremos que R é uma solugao basica para o problema de otimizacao linear na forma padrao caso i R satisfazer Ax b ii Existem m colunas ou linhas linearmente independentes em A iii 7 0 para as colunas nao selecionadas no item ii acima Sejam 112 1 0 0 0 8 0160100 12 A b 1000010 4 0100001 6 22 Por exemplo x 4 6 1 4 0 0 0T e uma solucao basica pois Ax 1 1 2 1 0 0 0 0 1 6 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 4 6 1 4 0 0 0 8 12 4 6 b satisfazendo a condicao i as colunas A1 A2 A3 A4 sao vetores linearmente independentes satisfazendo a condicao ii pois det A1 A2 A3 A4 6 e x5 x6 x7 0 satisfazendo a condicao iii Definicao 83 Diremos que x Rn e uma solucao viavel basica para o problema de otimizacao linear na forma padrao caso x Rn for uma solucao basica e alem disso ela satisfazer x 0 Exemplo Para o mesmo exemplo acima enquanto x 4 6 1 4 0 0 0T e uma solucao basica como vimos nao e uma solucao viavel basica Por outro lado x 0 0 0 8 12 4 6T e ao mesmo tempo uma solucao basica e solucao viavel basica pois Ax 1 1 2 1 0 0 0 0 1 6 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 8 12 4 6 8 12 4 6 b satisfazendo a condicao i as colunas A4 A5 A6 A7 sao vetores linearmente independentes satisfazendo a condicao ii pois det A4 A5 A6 A7 1 x1 x2 x3 0 satisfazendo a condicao iii e finalmente x 0 Um fato que iremos usar sem provas e a seguinte Teorema 84 3 Seja P um poliedro nao vazio e x P Entao os seguintes fatos sao equivalentes a x e um ponto extremo de P b x e uma solucao viavel basica para o problema definido pelo P O seguinte fato decorre do teorema acima Corolario 85 3 Como um poliedro e definido por um numero finito de desigualdades eou igual dades lineares o numero de solucoes basicas e solucoes viaveis basicas sao finitos Exemplo Mesmo que o numero de solucoes viaveis basicas seja um numero finito ele pode ser extremamente grande Por exemplo um cubo em dimensao n x Rn 0 xi 1 i 1 2 n pode ser descrito por 2n desigualdades mas possui 2n pontos extremos Hipotese 86 Suponhemos que a matriz A Rmn possui m linhas linearmente independentes Ou seja que tem posto completo Neste caso m n e A tambem possui m colunas linearmente independentes 23 Esta hipdtese nao é tao restritiva Quando existir um R que satisfaca A b e a hipdtese nao 6 satisfeita isso significa que pelo menos uma das igualdade digamos af b é uma igualdade redundante para o sistema de equacgdes de modo que podemos removéla das restricdes do problema Teorema 87 3 Considere o poliedro definido por um problema de otimizagao linear na forma padrao 4 e que a Hipotese 86 esteja satisfeita Entaéo R é uma solucao basica se e somente se A be existem indices B1 B2Bm tais que i As colunas Agi Ag2ABm 840 linearmente independentes ii Se o indice i 4 B1 B2 Bm entao TZ 0 Portanto podemos deduzir o seguinte procedimento para gerar solucoes basicas para o nosso problema Procedimento para gerar solucodes basicas 1 Escolha m colunas linearmente independentes Agi Ap2ABm de A R 2 Coloque 0 para todos os 1 B1 B2 Bm m 3 Resolva S Api 6 que tem uma solugao tinica i1 Observe que e Pelo Teorema 87 podemos determinar todas as solugoes basicas utilizando o Procedimento acima e Se a solucao basica determinada acima tiver todas as coordenadas nao negativas ela vai ser uma solucao vidvel basica e Como toda solucao vidvel basica é uma solucao basica o procedimento acima também gera todas as solugoes vidveis basicas possiveis Definigao 88 Dada uma solugao basica FB TRG TBQ TBum R 6 chamada de variavel basica e todas as outras coordenadas juntas formam a variadvel nao basica a qual de notaremos por Zy R As colunas Api AB 2ABm 840 chamadas de colunas da base e B Aga Ag Apm amatriz da base Por fim o conjunto de indices B1 B2 Bm é chamado de base Observe que se tivermos a matriz da base podemos determinar a varidvel basica de uma forma simples resolvendo um sistema linear Bezpbrp Bob No mesmo exemplo escolhendo Ay A5AgA7 como sendo as colunas da base que claramente sao vetores linearmente independentes temos BA As Ag A7 IB Logo g Ib b 8 1246 que além de ser uma uma solucao basica 6 uma solucao vidvel basica Por outro lado escolhendo A3As5AgA7 como sendo as colunas da base que também sao vetores linearmente independentes temos 00 0 3 1 0 0 BA3 As Ag A B 0 00 1 24 Logo xB B1b 4 12 4 6T e uma solucao basica mas nao e uma solucao viavel basica Bases e Solucoes Basicas Solucoes basicas distintas sao resultantes de bases distintas Bases distintas podem resultar em solucoes basicas iguais por exemplo quando b 0 Definicao 89 Se duas bases tiverem ındices comuns exceto um unico ındice as bases sao chamadas de adjuntas De modo analogo duas solucoes basicas sao chamadas de adjuntas se forem definidas por bases adjuntas Exemplo Nos exemplos anteriores 0 0 0 8 12 4 6T e 0 0 4 0 12 4 6T sao solucoes basicas adjuntas 83 Degeneracao Definicao 810 Seja x Rn uma solucao basica para um problema de otimizacao linear na forma padrao x e chamada de uma solucao basica degenerada se existirem mais de n m coordenadas com zero Exemplo Considere o exemplo anterior e escolhamos A1 A2 A3 A7 como as colunas da base Entao a solucao basica correspondente sera x 4 0 2 0 0 0 6T que e uma solucao basica degenerada pois existem n m 1 7 4 1 4 zeros 84 Otimalidade dos pontos extremos Novamente iremos assumir o seguinte resultado sem provas Teorema 811 3 Dado um problema de otimizacao linear que minimiza a funcao cT x sobre um poliedro nao vazio entendase aqui que as restricoes descrevem um poliedro e existe pelo menos um vetor que satisfaz todas as restricoes o valor otimo e ou existe uma solucao otima com o valor otimo correspondente 85 Direcao viavel Definicao 812 Dado um x P um vetor d Rn diferente de zero e chamado de direcao viavel para x se existe um numero positivo θ tal que x θd P Observe que se x P entao Ax b e x 0 Se d e uma direcao viavel para x existe um θ 0 tal que Ax θd b e x θd 0 e por aqui concluımos que Ad 0 86 Exercıcios 1 Seja P x Rn Ax b x 0 o poliedro correspondente a um problema de otimizacao linear na forma padrao Suponhamos que todas as linhas de A Rmn sao linearmente indepen dentes Assuma tambem que existe uma funcao objetivo cT x Indique se as proxima afirmacoes sao verdadeiras ou falsas Em caso de ser verdadeira tente demonstrar Caso seja falsa mostre um contra exemplo a O conjunto de todas as solucoes otimas e um conjunto limitado b Se existem duas solucoes otimas distintas existe um numero infinito de solucoes c Para toda solucao otima x Rn nao e possıvel que existam mais que m coordenadas positivas 25 d O conjunto de todas as solugoes 6timas forma um conjunto convexo e Sen m1 entaéo P possui no maximo duas solugoes vidveis basicas 2 Determine todas as solugoes basicas do seguinte poliedro utilizando o procedimento que foi visto Identifique também quais delas sao solugdes vidveis basicas 2 322 4x3 12 PaER 10x x 403 2 x1 0 x2 0 r3 0 3 Determine todas as solucdes basicas do seguinte poliedro utilizando o procedimento que foi visto Identifique também quais delas sao solugoes vidveis basicas 4x1 5x2 23 3 621 6x2 7 P R Te 21 8224 20 x1 0 x2 0 x3 0 r4 0 4 Determine todas as solucoes basicas e todas as solucdes vidveis basicas do seguinte poliedro De termine também uma solucao basica adjacente a 05 15 L12 2 wj21 P R yk Te 301 309 3 xr 20 rg 20 9 Método Simplex Considere o problema de otimizacao linear minimizar 227 9 273 sujeito a 2 242 34 24 6 224 4x3 X5 4 41 3 13 27 1 U1 234U5 U6 0 onde n 6 e m 3 Além disso as linhas da matriz A correspondente sao linearmente independentes satisfazendo a Hipotise 86 Como vimos existe um base que é facil de se determinar B1 B2 B3 456 matriz da base BI 8B ea solucio viavel basica correspondente 000641 91 O processo de uma iteragao do método simplex Suponhamos que estamos numa iteracado do método simplex e possuimos as seguintes informacoes definidas na Definigao 88 x solugao vidvel basica B1 B2 Bm base B Ax ABQ2 ote Apm matriz da base Bé invertivel pela Hipétese 86 onde B1 B2Bm sao indices distintos que podem tomar o valor 12 Além disso sabemos que a solucao vidvel basica pode ser partido em duas varidveis a saber r rLB B1 7 B2 ee TBm Bb variavel basica ay onde ay 0 para i B1 B2Bm varidvel nao badsica 26 Consideremos um iteragéo onde queremos deslocar da solugcao vidvel basica para 0d ao longo da direcao vidvel d Definigao 812 e 0 I Como queremos que somente uma varidvel nao basica digamos xj se torne uma varidvel basica iremos proceder da seguinte forma LB ZLB dp dy j 1 r 6 onde 5 2 2 3 dyj O KAJ 5 Como ja vimos pelo observacao depois da Definicao 812 Ad 0 Portanto temos n m 0 Ad 5 Aid S Api dpyy Ss Ajd Bdg Aj i1 i1 kB1B2Bm Logo conclufmos que dg BA ER II Além disso queremos que 0 novo vetor ponto tenha coordenadas nao negativas x 0d 0 a A solugao vidvel bdsica x é nao degenerada Neste caso xg 0 e podemos achar um 6 0 suficientemente pequeno para o qual teremos xp 6dg 0c xy Ody e O vide 5 Logo basta verificar que a condicao 6dg azp seja satisfeita ou seja LR OF min 22 i12m dpi 0 dB 3 a A solugao vidvel bdsica x é degenerada Neste caso como uma coordenada de ag é igual a zero é possivel que 0 seja 0 III Quando a solucao vidvel basica x se desloca para x 0d ao longo da diregao vidvel d queremos que o valor da fungao objetivo diminua cla c a 6d cx6cd mas n m cd So cid S cpdaa Ss cred chdp Cj Cj chB Aj i1 i1 kB1B2Bm por causa de 5 e a definigao de dg Logo como 0 queremos que o valor c chBA 0 para o indice j escolhido Definicao 91 Seja x R uma varidvel vidvel bdsica B R a matriz da base correspondente e cp R o vetor correspondente a base da funcao objetivo Entao para um indice arbitrario 7 o valor Gj Ci chBA é chamado de custo reduzido Pelo que vimos faz sentido pensarmos nos indices 7 correspondentes a varidvel nao basica Porém podemos definir 0 custo reduzido para um indice correspondente a varidvel basica Neste caso temos 12m e CB Cay ch B Api Como BBTe B Apw e temos CBG CBi che CBi CBi 0 Finalmente resumindo o que discutimos aqui podemos definir uma iteracéo do método simplex como o cdlculo de uma nova varidvel vidvel basica y 6d com um possivel valor menor cy para o valor da fungao objetivo a partir de uma varidvel vidvel basica 2 com o valor da fungao objetivo igual a cx 27 92 O método simplex Uma iteragao do Método Simplex 1 Seja B Agi Ap Axm uma matriz da base x a solucao vidvel basica correspon dente e suponhamos que a inversa da matriz da base B é conhecida 2 Calcule o custo reduzido G cj chBA para todos os indices das varidveis nao basicas gj 12nB1 B2Bm Se todos os custos forem nao negativos x serd a solugao dtima e finalize caso contrario escolha um indice j tal que G 0 3 Calcule dg BA R Se todos os elementos forem nao negativos teremos 6 oo e definiremos o valor étimo como sendo oo e finalize 4 Se um dos componentes for negativo calcule x OF min 2 i12m dpi 0 dB i 5 Seja 2 12m 0 indice tal que 6 Ta Forme uma nova matriz da base substituindo Ap por Aj e y sera a nova varidvel vidvel basica onde yj e yay ZB Odpq para i 12me 12 Iteragao Realizemos uma iteracao aplicado ao exemplo que consideramos No passo 2 calculamos o custo reduzido Note que o custo reduzido é calculado somente para os indices que nao estao na base Ou seja 12e3 2 cachBA 2000F 2 2 4 2 cochBA 1000F 0 1 3 l Bc3chBAz 1000IT 4 1 l Note que eg cg1CB2B3 C45 55 C6 Como o custo reduzido é negativo para os indices 12 e 3 podemos escolher qualquer um Escolhamos o menor indice 7 1 por exemplo Agora calcularemos dg B1A do passo 3 2 2 dpI 2 2 4 4 onde observamos que existem duas coordenadas negativas Note que dg dgqdg2d53 d4d5dg e nao utilizaremos as outras coordenadas do d que sao dj dz e ds No passo 4 calculamos LBG x x i12m dey 0 dpa dpa 4B2 LA Xs 6 4 miny p min4s 7 2 da ds 2 2 28 Portanto no passo 5 o menor indice é 0 2 o que corresponde a B2 5 A nova solucao basica é calculada como y 06 2 yaa tpi daa ya T4 dy 6 2 2 2 YB3 B3 dps Yo V6 Odg 124 9 Observe que as outras componentes de y sao zeros pois sao varidveis nao basicas Logo y 200209 A nova base sera B1 B2 B3 416 e a nova matriz da base é 1 2 O BA A Ag 0 2 O 0 4 1 22 Iteragao Podemos continuar o processo Chamemos o y obtido no passo anterior de novamente No passo 2 calculamos o custo reduzido Note que o custo reduzido é calculado somente para os indices que nao estao na base Ou seja 2 3 e 5 12 02 cchBA 10 20 0 2 0 0 0 4 1 3 1 l1 O 2 1020 0 0 0 1 0 2 1 3 1 2 01 BcchBA3 10 20 0 2 0 4 0 4 1 1 1 l1 O l 1020 0 43 0 4 3 0 2 1 l 1 2 00 GcchBA 00 20 0 2 O 1 0 4 1 0 1 1 0 0 0020 0 4 0 1 1 0 2 1 0 Note que eg cg1CB2B3 C4 15 C6 Como o custo reduzido é negativo somente para o indice 2 s6 podemos escolher este indice j 2 Agora calcularemos dg B Ag do passo 3 1 1 0O 2 2 dg 0 4 0 0o 0 0 2 1 3 3 onde observamos que existem duas coordenada negativas Note que dg dg1da2 da3 da di de e nao utilizaremos as outras coordenadas do d que sao do d3 e ds No passo 4 calculamos LB x x i12m dpi O dB i dpa 43 LA LE 2 9 l min min d4 dg 2 3 Portanto no passo 5 o menor indice é 0 1 0 que corresponde a B1 4 A nova solucao basica calculada como yo 6 1 yg TB dpa yi 11 6dy 2410 2 29 yB3 xB3 θdB3 y6 x6 θd6 9 1 3 6 Observe que as outras componentes de y sao zeros pois sao variaveis nao basicas Logo y 2 1 0 0 0 6T A nova base sera B1 B2 B3 2 1 6 e a nova matriz da base e B A2 A1 A6 2 2 0 0 2 0 3 4 1 3a Iteracao Podemos continuar o processo Chamemos o y obtido no passo anterior de x novamente No passo 2 calculamos o custo reduzido Note que o custo reduzido e calculado somente para os ındices que nao estao na base Ou seja 34 e 5 c3 c3 cT BB1A3 1 1 2 0 2 2 0 0 2 0 3 4 1 1 1 4 1 1 1 2 0 1 2 1 2 0 0 1 2 0 3 2 7 2 1 1 4 1 1 2 c4 c4 cT BB1A4 0 1 2 0 2 2 0 0 2 0 3 4 1 1 1 0 0 0 1 2 0 1 2 1 2 0 0 1 2 0 3 2 7 2 1 1 0 0 1 2 c5 c5 cT BB1A5 0 1 2 0 2 2 0 0 2 0 3 4 1 1 0 1 0 0 1 2 0 1 2 1 2 0 0 1 2 0 3 2 7 2 1 0 1 0 1 2 Note que cB cB1 cB2 cB3T c2 c1 c6T Como nao existe nenhum valor negativo para o custo reduzido concluimos que x 2 1 0 0 0 6T e a solucao otima e o valor otimo correspondente e cT x 2 1 1 0 0 0 2 1 0 0 0 6 5 93 Comparacao com o metodo simplex tableau Vimos na Secao 7 um outro metodo de resolver um problema de otimizacao linear chamado metodo simplex tableau que requeriu basicamente as mesmas operacoes Uma vez que agora discutimos o metodo simplex na forma matricial podemos concluir que o metodo simplex tableau nada mais era do que o metodo simplex organizado numa tabela como podemos ver na Tabela 4 94 Ciclagem Vimos no metodo simplex que existe uma certa arbitrariedade quando escolhemos uma variavel que entra da base e posteriormente uma variavel que sai da base Iremos ver no exemplo que segue que uma escolha arbitraria pode levar a um loop infinito do metodo simplex 30 Table 4 Método simplex tableau com notacao matricial varidveis termos basicas at independentes tp B C CpxrB minimizar 2122 x3 sujeito a 2 234 274 0 321 22 x3 5 0 521 3x22 2x3 27 0 U1 23 045 06 2 0 onde n 6 e m 3 Considere inicialmente uma base trivial B1 B2 B3 45 6 com a matriz da base B I B e a solucdo vidvel basica correspondente 0000007 Apliquemos o método simplex 12 Iteragao 12 Calculando 0 custo reduzido temos 10 0 0 12 3 5 1 2000I113 2 1000111 2 1 Como podemos escolher entre os indices 1 e 3 pois os custos reduzidos sao negativos escolhemos 7 1 13 Calculando a direcdo basica vidvel temos dg I 23 5 2 35 que possui dois elementos negativos 14 Calculo do x x 0 0 pa mn 2m 02 yin f 2 OD oo daay 4502 2 38 15 Podemos escolher entre os indices 1 e 2 pois ambos resultam em 6 0 Escolhemos 2 e portanto B B2 5 A nova base sera B1 B2 B3 416 como y 0 ya 40dy 0 ye xg 0 dg 0 a nova varidvel vidvel bdsica serd y 0000007 e 1 2 O B0 3 0O 0 5 1 Notamos que a varidvel vidvel bdsica nao muda mas a base bem como a matriz da base mudaram 22 Iteragao 1 2 0 22 Calculando o custo reduzido temos 20 10 0 4 O 11 37 f B 0 3 1 1 2 0 1 2 0 1 1 11 225 1 L 10 4N 10 10 0 3 O 2 3600 10 0 3 O 010 3 Neste 0 2 1 0 2 1 caso escolhemos j 3 pois o custos reduzido é negativo 2 cos 7 I 3 0 T 1 11r 23 Calculando a diregao basica vidvel temosdg 0 3 O 112 3 3 x 0 3 1 que possui dois elementos negativos 31 24 Calculo do x x 0 0 Porn 00 HY ig f OY Ag dpa dB 303 25 Podemos escolher entre os indices 1 e 2 pois ambos resultam em 9 0 Escolhemos 1 e portanto B B1 4 A nova base sera B1 B2 B3 316 como ys 0 yr 41 0dy 0 ye v6 0 dg 0 a nova varidvel vidvel basica sera y 0000007 e 1 2 O B 1 3 O 2 5 1 Notamos que a varidvel vidvel bdsica nao muda mas a base bem como a matriz da base mudaram 32 Iteracao 32 0 32 Calculando o custo reduzido temos 21 10 1 1 0 113 1 1 1 1 32 0 3 2 0 01 10 1 1 0 100 2q01 10 1 1 0 010 1 1 1 1 1 1 1 Como podemos escolher entre os indices 2 e 5 pois os custos reduzidos sao negativos escolhemos 7 2 3 2 0 33 Calculando a diregio basica vidvel temosdg 1 1 0 1135 2 3 1 1 1 que possui dois elementos negativos 34 Calculo do x x 0 0 Cr ee ee dpa 4593 2 38 35 Podemos escolher entre os indices 2 e 3 pois ambos resultam em 6 0 Escolhemos 3 e portanto B B3 6 A nova base sera B1 B2 B3 31 2 como ye 0 y3 43 0d3 0 yo 20 dz 0 a nova varidvel vidvel bdsica serd y 0000007 e 1 2 l B 1 3 1 2 5 8 Notamos que a varidvel vidvel bdsica nao muda mas a base como a matriz da base mudaram 4 Iteracao i4 1 38 3 B 3 Tore 42 Calculando 0 custo reduzido temos 01 12 3 3 3 100 3q6 1 1 3 3 3 4 1 98 i4 1 38 3 3 3B 3 3 3B o1 12 2 4 2 010 2q01 12 3 4 2 01 3 yoda yrotiog 3 3 3 3 3 3 Neste caso escolhemos 7 5 pois o custos reduzido é negativo 14 1 5 3 3 38 43 Calculando a direcao basica vidvel temos dg 3 3 010 34 Ayr 1 1 3 3 3 que possui dois elementos negativos 44 Calculo do x x 0 0 Porn 80 HY gig OOD og dp 4573 373 32 45 Podemos escolher entre os indices 2 e 3 pois ambos resultam em 6 0 Escolhemos 2 e portanto B B2 1 A nova base sera B1 B2 B3 35 2 como ys 0 yg 3 0d3 0 yo v20 dy 0 a nova varidvel vidvel basica sera y 0000007 e 1 O 1l B 1 1 1 2 0 3 Notamos que a varidvel vidvel bdsica nao muda mas a base como a matriz da base mudaram 52 Iteracgao 30 1 52 Calculando o custo reduzido temos 1102 5 1 2 23 5 2qG 2 0 1 3 0 1 30 1 0 1 0 2 5 1 2 100 1 010 2 5 1 2 001 1 Como 2 0 1 2 0 1 podemos escolher entre os indices 4 e 6 pois os custos reduzidos sao negativos escolhemos j 4 3 0 1 53 Calculando a diregao basica vidvel temos dg 5 1 2 10 0 35 2 que 2 0 1 possui um elemento negativo 54 Calculo do TBI 0 gt BW 55 S6 existe a opcao de escolher o indice 1 que resulta em 6 0 Portanto Bf B1 3 A nova base seré B1 B2 B3 452 como ys 0 ys 750ds5 0 yo r20 dg 0a nova varidvel vidvel badsica sera y 0000007 e 1 0 1 B 01 1 00 8 Notamos que a varidvel vidvel bdsica nao muda mas a base como a matriz da base mudaram 62 Iteracao 10 3 62 Calculando o custo reduzido temos G 1 00 2 0 1 4 23 5 1Q 00 4 10 10 100 2 013 11 2 4q0002 013 0 0 1 2 Neste caso 00 4 00 4 escolhemos 7 6 pois o custos reduzido é negativo 10 63 Calculando a diregao basica vidvel temos dg 0 1 1 001 44 1 00 4 que possui dois elementos negativos 44 Calculo do 6 min oo 27a min 0 dpa 4593 3003 65 Podemos escolher entre os indices 1 e 3 pois ambos resultam em 6 0 Escolhemos 3 e portanto B B3 2 A nova base sera B1 B2 B3 456 como yg 0 ya 40dy 0 ys 250ds 0 a nova varidvel vidvel bdsica serd y 0000007 e 1 0 0 B 0 1 0 001 33 Notamos que a variavel viavel basica nao muda mas a base como a matriz da base mudaram E que voltarmos a situacao inicial Uma forma bem simples de evitar a ciclagem e utilizando a Regra de Bland Regra de Bland 1 Encontre o menor ındice j com o custo reduzido cj negativo 2 Entre as variaveis xBi com dBi negativo e que possuem a menor razao xBi dBi escolha o que tiver o menor ındice Bi Teorema 92 Considere um problema de otimizacao linear que minimiza a funcao cT x sobre uma regiao viavel nao vazia o que e equivalente a dizer que existe pelo menos um vetor que satisfaz todas as restricoes e que a Hipotese 86 esteja satisfeita Se aplicarmos o metodo simplex com a regra de Bland para este problema obteremos duas possibilidades em um numero finito de iteracoes a O valor otimo e ou b Existe uma solucao otima com o valor otimo correspondente 95 Exercıcios 1 Resolva o seguinte problema de otimizacao linear partindo da solucao viavel basica x1 x2 x3 x4 x5 x6 0 0 0 0 5 3 minimizar 2x1 3x2 5x3 4x4 sujeito a x1 2x2 3x3 x4 x5 5 x1 x2 2x3 3x4 x6 3 x1 x2 x3 x4 x5 x6 0 2 Resolva o seguinte problema de otimizacao linear partindo da solucao viavel basica x1 x2 x3 x4 x5 x6 0 0 4 3 5 1 minimizar 2x1 x2 sujeito a 2x1 x2 x3 4 2x1 3x2 x4 3 4x1 x2 x5 5 x1 5x2 x6 1 x1 x2 x3 x4 x5 x6 0 3 Resolva o seguinte problema de otimizacao linear partindo da solucao viavel basica x1 x2 x3 x4 x5 0 0 1 2 3 minimizar 2x1 2x2 sujeito a 3x1 x2 x3 1 x1 x2 x4 2 x1 x2 x5 3 x1 x2 x3 x4 x5 0 34 10 Método Simplex Revisado Se analizarmos o método simplex pelo ponto de vista computacional podemos verificar que os maiores custos computacionais por iteracao devese inversao da matriz Ble R que tipicamente custa Om mutiplicacdéo desta matriz B com uma coluna cg R e posteriormente com A R que custa Om e finalmente agregando tudo o custo para calcular o custo reduzido seria Omn Ou seja tipicamente terfamos Omn por iteragao pois m n O método simplex revisado é um método simplex que visa uma implementacgao mais eficiente que evita o custo da inversao da matriz de ordem m em cada iteracao Isto é possivel observando que a matriz B atual e a matriz B calculada no final desta iteracao diferem de uma coluna e portanto seria natural esperar que as inversas das duas matrizes estejam relacionadas Uma iteragao do Método Simplex Revisado 1 Sejam B Ax Apa Apm uma matriz da base e x a solucao vidvel basica corre spondente Suponha que temos a inversa da matriz da base B previsamente calculada 2 Calcule p chB e determine o custo reduzido Cj p A para todos os indices das varidveis nao basicas j 12nB1 B2Bm Se todos os custos forem nao negativos sera a solugao 6tima e finalize caso contrario escolha um indice 7 tal que G 0 3 Calcule dg BA R Se todos os elementos forem nao negativos teremos 6 oo e definiremos o valor étimo como sendo oo e finalize 4 Se um dos componentes for negativo calcule x O min 2 i12m dpi 0 dB i 5 Seja 12m o indice tal que 6 Tew y sera a nova varidvel vidvel basica onde yj O yBo TB dp parai 12mE 6 Seja B dg R1 Adicione em cada linha desta matriz multiplos da linha operagdes elementares de modo que a tltima coluna tornese igual a ey R As m primeiras colunas desta matriz seré a inversa da nova matriz da base B Aqui o Passo 6 precisa de uma explicagao Lembremos que j é 0 indice que entrara na base e B seré o indice que saird da base O procedimento Adicione em cada linha desta matriz multiplos da linha operagdes elementares de modo que a Ultima coluna tornese igual a eg R corresponde a multiplicar a matriz B dg pela matriz C definida abaixo pelo lado esquerdo dpa 1 dB 2 1 4302 dB 2 C nr 30 dpm dB 2 1 Lembrese que dpe 0 como foi definido no Passo 5 Teremos entao dg 0 dp 1 CB dpCB CazcB c eB cB eg ABe 0 35 Agora se chamarmos as m primeiras colunas da matriz acima de B teremos BACBA e 1 B Api CB Api Ce i 1m ne Logo podemos concluir que B é a inversa da nova matriz da base B pois 15 1 B BB Aga Aggy Apie1 Ay Apcei Apm 1 2 e1 e v41 Em No método simplex revisado assumimos que antes da primeira iteracdo temos a inversa B disponivel O custo computacional por iteracdo seria Om para calcular o produtos entre uma matriz e um vetor c B Omn para calcular os custos reduzidos G cj p Aj Om para calcular dg BA e finalmente Om para calcular o produto entre as matrizes C e B Ou seja como m n Omn por iteragao Considere o mesmo problema de otimizacao linear considerado no método simplex minimizar 227 9 273 sujeito a 2 242 34 24 6 224 4x3 5 4 41 3 13 27 1 U1 02 0304 U5 V6 2 0 onde n 6 e m 3 Além disso as linhas da matriz A correspondente sao linearmente independentes satisfazendo a Hipotise 86 Como vimos existe uma base bem simples B1 B2 B3 456 a matriz da base B I B correspondente e a solucao vidvel basica 2 00 06 41 correspondente 12 Iteragao No passo 2 calculamos o custo reduzido Primeiramente p chB 1 000I000 De modo que o custo reduzido para os indices que nao estao na base 1 2 e 3 sao Gcap Ay 2 copA 1 c3p Az 1 Note que eg cg1CB2B3 C4 55 C6 Como o custo reduzido é negativo para os indices 12 e 3 podemos escolher qualquer um Podemos utilizar a regra de Bland e escolher o menor indice 7 1 Agora calcularemos dg BA do passo 3 2 2 dpI 2 2 4 4 onde observamos que existem duas coordenadas negativas Note que dg dgqdp2da3 d4d5dg e nao utilizaremos as outras coordenadas do d que sao dj dz e ds No passo 4 calculamos LB x x min 22 min 3 2B i12m dey 0 dpa dpa 4B2 LA Xs 6 4 miny p min4s 7 2 da ds 2 2 36 Portanto no passo 5 o menor indice é 0 2 o que corresponde a B2 5 A nova solucao basica é calculada como y 06 2 yaa tpi daa ya T4 dy 6 2 2 2 YB3 B3 dps Yo V6 Odg 124 9 Observe que as outras componentes de y sao zeros pois sao varidveis nao basicas Logo y 200209 A nova base sera B1 B2 B3 416 e a nova matriz da base é 1 2 O BA A Ag 0 2 O 0 4 1 Apliquemos o Passo 6 ou seja 23a 4B 0 l dp2 Zoe B 2 1 0 1 1 0 BCB T04 00 4 0 dae 04 1 0 2 1 den dBe 1 22 Iteragao Podemos continuar o processo Chamemos o y obtido no passo anterior de novamente No passo 2 calculamos o custo reduzido Primeiramente 1 1 0O p cpB0 20 0 4 O 10 0 2 1 Note que o custo reduzido é calculado somente para os indices que nao estao na base Ou seja 2 3 e 5 2 cgpAy 10 10 0 1 3 1 Bc3pA 10 10 4 3 1 0 Gc5pAs 00 10 1 1 0 Note que eg cg1CB2B3 C4 15 C6 Como o custo reduzido é negativo somente para o indice 2 s6 podemos escolher este indice j 2 Agora calcularemos dg B Ag do passo 3 1 1 0O 2 2 dg0 0 0o 0 0 2 1 3 3 onde observamos que existem duas coordenada negativas Note que dg dg1 4g2 4p3 da di de e nao utilizaremos as outras coordenadas do d que sao do d3 e ds No passo 4 calculamos LB x x min 22 min 20 2 i12m dpi O dB i dpa 43 LA LE 2 9 l min min d4 dg 2 3 37 Portanto no passo 5 o menor indice é 0 1 0 que corresponde a B1 4 A nova solucao basica calculada como y2 6 1 yp TB2 dpa yi 1 Ody 2410 2 YB3 B3 Odg3 yo te Odg 9 1 3 6 Observe que as outras componentes de y so zeros pois so varidveis nao basicas Logo y 210006 A nova base serd B1 B2 B3 216 e a nova matriz da base é 2 2 O BA2 A Ag 0 2 O 34 1 Apliquemos o Passo 6 ou seja 1 1 1 0 0 1 1 0 5 3 O B 4 10 0 7 OJ 0 F 0 3 3 301 0 2 1 8 f 4 32 Iteracao Podemos continuar o processo Chamemos o y obtido no passo anterior de novamente No passo 2 calculamos o custo reduzido Primeiramente 1 1 g 2 2 1 1 p cpB120 0 0 0 3 2 2 2 2 2 Note que o custo reduzido é calculado somente para os indices que nao estao na base Ou seja 34 e 5 l 1 1 1 T c3p A3 l 4 c3 c3 p Az 579 0 5 l 1 1 1 1 Gap A 0 0 0 F 2 2 2 0 0 1 1 1 T cp Ars O0 0 1 C5 C5 p 445 9 9 3 0 Note que cg cB1 B2 B3 c2 1 ce Como nao existe nenhum valor negativo para o custo reduzido concluimos que x 2 100 06 é a solucao 6tima e o valor 6timo correspondente é 2 1 T 0 c 2 1 1000 0 5 0 6 101 Exercicios 1 Execute o método simplex revisado para os problemas na subsecaéo 95 e compare 38 11 Calculo da Solucao Viavel Basica Inicial 111 Transformando o problema na forma padrao 1111 Maximizacao da funcao objetivo O caso mais facil e este onde precisaremos inverter o sinal dos coeficientes da funcao objetivo Considere o seguinte exemplo maximizar 8x1 15x2 sujeito a 3x1 5x2 x3 15 5x1 2x2 x4 10 x1 x2 x3 x4 0 cuja solucao otima e x 1 x 2 x 3 x 4 0 3 0 4 e valor otimo igual a 45 Este problema e equivante ao problema minimizar 8x1 15x2 sujeito a 3x1 5x2 x3 15 5x1 2x2 x4 10 x1 x2 x3 x4 0 cuja solucao otima tambem e x 1 x 2 x 3 x 4 0 3 0 4 mas o valor otimo igual a 45 1112 Problemas com desigualdades Considere o problema minimizar 8x1 15x2 sujeito a 3x1 5x2 15 5x1 2x2 10 x1 x2 0 cuja solucao otima e x 1 x 2 0 3 e valor otimo igual a 45 Este problema pode ser transformado num problema de otimizacao linear na forma padrao adicionando as variavies de folga x3 e x4 minimizar 8x1 15x2 sujeito a 3x1 5x2 x3 15 5x1 2x2 x4 10 x1 x2 x3 x4 0 cuja solucao otima e x 1 x 2 x 3 x 4 0 3 0 4 e o valor otimo igual a 45 Lembrese que a solucao otima do problema original e igual a x 1 x 2 0 3 pois x3 e x4 foram adicionadas 1113 Variaveis livres Considere o problema minimizar x1 x2 sujeito a x1 x2 2 1 1 3x1 x2 1 x1 x2 R 6 Note que x1 e x2 podem ser negativos zeros ou positivos Podemos transformar o problema 6 utilizando as seguintes substituicoes x1 x 1 x 1 e x2 x 2 x 2 Ou seja minimizar x 1 x 1 x 2 x 2 sujeito a x 1 x 1 1 2x 2 1 2x 2 x3 1 1 3x 1 1 3x 1 x 2 x 2 x4 1 x 1 x 1 x 2 x 2 x3 x4 0 7 39 o qual uma solucao étima é x7 x7 wF ay v5 xj 0 2 z 0 00 que corresponde ao valor 6timo 2 Uma solucao étima de 6 seria xj 75 2 a e seu valor 6timo 2 112 O método simplex de duas fases Aplicando as operacgées acima descritas podemos transformar qualquer problema de otimizacao linear na forma padrao que é um formato ideal para aplicarmos o método simplex mimimizar cl x sujeitoa Axb 3 xz 0 O Método Simplex de Duas Fases Fase I 1 Multiplique cada restrigao por 1 se necessario para se obter b O no problema de otimizacao linear na forma padrao 3 2 Adicione variadveis artificiais yj y2m caso necessario e resolva o problema auxiliar T mimimizar ey sujeito a AxIyb xy 0 onde e 111 utilizando o método simplex 3 Seo valor 6timo do problema auxiliar for positivo o problema original nao possui solucao viadvel a regiao vidvel é vazia e finalize 4 Se o valor 6timo do problema auxiliar for zero encontramos uma solucao vidvel para o problema original Caso as varidveis artificiais nao estiverem na base podemos eliminar todas as colunas e todas as varidveis correspondentes as varidveis artificiais Encontramos uma solugao vidvel inicial para o problema original 5 Se a ésima base B corresponder a uma varidvel artificial examine a ésima linha de todos os vetores BA R para j 12n Se todos os elementos forem iguais a zero a éésima linha representa uma restricao redundante e pode ser eliminada Caso contrario se a éésima linha de B TA para algum j 12n for diferente de zero aplique a mudanga de base para retirar a ésima varidvel basica e incluir a varidvel x na base Repita esta operagao até que todas as variaveis artificiais saiam da base Fase II 1 Considere a base obtida no final da Fase I como sendo a base inicial da Fase II que jd nao contém varidveis artificiais 2 Calcule o custo reduzido de todas as varidvies para esta base inicial utilizando os coeficientes da fungao objetivo do problema original 3 Aplique o método simplex para o problema original No Passo 3 da Fase I acima finalmente temos um teste para decidir se um problema de otimizacao linear tem regiao vidvel nao vazia ou vazia nao existem valores para as varidveis para que estas satisfagam todas as restrig6es No Passo 5 da Fase I acima quando detectamos que a fésima linha de todos os BA sao iguais a zero para j 12m a linha do problema original é redundante E portanto podemos garantir 40 que a Hipotese 86 e garantida no final deste procedimento Assim o metodo simplex de duas fases e completo porque consegue determinar se um problema de otimizacao linear tem uma regiao viavel vazia caso contrario consegue eliminar equacoes restricoes redundantes e assim satisfazer a Hipotese 86 na Fase II o metodo ou termina com o valor otimo ou um valor otimo finito e uma solucao otima sao determinados 113 O metodo do M grande Um metodo um pouco mais didatico que pode ser usado para determinar uma solucao viavel inicial e o metodo do M grande Nele um numero extremamente grande M e utilizado para penalizar as variaveis artificiais O numero M nao deve ser tratado como um numero na implementacao mas sim como um sımbolo Assim o objetivo agora sera minimizar a seguinte funcao objetivo cT x MeT y em vez de cT x no problema original ou eT y na Fase I do metodo simplex de duas fases Exemplo Considere o problema de otimizacao linear minimizar x1 x2 x3 sujeito a x1 2x2 3x3 3 x1 2x2 6x3 2 4x2 9x3 5 3x3 x4 1 x1 x2 x3 x4 0 e considere o problema auxiliar correspondente com as variaveis artificiais y1 y2 y3 e y4 minimizar x1 x2 x3 My1 y2 y3 y4 sujeito a x1 2x2 3x3 y1 3 x1 2x2 6x3 y2 2 4x2 9x3 y3 5 3x3 x4 y4 1 x1 x2 x3 x4 y1 y2 y3 y4 0 Utilizemos o metodo simplex tableau para a nossa explicacao conforme a Tabela 4 da subsecao 93 A base inicial corresponde a variaveis y1 y2 y3 y4 onde n 8 e m 4 O tableau correspondente esta logo abaixo lembrando que a ultima linha do tableau correspondende ao custo reduzido cj cj cT BB1Aj com o sinal trocado ou seja cj cB M M M MT e B I neste caso variaveis termos basicas x1 x2 x3 x4 y1 y2 y3 y4 independentes y1 1 2 3 0 1 0 0 0 3 y2 1 2 6 0 0 1 0 0 2 y3 0 4 9 0 0 0 1 0 5 y4 0 0 3 1 0 0 0 1 1 C 1 8M 1 21M 1 M 0 0 0 0 11M Tornaremos x4 uma variavel basica e y4 variavel nao basica variaveis termos basicas x1 x2 x3 x4 y1 y2 y3 y4 independentes y1 1 2 3 0 1 0 0 0 3 y2 1 2 6 0 0 1 0 0 2 y3 0 4 9 0 0 0 1 0 5 x4 0 0 3 1 0 0 0 1 1 C 1 8M 1 18M 1 0 0 0 0 M 10M 41 Tornaremos x3 uma varidvel basica e x4 varidvel nao basica varidveis termos basicas x1 x2 x3 LA Yr Yo YB YA independentes Y1 1 2 0 l 1 0 O l 2 Yy2 1 2 0 2 0 1 O 2 0 Y3 0 4 0 3 0 0 1 3 2 x3 0 0 1 4 0 0 0 4 4 C 1 8M1 0 36M 0 0 0 37M 4M 3 Tornaremos x2 uma varidvel badsica e y2 varidvel nao basica varidveis termos basicas Ly r 23 LA YI yo Y3 YA independentes I Q 0 0 1 1 l1 O 1 2 re 1 0 1 0 0 1 0 y3 2 0 0 1 0 2 1 1 2 3 0 0 1 4 0 0 0 4 C 4M 5 0 0 2M3 0 54M 0 M3 4M 3 Tornaremos x1 uma varidvel badsica e y varidvel nao basica varidveis termos basicas 2 2 23 24 YI Yy2 Y3 YA independentes foro Fo go 4 1 Y3 0 0 0 O 1 1 1 0 0 v3 0 0 1 0 0 0 4 4 Cc 0 0 0 fF 72M 72M 0 7M 5 Tornaremos x4 uma varidvel basica e x3 varidvel nao basica varidveis termos basicas 21 23 4 YI yo y3ya independentes v9 0 1 2 0 i 0 0 2 Y3 0 0 O O 1 1 1 0 0 x4 0 0 3 1 0 0 0 1 1 C 0 0 0 32M 72M 0 M i Como todos os valores da ultima linha sao nao positivos o método termina aqui com a solucaéo étima x7 5 2324 5 3 0 1 valor 6timo igual a t Verificamos também que existe uma varidvel artificial y3 basica mas ela tem valor igual a 0 Assim o método do M grande também consegue resolver um problema de otimizacao linear por completo Se uma varidvel artificial for positiva no final o problema de otimizacao linear tem uma regiao vidvel vazia caso contrario se esta varidvel artificial for igual a zero 6 um indicativo que existem equacoes restrigdes redundantes que podem ser eliminadas e assim satisfazer a Hipdtese 86 se o método continuar ou termina com o valor 6timo co ou um valor 6timo finito e uma solucao étima 114 Exercicios 1 Coloque os seguintes problemas na forma padrao maximizar 22x1 4x9 8x3 sujeito a 21 29 6 a xr x3 4 222 x3 8 U1 23 0 42 b minimizar 2x1 x2 sujeito a x1 2 x1 4 x2 2 x2 4 x1 x2 0 c maximizar x1 x2 2x3 sujeito a x1 x2 5 x2 3x3 8 x1 x3 4 x2 x3 0 2 Resolva os seguinte problemas utilizando o metodo simplex de duas fases ou o metodo do M grande a maximizar 2x1 3x2 3x3 x4 2x5 sujeito a x1 3x2 4x4 x5 2 x1 2x2 3x4 x5 2 x1 4x2 3x3 1 x1 x2 x3 x4 x5 0 b minimizar 3x1 x2 3x3 x4 sujeito a x1 2x2 x3 x4 0 2x1 2x2 3x3 3x4 9 x1 x2 2x3 x4 6 x1 x2 x3 x4 0 12 Teoria de Dualidade 121 Introducao a dualidade Ate agora vimos que o problema de otimizacao linear consiste num problema que pode ser descrito como por exemplo maximizar x1 2x2 sujeito a x1 5x2 18 2x1 x2 15 5x1 2x2 20 x2 8 x1 x2 0 8 Em matematica existe um conceito chamado de dualidade que explica a relacao do problema com o seu par por um outro ponto de vista Isto se aplica tambem ao problema de otimizacao linear No caso o problema dual correspondente a 8 sera como segue e como podese ver e tambem um problema de otimizacao linear minimizar 18y1 15y2 20y3 8y4 sujeito a y1 2y2 5y3 1 5y1 y2 2y3 y4 2 y1 y2 y3 y4 0 9 Observer que o problema 8 possui 2 variaveis e 4 desigualdades que nao sao as de nao negatividade enquanto 9 possui 4 variaveis e 2 desigualdades Esta relacao nao e uma coincidˆencia Alem disso um simples calculo mostra que uma solucao otima de 8 e x 1 x 2 136 27 70 27 com o valor otimo 92 9 enquanto que uma solucao otima de 9 e y 1 y 2 y 3 y 4 4 9 0 1 9 0 e o valor otimo e igual a 92 9 Novamente o fato do valor otimo do problema primal 8 ser igual ao valor otimo do dual 9 nao e uma coincidˆencia 43 122 Interpretacao econˆomica das variaveis duais Considere o seguinte exemplo Uma industria dispoe de 3 recursos A B e C em quantidades limitadas Com estes recursos esta industria pode produzir 2 tipos de produtos produto I e produto II conforme as limitacoes dadas na tabela a seguir disponibilidade recursos gasto para recursos unidades produzir uma unidade do produto I produto II A 14 1 2 B 9 1 1 C 56 7 4 O produto I quando vendido traz um lucro de 5 e o produto 2 de 6 por unidade Para sabermos o melhor planejamento da producao podemos resolver o seguinte problema de otimizacao linear maximizar 5x1 6x2 sujeito a x1 2x2 14 x1 x2 9 7x1 4x2 56 x1 x2 0 Por outro lado a mesma industria possui a alternativa de vender os produtos A B e C em vez de produzir os produtos I e II Portanto definindo y1 valor do recurso A por unidade y2 valor do recurso B por unidade y3 valor do recurso C por unidade o valor total do estoque que esta industria tem e 14y1 9y2 56y3 Por outro lado sabemos que o produto I quando produzido deve fornecer no mınimo um lucro de 5 Ou seja considerando a quantidade de produtos A B e C que sao necessarias para produzir o produto I temos y1 y2 7y3 5 De modo similar temos para o produto II 2y1 y2 4y3 6 Logo para determinar o valor mınimo do estoque total desta industria teremos que resolver o seguinte problema de otimizacao linear minimizar 14y1 9y2 56y3 sujeito a y1 y2 7y3 5 2y1 y2 6 y1 y2 y3 0 Aqui podemos interpretar que a solucao otima do problema de otimizacao linear acima sera o valor mınimo pelo qual podemos vender os recursos A B e C para que a venda dos recursos seja uma alternativa melhor do que produzir os produtos I e II Portanto concluimos que o dono da industria podera vender os produtos A B e C se os valores forem maiores que a solucao otima do problema acima 44 123 O problema dual Dado um problema primal de otimizacao linear no seguinte formato minimizar cT x sujeito a aT i x bi i M1 aT i x bi i M2 aT i x bi i M3 xj 0 j N1 xj 0 j N2 xj R j N3 10 onde a matriz A da restricao e definida como A aT 1 aT 2 aT m A1 A2 An M1 M2 M3 1 2 m N1 N2 N3 1 2 n com todos os conjuntos disjuntos O problema dual correspondente ao problema primal acima e definido como maximizar bT y sujeito a yi 0 i M1 yi 0 i M2 yi R i M3 AT j y cj j N1 AT j y cj j N2 AT j y cj j N3 11 Portanto a partir do problema primal ou dual podemos construir o problema dual ou primal correspondente utilizando a seguinte tabela problema primal minimizar maximizar problema dual bi 0 restricoes bi 0 variaveis yi bi R 0 cj variaveis xj 0 cj restricoes R cj Exemplos Considere o seguinte problema de otimizacao linear que consideraremos como sendo o problema primal maximizar 2y1 y2 2y3 sujeito a y1 y2 y3 1 y1 y3 2 y2 3y3 1 y1 0 y2 0 y3 R O problem dual correspondente e minimizar x1 2x2 x3 sujeito a x1 x2 2 x1 x3 1 x1 x2 3x3 2 x1 R x2 0 x3 0 45 Agora consideremos problemas em notacao matricial O problem dual correspondente ao problema primal na forma padrao minimizar cx minimizar cx sujeitoa Axb ouseja sujeitoa ala b i12m xz 0 xj 20 j 12n é igual a T T maximizar Db y maximizar Db y sujeito a Alyc pois sujeito a yiER 412m y eR Aly c j12n Por outro lado o problem dual correspondente ao problema primal na forma candnica minimizar cl x minimizar c sujeitoa Axb ouseja sujeittoa alab i12m xz 0 xj 20 j 12n é igual a T oo T maximizar Db y maximizar Db y sujeito a Aly e pois sujeito a ys 0 712m y 0 Avy cj j12n 124 Teoremas de dualidade Teorema 121 Teorema fraco de dualidade Sejam R uma solucao vidvel de 10 e y R uma solucao vidvel de 11 Entao a seguinte desigualdade é valida by c Proof Sejam z R e y R os vetores que satisfazem as condicdes da hipdtese Note que ai zb 0 yj 0 parai Mi e portanto al by 0 para i M De modo similar notamos que a mesma desigualdade vale para i M2 oui M3 Por outro lado 0 e ej AVy 0 para 7 N de modo que c Aly 0 para 7 Ny De modo similar notamos que a mesma desigualdade vale para 7 No ou 7 N3 Juntando estas informacoes temos T T 0s Sl afebiym SE eG APD 1M1UM2UM3 JENUN2UN3 7 Ta To ee Sone alan alan t1MUM2UM3 JENUN2UN3 t1MUM2UM3 JENUN2UN3 bycH como queriamos 1 Corolario 122 a Se o valor 6timo do problema primal 10 for igual a oo ou seja ilimitado inferiormente entao o problema dual 11 nao tem solucao vidvel b Se o valor 6timo do problema dual 11 for igual a 00 ou seja ilimitado superiormente entao o problema primal 10 nao tem solugao vidvel Um resultado de extrema importancia é 0 teorema de dualidade forte que veremos a seguir A prova dele pode ser feita por diversos caminhos Entre eles podemos utilizar o Lema de Farkas 412 por exemplo 46 Teorema 123 Teorema Forte de dualidade Se um problema de otimizacao linear tem uma solucao otima entao o problema dual correspondente tambem possui solucao otima e os valores otimos corre spondentes sao iguais Uma implicacao importante do teorema de dualidade e que os problemas de otimizacao linear podem ser completamente resolvidos pelo metodo simplex tanto na forma primal como na forma dual Ja vimos que o metodo simplex pode terminar com trˆes possibilidades diferentes regiao viavel vazia problema ilimitado e existˆencia da solucao otima O Table 5 resume estes fatos onde so podemos ter quatro possibilidades Table 5 primal dual problema primal problema dual valor otimo finito funcao objetivo ilimitada regiao viavel vazia valor otimo finito possıvel impossıvel impossıvel funcao objetivo ilimitada impossıvel impossıvel possıvel regiao viavel vazia impossıvel possıvel possıvel Exemplo E possıvel que ambos os problemas primal e dual possuirem regioes viaveis vazios Considere o seguinte problema primal minimizar x1 2x2 sujeito a x1 x2 1 2x1 2x2 3 cujo problema dual correspondente e maximizar y1 3y2 sujeito a y1 2y2 1 y1 2y2 2 e nao existem variaveis x1 x2 y1 e y2 que satisfacam os restricoes simultaneamente 125 Condicoes complementares das folgas O seguinte teorema proporciona uma importante relacao entre as solucoes otimas dos problemas primal e dual Teorema 124 Condicoes complementares das folgas Sejam x Rn e y Rm pontos viaveis do problema primal 10 e problema dual 11 respectivamente Estes pontos sao solucoes otimas dos respectivos problemas se e somente se yiaT i x bi 0 i M1 M2 M3 cj yT Ajxj 0 j N1 N2 N3 Exemplo Iremos ilustrar como podemos utilizar o teorema acima e provar que um solucao viavel basica e de fato uma solucao otima Considere os problemas primal e o dual correspondente minimizar 13x1 10x2 6x3 sujeito a 5x1 x2 3x3 8 3x1 x2 3 x1 x2 x3 0 maximizar 8y1 3y2 sujeito a 5y1 3y2 13 y1 y2 10 3y1 6 47 O ponto x 1 0 1T claramente e um ponto viavel para o problema primal e o valor da funcao objetivo cT x e igual a 19 Agora utilizemos o teorema das condicoes complementares das folgas Como o problema primal tem restricoes de igualdades as condicoes yiaT i x bi 0 sao automaticamente satisfeitas Vejamos portanto a outra condicao complementar cj yT Ajxj 0 para os ındices de x que nao sao zeros Ou seja 13 5y1 3y2 1 6 3y1 1 0 Assim obtemos duas equacoes cuja solucao e y1 2 e y2 1 Observe que estes valores tambem satisfazem a outra restricao y1 y2 10 Logo pelo teorema x 1 0 1T e uma solucao otima do problema primal e y 2 1T e uma solucao otima do problema dual Alem disso o valor da funcao objetivo do problema dual e 19 que e igual ao do problema primal 126 Exercıcios 1 Determine o problema dual correspondente a minimizar 3x1 2x2 x3 sujeito a 2x1 3x2 x3 1 2x1 3x2 8 x1 x2 x3 0 2 Considere o problema de otimizacao linear na forma padrao minimizar cT x sujeito a Ax b x 0 Mostre que o problema dual do problema dual do problema na forma padrao e exatamente igual ao problema original 3 Escreva o problema dual correspondente ao seguinte problema maximizar x1 x2 x3 sujeito a 2x1 x2 2x3 2 4x1 2x2 x3 2 x1 x2 x3 0 e inspecione a otimalidade dos seguintes pontos viaveis x 0 2 3 2 3T para o problema primal e y 1 3 1 3T para o problema dual 13 Metodo Simplex Dual Considere o problema de otimizacao linear na forma padrao minimizar cT x sujeito a Ax b x 0 e seu dual correspondente maximizar bT y sujeito a AT y c y Rm Lembremos que a Tabela 4 mostrava a relacao do metodo simplex com o metodo simplex tableau Table 4 Metodo simplex tableau com notacao matricial variaveis termos basicas xT independentes xB B1A B1b C cT cT BxB 48 Aqui estamos considerando que temos uma base de indices B B1 B2 Bm e a matriz da base correspondente B Agi Agi Apim Denotemos por N N1 N2Nnm todos os indices que nao estao na base B Entaéo podemos fazer uma particao do vetor c R em cp R e cy R a matriz de restricdes A R em B R ce An RmXnm Assim reordenando as colunas da varidvel 2 R de modo que as varidveis bdsicas aparecam primeiro e substituindo y cB obtemos a Tabela 6 Table 6 Método simplex dual tableau com notacéo matricial onde as coordenadas da varidvel 2 R foram reordenadas varidveis termos basicas xh xh independentes mp 5 Nos métodos simplex e simplex revisado assumimos que Bb 0 e que as iteracdes terminavam quando o custo reduzido y ch y Ay 0 Em vez disso assumamos que na iteracao atual temos c y A 0 0 que corresponde a dizer que a varidvel y R é um ponto vidvel para o problema dual e que Bb nao necessariamente seja nao negativo Isso equivale a dizer que estamos executando o método simplex para o problema dual mantendo a viabilidade do problema dual e tentando maximizar a funcao objetivo do problema dual Uma iteragao do Método Simplex Dual Revisado 1 Sejam B Agi Ap Axm uma matriz da base 2 RR a varidvel do problem primal e y R a varidvel do problema dual tal que o custo reduzido Cy ch y An seja nao negativo Suponha que temos a inversa da matriz da base B previsamente calculada 2 Examine os componentes do vetor Bb ag Se todos os valores forem nado negativos x sera uma solucao 6tima do problema primal y uma solucao 6tima do problema dual e finalize caso contrario escolha um indice 12m tal que xpi 0 3 Considere a ésima linha da matriz BA R que denotaremos por v1V2Un Se vu 0 para t 127 o valor é6timo do problema dual é igual a 00 e finalize 4 Se existir um componentes negativo digamos uv 0 calcule G y min 0 i12n viO Ui 5 Seja 7 12n 0 indice tal que n 2 A coluna Age saira da matriz da base B e no seu lugar entrard a coluna A 6 Seja BA R Adicione em cada linha desta matriz multiplos da linha operacées elementares de modo que a coluna correspondente a v ou seja B TA tornese igual a eg R Aqui o Passo 6 precisa de uma explicacao Lembremos que B é 0 indice que entrard na base e j seraé o indice que saira da base O procedimento Adicione em cada linha desta matriz multiplos da linha operagdes elementares de modo que a coluna correspondente a v tornese igual a eg R corresponde a multiplicar a matriz BA R pela matriz D definida abaixo pelo lado esquerdo 49 onde d BAj 1 Bu l 25 J D ve Up 4B m 1 vj A coluna que possui varios valores diferentes de 0 e 1 é a ésima coluna Observe que pela notacao dpe vj 0 como foi definido no Passo 5 Teremos entao DBA DBA BA B Aj BA BAj4 BA DBA DBA DBAj ee DBAj DBA Considere 0 seguinte problema de otimizacao linear minimizar 21 9 sujeito a 1 2x2 x3 2 U1 tq 1 X12304 0 e o problema dual correspondente maximizar 2y y2 sujeito a Ytye 1 2y1 1 Y1 Y2 0 1 2 1 O oe onde n 4e m 2 Além disso as linhas da matriz A 10 0 1 828 linearmente independentes satisfazendo a Hip6otise 86 12 Iteragao No Passo 1 considere a base B1B2 34 e a matriz da base B I B corre spondente Ainda N N1 N2 12 Assim podemos calcular 2g Bb 1 d 00 217 duzido ch chBAn 1 1 1 o que corresponde a x 0021 e 0 custo reduzido cy cp n 11 1 0 1 2 T Ls 0 0 01 ti 1 1 0 Assim estamos nas condigdes de aplicar o método simplex dual No Passo 2 existem dois indices que podem ser escolhidos 1 ou 2 para o qual rp 0 Escolhemos 1 pela regra de Bland e precisamos determinar a primeira linha da matriz BA no Passo 3 1 O 1 2 1 O 1 2 1 0 BA 5 LCs 0 0 D1 onde a linha 1 sé tem componentes negativos na primeira e segunda colunas No Passo 4 calculamos G 1 1 1 a min min4 i12n v70 Ui l 2 2 50 Portanto a coluna j 2 entrard na base no lugar de B1 3 pelo Passo 5 Assim a nova base sera B B1 B2 24 e a nova matriz da base sera 2 O Baa ay2 9 Apliquemos o Passo 6 ou seja 1 O 2 2 dBA 0 5 a e consideremos a primeira coluna na matriz D 1 23 J l 22 J B DB oS Bo cr dBm 1 vj 1 1 O 1 0O 3 0 31 0 1 0 1 22 Iteragao No Passo 1 considere a base B1 B2 24 e a inversa da matriz da base calculada anterior 1 mente Ainda N N1N2 13 Assim podemos calcular 2g Bb 6 jy 0 que corresponde a x 0101 e 0 custo reduzido 1 5 O 1 l 11 T Tpl 3 22so97 hetayaco004 1 f doe No Passo 2 s6 existe uma opgao de escolher 2 para o qual rpg 0 Precisamos determinar a segunda linha da matriz BA no Passo 3 1 1 1 s 0 1 2 1 0O 5 1 5 0 laj 2 2 2 BvA 2 C6 0 45 0 I onde a linha 2 sé tem um componente negativo na primeira coluna No Passo 4 calculamos a min min i12n v7O Ui l 2 Portanto a coluna j 1 entrard na base no lugar de B2 4 pelo Passo 5 Assim a nova base sera B B1 B2 21 e a nova matriz da base sera 2 1 Baa ay2 1 Apliquemos o Passo 6 ou seja 1 1 1 9g 1 1 Bla 2 2 tera4 2 e consideremos a segunda coluna na matriz D 51 1 dB vj dp 2 1 a B DB oe Bo Up EBm l Uj 4 1 1 1 14 2 i2 2 0 0 l 0 1 32 Iteracao No Passo 1 considere a base B1 B2 21 e a inversa da matriz da base calculada anterior 1 1 1 1 9 mente Ainda N N1 N2 34 Assim podemos calcular 2g Bb F i 1 1 4 o que corresponde a a 1 00 e o custo reduzido 1 1 t 1 1 0 11 T T pl T cpB An 0011 2 2 0 ch ehB Ax 000 5 01 22 No Passo 2 como xg 0 podemos concluir que x 1 50 0 é a solucao é6tima do problema primal com o valor 6timo igual a ce a 3 ey cpB 5 5 é a solugao étima do problema dual 131 Quando devemos usar 0 método simplex dual Como jd tinhamos visto um problema de otimizacao linear pode ser resolvido eficientemente se uti lizarmos o método simplex revisado Fica a pergunta entao se vale a pena utilizar o método simplex dual revisado Existem alguns casos em que é mais eficiente utilizarmos o segundo método como por exemplo e Devido ao ntmero de varidveis n ntimero de restrigoes de igualdade m e a esparsidade dos dados o método simplex dual revisado pode ser mais eficiente e Temos facilmente um solucao vidvel basica dual Por exemplo suponhamos que encontramos uma solugao 6tima 2 para o problema primal de um problema de otimizagao linear a solucao y para o problema dual e que queremos resolver o mesmo problema para um vetor 6 diferente do b original Neste caso como g Bb pode ser possivel que a solucdo 6tima obtida nao seja vidvel para o novo 6 Porém A y c é valido e o problema dual com o novo 6 continuara vidvel para y Assim podemos aplicar o simplex dual revisado sem a necessidade de resolver 0 problema pelo método simplex de duas fases ou o método do M grande 132 Exercicios 1 O objetivo deste exercicio 6 mostrar que aplicar o método simplex revisado ao problema dual é diferente de aplicarmos 0 método simplex dual revisado ao problema original Sejam o problema primal e o problema dual correspondente minimizar 21 22 wo maximizar yi Yy2 sujeitoa 24 1 sujeito a Y1 1 LQ 1 yo tL X1X2 0 O problema primal tem somente uma tnica escolha para a base Mostre que aplicando o método simplex dual revisado ao problema primal ele finaliza imediatamente com a solugéo étima Agora aplique o método simplex revisado ao problema dual e mostre que ele necessita algumas iteracdes para conseguir obter a solucaéo 6otima 52 4 e e e e 14 Andalise de Sensibilidade Como vimos no método simplex dual é frequente acontecer de precisarmos resolver um problema de otimizacao linear com os dados parecidos e assim aproveitarmos a solucao do problema original Considere novamente o problema de otimizacao linear na forma padrao T minimizar c 2x sujeitoa Axvb x0 Suponhamos que a matriz A R satisfaca a Hipdtese 86 no qual possui m linhas linearmente independentes conhecemos uma base B B1 B2 Bm com a matriz da base correspondente B e sua inversa B e a solucdo 6tima 2 R correspondente Ou seja Lp Bb 0c 0 custo reduzido n ch chB tAn OF que sao as caracteristicas da otimalidade no problema primal Iremos verificar em que condicées estas solucdes 6timas ou valores 6timos serao iguais quando a matriz A ou os vetores 6 e c sao modificados Dentre as diferentes perturbacoes iremos considerar os seguintes casos e Adicionar uma nova varidvel e Modificar o vetor c da funcao objetivo e Modificar o vetor b da restricao e Adicionar uma nova desigualdade como restricao e Adicionar uma nova igualdade como restriao 141 Adicionar uma nova variavel Suponhamos que adicionemos uma nova varidvel x41 com o respectivo coeficiente da fungao objetivo Cn41 e coluna A1 correspondente T minimizar C Cp41ln41 sujeitoa Aw Ansitn41b LMn1 0 Queremos saber se a matriz da base B correspondente a solucao étima do problema antes de adicionar a varidvel continua sendo a matriz 6tima Considere a0 que claramente é uma solucao vidvel basica Para que esta solucao seja 6tima no problema com a varidvel adicional temos que checar duas coisas Primeiro como R Bb 0 resta verificar se o custo reduzido é nao negativo Como Gy ch chBAyn 0 resta checar se T pl Chl Cnt Cp B Ani O Caso isso nao for verdade o método simplex revisado tipicamente acha a solugdo 6tima em poucas iteragoes Considere o problema minimizar 52 9123 sujeito a 321 22 x3 10 5x1 3x2 24 16 102 0304 0 53 para o qual a 22007 6 uma solucao étima A base neste caso é B B1 B2 12 a matriz da base e a sua inversa sao respectivamente 3 2 4 3 2 sa 8 3 4 Suponhamos que queremos agora resolver um problema com uma nova varidvel adicionada minimizar 5d22123 25 sujeitoa 3222 73 25 10 5x1 3x2 a425 16 U1 2 0304 U5 2 0 Primeiramente verifiquemos se 220007 6 uma solucdo 6tima para o problema com uma nova varidvel Para isto calculando o custo reduzido para a varidvel x5 temos 3 2 1 cs chB As 15 1 420 5 3 1 Assim nao é uma solucao 6tima mas aplicando 0 método simplex revisado 7 5 entrard na base Como 3 2 1 1 2 1 toBa5 1 4 eG temos que 6 4 1 e B B2 2 saird da base Logo yj 0 ys 1 yaa TB dgay y1 2113e temos y 3000 17 A nova base seré B B1 B2 15 a matriz da base e a sua inversa sao respectivamente 3 1 i eC mCP A 5 1 2 73 Finalmente calculando 0 custo reduzido para as varidveis nao basicas temos TT Tpl 3 3 2 1 0 ty ch chB Ay 11205 1 52 21210 5 75 3 0 1 o que mostra que 3 0 0 0 1 éa solugéo 6tima do problema onde acrescentamos uma nova varidvel Note que realizamos uma tnica iteracao a mais para resolver o problema 142 Modificar o vetor c da fungao objetivo Suponhamos que queremos modificar o vetor c digamos somente na componente j Ou seja de c para c 0de onde e é o vetor onde a coordenada j é igual a 1 e os demais iguais a zero Como a viabilidade do problema nao muda pois A e 6 nao sao modificados temos que somente considerar a otimalidade do custo reduzido Caso 7 for um indice de uma variavel nao basica 0 custo reduzido depois da modificacao na coorde nada 7 tornase cj 0 cpBA o qual queremos que seja nao negativo Ou seja para 06 chBA Cy 12 a solucaéo 6tima do problema antes da modificacaéo continua sendo 6tima Caso j B for um indice de uma varidvel bdsica 0 custo reduzido depois da modificagao tornase c cB der BA Vi N1N2Nnm 13 54 e portanto para que a solucao 6tima do problema antes da modificacao continuar sendo 6tima a seguinte condicao tem que ser valida chBA6eBA Vi N1N2Nnm Caso as condicoes acima nao forem satisfeitas 6 necessério continuar com o método simplex No mesmo exemplo vamos verificar 0 que acontece quando o vetor da funcdo objetivo ef 5 1 12 0 6 modificado para 5 6 1120 e 5 1 12 63 0 Lembrando que 22007 é uma solucao étima a base é B B1 B2 12 e a inversa da matriz da base é igual a 3 2 B 3 3 Para 5 6 1 120 Como 1 B1 é um indice da base temos que verificar as condigées 13 3 2 1 3 2 1 2125 1 1 ca0 2 4 0003 2 0 3 2 0 3 2 0 ra05 2 2 2 san 4a2 Conclufmos que 2200 continuara a ser a solucdo 6tima do problema com a modificacao se 2 7 3 0 5 Para 5 1 12 63 0 Como 3 é um indice que nao é base temos que verificar somente a condicao 12 3 2 1 5 1 122 mzco 3 4 o Concluimos que 2200 continuara a ser a solucdo étima do problema com a modificacao se 63 2 143 Modificar o vetor b da restricao Suponhamos que queremos modificar o vetor b da restricao digamos somente na componente 7 Ou seja de b para b de Neste caso o custo reduzido néo mudaria pois c e B nao sofreriam nenhuma modificagéo mas a viabilidade ficaria comprometida Sabemos que a solugao otima atual x satisfaz x Bb 0 Para que atual matriz da base continue sendo 6tima depois da modificacado precisaremos que Bb de 0 Denotando a coluna i da matriz B como g 1 82 mi esta condicdo 6 equivalente a LB LB max 3 o min 3 14 JE 124m Bji0 Byi J12m Bj20 By Logo a nova solucdo étima com a mesma matriz da base B serd 3 Bb de xroge o valor 6timo correspondente sera chep ch Bb 6e chat bchkg 55 No mesmo exemplo vamos verificar 0 que acontece quando o vetor b 10 16 é modificado para 10 6 16 Lembrando que a 22007 é uma solucao 6tima a base é B B1 B2 12 e a inversa da matriz da base é igual a 3 2 B 3 3 Para 10 6 16 Note que a primeira coluna de B é igual a g 3 5 Logo utilizando a férmula 14 temos 2 2 2 5 1s 3 e a solucdo 6tima correspondente pode ser determinado por p a dig 2 2 613 5 ou seja 2 36 2 5d 0 0 e o valor 6timo cha 6ehg 12 1061 144 Adicionar uma nova desigualdade como restrigao Suponhamos agora que adicionamos uma nova restricao de desigualdade al 41 bm1 ao problema de otimizacao linear na forma padrao Caso a solucao étima x satisfaga a nova restricao x continuara sendo uma solucao étima do novo problema Caso contrario subtrafmos uma nova varidvel 741 do lado esquerdo da desigualdade para obtermos uma igualdade minimizar cl a On41 sujeitoa Ax0an4156 ad n41 bm1 LUn1 0 Assim a nova matriz da restricgao sera A 0 ar 3 15 m1 Seja B a matriz da base com a base correspondente B Se adicionarmos o novo indice a base B B1 B2Bmm 1 a nova matriz da base sera B oO B 1 ao 16 onde a sao as coordenadas correspondentes do vetor a 4 matriz da base Esta matriz é invertfvel e sua inversa é dada por B 0 Bia B 9 an Logo os valores da varidveis basicas do novo problema tomam os valores b x tp B B 0 18 LB bint a x bm4t z 0 como ja sabemos e o custo reduzido para o novo problema é dado por B 6 O AO T T TT pel T c 0 50 gry Cai Fe cpB A 0 0 Portanto estamos na situacao inicial para aplicarmos o método simplex dual 56 Consideremos 0 mesmo exemplo e suponhamos que queremos adicionar uma restricao nova 71 2 5 que claramente nao é satisfeita para a solucdo 6tima x 2200 do problema original Neste caso Am1 1100 bm41 5 param 3 O problema com a nova restricao sera minimizar 5x21 123 sujeito a 32 279 x3 10 521 3x2 2X4 16 t X92 95 U1 23 0405 0 A base é B B1 B2 B3 1 25 e os indices das varidveis nao basicas N N1 N2 34 Como 2 x 2 ey B b Pow PB 2 Pmt at Pmt 1 1 5 1 pelo Passo 2 do método simplex dual revisado 3 e xp X5 deixara de ser a varidvel basica Agora no Passo 3 na terceira linha da matriz gi A oO BOO A 0 at l 7 aB 1 abi l 2 3 5 3 2 10 0 39 5 3 01 O 11 1 l 1 1 l an 3 2 00 103 2 O 01 5 3 0 00 2 1 1 temos um elemento negativo 1 que corresponde a coluna j 4 Logo esta serd a varidvel que saird da base A nova base sera B B1 B2 B3 1 24 a inversa da nova matriz da base 1 O 2 B 1 0 3 2 1 1 b 1 0 2 10 0 e a varidvel basica 2 B 5 10 38 146 5 20 ml 21 1 5 1 Conclufmos entaéo que 05010 sera solucéo do novo problema com valor 6timo igual a cx 5 11200050107 5 145 Adicionar uma nova igualdade como restrigao Suponhamos agora que adicionamos uma nova restricdo de igualdade a 412 bm41 ao problema de otimizacao linear na forma padrao Caso a solucao étima x satisfaga a nova restricao x continuara sendo uma solugao 6tima do novo problema Caso contrario como nao podemos garantir que a matriz da base seja invertivel com a linha adicional na matriz de restricao adotaremos a seguinte estratégia Primeiramente sem perda de generalidade assumimos que a 42 bm41 E iremos tentar resolver o seguinte problema auxiliar utilizando um M extremante grande e uma nova varidvel adicional 741 minimizar cla Man41 sujeitoa Ax0an4156 ad 4Xn41 bm41 LUn1 0 57 Assim a nova matriz da restrigéo sera 15 Seja B a matriz da base com a base correspondente B Se adicionarmos o novo indice 4 base B B1 B2 Bmm1 a nova matriz da base sera 16 onde a sao as coordenadas correspondentes do vetor a 4 matriz da base Esta matriz é invertfvel e sua inversa é 17 Além disso os valores da varidveis basicas do novo problema 18 sera nao negativos pois x 0 e pela nossa hipdtese al x bm4t O custo reduzido para o novo problema é dado por BO A 0 T T 0 WT pl Tp1 T c M ch M pa ne c ch B1AMaBAal 0 o qual nao sabemos se é um vetor nao negativo Portanto estamos na situacao inicial para aplicarmos o método simplex revisado Consideremos 0 mesmo exemplo e suponhamos que queremos adicionar uma restricao nova de igual dade x 22 1 que claramente nao é satisfeita para a solucdo 6tima x 22007 do problema original Além disso 2 x2 0 1 portanto satisfaz a condicao que impomos sem perda de generalidade Neste caso dm41 11000 bm41 1 para m 3 O problema auxiliar com a nova restricao sera minimizar 5x1 2 123 Mas sujeito a 32 279 x3 10 021 3x2 4 16 21 22 l U1 X22 0304 05 0 Verifiquemos primeiro 2 1 b x 2 2 my B ares 2 2 20 m1 B m1 1 1 1 1 Portanto 220017 6 uma solucao basica vidvel para o problema auxiliar Calculemos entao o custo reduzido para o problema auxiliar para um M grande suficiente a chBA M a BA Qt 0 3 2 3 2 1 O 5 11205 1 8 0 8 P24 sor 3 2 3 2 1 0 Mi11 11 28M M in 8 2822crr00 0 oo2sirresin que tem coordenadas negativara para M grande e pode forcar a saida da varidvel x5 146 Exercicios 1 No exemplo numérico da subsecao 142 determine as condicgdes para 62 quando substituimos o vetor da funcao objetivo de e 51120 por e 51 do120 e a 22007 continuar sendo a solugéo 6tima do problema 2 No exemplo numérico da subsecao 142 determine as condic6es para 64 quando substituimos o vetor da funcao objetivo de ec 51120 por e 51 1264 e 2200 continuar sendo a solucao étima do problema 3 No exemplo numérico da subsecao 143 determine as condic6es para 62 quando substituimos o vetor da restricdo de b 10 16 por b 1016 62 e B B1 B2 12 continuar sendo a matriz da base do problema 58 4 No exemplo numerico da subsecao 145 continue as iteracoes do metodo simplex para M 100 por exemplo e determine a solucao otima e o valor otimo 15 Metodos PrimaisDuais de Pontos Interiores 151 Breve fatos historicos 1939 O problema da dieta por George J Stigler 1939 Fundamentos do problema de otimizacao linear por L V Kantorovitch 1947 Metodo simplex por George Dantzig 1972 O problema de KleeMinty 1975 L V Kantorovitch e T C Koopmans recebem o prˆemio Nobel em economia 1979 Metodo de elipsoide para problema de otimizacao linear por L Khachian 1984 Metodo de afimescala e anunciado por N K Karmarkar 1987 Metodo primal de pontos interiores de menor complexidade por Clovis C Gonzaga 1987 Metodo primaldual de pontos interiores e desenvolvido por M Kojima S Mizuno A Yoshise N Megiddo e T Noma O que podemos aprender com a historia Em otimizacao e sempre necessario fazer a implementacao para verificar se o algorıtimo e eficaz 152 Condicoes de otimalidade para problemas de otimizacao linear Considere o problema de otimizacao linear na forma padrao novamente minimizar cT x sujeito a Ax b x 0 onde c Rn A Rmn e b Rm Como ja vimos o problema dual associado a este problema e maximizar bT y sujeito a AT y c y Rm Chamando s c AT y podemos escrever o mesmo problema como maximizar bT y sujeito a AT y s c s 0 y Rm Pelo Teorema das Condicoes Complementares das Folgas Teorema 124 sabemos que x Rn e y Rm sao solucoes otimas do problemas primal e dual respectivamente se e somente se existir um s Rn tal que as seguinte condicoes sao satisfeitas para x y s x y s AT y s c 19 Ax b 20 xisi 0 i 1 2 n 21 x s 0 22 Estas condicoes tambem sao conhecidas como condicoes de otimalidade de KarushKuhn Tucker KKT 59 153 Métodos primaisduais de pontos interiores Podemos reescrever as equacoes 1921 de uma forma diferente Alysc Fxy8 Az b 0 23 X Se onde F R7 R 6 uma funcio linear exceto a tiltima equacio X diagr1222n S diags1s28n ee 111 O método primaldual de pontos interiores consiste em aplicar o método de Newton a equacao 23 para obter x y s tal que x s 0 com o intuito de que a sequencia convirja para a y s Assim definimos a regiao vidvel primaldual F e a regiao estritamente vidvel primaldual F F xys R x R x R Ax 6b A y 8s cx8 0 F ys R xR x R Ax b A y 8 ca8 O Portanto nas iteracdes do método primaldual de pontos interiores temos a ys F Seja x y s F e analisemos uma iteracdéo do método de Newton Aplicando o método de Newton para a equacao 23 temos Az Oo A I Az O Ix y 8 Ay A O O Ay F xy 8 O As S O xX As X Se onde J é 0 Jacobiano de F Como queremos manter as varidveis da sequéncia estritamente positivas nado podemos tomar um passo completo do método de Newton e assim consideramos o método de Newton truncado xt y 87 wys aAa Ay As onde a 0 1 é o paraémetro para ser definido por um método de busca linear 154 O caminho central O caminho central C é uma curva parametrizada com pontos estritamente vidveis Considere o parametro Tt 0 Cada ponto vetor do caminho central a y8 C é uma solucao do sistema Alys c Az 5b us T i12n rs OO ou alternativamente 0 Fxys oO xzs 0 24 Te Ou seja C ay8 F a y8 satisfaz 24 para algum rt 0 E possivel provar que se F é nao vazio y8 existe unicamente para cada T 0 Observe que uma solucao do problema de otimizacao linear ira corresponder ao ponto do caminho cen tral quando 7 0 Portanto para controlar o equilibrio entre uma direcaéo convergindo para a solucao do problema e obter um ponto especifico do caminho central definemos o parametro centralizador o 01 e a medida de dualidade li as i 5 Si on 11 60 Resumindo para se obter uma direcao de busca primaldual genérico é necessdrio resolver a equacao Oo A I Ax O A O O Ay O S O xX As XSe ope que tem como objetivo encontrar um ponto ao Yous Soy C do caminho central 155 O esquema primaldual de pontos interiores Esquema PDPI Dado x y s F Para k 012 resolva Oo A TT Aa O A O O Ay O sk oO xk As XSet oppxe xT sk onde ox 01 e up ah th yh th sh ak ys aAw Ay As para az 0 1 tal que w1 s1 0 Final do Para 156 Métodos primaisduals que seguem o caminho Para manter as sequéncias geradas pelo método de pontos interiores préximo ao caminho central C definiremos a nocao de vizinhanga de C As duas vizinhangas de C mais utilizadas sao a vizinhanga da norma 2 No6 ay 8 F X Se pell2 On para algum 01 e a vizinhanga norma co de um lado Noo y8 F x8 yu i 12n para algum 01 157 Os métodos primaisduais redutores de poténcia de pontos interiores Nestes métodos utilizamos uma fungao potencial primaldual digamos que deve satisfazer duas propriedades xs oo se 445 0 para algum i e pw AO n co entao x ys Q onde 2 é 0 conjunto de solugdes primaisduais do problema Um exemplo destas funcoes é a funcao de TanabeTodd Ye n xs ploga s S log Xi Si i1 para algum p n 61 158 Os metodos primaisduais de pontos interiores com pontos iniciais nao viaveis A discussao ate agora assumia que o ponto inicial era um ponto viavel isto e Ax0 b AT y0 s0 c e x0 s0 0 Devido a 23 as iteracoes subsequentes serao pontos viaveis se pudermos tomar um passo αk 0 1 tal que xk1 xk αkxk 0 e sk1 sk αksk 0 Como esta situacao nao e realista iremos definir primeiro os resıduos para as duas equacoes lineares rk b Axk b rk c AT yk sk c E entao resolvemos as seguintes equacoes pelo metodo de Newton O AT I A O O Sk O Xk xk yk sk rk c rk b XkSke σkµke As sequˆencias obtidas nas iteracoes subsequentes serao viaveis se pudermos tomar um passo de Newton completo αk 1 ou podem amenizar a nao viabilidade se αk 0 1 159 Os metodos primaisduais preditorcorretor de Mehrotra de pontos interiores Uma rotina importante incorporada em resolvedores generico para problemas de otimizacao linear e o metodo preditorcorretor que possui duas caracterısticas Adicao de um passo corretor alem do passo preditor padrao para a direcao de busca a fim de melhorar a proximidade das iteracoes ao caminho central Escolha adaptativa para o parˆametro central σ 1510 Exercıcios 1 Mostre que N 2θ1 N 2θ2 quando 0 θ1 θ2 1 e que N γ1 N γ2 para 0 γ2 γ1 1 2 Mostre que N 2θ N γ se γ 1 θ 62