RESUMO Programação Linear e Inteira

Busca no Espaço Aplicada a Programação Linear e Inteira

Programação Linear (PL)

Método simplex:
Etapas do método simplex:

1- Incialização: introduza as variáveis de folga. Selecione, então, as variáveis originais para serem as variáveis não básicas originais, igualem a zero e considere as variáveis de folga como sendo as variáveis básicas iniciais. É conveniente o quadro simplex para registrar apenas a informação essencial das equações, isto é, o coeficiente das variáveis, as constantes do lado direto da equação, a variável básica que aparece em cada equação. Cada variável básica é igual a constante do lado direito de sua equação.
2- Regra de Parada: a atual solução básica viável é ótima se e somente se cada coeficiente na eq.(0) for não negativo(>=0). Se assim é, pare; de outro modo vá para o passo iterativo para obter a próxima solução básica viável – a qual envolve transformar uma variável não básica uma variável básica e vice-versa e então resolva para a nova solução.
3- Iteração: Parte 1. Determine a variável básica entrando selecionando a variável com o maior coeficiente negativo na eq.(0), pois esta é a variável não básica que iria aumentar Z a uma taxa mais rápida por estar sendo feita maior que zero. Faça um retângulo circunscrevendo a coluna a baixo deste coeficiente, ela é chamada coluna pivô.
Parte 2. Determine a variável básica saindo: a- Selecione cada coeficiente na coluna circunscrita que seja estritamente positivo(>0) b- Divida o valor do lado direito de cada linha pelo coeficiente correspondente c- Identifique as equações que tenham os menores destas razões d- Selecione a variável básica (vb) para esta equação, pois esta é a vb que primeiro alcança zero a medida que a vb entrando é aumentada.
Faça um retângulo circunscrevendo esta linha da equação no quadro a direita da coluna de Z, esta linha é chamada linha pivô. Parte 3. Determine a nova solução básica viável a partir da construção de um novo quadro simplex .