2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 [ILOG OPL IDE] Транспортная задача/коммивояжера/ЛП
Сообщение02.06.2013, 17:41 


02/06/13
3
Друзья и братья по разуму!!! Прошу Вашей помощи.
Помогите разобраться в транспортной задаче (перевозка, логистика), которую решаю на 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х. В этом случае программа дала верное решение. С увеличением количества пунктов ответ получается с "зацикливанием".

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

 Профиль  
                  
 
 Posted automatically
Сообщение02.06.2013, 19:38 
Супермодератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Posted automatically
Сообщение02.06.2013, 22:26 
Заслуженный участник


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

 Профиль  
                  
 
 Re: [ILOG OPL IDE] Транспортная задача/коммивояжера/ЛП
Сообщение03.06.2013, 13:25 
Заслуженный участник
Аватара пользователя


03/06/08
2319
МО
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; };



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

 Профиль  
                  
 
 Re: [ILOG OPL IDE] Транспортная задача/коммивояжера/ЛП
Сообщение03.06.2013, 19:29 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: [ILOG OPL IDE] Транспортная задача/коммивояжера/ЛП
Сообщение04.06.2013, 08:03 


02/06/13
3
пианист в сообщении #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$, по любому, еще какие-то условия нужны, иначе эти два соотношения никаких ограничений не накладывают (что и показал расчет :).


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

 Профиль  
                  
 
 Re: [ILOG OPL IDE] Транспортная задача/коммивояжера/ЛП
Сообщение30.06.2013, 01:33 
Заслуженный участник
Аватара пользователя


03/06/08
2319
МО
EleNA_OPL в сообщении #732355 писал(а):
пианист в сообщении #732149 писал(а):
И, кстати, на $U_y$, $U_z$, по любому, еще какие-то условия нужны, иначе эти два соотношения никаких ограничений не накладывают (что и показал расчет :).


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


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


Последний раз поднималось EleNA_OPL 30.06.2013, 01:33.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group