Conferência 5 – Revisão do Período Intermediário 1
Nossas conclusões sobre os tópicos abordados até agora (com a ajuda de BHM) ...
Não pretendemos ser abrangentes ...
8 de março de 2002
Primeira dica: RESPONDA À QUESTÃO FORMULADA!
Segunda dica: TENTE NÃO DEIXAR QUESTÕES EM BRANCO. RESPONDA
ALGUMA COISA! Caso contrário, não poderemos fazer nada por você…
Terceira dica: Certifique -se de ter entendido tudo sobre a prática do meio do
semestre .
Formulações
• Um programa linear tem 3 componentes: variáveis de decisão, função de objetivo e
restrições.
• Uma forma fácil de pensar sobre quantas variáveis de decisão são necessárias, e que
normalmente (mas nem sempre) funciona, é analisar o objetivo e verificar quais dados
de custo/lucro você dispõe. A seguir, deve existir uma variável de decisão para cada
ponto de dados de custo/lucro.
• Não esqueça da não-negatividade.
• Não complique ainda mais o problema (apesar disso ser difícil de cumprir…)
Elabore gráficos em 2D e encontre uma solução ideal
• Em primeiro lugar, remova as restrições e determine a região de viabilidade.
• Somente os vértices podem ser soluções ideais.
• A seguir, estabeleça o objetivo e desloque-o para cima ou para baixo, dependendo se
ele é um problema de maximização ou minimização, para verificar qual vértice é a
solução ótima.
• Para determinar intervalos nos coeficientes da função de objetivo, a inclinação da
mesma deve estar entre as inclinações das 2 restrições de limitação.
Formas Canônica e Padrão
• As condições para uma forma canônica são:
1. Todas as variáveis de decisão são restritas a valores não-negativos.
2. Todas as restrições, exceto para a não-negatividade das variáveis de decisão, são
assumidas como igualdades.
3. Os coeficientes do lado direito são todos não-negativos.
4. Uma variável de decisão é isolada em cada restrição, com um coeficiente +1. A
variável isolada em uma determinada restrição não aparece em nenhuma outra e
aparece com um coeficiente zero na função de objetivo.
• As PLs no formato padrão satisfazem as primeiras 3 condições acima.
• Um sistema de equações pode estar na forma canônica, mas uma PL em forma canônica
deve ter uma função de objetivo (Veja o primeiro ponto das Formulações)
• Se uma PL estiver na forma canônica, então a solução viável básica pode ser lida
imediatamente a partir da formulação/quadro.
Algoritmo Simplex
• Critério da Otimalidade - Suponha que, em um problema de maximização, todas as
variáveis não-básicas têm um coeficiente não-positivo na função de objetivo com uma
•
•
•
•
forma canônica. A seguir, a solução básica viável fornecida por essa forma canônica
maximiza a função objetivo sobre a região de viabilidade.
Critério de Não-limitação - Suponha que, em um problema de maximização, alguma
variável não-básica tem um coeficiente positivo na função de objetivo com uma forma
canônica. Se essa variável tiver coeficientes negativos ou zero em todas as restrições,
então a função de objetivo está na forma não-limitada acima da região de viabilidade.
Critério de Relação e "Pivotamento" - Ao se melhorar uma determinada forma
canônica por meio da introdução de uma variável xs na base, "pivote" em uma restrição
que forneça a relação mínima do coeficiente do lado direito para o coeficiente xs
correspondente. Calcule essas relações somente para restrições que tenham um
coeficiente positivo para xs.
Critério das Múltiplas Soluções Ótimas - Suponha que o critério da otimalidade se
mantém e uma variável não-básica tem um coeficiente zero da função de objetivo na
forma canônica final. Como o valor da função de objetivo permanece inalterado para os
aumentos nessa variável, obtemos uma solução ótima alternativa sempre que pudermos
aumentar a variável por "pivotamento".
Inviabilidade - Isso normalmente tem a ver com variáveis artificiais (veja abaixo) ou
com o fato de que a não-negatividade das restrições é violada.
Fase 1 do Algoritmo Simplex
• A Fase 1 se refere ao processo da primeira transformação de uma PL na forma
canônica, por meio da introdução de slack, surplus (falta ou sobra) e variáveis
artificiais, bem como a substituição por variáveis livres. A seguir, um objetivo pode ser
adicionado, representando a soma das variáveis artificiais. Esse é o objetivo da fase 1,
visando maximizar a negativa da soma, indicada como w.
• Se a solução do programa da fase 1 (ignorando o objetivo original) fornece w <> 0,
então o problema original é inviável. Se w = 0, então uma forma canônica foi
determinada para iniciar o problema original.
• Para obter mais informações, consulte as págs. 57-61 em BHM.
Análise de Sensibilidade
• O preço-sombra associado a uma restrição é a mudança no valor ideal da função de
objetivo por aumento unitário no valor do lado direito para a restrição; todos os outros
dados do problema permanecendo inalterados.
• O custo reduzido associado a uma restrição de não-negatividade para cada variável é o
preço-sombra daquela restrição.
• As restrições de não-agrupamento têm um preço-sombra de 0.
• Os preços-sombra são válidos para um intervalo fornecido pelo relatório de
sensibilidade do Excel.
• O custo reduzido para uma variável é o seu coeficiente de custo no quadro final.
• Se xs é a variável de transigência para uma restrição, então seu custo reduzido é o
negativo do preço-sombra para a restrição.
Preços e Multiplicadores Simplex
• O preço pode ser utilizado para determinar os custos reduzidos.
• Se a coluna j no quadro inicial é uma combinação linear das outras colunas, então ela é
a mesma combinação linear das outras colunas no quadro final. Esse princípio pode ser
utilizado para determinar custos e faixas reduzidas nos preços-sombra.