Invstigación de Operaciones II
Omar Jhondely Méndez Juárez
21/10/2021
PROBLEMA DE LA RUTA DE MÍNIMA DISTANCIA
La ruta más corta
Use el algoritmo de Dijkstra para determinar la ruta más corta entre el nodo 1 al 5
>>>Diagrama
Solución
-En primer lugar se va realizar el modelo matemático nombrando nuestras variables a escoger, en este caso nuestras variables son i,j.
>>>Modelo matemático
-Despues mendiante una restricción, definimos que nuestras variables van a ser binarias. 
-Por consiguiente se procede a realizar la matriz de Distancia de nuestro ejercicio: 
-Y por ultimo se realiza el sistema de restricciones nodo por nodo. 
#### Con los resultados obtenidos, vamos a implementar en R para poder determinar la ruta más corta.
#------------Adquisicion de librerias------------#
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.1library(ompr.roi)## Warning: package 'ompr.roi' was built under R version 4.1.1library(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#------------Modelacion------------#
m=1000
c=matrix(c(m,5,1,m,m,m,m,m,m,m,7,1,6,m,m,2,m,6,7,m,m,m,m,7,m,m,4,6,m,m,m,3,m,5,9,m,7,m,m,m,m,2,m,m,m,m,m,m,m),nrow = 7,byrow =TRUE)
modelo_md=MIPModel()%>%
add_variable(x[i,j],i=1:7,j=1:7,type = "binary")%>%
set_objective(sum_expr(c[i,j]*x[i,j],i=1:7,j=1:7),sense = "min")%>%
add_constraint(x[1,2]+x[1,3]==1)%>%
add_constraint(x[1,2]+x[3,2]+x[6,2]-x[2,4]-x[2,5]-x[2,6]==0)%>%
add_constraint(x[1,3]+x[4,3]-x[3,2]-x[3,4]-x[3,5]==0)%>%
add_constraint(x[2,4]+x[3,4]+x[5,4]-x[4,3]-x[4,6]-x[4,7]==0)%>%
add_constraint(x[2,5]+x[3,5]-x[5,4]-x[5,6]-x[5,7]==1)%>%
add_constraint(x[2,6]+x[4,6]+x[5,6]-x[6,2]-x[6,7]==0)%>%
add_constraint(x[4,7]+x[5,7]+x[6,7]==0)
#------------solucion del ejercicio------------#
solucion=solve_model(modelo_md,with_ROI(solver = "glpk",verbose=TRUE))## <SOLVER MSG> ----
## GLPK Simplex Optimizer, v4.47
## 7 rows, 49 columns, 32 non-zeros
## 0: obj = 0.000000000e+000 infeas = 2.000e+000 (7)
## * 2: obj = 6.000000000e+000 infeas = 0.000e+000 (6)
## * 5: obj = 4.000000000e+000 infeas = 0.000e+000 (4)
## OPTIMAL SOLUTION FOUND
## GLPK Integer Optimizer, v4.47
## 7 rows, 49 columns, 32 non-zeros
## 49 integer variables, all of which are binary
## Integer optimization begins...
## + 5: mip = not found yet >= -inf (1; 0)
## + 5: >>>>> 4.000000000e+000 >= 4.000000000e+000 0.0% (1; 0)
## + 5: mip = 4.000000000e+000 >= tree is empty 0.0% (0; 1)
## INTEGER OPTIMAL SOLUTION FOUND
## <!SOLVER MSG> ----solucion$objective_value## [1] 4get_solution(solucion,x[i,j])## variable i j value
## 1 x 1 1 0
## 2 x 2 1 0
## 3 x 3 1 0
## 4 x 4 1 0
## 5 x 5 1 0
## 6 x 6 1 0
## 7 x 7 1 0
## 8 x 1 2 0
## 9 x 2 2 0
## 10 x 3 2 1
## 11 x 4 2 0
## 12 x 5 2 0
## 13 x 6 2 0
## 14 x 7 2 0
## 15 x 1 3 1
## 16 x 2 3 0
## 17 x 3 3 0
## 18 x 4 3 0
## 19 x 5 3 0
## 20 x 6 3 0
## 21 x 7 3 0
## 22 x 1 4 0
## 23 x 2 4 0
## 24 x 3 4 0
## 25 x 4 4 0
## 26 x 5 4 0
## 27 x 6 4 0
## 28 x 7 4 0
## 29 x 1 5 0
## 30 x 2 5 1
## 31 x 3 5 0
## 32 x 4 5 0
## 33 x 5 5 0
## 34 x 6 5 0
## 35 x 7 5 0
## 36 x 1 6 0
## 37 x 2 6 0
## 38 x 3 6 0
## 39 x 4 6 0
## 40 x 5 6 0
## 41 x 6 6 0
## 42 x 7 6 0
## 43 x 1 7 0
## 44 x 2 7 0
## 45 x 3 7 0
## 46 x 4 7 0
## 47 x 5 7 0
## 48 x 6 7 0
## 49 x 7 7 0get_solution(solucion,x[i,j])%>%filter(value>0)%>%arrange(j)## variable i j value
## 1 x 3 2 1
## 2 x 1 3 1
## 3 x 2 5 1get_solution(solucion,x[i,j])%>%filter(value>0)%>%arrange(i)## variable i j value
## 1 x 1 3 1
## 2 x 2 5 1
## 3 x 3 2 1