Slide - Otimização Combinatória e Programação Inteira - 2023-2

Problemas de Programação Inteira com Matrizes Totalmente Unimodulares 2 curvas de nível da FO curvas de nível da FO ótimo * 3 curvas de nível da FO curvas de nível da FO 4 curvas de nível da FO curvas de nível da FO SIMPLEX? ótimos * * * 5 curvas de nível da FO curvas de nível da FO ótimo * 6 curvas de nível da FO curvas de nível da FO ótimo * 7 curvas de nível da FO curvas de nível da FO ótimo * 8 Quando todas as soluções de um Problema de Programação Linear são Inteiras? Ou Quando podemos usar algoritmos de Programação Linear para resolver problemas de Programação Inteira? 9 Max z = x1 + x2 + x3 s.a. 3x1 + x2 ≤ 10 x2 + x3 ≤ 30 Max z - x1 - x2 - x3 = 0 s.a. 3x1 + x2 + x4 = 10 x2 + x3 + x5 = 30 Max z -x1 -x2 -x3 = 0 s.a. 3x1 +x2 +x4 = 10 x2 +x3 +x5 = 30 base z x1 x2 x3 x4 x5 b z +1 -1 -1 -1 0 0 0 x4 0 +3 +1 0 +1 0 +10 x5 0 0 +1 +1 0 +1 +30 base z x4 x5 b z +1 0 0 0 x4 0 +1 0 +10 x5 0 0 +1 +30 Ax=b fora x1 x2 x3 -1 -1 -1 0 +3 +1 0 0 0 +1 +1 0 1z + 0x4 + 0x5 = 0 0z + 1x4 + 0x5 = 10 0z + 0x4 + 1x5 = 30 -1x1 - 1x2 - 1x3 = 0 1x1 + 1x2 + 0x3 = 0 0x1 - 1x2 + 1x3 = 0 BxB=b NxN=0 BxB=b x1 x2 x3 x4 x5 +3 +1 0 +1 0 0 +1 +1 0 +1 A= x4 x5 +1 0 0 +1 B= x1 x2 x3 +3 +1 0 0 +1 +1 N= xB=b\B xB=B-1b x4 x5 x4 x5 +1 0 0 +1 = b +10 +30 * det(B)=1 x4 x5 10 30 = BxB=b x1 x2 x3 x4 x5 +3 +1 0 +1 0 0 +1 +1 0 +1 A= x1 x3 +3 0 0 +1 B= x2 x4 x5 +1 +1 0 +1 0 +1 N= xB=b\B xB=B-1b x1 x3 x1 x3 +0,33 0 0 +1 = b +10 +30 * det(B)=3 x1 x3 3,33 30 = 13 Se o vetor b é formado por inteiros e a base ótima B tem det(B) = ± 1, então a solução é formada por inteiros! Como não sabemos qual será a base ótima, verificamos se todas as bases possíveis de A (submatrizes quadradas) têm determinante ± 1 (ou 0). Em caso positivo, A é chamada de Matriz Totalmente Unimodular. 14 Mas existe uma maneira mais fácil de verificar se A é TUM: Uma matriz A é TU se (i) (ii) (iii) as linhas de A podem ser particionadas em dois conjuntos tais que:  Se uma coluna tem duas entradas de mesmo sinal, suas linhas estão em conjuntos diferentes;  Se uma coluna tem duas entradas de sinais diferentes, suas linhas estão no mesmo conjunto. ij aij   − }, 1,0,1 { j a m i ij    = ,2 | | 1 Exemplo Lineu Silva comprou um carro novo. Precavido do jeito que é, Lineu já pensa sobre o que fazer com o carro nos próximos 3 anos, afinal talvez seja economicamente mais favorável trocar de carro ao fim de 1 ou 2 anos, ao invés de mantê-lo por 3 anos. Isto sobretudo porque os custos de utilização e manutenção crescem muito rapidamente com o envelhecimento dos veículos. 15 Exemplo Lineu vai pra ponta do lápis e calcula o preço de um carro novo menos o que a loja dá pelo usado, mais os custos de utilização e manutenção (oficina...), de comprar um carro novo no ano i e troca-lo no fim do ano j (o ano 0 e agora). 16 Exemplo Na tabela seguinte estão representados os custos calculados por Lineu. Assim, por exemplo, trocar o carro agora comprado (ano 0) no fim do ano 1 e depois manter o carro comprado no ano 1 até o fim do ano 3, corresponde a um custo de 800 + 2100 = 2900. 17 Exemplo Lineu tem que decidir quantas vezes deve trocar de carro (se alguma) de forma a minimizar a sua despesa total com carros durante estes 3 anos. Pergunta??  Este problema pode ser resolvido usando apenas programação linear??? 18 Caminho mínimo 800 1000 1200 2100 1800 3100 Fim do ano 0 1 2 3 20 2 2 2 2 2 2 {1} {2,3,4} {1,3}{2,4} ... 1 -1 21 A matriz de incidência de um grafo direcionado é totalmente unimodular. Problema de Transporte  Um grafo bipartido é um grafo cujos vértices podem ser divididos em dois conjuntos (U e V) disjuntos de forma que toda aresta conecta um vértice em U a um vértice em V.  Exemplo: Problema de Transporte 22 Problema Clássico de Transporte fonte 1 fonte 2 destino 2 destino 3 destino 1 𝒂𝟏 𝒂𝟐 𝒃𝟏 𝒃𝟐 𝒃𝟑 𝒄𝟐𝟏 𝒄𝟐𝟐 𝒄𝟐𝟑 𝒄𝟏𝟐 𝒄𝟏𝟑 𝒄𝟏𝟏 capacidade de fornecimento capacidade de absorção custo de transporte da rota toda a produção é absorvida Problema Clássico de Transporte Formulação do Problema como Problema de Programação Linear Problema Clássico de Transporte Exemplo Certa empresa possui dois armazéns, A1 e A2, onde dispõe de 100 e 50 unidades de determinado produto, respectivamente, com o que abastece três mercados, M1, M2 e M3, que consomem 80, 30 e 40 unidades. Sabendo que os custos de transporte são dados no quadro. Problema Clássico de Transporte restrições de oferta (origens) restrições de procura (destinos) Formulação do Problema como Problema de Programação Linear Problema de Transporte Este problema pode ser resolvido usando apenas programação linear??? 27 A matriz de incidência de Grafos Bipartidos é totalmente unimodular, logo, se b for um vetor de inteiros, a resposta do problema é inteira. 28