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

x_wolf,1 + x_cabbage,1 + x_coat,1 ‹= 1 + x_wolf,0 + x_cabbage,0 + x_coat,0 и

х_волк,1 >= х_волк,0

х_капуста, 1 >= х_капуста, 0

х_коза,1 >= х_коза,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_coat,t)

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

(Скорее всего, sum_t (x_wolf,t + x_cabbage,t + x_goat,t) тоже подойдет.)

Вы правы, что для этой формулировки потребуются целочисленные переменные. Традиционным способом решения такой задачи было бы сформулировать модель бинарной переменной и передать формулировку решателю. MATLAB в этом случае не будет работать, если у вас нет доступа к Optimization Toolbox.

http://www.mathworks.com/products/optimization/index.html

В вашей формулировке вам нужно будет решить следующее:

Переменные решения

В вашем случае это будет выглядеть примерно так:

x_it (выберите [yes=1 no=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, позволят вам очень кратко выразить эту группу ограничений.

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