транспортна задача
Якщо загальний запас продукції (вантажу) у постачальників дорівнює загальній потребі споживачів, то транспортна задача буде закритою. У разі, коли потреби споживачів перевищують можливості поставок, або коли запаси вантажу перевищують потреби споживачів, маємо відкриту транспортну задачу. Відкриту транспортну задачу зводимо до закритої шляхом введення мнимого постачальника в першому випадку, або уявного споживача - у другому. "Можливості поставок" мнимого постачальника або "потреби" мнимого споживача складають різницю між загальними запасами і загальними потребами. Тарифи на поставку вантажу від уявного постачальника реальним споживачам, або від реальних постачальників уявному споживачеві приймаються рівними нулю, так як реально вантаж в цьому випадку не поставляється.
Крім того, в завданню можуть бути і деякі інші обмеження. Наприклад, можуть бути привілейовані споживачі, яким вантаж повинен бути поставлений в повному обсязі, або привілейовані постачальники, від яких вантаж повинен бути вивезений повністю. Нехай в цьому завданню привілейованими споживачами є споживачі і. Щоб виключити випадок, коли привілейований споживач не отримає вантаж в повному обсязі, тариф на поставку вантажу від уявного постачальника до привілейованого споживачеві приймаємо "високим" (), що перевищує будь-який інший тариф в будь-яке число раз.
Вихідний опорний план зазвичай складають або методом північно-західного кута або методом мінімального елемента.
При складанні опорного плану методом північно-західного кута заповнення клітин розподільчої таблиці починається з клітини. Передбачається поставка від першого постачальника до першого споживача в максимальному обсязі (або до задоволення потреб першого споживача, або до вичерпання можливостей першого постачальника). Далі заповнюються клітини, розташовані поблизу діагоналі таблиці. Закінчується складання опорного плану в правому нижньому кутку таблиці.
Нижче наводиться приклад складання опорного плану методом північно-західного кута.
Плануємо поставку від постачальника споживачеві до задоволення його потреби у вантажі. Залишок запасу вантажу у першого постачальника поставляємо другого споживачеві. Так як другої споживачеві необхідна більша кількість вантажу, ніж залишилося у першого постачальника, то відсутню частину вантажу йому поставляє другий постачальник. Залишок вантажу після поставки другого споживачеві другий постачальник поставляє третього споживачеві і т.д. Закінчується побудова вихідного опорного плану методом північно-західного кута заповненням клітини.
Так як при цьому методі складання вихідного опорного плану ми взагалі не враховували тарифи перевезень, то цей опорний план навряд чи буде оптимальним. Перевірку складеного плану на оптимальність проводимо методом потенціалів. Необхідно знайти потенціали всіх споживачів і постачальників. У нашому випадку треба визначити потенціали чотирьох постачальників і п'яти споживачів (всього 9 потенціалів).
Вихідний опорний план методом північно-західного кута (нульова ітерація).
Для заповнених клітин сума потенціалів постачальника і споживача дорівнює тарифу поставок. Всього заповнене 8 клітин і можемо скласти тільки вісім рівнянь для визначення 9 параметрів. Тому потенціал приймаємо довільно. Нехай він дорівнює 0. Тоді:. . = 4-0 = 4.. . . і т.д. Після знаходження потенціалів всіх постачальників і споживачів знаходимо потенціали вільних клітин. Потенціал вільної клітини дорівнює сумі потенціалів постачальника і споживача. (). Потенціали поміщаємо в нижньому правому куті вільних клітин. Якщо хоча б для однієї вільної клітини. то план не оптимальний і його слід покращувати, складаючи цикл перерахунку плану. Цикл перерахунку складається для вільного осередку з максимальним перевищенням потенціалу над тарифом. Цикл перерахунку являє собою замкнуту ламану лінію, що складається з горизонтальних і вертикальних ланок. Вершини циклу, крім вільної клітини, для якої складається цикл, обов'язково повинні перебувати в заповнених клітинах. Для кожної вільної клітини можна скласти цикл і притому тільки один. Вершин циклу послідовно, починаючи з вільною клітини, присвоюються знаки і. Знаходиться мінімальна кількість вантажу в «негативних» клітинах і його перерозподіляємо по циклу, віднімаючи від «негативних» клітин і додаючи до «позитивним». В інших клітинах, які не є вершинами циклу, кількість вантажу залишається незмінним. Отримаємо новий опорний план, (1 ітерація) який також перевіряємо на оптимальність. Всі потенціали при цьому розраховуємо заново.
Розподільна таблиця. Перша ітерація.
Оскільки потенціал перевищує тариф. то для вільної клітини знову складаємо цикл перерахунку (друга ітерація). Вершини циклу розташовуються в осередках. . . . «Негативними» клітинами є клітини і. Мінімальна кількість вантажу знаходиться в осередку і становить 200 одиниць. Ця кількість вантажу перерозподіляємо по ціклу.Получім план другої ітерації, який також не є оптимальним.
Розподільна таблиця. Друга ітерація.
Розподільна таблиця. Третя ітерація.
Так як в розподільній таблиці третьої ітерації немає перевищення потенціалів вільних клітин над потенціалами цих клітин, то в ній
представлений оптимальний план перевезень, що забезпечує мінімальні сумарні транспортні витрати. Вони складуть:
300 5 + 300 4 + 250 4 + 50 5 + 250 5 + 3 300 + 350 4 + 50 0 = 7500.
Транспортна задача вирішена. Складено оптимальний план перевезень:
Оптимальний план перевезень, що забезпечує мінімум транспортних витрат.
Загальний обсяг поставок 1 800 + 50. од. Мінімальна вартість перевезень - 7500 ден. одиниць.
Складемо вихідний опорний план методом мінімального елемента. За цим методом послідовно планується поставка споживачам максимальної кількості вантажу по мінімально доступними тарифами. Часто план, складений цим методом, буває оптимальним.
Таблиця 1 Вихідний опорний план методом мінімального елемента (нульова ітерація).
Якщо планується поставка вантажу по конкретному тарифу, цей тариф відзначаємо в розподільній таблиці. У центральній частині клітини відзначаємо планований обсяг поставки. Також зазначаємо залишок вантажу у постачальника після запланованої поставки, або скільки вантажу залишилася отримати даному споживачеві. Якщо якийсь тариф вже не може бути використаний в подальшому, це також відзначаємо в розподільній таблиці. У табл. 2 записуємо порядок складання опорного плану.
Таблиця 2. Порядок складання вихідного опорного плану методом мінімального елемента.
Отриманий опорний план перевіряємо на оптимальність методом потенціалів. Так як треба визначити 9 потенціалів постачальників і споживачів, а заповнених клітин тільки 7, то два потенціалу можна вибрати довільно. Спочатку довільно вибираємо тільки потенціал = 0. Тоді = 9; = 4, = 8. З рівнянь. . = 3 - (- 4) = 7. Для знаходження потенціалу клітку вважаємо заповненої з об'ємом поставки = 0. Тоді: 3-0 = 3. З рівняння = 3-3 = 0. Таким чином, знайдені потенціали всіх постачальників і споживачів.
Далі знаходимо потенціали всіх вільних клітин, відзначаємо випадки перевищення потенціалів над тарифами, і для вільної клітини з максимальним перевищенням потенціалу над тарифом, складаємо цикл перерахунку плану. Перерахунок плану поставок виробляємо до отримання оптимального плану