C:\JUAN\POST\MARKDOWN
Traballo 4 de Programación Lineal - PFCM
2020-01-21
Propón o enunciado dun problema de fluxo máximo que involucre 11 nodos, definindo a rede cos arcos e capacidades correspondentes.
No ano 2230 d.C. atópase por primeira vez vida complexa en planetas non moi afastados da Terra. Desde ese momento, o oficio de astrobiólogo gaña pulo, xa que eses planetas son ricos en biodiversidade cun gran potencial de explotación como recurso, polo que novos investigadores se aventuran nos salvaxes exoplanetas á procura dun descubrimento que os faga ricos e famosos ao volver á casa.
Nunha destas viaxes de investigación e aventura, un grupo de astrobiólogos bolseiros da USC descobre un ser vivo semellante a un vexetal terrestre que capta moléculas dispersas no aire mediante unha «antena» e leva a cabo un complexo proceso dixestivo a través de nove «nódulos gástricos», que acaban enviando ás raíces uns zumes complexos extremadamente nutritivos e purificados.
Os investigadores da USC comprobaron experimentalmente o valor nutricional destes zumes e calculan que poderían facerse ricos vendendo suplementos alimenticios se fosen capaces de optimizar o proceso, xa que este ser parece utilizar de forma endóxena parte dos fluídos na produción doutras estruturas, como pugas defensivas, pétalos ou sementes, que non terían interese comercial.
Tras unha longa deliberación, un deses biólogos —que cursara a materia de Programación Lineal e Enteira da USC— propuxo, moi sagazmente, que se podería realizar un proceso de selección artificial para mellorar a especie (bautizada provisionalmente como Linae programatta), seleccionando só os exemplares que enviasen directamente á raíz unha maior produción deste zume, onde sería fácil recollela cun simple vial. Para iso sería moi útil predicir que ramas son as principais responsables da chegada neta de fluxo á raíz e forzar artificialmente a desaparición das menos importantes. Deste xeito aforraríanse centos de ensaios fallidos, tempo e diñeiro no proceso de cruzamento.
«Isto, en termos de programación lineal…» —pensou o astro-bio-estatístico— «…non deixa de ser un problema de fluxo de redes a custo mínimo. Se obtemos o grafo da vascularización deste ser a partir dos datos que temos do seu sistema vascular, saberemos como optimizar os fluxos, que arestas sobran, e poderemos seleccionar os exemplares que máis se acheguen ás características desexadas ata que, tras unhas cantas iteracións, a produción de zume extraíble directamente pola raíz alcance o seu óptimo.»
«Imos facernos ricos, e todo grazas á Programación Lineal!» —berraron todos.
«E eu o que máis! Que son o único que sabe programar este problema en R!» —berrou o astro-bio-estatístico, contento de ter cursado o seu Mestrado en Estatística nos seus anos mozos.
E así resolveu o problema de optimizar o fluxo de zumes gástricos nutritivos cara á raíz en Linae programatta:
[Nota: as medidas de capacidade están expresadas en mililitros de zume gástrico por hora (ml/h)]
Grafo correspondente: definición en R dos nodos, arestas e as súas cotas e custos asociados.
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
- Cos seguintes arcos e capacidades de fluxo asociados:
aristas
Escribe o modelo de programación lineal para o problema proposto, explicando o significado das variables, a función obxectivo e as restricións.
En linguaxe matemática, o modelo de programación lineal proposto pódese definir do seguinte xeito:
Sexa $G=(N,M)$ un grafo orientado con nodos $N=({A,1,…,9,R})$ e arcos $M=(a_{1},…,a_{15})$. Este grafo poderá representarse como unha matriz de incidencia $\overline{B}{n* m}$, en cuxas coordenadas se asignará un $1$ se $i$ é o nodo inicial do arco $a{k}$, $-1$ se $i$ é o nodo terminal de $a_{k}$ e $0$ noutro caso. Esta matriz créase como obxecto en R no seguinte apartado; non obstante, inclúoa aquí como matriz para efectos de visualización, coas arestas no eixe X e os nodos no Y:
Ademais, cada arco $k$ terá asociados tres parámetros: unha cota inferior (fluxo mínimo no arco $k$), unha cota superior (fluxo máximo no arco $k$) e un custo (positivo para custos de fluxo e negativo para beneficios).
$$ \begin{pmatrix} Cota Inferior & l_{k} \geq 0 \ Cota Superior & u_{k} \geq 0\ Coste & c_{k}\ \end{pmatrix} $$
Coa matriz de incidencia podemos formular correctamente o problema como unha función que minimizar (maximizar no noso caso, pero será cuestión de facer a inversa do resultado e listo) e unha serie de restricións.
- En primeiro lugar, definimos as variables, que serán as diferentes arestas sobre as que 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 función obxectivo e as súas restricións:
$\quad$$\quad$ Min $\quad$$\quad$ $-i_{A}$
Suxeito 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 con R.
- Xa temos o problema de optimización PFCM deseñado graficamente (como se pode ver na Figura 1) e listo para resolverse con R. Procedemos entón a resolver o problema mediante lpSolverAPI, definindo antes a matriz de incidencia, a función obxectivo que maximizar, as restricións… e demais.
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 de lpSolverAPI indícanos que existe unha solución óptima para o problema indicado.
A solución óptima implica un fluxo de 8 ml/h de zume gástrico a través da raíz, como indica o valor da función que se vai optimizar.
Finalmente, lpSolveAPI indícanos as arestas (conexións entre nódulos) que terían un fluxo nulo no óptimo. Son a aresta 7ª (nodos 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 sen fluxo cara á raíz —e que, polo tanto, son obxectivo dos esforzos de selección artificial dos astrobotánicos— son:
A aresta 7ª, que unía dous nodos intermedios, probablemente cunha función estrutural, non será necesaria no invernadoiro, polo que é unha candidata perfecta para optimizar o fluxo.
As arestas 10ª e 13ª sostiñan pugas defensivas que tampouco serán necesarias nun ambiente sen depredadores, polo que son outras dúas candidatas perfectas para optimizar o fluxo.
O resultado do grafo de exemplo que deben seguir os astrobotánicos nos seus cultivos para optimizar a extracción de zumes mediante selección artificial pode verse representado na Figura 2.
Resolve o problema con AMPL.
Os astrobiólogos teñen conexión a internet durante un par de horas ao mes por cortesía da Xunta, polo que aproveitan o tempo para, ademais de programar o problema PFCM en R, facelo tamén en AMPL e resolvelo na nube con Gurobi. Para iso presentan os seguintes documentos de texto:
- flujo.dat cos datos:
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 co 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 cos comandos e as saídas desexadas:
#Ejemplo del problema del flujo máximo
solve;
display Traf, Entrada_Traf;
$\$
- Tras unhas horas de espera, obteñen o seguinte resultado de optimización 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 óptimo é o mesmo: debe chegar a $8ml/h$, e nisto coinciden ambos os modelos.
– Non obstante, AMPL propón certas arestas novas como potencialmente eliminables no proceso de optimización:
$(3 - 6)$: Esta aresta non fora proposta previamente e, aínda que parece central no desenvolvemento de Linae programatta pola súa posición anatómica, tamén parece ser un colo de botella no fluxo de zumes gástricos, polo que se debería intentar seleccionar as variedades que teñan máis capacidade nesta aresta ou, se iso non é posible, quizais eliminala.
$(4 - 5)$: Esta aresta xa fora proposta anteriormente. Como é unha espiña, é só un sumidoiro inútil de zumes gástricos. Debe optimizarse.
$(8 - 7)$: Esta aresta xa fora proposta anteriormente. Como é unha espiña, é só un sumidoiro inútil de zumes gástricos. Debe optimizarse.
$(A - 3)$: Esta aresta tamén é nova e, aínda que parece central na anatomía de Linae programatta, unha análise máis próxima indica que ten un fluxo moi reducido, probablemente só para soster pétalos e sépalos e formar sementes. Esta aresta tamén podería optimizarse mediante cruzamento.
CONCLUSIÓN:
Grazas á formulación deste problema como un problema de Programación Lineal para optimizar un fluxo, os astrobiólogos teñen agora moito máis clara a anatomía e a fisioloxía vascular de Linae programatta. Grazas a iso, poderán realizar cruzamentos e seleccionar artificialmente a proxenie que máis se achegue ao cumprimento destes estándares establecidos con R e/ou AMPL (véxase a Figura 4), ata estabilizar a especie cunhas características beneficiosas que permitan explotala como recurso comercial.
(…)
Meses despois, os invernadoiros de campaña e os cruzamentos deron o seu froito, e os astrobiólogos —liderados polo astro-bio-estatístico— volven á casa con variedades seleccionadas de Linae programatta, preparados para ampliar a produción e, se se fan tan ricos como desexan, crear unha cátedra de optimización espacial na Facultade de Matemáticas da USC.
