в транспортній задачі.
а) метод північно-західного кута;
б) метод min елементу;
в) метод Фочеля.
Нехай ми маємо транспортну задачу. |
північ | ...
захід
... | ...
Для транспортної задачі
???
Нехай
Внаслідок одного кроку розміри вихідної таблиці в нас будуть зменшуватися на 1. , тобто
На кожному кроці в нас будуть задовольнятися потреби пункту споживання, або ??? ???. На останньому кроці ці два пункти здійснюються одночасно, тобто за m+n-1 ми завжди побудуємо початковий базисний план. |
5 | 16 | 4 | 18
5 | 5 | 5
12 | 6 | 4 | 2
18 | 18
План по цьому методу є дуже далекий від оптимального, тому що він не враховує вартості перевозом.
Метод мінімального елементу. |
1 | 11 | 7 | 9
1 | 1
7 |
10 |
12 | 9
1
1 | 1
9 |
8 | 7
5 |
2
1 | 1
4 | 11
3 |
7 |
8
Теоретичні основи розподільчого методу.
Озн. 1. Пару чисел ij ми будемо називати кліткою.
Озн. 2. Ті клітки, в які ми заносимо ??? ??? наз. Х – вибраними елементами.
Озн. 3. Набір кліток, що має вид
наз. ланцюгом.
Озн. 4. Набір кліток, що має вид
- наз. замкнутим ланцюгом.
Озн. 5. Довільна множина х – вибраних кліток наз. вибором.
Озн. 6. Вибір, який містить хоча б один замкнутий ланцюг наз. циклічним, а замкнутий ланцюг завжди буде мати парне число елементів, тому що від кожного рядка і стовпця завжди виходить по 2 елементи.
Озн. 7. Вибір, який не містить жодного замкнутого ланцюга називається ациклічним.
Теорема. Нехай х – допустимий план транспортної задачі, додатні елементи якого утворюють хоча б один замкнутий ланцюг. Тоді завжди від плану (Х) можна перейти до плану (У), в якому по крайній мірі на один ланцюг буде менше, при чому вартість перевози по плану У буде менша від вартості перевози по плану Х, під СХ, СУ – ми розуміємо скалярний добуток матриць СУСХ.
Доведення.
Нехай Х – допустимий план транспортної задачі, додатні компоненти якого утворюють замкнутий ланцюг.
Зафіксуємо одну із кліток даного ланцюга.
Розіб’ємо ланцюг Q на два під ланцюга , ??? до клітки, яким відповідають парні цифри.
кл., яким відповідають непарні цифри.
Поставимо у відповідність кожній під ланцюгову суму
Між цими двома сумами можна встановити співвідношення
Виберемо серед елементів парного під ланцюга min елемент. Тобто знайдемо . носить назву критичної маси, а перехід від плану Х до плану У зробимо за допомогою наступних формул.
Елемент Х позначимо і
Покажемо тепер, що якщо план Х був допустимим планом транспортної задачі, то план У також буде допустимим. Раз план Х був допустимим планом транспортної задачі , то план У буде допустимим планом Х, тому що якщо ми віднімаємо критичну масу від рядка, то ту ж саму критичну масу додаємо до стовпця, тому баланс по рядках і по стовпцях для У якщо виконувався для Х.
Зн. тепер в-ть перевози по плану У і покажемо, що ця вартість буде меншою або рівною вартості перевозом по плану Х.
(теорема доведена).
Зауваження 1.
Якщо у вихідному плані Х є декілька замкнутих ланцюгів, то з кожним з них ми поступаємо так само, як ми поступали з ланцюгом Q при доведенні теореми.
Зауваження 2.
З доведеної теореми слідує, що оптимально план транспортної задачі задачі слід шукати серед всіх ациклічних наборів.
Позначення 1.
Ациклічний набір для транспортної задачі якому відповідає m+n-1 заповнена клітка і разом з тим система лінійних незалежних векторів називається не виродженим базисним планом транспортної задачі.
Позначення 2.
Якщо базисному плану транспортної задачі відповідає менша, ніж m+n-1 клітка, то такий базисний план наз. виродженим планом.
??? 3.
Не вироджений базисний план транспортної задачі якому відповідає m+n-1 заповнена клітка називається вибором, а елемент ??? вартостей, що відповідають вибраним кліткам наз. Х – вибраним елементом.
Поставимо у відповідність кожній клітці матриці вартостей величину .
??? носить назву оцінки. Очевидно, що набір цих оцінок складає матрицю m x n. У зв’язку з таким підходом можна накреслити слідуючий план розв’язку транспортної задачі.
Для цього достатньо проаналізувати вільні клітки (визначити оцінки для вільних кліток).
Якщо величини , то план, який зв’язаний з даною матрицею оцінок є оптимальним.
Якщо серед кліток то відносно клітки з номером lk потрібно зробити процедуру, яку ми використовували при доведенні теореми, що дасть змогу від плану вартість перевози при цьому зменшиться. А так як число базисних планів є кінцеве, то за кінцеву кількість кроків ми зможемо відшукати оптимальний план транспортної задачі.
Про інваріантність виборів відносно еквівалентних матриць.
Нехай ми маємо дві транспортні задачі , при чому розміри обох m x n.
Вектори обмежень цих задач співпадають також, а – вектор запасів у пунктах в-ва, b – вектор споживання.
Теорема ??? плани задач співпадають.
Допустимо, що ми будуємо початок базисного плану цих задач методом північно-західного кута. Раз розміри задач співпадають, вектори обмежень також співпадають, тол зрозуміло, що початкові вибори цих задач будуть співпадати.
Початковий вибір для задачі позначимо і . Щоб довести нашу теорему потрібно показати, що якщо ми перейдемо від початкових виборів до наступних виборів цих задач, то ці наступні вибори будуть співпадати також.
???
Щоб довести виходячи з теорем. основ розподільчого методу достатньо показати, Що матриці оцінок задачі , тобто
Знайдемо матриці оцінок
Остачі суми = 0внаслідок того, що якщо ми деяке число додаємо до рядка, то те ж саме число ми віднімаємо від стовпця, що ??? тому, що якесь число додається до парного, що те ж саме число віднімається від