PROGRAMAÇÃO MATEMÁTICA - PESQUISA SOBRE MÉTODO DUAL

...

3. Resumo do Método:

Assumindo que a função objetiva é de maximização, o método dual-simplex envolverá as seguintes etapas:

- Introduzir variáveis de folga e achar uma solução básica inicial tal que todos

- os coeficientes da linha (0) do quadro inicial, estando a função objetiva somente em função das variáveis não-básicas, sejam ≥ 0 . Se esta solução for compatível então ela já é a solução ótima.

- Retirar da base aquela variável que for mais incompatível, isto é, aquela que tiver o menor valor negativo.

- Introduzir na base aquela variável cujo coeficiente na linha (0) atingir zero mais rapidamente quando um múltiplo da equação contendo a variável que sai for somado à linha (0).

- Achar uma nova solução básica e colocar a função objetiva somente em função das variáveis não-básicas. Se esta solução for compatível, isto é, se todos os i b forem ≥ 0 , ela é a solução ótima. Caso contrário, volte ao passo (b).

- Realmente, o método dual-simplex age no primal, exatamente como se o método simplex estivesse sendo simultaneamente aplicado as soluções básicas complementares

- do dual, pois,

- Determinar a variável que sai da base, no método dual-simplex, é equivalente a determinar a variável que entra na base no dual se o simplex estivesse nele sendo aplicado.

- Determinar a variável que entra na base, no método dual-simplex, é equivalente a determinar a variável que sai da base no dual se o simplex estivesse nele sendo aplicado. O coeficiente da linha (0) que atinge zero mais rapidamente corresponde à variável do dual que atinge zero mais rapidamente.

- Os critérios para otimização são também complementares.

4. Referência Bibliográfica

Bartels, R.H. (1971). A Stabilization of the Simplex Method. Numerische Mathematik, 16, 414-434. [ Links ]

(2) Bartels, R.H. & Golub, G.H. (1969). The Simplex Method of Linear Programming Using the LU Decomposition. Communications of the Association for Computing Machinery, 12, 266-268. [ Links ]