[ILOG OPL IDE] Транспортная задача/коммивояжера/ЛП

[EleNA_OPL]

Друзья и братья по разуму!!! Прошу Вашей помощи.
Помогите разобраться в транспортной задаче (перевозка, логистика), которую решаю на IBM ILOG OPL IDE.
Постановка: в компании имеется 2 авто. Необходимо совершить оптимальные поездки в указанные пункты за определенное время. Все поездки должны начинаться и заканчиваться базовым пунктом. В каждом пункте, кроме базового, может (но не обязано!!) побывать только одно авто. Сумма всех затрат должна быть минимальной.

В тело программы ввожу количество пунктов задачи, макс. время на выполнение всех операций, все необходимые массивы, переменные и пр.
is – номер пункта 1, где I – общее количество пунктов;
js – номер пункта 2;
yis js и zis js – булевая переменная, определяющая путь, между пунктами «is» и «js» для 1ТС и 2ТС (размерность IхI);
Fy, Fz и Ny, Nz – матрица (размерность IxI) - определяет затраты и средн скорость каждого ТС на перемещение по путям «is», «js»;
Py, Pz – признак посещения автомобилем пунктов маршрута (булевые переменные) (размерность I).
Сy, Сz – стоимость эксплуатации 1 часа авто на перемещение между путями;
ty, tz – заданное максимальное время выполнения операции;
Uy, Uz – вещественные переменные, обеспечивающее невозможность распадения контура-решения на отдельные контуры 1ТС и 2ТС.

Далее ЦФ + ограничения:

         minimize (Cy*sum(i in is, j in js)(Fy[i][j]*y[i][j])/Ny[i][j])+Cz*(sum(i in is, j in js)(Fz[i][j]*z[i][j])/Nz[i][j]);

subject to { forall(i in is)  Py[1]+Pz[1] == 2;
                forall(i in 2..I)  Py[i]+Pz[i] >= 1;  
        sum(i in is, j in js)(Fy[i][j]*y[i][j])/Ny[i][j] <= ty;
      sum(i in is, j in js)(Fy[i][j]*y[i][j])/Ny[i][j] <= tz;
              forall(i in is)  sum(j in js) y[i][j] == Py[i];
              forall(j in js)  sum(i in is) y[i][j] == Py[j];
              forall(i in is)  sum(j in js) z[i][j] == Pz[i];
              forall(j in js)  sum(i in is) z[i][j] == Pz[j];
  forall(i,j in 2..I : i != j) Uy[i]-Uy[j]+(I+1)*y[i][j] <= I;
  forall(i,j in 2..I : i != j) Uz[i]-Uz[j]+(I+1)*z[i][j] <= I; };

В ходе решения программа выдает решение, часть которого "зацикливается" (см. путь "у" 1-2-6-1 а далее не понятно- 3-3, 4-4, 5-5, 7-7, 8-8), что происходить не должно (т.к. два последних ограничения должны исключать это):

// solution (optimal) with objective 9.40555555555556
y = [[0 1 0 0 0 0 0 0]
             [0 0 0 0 0 1 0 0]
             [0 0 1 0 0 0 0 0]
             [0 0 0 1 0 0 0 0]
             [0 0 0 0 1 0 0 0]
             [1 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 1 0]
             [0 0 0 0 0 0 0 1]];
z = [[1 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0]];
Py = [1 1 1 1 1 1 1 1];
Pz = [1 0 0 0 0 0 0 0];
Uy = [-1 0 0 0 0 0 0];
Uz = [0 0 0 0 0 0 0];

Думаю ошибка либо в формулах ЦФ или огранич.; либо в написании самой программы. Попыталась найти ошибку путем сокращения количества пунктов до 3х. В этом случае программа дала верное решение. С увеличением количества пунктов ответ получается с "зацикливанием".

Помогите пожалуйста кто шарит в этом. Я весь мозг сломала))

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Наберите все формулы $\TeX$ом, а программный код - тегом code. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[GAA]

Тема перемещена из форума «Карантин» в форум «Программирование»

[пианист]

EleNA_OPL в сообщении #731657 писал(а):

   forall(i,j in 2..I : i != j) Uy[i]-Uy[j]+(I+1)*y[i][j] <= I;
  forall(i,j in 2..I : i != j) Uz[i]-Uz[j]+(I+1)*z[i][j] <= I; };

Рискну предположить (данная технология мне незнакома): тут, случайно, не нужно ли по всем узлам пробегать (включая первый)?

[пианист]

И, кстати, на $U_y$, $U_z$, по любому, еще какие-то условия нужны, иначе эти два соотношения никаких ограничений не накладывают (что и показал расчет :).

[EleNA_OPL]

пианист в сообщении #731967 писал(а):

EleNA_OPL в сообщении #731657 писал(а):

   forall(i,j in 2..I : i != j) Uy[i]-Uy[j]+(I+1)*y[i][j] <= I;
  forall(i,j in 2..I : i != j) Uz[i]-Uz[j]+(I+1)*z[i][j] <= I; };

Рискну предположить (данная технология мне незнакома): тут, случайно, не нужно ли по всем узлам пробегать (включая первый)?

Увы, нет. Обязательно должен считать со 2 пункта (ведь поездки все начинаются со 2 пункта, а 1 пункт - это просто "база"), иначе решение вообще отсутствует.

-- 04.06.2013, 08:16 --

пианист в сообщении #732149 писал(а):

И, кстати, на $U_y$, $U_z$, по любому, еще какие-то условия нужны, иначе эти два соотношения никаких ограничений не накладывают (что и показал расчет :).

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

[пианист]

EleNA_OPL в сообщении #732355 писал(а):

пианист в сообщении #732149 писал(а):

И, кстати, на $U_y$, $U_z$, по любому, еще какие-то условия нужны, иначе эти два соотношения никаких ограничений не накладывают (что и показал расчет :).

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

Виноват, перепутал числитель со знаментелем, и мне показалось, что $U_y$, $U_z$ можно положить равными нулю, после чего те два соотношения всегда будут выполнены, что, конечно, не так.
Однако, как бы оно там ни было, требуемого эта пара условий тоже не обеспечивает: в приведенном решении $U_y$, $U_z$ подобраны (нули, кроме $U_y[1]$), а маршрут, тем не менее, развалился.
М.б., Вы приведете резоны, почему, собс-но, эти равенства должны обеспечивать связность, вместе подумаем, чего не хватает.