Так як мінор любого порядку для матриці умов транспортної задачі є завжди 0 або , то зрозуміло, що розв’язки транспортної задачі будуть цілочисельні.

Методи побудови початкового базисного плану в транспортній задачі.

а) метод північно-західного кута;

б) метод 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 – вектор споживання.

Теорема ??? плани задач співпадають.

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

Початковий вибір для задачі позначимо і . Щоб довести нашу теорему потрібно показати, що якщо ми перейдемо від початкових виборів до наступних виборів цих задач, то