Ejercicio 2

Use el algoritmo de Programacion Lineal para determinar la ruta más corta entre el nodo 1 y todos los demás nodos en la red (Nodo 1 al 5)

\(X_ij=1\), si se relaciona co el arco \(ij\)

\(X_ij=0\), en caso contrario

\(S.a.r:\) Flujo que sale es igual a Flujo que sale.

\(X_ij=[0,1]\)

Matriz de Distancias

1 2 3 4 5
1 M 5 1 M M
2 M M M 7 1
3 M 2 M 6 7
4 M M 7 M M
5 M M M 3 M 
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)
library(dplyr)
m=1000
c=matrix(c(m,5,1,m,m,m,m,m,7,1,m,2,m,6,7,m,m,7,m,m,m,m,m,3,m),nrow = 5,byrow =TRUE)
m=1000
c=matrix(c(m,5,1,m,m,m,m,m,7,1,m,2,m,6,7,m,m,7,m,m,m,m,m,3,m),nrow = 5,byrow =TRUE)
modelo_md=MIPModel()%>%
  add_variable(x[i,j],i=1:5,j=1:5,type = "binary")%>%
  set_objective(sum_expr(c[i,j]*x[i,j],i=1:5,j=1:5),sense = "min")%>%
  add_constraint(x[1,2]+x[1,3]==1)%>%
  add_constraint(x[1,2]+x[3,2]-x[2,4]-x[2,5]==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]==0)%>%
  add_constraint(x[2,5]+x[3,5]-x[5,4]==1)
solucion=solve_model(modelo_md,with_ROI(solver = "glpk",verbose=TRUE))
## <SOLVER MSG>  ----
## GLPK Simplex Optimizer, v4.47
## 5 rows, 25 columns, 18 non-zeros
##       0: obj =  0.000000000e+000  infeas = 2.000e+000 (5)
## *     2: obj =  6.000000000e+000  infeas = 0.000e+000 (4)
## *     5: obj =  4.000000000e+000  infeas = 0.000e+000 (2)
## OPTIMAL SOLUTION FOUND
## GLPK Integer Optimizer, v4.47
## 5 rows, 25 columns, 18 non-zeros
## 25 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] 4
get_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     1

Se obtiene una solucion entera optima para el problema, la solucion al modelo son los arcos con los cuales se debe de desplazar para recorrer una minima distancia. En este caso se obtiene que se deben de recorrer 4 (millas) con los siguientes arcos [3,2],[1,3],[2,5] con los acules solo recorreriamos 4 (unidades).