Ветошкин а

Ветошкина А.А. Костякова А.І. Виродження ТРАНСПОРТНОЇ ЗАВДАННЯ І ЯК З НЕЮ БОРОТИСЯ

Як відомо, транспортна задача буває відкрита і закрита. Відкритої називається задача, в якій баланс постачальників і споживачів не рівні між собою. Це явище зазвичай і зустрічається часто-густо. Спосіб боротьби з цим единственен і простий: додаємо фіктивного постачальника, якщо баланс постачальників менше, ніж баланс споживачів, і навпаки.

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

З першого погляду здається, що вирожденність завдання - явище випадкове і ніяким законам не підкоряється. Навіть більше того, базові плани, створені за допомогою різних методів, наприклад, Північно-західного кута і Мінімальних значень, дають вироджених і невироджених плани для однієї і тієї ж задачі. Це, природно, породжує думки: прихована вирожденність в завданню або метод створення плану створює її. Але коли в іншому завданні не спрацьовує, навпаки, той метод, який тільки що створив нормальний невироджених план, залишається одна думка: вирожденність - явище потойбічне і не залежить від завдання і застосовуваного методу створення плану.

І все-таки існує спосіб не тільки позбутися від вирожденність, але і «знищити» її до кінця життя. Яким чином? Яка природа вирожденність і звідки вона виникає? Розглянемо питання в такому порядку: природа вирожденність; звідки (і чому) виникає вирожденність; як з нею боротися.

Отже, природа вирожденність. Виродженість - коли не вистачає клітин-рівнянь для визначення потенціалів в плані. Це, коли необхідно для нормальної роботи m + n-1 рівняння, а їх, на жаль, m + n-2. І ще гірше, якщо їх виходить тільки m, як в цьому завданні (див. Таблиця 1) при використанні методу Північно-західного кута.

Одержувач> Джерело v

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

Теорема: Про неможливе упровадженому циклі

Зайнятий стовпець - стовпець, в якому знаходиться клітина плану і значення одержувача дорівнює 0.

Незайнятий стовпець - стовпець, в якому знаходиться клітина плану і значення одержувача не дорівнює 0, або в стовпці немає жодної клітини плану.

П-конструкція - вертикальний відрізок в стовпці k (тулуб) з кінцями на рядках i і j і двома горизонтальними «хвостами», спрямованими в одну сторону, наприклад, вправо. Будь-які інші орієнтації зводяться до даної шляхом поворотів або відображень.

Формулювання: У тому випадку, коли при створенні плану одночасно обнуляються постачальник і одержувач, і нульова клітина поміщається в будь-який незайнятий стовпець, цикл не утворюється.

Доказ: будь-який цикл містить в собі П-подібну конструкцію, позначені номерами від 1 до 4 (див. Малюнок 1).

Малюнок 1. Різні види циклів.

Цю конструкцію в нашій задачі можна представити так: (1,1), (1,2), (2,2), (2,1) або (2,1), (1,1), (1,2) , (2,2) (див. таблиця 6). Вона з'являється, коли нульова клітина поміщається в (1,1) при наявності зайнятих клітин (1,2), (2,2), (2,1).

Якщо ми доведемо, що така конструкція не може з'явитися в нашому випадку, це і буде означати, що цикли в створеному за правилами плані неможливі.

Лемма: В правильно складається плані П-конструкції не з'являються.

Доказ: Перевіримо варіанти ситуацій, коли дана конструкція може утворитися. У всіх випадках обробляється рядок j.

1. Рядок i має одну зайняту клітку, і обробка її закінчена.

2. Рядок i має одну зайняту клітку, і обробка її не закінчена.

3. Рядок i має більше однієї зайнятої клітини.

Щоб не заплутувати доказ, умовно приймемо, що в інших рядках немає жодної зайнятої клітини. В іншому випадку в якості рядка i необхідно перевірити всі рядки по черзі.

У першому випадку в рядку j в тому стовпці, де рядок i має зайняту клітку, можна розмістити як клітку плану, так і нульову клітину, оскільки в рядку i немає «хвоста», як одного з елементів П-конструкції. В подальшому розгляді будемо розглядати випадок 3 для стовпця, в який ми помістили дві клітини.

