Arbol de Mínima Expansión (Eliminación de subciclos)

4. En la figura 6.8 se ven las distancias, en millas, de las conexiones factibles que unen nueve pozos marinos de gas natural con un punto de entrega en tierra. Como la ubicación del pozo 1 es la más cercana a la costa, tiene capacidad de bombeo y de almacenamiento suficiente para bombear la producción de los ocho pozos restantes hasta el punto de entrega. Determine la red mínima de tubería que una las bocas de pozo con el punto de entrega.

Red para el problema 4

Remodelación del diagrama

Modelo 02

Matríz de distancias

Matrix

Con los datos obtenidos en nuestra modelado, se procederá a resolver nuestro ejercicio en R.
library(ROI)
## ROI: R Optimization Infrastructure
## Registered solver plugins: nlminb, glpk.
## Default solver: auto.
library(ROI.plugin.glpk)
library(ompr)
## Warning: package 'ompr' was built under R version 4.1.1
library(ompr.roi)
## Warning: package 'ompr.roi' was built under R version 4.1.1
library(dplyr)
## Warning: package 'dplyr' was built under R version 4.1.1
## 
## Attaching package: 'dplyr'
## The following objects are masked from 'package:stats':
## 
##     filter, lag
## The following objects are masked from 'package:base':
## 
##     intersect, setdiff, setequal, union
m=100
dd=matrix(c(m,5,9,20,4,m,m,14,15,
            5,m,6,m,m,m,m,m,m,
            9,6,m,15,10,m,m,m,m,
            20,m,15,m,20,7,12,m,m,
            4,m,10,20,m,3,5,13,6,
            m,m,m,7,3,m,m,m,m,
            m,m,m,12,5,m,m,7,m,
            14,m,m,m,13,m,7,m,5,
            15,m,m,m,6,m,m,5,m),nrow = 9,byrow = TRUE)
colnames(dd)=(c("1","2","3","4","5","6","7","8","9"))
rownames(dd)=(c("1","2","3","4","5","6","7","8","9"))
modelo_dmst2=MIPModel()%>%
  add_variable(x[i,j],i=1:9,j=1:9,type = "binary")%>%
  add_variable(u[i], i = 1:nrow(dd), lb = 1, ub = nrow(dd)) %>%
  set_objective(sum_expr(dd[i,j]*x[i,j],i=1:9,j=1:9),sense = "min")%>%
  add_constraint(sum_expr(x[i,j],i=2:9,j=1:9)==nrow(dd)-1)%>%
  add_constraint(u[i] >= 2, i = 2:nrow(dd)) %>% 
  add_constraint(u[i] - u[j] + 1 <= (nrow(dd) - 1) * (1 - x[i,j]), i = 2:nrow(dd), j = 2:nrow(dd))
solucion_dmst2=solve_model(modelo_dmst2,with_ROI(solver = "glpk",verbose=TRUE))
## <SOLVER MSG>  ----
## GLPK Simplex Optimizer, v4.47
## 73 rows, 90 columns, 256 non-zeros
##       0: obj =  0.000000000e+000  infeas = 1.600e+001 (1)
## *    16: obj =  2.670000000e+002  infeas = 0.000e+000 (1)
## *    29: obj =  3.625000000e+001  infeas = 0.000e+000 (0)
## OPTIMAL SOLUTION FOUND
## GLPK Integer Optimizer, v4.47
## 73 rows, 90 columns, 256 non-zeros
## 81 integer variables, all of which are binary
## Integer optimization begins...
## +    29: mip =     not found yet >=              -inf        (1; 0)
## +    85: >>>>>  4.100000000e+001 >=  3.700000000e+001   9.8% (20; 1)
## +  1429: mip =  4.100000000e+001 >=     tree is empty   0.0% (0; 627)
## INTEGER OPTIMAL SOLUTION FOUND
## <!SOLVER MSG> ----
solucion_dmst2$objective_value
## [1] 41
get_solution(solucion_dmst2,x[i,j])%>%filter(value>0)
##   variable i j value
## 1        x 2 1     1
## 2        x 5 1     1
## 3        x 3 2     1
## 4        x 6 4     1
## 5        x 7 5     1
## 6        x 9 5     1
## 7        x 5 6     1
## 8        x 9 8     1

Resultados obtenidos en R

Con los resultados obtenidos en R studio podemos analizar las variables obtenidas y de esta forma sugerir el modelo correspondiente para nuestro problema como se muestra a continuación:

sugerencia del modelo