Decomposição de Dantzig-Wolfe: diferenças entre revisões
m general cleanup utilizando AWB |
Discordância de número arrumada |
||
| Linha 4: | Linha 4: | ||
Ele opera formando um ``problema mestre`` equivalente, com poucas linhas, mas com número muito maior de colunas. Este problema é então resolvido sem tabular todas as colunas, gerando elas sempre que o [[Algoritmo simplex|método simplex]] precisa, usando uma tecnica conhecida com geração de coluna. |
Ele opera formando um ``problema mestre`` equivalente, com poucas linhas, mas com número muito maior de colunas. Este problema é então resolvido sem tabular todas as colunas, gerando elas sempre que o [[Algoritmo simplex|método simplex]] precisa, usando uma tecnica conhecida com geração de coluna. |
||
O |
O algoritmo envolve iterações entre um conjunto de subproblemas cujo função objetivo contém parâmetros variáveis e um problema mestre. |
||
O subproblema recebe um conjunto de parâmetros do problema mestre e então envia suas soluções para o problema mestre, que combina esta solução com a solução anterior e computa novos parâmetros. |
O subproblema recebe um conjunto de parâmetros do problema mestre e então envia suas soluções para o problema mestre, que combina esta solução com a solução anterior e computa novos parâmetros. |
||
Revisão das 03h50min de 23 de setembro de 2014
O princípio da decomposição de Dantzig-Wolfe, originalmente desenvolvida pelos matemáticos norte-amercianos George Dantzig e Phil Wolfe, foi publicado em 1960[1] dando início a um intenso trabalho de pesquisa na área de programação matemática em larga escala. Este procedimento é mais adequado quando aplicado à problemas lineares cuja matriz de coeficientes tem uma estrutura angular, isto é, um ou mais blocos independentes lincados por equações acopladas.
Ele opera formando um ``problema mestre`` equivalente, com poucas linhas, mas com número muito maior de colunas. Este problema é então resolvido sem tabular todas as colunas, gerando elas sempre que o método simplex precisa, usando uma tecnica conhecida com geração de coluna.
O algoritmo envolve iterações entre um conjunto de subproblemas cujo função objetivo contém parâmetros variáveis e um problema mestre.
O subproblema recebe um conjunto de parâmetros do problema mestre e então envia suas soluções para o problema mestre, que combina esta solução com a solução anterior e computa novos parâmetros.
Ver também
Referências
- ↑ George B. Dantzig and Philip Wolfe. Decomposition Principle for Linear Programs. Operations Research 8 (1960) pp 101–111