Baixe o app para aproveitar ainda mais
Prévia do material em texto
Lista de Exercícios - Otimização Linear Profa. Maria do Socorro – DMAp/IBILCE/UNESP Método Simplex Ref.: Bazaara, M. e J.J. Javis - ‘Linear Programming and Network Flows’ - John Wiley, 1977. 1) Resolva o problema abaixo pelo método simplex começando com a solução básica factível (x1,x2) = (4,0). max -x1 + 2x2 s.a 3x1 + 4x2 = 12 2x1 - x2 12 x1, x2 0 2) Considere o problema max 2x1 + x2 – 3x3 + 5x4 s.a x1 + 2x2 + 4x3 - x4 6 2x1 + 3x2 - x3 + x4 12 x1 + x3 + x4 4 x1, x2, x3, x4 0 Encontre a solução básica factível onde as variáveis x1, x2 e x4 são básicas. Esta solução é ótima? Senão encontre a solução ótima partindo desta solução. 3) Resolva os problemas abaixo pelo método simplex. a) Min zxx 212 s.a. 93 21 xx 322 21 xx and 80,10 21 xx b) Min zxxxxx 54321 322 s.a 022 54321 xxxxx 5,...,1,0 0 022 54321 54321 jx xxxxx xxxxx j c) Max z 1x s.a 2043 4321 xxxx 4,...1,0 037 52 421 31 jx xxx xx j d) 02,1 121 62312 . 3min 21 xx xx xx as xxz e) 02,1 121 4221 . 2412max xx xx xx as xxz f) 02,1 321 4221 . 231max xx xx xx as xxz 4) Verifique usando o método simplex que o problema abaixo é ilimitado. Escreva a classe de soluções viáveis que fazem com que: as xxxx . 321 = zMin 4321 102 4321 xxxx 4,...,1,0 302443 20225 4321 4321 jx xxxx xxxx j 5) - Considere o seguinte problema: Min zxxxx 4321 52 s.a. 44321 xxxx 4,...,1,0 252 52432 4321 4321 jx xxxx xxxx j . Mostre, usando o método simplex que o problema é infactível. 4- Use o método simplex para verificar se o sistema de inequações abaixo é compatível. 4,...,1,0 9235 45444 44 4321 4321 431 jx xxxx xxxx xxx j 6) Considere o problema: Min zxxxx 4321 1232 s.a 0992 4321 xxxx 0,0,0,0 02 4321 433 1 213 1 xxxx xxxx acrescente as variáveis de folga 5x 6x , e as use como solução básica inicial. a) Resolva o problema pelo método simplex considerando que: i - a variável candidata a entrar na base é a variável não básica como menor custo relativo ii - a variável que sai da base é a variável básica com menor índice 𝑙 = 𝑖 satisfazendo miy y x l i i B i ,..1,0, ˆ min o que acontece? b) Resolva o problema usando a regra de Bland para mostrar que o algoritmo converge. c) Resolva o problema usando um dado para tomar as suas decisões em caso de empate e mostre que o algoritmo converge. 7) Considere o problema: Max 21 xxz s.a 121 xx 0,0 32 3 21 21 21 xx xx xx a) Desenhe a região factível b) Resolva o problema graficamente c) Mostre graficamente que a solução ótima é degenerada d) mostre na figura que restrição pode ser retirada do problema para obter uma solução ótima nào degenerada. 8) Considere o seguinte problema de programação linear: 𝑚𝑎𝑥 321 32 xxxz s.a 62 321 xxx 3,...,1,0 42 31 jx xx j a)Resolva pelo método simplex. b) Multiplique a segunda equação por 2 e resolva o problema novamente. Qual é o efeito desta multiplicação nos valores da variáveis duais? Qual é o efeito no valor ótimo da função objetivo? 9) Considere o seguinte problema de programação linear: Min 321 3 xxxz s.a 3,...,1,0 2 62 321 321 jx xxx xxx j a)Resolva pelo método simplex. b)Troque o sinal da primeira restrição para ' <=' e resolva o problema novamente. 10) Resolva o problema pelo método simplex revisado: min 4321 8429 xxxxz s.a 4,...,1,0 103 2032 4321 4321 jx xxxx xxxx j a) mostre que o problema possui infinitas soluções b) encontre todas as soluções básicas viáveis ótimas 11) Resolve o problema abaixo pelo método simplex. Desenhe a região factível e mostre no gráfico a solução visitada a cada iteração. .0,0 523 42 . min 21 21 21 21 xx xx xx as xxz 12) Mostre que o seguinte problema é infactível. 0,0,0 1 6 54 . 332min 321 1 321 321 321 xxx x xxx xxx as xxxz 13) Vimos que a maior parte do esforço computacional do método simplex é dedicado ao cálculo dos custos relativos, j t jj Acc ˆ , das variáveis não básicas. Suponha que ao invés de usar a regra: }ˆ{minˆ j j k cc para escolher a variável não básica candidata a entrar na base, simplesmente escolhemos a primeira variável que tiver 0ˆ j t jj Acc . Isto poderia eliminar o cálculo de um grande número de custos relativos. Discute as vantagens e desvantagens desta regra. 14) O objetivo deste exercício é examinar o que acontece com a solução ótima do problema quando pequenas modificações no mesmo ocorrem. Considere o problema: Min zxxxx 4321 1234 s.a 10232 4321 xxxx 4,...1,0 163241 4321 jx xxxx j a) Resolva o problema usando um software. Anote a solução obtida b) mude o custo de 𝑥4 para 4 e reotimize o problema. Mude para 8 e reotimize. Como a soluçào ótima do problema variou em cada caso? c) mude o coeficiente de 𝑥2 na segunda equação para 𝑎22 = 5 e reotimize. O que muda na soluçào do problema? d) Faça as seguintes modificações no valor do lado direito da primeira restrição: mude de b1 = 10 para b1 = 8 e reotimize. mude de b1 = 10 para b1 = 12 e reotimize mude de b1 = 10 para b1 = 20 e reotimize examine a nova solução em cada caso. e) Acrescente uma nova atividade (𝑥5) ao problema com os seguintes dados: c5 = -1 a15 = 2, a25 = -3. Reotimize o problema. Como voce poderia ter previsto esta nova solução analisando a solução do problema original? f) Acrescente individualmente cada uma das restrições abaixo e analise as mudanças na solução ótima. 6 8422 4 4321 4321 4321 xxxx xxxx xxxx
Compartilhar