glpk (gusek) 中线性问题的两个变量的乘法

Question

我正在尝试解决一个分配问题。在我的目标函数中尝试在线性规划（使用 glpk gusek）中乘以两个变量时遇到以下问题：

minimize PATH_COST: sum{k in Rodzaj_Transportu}(sum{z in numery_Zlecen}Koszty_Suma[k,z])*y[k,z]; #y is a binary variable; Koszty_Suma is total cost for ordez z and car type k

出现以下错误："model.mod:47: multiplication of linear forms not allowed"。

代码（.dat 文件）：

data;

set numery_Zlecen := 1, 2, 3; #order numbers

set Miasta := '*some data: *' #cities.

#order numer (from city to city)
set Zlecenie[1] := Warszawa Paris;
set Zlecenie[2] := Berlin Praha;
set Zlecenie[3] := Praha Amsterdam;

#number of packages for transport for a particular order
param Ilosc_Wyrobow := 
1 10
2 50
3 110;

param Godziny_Pracy := 9; #number of working hours during the day
param Pojemnosc_Samochodu := 35; #capacity of the car (how many packages it can take)
param Srednia_Predkosc := 80; #average car speed
param Spalenie_Paliwa := 0.25; #fuel combustion
param Wynagrodzenie_za_Godzine := 20; #salary for one working hour
param Cena_Noclegu := 100; #price of accommodation

param Dystans: '*some data: *' #km between cities.
param Koszt_Paliwa : '*some data: *' #fuel consumption depends on country.
end;

代码（.mod 文件）：

#INDEXY
#=====================================================================
set Miasta;                 #i,j
set numery_Zlecen;              #z
set Zlecenie{numery_Zlecen} dimen 2;    #p,q
set Rodzaj_Transportu;          #k

#PARAMETRY
#=====================================================================
param Dystans {Miasta,Miasta};
param Ilosc_Wyrobow{numery_Zlecen}; 
param Godziny_Pracy >= 0;
param Pojemnosc_Samochodu {Rodzaj_Transportu}>= 0;
param Srednia_Predkosc >=0;
param Spalenie_Paliwa >=0;
param Koszt_Paliwa {Miasta,Miasta};
param Wynagrodzenie_za_Godzine >= 0;
param Cena_Noclegu >= 0;

#ZMIENE
#=====================================================================
var x{Miasta,Miasta,numery_Zlecen} <= 1, >= 0; #variable x equal 1 when we're going the path from city A to city B; otherwise it equals 0
var y{Rodzaj_Transportu,numery_Zlecen} binary <=1, >=0; #variable that shows what types of car/s we are using for order (can be 0 or 1)
var Koszty_Suma{Rodzaj_Transportu,numery_Zlecen}; #total costs
var Koszty_Transportu{numery_Zlecen}; #transport costs
var Koszty_Odpoczynku{numery_Zlecen}; #rest costs
var Koszty_Wynagrodzenia{numery_Zlecen}; #salary costs

#FUNKCjA CELU
#=====================================================================
minimize PATH_COST: sum{k in Rodzaj_Transportu}(sum{z in numery_Zlecen}Koszty_Suma[k,z])*y[k,z];

#OGRANICZENIA (constraints)
#=====================================================================
s.t. SOURCE{z in numery_Zlecen, (p,q) in Zlecenie[z], i in Miasta: i = p && p != q}:
sum {j in Miasta} (x[i ,j ,z ]) - sum {j in Miasta}( x[j ,i ,z ]) = 1;

s.t. INTERNAL {z in numery_Zlecen, (p,q) in Zlecenie[z],i in Miasta: i != p && i != q && p != q }:
sum {j in Miasta} (x[i ,j ,z ]) - sum {j in Miasta}( x[j ,i ,z ]) = 0;

s.t. OGR_KM_DZIEN{z in numery_Zlecen,(p,q) in Zlecenie[z], j in Miasta, i in Miasta: i != q}:
if (Dystans[i,j] > (Godziny_Pracy*Srednia_Predkosc)) and i != q then x[i,j,z] = 0;

s.t. OGR_KOSZTY_SUMA{z in numery_Zlecen, k in Rodzaj_Transportu}:
Koszty_Suma[k,z] = (Koszty_Transportu[z] + Koszty_Odpoczynku[z] + Koszty_Wynagrodzenia[z])*ceil(Ilosc_Wyrobow[z]/Pojemnosc_Samochodu[k]);

s.t. OGR_KOSZTY_TRANSPORTU{z in numery_Zlecen}:
Koszty_Transportu[z] = (sum{i in Miasta} (sum{j in Miasta} ( Dystans[i,j]*x[i,j, z]*Koszt_Paliwa[i,j] ) ))*Spalenie_Paliwa;

s.t. OGR_KOSZTY_ODPOCZYNKU{z in numery_Zlecen}:
Koszty_Odpoczynku[z] =
(sum{i in Miasta} (sum{j in Miasta} ( Dystans[i,j]*x[i,j, z] ) ))/(Godziny_Pracy*Srednia_Predkosc) * Cena_Noclegu;

s.t. OGR_KOSZTY_WYNAGRODZENIA{z in numery_Zlecen}:
Koszty_Wynagrodzenia[z] = 
((sum{i in Miasta} (sum{j in Miasta} ( Dystans[i,j]*x[i,j, z] ) ))/(Srednia_Predkosc)) * Wynagrodzenie_za_Godzine; 

s.t. OGR_Y_JEDEN{z in numery_Zlecen}:
sum{k in Rodzaj_Transportu}(y[k,z]) = 1;
solve;

如何消除这个错误？欢迎任何解决此类问题的提示。

Answer 1

首先我认为括号不正确（注意 y[k,z] 取决于 z）。表达式

  sum{k in Rodzaj_Transportu}(sum{z in numery_Zlecen}Koszty_Suma[k,z])*y[k,z];

在数学上不正确。所以，我假设你的意思是：

sum{k in Rodzaj_Transportu}(sum{z in numery_Zlecen}Koszty_Suma[k,z]*y[k,z]);

让我稍微重申一下这个问题。我假设我们可以这样写：

sum((i,j), x[i,j]*y[i,j])

其中 y 是一个二进制变量，x 是一个连续变量。我也假设 0 <= x[i,j] <= U[i,j]。（U 是上限）。

这里是线性化这个二次项的方法。我们可以使用以下不等式引入变量 z[i,j]=x[i,j]*y[i,j]：

 z[i,j] <= U[i,j]*y[i,j] 
 z[i,j] <= x[i,j]
 z[i,j] >= x[i,j]-U[i,j]*(1-y[i,j])
 0 <= z[i,j] <= U[i,j]

现在您可以 minimize sum((i,j),z[i,j])。对于类似的线性化，请参见 link。

glpk (gusek) 中线性问题的两个变量的乘法

Multiplication of two variables for linear problems in glpk (gusek)

linear-programming

glpk