Ваш I nteger Формулировка линейного программирования (ILP) не совсем верна, в своем последнем ограничении вы пишете, что во всех классах ровно 30 учеников, но это неверно,В классе не может быть более 30 учеников.
Таким образом, формулировка должна выглядеть примерно так:
развернуть ∑ ij x ij p ij
в зависимости от:
∑ j x ij = 1, ∀i
∑ i x ij ≤30, ∀j
Что касается максимального потока, вы можете представить каждого студентакак узел в сети, а каждый класс как узел, например, для четырех учеников и трех классов, график выглядит так:
Здесьвместимость с для студентов с i составляет 1 , поскольку каждый студент может сделать не более одного выбора, поэтому с (с, с i ) = 1 .Вместимость классной комнаты - 30, это означает, что для каждого класса c j , он считает, что c (c i , d)= 30 .Кроме того, емкость между s i и c j также равна 1 (хотя большая емкость не будет иметь значения),поэтому c (s i , c j ) = 1 .
Здесь мы добавляем " cost " ккрая между s i и c j , что равно a (s i ,c j ) = - p ij , поэтому, если предпочтение выше, стоимость ниже.Стоимость остальных ребер равна нулю, поэтому a (s, s i ) = a (c j , d) = 0 .Таким образом, здесь мы назначим потоки (на основе емкости по одному на каждого учащегося, так что общий поток в аудиторию составляет менее 30) и минимизируем стоимость, поэтому минимизируем сумму -p ij s.Если поток существует таким образом, что существует поток 1 из источника s каждому студенту s i , тогда мы можем дать каждому студенту выбор, иОбщая стоимость будет оптимизирована.