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

Перерозподіл перевезень в транспортній задачі з метою поліпшення рішення відбувається по циклу (відомий як цикл перерахунку). Даний цикл в транспортній таблиці являє собою сукупність клітинок, з'єднаних замкнутою ламаною лінією, яка в кожній клітинці робить поворот на 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.

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар