Investigação Operacional
Métodos de Programação Linear: Gráfica, Simplex
(Mestrado)
Engenharia Industrial
http://dps.uminho.pt/pessoais/zan
Universidade do Minho - Escola de Engenharia
Departamento de Produção e Sistemas
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
1
Representação Gráfica
Considere o seguinte problema de PL:
duas variáveis, permite a representação gráfica do problema
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
2
Representação Gráfica
Não negatividade
Uma restrição
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
3
Representação Gráfica
Duas restrições
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
4
Representação Gráfica
Conjunto de restrições
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
5
Representação Gráfica
Espaço de soluções
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
6
Representação Gráfica
Função objectivo:
família de rectas
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
7
Representação Gráfica
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
8
Soluções de modelos de PL
Conjunto das soluções admissíveis pode ser
–Vazio
–Não vazio (Limitado ou Ilimitado)
Um modelo de PL pode
–Ser impossível
–Ser ilimitado
–Ter soluções óptimas alternativas*
–Ter uma única solução óptima
Os dois primeiros casos, normalmente, indicam que o modelo de PL
está mal formulado ou houve erros na sua introdução, já que não é
frequente existirem problemas de decisão "reais" sem alternativas
ou com alternativas tão boas quanto desejarmos.
* Tipicamente, o software para PL só identifica uma solução óptima.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
9
Soluções de modelos de PL
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
10
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
11
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
12
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
13
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
14
Algoritmos para PL
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
15
Algoritmos para PL
Se tiver curiosidade em ter uma ideia do que é
isto de teoria da complexidade, uma excelente
introdução para leigos é feita em J. Buescu,
“Quem quer ser milionário?”, em “O Mistério do
Bilhete de Identidade e outras histórias –
Crónicas das fronteiras da Ciência”, Gradiva, 4ª
edição, 2002.
Já agora, o problema de PL é um problema do
tipo P (provado em 1979 devido ao método do
Elipsóide) mas o algoritmo Simplex não é
polinomial.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
16
Forma do modelo de PL
•Forma normal /estandardizada / padrão
– Maximização;
– Todas as restrições são equações;
– Todas as variáveis são restringidas a serem não negativas.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
17
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
18
Simplex
Considere um problema de maximização de lucro
relacionado com duas actividades e três recursos.
Na tabela seguinte são dados os consumos unitários de
cada recurso (A, B e C) por actividade (1 e 2), a
disponibilidade de cada recurso e o lucro unitário de
cada actividade.
Formule o problema através de um modelo de PL.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
19
Simplex
• Temos 3 equações e 5 incógnitas (sistema de equações indeterminado).
• Se fixarmos 2 variáveis a zero, temos 3 equações a 3 incógnitas e
podemos determinar a solução desse sistema.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
20
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
21
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
22
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
23
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
24
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
25
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
26
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
27
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
28
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
29
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
30
Simplex
Problema geral: n variáveis, m
equações.
Qualquer conjunto de m variáveis
cujo sistema de equações tenha
solução designa-se por base
(exemplo, x3, x4, x5).
Dada uma base é fácil determinar
a solução lhe está associada, basta
fixar a 0 as variáveis que não
fazem parte da base (variáveis
não básicas, no exemplo dado x1 e
x2) e resolver o sistema de
equações para as restantes
(variáveis básicas) - obtendo-se
uma solução básica
ex. x1=0, x2=0, x3=720, x4=880, x5=160
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
31
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
32
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
33
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
34
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
35
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
36
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
37
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
38
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
39
Simplex
A cada ponto extremo corresponde uma solução básica admissível
(sem coordenadas negativas) e vice-versa.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
40
Simplex
•Uma solução básica pode ser admissível ou não
admissível (no exemplo, A,B,G,F,I correspondem a bases
admissíveis e C,H,E,D a bases não admissíveis). Para
saber se a base é admissível ou não basta ver se as
restrições de não negatividade são satisfeitas.
•Já tínhamos chegado à conclusão de que se existe uma
solução óptima finita, então há, pelo menos, um ponto
extremo que é solução óptima. A cada ponto extremo
está associada uma base admissível...
•...então basta determinar todas as soluções básicas e o
seu valor (na função objectivo) e ver qual é a solução que
tem maior valor (problema de maximização).
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
41
Simplex
•Determinar a solução associada a uma base é fácil:
resolver um sistema de m equações a m incógnitas
(método de Gauss-Jordan).
•Só há um "pequeno" problema, o número de bases pode
atingir
n!
Cm 
n
 n  m  !m !
•Por exemplo, para um problema com 100 variáveis e 10 restrições esse
número é 1.73e+13. Com a folha de cálculo Excel (Microsoft Office 2003)
já não se consegue determinar esse valor para um problema com 2000
variáveis e 250 restrições. O número de combinações é gigantesco para um
problema pequeno!
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
42
Simplex
•Algoritmo Simplex:
– começa-se numa base e vê-se se ela corresponde à
solução óptima (temos maneira de fazer isso?).
– Se for, temos a solução óptima.
– Se não for, passamos para outra base (como?) que
pareça promissora (e como se vê isso?) e repetimos
o procedimento.
•Não parece grande ideia, dado o número de bases ser tão grande...
De facto, a análise (com base na teoria da complexidade) do
comportamento do algoritmo simplex no pior caso não é muito
simpática para este algoritmo (já foram construídos
propositadamente problemas em que o simplex tinha de testar
todas as bases!).
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
43
Simplex
A boa notícia é que, em problemas reais, o
comportamento do algoritmo é muitíssimo melhor do que
a análise para o pior caso da teoria da complexidade.
•O algoritmo Simplex (na verdade, os algoritmos da
classe de métodos Simplex, porque, na prática, há
diferenças consideráveis entre os diferentes algoritmos
que se baseiam nestas ideias) continua a ser largamente
o mais utilizado na resolução de problemas de PL reais.
•O Simplex é um exemplo clássico de como, por vezes, a
análise teórica do pior caso, não é adequada à
classificação prática dos algoritmos.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
44
Simplex
•No seguinte problema qual é a base que tem
uma solução mais fácil de calcular?
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
45
Simplex
•função objectivo: z-10x1-9x2-0x3-0x4-0x5=0
•Os valores que aparecem nesta linha são denominados por custos reduzidos.
•A que solução corresponde o quadro simplex apresentado?
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
46
Simplex
•Um quadro simplex que corresponda a uma solução
básica admissível (primal) tem as seguintes
características:
– Uma coluna correspondente a uma variável básica tem um 1 na
linha associada à variável básica e zeros em todas as outras
linhas (exemplo, a coluna de x5 tem um 1 na terceira linha associada à variável x5 e zeros nas primeira e segunda linhas).
Esta característica implica que as colunas das variáveis
básicas formam uma matriz identidade.
– Na linha da função objectivo, todas as variáveis básicas têm
coeficiente 0.
– Os termos independentes são sempre maiores ou iguais a
zero (manter válida a não-negatividade).
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
47
Simplex
•A cada quadro simplex corresponde uma solução básica
admissível imediatamente perceptível através das
variáveis básicas e da coluna dos termos independentes.
– No exemplo, x3=200, x4=230, x5=70.
•A solução associada ao quadro simplex é óptima?
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
48
Simplex
•Não! Se se aumentar o valor de x1 ou x2 o valor de z
aumenta (e pretende-se maximizar o valor de z). O que o
coeficiente -10 de x1 (linha da função objectivo)
significa é que por cada unidade de aumento de x1 o valor
da função objectivo, aumenta 10 unidades (o sinal
negativo é devido à mudança de membro efectuada
inicialmente).
•Em cada iteração do simplex passa-se (da base actual)
para uma base adjacente (que se obtém da actual
passando uma variável não básica a básica e uma variável
básica a não básica - o número de variáveis básicas é
constante).
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
49
Simplex
•Não! Se se aumentar o valor de x1 ou x2 o valor de z
aumenta (e pretende-se maximizar o valor de z). O que o
coeficiente -10 de x1 (linha da função objectivo)
significa é que por cada unidade de aumento de x1 o valor
da função objectivo, aumenta 10 unidades (o sinal
negativo é devido à mudança de membro efectuada
inicialmente).
•Em cada iteração do simplex passa-se (da base actual)
para uma base adjacente (que se obtém da actual
passando uma variável não básica a básica e uma variável
básica a não básica - o número de variáveis básicas é
constante).
•Qual a variável mais promissora para entrar na base?
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
50
Simplex
•A variável mais promissora é x1 (aumento de 10
unidades na função objectivo por unidade de aumento de
x1, para x2 esse valor é 9 o que é pior já que se está a
maximizar).
– Isto é uma decisão gulosa, míope… não garante que seja a
melhor decisão.
– E se houver empate? (custos reduzidos iguais)
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
51
Simplex
•Sendo assim x1 entra na base (passará a tomar um valor
positivo)!
– Qual a variável que sai base?
•Como o aumento do valor de x1 aumenta o valor da
função objectivo, queremos aumentar o mais possível o
seu valor.
– Qual é o limite?
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
52
Simplex
• Tem de haver um limite (ou melhor, se não houver um
limite o problema é ilimitado, mas não é esse o caso do
exemplo).
O que acontece às outras variáveis
quando se aumenta o valor de x1
A variável x2 continua não básica
(logo com valor igual a 0).
As outras relacionam-se com x1
através das restrições.
Qual a variável que deve sair da base?
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
53
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
54
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
55
Coluna pivot
Universidade do Minho
2006
Simplex
Investigação Operacional
José António Oliveira – [email protected]
56
Coluna pivot
Universidade do Minho
2006
Simplex
Investigação Operacional
José António Oliveira – [email protected]
57
Coluna pivot
Simplex
Linha pivot
A variável que sai da base é x5, a primeira que se anula (logo passa a não
básica) quando se tenta aumentar x1 o mais possível.
A razão entre o valor da coluna dos termos independentes e o valor da coluna da variável que vai
entrar na base para todas as linhas (cujo valor seja positivo) e escolher a menor.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
58
Coluna pivot
Simplex
Linha pivot
(Na resolução primal) O elemento pivot nunca pode ser
negativo.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
59
Coluna pivot
Simplex
Se houver empate na saída?
– escolha indiferente: algoritmo pode entrar em ciclo
– escolhe-se a razão de maior divisor: sai x3
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
60
Simplex
•Como obter o quadro correspondente à nova base?
– Cada linha corresponde a uma equação de um sistema, logo
• pode-se multiplicar toda a linha por uma constante
• pode-se somar duas linhas, substituindo uma delas pelo
resultado da soma, que o sistema de equações não se altera (só
se altera a sua representação). No exemplo, a linha 3 (L3) é a
linha pivot, fazendo as operações
L3 / 2 (para a linha L3)
5L3 + L4 (para a linha L4)
-2L3+L2 (para a linha L2)
-(5/2)L3+L1 (para a linha L1)
Coluna pivot
•obtém-se o quadro simplex correspondente à nova base
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
61
Simplex
Para experimentar e/ou verificar cálculos:
http://www.tutor.ms.unimelb.edu.au/simplex_intro/index.html
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
62
PROGRAMAÇÃO LINEAR - PL
•
Fizemos uma iteração do algoritmo simplex primal:
1.
Teste de optimalidade (a solução básica actual é óptima se todos os
coeficientes da função objectivo (custos reduzidos) são não
negativos). Se a solução é óptima, parar. Se não, prosseguir com o
passo 2.
Decidir qual a variável que entra na base (é aquela que tem o
coeficiente mais negativo na linha da função objectivo - em caso
de empate escolher a variável que “crescerá mais”. Se persistir o
empate, escolher arbitrariamente). Prosseguir com o passo 3.
Decidir qual a variável básica que sai da base (é aquela que tem a
razão do critério de saída mais pequena - excluindo as razões
negativas; em caso de empate, escolher o maior elemento pivot. Se
persistir o empate, escolher arbitrariamente). Se não houver nenhuma
razão estritamente positiva o problema é ilimitado, parar. Se não,
prosseguir para 4.
Actualizar o quadro simplex para a base actual e passar à iteração
seguinte (passo 1).
2.
3.
4.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
63
Simplex
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
64
Simplex
• O quadro simplex obtido em qualquer iteração corresponde
sempre a uma solução básica admissível e a um ponto extremo.
• Quadro óptimo do exemplo (após duas iterações).
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
65
Simplex
• Soluções alternativas
– O que são?
– Como se identifica a sua existência?
•Custo(s) reduzido(s) NULO(s) nas variáveis não básicas.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
66
Simplex
• Degenerescência…
– O algoritmo simplex pode entrar em ciclo (se não
forem tomadas as devidas previdências) por causa
da existência de soluções básicas degeneradas
(soluções em que há variáveis básicas com valor
zero).
– A causa é a presença de restrições redundantes
(que não são fáceis de detectar analiticamente...).
De uma iteração para a seguinte, pode acontecer
que a base seja diferente, mas o valor das
variáveis de decisão seja o mesmo (uma básica com
valor zero sai da base e uma não básica entre na
base com valor zero).
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
67
Simplex
• Degenerescência…
– Na prática, o software actual tem implementadas formas de
lidar com a degenerescência (através de regras mais
sofisticadas do que escolher arbitrariamente a variável que
entra na base em caso de empate).
– De qualquer maneira, em problemas muito degenerados, este
fenómeno pode abrandar significativamente a execução do
método.
Um só ponto extremo
e duas bases!
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
68
Simplex
•Como obter um quadro simplex válido para um problema
que tenha restrições de igualdade e/ou de maior ou
igual?
– Note-se que, se o problema só tiver restrições de "menor
ou igual", temos sempre uma base "à mão": a constituída
pelas variáveis de folga - como no exemplo anterior.
– O ponto de solução nula pertence ao espaço de soluções
válidas, e forma-se a base com as variáveis de folga.
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
69
Simplex
•Modelos (a) e (b) são equivalentes.
– O modelo (b) está na forma estandardizada e inclui uma variável de
excesso (primeira restrição) e uma variável de folga (segunda restrição).
– Para a segunda linha é fácil encontrar uma variável básica inicial (tem
coeficiente 1 na própria linha e 0 nas restantes).
– Qual a variável básica a associar à primeira linha? Não é claro. Não há
nenhuma variável que tenha coeficiente 1 na própria linha e 0 nas
restantes.
•Modifica-se o modelo por inclusão de variáveis
artificiais ->vê-se isso na próxima aula
Universidade do Minho
2006
Investigação Operacional
José António Oliveira – [email protected]
70