Перерозподіл перевезень в транспортній задачі з метою поліпшення рішення відбувається по циклу (відомий як цикл перерахунку). Даний цикл в транспортній таблиці являє собою сукупність клітинок, з’єднаних замкнутою ламаною лінією, яка в кожній клітинці робить поворот на 90 градусів, і обов’язковою вимогою є те, що в кожному рядку і кожному стовпці, по яких проходить цикл, повинно бути дві і тільки дві вершини. Також слід відмітити, що кожен цикл перерахунку складається з парного числа вершин, одна з яких міститься у вільній клітинці, а інші – у заповнених. Якщо відрізки ламаної лінії перетиноються, то точка перетину вершиною не вважається. Для кожної вільної клітини можна побудувати цикл перерахунку і при чому єдиний.
Після того як для деякої вільної клітини побудований цикл, слід перейти до нового допустимого рішення. Для цього необхідно здійснити перерозподіл перевезень в межах клітинок, пов’язаних циклом. Даний перерозподіл здійснюють за такими правилами:
- Кожній з клітинок, пов’язаних циклом (включно з вільною клітинкою), приписують певний знак, причому вільній клітинці – знак «+», а всім іншим клітинкам – по черзі знаки «-» і «+».
- Серед значень клітинок позначених мінусом вибираємо мінімальне і до клітинок позначених знаком плюс додаємо це (мінімальне) значення, а від клітинок позначених знаком мінус — віднімаємо дане значення. В результаті клітинка де знаходилось мінімальне значення стає вільною. Таким чином ми отримуємо новий опорний план, який знову потрібно перевірити на оптимальність.
Зауваження: всі описані дії проводяться над клітинками, які утворюють цикл перерахунку; при переході до нового опорного плану число зайнятих клітин залишається незмінним, рівним m + n – 1; якщо в циклі існує дві або більше клітинки з одинаковими значеннями, які позначені знаком «-», то одна з них стає вільною, а решта – залишаються зайнятими, перевезення яких рівне нулю.
Тепер, після того як основні правила побудови циклу перерозподілу плану задачі відомі, спробуємо реалізувати перехід від одного опорного плану транспортної задачі, до іншого, в середовищі програмування Delphi. Припустимо, що з допомогою методу північно-західного кута, ми отримали опорний план деякої транспортної задачі, який міститься в настпуній таблиці.
Далі, припустимо, що використовуючи метод потенціалів ми визначили, що даний план не являється оптимальним, і клітинка таблиці, яка міститься в третьому рядку і другій колонці повинна бути зайнятою. Тобто для даної клітинки потрібно побудувати цикл перерахунку. Для побудови циклу будемо використовувати наступний алгоритм: якщо в рядку чи у стовпці таблиці немає парної кількості зайнятих клітинок, то такі клітинки вилучаємо із циклу перерозподілу вантажу; надалі вони не враховуватимуться у розрахунках. Якщо в результаті цієї дії створюються інші рядки (колонки), які не мають пари, то їх також вилучаємо із циклу. У результаті залишаються тільки ті клітинки таблиці, що мають пару і утворюють цикл. Відмітимо, що на кожний рядок і колонку циклу приходяться лише по дві таких клітинки.
Отже, створимо новий Delphi-проект і спробуємо реалізувати вищерозглянутий алгоритм. Для цього, на головній формі проекту розмістимо компонент Button1, з допомогою якого будемо здійснювати побудову циклу перерахунку, і другий компонент StringGrid1 – який будемо відображати результат у вигляді таблиці.
Далі, на подію OnClick кнопки “Побудова циклу перерахунку” напишемо наступний код:
procedure TForm1.Button1Click(Sender: TObject);
var
i, ii, j, jj, n, m, k, z: integer;
A: array[1..3, 1..4] of real;
p: boolean;
begin
n := 3; m := 4;
{ Записуємо опорний план транспортної задачі в масив }
A[1, 1] := 35; A[1, 2] := 0; A[1, 3] := 0; A[1, 4] := 0;
A[2, 1] := 10; A[2, 2] := 20; A[2, 3] := 20; A[2, 4] := 0;
A[3, 1] := 0; A[3, 2] := 0; A[3, 3] := 10; A[3, 4] := 30;
{ Елемент масиву, який повинен бути зайнятим робимо відмінним від нуля }
A[3, 2] := -1;
p := true;
k := 2;
while (p) do
begin
p := false;
if (k mod 2 <> 0) then
begin
{ Якщо у рядку матриці A не міститься парної кулькості відмінних від нуля елементів, то елементу, який немає пари присвоюєм значення нуль, тобто вилучаємо його з розгляду }
for i := 1 to n do
begin
z := 0;
for j := 1 to m do
if (A[i, j] <> 0) then
begin
z := z + 1;
jj := j;
end;
if (z = 1) then
begin
A[i, jj] := 0;
p := true;
end;
end;
end
else
begin
{ Аналогічним чином, якщо у стовпці матриці A не міститься парної кулькості відмінних від нуля елементів, то елементу, який немає пари присвоюєм значення нуль, і таким чином, також вилучаємо його з розгляду }
for j := 1 to m do
begin
z := 0;
for i := 1 to n do
if (A[i, j] <> 0) then
begin
z := z + 1;
ii := i;
end;
if (z = 1) then
begin
A[ii, j] := 0;
p := true;
end;
end;
end;
k := k + 1;
end;
{ Виводимо результат в елемент StringGrid1 }
for i := 1 to n do
for j := 1 to m do
StringGrid1.Cells[j-1, i-1] := FloatToStr(A[i, j]);
end;
Запустивши проект на виконання і натиснувши кнопку Button1 бачимо, що у компоненті StringGrid1 відмінними від нуля являються лише ті комірки, які утворюють цикл перерахунку та з допомогою яких переходимо до нового опорного плану.
Скачати даний проект можна за посиланням Побудова циклу перерахунку в середовищі програмування Delphi.
Дуже дякую за цю статтю, дуже хотілось щоб ви описали алгоритм за яким по найденим елементам в циклі ми змогли би робити почергові дії над ними, тобто знайшовши потрібний нам елемент з відємною дельтою ми віднімали і додавали би його почергово від і до інших елементів.
Доброго вечора Костянтин.
Наскільки я зрозумів Вас цікавить процес перерозподілу плану транспортної задачі, згідно з побудованим циклом перерахунку. Delphi-проект, що реалізує це, міститься за вказаним нижче посиланням:
Перехід до нового опорного плану в транспортній задачі.
admin, ця програма працює коректно? просто прочитавши код як я зрозумів ми в за допогою цикла перерахунку повинні були отримати 10 в клітинці з індексом від’ємного елемента, 20, 30 в двох інших клітинках і 0 в клітинці де було 10, але при виконанні програма видає 2.15… в клітинці з від’ємним елементом а інші клітинки з циклу залишає без змін.
Привіт Констянтин.
Вказані Вами у коментарі значення для нового допустимого рішення транспортної задачі, є не зовсім правильними. Помилка полягає в тому, що Ви невірно розставили знаки для комірок пов’язаних циклом. Згідно з правилом 1, кожній з комірок, побудованого циклу, знак «+» та «-» повинен приписуватись в наступному порядку: вільній комірці — знак «+»; всім іншим — по черзі знаки «-» і «+». Тобто, в нашому випадку, знаки повинні бути розставлені наступним чином:
Після того, як знаки розставлено, переходимо до перерозподілу перевезень в межах комірок, пов’язаних циклом. Для цього, згідно з правилом номер 2, на першому кроці, серед значень комірок позначених мінусом вибираємо мінімальне. В нашому випадку таким являється значення 10.
Далі, до комірок позначених знаком плюс додаємо це значення, а від комірок позначених знаком мінус — віднімаємо його. Таким чином отримуємо новий опорний план.
Також хотідося б дати відповідь на питання “admin, ця програма працює коректно?”, але не зовсім зрозумілим являється те, про яку програму йде мова. Якщо про delphi-проект, який міститься за посиланням Перехід до нового опорного плану в транспортній задачі, то переглянувши знімок його головної форми (рисунок, що міститься вище), можна зробити висновок, що результати зовсім не такі. Якщо для Вас це питання являється принциповим, то опишіть будь-ласка більш детально про яку програму йде мова.
Я вдячний за настільки детальну відповідь, це не принципове питання, я таких результатів я і очікував, але допустив помилку в коментарі вище, можливо ця проблема виникла в мене через те що я запускав за допомогою ехе файла а не через середовище делфі, ось скрін програми яка була скачана за даним посилання: Перехід до нового опорного плану в транспортній задачі – i.imgur.com/LdLgxEu.png