Перехід від одного плану перевезень в транспортній задачі до іншого використовуючи цикл перерахунку

Перерозподіл перевезень в транспортній задачі з метою поліпшення рішення відбувається по циклу (відомий як цикл перерахунку). Даний цикл в транспортній таблиці являє собою сукупність клітинок, з’єднаних замкнутою ламаною лінією, яка в кожній клітинці робить поворот на 90 градусів, і обов’язковою вимогою є те, що в кожному рядку і кожному стовпці, по яких проходить цикл, повинно бути дві і тільки дві вершини. Також слід відмітити, що кожен цикл перерахунку складається з парного числа вершин, одна з яких міститься у вільній клітинці, а інші – у заповнених. Якщо відрізки ламаної лінії перетиноються, то точка перетину вершиною не вважається. Для кожної вільної клітини можна побудувати цикл перерахунку і при чому єдиний.

Графічне представлення циклу перерахунку
Графічне представлення можливих конфігурацій циклу перерахунку

Після того як для деякої вільної клітини побудований цикл, слід перейти до нового допустимого рішення. Для цього необхідно здійснити перерозподіл перевезень в межах клітинок, пов’язаних циклом. Даний перерозподіл здійснюють за такими правилами:

  1. Кожній з клітинок, пов’язаних циклом (включно з вільною клітинкою), приписують певний знак, причому вільній клітинці – знак «+», а всім іншим клітинкам – по черзі знаки «-» і «+».
  2. Серед значень клітинок позначених мінусом вибираємо мінімальне і до клітинок позначених знаком плюс додаємо це (мінімальне) значення, а від клітинок позначених знаком мінус — віднімаємо дане значення. В результаті клітинка де знаходилось мінімальне значення стає вільною. Таким чином ми отримуємо новий опорний план, який знову потрібно перевірити на оптимальність.

Зауваження: всі описані дії проводяться над клітинками, які утворюють цикл перерахунку; при переході до нового опорного плану число зайнятих клітин залишається незмінним, рівним m + n – 1; якщо в циклі існує дві або більше клітинки з одинаковими значеннями, які позначені знаком «-», то  одна з них стає вільною, а решта –  залишаються зайнятими, перевезення яких рівне нулю.

Тепер, після того як основні правила побудови циклу перерозподілу плану задачі відомі, спробуємо реалізувати перехід від одного опорного плану транспортної задачі, до іншого, в середовищі програмування Delphi. Припустимо, що з допомогою методу північно-західного кута, ми отримали опорний план деякої транспортної задачі, який міститься в настпуній таблиці.

Опорний план транспортної задачі отриманий з допомогою методу північно-західного кута
Опорний план транспортної задачі отриманий з допомогою методу північно-західного кута

Далі, припустимо, що використовуючи метод потенціалів ми визначили,  що даний план не являється оптимальним, і клітинка таблиці, яка міститься в третьому рядку і другій колонці повинна бути зайнятою. Тобто для даної клітинки потрібно побудувати цикл перерахунку. Для побудови циклу будемо використовувати наступний алгоритм: якщо в рядку чи у стовпці таблиці немає парної кількості зайнятих клітинок, то такі клітинки вилучаємо із циклу перерозподілу вантажу; надалі вони не враховуватимуться у розрахунках. Якщо в результаті цієї дії створюються інші рядки (колонки), які не мають пари, то їх також вилучаємо із циклу. У результаті залишаються тільки ті клітинки таблиці, що мають пару і утворюють цикл. Відмітимо, що на кожний рядок і колонку циклу приходяться лише по дві  таких клітинки.

Отже, створимо новий Delphi-проект і спробуємо реалізувати вищерозглянутий алгоритм. Для цього, на головній формі проекту розмістимо компонент Button1, з допомогою якого будемо здійснювати побудову циклу перерахунку, і другий компонент StringGrid1 – який будемо відображати результат у вигляді таблиці.

Delphi-проект, який реалізує алгоритм побудови циклу перерахунку
Delphi-проект, який реалізує алгоритм побудови циклу перерахунку

Далі, на подію 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 відмінними від нуля являються лише ті комірки, які утворюють цикл перерахунку та з допомогою яких переходимо до нового опорного плану.

Побудова циклу перерахунку
Вивід елементів масива, які утворюють цикл в компонент StringGrid

Скачати даний проект можна за посиланням Побудова циклу перерахунку в середовищі програмування Delphi.

5 коментарів

  1. Дуже дякую за цю статтю, дуже хотілось щоб ви описали алгоритм за яким по найденим елементам в циклі ми змогли би робити почергові дії над ними, тобто знайшовши потрібний нам елемент з відємною дельтою ми віднімали і додавали би його почергово від і до інших елементів.

  2. Доброго вечора Костянтин.
    Наскільки я зрозумів Вас цікавить процес перерозподілу плану транспортної задачі, згідно з побудованим циклом перерахунку. Delphi-проект, що реалізує це, міститься за вказаним нижче посиланням:
    Перехід до нового опорного плану в транспортній задачі.

  3. admin, ця програма працює коректно? просто прочитавши код як я зрозумів ми в за допогою цикла перерахунку повинні були отримати 10 в клітинці з індексом від’ємного елемента, 20, 30 в двох інших клітинках і 0 в клітинці де було 10, але при виконанні програма видає 2.15… в клітинці з від’ємним елементом а інші клітинки з циклу залишає без змін.

  4. Привіт Констянтин.
    Вказані Вами у коментарі значення для нового допустимого рішення транспортної задачі, є не зовсім правильними. Помилка полягає в тому, що Ви невірно розставили знаки для комірок пов’язаних циклом. Згідно з правилом 1, кожній з комірок, побудованого циклу, знак «+» та «-» повинен приписуватись в наступному порядку: вільній комірці — знак «+»; всім іншим — по черзі знаки «-» і «+». Тобто, в нашому випадку, знаки повинні бути розставлені наступним чином:

    Цикл перерахунку

    Після того, як знаки розставлено, переходимо до перерозподілу перевезень в межах комірок, пов’язаних циклом. Для цього, згідно з правилом номер 2, на першому кроці, серед значень комірок позначених мінусом вибираємо мінімальне. В нашому випадку таким являється значення 10.

    Далі, до комірок позначених знаком плюс додаємо це значення, а від комірок позначених знаком мінус — віднімаємо його. Таким чином отримуємо новий опорний план.
    Новий опорний план транспортної задачі

    Також хотідося б дати відповідь на питання “admin, ця програма працює коректно?”, але не зовсім зрозумілим являється те, про яку програму йде мова. Якщо про delphi-проект, який міститься за посиланням Перехід до нового опорного плану в транспортній задачі, то переглянувши знімок його головної форми (рисунок, що міститься вище), можна зробити висновок, що результати зовсім не такі. Якщо для Вас це питання являється принциповим, то опишіть будь-ласка більш детально про яку програму йде мова.

  5. Я вдячний за настільки детальну відповідь, це не принципове питання, я таких результатів я і очікував, але допустив помилку в коментарі вище, можливо ця проблема виникла в мене через те що я запускав за допомогою ехе файла а не через середовище делфі, ось скрін програми яка була скачана за даним посилання: Перехід до нового опорного плану в транспортній задачі – i.imgur.com/LdLgxEu.png

Залишити коментар

Your email address will not be published. Required fields are marked *

*