Aplicación del Problema de la Ruta más Segura

La figura 6.13 muestra la red de comunicaciones entre dos estaciones, 1 y 7. La probabilidad de que un enlace de la red funcione sin fallar se ve en cada arco. Los mensajes se mandan de la estación 1 a la estación 7, y el objetivo es determinar la ruta que maximice la probabilidad de una buena transmisión.

Figura 6.13

MODELACIÓN:

MM

Matriz de distancia

Restricciones

Con los resultados obtenidos, vamos a implementar en R para poder determinar la ruta más optima.

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
p=matrix(c(m,-0.223,-1.204,-0.431,m,m,m,m,m,m,-0.105,-0.693,m,m,m,m,m,m,m,-0.051,m,m,m,-0.163,m,-0.357,-0.511,m,m,m,m,m,m,-0.693,-0.223,m,m,m,m,m,m,-0.105,m,m,m,m,m,m,m),nrow = 7, byrow = TRUE)
modelo_rs=MIPModel()%>%
  add_variable(x[i,j],i=1:7,j=1:7,type = "binary")%>%
  set_objective(sum_expr(p[i,j]*x[i,j],i=1:7,j=1:7),sense = "max")%>%
  add_constraint(x[1,2]+x[1,3]+x[1,4]==1)%>%
  add_constraint(x[1,2]-x[2,4]-x[2,5]==0)%>%
  add_constraint(x[1,3]+x[4,3]-x[3,6]==0)%>%
  add_constraint(x[1,4]+x[2,4]-x[4,3]-x[4,5]-x[4,6]==0)%>%
  add_constraint(x[2,5]+x[4,5]-x[5,6]-x[5,7]==0)%>%
  add_constraint(x[3,6]+x[4,6]+x[5,6]-x[6,7]==0)%>%
  add_constraint(x[5,7]+x[6,7]==1)
solucion_rs=solve_model(modelo_rs,with_ROI(solver = "glpk",verbose=TRUE))
## <SOLVER MSG>  ----
## GLPK Simplex Optimizer, v4.47
## 7 rows, 49 columns, 24 non-zeros
##       0: obj =  0.000000000e+000  infeas = 2.000e+000 (7)
## *     5: obj = -1.139000000e+000  infeas = 0.000e+000 (3)
## *    11: obj = -6.470000000e-001  infeas = 0.000e+000 (1)
## OPTIMAL SOLUTION FOUND
## GLPK Integer Optimizer, v4.47
## 7 rows, 49 columns, 24 non-zeros
## 49 integer variables, all of which are binary
## Integer optimization begins...
## +    11: mip =     not found yet <=              +inf        (1; 0)
## +    11: >>>>> -6.470000000e-001 <= -6.470000000e-001   0.0% (1; 0)
## +    11: mip = -6.470000000e-001 <=     tree is empty   0.0% (0; 1)
## INTEGER OPTIMAL SOLUTION FOUND
## <!SOLVER MSG> ----
solucion_rs$objective_value
## [1] -0.647
get_solution(solucion_rs,x[i,j])%>%filter(value>0)%>%arrange(j)
##   variable i j value
## 1        x 1 2     1
## 2        x 4 3     1
## 3        x 2 4     1
## 4        x 3 6     1
## 5        x 6 7     1
get_solution(solucion_rs,x[i,j])%>%filter(value>0)%>%arrange(i)
##   variable i j value
## 1        x 1 2     1
## 2        x 2 4     1
## 3        x 3 6     1
## 4        x 4 3     1
## 5        x 6 7     1

A continuación se va analizar la comprobación de nuestros resultados obtenidos en R

Analisis de comprobación