C:\JUAN\POST\MARKDOWN
Trabalho 4 de Programação Linear - PFCM
2020-01-21
Propõe o enunciado de um problema de fluxo máximo que envolva 11 nós, definindo a rede com os arcos e capacidades correspondentes.
No ano 2230 d.C., encontra-se pela primeira vez vida complexa em planetas não muito distantes da Terra. A partir desse momento, a profissão de astrobiólogo ganha impulso, pois esses planetas são ricos em biodiversidade com grande potencial de exploração como recurso, pelo que jovens investigadores se aventuram nos exoplanetas selvagens em busca de uma descoberta que os torne ricos e famosos quando regressarem a casa.
Numa destas viagens de investigação e aventura, um grupo de astrobiólogos bolseiros da USC descobre um ser vivo semelhante a uma planta terrestre que capta moléculas dispersas no ar através de uma «antena» e realiza um complexo processo digestivo através de nove «nódulos gástricos», que acabam por enviar às raízes sucos complexos extremamente nutritivos e purificados.
Os investigadores da USC comprovaram experimentalmente o valor nutricional destes sucos e calculam que poderiam enriquecer com a venda de suplementos alimentares se fossem capazes de otimizar o processo, pois este ser parece utilizar de forma endógena parte dos fluidos na produção de outras estruturas, como espinhos defensivos, pétalas ou sementes, que não teriam interesse comercial.
Após uma longa deliberação, um desses biólogos —que tinha frequentado a disciplina de Programação Linear e Inteira da USC— propôs, com grande sagacidade, que se poderia realizar um processo de seleção artificial para melhorar a espécie (provisoriamente batizada de Linae programatta), selecionando apenas os exemplares que enviassem diretamente para a raiz uma maior produção deste suco, onde seria fácil recolhê-lo com um simples frasco. Para isso, seria muito útil prever quais os ramos principalmente responsáveis pela chegada líquida de fluxo à raiz e forçar artificialmente o desaparecimento dos menos importantes. Desta forma, poupar-se-iam centenas de ensaios falhados, tempo e dinheiro no processo de cruzamento.
«Isto, em termos de programação linear…» —pensou o astro-bio-estatístico— «…não deixa de ser um problema de Fluxo de Redes de Custo Mínimo. Se obtivermos o grafo da vascularização deste ser a partir dos dados que temos do seu sistema vascular, saberemos como otimizar os fluxos, quais as arestas supérfluas, e poderemos selecionar os exemplares que mais se aproximem das características desejadas até que, após algumas iterações, a produção de suco extraível diretamente pela raiz atinja o seu ótimo.»
«Vamos ficar ricos, e tudo graças à Programação Linear!» —gritaram todos.
«E eu mais do que todos! Sou o único que sabe programar este problema em R!» —gritou o astro-bio-estatístico, feliz por ter concluído o seu Mestrado em Estatística quando era jovem.
E assim resolveu o problema de otimizar o fluxo de sucos gástricos nutritivos em direção à raiz de Linae programatta:
[Nota: as medidas de capacidade são expressas em mililitros de suco gástrico por hora (ml/h)]
Grafo correspondente: definição em R dos nós, arestas e respetivos limites e custos associados.
library('igraph')
nodes <- c("A", "1", "2", "3", "4", "5", "6", "7", "8", "9", "R")
# A=Antena Filtradora
# R=Raiz
# 1-9: Nódulos Gástricos
# coordenadas en X, Y y color de los nodos
x <- c(3,1,5,2,4,5,3,1,2,3,3)
y <- c(1,2,2,3,3,3,4,4,5,6,7)
color <- c("red", rep("lightblue", 9), "gold")
nodos <- data.frame(nodes, x ,y, color)
# direccion aristas
from <- c('A','A','A','A','1','2','3','4','3','4','6','6','8', '8','9')
to <- c('1','3','4','2','3','4','4','5','6','6','9','8','7', '9','R')
capacity <- c( 5, 1, 1, 5, 5, 5, 3, 6, 5, 10, 2, 6 , 2, 15, 20)
aristas <- data.frame(from, to, capacity)
grafo <- graph_from_data_frame(vertices = nodos, d = aristas, directed = T)
E(grafo)$label <- c(
"(0,5,0)",
"(0,1,0)",
"(0,1,0)",
"(0,5,0)",
"(0,5,0)",
"(0,5,0)",
"(0,3,0)",
"(0,6,0)",
"(0,5,0)",
"(0,10,0)",
"(0,2,0)",
"(0,6,0)",
"(0,2,0)",
"(0,15,0)",
"(0,20,0)")
tkplot(grafo)
# se usa tkPlot grafo para poder hacer edición de la apariencia a posteriori,
# se incluye a continuación la imagen corregida
- Com os seguintes arcos e capacidades de fluxo associados:
aristas
Escreve o modelo de programação linear para o problema proposto, explicando o significado das variáveis, a função objetivo e as restrições.
Em linguagem matemática, o modelo de programação linear proposto pode ser definido da seguinte forma:
Seja $G=(N,M)$ um grafo orientado com nós $N=({A,1,…,9,R})$ e arcos $M=(a_{1},…,a_{15})$. Este grafo poderá ser representado como uma matriz de incidência $\overline{B}{n* m}$, em cujas coordenadas será atribuído $1$ se $i$ for o nó inicial do arco $a{k}$, $-1$ se $i$ for o nó terminal de $a_{k}$ e $0$ nos restantes casos. Esta matriz é criada como objeto em R na secção seguinte; no entanto, incluo-a aqui como matriz para efeitos de visualização, com as arestas no eixo X e os nós no Y:
Além disso, cada arco $k$ terá três parâmetros associados: um limite inferior (fluxo mínimo no arco $k$), um limite superior (fluxo máximo no arco $k$) e um custo (positivo para custos de fluxo e negativo para benefícios).
$$ \begin{pmatrix} Cota Inferior & l_{k} \geq 0 \ Cota Superior & u_{k} \geq 0\ Coste & c_{k}\ \end{pmatrix} $$
Com a matriz de incidência podemos formular corretamente o problema como uma função a minimizar (maximizar no nosso caso, mas será apenas uma questão de inverter o resultado) e um conjunto de restrições.
- Em primeiro lugar, definimos as variáveis, que serão as diferentes arestas sobre as quais calculamos o fluxo:
$$ \begin{pmatrix} Variable & Arista \ i_{1} & 1ª \ i_{2} & 2ª \ (…) & (…) \ i_{15} & 15ª \ i_{A} & Auxiliar \ \end{pmatrix} $$
- E agora definimos a função objetivo e as suas restrições:
$\quad$$\quad$ Min $\quad$$\quad$ $-i_{A}$
Sujeito a:
$\quad$$\quad$$\quad$$\quad$ $i_{1}$$+i_{2}$$+i_{4}$$+i_{5}-i_{16}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{1}$$+i_{3}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{2}$$+i_{6}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{3}$$-i_{4}$$+i_{7}$$+i_{8}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{5}$$-i_{6}$$-i_{7}$$+i_{9}+i_{10}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{10}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{8}$$-i_{9}$$+i_{11}$$+i_{12}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{13}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{12}$$+i_{13}$$+i_{14}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{11}$$-i_{14}$$=$$0$
$\quad$$\quad$$\quad$$\quad$ $-i_{15}$$+i_{16}$$=$$0$
$\$
Resolve o problema com R.
- Já temos o problema de otimização PFCM concebido graficamente (como se pode ver na Figura 1) e pronto para ser resolvido com R. Procedemos então à resolução do problema através do lpSolverAPI, definindo primeiro a matriz de incidência, a função objetivo a maximizar, as restrições… e assim por diante.
library(lpSolveAPI)
nodos <- 11
arcos <- 16 # 15 más el arco auxiliar
# matriz de incidencia
B <- matrix(0, nrow = nodos, ncol = arcos)
# nodos iniciales
B[1, 1] <- 1
B[1, 2] <- 1
B[1, 4] <- 1
B[1, 5] <- 1
B[2, 3] <- 1
B[3, 6] <- 1
B[4, 7] <- 1
B[4, 8] <- 1
B[5, 9] <- 1
B[5, 10] <- 1
B[7, 11] <- 1
B[7, 12] <- 1
B[9, 13] <- 1
B[9, 14] <- 1
B[10, 15] <- 1
B[11, 16] <- 1
# nodos terminales
B[2, 1] <- -1
B[3, 2] <- -1
B[4, 3] <- -1
B[4, 4] <- -1
B[5, 5:7] <- -1
B[6, 10] <- -1
B[7, 8:9] <- -1
B[9, 12] <- -1
B[8, 13] <- -1
B[10, 11] <- -1
B[10, 14] <- -1
B[11, 15] <- -1
B[1,16] <- -1
B
write.table(B, "./B.txt", sep=";")
# costes
costes <- rep(0, arcos)
costes[16] <- c(-1)
costes
# cotas inferiores
L <- rep(0, arcos)
# cotas superiores
U <- rep(1e30, arcos)
U[1:(arcos-1)] <- c(5,5,5,1,1,5,3,5,10,6,2,6,2,15,20)
U
# resolvemos el problema asociado
n_restricciones <- nrow(B)
n_variables <- ncol(B)
PFCM <- make.lp(nrow = n_restricciones, ncol = n_variables)
# matriz de restricciones
for (i in 1:n_restricciones){
set.row(PFCM, i, B[i, ])
}
set.objfn(PFCM, costes)
b <- rep(0, n_restricciones)
set.rhs(PFCM, b)
tipores <- rep("=", n_restricciones)
set.constr.type(PFCM, tipores)
set.bounds(PFCM, upper = U)
set.bounds(PFCM, lower = L)
PFCM
val <- solve(PFCM)
val
obj<-get.objective(PFCM)
obj
vars<-get.variables(PFCM)
vars
A saída do lpSolverAPI indica-nos que existe uma solução ótima para o problema apresentado.
A solução ótima implica um fluxo de 8 ml/h de suco gástrico através da raiz, conforme indicado pelo valor da função a otimizar.
Por fim, o lpSolveAPI indica-nos as arestas (ligações entre nódulos) que teriam fluxo nulo no ótimo. São a 7.ª aresta (nós 3-4), a 10.ª (4-5) e a 13.ª (8-7).
# cambiamos el color de los vértices (azul) que maximizan el flujo
vcol <- rep("gray", 14)
vars.n <- vars[-15]
vcol[vars.n != 0] <- "green"
E(grafo)$color = vcol
tkplot(grafo)
O grafo obtido indica que as arestas sem fluxo em direção à raiz —e que são, portanto, alvo dos esforços de seleção artificial dos astrobotânicos— são:
A 7.ª aresta, que ligava dois nós intermédios, provavelmente com uma função estrutural, não será necessária na estufa, sendo uma candidata perfeita para otimizar o fluxo.
As 10.ª e 13.ª arestas sustentavam espinhos defensivos que também não serão necessários num ambiente sem predadores, sendo outras duas candidatas perfeitas para otimizar o fluxo.
O resultado do grafo de exemplo que os astrobotânicos devem seguir nas suas culturas para otimizar a extração de sucos por seleção artificial pode ser visto na Figura 2.
Resolve o problema com AMPL.
Os astrobiólogos têm ligação à internet durante algumas horas por mês, cortesia da Xunta, pelo que aproveitam o tempo para, além de programarem o problema PFCM em R, o fazerem também em AMPL e resolvê-lo na nuvem com Gurobi. Para isso, apresentam os seguintes documentos de texto:
- flujo.dat com os dados:
set INTER := A 1 2 3 4 5 6 7 8 9 R ;
param entr := A ;
param sali := R ;
param: CAMI: capa :=
A 1 5, A 2 5, A 3 1, A 4 1,
1 3 5,
2 4 5,
3 4 3, 3 6 5,
4 5 6, 4 6 10,
6 9 2, 6 8 6,
8 7 2, 8 9 15,
9 R 20;
- flujo.mod com o modelo proposto:
set INTER; # intersecciones
param entr symbolic in INTER; # entrada a la red
param sali symbolic in INTER, <> entr; # salida de la red
set CAMI within (INTER diff {sali}) cross (INTER diff {entr});
param capa {CAMI} >= 0; # capacidades de caminos
var Traf {(i,j) in CAMI} integer, <= capa[i,j], >=0; # tráfico
maximize Entrada_Traf: sum {(entr,j) in CAMI} Traf[entr,j];
subject to Equilibrio {k in INTER diff {entr,sali}}: sum {(i,k) in CAMI} Traf[i,k] = sum {(k,j) in CAMI} Traf[k,j];
- flujo.run com os comandos e resultados pretendidos:
#Ejemplo del problema del flujo máximo
solve;
display Traf, Entrada_Traf;
$\$
- Após algumas horas de espera, obtêm o seguinte resultado de otimização do fluxo:
Gurobi 8.1.0: optimal solution; objective 8 Traf := 1 3 2 2 4 5 3 4 2 3 6 0 4 5 0 4 6 8 6 8 6 6 9 2 8 7 0 8 9 6 9 R 8 A 1 2 A 2 5 A 3 0 A 4 1 ;
Entrada_Traf = 8
– O resultado de fluxo ótimo é o mesmo: deve atingir $8ml/h$, e ambos os modelos concordam quanto a isso.
– No entanto, o AMPL propõe algumas arestas novas como potencialmente elimináveis no processo de otimização:
$(3 - 6)$: Esta aresta não tinha sido proposta anteriormente e, embora pareça central no desenvolvimento de Linae programatta pela sua posição anatómica, também parece ser um estrangulamento no fluxo de sucos gástricos, pelo que se deveria tentar selecionar variedades com maior capacidade nesta aresta ou, se isso não for possível, talvez eliminá-la.
$(4 - 5)$: Esta aresta já tinha sido proposta anteriormente. Como é um espinho, é apenas um sumidouro inútil de sucos gástricos. Deve ser otimizada.
$(8 - 7)$: Esta aresta já tinha sido proposta anteriormente. Como é um espinho, é apenas um sumidouro inútil de sucos gástricos. Deve ser otimizada.
$(A - 3)$: Esta aresta também é nova e, embora pareça central na anatomia de Linae programatta, uma análise mais próxima indica que tem um fluxo muito reduzido, provavelmente apenas para sustentar pétalas e sépalas e formar sementes. Esta aresta também poderia ser otimizada através de cruzamento.
CONCLUSÃO:
Graças à formulação deste problema como um problema de Programação Linear para a otimização de um fluxo, os astrobiólogos têm agora muito mais clara a anatomia e a fisiologia vascular de Linae programatta. Graças a isso, poderão realizar cruzamentos e selecionar artificialmente a descendência que mais se aproxime do cumprimento destes padrões estabelecidos com R e/ou AMPL (ver Figura 4), até estabilizar a espécie com características benéficas que permitam explorá-la como recurso comercial.
(…)
Meses depois, as estufas de campanha e os cruzamentos deram frutos, e os astrobiólogos —liderados pelo astro-bio-estatístico— regressam a casa com variedades selecionadas de Linae programatta, prontos para aumentar a produção e, se ficarem tão ricos quanto desejam, criar uma cátedra de otimização espacial na Faculdade de Matemática da USC.
