Programação linear - Algoritmos: Notas e Compilações

A special thanks to the TA Filipe Vilas Boas for scribing this page

4.6 Programação Linear¶

\begin{array}{ll} \textbf{SIMPLEX}(A,b,c) \langle \langle \text{na forma padrão}\rangle \rangle \\ 1.\quad \text{faça a conversão do programa para a forma relaxada: } (N , B, A, b, c, v) \\ 2.\quad \text{seja } b = (\overline{x_1}, \overline{x_2}, ...) \text{ a solução básica obtida ao atribuir 0 a cada variável não-básica} \\ 3.\quad \text{enquanto existir coeficiente positivo } (c_i ) \text{ na função objetivo } \\ 4.\quad \quad \text{selecione na função objetivo uma variável não-básica } x_e \in N \text{ cujo coeficiente } (c) \text{ seja positivo} \\ 5.\quad \quad \text{selecione a restrição da variável básica } x_l \in B \text{ cujo coeficiente de } x_e \text{ seja negativo e o menor possível}\\ 6.\quad \quad \text{isole } x_e \text{ na restrição da variável básica } x_l\\ 7.\quad \quad \text{substitua } x_e \text{ nas outras equações e função objetivo }\\ 8.\quad \quad \text{neste ponto } x_e \text{ se tornou básica e } x_l, \text{ não-básica}\\ 9.\quad \quad \text{atualize } (N , B, A, b, c, v) \text{ e a solução básica } b = (\overline{x_1}, \overline{x_2}, ...)\\ 10.\! \quad \text{retorne solução } b = (\overline{x_1}, \overline{x_2}, ...) \text{ de custo } v \\ \end{array}