У другому випадку в рядку j в тому ж стовпці можна нічого розмістити, оскільки стовпець вже зайнятий (згадаємо, як з'являються клітини плану). Так що основи для П-конструкції немає.

Значить, «наріжним» в доказі є випадок 3. Очевидно, що всі стовпці, в яких розташовані зайняті клітини рядка i, зайняті, крім одного, в якому рядок обнулилася (Природно, два і більше незайнятих стовпців при наявності клітин плану означають, що рядок i обнуляє кілька разів, чого бути не може). Але і він може бути зайнятий, якщо обнулився разом з рядком. Якщо всі стовпці зайняті, то як і в випадку 2, основи для П-конструкції немає.

Залишається одна можливість - єдиний незайнятий стовпець. Розміщуємо в нього клітку. Якщо рядок j обнулилася, а стовпець - немає, то хвіст з даної клітини не з'явиться. Якщо і стовпець обнулився, то поміщаємо нульову клітину у вільний стовпець як частина плану. Ця клітина не замкне цикл, оскільки з рядка i чи не з'явиться нових клітин плану (всі стовпці обнулені), а вже наявні, разом з йдуть з них шляхами, не стосуються незайнятого стовпчика.

Таким чином, П-конструкції в правильно складається плані не з'являються. І, отже, цикли не утворюються. Що й потрібно було довести.

Повернемося до питання про вирожденність отриманого плану. Згадаймо, що кожна клітина плану є по суті одне рівняння в методі потенціалів, що зв'язує дві змінних v (i) і u (j). При розрахунках одна змінна є обумовленою, друга визначеною. Нам треба порахувати, скільки визначаються змінних є у всіх клітинах-рівняннях.

Нехай в рядку i знаходиться m (i) клітин, беручи до уваги нульовий. Подивимося, що визначають ці рівняння. Якщо рядок i в процесі занесення в план клітини (i, j) обнуляється, а стовпець j - немає, то цим рівнянням визначається змінна v (i) і (m (i) - 1) змінних u, крім, природно, змінної u ( j), яка визначиться, коли обнулится стовпець j. Якщо стовпець обнуляється разом з рядком, то визначається m (i) змінних u, а додавання нульовий осередку визначається змінна v (i) (не забуваємо, що в останнього заповненого рядку немає нульовий клітини). Тепер порахуємо рівняння і змінні. Оскільки всі стовпці в процесі складання плану обнулені, то сума m (i) дорівнює загальній кількості стовпців, тобто m. Оскільки при обнулення кожного рядка (крім останньої) визначається одна змінна v (i), то при обнулення всіх рядків ми визначили n-1 змінних. Загальна кількість певних змінних становить m + (n-1). Що й треба було!

ВИСНОВОК: Застосовуючи правило «Якщо при створенні плану одночасно обнуляються постачальник і одержувач, то нульова клітина плану поміщається в будь-який незайнятий стовпець» ми отримуємо невироджених і незацікленний план, і без будь-яких хитрощів.

На завершення наводимо базовий план, складений з урахуванням правила, ітерації і оптимальний план розглянутої задачі з різницями потенціалів і ціною (оцінкою) плану.

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

Усунення вирожденність в наявному плані

Якщо базовий план вже складено і виявлено, що він вироджений, то пропонується формалізоване правило для виправлення таких планів.

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

Дійсно: одна клітина базового плану, якщо вона перша в групі, відзначає один рядок плюс один стовпець, що не перша-один рядок або один стовпець. Таким чином K клітин групи відзначають K +1 рядків або стовпців. Оскільки всього N + M рядків або стовпців, N- кількість рядків, M-кількість стовпців. Для однієї групи отримуємо:

K + 1 = N + M або K = N + M-1

що й потрібно було довести .

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

K + L = N + M або K = N + M- L

Тобто для отримання невиродженого плану потрібно додати L -1 клітку в план. Визначимо місця для цих клітин. Якщо нова клітина плану потрапить в порожню клітину з двома однаковими номерами, то вона замкне цикл, що для плану небажано. При розподіл нових клітин плану таким чином, щоб один з номерів дорівнював 1, не допускаючи повторів номерів, ми пов'язуємо різні групи і отримуємо L -1 нову клітку. Затвердження таким чином доведено.

Результат вищеописаного алгоритму наведено в таблиці

Н нові (або додаються) клітини плану (2)

П погані клітини (замикають цикл)

K = 7 (кількість клітин існуючого плану);

L = 3 (кількість які утворилися груп);

N = 5 (кількість рядків);

M = 5 (кількість стовпців).

Висновок: необхідно визначити групи зв'язкових клітин, якщо ця група не одна, то нові клітини плану ставити в місцях пов'язаних з різними групами.

Якщо Ви ще не зареєстровані на сайті, то Вам необхідно зареєструватися: