Wolfe Aplicado ao Problema Combinatório de Job

Transcrição

Universidade Federal da Bahia
Instituto de Matemática
Curso de Pós-graduação em Matemática
Dissertação de Mestrado
Método de Decomposição de Dantzig-Wolfe aplicado ao
problema combinatório de Job-Shop
Azly Santos Amorim de Santana
Salvador-Bahia
Outubro 2003
Método de Decomposição de Dantzig-Wolfe aplicado ao
problema combinatório de Job-Shop.
Dissertação apresentada ao colegiado do curso de Pós-Graduação em Matemática da Universidade
Federal da Bahia, como requisito parcial para obtenção do Tı́tulo de Mestre em Matemática Pura.
Banca examinadora
Profa . Dra Isamara Carvalho Alves (Orientadora).
Prof. Dr. Isaac Costa Lázaro
Prof. Dr. Jés de Jesus Fiais Cerqueira
Santana, A.
“Método de Decomposição de Dantzig-Wolfe aplicado ao problema combinatório de Job-shop” / Azly Santos Amorim de Santana.
Salvador-Ba, 2003.
Orientadora: Dra.
Isamara Carvalho Alves (Universidade Federal da
Bahia).
Dissertação de Mestrado apresentada ao curso de Pós-graduacão em
Matemática da UFBA, 91 páginas.
Palavras-Chave:Métodos de Decomposição, Decomposição de Problemas
Combinatórios, Método de Decomposição de Dantzig-Wolfe, Problemas de
Seqüenciamento do tipo Job-Shop.
A Deus, meus Pais e Mô.
“Você é do tamanho do seus sonhos.”
César Souza.
Agradecimentos
Nesta etapa da vida, algumas pessoas contribuı́ram para o meu crescimento profissional e
espiritual. Agradeço com carinho aos meus pais pela incondicional credibilidade e apoio em todas
as minhas decisões. A “Mô” pela confiança, paciência e amor. A Ana Rita e Simone por me fazer
entender o verdadeiro conceito de amizade. Aos meus primeiros e eternos amigos acadêmicos Adriana
(Di), Ana Paula (Paulinha), Abı́lio (Bilolão), Gilson (Ligeirinho), Luciano (Negão), Moema (Mó),
Osvaldo (Junico) e Rogério (Mancha). Agradeço com muitas saudades os momentos de apoio e diversão
aos queridos companheiros, Adriano (Didi), Alex (Pig), Andréa (Déa), Ariadne, Calitéia (Baixinha),
Conceição (Ceiça), Claúdio (Mano), érica (Kinha), Gilmar (Tchê), Ivana (Mocó), Ismar (Dindo),
Jorge (Gump), José Joaquim, Juceli (Jú), Laura (Gospel), Maurı́cio (Tio Mau), Odete (Amanda),
Paulo (Nasci), Reinaldo (Amigo), Rosely (Rosy), Stela (Pró), Rui. Aos professores Bahiano, Enaldo,
Elinalva, Isaac, Marco Antonio, pelo profissionalismo e caráter, ao professor Jés pela disponibilidade e
sugestões e, em especial, a Isamara pela credibilidade e dedicada orientação. Finalmente, à secretária
Tânia por ter sido sempre tão prestativa e a grande amiga Cı́ntia Lé que tanto torceu por este tı́tulo
de mestre.
vi
Resumo
Neste trabalho, é abordado o método de decomposição de Dantzig-Wolfe aplicado ao problema de seqüenciamento do tipo job-shop. Este problema tem como caracterı́stica principal sua complexidade computacional na categoria de um problema NP-difı́cil(Jonhson[16] e Zwaneveld[35]). Tais
problemas estão sujeitos a um conjunto de restrições envolvendo as operações nos produtos e nas
máquinas, cujo objetivo é diminuir o custo de produção. A metodologia aplicada consiste em decompor o problema de job-shop em blocos (i é, subproblemas), reduzindo um grande volume de cálculo
central por cálculos locais. Estes subproblemas são resolvidos separadamente e as suas soluções são
supervisionadas por um nı́vel coordenador denominado Problema Mestre. Desta forma, o Problema
Mestre gerencia as soluções fazendo com que as combinações convexas destas gerem a solução do
problema global.
Sendo assim, a partir do problema de job-shop, podemos formular o Problema Mestre e os subproblemas correspondentes. Cada subproblema é associado ao conjunto de restrições de uma máquina
e ao Problema Mestre está associado as restrições de acoplamento representadas pelas restrições de
precedência nos produtos. Contudo, ocorre que o conjunto de soluções viáveis de cada subproblema
é ilimitado e pode acontecer infactibilidade. Conseqüentemente, propomos algumas modificações que
permitem a aplicabilidade do método aos problemas de seqüenciamento do tipo job-shop. Os resultados encontrados por meio de testes numéricos em problemas de pequeno porte mostraram que a
convergência do método é possı́vel, desde que sejam adotados limites adequados para as variáveis do
problema.
PALAVRAS CHAVE: Métodos de Decomposição,Decomposição de Problemas Combinatórios, Método de Decomposição de Dantzig-Wolfe, Problemas de Seqüenciamento do tipo Job-Shop.
Abstract
This work, address the Dantzig-Wolfe decomposition method applied in job-shop scheduling problems. These problems are well known as NP-hard in the strong sense (Johnson [16] and
Zwaneveld [35]) constrained by capacity and precedence constraints, whose objective is decreasing
the manufacturing cost. The use of this method is justified by the block angular structure of the
technological coefficients matrices. Hence, the applied methodology decomposes the original problem
into blocks (subproblems) supervisioned by a coordinator level (master problem) decreasing a large
volume of central calculus by several local calculus. These subproblems receive a set of parameters
from the master problem and their solutions are sent to the master problem, which combines these
with previous solutions in the optimal way and computes new prices.
From the job-shop problem, the master problem can be modelled considering link constraints
the precedence constraints and the each subproblem is associated with one machine. However, the
viable solution set of each subproblem is unbounded and the method may converge to an unfeasible
solution. Consequently, we propose an modification which will allow us the applicability of this method
in the job-shop problem. The results obtained from numeric tests of lower dimensions showed us that
the convergence of the method is possible since adequate limit are adopted is possible since adequate
limits are adopted.
KEY-WORDS: Decomposition Methods, Dantzig-Wolfe Decomposition Method,Job-Shop
Scheduling Problems.
Sumário
Resumo
vii
Abstract
viii
Lista de Figuras
xi
Lista de Tabelas
xiii
Introdução
1
1 Método de Decomposição de Dantizg-Wolfe
3
1.1
Princı́pio da Decomposição de Dantzig-Wolfe . . . . . . . . . . . . . . . . . . . . . . .
5
1.2
Algumas considerações sobre o algoritmo de Dantzig-Wolfe . . . . . . . . . . . . . . .
11
1.3
Problema Mestre Restrito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.4
Estratégia alternativa para decompor o primal . . . . . . . . . . . . . . . . . . . . . .
12
1.5
Região Xi ilimitada
14
1.6
Limite inferior para o custo mı́nimo
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
1.7
Interpretação econômica do método
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
1.8
Exemplo numérico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Os Problemas de Job-Shop
2.1
2.2
3
27
Os problemas de fábrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
2.1.1
Os produtos e os critérios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
2.1.2
As máquinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
O Problema de Job-Shop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.2.1
Formulação Matemática
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
2.2.2
Métodos de Resolução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
Método de Dantzig-Wolfe e o Problema de Job-Shop
3.1
Decomposição do Job-Shop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
37
37
Sumário
3.2
x
3.1.1
Modelagem Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
3.1.2
Método de Dantizg-Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
3.1.3
Aplicação do método de Dantzig-Wolfe ao Job-Shop . . . . . . . . . . . . . . .
40
3.1.4
Região Xk ilimitada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
Problemas Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
3.2.1
Problema Teste 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
3.2.2
Problema Teste 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
Conclusão
81
Apêndice
83
Referências Bibliográficas
86
Índice Remissivo
89
Lista de Figuras
1.1
Comportamento dos métodos de decomposição. . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Estrutura bloco-angular com restrições de acoplamento. . . . . . . . . . . . . . . . . .
5
1.3
Estrutura bloco-angular com variáveis de acoplamento. . . . . . . . . . . . . . . . . . .
5
1.4
Estrutura bloco-angular com restrições e variáveis de acoplamento. . . . . . . . . . . .
5
1.5
Região factı́vel do conjunto X1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
1.6
Região factı́vel do conjunto X2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.1
Grafo potencial-tarefa representando o exemplo do job-shop. . . . . . . . . . . . . . . .
32
2.2
Diagrama de Gantt representando duas soluções para o exemplo do job-shop. . . . . .
32
2.3
Grafo conjuntivo da solução S2 para o exemplo do job-shop. . . . . . . . . . . . . . . .
33
3.1
Convergência do método do problema teste 1. . . . . . . . . . . . . . . . . . . . . . . .
64
3.2
Diagrama de Gantt representando as soluções encontradas do problema teste 1. . . . .
64
3.3
Convergência do método do problema teste 2. . . . . . . . . . . . . . . . . . . . . . . .
79
3.4
Diagrama de Gantt representando as soluções encontradas do problema teste 2. . . . .
79
A.5 Direções e direções extremas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
xi
Lista de Tabelas
1.1
Tabela do Método Simplex Revisado referente ao problema mestre. . . . . . . . . . . .
15
1.2
Tabela inicial do simplex revisado do problema mestre. . . . . . . . . . . . . . . . . . .
21
1.3
Entra na base a variável λ22 , sai λ12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
1.4
Entra na base a variável λ21 , sai s. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
1.5
Solução ótima do exemplo 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
1.6
Entra λ31 e sai λ11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
1.7
Solução ótima do exemplo 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.1
Dados do problema-exemplo de job-shop. . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.1
Tabela do simplex revisado do problema mestre. . . . . . . . . . . . . . . . . . . . . .
45
3.2
Dados do problema teste 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
3.3
Tabela inicial do simplex revisado do P.M do problema teste 1. . . . . . . . . . . . . .
52
3.4
Entra na base a variável λ22 , sai s4 .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
3.5
Entra na base a variável λ32 , sai s2 .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
3.6
Tabela final na iteração 1 do problema teste 1. . . . . . . . . . . . . . . . . . . . . . .
55
3.7
Entra na base a variável λ33 , sai λ32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
3.8
Tabela final na iteração 2 do problema teste 1. . . . . . . . . . . . . . . . . . . . . . .
58
3.9
Entra na base a variável λ34 , sai λ33 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
3.10 Tabela final da iteração 3 do problema teste 1. . . . . . . . . . . . . . . . . . . . . . .
61
3.11 Limites por iteração do problema teste 1. . . . . . . . . . . . . . . . . . . . . . . . . .
63
3.12 Comparação das soluções do problema teste 1. . . . . . . . . . . . . . . . . . . . . . .
63
3.13 Dados do problema teste 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
3.14 Tabela inicial do simplex revisado do P.M do problema teste 2. . . . . . . . . . . . . .
71
3.15 Entra λ32 , sai s2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
3.16 Entra λ12 ,sai λ11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
xii
Lista de tabelas
xiii
3.17 Entra λ22 , sai s1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
3.18 Tabela final na iteração 1 do problema teste 2. . . . . . . . . . . . . . . . . . . . . . .
75
3.19 Entra λ23 ,sai λ22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
3.20 Tabela final na iteração 2 do problema teste 2. . . . . . . . . . . . . . . . . . . . . . .
76
3.21 Limites por iteração do problema teste 2. . . . . . . . . . . . . . . . . . . . . . . . . .
78
3.22 Comparação das soluções do problema teste 2. . . . . . . . . . . . . . . . . . . . . . .
78
Introdução
Em geral os métodos de decomposição consistem em decompor um problema inicial de grande
porte em problemas com dimensões menores, denominados subproblemas (ou problemas escravos). Tais
subproblemas são supervisionados por um nı́vel de coordenação denominado Problema Mestre (ou
problema coordenador). O procedimento consiste de um conjunto de subproblemas independentes cuja
função objetivo e/ou vetor dos recursos (composta dos multiplicadores simplex do problema mestre)
são atualizados a cada ITERAÇÃO de acordo com os parâmetros recebidos do problema coordenador.
Assim, a cada ITERAÇÃO, os subproblemas são resolvidos separadamente e, em seguida, enviam suas
soluções ao Problema Mestre.Esta troca de informações entre o Problema Mestre e os subproblemas
é realizada em um número finito de iterações, garantindo a convergência para o valor ótimo, ou
um sub-ótimo, do problema global. Dentre os principais métodos de decomposição podemos citar:
as técnicas da Relaxação Lagrangeana[17][19][27]; o método de Dantzig-Wolfe [10][27]; o método de
Benders[5][18][27]; e o método de Rosen[27]. A aplicação desses métodos dependerá da estrutura
matricial dos coeficientes que envolvem o problema.
Este trabalho aborda, em particular, o método de decomposição de Dantzig-Wolfe. Este
método é aplicado em problemas lineares de grandes dimensões onde a matriz de coeficientes possui
uma estrutura especial do tipo bloco angular, isto é, um ou mais blocos independentes são acoplados
por um conjunto de restrições. As restrições de acoplamento, juntamente com a propriedade que
permite reescrever elementos de um conjunto convexo como combinação linear convexa dos seus pontos
extremos, possibilita a formação de um problema equivalente com um número menor de restrições
denominado Problema Mestre. Este problema é resolvido por meio do método simplex revisado ([4]).
O procedimento de resolução tem uma interpretação econômica a qual diz que o problema mestre
coordena as ações dos subproblemas enviando os valores dos multiplicadores do simplex associados
aos recursos usados no problema.
O problema de seqüenciamento do tipo job-shop é um problema combinatório conhecido
Introdução
2
por sua complexidade na categoria de um problema NP-difı́cil (Johnson[16] e Zwaneveld [35]). Além
disso, os coeficientes das suas restrições apresentam uma estrutura matricial bloco angular. Tais
caracterı́sticas justificam a aplicação de um método de decomposição. Podemos então a partir do
problema de job-shop, formular um problema equivalente em dois nı́veis conforme apresentado no
método de Dantzig-Wolfe. Para isso, construiremos o problema mestre considerando como restrições
de acoplamento as restrições de precedência (restrições nos produtos), e a cada conjunto de restrições
de máquina associaremos um subproblema. No entanto, o conjunto de soluções viáveis é ilimitado e
pode acontecer subproblemas infactı́veis. Conseqüentemente, são necessárias algumas modificações nos
espaços de soluções para garantir a aplicabilidade do método ao problema de job-shop. Primeiramente,
propomos a criação de limites relacionadas às variáveis envolvidas nas restrições de acoplamento a fim
de limitar os conjuntos de soluções. Em seguida, efetuamos o ajuste das soluções obtidas para garantir
a converg encia ao valor ótimo do problema global. O texto está organizado da seguinte forma:
O Capı́tulo 1 começa descrevendo brevemente os métodos de decomposição e em quais casos podem ser utilizados. Em seguida, enfatizamos o método de decomposição de Dantzig-Wolfe,
mostrando de que forma o mesmo é estruturado e quais as alterações necessárias para o caso no qual o
conjunto de soluções é ilimitado. Além disso, mostramos como podemos determinar um limite inferior
para a solução ótima do problema original bem como a interpretação econômica do método.
O Capı́tulo 2 tem como objetivo definir o problema de job-shop e apresentar a formulação
matemática adotada. apresentamos as restrições adotada para o job-shop e as suas principais caracterı́sticas, assim como a sua representação pelo grafo potencial-tarefa e pelo Diagrama de Gantt.
Finalmente, no Capı́tulo 3, reescrevemos o método de Dantzig-Wolfe adaptando-o à notação
adotada ao problema de job-shop e aplicando ajustes ao conjunto das soluções viáveis de forma tal
que garanta a factibilidade do problema mestre e dos subproblemas. Concluı́mos apresentando testes
numéricos e as respectivas análises que validam a aplicabilidade do método em problemas de pequenas
dimensões.
Capı́tulo 1
Método de Decomposição de
Dantizg-Wolfe
Em geral, os métodos de decomposição consistem em decompor um problema inicial de grande
porte em problemas com dimensões menores, denominados subproblemas ( ou problemas escravos )
permitindo substituir um grande volume de cálculo central por cálculos locais. Tais subproblemas
trabalham de forma paralela, seqüencial ou interativa, supervisionados por um nı́vel de coordenação,
denominado problema mestre (ou problema coordenador). O problema mestre recebe informações dos
subproblemas e altera, a cada iteração, os parâmetros que atualiza a função custo e/ou o vetor de
recursos de cada subproblema, permitindo através de suas soluções uma aproximação para a solução
ótima global, se esta existir. Na Figura 1.1, este processo é representado considerando o problema
original particionado em p subproblemas, onde t1 , t2 , · · · , tp são as soluções locais dos correspondentes
subproblemas e os λ0 s é o vetor-solução do problema mestre.
PROBLEMA MESTRE
t1
λ
λ
tp
SUBPROBLEMA
SUBPROBLEMA
No 1
No p
Figura 1.1: Comportamento dos métodos de decomposição.
Princı́pio da Decomposição de Dantizg-Wolfe
4
Os métodos de decomposição são utilizados quando temos um/ou mais dos seguintes objetivos:
• Reduzir a dimensão do problema quando o número de variáveis e/ou de restrições é muito elevado
a fim de efetuar a resolução dos subproblemas de dimensões menores;
• Hierarquizar um processo de decisão em vários nı́veis, onde cada unidade econômica possui uma
unidade de controle que garante a coordenação entre os subsistemas dos nı́veis inferiores;
• Descentralizar um problema de decisão decompondo-o em subproblemas com suficiente autonomia para tomar suas próprias decisões;
• Particionar um problema com dados heterogêneos em subproblemas homogêneos;
• Paralelizar de acordo com a evolução do material para o cálculo paralelo (multitarefa, multiprocessador).
O Princı́pio da decomposição, consiste inicialmente em analisar a estrutura do problema e,
a partir desta informação, fazer a escolha do método de decomposição mais adequado. Dentre os principais métodos clássicos de decomposição podemos citar: as técnicas da Relaxação Lagrangeana[17][19][27];
o método de Dantzig-Wolfe [10][27]; o método de Benders[5][18][27] e o método de Rosen[27]:
(i) O método da Relaxação Lagrangeana e o de Dantzig-Wolfe são aplicados aos problemas que
apresentam a matriz de coeficientes com a estrutura bloco-diagonal com restrições de acoplamento
conforme apresentada na Figura 1.2;
(ii) O método de Benders é aplicado aos problemas que apresentam a matriz de coeficientes com a
estrutura bloco-angular com variáveis de acoplamento conforme a Figura 1.3;
(iii) O método de Rosen é aplicados aos problemas que apresentam a matriz de coeficientes com a
estrutura bloco-angular com restrições e variáveis de acoplamento conforme a Figura 1.4.
Este trabalho enfatiza o método de Dantzig-Wolfe. Sendo assim, este capı́tulo aborda o
algoritmo de decomposição de Dantzig-Wolfe considerando conjuntos de soluções limitados e ilimitados.
RESTRIÇÕES DE
ACOPLAMENTO
{
5
A2
A1
AP
B1
B2
BP
Figura 1.2: Estrutura bloco-angular com restrições de acoplamento.
{
VARIA´VEIS DE
ACOPLAMENTO
B1
b1
b2
B2
bP
BP
Figura 1.3: Estrutura bloco-angular com variáveis de acoplamento.
{
VARIA´VEIS DE
ACOPLAMENTO
RESTRIÇÕES DE
ACOPLAMENTO
{
A1
A2
AP
B1
b0
b1
b2
B2
BP
bP
Figura 1.4: Estrutura bloco-angular com restrições e variáveis de acoplamento.
1.1
Princı́pio da Decomposição de Dantzig-Wolfe
Consideremos o Programa Linear:


min z = cx





 Sujeito a :
(P L)

 Ax = b





x≥0
cuja matriz dos coeficientes das restrições tem estrutura p-bloco angular, com p ≥ 1, na forma:


 A1 A2 · · · Ap 



 B1




 .

A= 
B2



..


.




Bp
(1.1)
6
Notemos que qualquer programa linear pode ser visto nesta forma se for considerado p=1.
Assim, particionando o conjunto de restrições em dois subconjuntos, de acordo com a matriz A, temos
o (P L) (1.1) como segue













min z = cx
Sujeito












(1.2)
a:
Â1 x = b1 (r1 restrições)
(1.3)
A2 x = b2 (r2 restrições)
(1.4)
x ≥ 0
(1.5)
Assumiremos que o poliedro convexo (Ver definição no Apêndice)
S2 = {x|A2 x = b2 , x ≥ 0}
é limitado, e chamaremos o conjunto E = {x1 , · · · , xj , · · · , xr } dos r pontos extremos de S2 . Portanto,
qualquer x ∈ S2 pode ser escrito como combinação convexa destes pontos extremos:
r
X
x=
λj xj
(1.6)
j=1
onde
r
X
λj = 1,
(1.7)
λj ≥ 0; j = 1, · · · , r.
(1.8)
j=1
O problema original (1.2) - (1.5) deverá ser visto como segue: selecionemos, de todas as
soluções de (1.4) e (1.5), aquelas que satisfazem (1.3) e minimize z. Substituindo (1.2) em (1.6) e
(1.3), obtemos
r
X
(Â1 xj )λj = b1 ,
(1.9)
j=1
e
z=
r
X
(cxj )λj .
(1.10)
= Â1 xj ,
(1.11)
= cxj ,
(1.12)
j=1
Definindo,
pj
e
fj
7
teremos o Programa Linear (1.2)-(1.5)
na variável λj :

r
X



min
z
=
fj λj




j=1





Sujeito
a:



r

X
pj λj = b1


j=1



r

X



λj = 1




j=1



λj ≥ 0;
j = 1, · · · , r.
(1.13)
(1.14)
(1.15)
(1.16)
Este novo problema (1.13)-(1.16), denominado Problema Mestre (PM), é equivalente ao
problema original (1.2) - (1.5). O PM contém apenas (r1 + 1) restrições, enquanto que o problema
original possuı́a (r1 + r2 ), significando assim uma considerável redução no número de restrições para
r2 muito grande.
Particularmente, a técnica do Método Simplex Revisado [4] é usado para resolver o PM.
Veremos então como isto é feito considerando o coeficiente do custo relativo f¯j para a variável λj do
seguinte modo:

pj


f¯j = fj − π  − − −

1



;

(1.17)
onde o vetor π = fB B −1 , para fB = cB xB , ou seja, π é o vetor dos multiplicadores do simplex.
Agora, vamos particionar π: π = (π1 , π0 ) onde π1 é o vetor das variáveis duais correspondentes
às restrições(1.14) e π0 é a variável dual correspondente à única restrição (1.15). Então, usando as
definições (1.11) e (1.12) de fj e pj em f¯j podemos reescrevê-lo na forma,
f¯j = (c − π1 Â1 )xj − π0 .
(1.18)
O critério usual do método simplex considera
min f¯j = f¯s = (c − π1 Â1 )xs − π0 ;
j
(1.19)
indicando desta forma a variável λs para entrar na base. Relembremos que xj é um ponto extremo
de S2 , e notemos que f¯j é linear em xj . Sabendo-se que uma solução ótima de um programa linear
convexo, cujo conjunto de restrições é limitado, sempre ocorre em um ponto extremo deste conjunto,
notemos que a expressão (1.19) é equivalente ao subproblema definido como











8
min (c − π1 Â1 )x
(1.20)
Sujeito a :










A2 x = b2 ,
(1.21)
x ≥ 0.
(1.22)
Seja xs o ponto ótimo do subproblema (1.20) - (1.22) com valor objetivo f¯s . Se f¯s ≥ 0
significa que todos os custos relativos à base λj são não positivos, logo não podemos mais melhorar a
solução do PM. Em decorrência, assumiremos que a solução ótima do problema original PL(1.1) é
0
x =
r
X
λj xj
(1.23)
j=1
onde os xj ’s são pontos extremos de S2 correspondentes à base λj .
Caso contrário, sef¯s < 0 ainda
podemos melhorar a solução do PM. Daı́, λs entra na base

s
Â1 x
 é atualizada, pré-multiplicando-a pelo inverso da base de λj ,ou
e a coluna correspondente 
1


s
Â1 x
. Notemos que ys ≤ 0 não pode ocorrer visto
seja B −1 , originando a nova coluna ys = B −1 
1
que S2 foi assumido como limitado produzindo um problema mestre limitado.
A variável λB a sair da base é determinada pela razão mı́nima usual, ou seja, deixa a base a
variável λr onde o ı́ndice r é determinado como segue:
b̄r
b̄i
=
min { , yis > 0};
yrs 1≤i≤(m+1) yis
(1.24)
onde yrs é denominado elemento pivô. Com o pivoteamento, a base inversa,(B −1 ), as variáveis
duais,(π), e o valor objetivo (z) são atualizados.
Este procedimento torna-se bastante interessante se p > 1, isto é, se o problema resolvido
tem a forma
9





min z = c1 x1 + c2 x2 + · · · + cp xp













Sujeito a:







A1 x1
+ A2 x2 + · · · + Ap xp = b0
























B1 x1
= b1
B2 x2
..
= b2
.
= ..
.
(1.25)
(1.26)
Bp xp = bp
x1 ≥ 0, x2 ≥ 0, · · · , xp ≤ 0.
com o subproblema (1.20) - (1.22)

p
X



(ci − π1 Â1 )xi
min




i=1







Sujeito a:






Bi xi = bi , i = 1, · · · , p






xi ≥ 0, i = 1, · · · , p.
(1.27)
(1.28)
(1.29)
(1.30)
O objetivo (1.28) é uma soma separável em xi e as restrições (1.29) são independentes. Desta
forma, este problema pode ser reduzido a p-subproblemas independentes, onde o i-ésimo subproblema
pode ser representado como segue:




min (ci − π1 Ai )xi .





















Sujeito a :
(1.31)
(1.32)
Bi xi = bi ,
xi ≥ 0.
(1.33)
Adotando-se
Xi = {xi |Bi xi = bi ; xi ≥ 0},
(1.34)
o i-ésimo subproblema apresenta-se:
min (ci − π1 Ai )xi .
xi ∈Xi
(1.35)
Um algoritmo de dois nı́veis para resolver o problema de (1.25) - (1.27) deverá agora ser
formulado com o problema mestre (1.13) - (1.16) no primeiro nı́vel e os subproblemas (1.31) - (1.33)
Algoritmo de Dantzig-Wolfe
10
no segundo. Assumiremos que uma solução inicial do problema mestre é conhecida com a matriz base
correspondente, B, e as variáveis duais π1 , π0 .
Neste caso, o algoritmo de decomposição de Dantzig-Wolfe pode ser visto como segue:
Algoritmo 1.1. Algoritmo de Decomposição de Dantzig-Wolfe
1. Usando as variáveis duais π1 , resolvemos cada subproblema i (1.31) - (1.33) obtendo
as suas respectivas soluções xi (π1 ), e o valor ótimo objetivo, zi0 . Seja
x(π1 ) = (x1 (π1 ), · · · , xp (π1 ))t .
2. Calculamos os valores dos custos relativos das variáveis λ0j s, f¯j (1.18), e escolhemos
o mı́nimo entre eles:
min f¯j =
j
p
X
zi0 − π0 ;
(1.36)
i=1
onde
zi0 = min (ci − π1 Ai )xi .
(1.37)
Se este valor mı́nimo for um valor não negativo, ou seja ,
min f¯j ≥ 0,
(1.38)
significa que podemos parar o algoritmo, pois não existem mais candidatas a entrar na
base. Assim, a solução ótima para (1.25) - (1.27) é
x0 =
r
X
λj xj ,
(1.39)
j=1
onde xj são pontos extremos de S2 correspondentes à variável básica λj .
3. Se min f¯j < 0, construı́mos a coluna




p
X

Ai xi (π1 ) 

i=1

1
(1.40)
atualizada através da multiplicação pela inversa da antiga base, B −1 , e usando a operação
pivô do simplex usual, obtemos uma nova base inversa e um novo vetor dos multiplicadores
simplex (variáveis duais). Retornamos à 1 e repetimos todo o processo.
Observações
11
Se o problema mestre é não degenerado[4], então cada iteração decresce z para um valor não
nulo. Isto se deve ao fato que existe um número finito de bases possı́veis e nenhuma se repete. Sendo
assim, o princı́pio da decomposição de Dantzig-Wolfe encontrará a solução ótima em um número finito
de iterações.
Observe que a solução ótima do problema original, x0 , não é necessariamente qualquer uma
das soluções dos subproblemas. Por (1.39) temos que x0 é alguma combinação convexa de tais soluções.
Portanto, o problema mestre não pode obter o ótimo do problema original simplesmente enviando os
correspondentes custos π1 aos subproblemas. O problema mestre deverá combinar estas soluções para
obter a solução global.
1.2
Algumas considerações sobre o algoritmo de Dantzig-Wolfe
1. Observamos que o seguinte algoritmo é uma implementação direta do método simplex revisado.
Exceto o cálculo dos custos relativos f¯ij que é obtido resolvendo o subproblema i. Entretanto, o
algoritmo converge em um número finito de iterações.
2. Em cada iteração, uma melhor solução básica factı́vel para o problema mestre, (1.47)-(1.53),
é obtida ao introduzir a variável não básica λsj , gerada pela solução do subproblema, (1.55)
- (1.57). Sendo assim,
osubproblema fornece um ponto extremo xjs , que corresponde a uma

f¯sj
.
coluna atualizada 
ysj
3. Em cada iteração um novo vetor dual é passado do problema mestre para o subproblema. A base
ótima da última iteração é utilizada, a fim de atualizar a sua função, modificando seus custos.
4. Em cada iteração, o subproblema não precisa ser otimizado completamente. é necessário apenas
que o corrente ponto extremo xjs satisfaça f¯sj ≤ 0. Neste caso λsj é candidato a entrar na base.
5. Se as restrições do problema mestre são desigualdades, então nós devemos verificar os custos das
variáveis de folga que foram adicionadas resolvendo os subproblemas. Para as restrições i do
problema mestre do tipo ≤ associada à variável de folga si , nós temos,


e1
 − 0 = π1 .
fsi − zsi = (π1 , π0 ) 
0
(1.41)
Assim, para um problema de minimização uma variável de folga associada com a restrição do
tipo ≤ é eleita a entrar na base se π1 > 0. ( Note que o critério de entrada é π1 < 0 para
restrições do tipo ≥).
Problema Mestre Restrito
12
6. Para darmos inı́cio ao método, deveremos partir de uma solução básica factı́vel inicial. Caso,
esta solução não seja possı́vel ao ser acrescentado as variáveis de folga, devemos usar algum
método para obter tal solução; como por exemplo o Método das Duas Fases ou do Big-M[4].
1.3
Problema Mestre Restrito
Como previamente formulado, o princı́pio da decomposição de Dantzig-Wolfe, resolve proble-
ma de otimização em dois nı́veis. Ao nı́vel chamado Problema Mestre (1.13) - (1.16), é possı́vel apresentar uma nova formulação denominada de Problema Mestre Restrito. Tal problema apresenta
além das colunas referente à variável de entrada, as colunas das variáveis que foram retiradas. Então
o problema mestre restrito pode ser
escrito na forma



min f1 λ1 + · · · + fm λm + f λ












 Sujeito a:
(1.42)
(1.43)


p
λ
+
·
·
·
+
p
λ
+
pλ
=
b

1 1
m m
0






(1.44)

λ1 + · · · + λm + λ = 1





 λ ≥ 0, i = 1, · · · , m, λ ≥ 0
(1.45)
i
0
onde m = m1 + 1, os λi s são as variáveis básicas corrente e λ é a variável que está entrando na base.
Assumindo que a variável λ tem um custo relativo f¯ < 0, se a base corrente é não degenerada, a
variável que deixar a base terá um f¯ positivo, e portanto, a nova solução será ótima. O único caso no
qual mais de uma iteração é necessária para passar o teste de otimalidade é quando a base corrente
é degenerada e o elemento pivô, (1.24), na coluna de entrada é negativo. Neste caso, não é muito
vantajoso resolver o problema na forma (1.42) - (1.45).
1.4
Estratégia alternativa para decompor o primal
Uma outra forma de decompor o problema primal (1.25) - (1.27), alterando a forma do
problema mestre (1.13) - (1.16), é considerar as soluções para o conjunto de restrições do subproblema
i escritas como:
xi =
r
X
λij xji
(1.46)
j=1
com o xji ponto extremo de Xi (1.34); i = 1, 2, · · · , p. Então, é fácil verificar que o problema mestre
resulta em
Estratégia alternativa para decompor o primal

























13
min
p X
r
X
fij λij
(1.47)
Sujeito a:
p X
r
X
pij λij = b0
(1.48)
i=1 j=1


i=1 j=1



r

X



λij = 1, i = 1, 2, · · · , p,




j=1







λij ≥ 0




onde
fij
pij
= ci xji
= Ai xji
(1.49)
(1.50)
(1.51)
(1.52)
(1.53)
Este novo problema apresenta algumas vantagens computacionais que podem ser vistas
quando consideramos as soluções de (1.47) - (1.53) pelo método simplex revisado. Além disso, difere
do problema mestre (1.13) - (1.16) obtido inicialmente, em dois aspectos: (1) particularmente, ele
tem p linhas convexas;(2) cada subsistema Bi xi = bi , xi ≥ 0, é representado separadamente por um
conjunto de variáveis λij .
Sejam B uma matriz básica factı́vel (m1 + p) × (m1 + p) e π1 , π01 , · · · , π0p as variáveis duais
para esta base, com π1 associado à restrição (1.48) e os π0i associados à restrição (1.49). Atualizando
a coluna associada à λij , produzimos
f¯ij = (ci − πAi )xji − π0i .
(1.54)
O problema encontrado para i fixo, min f¯ij , é equivalente a resolver o i-ésimo subproblema
j




min (ci − π1 Ai )xi
(1.55)





















Sujeito a:
(1.56)
Bi xi = bi ,
xi ≥ 0.
(1.57)
Esses são os mesmos subproblemas conforme foram obtidos previamente em (1.31) - (1.33).
O caso da região Xi ilimitada
14
Seja zi0 o valor objetivo minimal do subproblema (1.55) - (1.57) acima. Se
f¯sj = min min f¯ij = min (zi0 − π0i ) ≥ 0
i
j
i
(1.58)
a solução corrente é ótima. Caso contrário, a coluna a entrar na base é aquela com
min(zi0 − π0i ).
i
(1.59)
Se o mı́nimo acima ocorre para i = se xjs (π1 ) é solução
 do subproblema s, a coluna correspon-
As xjs (π1 )




dente à variável a entrar na base é dada por  − − − − −  , onde us é um vetor p-componente com


us
um na posição s e zeros nas outras. Esta nova coluna entra na base produzindo novos multiplicadores
(π1 , π0 ). Colunas similares poderiam ter sido gerados das soluções de outros subproblemas.
Seja m = m1 +p, definimos {pij } como as colunas da base corrente, e seja p∗1 , · · · , p∗p as colunas
geradas das últimas soluções dos subproblemas correspondentes a λ∗1 , λ∗2 , · · · , λ∗p . O novo problema
mestre restrito será
1.5

p
p
X
X
X



min
fij λij +
fi∗ λ∗i = b0




i=1 j básico
i=1




p
p

X
X
X




p
λ
+
p∗i λ∗i = b0
ij ij


i=1 j básico
i=1

X



λij + λ∗i = 1; i = 1, 2, · · · , p





j básico




λij ≥ 0, i = 1, 2, · · · , p j = 1, 2, · · · , r





λ∗i ≥ 0, i = 1, 2, · · · , p
(1.60)
(1.61)
(1.62)
(1.63)
(1.64)
Região Xi ilimitada
Para um conjunto Xi = {xi |Bi xi = bi ; xi ≥ 0} ilimitado o algoritmo de decomposição
de Dantzig-Wolfe deve ser modificado. Neste caso, os pontos de Xi serão representados como uma
combinação linear convexa dos pontos extremos de Xi mais uma combinação linear não negativa das
suas direções extremas (ver em Apêndice ). Em outras palavras, ∀xi ∈ Xi temos,
15
r
X
λij xji +
l
X
µik dki
(1.65)
λij = 1
(1.66)
λij ≥ 0, j = 1, 2, · · · , r; i = 1, 2, · · · , p
(1.67)
µik ≥ 0, k = 1, 2, · · · , l; i = 1, 2, · · · , p
(1.68)
xi =
j=1
k=1
r
X
j=1
onde x1i , x2i , · · · , xri são pontos extremos de Xi e d1i , d2i , · · · , dli são direções extremas de Xi . O
problema original deverá ser transformado no chamado problema mestre nas variáveis λij e µik como
segue:

p X
p X
r
l
X
X

j


(ci xi )λij +
(ci dki )µik
min




i=1 j=1
i=1 k=1












Sujeito a:




p X
p X
r
l

X
 X
j
(Ai xi )λij +
(Ai dki )µik = b0

i=1 j=1
i=1 k=1




r

X



λij = 1; i = 1, 2, · · · , p




j=1






λij ≥ 0, j = 1, 2, · · · , r; i = 1, 2, · · · , p






µik ≥ 0, k = 1, 2, · · · , l; i = 1, 2, · · · , p.
(1.69)
(1.70)
(1.71)
(1.72)
(1.73)
Para resolver este problema (1.69)-(1.73) optamos por utilizar o método simplex revisado visto
que o número de variáveis poderá ser muito grande dependendo da quantidade de pontos extremos
e direções extremas. A fim de iniciarmos tal método, devemos ter uma solução básica factı́vel com
a sua matriz base correspondente, B, as variáveis duais π1 correspondentes à restrição (1.70) e π0i
−1
correspondente à restrição (1.71). Lembremos

 que π = (π1 , π01 , · · · , π0i , · · · , π0p ) = fB B , fB é o
b0
, mostrado na Tabela 1.1.
custo das variáveis básicas e b̄ = B −1 
1
(π1 , π01 , · · · , π0i , · · · , π0p )
fB b̄
B −1
b̄
Tabela 1.1: Tabela do Método Simplex Revisado referente ao problema mestre.
Relembremos que a solução é ótima para o problema original se os custos relativos das
variáveis do problema mestre são todos não negativos, f¯ij ≥ 0 e f¯ik ≥ 0. Em particular, as condições
16
de otimalidade devem satisfazer às seguintes condições:

(i) λij não básica ⇒ 0 ≤ f¯ij
= ci xji − π 

(ii) µik não básica ⇒ 0 ≤ f¯ik = ci dki − π 
Ai xji
1
Ai dki
0

 = (ci − π1 Ai )xj − π0i
i
(1.74)

 = (ci − π1 Ai )dki
(1.75)
Devido ao elevado número de variáveis não-básicas, verificar as condições de otimalidade
(1.74) - (1.75) é computacionalmente inviável. Portanto devemos determinar se as condições são
válidas ou não resolvendo os subproblemas. Determinamos inicialmente o conjunto solução e o valor
objetivo minimal zi0 , de cada subproblema i (1.31) - (1.33) e, em seguida, aplicamos o critério usual
do método simplex (1.58)
Suponhamos primeiramente que o valor da solução ótima do subproblema é ilimitada. Isto é
possı́vel se somente se, uma direção extrema dks é encontrada tal que (cs − π1 As )dks < 0. Isto significa
que a condição
(1.75) foi violada. Portanto, a variável µsk é eleita a entrar na base. Neste caso,


A dk
 s s  é atualizada pré-multiplicando-a por B −1 e a coluna resultante é inserida na Tabela 1.1.
0
Assim, o método simplex revisado continua com uma próxima iteração.
Consideremos agora a solução ótima limitada. Neste caso, (ci − π1 Ai )dki ≥ 0 ocorre para
todas as direções extremas, então a condição necessária e suficiente (1.75) para que a solução seja
limitada, é válida. Por outro lado observemos também a validade da equação (1.74). Sejam xjs um
ponto extremo ótimo e f¯sj o objetivo ótimo para o subproblema s (1.31)-(1.33). Se f¯sj ≥ 0, a condição
(1.74) é válida para o subproblema s, ou seja, pela otimalidade de xjs , para cada ponto extremo xji ,
temos
f¯ij = (ci − π1 Ai )xji − π0i ≥ (cs − π1 As )xjs − π0s = f¯sj
(1.76)
e portanto, temos uma solução ótima do problema original.
Caso contrário, se f¯sj < 0 então λsj é eleita a entrar na base. Isto é feito inserindo a coluna


j


As xs


f¯sj

−1

 na Tabela 1.1, onde ysj = B  − − − − − 
 onde us é um vetor p-componente com um


ysj
us
na posição s e zeros nas outras. é importante salientar que se o problema mestre apresentar outras
variáveis explı́citas incluindo as variáveis de folga, então deveremos verificar os custos reduzidos destas
variáveis antes de deduzirmos a otimalidade.
17
Em resumo, cada subproblema i é resolvido separadamente. Se o subproblema s produz uma
solução ilimitada, então uma direção extrema dks encontrada, é candidata a entrar na base do problema
mestre. Se o subproblema s produz um ponto ótimo limitado e f¯sj < 0, então a variável associada
ao ponto extremo é candidato a entrar na base mestre. Se nenhuma dessas condições ocorre, então
não existem candidatas a entrar na base do problema mestre, ou seja, temos o ótimo. Caso contrário,
podemos aplicar a regra do f¯sj mais negativo dentre as variáveis candidatas a entrar na base mestre.
Selecionando a candidata, atualizamos a coluna correspondente, fazemos os devidos pivoteamentos na
tabela mestre e repetimos o processo com as outras candidatas.
1.6
Relembrando o Algoritmo de Dantzig-Wolfe(Seção 1.1) vimos que para satisfazermos o seu
critério de parada tı́nhamos que efetuar muitos cálculos nas iterações. Este fato nos levaria a consumir
muito tempo computacional quando o problema fosse de grande porte.
Por esta razão, desenvolveremos um limite inferior para o valor objetivo da solução factı́vel do
problema original, e portanto, um limite inferior do objetivo ótimo. Por outro lado, como o algoritmo
de Dantzig-Wolfe gera pontos factı́veis que não pioram o valor objetivo pelo problema mestre, nós
temos uma seqüencia de limites superiores não crescente. Então, devemos parar quando a diferença
entre o objetivo do ponto factı́vel corrente e o limite inferior estiver dentro de uma tolerância aceitável.
Isto não deverá fornecer o ponto ótimo verdadeiro, mas garantirá boas soluções factı́veis dentro de
qualquer precisão desejável ao ótimo.
Considere o problema mestre (1.47)-(1.53), reescrito abaixo;

p X
r
X



min z =
fij λij




i=1 j=1












Sujeito a:



p X

r

X
pij λij = b0


i=1
j=1



r

X



λij = 1, i = 1, 2, · · · , p,




j=1







λij ≥ 0




(1.77)
(1.78)
(1.79)
(1.80)
(1.81)
18
onde
(1.82)
= ci xji
fij
= Ai xji
pij
(1.83)
Multiplicando (1.78) pelos multiplicadores simplex π1 e (1.79) pelos multiplicadores π0i ,somando
e subtraindo da equação (1.77), produzimos
z − π1 b0 −
X
π0i =
XX
i
i
λij (fij − π1 pij − π0i )
(1.84)
j
O valor da expressão (fij − π1 pij − π0i ) na equação (1.84) é o custo relativo para λij , f¯ij .
Resolvendo os subproblemas (1.55)- (1.57), calculamos min f¯ij para cada i. Como λij é não negativo,
j
f¯ij , poderá ser substituı́do por este valor minimal e portanto a equação (1.84) pode ser vista como a
desigualdade (1.85) abaixo:
z − π1 b0 −
z − π1 b0 −
X
π0i ≥
XX
i
i
X
X
π0i ≥
i
i
λij min f¯ij
j
j
(min f¯ij )
j
X
λij
(1.85)
(1.86)
j
Substituindo (1.79) a desigualdade (1.86) torna-se:
z ≥
X
(min f¯ij ) + π1 b0 +
j
i
X
π0i
(1.87)
i
Sabendo que (1.87) é válida para todos os valores de z obtido do problema mestre (1.77)(1.83), então valerá para o valor mı́nimo. Assim,
min z ≥
X
i
(min f¯ij ) + π1 b0 + π0 ep
j
(1.88)
onde ep é o vetor p-dimensional com componentes iguais ao valor um. A expressão (1.88) poderá ser
escrito na forma mais compacta fazendo,




b0
b
0
 = cB B −1 
 = cB xB = zB
(π1 , π0 ) 
ep
ep
(1.89)
onde zB é o valor de z associado á base corrente, B. Portanto (1.88) torna-se:
min z ≥ zB +
p
X
i=1
definindo assim o limite inferior.
(min fij )
j
(1.90)
1.7
19
Considere um nı́vel central e um subnı́vel de uma organização descentralizada. O nı́vel
p
X
central opera em um primeiro conjunto de restrições
Ai xi = b0 , e o subnı́vel no segundo conjunto
i=1
de restrições Bi xi = bi , i = 1, 2, · · · , p. Temos que b0 e bi deverá ser interpretado como recursos para o
nı́vel central e subnı́vel, respectivamente. Durante o curso do algoritmo, informações são comunicadas
de um nı́vel para o outro. O nı́vel central resolve o Problema mestre e como resultado, valores marginais
π ou recursos centrais, são comunicados para os subnı́veis. O subnı́vel resolve os subproblemas nos
quais a função objetivo incorpora os custos para utilização dos recursos centrais. O subnı́vel então
sugere atividades xi para incorporar ao nı́vel central. Durante as iterações, nenhuma informação direta
correspondente aos coeficientes nas restrições é comunicada entre o nı́vel central e o subnı́vel. Além
disso, a informação do custo é comunicado do nı́vel central para o subnı́vel.
Na maioria das aplicações, as restrições que não são de acoplamento formam a estrutura diagonal, nas quais as variáveis são agrupadas em blocos independentes. Isto significa que os subproblemas
são separados em vários problemas independentes. Em um contexto econômico, a estrutura bloco
angular reflete a divisão em múltiplos subnı́veis independentes, onde cada um comunica diretamente
com o nı́vel central.
1.8
Exemplo numérico
Para ilustrar o princı́pio da decomposição de Dantzig-Wolfe, consideremos o problema
min −x1 − x2 − 2x3 − x4
(1.91)
Sujeito a:
x1
+
2x2
x1
+
2x1
+
+
2x3
+
x4
≤
40
3x2
≤
30
x2
≤
20
(1.92)
(1.93)
(1.94)
Exemplo
20
x3
x3
xj
+
≥
≤
10
x4
≤
10
x4
≤
15
0
(1.95)
(1.96)
(1.97)
(1.98)
j = 1, · · · , 4
Este problema tem a primeira restrição, (1.92), identificada como de acoplamento e dois
blocos independentes, sendo o primeiro bloco formado pela segunda e terceira restrição (1.93) - (1.94)
e o segundo bloco formado pela quarta, quinta e sexta restrição, (1.95), (1.96) e (1.97) respectivamente,
cujas as regiões factı́veis são mostradas nas Figuras 1.5 e 1.6, respectivamente.
x
x
2
4
20
15
10
(5,10)
10
(10,5)
(6,8)
10
30
x
10
15
1
x
3
Figura 1.6: Região factı́vel do conjunto X2 .
Figura 1.5: Região factı́vel do conjunto X1 .
Além disso, o problema pode ser decomposto em dois problemas menores, incluindo ao prop X
r
X
blema mestre as restrições de convexidade
λij = 1. Seja x1 e x2 soluções factı́veis para os
i=1 j=1
p
X
p X
r
X
i=1
i=1 j=1
blocos 1 e 2, respectivamente, escrevemos x =
xi =
λij xji , onde xji são pontos extremos do
subproblema i. A função objetivo e as restrições de acoplamento são escritas como
z = c1 x1 + c2 x2
A1 x1 + A2 x2 + s = b
h
onde c1 = (−1, −1), c2 = (−2, −1), A1 =
i
h
i
,
A
=
1 2
2 1 ,x1 = (x1 , x2 ),x2 = (x3 , x4 ), b = 40
2
e s = (s1 , s2 ) tal que s ≥ 0. O problema mestre é transformado em
min z =
X
j
(c1 xj1 )λ1j +
X
j
(c2 xj2 )λ2j
(1.99)
Exemplo
21
Sujeito a:
2 X
X
(Ai xji )λij + s = b
i=1
(1.100)
j
2 X
X
λij = 1
(1.101)
λij ≥ 0, i = 1, 2
(1.102)
i=1
j
Escolhendo x11 = x12 = (0, 0) e substituindo no problema mestre (1.99)-(1.102), devemos obter
como solução básica inicial
λ11 = λ21 = 1,
s = 40.
Assim, a tabela do simplex revisado é como segue:
Variável básica
Colunas do problema mestre
s
s
λ11
λ11
λ12
−z
1
Constantes
40
1
λ12
1
1
1
−z
1
0
Tabela 1.2: Tabela inicial do simplex revisado do problema mestre.
ITERAÇÃO 1
Os multiplicadores do simplex (variáveis duais) para o problema mestre estão contidos no
topo da Tabela 1.2, os quais são todos nulos. Logo o primeiro conjunto de subproblemas é
min z1 = −x1 − x2
Sujeito a:
B1 x1 ≤ b1
onde

B1 = 

1 3
2 1

Exemplo
22
e
min z2 = −2x3 + x4
Sujeito a:
B2 x2 ≤ b2
onde


1 0




B2 =  0 1 


1 1
com soluções ótimas:
x21 = (6, 8) z10 = −14,
x22 = (10, 5) z20 = −25.
Os custos mı́nimos relativos são:
min fˆx1 = z10 − π01 = −14 ≤ 0,
min fˆx2 = z20 − π02 = −25 ≤ 0.
Assim, temos associado a cada solução dos subproblemas uma coluna do problema mestre.
As colunas correspondentes à solução corrente são:

c1 x21


 A1 x21


 1

0



−14
 
 
  22
=
 
  1
 
0








c2 x22


 A2 x22
e 

 0

1



−25
 
 
  25
=
 
  0
 
1







O problema mestre restrito decorrente do problema mestre corrente mais as novas colunas é
como segue;
min −14λ21 − 25λ22
(1.103)
Sujeito a:
22λ21 + 25λ22 + s = 40
λ11
λ21
+
λ12 +
+
λ22
=
1
=
1
(1.104)
com todas variáveis não negativas. O problema (1.103)-(1.104) é resolvido pelo Método Simplex
Revisado produzindo as Tabelas 1.3, 1.4 e 1.5 abaixo:
Exemplo
23
Variável básica
s
s
λ11
λ12
−z
Constantes
λ22
40
25
1
0
1
1
0
-25
1
λ11
1
λ12
1
−z
Coluna de entrada
1
Tabela 1.3: Entra na base a variável λ22 , sai λ12 .
Variável básica
s
s
λ11
1
λ11
λ12
−z
Constantes
λ21
15
22
1
1
1
1
25
-14
-25
1
λ22
1
−z
25
Coluna de entrada
1
Tabela 1.4: Entra na base a variável λ21 , sai s.
Variável básica
s
λ21
1
22
λ11
1
− 22
λ11
1
λ22
−z
14
22
λ12
−z
Constantes
25
− 22
15
22
25
22
7
22
1
1
200
22
1
6
34 11
Tabela 1.5: Solução ótima do exemplo 1.
a nova solução para o problema original é:
x1 = λ11 x11 + λ21 x21 =
7
15
(0, 0) +
(6, 8)
22
22
x2 = λ22 x22 = (10, 5)
368
.
z = −
11
ITERAÇÃO 2
Novos multiplicadores simplex são encontrados na Tabela 1.5
µ
¶
14
200
(π, π01 , π02 ) = − , 0, −
.
22
22
(1.105)
(1.106)
(1.107)
Exemplo
24
Esses são usados para formar novos custos para os subproblemas
14
8
6
(1, 2)]x1 = − x1 + x2
22
22
22
14
16
8
z2 = (c2 − πA2 )x2 = [(−2, −1) + (2, 1)]x2 = − x3 + − x4
22
22
22
z1 = (c1 − πA1 )x1 = [(−1, −1) +
(1.108)
(1.109)
Minimizando z1 e z2 sobre o conjunto de restrições dos subsistemas obtemos a solução ótima:
x31 = (10, 0)
80
z10 = −
22
(1.110)
x22 = (10, 5)
200
z20 = −
22
(1.112)
(1.111)
(1.113)
O novo problema mestre restrito ficará da forma
min −14λ21 − 25λ22 − 10λ31 − 25λ32
(1.114)
Sujeito a:
22λ21 + 25λ22 + 10λ31 + 25λ32 = 40
λ11
λ21
+
+
λ31
λ22
+
λ32
=
1
=
1
(1.115)
A solução ótima para o problema restrito é uma solução básica factı́vel para este problema,
com base inversa dada no final da Tabela 1.5 da Iteração 1. A solução do problema (1.114) - (1.115)
é apresentado nas Tabelas1.6 e 1.7.
Variável básica
s
λ21
1
22
λ11
1
− 22
λ11
1
λ12
Constantes
λ31
25
− 22
15
22
10
22
25
22
7
22
12
22
1
1
0
1
6
34 11
− 80
22
λ22
−z
14
22
Coluna de entrada
200
22
−z
Tabela 1.6: Entra λ31 e sai λ11 .
Exemplo
25
Variável básica
s
λ11
λ12
λ21
1
12
− 10
12
− 25
12
5
12
λ31
1
− 12
22
12
25
12
7
12
1
1
λ22
−z
4
12
80
12
−z
200
12
Constantes
− 110
3
1
Tabela 1.7: Solução ótima do exemplo 2.
A solução factı́vel corrente para o problema original (1.91)-(1.98) é
¶
µ
5
7
25 10
2 2
3 3
x1 = λ1 x1 + λ1 x1 = (6, 8) + (10, 0) =
,
12
12
3 3
x2 = λ22 x22 = (10, 5)
110
z = −
.
3
(1.116)
(1.117)
(1.118)
ITERAÇÃO 3
Os novos multiplicadores do simplex (ver Tabela 1.7) e as funções objetivos dos subproblemas
são
µ
(π, π01 , π02 ) = −
4 80 200
, ,
12 12 12
¶
(1.119)
z1 = (c1 − πA1 )x1 = [(−1, −1) +
4
12 (1, 2)]x1
= − 23 x1 + − 31 x2
z2 = (c2 − πA2 )x2 = [(−2, −1) +
14
22 (2, 1)]x2
= − 43 x3 + − 32 x4
A solução ótima dos subproblemas é
x41 = (6, 8)
(1.120)
ou
x51 = (10, 0)
20
z10 = −
3
(1.121)
x42 = (10, 5);
50
z20 = −
3
(1.123)
min fˆx1 = z10 − π01 = 0
(1.125)
min fˆx2 = z20 − π02 = 0
(1.126)
80
12
(1.127)
min ĉs = −π01 =
(1.122)
(1.124)
Exemplo
26
Visto que o valor de (1.125), (1.126) e (1.127) são não negativos, a solução corrente do problema
mestre é ótima, e a solução ótima do problema original conforme (1.116) - (1.118), é dada por:
25 10
, )
3 3
x2 = (x3 , x4 ) = (10, 5)
110
z = −
.
3
x1 = (x1 , x2 ) = (
(1.128)
(1.129)
(1.130)
Capı́tulo 2
Os Problemas de Job-Shop
Os problemas de seqüenciamento do tipo job-shop são problemas combinatórios classificados
NP-difı́cil[16]. Este problema de job-shop tem como dados: tarefas, restrições de potencialidade,
recursos e função econômica.
As tarefas podem ser ligadas por restrições de potencialidade . Estas englobam: (i) as restrições de sucessão , as quais significam, uma tarefa deve ser executada posteriormente a uma outra tarefa;
(ii) as restrições de localização no tempo , as quais significam,uma tarefa deve ser concluı́da em uma
determinada data ou sua execução não deve começar antes e nem finalizar após uma determinada data.
Estas tarefas requerem certos recursos para a sua exe cução. Estes recursos, por sua vez, introduzem
restrições disjuntivas no problema. Uma restrição disjuntiva aparecerá quando duas tarefas, utilizando
um mesmo recurso, não puderem ser executadas simultaneamente. Enfim, deve-se programar as tarefas
de forma a otimizar um determinado critério que será a minimização de uma determinada função
econômica.
De um ponto de vista industrial, num problema de fábrica, as tarefas (chamadas operações
elementares) são reagrupadas em entidades chamadas trabalhos (ou jobs). Um problema de fábrica,
em geral, contém um conjunto de máquinas distintas e cada trabalho é um conjunto de operações
elementares, onde cada uma delas deve ser executada numa máquina diferente.
Podemos distinguir três tipos de problemas de fábrica , segundo a natureza das restrições de
precedência entre as operações de um mesmo trabalho[3]: (1) se as operações são independentes, tratase de um problema de open-shop ; (2) se as operações são ligadas por uma ordem, não necessariamente
idêntica para todos os trabalhos, trata-se de um problema de job-shop ; (3) se as operações são ligadas
Os problemas de fábrica
28
por uma mesma ordem para todos os trabalhos, trata-se de um problema de flow-shop .
Em particular, trataremos o problema de job-shop cujas caracterı́sticas serão mostradas nas seções
seguintes.
2.1
Os problemas de fábrica
Nos problemas de fábrica, as tarefas são as operações elementares relativas à fabricação de um
produto; elas necessitam para sua realização de um recurso principal chamado máquina. A fabricação
de um produto é sempre denominado trabalho(job). Geralmente, as operações de um mesmo trabalho
são organizadas em uma seqüência denominadas gama operatória , enquanto que as operações de
trabalhos diferentes são independentes.
Consideramos o caso no qual uma fábrica contém m máquinas distintas e n produtos. Cada
n
X
produto Pi é um conjunto de ni operações elementares. Assim, existem n0 =
ni operações na
i=1
fábrica, cada uma delas tendo que ser executada, numa máquina diferente: a utilização de uma
máquina k por uma operação j é denotada Mk (Oj ) = Mk ; Nós utilizamos as seguintes notações:
• P = o conjunto de n produtos (trabalhos) Pi .
• M = o conjunto de m máquinas Mk .
• O = o conjunto de todas as operações(tarefas) Oj .
0
• O = O ∪ {O0 , Of im } = o conjunto de todas as operações (tarefas), incluindo as operações
fictı́cias,O0 e Of im , que não são executadas em máquinas e não aparecem nos produtos. Estas
operações devem ser executadas respectivamente, antes e após todas as operações Oj ∈ O. O
0
conjunto O contém n0 operações enquanto que O contém (n0 + 2) operações.
2.1.1
Os produtos e os critérios
Os produtos podem chegar na fábrica numa mesma data ou de forma seqüenciada. Esta-
mos falando respectivamente dos problemas estáticos e dinâmicos. Quando as datas de chegada dos
produtos são conhecidas de forma determinada podemos impor ao produto Pi ,
• uma “data mais cedo (ri )” que representa o instante mais cedo de inı́cio de sua execução;
O problema de Job-Shop
29
• uma “data mais tarde (di )” que representa o instante limite de fim de sua execução.
A data de fim de execução para cada produto i é comumente denotada por
Ci = max {Cj },
1≤j≤ni
onde Cj representa a data de fim de execução da operação j na gama operatória do produto i.
2.1.2
As máquinas
As máquinas são recursos disjuntivos e assim, a execução das operações que utilizam a mesma
máquina deve ser planejada de tal sorte que as máquinas tenham uma operação por vez para tratar. O
seqüenciamento dos problemas de fábrica resulta freqüentemente na procura de seqüencias de operações
sobre as máquinas.
Consideramos o caso onde uma operação só pode ser executada numa única máquina (fábricas
com máquinas especializadas ), e os casos particulares onde todas as operações são executadas numa
única máquina existente na fábrica (fábricas com uma única máquina).
Nas fábricas com máquinas especializadas, podemos distinguir três tipos de problemas de
fábrica segundo a natureza das restrições de precedência entre as operações elementares de um mesmo
trabalho denominados[31]: (1) open-shop,(2) job-shop e (3) flow-shop.
O caso particular onde uma só máquina existe na fábrica problemas com uma máquina foi
muito estudado na literatura [3]; a fabricação de cada produto é então reduzida a uma única operação
denominada simplesmente tarefa.
2.2
O Problema de Job-Shop
Consideremos os problemas de seqüenciamento do tipo job-shop constituı́dos por um conjunto
M de m máquinas, um conjunto P de n produtos, um conjunto O de n0 operações:
M = {Mk |k = 1, . . . , m} ; P = {Pi |i = 1, . . . , n} ; e O = {Oj |j = 1, . . . , n0 }.
A utilização de uma máquina Mk por uma operação Oj é denotado por M (Oj ) = Mk . O
número total de operações executado por uma máquina Mk é denotado por mk . A duração de execução
de Oj em Mk , denominada de tempo operatório, é denotada pj . Durante este tempo, a máquina será
30
ocupada e todas as outras operações sobre a mesma máquina aguardarão a sua vez de processamento.
Dessa forma, toda operação numa máquina terá uma data de inı́cio de execução denotada por tj .
Esta data, calculada para cada operação numa mesma máquina, depende do instante de finalização da
operação precedente. O instante de término para uma operação Oj é denotado Cj , onde Cj = tj + pj .
Uma operação pode ser então caracterizada por seu produto, sua posição na gama operatória,
sua máquina e sua duração de execução. A máquina deve ser ocupada durante um perı́odo de tempo
conhecido a fim de processar a operação.
A seguir apresentamos as principais caracterı́sticas de um produto Pi :
• ni = número de operações.
• Pi = {O1 ; O2 ; . . . ; Oni } = seqüência de operações (gama operatória).
• pi =
ni
X
pj = duração total de fabricação de Pi .
j=1
• ri = instante mais cedo de lançamento para toda operação de Pi .
• di = instante mais tarde do fim de execução para todas as operações de Pi .
• Ci = instante para finalizar o processamento completo de Pi , onde Ci = max {Cj }.
1≤j≤ni
Nos limitamos aos problemas de job-shop estáticos e determinı́sticos com máquinas especializadas. Dizemos que um problema é estático quando todos os seus dados são conhecidos a priori, e
determinı́stico quando os tempos associados a cada operação são perfeitamente determinados. Dizemos
que o problema é com máquinas especializadas quando possui uma lista de operações, para cada
produto, e uma ordem de passagem nas máquinas, imposta inicialmente.
As restrições do problema de job-shop estão relacionadas às possibilidades de utilização das
máquinas e às ligações que podem existir entre as operações. As restrições que nós adotamos são as
seguintes:
• referentes às máquinas
– As máquinas são independentes umas das outras, e estão disponı́veis durante todo o perı́odo
do seqüenciamento.
– Uma máquina não pode executar mais de uma operação em um determinado instante. A
superposição de operações em uma mesma máquina é proibida.
31
– Não pode existir a preempção, isto é, uma operação em execução não pode ser interrompida
pois todas possuem a mesma prioridade.
• referentes aos produtos
– Os produtos são independentes entre si e não existe uma ordem de prioridade entre eles.
– Um produto deve passar por uma única máquina a cada vez, ou seja, cada operação de sua
gama operatória deve passar por uma máquina diferente.
– Na gama operatória de um produto, cada operação deve respeitar uma ordem de execução:
a operação Oj+1 não pode ser iniciada antes do término de Oj .
A fim de tornar mais compreensiva todas as definições vistas, apresentamos um exemplo de um problema de job-shop cujos dados são mostrados na Tabela 2.1. O critério de otimização deste problema é a
n=4
m=3
n1 = n2 = n3 = 3
m1 = m2 = m3 = 4
produto
operação
duração
máquina
1
1
3
2
1
2
3
3
1
3
1
1
2
4
3
3
2
5
2
2
2
6
3
1
3
7
1
2
3
8
4
1
3
9
4
3
4
10
4
1
4
11
3
2
4
12
2
3
Tabela 2.1: Dados do problema-exemplo de job-shop.
minimização do tempo total de seqüenciamento (makespan): min {max Ci }. Devemos então determinar
i
a seqüência das operações em cada máquina, de tal sorte que ela seja a menor possı́vel respeitando
todas as restrições do problema.
Podemos também representar este problema de job-shop utilizando grafo potencial-tarefas
G = (X , C ∪ D) onde X é o conjunto de nós do grafo associado a cada operação de um determinado
produto, C representa o conjunto relativo aos arcos associados às restrições de precedência e D representa o conjunto dos arcos associados às restrições disjuntivas[31]. Desta forma, o problema acima,
ficará ilustrado pelo grafo G como mostra a Figura 2.1.
Na Figura 2.1, mostramos o grafo com o conjunto de arcos conjuntivos C representados pelas
flechas contı́nuas e o conjunto dos arcos disjuntivos D representados pelas flechas pontilhadas. Estes
32
3
3
1
O1
O2
O3
3
2
3
O4
O5
O6
0
0
O0
1
4
4
O7
O8
O9
3
4
2
O11
O10
MAQUINA
´
1
´
MAQUINA
2
Ofin
O12
´
MAQUINA
3
Figura 2.1: Grafo potencial-tarefa representando o exemplo do job-shop.
arcos disjuntivos representam as máquinas. Cada operação é representada por um nó. Os arcos que
partem de cada nó são ponderados pela duração da operação correspondente. Os arcos que estão à
origem do nó O0 são ponderados pelo instante do lançamento da primeira operação de cada produto.
Os arcos que chegam ao nó Of im são ponderados pelo instante do término da última operação de cada
produto. Neste exemplo, todos os produtos são lançados inicialmente ao instante 0[31].
Para representar a solução deste problema de job-shop utilizamos o diagrama de Gantt, que
nos permite visualizar um seqüenciamento representando a ocupação das máquinas pelas operações
em função do tempo[31]. Apresentamos, na Figura 2.2, duas soluções possı́veis para este problema
num diagrama de Gantt. Observamos que todas as restrições do problema são respeitadas; não existe
superposição entre as operações. Notemos que a solução S1 forneceu um comprimento do seqüenciamento maior que a solução S2 : Cmax1 À Cmax2 . Isto foi devido ao fato que, em S1 , encontramos muito
mais tempo morto1 nas máquinas que em S2 . Estes tempos mortos são representados pelos espaços
vazios de uma faixa antes do inı́cio da execução de alguma operação numa mesma máquina.
M1
P1
P2
M2
P3
M3
P4
0
~ S :
Solucao
1
´
C
= 33
max1
33
tempo
M1
P1
P2
M2
P3
P4
M3
0
13
~ S :
Solucao
2
´
tempo
C
= 13
max2
Figura 2.2: Diagrama de Gantt representando duas soluções para o exemplo do job-shop.
Na Figura 2.3, mostramos a solução S2 para o job-shop representada por um grafo conjuntivo.
1
Tempo morto de uma máquina é o tempo que esta fica ociosa aguardando alguma operação para execução.
33
3
3
1
O1
O2
O3
3
2
3
O4
O5
O6
1
4
4
O7
O8
O9
0
0
O0
3
4
2
O11
O10
MAQUINA
1
´
Ofin
O12
MAQUINA
´
2
MAQUINA
´
3
Figura 2.3: Grafo conjuntivo da solução S2 para o exemplo do job-shop.
2.2.1
Formulação Matemática
Existem diversas propostas de formulações para problemas de seqüenciamento do tipo job-
shop[31]. No entanto, utilizaremos o modelo matemático proposto por A.S.Manne[29]. A formulação
em números inteiros proposta por Manne define uma nova variável para cada par ordenado de operações
utilizando a mesma máquina. Esta variável em 0-1 se escreve yuv , tal que:

 1,
se Ov precede Ou sobre Mk
yuv =
 0,
se O precede O sobre M .
u
v
k
Este modelo supõe também o conhecimento de uma borda superior BS da duração total
do seqüenciamento. Esta borda pode ser a soma de todos os tempos operatórios das operações do
problema:
BS =
n0
X
pj .
(2.1)
j=1;j∈O
sendo assim, as restrições do problema de job-shop podem ser expressas pelas equações:
h
∀(j, j + 1) ∈ C
(2.2)
≥ tu + pu − BS(yuv ),
∀(u, v) ∈ D
(2.3)
tu ≥ tv + pv − BS(1 − yuv ),
∀(v, u) ∈ D
(2.4)
tj+1 ≥ tj + pj ,
h
tv
h
As restrições (2.2) representam as restrições de precedência ( restrições de produto) , por
isso elas incluem todos os arcos conjuntivos pertencentes ao conjunto C . As restrições (2.3) e (2.4)
representam as restrições disjuntivas restrições de máquina(restrições de capacidade das máquinas),
ou seja, ela representa todos os pares de arcos disjuntivos pertencentes ao conjunto D. Lembremos que
os conjuntos C e D constituem o grafo potencial tarefa G visto na Seção 2.2. Neste modelo, para cada
par de restrições disjuntivas, apenas uma delas é ativada. Assim, quando arbitramos Ou antes de Ov ,
34
yuv vale 0. Conseqüentemente a restrição (2.4) é desativada já que tu ≥ tv + pv − BS, pois da forma
que BS foi definido (2.1), faria com que a operação tu tivesse um tempo de inı́cio elevado, ou mais
especificamente, ele seria igual ou maior que BS menos a duração da operação v. Matematicamente
terı́amos:
tu ≥ tv + p v −
n0
X
pj ,
(2.5)
j=1
tornando assim a equação (2.5) inviável, pois o tempo de inı́cio da operação v teria que aumentar
bastante não oferecendo assim uma minimização no tempo total de produção. Enquanto que a restrição
(2.3) é ativada já que torna-se
tv
≥ tu + p u .
Consideremos como objetivo,
min
X
(2.6)
tj
j
onde tj determina o tempo de inı́cio da operação j.
2.2.2
Métodos de Resolução
Os algoritmos de resolução para os problemas de seqüenciamento do tipo job-shop são basea-
dos em métodos clássicos da otimização combinatória métodos exatos que buscam a solução ótima, ou
são simplesmente algoritmos aproximados (heurı́sticos) que não garantem a otimalidade da solução,
mas permitem o tratamento dos problemas de grande porte em um tempo razoável.
O objetivo dos métodos exatos é encontrar, em um tempo de cálculo menor possı́vel, a
solução ótima do problema. Para os problemas de job-shop, isto é um desafio devido à sua natureza
combinatória que o classifica como um problema NP-difı́cil[16]. Dentre os métodos de resolução exata
mais eficientes para os problemas de job-shop, temos o método de separação e avaliação(Branch and
Bound)[9].
O princı́pio de um método heurı́stico é encontrar, em um tempo polinomial, a melhor possı́vel
solução viável[i.e., sub-ótimo para o job-shop [7].
Os mais utilizados são os métodos heurı́sticos seriais que utilizam os algoritmos de lista para construir,
de modo progressivo, os seqüenciamentos sem atraso no processamento nas máquinas. Estes tipos de
seqüenciamentos são tais que uma máquina não pode estar parada enquanto existir, no mı́nimo, uma
operação para ser processada. Da literatura [7], podemos citar os algoritmos de lista mais conhecidos:
regra EDD (Earliest Dead Date), regra SPT (Shortest Processing Time) e regra FIFO (First in First
35
Out).
Atualmente, existem numerosos algoritmos heurı́sticos para resolver o job-shop: (1) as heurı́sticas
construtivas [1][11][30] são baseadas sobre as operações ou sobre as máquinas, sendo que as soluções
obtidas estão muito distantes do valor ótimo; (2) as heurı́sticas melhoradas que quando aplicadas
aos problemas de grande dimensão, tornam-se muito lenta e menos eficazes. As mais conhecidas são
os métodos tabu [20][21][34][11][22], os recursos simulados[23][32] e os algoritmos genéticos[8][12]; (3)
redes neurais e inteligência artificial. Estas técnicas são cada vez mais utilizadas pelos especialistas da
área de pesquisa operacional que tratam os problemas de seqüenciamento do tipo job-shop[6][24][26].
Podemos ainda citar os métodos de decomposição, os quais buscam encontrar a solução do
problema original através da resolução dos seus subproblemas. Conhecidos da literatura, temos os
métodos clássicos de decomposição e os métodos de decomposição espacial. Os métodos clássicos de
decomposição em programação matemática para resolver os problemas combinatórios possuem como
base o princı́pio da relaxação lagrangeana[27],[17].
Aplicado aos problemas de job-shop, destacamos os trabalhos de Fisher, M.L.[13][14][15].
Fisher, em um primeiro tempo, utilizou os multiplicadores de Lagrange para dualizar as restrições de
recursos (máquinas) formando o problema de Lagrange no qual as restrições de produtos aparecem
explicitamente, enquanto que as de máquinas estão presentes apenas na função de Lagrange. Conseqüentemente, os subproblemas eram constituı́dos pelas restrições de produtos, e o problema mestre
era encarregado de verificar a factibilidade das restrições de máquinas determinando assim os multiplicadores de Lagrange. Mais tarde, Fisher [15] propôs uma metodologia que efetua um tipo de relaxação
lagrangeana (surrogate duality relaxation). Isto significa que a relaxação era obtida substituindo certas
restrições do problema por uma combinação linear ponderada destas mesmas restrições. Vale observar
que a diferença em relação à clássica relaxação lagrangeana reside no fato que as restrições agregadas e
ponderadas não são eliminadas e adicionadas à função objetivo. Em suma, o interesse nesta metodologia é mais teórico que prático já que as bordas obtidas são melhores que aquelas obtidas pela relaxação
lagrangeana clássica.
Os métodos de decomposição espacial são aplicados aos problemas de job-shop com várias
máquinas e consistem em formar sub-problemas de job-shop reagrupando máquinas e produtos. Em
geral, os produtos são agrupados em famı́lias e as máquinas em células de fabricação de tal sorte que os
produtos de uma mesma famı́lia sejam fabricados essencialmente, por máquinas de uma célula principal
e utilizam de forma excepcional as máquinas de outras células. As operações dos produtos que são
executadas por máquinas que não fazem parte da célula principal são denominadas elementos residuais
ou excepcionais. Sendo assim, apesar do job-shop ter sido decomposto, os subproblemas continuam
36
interligados pelos elementos residuais. Esta filosofia de decomposição aparece sob os conceitos da
tecnologia de grupos[24][25].
Mais recentemente, surgiu a metodologia de Alves, I. [2] que propõe a resolução do problema
de job-shop utilizando a decomposição espacial junto à decomposição clássica. Neste procedimento,
utiliza-se a tecnologia de grupos a fim de particionar o problema de job-shop e, em seguida, a técnica da
relaxação lagrangeana é utilizada para resolver os subproblemas coordenados por um problema mestre.
O problema mestre é formado pelas restrições de acoplamento resultantes dos elementos residuais.
Desta forma, as restrições contendo os elementos excepcionais não são desprezadas do problema. Elas
são enviadas a um nı́vel coordenador enquanto que as demais restrições formam os subproblemas. Ou
seja, cada famı́lia de produto correspondente à sua célula principal constitui um subproblema que
será resolvido independente dos outros. Utilizando a técnica clássica de decomposição da relaxação
lagrangeana acoplada à tecnologia de grupos, podemos observar que os subproblemas resultantes
conservam um número maior de restrições, isto é, eles se aproximam mais do problema original pois
as restrições de produtos (ou de máquinas) relaxadas são apenas aquelas que contém os elementos
residuais. Isto garante de forma mais eficiente, a factibilidade das soluções locais dos subproblemas. A
fim de tornar a convergência mais rápida desta metodologia, Ramos, A. [31] propôs o ajuste de alguns
parâmetros do método do subgradiente quando utilizado para resolver o problema mestre.
No capı́tulo seguinte apresentaremos o método de decomposição de Dantzig-Wolfe aplicado
ao problema de job-shop.
Capı́tulo 3
Método de Dantzig-Wolfe e o
Problema de Job-Shop
Os capı́tulos anteriores descrevem o método de decomposição de Dantzig-Wolfe e o problema
de seqüenciamento do tipo Job-Shop. Neste capı́tulo, utilizaremos o método de Dantzig-Wolfe como
descrito no Capı́tulo 1 para resolver um particular problema de job-shop conforme Capı́tulo 2. Assumiremos como restrições de acoplamento as restrições de precedência e associado a cada máquina
Mk um subproblema k. Contudo, acontece a ausência de limites inferiores e/ou superiores de algumas
variáveis quando tratamos as restrições de precedência como acoplamento. Desta forma, adotaremos
novos limites de modo a compensar tal perda. A fim de verificar a aplicabilidade do método de
Dantzig-Wolfe ao job-shop, apresentamos alguns exemplos numéricos e as respectivas análises. Além
disso, abordamos de que forma tratamos um problema de job-shop sem introduzir estes novos limites,
ou seja, no caso do conjunto de soluções ser ilimitados.
3.1
3.1.1
Decomposição do Job-Shop
Modelagem Matemática
Relembremos, do Capı́tulo 2, que o modelo matemático adotado para o problema de job-shop
tem como base o modelo de A.S. Manne [29], descrito da seguinte forma:
min
n0
X
j=1
tj
(3.1)
38
Sujeito a:
(3.2)
tj+1 ≥ tj + pj ,
tv
∀(j, j + 1) ∈ C
≥ tu + pu − BS(yuv ),
tu ≥ tv + pv − BS(1 − yuv ),
BS =
yuv

 1,
=
 0,
n
X
∀(u, v) ∈ D
(3.3)
∀(v, u) ∈ D
pj
(3.4)
j=1
se Ov precede Ou sobre Mk
(3.5)
se Ou precede Ov sobre Mk .
As restrições (3.2) representam as restrições de precedência (restrições de produto), as restrições (3.3) - (3.5) representam as restrições de capacidade (restrições de máquina), e a variável tj
determina o tempo de inı́cio da execução da operação j.
3.1.2
Método de Dantizg-Wolfe
Como descrito no Capı́tulo 1, o método de decomposição de Dantzig-Wolfe consiste de dois
nı́veis de resolução os quais a cada iteração, trocam informações até chegar ao valor ótimo ou fornecer
soluções próximas ao ótimo do problema original. Relembremos o algoritmo da decomposição de
Dantzig-Wolfe.
Consideremos o seguinte Programa
 Linear, p
X



min
z
=
ci xi
(3.6)




i=1








Sujeito a :


p

X
(3.7)



Ai xi = b0




i=1





(3.8)
xi ∈ Xi
onde assumiremos, inicialmente, o conjunto Xi = {xi |Bi xi = bi , xi ≥ 0} limitado e chamaremos
Ei = {x1i , x2i , · · · , xri } o conjunto dos pontos extremos de Xi , i = 1, · · · , p. Assim, podemos escrever
X
λij xji
(3.9)
λij = 1
(3.10)
λij ≥ 0; j = 1, · · · , r.
(3.11)
xi =
j
r
X
j=1
39
Substituindo (3.9)- (3.11) em (3.6)- (3.8), o problema original poderá ser transformado no
problema mestre(PM) na variável λij

p
r X
X



min
z
=
(ci xji )λij




j=1 i=1












Sujeito a :



p

r X

X



(Ai xji )λij = b0





























(3.12)
(3.13)
j=1 i=1
r
X
λij = 1
(3.14)
λij ≥ 0
(3.15)
j=1
i = 1, · · · , p
(3.16)
j = 1, · · · , r
onde
= ci xji
fij
pij
= Ai xji
(3.17)
(3.18)
No problema mestre (3.12) - (3.18) aplicaremos o método simplex revisado[4], onde o critério
usual pede para resolvermos o seguinte subproblema:
zi0 = min (ci − π1 Ai )xi
xi ∈Xi
(3.19)
Analisaremos o critério min (zi0 − π0i ) ≥ 0 (1.58), sendo π1 e π0i as variáveis duais associadas
i
às restrições (3.13) e (3.15) respectivamente e definiremos qual variável entra na base ou se a solução
corrente do problema mestre (3.12)- (3.18) é ótima. Neste caso, a solução ótima do problema original
(3.19) - (3.23) é dada pela expressão:
x0 =
X
λij xji
(3.20)
j
onde os xji ’s são pontos extremos de Xi correspondentes à base referente à λij . Caso contrário, ainda
podemos melhorar a solução do problema mestre, escolhendo a variável associada ao custo f¯is (1.58)
a entrar na base do atual sistema do PM. A seguir apresentaremos de que forma esta metodologia é
aplicada ao problema de job-shop, incluindo as possı́veis modificações que seriam feitas na modelagem.
3.1.3
40
Aplicação do método de Dantzig-Wolfe ao Job-Shop
Consideremos o problema de seqüenciamento do tipo job-shop (3.1) - (3.5) e as restrições de
acoplamento como sendo as restrições de precedência (3.2). Suponhamos, inicialmente, que o problema
foi particionado em k subproblemas independentes onde cada um destes possuem nk tarefas associadas
à máquina Mk . Assim, podemos reescrever o modelo matemático do problema de job-shop da seguinte
maneira:
min
τ k ≥0
p
X
τk
(3.21)
k=1
Sujeito a:
k
[τj+1
≥ τjr + pj
∀(j, j + 1) ∈ C e (k 6= r)
k
[τuk ≥ τvk + pv − BS(yuv
)
k
[τvk ≥ τuk + pu − BS(1 − yuv
)
BS =
k
yuv
n
X
∀(u, v) ∈ Dk ;
Mk ∈ M
∀(u, v) ∈ Dk ;
Mk ∈ M
pj
(3.22)
(3.23)
(3.24)
j=1

 1,
=
 0,
se Ovk precede Ouk sobre Mk
se Ouk precede Ovk sobre Mk
(3.25)
onde τ k = (tk1 , tk2 , · · · , tknk ) e cada componente tki representa o tempo inicial da tarefa i do bloco k.
Uma outra forma de apresentarmos o problema de job-shop (3.21) - (3.25) seguindo a formulação (3.6)-(3.8) seria como segue:































min
τ k ≥0
p
X
τk
(3.26)
k=1
Sujeito a:
p
X
Ak τ k ≥ p0
(3.27)
k=1
τk
∈ Xk ; k = 1, 2, · · · , p
(3.28)
Chamaremos Xk o conjunto dos τ k que satisfazem as restrições (3.23)-(3.25) e seja Ek =
{τ1k , τ2k , · · · , τrk } o conjunto dos pontos extremos de Xk . Ocorre que o conjunto Xk define um conjunto
ilimitado. Observamos que ao tratarmos as restrições de precedência como acoplamento, acontece
a ausência dos limites inferior e superior para as variáveis tki pertencentes a estas restrições. Desta
forma, ao encontrarmos uma solução local para cada subproblema k, provavelmente, essas soluções
não irão satisfazer as restrições de precedência globais(3.2). Por estas razões, devemos inserir limites
41
para estas variáveis, a fim de eliminar a infactibilidade global destas soluções locais, como também
limitar a região factı́vel. Portanto, para k = 1, 2, · · · , p e para Xk limitado, τ k da forma:
τk =
p X
r
X
λij τjk
(3.29)
λkj = 1;
(3.30)
λkj ≥ 0, k = 1, 2, · · · , p j = 1, 2, · · · , r
(3.31)
k=1 j=1
r
X
j=1
Utilizamos, inicialmente, o seguinte padrão para estes limites:
LIki = LSk(i−1)
e
LSki = BS −
n0
X
pl
(3.32)
l=i
onde LIki e LSki são, respectivamente, os limites inferior e superior do tempo de inı́cio da operação
tki . Assim, temos
LIki ≤ tki ≤ LSki .
(3.33)
Pensando no problema de job-shop, podemos relacionar o limite LIki ao rik , representando
assim o instante mais cedo de inı́cio da execução operação Oik e o limite LSki acrescentado as duração
da variável tki , ao dki , representando o instante limite do fim da execução da operação Oik . Logo, temos;
rik ≤ tki ≤ dki
(3.34)
Desta forma, ao aplicarmos o método de Dantzig-Wolfe teremos abaixo o problema mestre
(3.35)- (3.38) e o k-ésimo subproblema (3.41)-(3.43).
Problema Mestre













































min
τ k ≥0
p
r X
X
fkj λkj
(3.35)
j=1 k=1
Sujeito a:
p X
r
X
qkj λkj ≥ p0
k=1 j=1
p X
r
X
(3.36)
λkj = 1
(3.37)
λkj ≥ 0; k = 1, 2, · · · , p; j = 1, 2, · · · , r
(3.38)
k=1 j=1
onde
qkj
= Ak τkj , k = 1, 2, · · · , p; j = 1, 2, · · · , r
fkj
= ck τkj , k = 1, 2, · · · , p; j = 1, 2, · · · , r
(3.39)
(3.40)
Algoritmo de Dantzig-Wolfe aplicado ao Job-Shop
42
p0 - vetor das durações das operações precedentes na gama operatória,
ck - vetor com nk componentes iguais a unidade.
Subproblema k





min (ck − π1 Ak )τ k







Sujeito a:

(3.41)












τ k ∈ Xk
(3.42)
LIki ≤ tki ≤ LSki
(3.43)
Consideremos o nosso problema de job-shop (3.26) - (3.28):

p
X



τk
min




k=1








Sujeito a:


p

X



Ak τ k ≥ p0




k=1





τ k ∈ Xk .
(3.44)
(3.45)
(3.46)
Do problema mestre formulado (3.35)-(3.40), teremos que partir da sua solução básica inicial.
é importante ressaltar que o sistema (3.36) é de desigualdades do tipo ≥, portanto o vetor das variáveis
de folga deve ser inserido no problema mestre e ser representado como s = (s1 , s2 , · · · , si , · · · , sm ),
cujo i-ésimo componente corresponde a i-ésima restrição. Todavia, não é possı́vel determinar uma
solução viável ao acrescentar tais variáveis. Sendo assim, recorremos a algum método para obter
tal solução, como por exemplo no método de Duas Fase ou Big-M (Lasdon[27],Bazaraa[4]). Através
deste procedimento conseguimos obter uma solução básica inicial e conseqüentemente, a matriz básica
correspondente, B, as variáveis duais π1 e π0 .
Neste caso, o algoritmo de Dantzig-Wolfe aplicado ao problema de job-shop, pode ser visto
da seguinte forma:
43
Algoritmo 3.1. Algoritmo de Dantzig-Wolfe aplicado ao job-shop
1. Usando as variáveis duais π1 obtidas do problema mestre, resolvemos cada subproblema k (3.41)-(3.43) obtendo as suas respectivas soluções τ k (π1 ), e o valor ótimo objetivo,
zk0 . Seja τ (π1 ) = (τ 1 (π1 ), · · · , τ p (π1 ))t .
2. Calculemos os valores dos custos relativos das variáveis λ0kj s, f¯kj (1.18), e determinemos:
min min f¯kj = min (zk0 − π0k ) = f¯vj .
k
j
k
onde
zk0 = min (ck − π1 Ak )τ k .
Sujeito a:
τ k ∈ Xk
LIik ≤ tki ≤ LSik
(3.47)
(3.48)
(3.49)
(3.50)
(3.51)
Se
min f¯kj ≥ 0,
(3.52)
k
significa que nós podemos parar, pois não existem mais candidatos a entrar na base. Assim,
a solução ótima para (3.21) - (3.25) é
τ0 =
p
X
k=1
τk =
p X
r
X
λkj τjk ,
(3.53)
k=1 j=1
onde τjk são pontos extremos de Xk correspondentes à variável básica λkj .
3. Se min (zk0 − π0k ) ≤ 0, construı́mos a coluna
k


Av τ v (π1 )


(3.54)
uv
atualizada através da multiplicação pela inversa da antiga base, B −1 , e usando a operação
pivô do método simplex usual, obtemos uma nova base inversa e um novo vetor dos multiplicadores simplex(variáveis duais).
44
4. Utilizamos as soluções corrente dos subproblemas para reajustar os respectivos
limites(3.33), ou seja, estes limites serão ajustados a cada iteração de acordo com a solução
precedente, da seguinte forma:
(iter)
1. LIki
(inter)
2. LSki
(iter−1)
= LSk(i−1) + pi−1
(iter−1)
= LSki
(iter)
− (LIki
(iter−1)
− LIki
(iter−1)
limites da iteração corrente e LIki
(iter)
) onde, LIki
(iter−1)
e LSki
(inter)
e LSki
são os
são limites da iteração anterior.
Retornamos a 1.
3.1.4
Região Xk ilimitada
Como já descrito no Capı́tulo 1 na seção (1.5), para Xk ilimitado, o método de Dantzig-Wolfe
admite alterações em conseqüência de uma nova combinação para seus elementos τk . Esta seção fará
uma abordagem teórica de tais possı́veis alterações para o caso do problema de job-shop.
Seja Xk um conjunto ilimitado dos τ k que satisfazem as restrições (3.23) - (3.25). Neste caso,
∀τ k ∈ Xk serão representados como segue:
p X
r
X
(3.55)
λkj = 1
(3.56)
λkj ≥ 0, j = 1, 2, · · · , r; k = 1, 2, · · · , p
(3.57)
µks ≥ 0, s = 1, 2, · · · , l; k = 1, 2, · · · , p.
(3.58)
=
k=1 j=1
λkj τjk
p X
l
X
µsj dks
τk
+
k=1 s=1
p
r
XX
k=1 j=1
onde τ1k , τ2k , · · · , τrk são pontos extremos de Xk e dk1 , dk2 , · · · , dks são direções extremas de Xk . O
problema original deverá ser transformado no chamado problema mestre nas variáveis λkj e µks como
segue:
45

p X
p X
r
l
X
X


k

min
(ck τj )λkj +
(ck dks )µks




k=1 j=1
k=1 s=1












Sujeito a:




p
p X
r
l

X
 XX
(Ak τjk )λkj +
(Ak dks )µks ≥ p0

k=1 j=1
k=1 s=1




p X
r

X



λkj = 1




j=1
k=1






λkj ≥ 0, k = 1, 2, · · · , p; j = 1, 2, · · · , r






µks ≥ 0, k = 1, 2, · · · , p; s = 1, 2, · · · , l.
(3.59)
(3.60)
(3.61)
(3.62)
Optaremos novamente em aplicar o Método Simplex Revisado, lembrando que o número de
variáveis poderá ser muito grande, a depender da quantidade de pontos extremos e direções extremas.
Iniciaremos com uma solução básica factı́vel e com a matriz base correspondente, B, as variáveis
duais π1 e π0i correspondente á restrição (3.60) e á restrição (3.60), respectivamente. Lembremos
 que

b
0
,
π = (π1 , π01 , · · · , π0k , · · · , π0p ) = fB B −1 , fB é o custo das variáveis básicas λB e b̄ = B −1 
1
mostrado na Tabela 3.1.
(π1 , π01 , · · · , π0k , · · · , π0p )
fB b̄
B −1
b̄
Tabela 3.1: Tabela do simplex revisado do problema mestre.
A solução é ótima para o problema original se os custos relativos de todas as variáveis do problema
mestre são não-negativas, f¯kj ≥ 0 e f¯ks ≥ 0 para todas as variáveis não-básicas. Em particular, as
condições de otimalidade devem satisfazer as seguintes condições:

Ak τjk
k
¯

(i) λkj não básica ⇒ 0 ≤ fkj = ck τj − π
1

Ak dks
(ii) µks não básica ⇒ 0 ≤ f¯ks = ck τjk − π 
0

 = (ck − πAk )τjk − π0k
(3.63)

 = (ck − πAk )dks
(3.64)
Assim, devemos verificar se essas condições são satisfeitas ou não. Determinamos inicialmente
o conjunto solução e o valor objetivo minimal zk0 , de cada subproblema k(3.41) - (3.43) e, em seguida,
aplicamos o critério usual do método simplex (3.52). Se
min min f¯kj = min (zk0 − π0k ) ≥ 0,
k
j
k
(3.65)
Problema Teste 1
46
a solução corrente é ótima. Caso contrário, a coluna para entrar na base é aquela com
min (zk0 − π0k ).
k
(3.66)
Suponhamos primeiramente que o valor da solução ótima do subproblema é ilimitada. Isto é
possı́vel se somente se for encontrada uma direção extrema dvj tal que (ck − πAk )dsv < 0, significando
que
(3.64) foi violada. Portanto, a variável µvs é eleita a entrar na base. Neste caso,
 a condição

v
A d
 v s  é atualizada pré-multiplicando por B −1 e a coluna resultante é inserida na Tabela (3.1).
0
Assim, o método simplex revisado continua com uma próxima iteração.
Consideremos a solução ótima sendo limitada. Neste caso, (ck − πAk )dks ≥ 0 para todas as
direções extremas, valendo a equação (3.64). Agora, observaremos se a equação (3.63) é válida. Seja
τjv um ponto extremo ótimo e considere o objetivo ótimo f¯vj , para o subproblema v. Se f¯vj ≥ 0, então
pela otimalidade de τvk , para cada ponto extremo τjk , temos
(ck − π1 Ak )τjk − π0k ≥ (cv − π1 Av )τjv − π0v = f¯vj ≥ 0
(3.67)
e portanto, a condição (3.63) é satisfeita e temos uma solução ótima do problema original (3.1)
- (3.5).


f¯vj
 na
Caso contrário, a variável λvj é eleita a entrar na base. Isto é feito inserindo a coluna 
yvj


j
Av τv




−1
Tabela 3.1, onde yvj = B  − − − − −  onde uv é um vetor p-componente com um na posição v


uv
e zeros nas outras.
3.2
3.2.1
Problemas Testes
Problema Teste 1
Considere o seguinte problema teste de job-shop, cujos dados são mostrados na Tabela 3.2.
Problema Teste 1
47
produto
operação
duração
máquina
1
1
3
1
1
2
2
2
1
3
1
3
2
4
1
1
2
5
3
3
2
6
4
2
Tabela 3.2: Dados do problema teste 1.
De acordo com o Modelo Matemático (3.1)-(3.5) o problema da Tabela 3.2 é da forma:
min
6
X
(3.68)
tj
j=1
Sujeito a:
−
t1
−
+
t2
−
t2
+
t3
t4
+
t6
≥
3
≥
2
+
t5
≥
1
−
t5
≥
3
3
−
14y14
13
+
14y14
2
−
14y26
10
+
14y26
1
−
14y35
11
+
14y35
−
t1
+
t4
≥
+
t1
−
t4
≥
ti
≥
−
t2
+
t6
≥
+
t2
−
t6
≥
y14
,
y26
0
,
i
,
=
−
t3
+
t5
≥
+
t3
−
t5
≥
y35
1,
∈
2,
−
−
−
{0, 1}
··· ,
6
(3.69)
(3.70)
(3.71)
Além disso, adotamos inicialmente os limites inferior (LIi ) e superior (LSi ), a fim de eliminar
a infactibilidade e limitar o conjunto das soluções viáveis do problema.
LIi ≤ ti ≤ LSi ,
(3.72)
onde
LIi = LS(i−1)
n0
X
LSi = BS −
pl .
l=i
(3.73)
(3.74)
Problema Teste 1
48
Desta forma, pensando no problema de job-shop, podemos relacionar o limite LIi ao ri ,
representando assim o instante mais cedo de inı́cio da execução da operação Oi e o limite LSi adicionado
à duração pi , representando o instante limite do fim da execução da operação Oi , di = LSi + pi .
Logo temos:
0
≤
t1
≤
8
8
≤
t2
≤
11
11
≤
t3
≤
13
0
≤
t4
≤
6
6
≤
t5
≤
7
8
≤
t6
≤
10
(3.75)
Porém, reescrevendo o problema (3.68)-(3.75) conforme notação adotada na Seção 3.1.3,
teremos:
2
X
min
t1i
+
i=1
2
X
t2i
2
X
+
i=1
t3i
(3.76)
i=1
Sujeito a:
t11
−
−
+
t21
−
t21
+
t31
t12
+
t22
≥
1
−
≥
3
t12
≥
+
t11
−
t12
≥
−
t21
+
t22
≥
+
t21
−
t22
≥
tki
≥
0
−
t31
+
t32
≥
+
t31
−
t32
≥
3
y12
,
,
∀i
=
;
∈
0
≤
t11
≤
8
8
≤
t21
≤
11
11
≤
t31
≤
13
0
≤
t12
≤
6
6
≤
t32
≤
7
≤
t22
≤
10
8
−
−
−
2,
(3.77)
3
−
1
14y12
13
+
1
14y12
2
−
2
14y12
10
+
2
14y12
1
−
3
14y12
11
+
3
14y12
(3.78)
(3.79)
{0, 1}
k = 1,
2
t31
+
2
y12
≥
t31
t11
,
3
+
−
1
y12
≥
3
(3.80)
(3.81)
Problema Teste 1
49
ou seja,
min c1 τ 1 + c2 τ 2 + c3 τ 3
S.a:
A1 τ 1
+
A2 τ 2
+
A3 τ 3
τ1
∈
X1 ;
τ2
∈
X2 ;
τ3
∈
X3 ;
≥
p0
onde,

 −1

 0

A1 = 
 0


0
τ1
=
(t1 , t4 )
=
(t11 , t12 )
τ2
=
(t2 , t6 )
=
(t21 , t22 )
τ3
=
(t3 , t5 )
=
(t31 , t32 )
p0
=
(3, 2, 1, 3)

0 

0 


−1 


0

1
;


 −1

A2 = 
 0


0


0 

0 


0 


1
 0

 1

A3 = 
 0


0
;

0 

0 


1 


−1
X1 − região formada pelas restrições (3.88) - (3.92) que compõem o Subproblema 1 abaixo,
sendo que as restrições (3.90)- (3.91) são alteradas a cada iteração.
O problema mestre é apresentado como segue:
min
z=
r
X
(c1 τj1 )λ1j
j=1
S.a:
r
X
j=1
(A1 τj1 )λ1j
+
r
X
(c2 τj2 )λ2j
r
X
+
j=1
+
r
X
(A1 τj1 )λ2j
(c3 τj3 )λ3j
(3.82)
j=1
+
j=1
r
X
(A1 τj1 )λ3j
−
s
=
p0
(3.83)
j=1
r
X
λ1j
≥
1
;
λ1j
≥
0
(3.84)
λ2j
≥
1
;
λ2j
≥
0
(3.85)
λ3j
≥
1
;
λ3j
≥
0
(3.86)
j=1
r
X
j=1
r
X
j=1
Problema Teste 1
50
onde s = (s1 , s2 , s3 , s4 )t .
Resolveremos os subproblemas (3.87)- (3.92), (3.96)- (3.101) e (3.105)-(3.110):
PASSO INICIAL
Subproblemas
Subproblema 1 - Máquina 1
min z1 = c1 τ 1 = t11 + t12
(3.87)
Sujeito a:
1
−t11 + t12 ≥ 3 − 14y12
(3.88)
1
t11 − t12 ≥ −13 + 14y12
(3.89)
0 ≤ t11 ≤ 8
(3.90)
0 ≤ t12 ≤ 6
(3.91)
1
y12
∈ {0, 1}
(3.92)
Solução:
τ11 = (1, 0)
(3.93)
z01 = 1
(3.94)
1
y12
=1
(3.95)
min z2 = c2 τ 1 = t21 + t22
(3.96)
Sujeito a:
2
t21 − t22 ≥ 2 − 14y12
(3.97)
2
−t21 + t22 ≥ −10 + 14y12
(3.98)
8 ≤ t21 ≤ 11
(3.99)
8 ≤ t22 ≤ 10
(3.100)
2
y12
∈ {0, 1}
(3.101)
Problema Teste 1
51
Solução:
τ12 = (8, 10)
(3.102)
z02 = 18
(3.103)
2
y12
=0
(3.104)
min z2 = c3 τ 3 = t31 + t32
(3.105)
Sujeito a:
3
−t31 + t32 ≥ 1 − 14y12
(3.106)
3
t31 − t32 ≥ −11 + 14y12
(3.107)
11 ≤ t31 ≤ 13
(3.108)
6 ≤ t32 ≤ 7
(3.109)
3
y12
∈ {0, 1}
(3.110)
Solução:
τ13 = (11, 6)
(3.111)
z03 = 17
(3.112)
3
y12
=1
(3.113)
Com as soluções (3.93),(3.102) e (3.111) dos Subproblemas 1,2,3, respectivamente, obtemos
o problema mestre (3.114)-(3.118) como segue:
min z =
(c1 τ11 )λ1j
+
(c2 τ12 )λ21
(3.114)
(c3 τ13 )λ31
+
S.a:
(A1 τ11 )λ11
+
(A2 τ12 )λ21
+
(A3 τ13 )λ31
−
s
=
p0
(3.115)
λ11
≥
1
;
λ11
≥
0
(3.116)
λ21
≥
1
;
λ21
≥
0
(3.117)
λ31
≥
1
;
λ31
≥
0
(3.118)
No entanto, ao acrescentarmos as variáveis de folga, não é possı́vel encontrar uma solução
básica inicial. Portanto, aplicaremos o método de duas fases([4]) ao problema mestre (3.114)-(3.118).
Assim, a tabela inicial do método simplex revisado, Tabela 3.3, é a seguinte:
Problema Teste 1
52
Variável básica
s1
s1
s2
s3
s4
λ11
λ21
λ31
−z
Constantes
1
s2
4
1
1
s3
1
s4
5
1
λ11
1
1
λ21
1
1
λ31
1
1
−z
-1
-18
-17
1
1
-36
Tabela 3.3: Tabela inicial do simplex revisado do P.M do problema teste 1.
Conseqüentemente,
π = (π1 , π01 , π02 , π03 ) = fB B −1 = (cB τ B )B −1
π = (0, 0, 0, 0, 1, 18, 17)
(3.119)
ITERAÇÃO 1
Relembremos que a partir desta iteração, novos limites são aplicados a cada tarefa a fim
de obtermos uma melhor aproximação à solução do problema original (3.76)-(3.80). Consideramos
a solução da iteração anterior e reajustamos os limites inferiores de cada tarefa de acordo com as
restrições de precedência. Proporcionalmente, ajustamos os limites superiores, conforme procedimento
do algoritmo 3.1 no item 2. Desta forma, considerando a variável dual (3.119) e as novas restrições
temos:
min z1 = c1 τ 1 = t11 + t12
(3.120)
Sujeito a:
1
−t11 + t12 ≥ 3 − 14y12
(3.121)
1
t11 − t12 ≥ −13 + 14y12
(3.122)
0 ≤ t11 ≤ 1
(3.123)
t12 = 0
(3.124)
1
y12
∈ {0, 1}
(3.125)
Problema Teste 1
53
Solução:
τ21 = (1, 0)
(3.126)
z01 = 1
(3.127)
1
y12
=1
(3.128)
min z2 = c2 τ 2 = t21 + t22
(3.129)
Sujeito a:
2
t21 − t22 ≥ 2O14y12
(3.130)
2
−t21 + t22 ≥ −10 + 14y12
(3.131)
4 ≤ t21 ≤ 7
(3.132)
5 ≤ t22 ≤ 8
(3.133)
2
y12
∈ {0, 1}
(3.134)
Solução:
τ22 = (4, 6)
(3.135)
z02 = 10
(3.136)
2
y12
=0
(3.137)
min z2 = c3 τ 3 = t31 + t32
(3.138)
Sujeito a:
3
−t31 + t32 ≥ 1 − 14y12
(3.139)
3
t31 − t32 ≥ −11 + 14y12
(3.140)
9 ≤ t31 ≤ 11
(3.141)
1 ≤ t32 ≤ 2
(3.142)
3
y12
∈ {0, 1}
(3.143)
Solução:
τ23 = (9, 1)
(3.144)
z03 = 10
(3.145)
3
y12
=1
(3.146)
Problema Teste 1
54
Assim teremos:
z10 − π01 = 1 − 1 = 0
(3.147)
z20 − π02 = 10 − 18 = −8
(3.148)
z30 − π03 = 10 − 17 = −7
(3.149)
Portanto λ22 e λ32 são candidatas a entrar na base visto que seus custos reduzidos são não
negativos (≤ 0). Tomamos inicialmente λ22 pois z20 − π02 = −8 < −7. Isto é mostrado na seguinte
seqüência de Tabelas 3.4, 3.5 e 3.6. Além disso, o limite inferior(LI) para o ótimo do problema proposto
(3.76) - (3.81) é dado por 36 − 15 = 21 e o limite superior(LS) é 36.
Variável básica
s1
s1
s2
s3
s4
λ11
λ21
λ31
−z
1
s2
1
s3
1
s4
1
λ11
1
λ21
1
λ31
1
−z
-1
-18
-17
1
Coluna de entrada
Constantes
λ22
4
4
1
-4
5
0
1
6
1
0
1
1
1
0
-36
-8
Tabela 3.4: Entra na base a variável λ22 , sai s4 .
Variável básica
s1
s1
s2
s3
λ22
s2
s3
1
1
λ22
Constantes
λ32
− 32
10
3
2
3
2
3
5
3
25
3
λ21
−z
5
1
1
6
− 16
1
0
5
6
1
6
1
1
−104
3
-7
1
6
1
− 61
1
λ31
−z
λ31
1
λ11
λ21
λ11
Coluna de entrada
1
4
3
-1
-18
-17
1
Tabela 3.5: Entra na base a variável λ32 , sai s2 .
Problema Teste 1
55
Variável básica
s1
λ32
1
2
− 25
− 18
25
16
5
λ32
3
25
2
25
1
5
s3
3
− 25
2
− 25
24
5
λ22
1
50
9
50
1
5
λ21
1
− 50
9
− 50
λ31
3
− 25
2
− 25
−z
21
25
142
75
s1
s3
1
λ22
λ11
λ11
λ21
λ31
−z
1
1
4
5
1
4
5
1
-1
Constantes
-18
-17
1
− 499
15
Tabela 3.6: Tabela final na iteração 1 do problema teste 1.
Da Tabela 3.6 podemos determinar a solução corrente do problema proposto (3.76) - (3.81):
λ11 τ11 = 1.(1, 0) =
λ21 τ12 =
4
5 .(8, 10)
λ22 τ22 =
1
5 .(4, 6)
λ31 τ13 =
4
5 .(11, 6)
λ32 τ23 =
1
5 .(9, 1)
(1, 0)
40
= ( 32
5 , 5 )
=
( 45 , 65 )
(3.150)
24
= ( 44
5 , 5 )
=
( 95 , 15 )
ou seja,
τ 1 = λ11 τ11 = (1, 0)
46
τ 2 = λ21 τ12 + λ22 t22 = ( 36
5 , 5 )
(3.151)
τ 3 = λ31 τ 3 + λ32 t32 = ( 53
5 , 5).
53
46
Assim, τ = (t1 , t2 , t3 , t4 , t5 , t6 ) = (1, 36
5 , 5 , 0, 5, 5 ) e z = 33
ITERAÇÃO 2
Conforme Tabela 3.6,
π = (0, −
21
142
, 0, −
, 1, 18, 17).
25
75
(3.152)
Atualizando as funções objetivo e calculando os novos limites de cada subproblema temos:
Problema Teste 1
56
min z1 = (c1 − π1 A1 )τ 1 = t11 + t12
(3.153)
Sujeito a:
1
−t11 + t12 ≥ 3 − 14y12
(3.154)
1
t11 − t12 ≥ −13 + 14y12
(3.155)
0 ≤ t11 ≤ 1
(3.156)
t12 = 0
(3.157)
1
∈ {0, 1}
y12
(3.158)
Solução:
τ31 = (1, 0)
(3.159)
z01 = 1
(3.160)
1
y12
=1
(3.161)
4 2 217 2
t1 +
t2
25
75
(3.162)
2
t21 − t22 ≥ 2 − 14y12
(3.163)
2
−t21 + t22 ≥ −10 + 14y12
(3.164)
4 ≤ t21 ≤ 7
(3.165)
5 ≤ t22 ≤ 8
(3.166)
2
y12
∈ {0, 1}
(3.167)
min z2 = c2 τ 2 =
Sujeito a:
Solução:
τ32 = (4, 6)
(3.168)
z02 = 18
(3.169)
2
y12
=0
(3.170)
Problema Teste 1
57
46 3 67 3
t1 −
t2
25
75
(3.171)
3
−t31 + t32 ≥ 1 − 14y12
(3.172)
3
t31 − t32 ≥ −11 + 14y12
(3.173)
9 ≤ t31 ≤ 11
(3.174)
1 ≤ t32 ≤ 2
(3.175)
3
∈ {0, 1}
y12
(3.176)
min z3 = (c3 − π3 A3 )τ 3 =
Sujeito a:
Solução:
(3.177)
τ33 = (9, 1)
1175
75
(3.178)
3
y12
=1
(3.179)
z03 =
Considerando as soluções (3.159),(3.168),(3.177) e as variáveis duais da expressão (3.152)
temos os seguintes custos reduzidos:
z10 − π01 = 1 − 1 = 0
(3.180)
z20 − π02 = 18 − 18 = 0
1175
100
4
z30 − π03 =
− 17 = −
=−
75
75
3
(3.181)
(3.182)
Observamos que z10 − π01 = z20 − π03 = 0, conforme o custo reduzido (3.180) e (3.181).
Portanto, de acordo com (3.182), λ33 é a única variável a entrar na base(ver Tabela 3.6 e 3.8).
O novo limite inferior é dado por
499
15
−
4
3
=
479
15
= 31, 93 e o superior é
499
15
= 33, 26
Problema Teste 1
58
Variável básica
s1
λ32
1
2
− 25
λ32
3
25
s3
3
− 25
λ22
1
50
s1
s3
1
λ22
λ11
Constantes
λ33
18
− 25
16
5
0
2
25
1
5
1
2
− 25
24
5
0
9
50
1
5
0
1
0
4
5
0
1
4
5
0
-17
− 499
15
− 43
λ11
λ21
λ31
Coluna de Entrada
−z
1
λ21
1
− 50
9
− 50
λ31
3
− 25
2
− 25
−z
21
25
142
75
1
-1
-18
1
Variável básica
s1
λ33
1
2
25
− 18
25
16
5
λ33
3
25
2
25
1
5
s3
3
− 25
2
− 25
24
5
λ22
1
50
9
50
1
5
λ21
1
− 50
9
− 50
λ31
3
− 50
2
− 25
−z
1
2
s1
s3
1
λ22
λ11
λ11
λ21
λ31
−z
1
Constantes
1
4
5
1
4
5
1
-1
-18
-17
1
-33
Temos da Tabela 3.8 a seguinte solução para o problema proposto (3.76) - (3.81):
λ11 τ11 = 1.(1, 0) =
λ21 τ12 =
4
5 .(8, 10)
λ22 τ22 =
1
5 .(4, 6)
λ31 τ13 =
4
5 .(11, 6)
λ33 τ33 =
1
5 .(9, 1)
(1, 0)
125
= ( 25
4 , 16 )
=
( 78 , 21
16 )
(3.183)
24
= ( 44
5 , 5 )
=
( 95 , 15 )
ou seja, a mesma solução da Iteração 3, conforme dados abaixo:
τ 1 = λ11 τ11 = (1, 0)
46
τ 2 = λ21 τ12 + λ22 τ22 = ( 36
5 , 5 )
τ 3 = λ31 τ 3 + λ33 τ33 = ( 53
5 , 5)
53
46
τ = (t1 , t2 , t3 , t4 , t5 , t6 ) = (1, 36
5 , 5 , 0, 5, 5 )
(3.184)
Problema Teste 1
59
Nesta iteração temos como limite inferior 33 − 1 = 32 e limite superior 33.
ITERAÇÃO 3
De acordo com a Tabela 3.8, π = (0, −1, 0, −2, 1, 18, 17) e considerando as soluções (3.159),
(3.168) e (3.177) os subproblemas 1, 2 e 3 continuam sujeitos as mesmas restrições que a Iteração 2,
visto que as soluções não alteraram. Segue-se:
min z1 = c1 τ 1 = t11 + t12
(3.185)
Sujeito a:
1
−t11 + t12 ≥ 3 − 14y12
(3.186)
1
t11 − t12 ≥ −13 + 14y12
(3.187)
0 ≤ t11 ≤ 1
(3.188)
t12 = 0
(3.189)
1
y12
∈ {0, 1}
(3.190)
Solução:
τ41 = (1, 0)
(3.191)
z01 = 1
(3.192)
1
y12
=1
(3.193)
min z2 = c2 τ 2 = 3t22
(3.194)
Sujeito a:
2
t21 − t22 ≥ 2 − 14y12
(3.195)
2
−t21 + t22 ≥ −10 + 14y12
(3.196)
4 ≤ t21 ≤ 7
(3.197)
5 ≤ t22 ≤ 8
(3.198)
2
y12
∈ {0, 1}
(3.199)
Solução:
(3.200)
τ42 = (4, 6)
(3.201)
z02 = 18
(3.202)
2
y12
=0
(3.203)
Problema Teste 1
60
min z2 = c3 τ 3 = 2t31 − t32
(3.204)
Sujeito a:
3
−t31 + t32 ≥ 1 − 14y12
(3.205)
3
t31 − t32 ≥ −11 + 14y12
(3.206)
9 ≤ t31 ≤ 11
(3.207)
1 ≤ t32 ≤ 2
(3.208)
3
∈ {0, 1}
y12
(3.209)
Solução:
(3.210)
τ43 = (9, 2)
(3.211)
z02 = 16
(3.212)
3
y12
=0
(3.213)
Portanto teremos:
z10 − π01 = 1 − 1 = 0
(3.214)
z20 − π02 = 18 − 18 = 0
(3.215)
z30 − π03 = 16 − 17 = −1
(3.216)
Como z10 − π01 = z20 − π02 = 0, então λ34 é a única candidata a entrar na base.
Variável básica
s1
λ34
Constantes
λ34
1
2
25
18
− 25
16
5
18
25
λ34
3
25
2
25
1
5
23
25
s3
3
− 25
2
− 25
24
5
27
25
λ22
1
50
9
50
1
5
9
− 50
1
0
λ21
1
− 50
9
− 50
4
5
9
50
λ31
3
− 50
2
− 25
4
5
2
25
−z
1
2
-33
-1
s1
s3
1
λ22
λ11
λ11
λ21
λ31
−z
Coluna de entrada
1
1
1
-1
-18
-17
1
Problema Teste 1
61
Variável básica
s1
λ34
1
4
− 23
− 18
23
70
23
λ34
3
23
2
23
5
23
s3
6
− 23
4
− 23
105
23
λ22
1
23
9
46
11
46
s1
s3
λ22
1
λ11
λ11
λ21
λ31
−z
1
λ21
1
− 23
9
− 46
λ31
3
− 23
2
− 23
−z
26
− 23
− 48
23
1
35
46
1
18
23
1
-1
Constantes
-18
-17
1
− 754
23
Tabela 3.10: Tabela final da iteração 3 do problema teste 1.
Conforme a Tabela 3.10
π = (0, −
26
48
, 0, − , 1, 18, 17).
23
23
(3.217)
Além disso, pela mesma razão da Iteração 3 os subproblemas estão sujeitos às mesmas restrições.
Portanto, segue os subproblemas com as funções objetivo atualizadas:
ITERAÇÃO 4
min z1 = c1 τ 1 = t11 + t12
(3.218)
Sujeito a:
1
−t11 + t12 ≥ 3 − 14y12
(3.219)
1
t11 − t12 ≥ −13 + 14y12
(3.220)
0 ≤ t11 ≤ 1
(3.221)
t12 = 0
(3.222)
1
y12
∈ {0, 1}
(3.223)
Solução:
τ51 = (1, 0)
(3.224)
z01 = 1
(3.225)
1
y12
=1
(3.226)
Problema Teste 1
62
min z2 = c2 τ 2 = −
3 2 71 2
t1 +
t2
23
23
(3.227)
Sujeito a:
2
t21 − t22 ≥ 2 − 14y12
(3.228)
2
−t21 + t22 ≥ −10 + 14y12
(3.229)
4 ≤ t21 ≤ 7
(3.230)
5 ≤ t22 ≤ 8
(3.231)
2
∈ {0, 1}
y12
(3.232)
Solução:
(3.233)
τ52 = (4, 6)
(3.234)
z02 = 18
(3.235)
2
y12
=0
(3.236)
49 3 25 3
t1 −
t2
23
23
(3.237)
3
−t31 + t32 ≥ 1 − 14y12
(3.238)
3
t31 − t32 ≥ −11 + 14y12
(3.239)
9 ≤ t31 ≤ 11
(3.240)
1 ≤ t32 ≤ 2
(3.241)
3
y12
∈ {0, 1}
(3.242)
min z2 = c3 τ 3 =
Sujeito a:
Solução:
(3.243)
τ53 = (9, 2)
(3.244)
z02 = 17
(3.245)
3
y12
=0
(3.246)
Assim, os custos reduzidos z10 − π01 = z20 − π02 = z30 − π03 = 0, não ocorrendo candidatas a
entrar na base significa que chegamos na solução ótima.
Notemos que o limite inferior da solução ótima do problema proposto (3.76)-(3.81) é o mesmo
valor da sua solução corrente:
754
23
−0=
754
23
= 32, 78.
Problema Teste 1
63
Deste modo, a solução ótima para o problema proposto (3.76)-(3.81):
λ11 τ11 = 1.(1, 0) =
λ21 τ12 =
35
46 .(8, 10)
λ22 τ22 =
11
46 .(4, 6)
λ31 τ13 =
18
23 .(11, 6)
λ34 τ43 =
5
23 .(9, 2)
(1, 0)
175
= ( 140
23 , 23 )
=
33
( 22
23 , 23 )
(3.247)
108
= ( 198
23 , 23 )
=
10
( 45
23 , 23 )
ou seja,
τ 1 = λ11 τ11 = (1, 0)
(3.248)
162 208
,
)
23 23
243 118
= λ31 τ 3 + λ34 τ43 = (
,
)
23 23
τ 2 = λ21 τ12 + λ22 τ22 = (
(3.249)
τ3
(3.250)
243
208 118
Assim τ 0 = (t1 , t2 , t3 , t4 , t5 , t6 , t7 ) = (1, 162
23 , 23 , 0, 23 , 23 ) e z =
754
23
= 32, 78 é o vetor ótimo
e a valor ótimo respectivamente.
A Tabela 3.11 mostra, a cada iteração o limite inferior(LI) e o limite superior(LS) para a
solução ótima do problema proposto(3.76)-(3.81) considerando os limites adotados para as variáveis
(ver algoritmo 3.1). Enquanto que a Tabela 3.12 indica o valor ótimo para o problema original (3.68)
- (3.71) sem os limites adotados, o valor ótimo para o problema proposto (3.76)- (3.81) e o seu valor
ótimo ao aplicarmos o método de resolução de Dantzig-Wolfe incluindo o ajuste dos limites LIi (3.73)
e LSi (3.74).
Iteração
LS
LI
1
36
21
2
33,26
31,93
3
33
32
4
32,78
32,78
Tabela 3.11: Limites por iteração do problema teste 1.
Valor ótimo sem limite
18
Valor ótimo com limite
36
Valor ótimo encontrado
32,78
Tabela 3.12: Comparação das soluções do problema teste 1.
Problema Teste 1
64
33,26
e dos limites inferiores
Progresso dos valores da função objetivo
Valores da função objetivo ( Primal )
36
33
32,78
32
31,93
Limites inferiores ( Dual )
21
1
2
3
4
Iteração
Figura 3.1: Convergência do método do problema teste 1.
M1
P1
P2
M2
M3
0
10
~ S :
Solucao
1
´
C
max1
=10
33
tempo
M1
P1
P2
M2
M3
14
0
~ S :
Solucao
2
´
tempo
C
max2 = 14
M
1
P
M
2
P
M
3
1
2
10
Solucao S : C
=10
max
3
Figura 3.2: Diagrama de Gantt representando as soluções encontradas do problema teste 1.
Analisando os valores expressos nas Tabelas 3.11 e 3.12, notamos que o ”valor ótimo encontrado“ é um limitante inferior para o ”o valor ótimo sem limite”do problema proposto inicial
(3.76)-(3.81) e um limitante superior para o ”valor ótimo sem limite”do problema original (3.68)(3.71). Podemos então concluir que apesar do valor ótimo encontrado para os problemas criados a
partir do problema original, é possı́vel determinar limitantes inferior e superior para o valor ótimo
global. Porém, devemos adotar limites adequados que contornem a infactibilidade e limite a região
factı́vel sem causar importantes alterações no espaços de soluções do problema original. Isto significa
Problema Teste 2
65
dizer que quanto melhor forem os limites adotados para as variáveis do problema original, os limitantes
estarão mais próximo do valor ótimo global original.
3.2.2
Problema Teste 2
Considere o seguinte problema de job-shop, cujos dados são mostrados na Tabela 3.13.
produto
operação
duração
máquina
1
1
5
1
1
2
2
2
1
3
3
3
2
4
2
2
2
5
1
1
3
6
3
2
3
7
2
3
Tabela 3.13: Dados do problema teste 2.
Conforme o Modelo Matemático (3.1)-(3.5) o problema da Tabela 3.13 apresenta-se da
seguinte forma:
min
7
X
(3.251)
tj
j=1
Sujeito a:
−
t1
+
t5
+
t2
−
t2
+
−
t3
t4
−
t6
+
t7
≥
5
≥
2
≥
2
≥
3
5
−
18y15
17
+
18y15
−
t1
+
t5
≥
+
t1
−
t5
≥
−
(3.252)
Problema Teste 2
66
+
t2
−
t4
≥
−
t2
+
t4
≥
+
t2
−
t6
≥
−
t2
+
t6
≥
+
t4
−
t6
≥
−
t4
+
t6
≥
y15
,
y24
ti
≥
0
,
,
+
t3
−
t7
≥
−
t3
+
t7
≥
y26
i
,
=
y46
1,
,
2,
y37
··· ,
∈
−
−
−
−
2
−
18y24
16
+
18y24
3
−
18y26
16
+
18y26
3
−
18y46
16
+
18y46
2
−
18y37
15
+
18y37
(3.253)
(3.254)
{0, 1}
(3.255)
7
Determinando os limites conforme expressões (3.73) e (3.74) temos:
0
≤
t1
≤
8
8
≤
t2
≤
13
13
≤
t3
≤
15
0
≤
t4
≤
15
15
≤
t5
≤
17
0
≤
t6
≤
13
13
≤
t7
≤
16
(3.256)
Porém, reescrevendo o problema original (3.251)-(3.256) conforme notação adotada na Seção
3.1.3, teremos:
min
2
X
t1i
+
i=1
3
X
t2i
+
i=1
2
X
t3i
(3.257)
i=1
Sujeito a:
−
t11
+
t12
+
t21
−
t21
+
−
t31
t22
−
t23
+
t32
≥
5
≥
2
≥
2
≥
3
(3.258)
Problema Teste 2
67
−
t11
+
t12
≥
+
t11
−
t12
≥
+
t21
−
t22
≥
−
t21
+
t22
≥
+
t21
−
t23
≥
−
t21
+
t23
≥
1
y12
tki
+
t22
−
t23
≥
−
t22
+
t23
≥
2
y12
,
≥
0
2
y13
,
,
∀i
,
;
+
t31
−
t32
≥
−
t31
+
t32
≥
2
y23
3
y12
,
t11
≤
8
8
≤
t21
≤
13
13
≤
t31
≤
15
0
≤
t22
≤
15
15
≤
t12
≤
17
0
≤
t22
≤
13
≤
t32
≤
16,
13
min c1 τ 1 + c2 τ 2 + c3 τ 3
S.a:
+
A2 τ 2
+
A3 τ 3
τ1
∈
X1 ;
τ2
∈
X2 ;
τ3
∈
X3 ;
−
−
−
{0, 1}
1
18y12
17
+
1
18y12
2
−
2
18y12
16
+
2
18y12
3
−
2
18y13
16
+
2
18y13
3
−
2
18y23
16
+
2
18y23
2
−
3
18y12
15
+
3
18y12
(3.259)
(3.260)
(3.262)
ou seja,
A1 τ 1
−
−
(3.261)
k = 1, 2, 3
≤
0
∈
−
5
≥
p0
onde,
τ1
=
(t1 , t5 )
=
(t11 , t12 )
τ2
=
(t2 , t4 , t6 )
=
(t21 , t22 , t23 )
τ3
=
(t3 , t7 )
=
(t31 , t32 )
p0
=
(5, 2, 2, 3)
Problema Teste 2
68

 −1

 0

A1 = 
 0


0

0 

0 


1 


0

1
;


 −1

A2 = 
 0


0

0 

0 


0 


−1
0
0
−1
0

 0

 1

A3 = 
 0


0
;

0 

0 


0 


1
X1 − região formada pelas restrições (3.269)-(3.273) que compõem o Subproblema 1 abaixo,
sendo que as restrições (3.271) - (3.272) são alteradas a cada iteração.
O problema mestre é apresentado como segue:
min
z=
r
X
(c1 τj1 )λ1j
+
j=1
S.a:
r
X
(A1 τj1 )λ1j
j=1
r
X
(c2 τj2 )λ2j
r
X
+
j=1
+
r
X
(A1 τj1 )λ2j
(c3 τj3 )λ3j
(3.263)
j=1
+
j=1
r
X
(A1 τj1 )λ3j
−
s
=
p0
(3.264)
j=1
r
X
λ1j
≥
1
;
λ1j
≥
0
(3.265)
λ2j
≥
1
;
λ2j
≥
0
(3.266)
λ3j
≥
1
;
λ3j
≥
0
(3.267)
j=1
r
X
j=1
r
X
j=1
onde s = (s1 , s2 , s3 , s4 )t .
Resolvendo os subproblemas (3.268)- (3.273), (3.277)- (3.289) e (3.294)-(3.299):
PASSO INICIAL
Subproblemas
min z1 = c1 τ 1 = t11 + t12
(3.268)
Sujeito a:
1
−t11 + t12 ≥ 5 − 18y12
(3.269)
1
t11 − t12 ≥ −17 + 18y12
(3.270)
Problema Teste 2
69
0 ≤ t11 ≤ 8
(3.271)
15 ≤ t12 ≤ 17
(3.272)
1
y12
∈ {0, 1}
(3.273)
Solução:
τ11 = (0, 15)
(3.274)
z01 = 15
(3.275)
1
=0
y12
(3.276)
min z2 = c2 τ 1 = t21 + t22 + t23
(3.277)
Sujeito a:
2
t21 − t22 ≥ 2 − 18y12
(3.278)
2
−t21 + t22 ≥ −16 + 18y12
(3.279)
2
t21 − t23 ≥ 3 − 18y13
(3.280)
2
−t21 + t23 ≥ −16 + 18y13
(3.281)
2
t22 − t23 ≥ 3 − 18y23
(3.282)
2
−t22 + t23 ≥ −16 + 18y23
(3.283)
8 ≤ t21 ≤ 13
(3.284)
0 ≤ t22 ≤ 15
(3.285)
0 ≤ t23 ≤ 13
(3.286)
2
y12
∈ {0, 1}
(3.287)
2
y13
∈ {0, 1}
(3.288)
2
y23
∈ {0, 1}
(3.289)
Solução:
τ12 = (8, 0, 2)
(3.290)
z02 = 10
(3.291)
2
y12
=0
(3.292)
2
2
y13
= y23
=1
(3.293)
Problema Teste 2
70
min z2 = c3 τ 3 = t31 + t32
(3.294)
Sujeito a:
3
t31 − t32 ≥ 2 − 18y12
(3.295)
3
−t31 + t32 ≥ −15 + 18y12
(3.296)
13 ≤ t31 ≤ 15
(3.297)
13 ≤ t32 ≤ 16
(3.298)
3
∈ {0, 1}
y12
(3.299)
Solução:
τ13 = (15, 13)
(3.300)
z03 = 28
(3.301)
3
y12
=0
(3.302)
Com as soluções (3.274),(3.290) e (3.300) dos Subproblemas 1,2,3, respectivamente, obtemos
o problema mestre (3.303)-(3.307) como segue:
min z =
(c1 τ11 )λ1j
+
(c2 τ12 )λ21
(3.303)
(c3 τ13 )λ31
+
S.a:
(A1 τ11 )λ11
+
(A2 τ12 )λ21
+
(A3 τ13 )λ31
−
s
=
p0
(3.304)
λ11
≥
1
;
λ11
≥
0
(3.305)
λ21
≥
1
;
λ21
≥
0
(3.306)
λ31
≥
1
;
λ31
≥
0
(3.307)
Aplicando o Método de Duas Fases([4]) ao problema mestre (3.303)-(3.307) obtemos a solução
básica inicial como mostra a Tabela 3.14.
Conseqüentemente,
π = (π1 , π01 , π02 , π03 ) = fB B −1 = (cB τ B )B −1
π = (0, 0, 0, 0, 15, 10, 28)
(3.308)
ITERAÇÃO 1
Relembremos que a partir desta iteração, novos limites são aplicados a cada tarefa a fim de
obtermos uma melhor aproximação para a solução do problema original (3.251)-(3.255). Relembremos
Problema Teste 2
71
Variável básica
s1
s1
s2
s2
s3
s4
λ11
λ21
λ31
−z
1
Constantes
3
1
5
s3
1
13
s4
1
λ11
10
1
λ21
1
1
λ31
1
1
−z
-15
-10
-28
1
1
-53
Tabela 3.14: Tabela inicial do simplex revisado do P.M do problema teste 2.
que tomemos a solução da iteração anterior e reajustamos os limites inferiores de cada tarefa de
acordo com as restrições de precedência. Proporcionalmente, ajustamos os limites superiores, conforme
procedimento do algoritmo (3.1) no item 2. Desta forma, considerando a variável dual (3.308) e as
novas restrições temos:
min z1 = c1 τ 1 = t11 + t12
(3.309)
Sujeito a:
1
−t11 + t12 ≥ 5 − 18y12
(3.310)
1
t11 − t12 ≥ −17 + 18y12
(3.311)
t11 = 0
(3.312)
2 ≤ t12 ≤ 4
(3.313)
1
y12
∈ {0, 1}
(3.314)
Solução:
INFACTÍVEL
(3.315)
Observemos que a solução do Subproblema 1 é infactı́vel. Isto ocorre ao considerarmos
as restrições (3.312) e (3.313), não satisfazendo assim as restrições de máquina (3.310) e (3.311).
Reajustamos novamente os limites, substituindo a restrição (3.313) pela restrição
2 ≤ t12 ≤ 6.
(3.316)
Problema Teste 2
72
A nova solução é dada como:
τ22 = (0, 5)
(3.317)
z01 = 5
(3.318)
1
y12
=0
(3.319)
min z2 = c2 τ 2 = t21 + t22 + t23
(3.320)
Sujeito a:
2
t21 − t22 ≥ 2 − 18y12
(3.321)
2
−t21 + t22 ≥ −16 + 18y12
(3.322)
2
t21 − t23 ≥ 3 − 18y13
(3.323)
2
−t21 + t23 ≥ −16 + 18y13
(3.324)
2
t22 − t23 ≥ 3 − 18y23
(3.325)
2
−t22 + t23 ≥ −16 + 18y23
(3.326)
5 ≤ t21 ≤ 8
(3.327)
t22 = 0
(3.328)
t23 = 2
(3.329)
2
y12
∈ {0, 1}
(3.330)
2
y13
∈ {0, 1}
(3.331)
2
y23
∈ {0, 1}
(3.332)
Solução:
(3.333)
τ22 = (5, 0, 2)
(3.334)
z02 = 7
(3.335)
2
y12
=1
(3.336)
2
2
y13
= y23
=0
(3.337)
Problema Teste 2
73
min z2 = c3 τ 3 = t31 + t32
(3.338)
Sujeito a:
3
t31 − t32 ≥ 2 − 18y12
(3.339)
3
−t31 + t32 ≥ −15 + 18y12
(3.340)
12 ≤ t31 ≤ 14
(3.341)
5 ≤ t32 ≤ 8
(3.342)
3
∈ {0, 1}
y12
(3.343)
Solução:
(3.344)
τ23 = (12, 5)
(3.345)
z02 = 17
(3.346)
3
y12
=0
(3.347)
z10 − π01 = 5 − 15 = −10
(3.348)
z20 − π02 = 7 − 10 = −3
(3.349)
z30 − π03 = 17 − 28 = −11
(3.350)
Assim teremos:
Portanto λ32 , λ12 e λ22 são candidatas a entrar na base visto que seus custos reduzidos são
não negativos (≤ 0). Tomamos inicialmente λ32 pois z30 − π03 = −11 < −10 < −3. Isto é mostrado na
seguinte seqüência de Tabelas 3.15, 3.16, 3.17 e 3.18. Notemos que o limite inferior(LI), para o ótimo
do problema proposto (3.257) - (3.262) é dado por 53 − 24 = 29 e o limite superior é 53.
Problema Teste 2
74
Variável básica
s1
s1
s2
s3
s4
λ11
λ21
λ31
−z
Coluna de entrada
Constantes
λ32
3
0
5
12
13
0
10
5
1
0
1
0
1
1
-53
-11
1
s2
1
s3
1
s4
1
λ11
1
λ21
1
λ31
1
−z
-15
-10
-28
1
Tabela 3.15: Entra λ32 , sai s2 .
Variável básica
s1
s1
λ32
s3
s4
λ11
λ21
λ31
−z
Coluna de entrada
Constantes
λ12
3
0
5
12
0
13
5
95
12
0
1
1
1
0
7
12
0
−581
12
-10
1
1
12
λ32
s3
1
−5
12
s4
1
λ11
1
λ21
1
λ31
−1
12
−z
11
12
1
-15
-10
-28
1
Tabela 3.16: Entra λ12 ,sai λ11 .
Variável básica
s1
s1
λ32
λ32
s4
λ12
λ21
λ31
−z
Constantes
λ22
3
5
5
12
−5
12
1
1
12
s3
s4
s3
Coluna de entrada
1
−5
12
-5
1
λ12
1
λ21
1
λ31
−1
12
−z
11
12
1
-5
-10
-28
1
8
0
95
12
1
12
1
0
1
1
7
12
5
12
−461
12
-3
Tabela 3.17: Entra λ22 , sai s1 .
Da Tabela 3.18 podemos determinar a solução corrente do problema proposto (3.257) - (3.262):
λ12 τ21 = 1.(0, 5) =
λ21 τ12 =
2
5 .(8, 0, 2)
(0, 5)
4
= ( 16
5 , 0, 5 )
(3.351)
Problema Teste 2
75
Variável básica
λ22
λ22
1
5
λ32
1
12
λ32
s4
λ12
λ31
−z
1
12
Constantes
2
3
1
1
− 60
λ21
3
5
s3
s4
s3
5
− 12
-5
8
188
15
1
λ12
1
λ21
− 51
λ31
−1
12
−1
12
−z
3
5
11
12
1
2
5
1
1
3
1
-5
-10
-28
1
−2197
60
λ22 τ22 =
3
5 .(5, 0, 2)
= (3, 0, 65 )
λ31 τ13 =
1
3 .(15, 13)
= (5, 13
3 )
λ32 τ23 =
2
3 .(12, 5)
=
(3.352)
(8, 10
3 )
ou seja,
τ 1 = λ12 τ21 = 1.(0, 5) = (0, 5)
τ 2 = λ21 τ12 + λ23 t23 = ( 31
5 , 0, 2)
(3.353)
τ 3 = λ31 τ 3 + λ32 t32 = (13, 23
3 ).
23
Assim, τ = (t1 , t2 , t3 , t4 , t5 , t6 , t7 ) = (0, 31
5 , 13, 0, 5, 2, 3 ) e z =
508
15
= 33, 86.
ITERAÇÃO 2
Conforme Tabela 3.18, π = (− 35 , − 11
12 , 0, 0, 5, 10, 28) e atualizando as funções objetivo de cada
subproblema teremos:
2
min z1 = (c1 − π1 A1 )τ 1 = t11 + t12
5
41
min z2 = (c2 − π2 A2 )τ 2 = t21 + t22 + t23
60
23
3
min z3 = (c3 − π3 A3 )τ = t31 + t32
12
Cada subproblema estará sujeito às mesmas restrições da iteração anterior, visto que as
soluções dos mesmos não alteraram. Assim, temos como solução:
τ31 = (0, 5)
1 =0
y12
z10 = 5
2 = y 2 = 0; y 2 = 1 z 0 =
τ32 = (5, 0, 2) y12
13
23
2
τ33 = (12, 5)
3 =0
y12
65
12
z30 = 28
(3.354)
Problema Teste 2
76
Daı́ determinamos os custos reduzidos:
z10 − π01 = 5 − 5 = 0
65
55
z20 − π02 =
− 10 = −
12
12
0
z3 − π03 = 28 − 28 = 0
(3.355)
(3.356)
(3.357)
Observamos que z10 − π01 = z30 − π03 = 0, conforme o custo reduzido (3.355) e (3.357).
Portanto, de acordo com (3.356), λ23 entra na base(ver Tabela 3.18 e 3.20).
O novo limite inferior é dado por
Variável básica
−
55
12
1922
60
=
= 32, 03.
λ22
λ32
λ22
1
5
λ32
1
12
1
12
1
− 60
5
− 12
s3
s3
s4
2197
60
s4
1
λ11
λ21
λ31
−z
Coluna de entrada
Constantes
λ23
3
5
1
2
3
0
-5
1
λ12
1
λ21
− 15
λ31
−1
12
−1
12
−z
3
5
11
12
1
1
-5
-10
-28
1
8
0
188
15
0
1
0
2
5
0
1
3
0
2197
60
− 55
12
Tabela 3.19: Entra λ23 ,sai λ22 .
Variável básica
λ23
λ23
1
5
λ32
1
12
λ32
s4
λ21
λ31
−z
1
12
Constantes
2
3
1
1
− 60
λ11
3
5
s3
s4
s3
5
− 12
λ12
-5
8
188
15
1
1
λ21
− 51
λ31
−1
12
−1
12
−z
91
60
11
12
1
2
5
1
1
3
1
-5
-10
-28
1
−508
15
Problema Teste 2
77
Temos da Tabela 3.20 a seguinte solução para o problema proposto (3.251) - (3.262):
λ12 t12 = 1.(0, 5) =
(0, 5)
λ21 t21 =
2
5 .(8, 0, 2)
4
= ( 16
5 , 0, 5 )
λ23 t23 =
3
5 .(5, 0, 2)
= (3, 0, 65 )
λ31 t31 =
1
3 .(15, 13)
= (5, 13
3 )
λ32 t32 =
2
3 .(12, 5)
=
(3.358)
(8, 10
3 )
ou seja,
τ 1 = λ12 t12 = (0, 5)
τ 2 = λ21 t21 + λ23 t23 = ( 31
5 , 0, 2)
(3.359)
τ 3 = λ31 t31 + λ32 t32 = (13, 23
3 )
z=
508
15 .
ITERAÇÃO 3
11
De acordo com a Tabela 3.20, π = (− 23
12 , − 12 , 0, 0, 5, 10, 28). Segue-se:
31
min z1 = (c1 − π1 A1 )τ 1 = − t11 + t12
60
8
min z2 = (c2 − π2 A2 )τ 2 = t21 + t22 + t23
5
23
3
min z3 = (c3 − π3 A3 )τ = t31 + t32 .
12
Da mesma forma que na iteração anterior, cada subproblema está sujeito às mesmas restrições, fornecendo os seguintes resultados:
τ31 = (0, 5)
1 =0
y12
z10 = 5
2 = y 2 = 0; y 2 = 1 z 0 = 10
τ32 = (5, 0, 2) y12
13
23
2
τ33 = (12, 5)
3 =0
y12
(3.360)
z30 = 28
z10 − π01 = 5 − 5 = 0
(3.361)
z20 − π02 = 10 − 10 = 0
(3.362)
z30 − π03 = 28 − 28 = 0
(3.363)
Como z10 − π01 = z20 − π02 = z30 − π03 = 0 então não existem mais candidatas a entrar na
base. Logo, a solução corrente é ótima. Notemos que o limite inferior da solução ótima do problema
proposto (3.251)-(3.262) é o mesmo valor da solução corrente:
508
15
−0=
508
15
= 33, 86.
Problema Teste 2
78
Deste modo temos a seguinte solução ótima para o problema proposto (3.76)-(3.262):
λ12 t12 = 1.(0, 5) =
(0, 5)
λ21 t21 =
2
5 .(8, 0, 2)
4
= ( 16
5 , 0, 5 )
λ23 t23 =
3
5 .(5, 0, 2)
= (3, 0, 65 )
λ31 t31 =
1
3 .(15, 13)
= (5, 13
3 )
λ32 t32 =
2
3 .(12, 5)
=
(3.364)
(8, 10
3 )
23
3
3
3
ou seja, τ 1 = (0, 5), τ 2 = λ21 t21 + λ23 t23 = ( 31
5 , 0, 2) e τ = λ31 t + λ32 t2 = (13, 3 ).
23
Assim τ 0 = (t1 , t2 , t3 , t4 , t5 , t6 , t7 ) = (0, 31
5 , 13, 0, 5, 2, 3 ) e z =
508
15
é o valor ótimo e a solução
ótima.
Relembremos que a Tabela 3.21 mostra o limite inferior(LI) e o limite superior(LS) a cada
iteração, para a solução ótima do problema proposto(3.257)-(3.255) atualizando os limites das variáveis
a cada direção(ver algoritmo 3.1). Enquanto que a Tabela 3.22 indica o valor ótimo no caso do problema
original(3.251)-(3.255) sem os limites adotados, o valor ótimo para o problema (3.257)-(3.262) e o valor
ótimo encontrado ao aplicarmos o método de resolução de Dantzig-Wolfe incluindo os limites.
Iteração
LS
LI
1
53
29
2
36, 61
32, 03
3
32, 86
32, 86
Tabela 3.21: Limites por iteração do problema teste 2.
Valor ótimo sem limite
24
Valor ótimo com limite
53
Valor ótimo encontrado
32, 86
Tabela 3.22: Comparação das soluções do problema teste 2.
79
Valores da função objetivo ( Primal )
53
36,61
e dos limites inferiores
Progresso dos valores da função objetivo
Problema Teste 2
32,86
32,03
29
Limites inferiores ( Dual )
1
2
3
Iteração
Figura 3.3: Convergência do método do problema teste 2.
M1
P1
P2
M2
M3
0
10
~ S :
Solucao
1
´
C
max1
=10
33
tempo
M1
P1
P2
M2
M3
14
0
~ S :
Solucao
2
´
tempo
C
max2 = 14
M
1
P
M
2
P
M
3
1
2
10
Solucao S : C
=10
max
3
Figura 3.4: Diagrama de Gantt representando as soluções encontradas do problema teste 2.
Do mesmo modo que o Problema Teste 1, verificamos que a solução encontrada ao final do
método ainda não é a melhor solução para o problema de job-shop(3.251)-(3.255). Além disso, é
possı́vel verificar na Figura 3.3 a convergência do método e melhores valores para a função objetivo a
cada iteração. Observamos ainda os limitantes para o ótimo do problema proposto (3.257)-(3.262).
Analisando os valores expressos nas Tabelas 3.21 e 3.22 vemos que a solução ótima encontrada é um limitante inferior para o problema proposto (3.257)-(3.262) e um limitante superior para
o problema original (3.251)-(3.255). Além disso, notemos que neste caso conseguimos contornar a
infactibilidade através do ajuste no limite (3.313) por (3.316). Este fato mostra a importância em
determinar limites adequados que contornem a infactibilidade a fim de obtermos uma solução mais
Problema Teste 2
próxima do valor ótimo.
80
Conclusão
Neste trabalho abordamos o método de decomposição de Dantzig-Wolfe que propõe a decomposição de um problema linear de grande dimensão em subproblemas de dimensões menores e mais
fáceis de serem resolvidos, supervisionados por um problema coordenador.
Deste ponto de vista, como os problemas d seqüenciamento do tipo job-shop são problemas
combinatórios de grande dimensão e portanto, difı́ceis de serem resolvidos, podemos utilizar o Método
de Decomposição de Dantzig-Wolfe a fim de determinar a solução ótima, ou sub-ótima.
Sendo assim, propomos a decomposição de um particular problema de seqüenciamento do tipo
job-shop em k subproblemas independentes associados a cada máquina Mk , e formulamos o problema
coordenador considerando as restrições de precedência como de acoplamento. Tais considerações fazem
com que as variáveis das restrições de acoplamento, envolvidas em cada subproblema, limites sem
limites inferior e/ou superior. Isto acarreta em conjuntos de soluções ilimitadas. Além disso, pode
ocorrer que algumas soluções dos subproblemas não satisfaçam as restrições de precedências. Sendo
assim, sugerimos a criação de limites, que ajustados a cada iteração, garantem a limitação das regiões
viáveis de cada subproblema, a factibilidade do problema mestre e/ou subproblemas, e a obtenção de
soluções mais próximas do valor ótimo do problema original. Portanto, o problema proposto criado
a partir do problema original é diferenciado pelas restrições limitantes das variáveis envolvidas nas
restrições de acoplamento. Como tais limites são determinados baseados numa borda superior, a
região de soluções viáveis do problema original está contida na região do problema proposto. Em
conseqüência, a solução do problema proposto é um limitante superior para a solução do problema
original. Porém, quando aplicamos o método de Dantzig-Wolfe ao problema proposto e ajustamos os
limites das variáveis a cada iteração, a solução ótima converge para valores próximos à solução ótima
do problema original.
Este resultado é importante pois podemos utilizar a solução ótima obtida pelo Método de
Dantzig-Wolfe como um limitante superior para a solução do problema original. Este limitante é de
Conclusão
82
grande interesse no desenvolvimento de métodos por Separação e Avaliação,(Branch and Bound).
Tendo em vista que a proposta deste trabalho é viabilizar a aplicabilidade do método de
Dantzig-Wolfe em problemas de job-shop, os limites adotados têm importância fundamental. Assim, é
necessário a criação de procedimentos que determinem limites mais eficientes que forneçam um valor
ótimo do problema proposto mais próximo do ótimo do problema original. Além disso, como inicialmente os conjuntos de restrições dos subproblemas representam regiões ilimitadas, podemos aplicar
o método de Dantzig-Wolfe considerando as direções extremas do conjunto de soluções viáveis do
problema, modificando assim a formulação do problema mestre e os critérios de otimalidade. Estudos
mais aprofundados devem ser feitos de modo a determinar tais direções e garantir quais das mesmas
converge para o valor ótimo, ou uma melhor solução, do problema original.
Apêndice
Este anexo abordará conceitos e teoremas utilizados no decorrer deste trabalho, a fim de
proporcionar um melhor entendimento do mesmo.
A.1 Definição. Um conjunto X em E n (espaço vetorial de dimensão n) é chamado um se dado
qualquer dois pontos x1 e x2 em X, então λx1 + (1 − λ)x2 ∈ X, para cada λ ∈ [0, 1].
A.2 Definição. Qualquer ponto da forma λx1 + (1 − λ)x2 ∈ X para cada λ ∈ [0, 1] é chamada de
x1 e x2 .
Assim, a convexidade de X pode ser interpretada geometricamente como, a cada par de
pontos x1 e x2 em X o segmento de reta que os liga, ou a combinação convexa dos dois pontos, devem
pertencer a X.
A.3 Definição. Um ponto x em um conjunto convexo X é chamado de de X, se x não pode
ser representado como uma combinação convexa de dois pontos distintos em X, ou seja, se x =
λx1 + (1 − λ)x2 com λ ∈ (0, 1) e x1 , x2 ∈ X.
A.4 Definição. O raio é uma coleção de pontos da forma {x0 + λ · d; λ ≥ 0}, onde d é um vetor
não nulo. x0 é chamado o e d é a .
A.5 Definição. Em um conjunto convexo, um vetor não nulo d é chamado , se para cada x0 em
um conjunto, o raio x0 + λd; λ ≥ 0 também pertence ao conjunto. Deste modo, um conjunto limitado,
não possui direção.
Considerando o conjunto poliedral X = {x|Ax ≤ b, x ≥ 0}. Então um vetor não nulo d é
uma direção de X se, e somente se,
A(x + λd) ≤ b
x + λd ≥ 0,
Apêndice
84
para λ ≥ 0 e x ∈ X. Visto que x ∈ X, então Ax ≤ b e a primeira desigualdade acima vale para
um λ ≥ 0 arbitrariamente grande se, e somente se, Ad ≤ 0. Da mesma maneira, x + λd ≥ 0 é não
negativo para um λ ≥ 0 arbitrariamente grande se, e somente se,
d ≥ 0, d 6= 0 e Ad ≤ 0.
De forma similar, se X = {x|Ax = b, x ≥ 0} 6= ∅, ao vetor d é direção de X se, e somente se,
d ≥ 0, d 6= 0 e Ad = 0.
A mesma idéia de ponto extremo, se estende para , ou seja, uma direção de um conjunto
convexo é extrema , quando não pode ser representada como uma combinação positiva de duas direções
distintas do conjunto. Dois vetores, d1 e d2 , são ditos distintos se d1 não pode ser representado como
um múltiplo de d2 .
Já caracterizamos acima a direção de X como vetores d satisfazendo as condições
d ≥ 0, d 6= 0 e Ad ≤ 0.
Geometricamente, isto é chamado de sistema homogêneo, definindo um cone poliedral, também
conhecido como cone recessão, obtido pela translação dos hiperplanos definidos em X, de forma paralela a eles mesmo até passar sobre a origem. A fim de eliminar duplicações, essas direções deverão
ser normalizadas, de forma conveniente. Deste modo utilizaremos a norma |d1 | + · · · + |dn | = 1, nos
dando a nova restrição d1 + · · · + dn = 1, visto que d ≥ 0. Portanto, o conjunto
D = {Ad ≤ 0, 1d = 1, d ≥ 0},
caracteriza o conjunto de de X, onde 1 é um desses vetores. Assim, as direções extremas de X são
exatamente os pontos extremos de D.
A.6 Teorema. Seja X = {x : Ax ≤ 0, x ≥ 0} um conjunto (poliedral) não vazio. Então o conjunto
de pontos extremos é não vazio e tem um número finito de pontos, chamados x1 , x2 , · · · , xk . Além
disso, o conjuntos de direções extremas é vazio se, e somente se, X é limitado. Se X não é limitado,
então o conjunto de direções extremas é não vazio e tem um número finito de vetores, chamados
d1 , d2 , · · · , dl . Entretanto, x ∈ X se, e somente se, pode ser representado como uma combinação
convexa de x1 , x2 , · · · , xk [i.e., do conjunto de pontos extremos] mais uma combinação linear não
negativa de d1 , d2 , · · · , dl [i.e.,conjunto de direções extremas], ou seja,
Apêndice
85
x2
ou d 2
2
conjunto X
3
1
restrição de normalizacão
Conjunto D
2
3
x 1 ou d
1
1
Figura A.5: Direções e direções extremas
x =
k
X
j=1
k
X
λj xj +
l
X
µj dj
(A.365)
j=1
λj
= 1
(A.366)
λj
≥ 0, j = 1, 2, · · · , k
(A.367)
µj
≥ 0, j = 1, 2, · · · , l
(A.368)
j=1
Ver demonstração em [4]
[1] Adams J.; Balas E. et Zawack D. (1988)“ The shifting bottleneck procedure for the job-shop
scheduling ”, Management Science, vol.34, No.3, 391-401.
[2] Alves, Isamara C. (2000) “Application de la Technologie de Groupes et de la Relaxation Lagrangienne au Probléme D‘Ordennancement de Type Job-Shop”,Tese de Doutorado,Université
Blaise Pascal.
[3] Baker K. R. (1974)“Introduction to Sequencing and Scheduling ”, Wiley, New York.
[4] Bazaraa, Mokhtar S. (1990) Jarvis, John J. e Sherali, Hanif D. “Linear Programming and
Network Flows”: Woley.
[5] Benders J.F. (1962)“Partitioning procedures for solving mixed-variables programming problems”, Num. Math., vol.4 , 238-252.
[6] Bensana E. (1987)“ Utilisation de Techniques d’Intelligence Artificielle pour l’Ordonnancement
d’Atelier ”, Tese de Doutorado, Ecole Nationale Supérieure de l’Aéronautique et de l’Espace.
[7] Blazewicz J. et al. (1996)“Scheduling Computer Manufacturing Process”, Springer-Vertag,
Berlin.
[8] Caux C.; Pierreval H. e Portmann M.C. (1990)“ Les algorithmes génétiques et leur application aux problèmes d’ordonnancement ”, Journées d’étude “ Ordonnancement et entreprise
”, 5-45, 16-17/Juin, Toulouse.
[9] Carlier J.; Pinson E. (1987)“A branch and bound method for the job-shop problem”, Technical
Report Institut de Mathématiques Appliquées, Université de Angers.
[10] Dantzig e Wolfe, P. (1960) “The Decomposition Algorithm for Linear Programs”, Econometrica, vol.29, No.4, 767-778.
86
87
[11] Dell’Amico M. et Trubian M. (1993)“ Applying tabu-search to the job-shop scheduling problem ”, Annals of Operations Research, vol.41, 231-252.
[12] Falkenauer E. et Bouffouix S. (1991)“ A genetic algorithm for job-shop ”, IEEE International
Conference on Robotics and Automation, Sacramento, California.
[13] Fisher, M. L. (1973) “Optimal solution of scheduling problems using Lagrange multipliers:
parte I”, Oper. Res, Vol21,1114-1127.
[14] Fisher, M. L. (1973) “Optimal solution of scheduling problems using Lagrange multipliers: parte
II”, In: Syposum on the theory of scheduling and its Applications, Springer, Bertin, 294-318.
[15] Fisher, M.L.; Lageweg, B.J.; Lenstra, J.K.; Kan A.H.G.R. (1983) “Surrogate Duality
Relaxation for job shop scheduling”, Discrete Applied Mathematics. Vol.5,65-75.
[16] Garey; M.R.Johnson, D. S.; (1976) “The Complexity of Flowshop and jobshop scheduling”,
Mathematics of operation Research, vol.1, 117-129.
[17] Geoffrion A.M. (1970) “Elements of large-scale mathematical programming Part I ”, Management Science, vol.16 No.11, 652-675.
[18] Geoffrion, A.M.(1972)“Generalized Benders Decomposition”, Journal of Optimization Theory
and Applications, vol.10, No.4, 237-260.
[19] Geoffrion, A.M.(1974)“Lagrangean Relaxation For Interger Programming”, Mathematical
Programming Study.
[20] Glover F. (1989)“ Tabu search, part1”, ORSA Journal on Computing, vol.1, No.3, 190-260.
[21] Glover F. (1990)“ Tabu search, part2”, ORSA Journal on Computing, vol.2, No.1, 4-32.
[22] Hertz A. et Widmer M. (1994)“ La méthode tabou appliquée aux problèmes d’ordonnancement
”, Journées d’étude “ Ordonnancement et entre prise ”, 97-125, 16-17/Juin, Toulouse.
[23] Kirkpatrick S. (1984)“ Optimization by simulated annealing : Quantitative studies ”, Journal
of Statistical Physics, vol.34, No.5-6, 975-986.
[24] Kusiak A. (1989)“ Knowledge -based systems in manufacturing ”, Taylor & Francis, New York.
[25] Lemonias H. (1990)“Ordonnancement d’atelier à tâches, une approche par décomposition”,
Tese de Doctorado, IMAG-Grenoble.
[26] Lopez P. (1991)“ Approche énergétique pour l’ordonnancement de tâches sous contraintes de
temps et de ressources ”, Tese de Doutorado de l’Université Paul Sabatier, Toulouse.
88
[27] Lasdon L.S. (1970) “Optimization Theory for Large Systems”, McMillan Co..
[28] Tind J. (1998) “Decomposition Principle of Linear Programming”, University of Copenhagem,
Denmark.
[29] Thompson, Geral L.; Muth, John F. (1963) “Industrial scheduling”, Garnegie Institute of
Technology ,187-191.
[30] Panwalkar S.S. et Iskander W. (1977)“ A survey of scheduling rules ”, Operations Research,
vol.25, No.1, January-February, 45-61.
[31] Ramos, Alex D. (2002) “Método do subgradiente aplicado ao Job-Shop decomposto pela
Técnologia de Grupo e Relaxação Lagrangeana. Dissertação de Mestrado, Universidade Federal da Bahia
[32] Siarry P. (1994)“ La méthode du récuit simulé théorie et applications ”, Journées d’étude “
Ordonnancement et entreprise ”, 47-67, 16-17/Juin, Toulouse.
[33] Singer, M. (1999) “Decomposition methodos for large job shops”, Jornal Elsevier Science Ltda.
[34] Van Laarhoven P.J.M.; Aarts E.H.L. et Lenstra J.K. (1992)“ Job-shop scheduling by
simulated annealing ”, Operations Research, vol. 40, No.1, 113-126.
[35] Zwaneveld, C.M.; Van Wassenhove, L.N.;Strusevich, V.A.; Sevast Janov, S.V.;
Potts, C.N. (1995) “The two-stage assembly scheduling problem: Complexty and approximation”, Operation Research, vol.43, 1995.
Index
Algoritmo de Decomposição de Dantzig-Wolfe,
Branch and Bound, 34
10
da Relaxação Lagrangeana, 4
de Benders, 4
combinação convexa, 83
de Dantzig-Wolfe, 4
conjunto convexo, 83
de Rosen, 4
data
de separação e avaliação, 34
mais cedo, 28
heurı́stico, 34
mais tarde, 29
métodos
diagrama de Gantt, 32
exatos, 34
direção
heurı́sticos seriais, 34
de um conjunto, 83
ponto extremo, 83
do raio, 83
Problema
extrema, 84
de job-shop, 29
direções recessão, 84
Mestre, 7
elemento
Mestre Restrito, 12
pivô, 8
problema
coordenador, 3
fábricas
de flow-shop, 28
com máquinas especializadas, 29
de job-shop, 27
com uma única máquina, 29
de open-shop, 27
gama operatória, 28
escravo, 3
Grafo
mestre, 3
potencial-tarefa, 32
NP-difı́cil, 34
problema com uma máquina, 29
Interpretação econômica, 19
problemas
Limite inferior, 17
de fábrica, 27
makespan, 31
raio, 83
método
restrições
89
de localização no tempo, 27
de máquina, 33
de potencialidade, 27
de precedência, 33
de produto, 33
disjuntivas, 27, 33
do problema de job-shop, 30
dÏ sucessão, 27
subproblemas, 3
tecnologia de grupos, 36
vértice do raio, 83
90
Universidade Federal da Bahia-UFBa
Instituto de Matemática/Depto. de Matemática
Campus de Ondina, Av. Adhemar de Barros s/n, CEP:40170-110
www.im.ufba.br/hpinst/mestrado

Wolfe Aplicado ao Problema Combinatório de Job

Transcrição

Documentos relacionados

Oitavo e Nono Anos

Matemática Discreta 2011.1

1 Segunda Prova: EDO - Mecânica /Integral em 20/10/2015 C. A.

Gabarito - Profmat

Bases e soluç˜oes de equaç˜oes diferenciai

Ambiente de monitoramento para o Canal da Piracema

Equaçoes Diferenciais Parciais

2ª Eliminatória - Olimpíadas Portuguesas de Matemática

Polos Olímpicos de Treinamento Aula 1

Uma heurística híbrida para o problema de corte