Relatório atividade REO3

Prévia do material em texto

Roteiro de estudos Orientados: Parte 1
1Departamento de Automática, Universidade Federal de Lavras, C.P. 3037, 37200-000, Lavras, MG, Brasil.
1Engenharia de Controle e Automação, Universidade Federal de Lavras, C.P. 3037, 37200-000, Lavras, MG, Brasil.
26 de Junho de 2020
A seguir será apresentada a resolução concernente ao REO 3 da disciplina Otimização de Sistemas ofertada pelo prof. Leonardo Paiva. Para resolução da atividade, dois passos foram executados: modelagem do problema, solução através da programação do software LINDO.
1 – Como primeiro passo para desenvolver uma resolução de um problema de otimização, devemos modelar o problema. Diferente dos unilaterais, isto é, só tem um sentido de locomoção entre dois nós, esse, por sua vez, trata-se de um problema em que o sentido de entre dois pode ser assumir ida e volta. Para solução, vamos seguir alguns passos:
1. O problema tem a finalidade de minimizar a duração total das viagens, uma vez que Ivete, juntamente com seu trio elétrico, deve percorrer todos os pontos determinados. 
2. Para isso, a variável de decisão do problema será do tipo binário: se o trio elétrico vai do nó i para o nó j. Caso seja igual à 0, então aquele trajeto não foi selecionado. Por outro lado, se for igual à 1, foi selecionado.
3. Como dizemos no enunciado, para dois nós, o trajeto de ida e volta podem ser selecionados. Por exemplo, Ivete pode ir do nó 1 ao 2, como pode sair do 2 e chegar no 1. Com isso em mente, a função objetivo deve levar em consideração esses dois sentidos e é dada pela soma ponderada de cada trajeto, a saber:
a. Minimizar (F.O) TT = 34x12 + 47x13 + 67x14 + 48x15 + 34x21 + 17x23 + 34x24 + 23x25 + 47x31 + 17x32 + 26x34 + 34x35 + 67x41 + 34x42 + 26x43 + 31x45 + 48x51 + 23x52 + 34x53 + 31x54
4. Como o trio deve comtemplar todas as cidades, deve sair de um ponto e chegar no outro. Para garantir que trio realize somente um trajeto por vez, devemos pensar em uma restrição. Por exemplo, caso esteja no nó 1, ele pode ir para o 2, ou 3, ou 4, ou 5. Para esse caso tem-se: 
a. x12 + x13 + x14 + x15 = 1
b. Pensando nisso, caso ele esteja em qualquer um das outras cidades, tem-se mais as seguintes restrições:
i. x21 + x23 + x24 + x25 = 1
ii. x31 + x32 + x34 + x35 = 1
iii. x41 + x42 + x43 + x45 = 1
iv. x51 + x52 + x53 + x54 = 1
5. No passo 4, analisamos o caso em que o trio está em uma dada posição e queremos saber qual será a próxima. No entanto, caso esteja na cidade i, qual seria o destino anterior? Por exemplo, caso esteja na cidade 1, sua posição anterior poderia ser uma das outras 4 cidades. Assim, a restrição para esse exemplo seria: x21 + x31 + x41 + x51 = 1. Fazendo essa análise para todas as outras cidades, tem-se as restantes restrições:
i. x12 + x32 + x42 + x52 = 1
ii. x13 + x23 + x43 + x53 = 1 
iii. x14 + x24 + x34 + x54 = 1 
iv. x15 + x25 + x35 + x45 = 1 
6. Para o outro conjunto de restrições, analisamos que, como o objetivo é percorrer todas as cidades em menor tempo possível, um trajeto onde um caminho cíclico é realizado, não resulta em uma boa tomada de decisão, sendo assim: . Isso indica que caso saísse do nó i para o nó j, o trajeto de j para i não será executado. Semelhante para o outro caso, ou seja, caso saia de j para i, i para j não será realizado. Se nenhum for realizado, a desiguldade permanece. Segue então o bloco de restrições referente a essa parte:
i. x12 + x21 <= 1
ii. x13 + x31 <= 1
iii. x14 + x41 <= 1
iv. x15 + x51 <= 1
v. x23 + x32 <= 1
vi. x24 + x42 <= 1
vii. x34 + x43 <= 1
viii. x35 + x53 <= 1
ix. x45 + x54 <= 1
7. De maneira similar ao passo 6, devemos eliminar as sub-rotas com três nós. Não é conveniente que o trio circule entre três nós e volte a posição inicial se ainda tem pontos a serem passados. Sendo assim, caso o trio saia do ponto i, vá para um ponto j, de j vá para um ponto k, deste ponto não pode voltar para o ponto i. Logo, se xij foi selecionado e depois xjk, xki não pode ser selecionada, então:
a. - visto que as variáveis são binárias e para este bloco de restrições referente às eliminações de sub-rotas com três caminhos, somente dois trajetos podem ser executados. Por isso o menor igual à 2. 
b. As restrições são dadas por:
c. x12 + x23 + x31 <= 2
d. x12 + x24 + x41 <= 2
e. x12 + x25 + x51 <= 2
f. x13 + x32 + x21 <= 2
g. x13 + x34 + x41 <= 2
h. x13 + x35 + x51 <= 2
i. x14 + x42 + x21 <= 2
j. x14 + x43 + x41 <= 2
k. x14 + x45 + x51 <= 2
l. x15 + x52 + x21 <= 2
m. x15 + x53 + x31 <= 2
n. x15 + x54 + x41 <= 2
o. x21 + x13 + x32 <= 2
p. x21 + x14 + x42 <= 2
q. x21 + x15 + x52 <= 2
r. x23 + x31 + x12 <= 2
s. x23 + x34 + x42 <= 2
t. x23 + x35 + x52 <= 2
u. x24 + x41 + x12 <= 2
v. x24 + x43 + x32 <= 2
w. x24 + x45 + x52 <= 2
x. x25 + x51 + x12 <= 2
y. x25 + x53 + x32 <= 2
z. x25 + x54 + x42 <= 2
aa. x31 + x12 + x23 <= 2
ab. x31 + x14 + x43 <= 2
ac. x31 + x15 + x53 <= 2
ad. x32 + x21 + x13 <= 2
ae. x32 + x24 + x43 <= 2
af. x32 + x25 + x53 <= 2
ag. x34 + x41 + x13 <= 2
ah. x34 + x42 + x23 <= 2
ai. x34 + x45 + x53 <= 2
aj. x35 + x51 + x13 <= 2
ak. x35 + x52 + x23 <= 2
al. x35 + x54 + x43 <= 2
am. x41 + x12 + x24 <= 2
an. x41 + x13 + x34 <= 2
ao. x41 + x15 + x54 <= 2
ap. x42 + x21 + x14 <= 2
aq. x42 + x23 + x34 <= 2
ar. x42 + x25 + x54 <= 2
as. x43 + x31 + x14 <= 2
at. x43 + x32 + x24 <= 2
au. x43 + x35 + x54 <= 2
av. x45 + x51 + x14 <= 2
aw. x45 + x52 + x24 <= 2
ax. x45 + x53 + x34 <= 2
ay. x51 + x12 + x25 <= 2
az. x51 + x13 + x35 <= 2
ba. x51 + x14 + x45 <= 2
bb. x52 + x21 + x15 <= 2
bc. x52 + x23 + x35 <= 2
bd. x52 + x24 + x45 <= 2
be. x53 + x31 + x15 <= 2
bf. x53 + x32 + x25 <= 2
bg. x53 + x34 + x45 <= 2
bh. x54 + x41 + x15 <= 2
bi. x54 + x42 + x25 <= 2
bj. x54 + x43 + x35 <= 2
8. Por fim, inserindo todos estes dados no LINDO, tem-se:
 
A descrição INT indica que as variávies são do tipo binárias.
Como resultado, tem-se:
Como conlusão, temos que os trajetos selecionados são:
· X15 : indo da cidade 1 para a 5;
· X21: indo da cidade 2 para 1;
· X32 : indo da cidade 3 para 2;
· X43: indo da cidade 4 para a 3;
· X54: indo da cidade 5 para a 4;
Gerando um tempo de trajeto igual à 156 min.