Задача линейного программирования: минимизировать количество используемых грузовиков

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

Нам нужно перевезти n разных товаров с завода на склад. Каждое произведение имеет свой вес (элемент i имеет вес wi‹W). Мы используем грузовики с максимальной грузоподъемностью W, цель состоит в том, чтобы свести к минимуму количество используемых грузовиков.

Я пробовал по-другому, но у меня всегда возникают проблемы с моделированием количества грузовиков в целевой функции.

Я использовал переменную Yij, которая равна 1, если грузовик i перевозит элемент j, и 0 в противном случае, и мне удалось записать различные ограничения. Но я не могу найти, как подсчитать количество грузовиков, используемых с этой переменной.

Если у кого-то есть какие-либо предложения, это было бы очень полезно.

Спасибо


integer linear-programming cplex opl
person Johnn1xy    schedule 02.01.2021    source источник
comment
Добро пожаловать @Johnn1xy. Добавление вашей формулировки к вопросу поможет внести ясность и показать вам, что следует изменить.   -  person abc    schedule 02.01.2021

Ответы (1)


arrow_upward
0
arrow_downward

Предполагая, что Yij представляет собой rectangular matrix of size (m=items, n=trucks) полный двоичных переменных, таких как:

truck    0    1   2
item 0   x00  x   x
item 1   x10  x   x
item 2   x20  x   x
item 3   x30  x   x

вы можете создать дополнительные бинарные переменные t_used_0 (показаны только для truck_0), например:

sum(Yij_column_0) <= m * t_used_0

    <-> x00 + x10 + x20 + x30 <= 4 * t_used_0

sum(Yij_column_0) >= t_used_0

    <-> x00 + x10 + x20 + x30 >= t_used_0

Затем у вас есть n вспомогательные двоичные переменные t_used_i, которые вы можете суммировать в своей цели.

(В этих линеаризациях существует много степеней свободы (например, эквивалентность или только импликация), что отчасти объясняет, почему пользователь abc запросил дополнительную информацию. В общем, вы используете все возможный.)

person sascha    schedule 02.01.2021