Фокс-Коза-Капуста Транспорт
Мой вопрос касается старой транспортной проблемы - перевозить три предмета через реку на лодке, способной перевезти только один предмет за раз. Ограничение состоит в том, что некоторые предметы нельзя оставлять вместе, например, капусту с козой, волка с козлом и т. Д. Эту проблему следует решить с помощью целочисленного программирования или другого подхода к оптимизации. Функция стоимости - это все элементы, находящиеся на другой стороне реки, и поездки, необходимые для их получения, могут быть выходными данными Simplex (?), Который пробует различные возможные решения. Мне было интересно, есть ли у кого-нибудь целочисленное программирование (или линейное программирование) формулировка этой проблемы, и / или Matlab, Octave, Python-код, который может предложить решение программно, включая трассировку Simplex, пробующую все пути - наши поездки на лодке,
Здесь были интересные вещи
http://www.zib.de/Publications/Reports/SC-95-27.pdf
Спасибо,
2 ответа
Я рекомендую использовать бинарные переменные x_i, t для моделирования позиций ваших предметов, то есть они равны нулю, если предмет находится на левом берегу после поездки t, и одну - в противном случае. Максимум одна из этих переменных может измениться во время поездки. Это может быть смоделировано
x_wolf,1 + x_cabbage,1 + x_goat,1 <= 1 + x_wolf,0 + x_cabbage,0 + x_goat,0 и
x_wolf, 1> = x_wolf, 0
x_cabbage, 1> = x_cabbage, 0
x_goat, 1> = x_goat, 0
Аналогичные ограничения требуются для поездок в другом направлении.
Кроме того, после нечетного числа поездок вам нужно ограничиться проверкой предметов на левом берегу, а также вы должны проверить правый берег. Например:
x_wolf, 1 + x_goat, 1> = 0 и
x_wolf,2 + x_goat,2 <= 1 ...
Используйте верхнюю границу для t, так что решение наверняка возможно.
Наконец, введите двоичную переменную z_t и пусть
z_t <= 1/3 (x_wolf,t + x_cabbage,t + x_goat,t)
и максимизировать sum_t (z_t).
(Скорее всего, работают также sum_t (x_wolf,t + x_cabbage,t + x_goat,t).)
Вы правы, что эта формулировка потребует целочисленных переменных. Традиционный способ решения такой проблемы состоит в том, чтобы сформулировать модель двоичной переменной и передать ее в решатель. В этом случае MATLAB не будет работать, если у вас нет доступа к панели инструментов оптимизации.
http://www.mathworks.com/products/optimization/index.html
В вашей формулировке вам необходимо учесть следующее:
Переменные решения
В вашем случае это будет выглядеть примерно так:
x_it (выберите [да =1 нет =0] для перевозки предмета i во время поездки на лодке номер t)
Объективная функция
Я не совсем уверен, что это из вашего описания, но должна быть стоимость, c_t, связанная с каждой поездкой на лодке. Если вы хотите минимизировать общее время, каждая поездка будет иметь постоянную стоимость 1. Поэтому ваша цель должна выглядеть примерно так:
минимизировать SUM((i,t),c_t*x_it) (поэтому вы минимизируете общую стоимость за все поездки)
Ограничения
Это сложная часть вашей проблемы. Сложным ограничением является исключительность, которую вы определили. Помните, что x_it является двоичным.
Для каждой пары элементов (i1, i2), которые конфликтуют друг с другом, у вас есть ограничение, которое выглядит следующим образом
x_(i1 t) + x_(i2 t) <= 1
Например:
x _ ("капуста" "1") + x_("козел" "1") <=1
x _ ("волк" "1") + x_("козел" "1") <=1
x _ ("капуста" "2") + x_("козел" "2") <= 1
x _ ("волк" "2") + x_("козел" "2") <= 1
ЭСТ.
Вы видите, как это предотвращает конфликт. Расписание лодок, которое назначает "капусту" и "козу" одной и той же поездке, нарушит это двоичное ограничение эксклюзивности, поскольку "1+1 > 1"
Такие инструменты, как GAMS,AMPL и GLPK, позволят вам выразить эту группу ограничений очень кратко.
Надеюсь, это поможет.