GLPK:没有原始可行的解决方案

Question

我正在尝试解决 GLPK 中的问题，但它给了我这个消息"问题没有原始可行的解决方案"。您将在下面找到该程序。给我错误的约束是"约束 6"，但我不知道如何修复它。TNX为您提供帮助

param n, integer ; # nbr noeuds
param l, integer ; # Number of periods
param m, integer ; # nbr vehicle
set N := 0..n ; # set of nodes (plans & customers)
set Nc := 1..n ;
set T := 0..l ; # set of periods
set K := 1..m ; # vehicles
set A := {i in N, j in N : i!=j}; #Set of Arcs
# paramètres 
param u ; # unit produc. cost
param f ; # fixed produc. cost
param h{i in N},integer, >=0 ; # Holding cost
param c {i in N, j in N},integer, >=0 ; # Transportation cost
param C ; # Production capacity
param Q ; # Vehicle capacity
param L {i in N},integer, >=0 ; #Maximum or target inventory level at node i
param I0 {i in N},integer, >=0 ; # initial inventory at node i period 0
param d{i in N, t in T},integer, >=0  ; # demand
param M{t in T} := min( C, sum {j in T, i in Nc:j>=t } d[i,j] );
param Mx{i in Nc, t in T} := min( L[i], Q, sum {j in T:j>=t } d[i,j] );
# variables 
var p{t in T}, >=0, integer ; # production qty 
var q{i in N, t in T}, >=0, integer ; # qty delivered
var y{t in T}, binary ;# Setup for period t (1 if there is production at 
var x{i in N, j in N, t in T}, binary; # 1 if a vehicle travels directly from node i to j, 0 otherwise
var I{i in N, t in T}, integer, >=0 ;   # Inventory at node i, period t
var z0{t in T}, integer, >=0; # the number of vehicles leaving the plant in period t
var z {i in Nc, t in T}, binary;  # 1 if customer i is visited in t, 0 otherwise
var w {i in N, t in T}, integer, >=0  ;#load of vehicle before making a delivery
# fonction objectif: mimiser les coûts
minimize cost: sum{t in T:t>0} ( u*p[t]+ f*y[t] +(sum{i in N} h[i]*I[i,t] )+ 
(sum{ (i,j) in A} c[i,j]*x[i,j,t] )) ;

s.t. RInit{i in N}       : I0[i] = 0 ;
# Constraint (2)
s.t. R1{t in T:t>0}:I[0, t-1]+p[t]=sum{i in Nc}q[i,t]+I[0,t];
# Constraint (3)
s.t. R2{i in Nc, t in T:t>0} : I[i,t-1] + q[i,t] = d[i,t] + I[i,t] ;
# Constraint (4)
s.t. R3{t in T:t>0} : p[t] <= M[t]*y[t] ;
# Constraint (5)
s.t.R4{t in T:t>0} : I[0,t] <= L[0];
# Constraint (6)
s.t. R5{i in Nc, t in T:t>0} : I[i,t-1]+q[i,t] <= L[i];
# Constraint (7)
s.t. R6{i in Nc, t in T:t>0} : q[i,t] <= Mx[i,t]*z[i,t];
# Constraint (8)
s.t. R7{ i in Nc ,t in T:t>0}: (sum{j in N} x[j,i,t])=z[i,t];
# Constraint (9)
s.t. R8{i in N, t in T: t>0 and i>0} :sum{j in N}x[j,i,t]+sum{j in N} x[i,j,t]= 2*z[i,t];
# Constraint (10)
s.t. R9{t in T: t>0}: z0[t]<= m;
#Constraint (11)
s.t. R10{ t in T,(i,j) in A: t>0 and i>0}: w[i,t]-w[j,t]>=q[i,t]-Mx[i,t]*(1-x[i,j,t]);
#Constraint (12)
s.t. R11{i in Nc, t in T: t>0}:0 <= w[i,t] ;
s.t. R12{i in Nc, t in T: t>0}: w[i,t] <= Q*z[i,t];
#Constraint (13)
s.t. R13{i in N, t in T:t>0}: p[t] >=0;
s.t. R14{i in N, t in T:t>0} : I[i,t] >=0; 
s.t. R15{i in N, t in T:t>0} : q[i,t] >=0;
solve ;
printf "nnTotal cost:%fn", cost ;
display Mx ;
display M ;
data;
param n := 3;
param l := 6 ;
param m := 1 ;
param u := 1 ;
param f := 10 ;
param C := 4;
param Q := 5;
param d : 0 1 2 3 4 5 6 :=
          0  0 0 0 0 0 0 0
          1  0 5 6 7 8 9 10
          2  0 6 7 8 9 10 11 
          3  0 6 7 8 9 10 12 ;
param c : 0 1 2 3  :=
   0  0 0 0 0 
   1  5 6 7 8 
   2  6 7 8 9 
   3  6 7 8 9  ;
param h  :=
   0  4
   1  5
   2  6
   3  6  ;
param I0  :=
   0  0
   1  0
   2  0
   3  0  ;
param L  :=
   0  0
   1  1
   2  2
   3  3  ;
end ;

Answer 1

我认为问题出在您的参数化上。

在约束 3 中：

s.t. R2{i in Nc, t in T:t>0} : I[i,t-1] + q[i,t] = d[i,t] + I[i,t];

您设置 I+q 等于参数 d 加上某些东西。D 在 5 到 12 的范围内，所有变量均为正数。

在约束 6 中：

s.t. R5{i in Nc, t in T:t>0} : I[i,t-1]+q[i,t] <= L[i];

您将相同的 I+q 限制为小于参数 L，该参数的范围仅为 1 到 3。所以 I+q 必须大于 d （5） 且小于 L （1），这是不可行的。