Arbol de Mínima Expansión

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 con flechas de salida

Modelo 02

Variables de decisión para nuestro ejercicio

Variables en uso

Matríz de distancias

Matrix

Modelo Matemático del ejercicio

—————————————–

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
d=matrix(c(m,5,9,20,4,m,m,14,15,
           m,m,6,m,m,m,m,m,m,
           m,m,m,15,10,m,m,m,m,
           m,m,m,m,20,7,12,m,m,
           m,m,m,m,m,3,5,13,6,
           m,m,m,m,m,m,m,m,m,
           m,m,m,m,m,m,m,7,m,
           m,m,m,m,m,m,m,m,5,
           m,m,m,m,m,m,m,m,m),nrow = 9, byrow = TRUE)

modelo_mst=MIPModel()%>%
  add_variable(x[i,j],i=1:9,j=1:9,type = "binary")%>%
  set_objective(sum_expr(d[i,j]*x[i,j],i=1:9,j=1:9), sense = "min")%>%
  add_constraint(sum_expr(x[i,j],i=1:9,j=1:9)==8)

solucion_mst=solve_model(modelo_mst,with_ROI(solver = "glpk",verbose=TRUE))
## <SOLVER MSG>  ----
## GLPK Simplex Optimizer, v4.47
## 1 row, 81 columns, 81 non-zeros
##       0: obj =  0.000000000e+000  infeas = 8.000e+000 (1)
## *     8: obj =  8.000000000e+002  infeas = 0.000e+000 (1)
## *    24: obj =  4.100000000e+001  infeas = 0.000e+000 (0)
## OPTIMAL SOLUTION FOUND
## GLPK Integer Optimizer, v4.47
## 1 row, 81 columns, 81 non-zeros
## 81 integer variables, all of which are binary
## Integer optimization begins...
## +    24: mip =     not found yet >=              -inf        (1; 0)
## +    24: >>>>>  4.100000000e+001 >=  4.100000000e+001   0.0% (1; 0)
## +    24: mip =  4.100000000e+001 >=     tree is empty   0.0% (0; 1)
## INTEGER OPTIMAL SOLUTION FOUND
## <!SOLVER MSG> ----
solucion_mst$objective_value
## [1] 41
get_solution(solucion_mst,x[i,j])%>%filter(value>0)
##   variable i j value
## 1        x 1 2     1
## 2        x 2 3     1
## 3        x 1 5     1
## 4        x 4 6     1
## 5        x 5 6     1
## 6        x 5 7     1
## 7        x 5 9     1
## 8        x 8 9     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

Y finalmente con nuestro nuevo modelo se realiza el nuevo diagrama enlazando la red.

Nuevo modelo