Фокс-Коза-Капуста Транспорт

Question

Мой вопрос касается старой транспортной проблемы - перевозить три предмета через реку на лодке, способной переносить только один предмет за раз.Ограничение состоит в том, что некоторые элементы нельзя оставлять вместе, например, капусту с козой, волка с козлом и т. Д. Эту проблему необходимо решить с помощью целочисленного программирования или другого подхода к оптимизации.Функция стоимости - это все элементы, находящиеся на другой стороне реки, и поездки, необходимые для их получения, могут быть выходными данными Simplex (?), Который пробует различные возможные решения.Мне было интересно, есть ли у кого-нибудь целочисленное программирование (или линейное программирование) формулировка этой проблемы, и / или Matlab, Octave, код на Python, который может предложить решение программно, включая трассировку Simplex, пробующую все пути - наши поездки на лодке,

Здесь было несколько интересных вещей

http://www.zib.de/Publications/Reports/SC-95-27.pdf

Спасибо,

Answer 1

Я рекомендую использовать бинарные переменные x_i, t для моделирования позиций ваших предметов, т.е. они равны нулю, если предмет расположен на левом берегу после поездки t, и одной в противном случае.Максимум одна из этих переменных может измениться во время поездки.Это можно смоделировать с помощью

x_wolf, 1 + x_cabbage, 1 + x_goat, 1 <= 1 + x_wolf, 0 + x_cabbage, 0 + x_goat, 0 и </p>

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 ... </p>

Использовать верхнюю границу дляt, такое, что решение, безусловно, возможно.

Наконец, введите двоичную переменную z_t и пусть

z_t <= 1/3 (x_wolf, t + x_cabbage, t + x_goat, t)</p>

и максимизировать sum_t (z_t).

(Скорее всего, работать с sum_t (x_wolf, t + x_cabbage, t + x_goat, t).)

Answer 2

Вы правы, что эта формулировка потребует целочисленных переменных.Традиционный способ решения такой проблемы состоит в том, чтобы сформулировать модель двоичной переменной и передать ее в решатель.В этом случае 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_ (i2t) <= 1 </p>

Например:

x _ ("капуста" "1") + x _ ("козел" "1") <= 1 </p>

x_ ("волк" "1") + x _ ("коза" "1") <= 1 </p>

x _ ("капуста" "2") + x _ ("коза" "2") <= 1 </p>

x _ ("волк" "2") + x _ ("козел" "2") <= 1 </p>

т. Д.

Вы видите, как это предотвращает конфликт.Расписание лодок, которое назначает «капусту» и «козу» одной и той же поездке, нарушит это двоичное ограничение эксклюзивности, поскольку «1 + 1> 1»

Такие инструменты, как GAMS, AMPL и GLPK, позволят вам выразить эту группуиз ограничений очень кратко.

Надеюсь, это поможет.