Computer Science › Algoritmos e Software
Um programa linear tem uma função objetivo linear a maximizar ou minimizar, restrições lineares, e tipicamente não-negatividade das variáveis; três regras mecânicas (negar, inverter ≥, dividir =) colocam qualquer PL na forma padrão.
A região factível de um PL é a interseção de semiplanos, sempre um polígono convexo; uma linha objetivo varrendo essa região sempre atinge seu extremo em um vértice, nunca estritamente no interior, o que torna o método gráfico (e depois o simplex) suficiente.
Sempre que um programa linear com região factível limitada tem uma solução ótima, pelo menos uma solução ótima ocorre em um vértice, provado por convexidade e linearidade, reduzindo a busca de um contínuo infinito para uma lista finita de vértices.
Variáveis de folga transformam desigualdades em equações; cada iteração escolhe uma variável de entrada (coeficiente mais negativo na linha objetivo), roda o teste da razão para achar a variável de saída, e pivoteia até que nenhum coeficiente negativo reste.
Restrições ≥ ou = quebram o início fácil do simplex; variáveis artificiais constroem um ponto de partida factível fictício para uma Fase 1 que zera os artificiais, seguida por uma Fase 2 que otimiza o objetivo real a partir do vértice encontrado.
Empates no teste da razão criam soluções básicas degeneradas, que a regra de Bland previne de virar ciclos infinitos; separadamente, o resultado de Klee-Minty mostra que a regra padrão de entrada precisa de 2^n pivôs no pior caso, um fato sobre o algoritmo simplex, não sobre o problema de programação linear em si (resolvido em tempo polinomial por métodos de pontos interiores).
Todo PL em forma padrão tem um dual construído mecanicamente (trocar max por min, transpor a matriz, trocar lado direito por coeficientes objetivo, inverter desigualdades); cada variável dual é um preço-sombra, e o valor ótimo do dual bate exatamente com o do primal.
Dualidade fraca prova cᵀx ≤ bᵀy para qualquer par factível; dualidade forte mostra que isso vira igualdade exata no ótimo, lido diretamente dos coeficientes de folga na linha objetivo final do simplex; folga complementar liga precisamente quais variáveis primais positivas forçam quais restrições duais justas.
O simplex dual parte de um tableau dual-factível mas primal-infactível (linha objetivo sem coeficientes negativos, mas algum lado direito negativo) e restaura factibilidade primal sem nunca perder factibilidade dual, o espelho estrutural exato do simplex comum, ideal para reotimizar depois de adicionar uma restrição nova.
A relaxação linear de um PL inteiro sempre dá um limite otimista; arredondamento ingênuo pode ser estritamente subótimo (demonstrado concretamente); branch and bound resolve exatamente ramificando em uma variável fracionária e podando subproblemas cujo limite de relaxação não consegue superar a melhor solução inteira já encontrada.
O PL de fluxo máximo, com a regra estendida de dualidade para restrições de igualdade (variável dual livre), tem um dual que é exatamente uma relaxação fracionária de corte mínimo; dualidade forte então implica o teorema do fluxo máximo/corte mínimo, uma segunda prova completamente independente da via de Ford-Fulkerson.
Part of the Computer Science curriculum.
Um programa linear tem uma função objetivo linear a maximizar ou minimizar, restrições lineares, e tipicamente não-negatividade das variáveis; três regras mecânicas (negar, inverter ≥, dividir =) colocam qualquer PL na forma padrão.
A região factível de um PL é a interseção de semiplanos, sempre um polígono convexo; uma linha objetivo varrendo essa região sempre atinge seu extremo em um vértice, nunca estritamente no interior, o que torna o método gráfico (e depois o simplex) suficiente.
Sempre que um programa linear com região factível limitada tem uma solução ótima, pelo menos uma solução ótima ocorre em um vértice, provado por convexidade e linearidade, reduzindo a busca de um contínuo infinito para uma lista finita de vértices.
Variáveis de folga transformam desigualdades em equações; cada iteração escolhe uma variável de entrada (coeficiente mais negativo na linha objetivo), roda o teste da razão para achar a variável de saída, e pivoteia até que nenhum coeficiente negativo reste.
Restrições ≥ ou = quebram o início fácil do simplex; variáveis artificiais constroem um ponto de partida factível fictício para uma Fase 1 que zera os artificiais, seguida por uma Fase 2 que otimiza o objetivo real a partir do vértice encontrado.
Empates no teste da razão criam soluções básicas degeneradas, que a regra de Bland previne de virar ciclos infinitos; separadamente, o resultado de Klee-Minty mostra que a regra padrão de entrada precisa de 2^n pivôs no pior caso, um fato sobre o algoritmo simplex, não sobre o problema de programação linear em si (resolvido em tempo polinomial por métodos de pontos interiores).
Todo PL em forma padrão tem um dual construído mecanicamente (trocar max por min, transpor a matriz, trocar lado direito por coeficientes objetivo, inverter desigualdades); cada variável dual é um preço-sombra, e o valor ótimo do dual bate exatamente com o do primal.
Dualidade fraca prova cᵀx ≤ bᵀy para qualquer par factível; dualidade forte mostra que isso vira igualdade exata no ótimo, lido diretamente dos coeficientes de folga na linha objetivo final do simplex; folga complementar liga precisamente quais variáveis primais positivas forçam quais restrições duais justas.
O simplex dual parte de um tableau dual-factível mas primal-infactível (linha objetivo sem coeficientes negativos, mas algum lado direito negativo) e restaura factibilidade primal sem nunca perder factibilidade dual, o espelho estrutural exato do simplex comum, ideal para reotimizar depois de adicionar uma restrição nova.
A relaxação linear de um PL inteiro sempre dá um limite otimista; arredondamento ingênuo pode ser estritamente subótimo (demonstrado concretamente); branch and bound resolve exatamente ramificando em uma variável fracionária e podando subproblemas cujo limite de relaxação não consegue superar a melhor solução inteira já encontrada.
O PL de fluxo máximo, com a regra estendida de dualidade para restrições de igualdade (variável dual livre), tem um dual que é exatamente uma relaxação fracionária de corte mínimo; dualidade forte então implica o teorema do fluxo máximo/corte mínimo, uma segunda prova completamente independente da via de Ford-Fulkerson.