Блог

Я ищу решение проблемы линейного программирования, и мне нужно определить следующие ограничения:

 gji = 1 if guest j is seated at table i, 0 otherwise 
gki = 1 if guest k is seated at table i, 0 otherwise  
pjik = gij * gik = 1 if guest j AND guest k are seated at table i, 0 otherwise 
  

Я написал первые два costrains (используя библиотеку Pulp), но я не знаю, как представить умножение gji*gki

Мой код:

 Gji = LpVariable.matrix("Gji",(range(0,number_guest),range(0,number_table)),lowBound=0, upBound=1, cat='binary')

Gki = LpVariable.matrix("Gki",(range(0,number_guest),range(0,number_table)),lowBound=0, upBound=1, cat='binary')

for row in range (0,number_guest):
    prob  = lpSum(Gji[row])<=1
    prob  = lpSum(Gji[row])>=1

for columns in range (0,number_table):
    prob  = lpSum(np.matrix(Gji).T[columns].tolist()) <= a
  

Как я могу написать costrain для Pjki ?

Всегда сначала формулируйте правильную математическую модель, прежде чем внедрять ее в PuLp.

Пусть

 g(i,k) = 1 if guest i sits at table k
         0 otherwise
  

и

 p(i,j,k) = 1 if guests i and j sit at table k
           0 otherwise
  

Сначала вам нужны некоторые ограничения назначения:

 sum(i, g(i,k)) <= capacity(k)  for all k
sum(k, g(i,k)) = 1             for all i
  

Двоичное умножение

 p(i,j,k) = g(i,k) * g(j,k) 
  

может быть линеаризован как

 p(i,j,k) <= g(i,k)
p(i,j,k) <= g(j,k)
p(i,j,k) >= g(i,k) g(j,k)-1
p(i,j,k) ∈ {0,1}
  

Обычно нам не нужны все эти переменные и уравнения, но это зависит от деталей модели. Конечно, мы должны только рассмотреть i<j . Интересно, что эта формулировка настолько жесткая, что мы можем ослабить p (i, j, k), чтобы они были непрерывными между 0 и 1: они будут целыми числами автоматически.

Это математическое описание легко переводится на Python / Pulp. Вероятно, вам следует переделать свой код на Python, поскольку в нем есть некоторые бессмысленные вещи. Некоторые подсказки:

• двоичные переменные уже имеют границы 0 и 1
• Pulp может выполнять ограничения равенства (писать <= и >= ограничения глупо)
• постарайтесь сделать вещи более удобочитаемыми (ближе к математическому представлению)
• для другого подхода см.wedding.py