изначення B n +1 , якому пріпішем фіктивну заявку, рівну надлишку запасів над заявками
b n +1 = Г… а i - ГҐ b j (де i = 1, ..., m; j = 1, ..., n),
а вартість перевезень з усіх пунктів відправлення у фіктивний пункт призначення b n +1 будемо вважати рівною нулю. Введенням фіктивного пункту призначення B n +1 з його заявкою b n +1 ми зрівняли баланс транспортної задачі, і тепер її можна вирішувати, як звичайну транспортну задачу з правильним балансом.
Транспортна задача з надлишком заявок.
Це завдання можна звести до звичайної транспортної задачі з правильним балансом, якщо ввести фіктивний пункт відправлення A m +1 із запасом a m +1 рівним невистачаючому запасу, і вартість перевезень з фіктивного пункту відправлення в усі пункти призначення прийняти рівною нулю. br/>
6. Завдання, двоїста до транспортної.
Побудуємо завдання, двоїсту до транспортної. З цією метою згадаємо, що кожному пункту відправлення та призначення відповідає певне обмеження
(6.1)
В br/>
У той же час кожному обмеженню з (6.1) зіставляється певна невідома в двоїстої завданню. Тим самим встановлюється відповідність між усіма пунктами і і всіма невідомими двоїстої завдання.
Позначимо невідому в двоїстої завданню, що відповідає пункту відправлення, через, а пунктом призначення - черезВ . p> Кожному невідомому в транспортній задачі відповідає обмеження, що зв'язує невідомі в двоїстої завданню. Невідоме входить рівно в два обмеження системи (6.1): одне з них відповідає пункту, а інше - пункту. В обох цих рівняннях коефіцієнт при дорівнює 1. Тому відповідне обмеження в двоїстої завданню має вигляд
В В
(6.2)
br clear=ALL>
.
Права частина нерівності (6.2) дорівнює, тому що саме з цим коефіцієнтом невідома входить до мінімізіруемую формулу (2.4).
оптимизируемого форма двоїстої задачі має вигляд
(6.3)
В br/>
Таким чином, завдання двоїста до транспортної формулюється наступним чином. При обмеженнях (6.2) максимізувати формулу (6.3). Підкреслимо, що знак значень невідомих і може бути довільним.
Припустимо, що нам відомо деякий допустимий базисне рішення транспортної задачі, в якому всі базисні невідомі суворо позитивні. Це рішення оптимально лише в тому ...
