., v n , - u 1 , - u 2 ., - u m , при яких
якщо, (1.12)
якщо 0 <, (1.13)
якщо. (1.14)
Сенс умов оптимальності (1.12) - (1.14) полягає в наступному:
якщо прирощення вартості продукту v j - u j менше транспортних витрат c ij , то таке перевезення збиткова, а тому. Якщо ж прирощення вартості продукту v j - u j більше транспортних витрат c ij (3.1.14), то ця перевезення прибуткова, а тому її величина повинна бути максимальною, тобто . p> Таким чином, теорема 3.3 по суті виражає принцип рентабельності для T d - завдання.
Відкриті транспортні моделі. Існує ряд практичних завдань, в яких умова балансу не виконується. Такі моделі називаються відкритими. Можливі два випадки:
1)
2)
У першому випадку повне задоволення попиту неможливо.
Таке завдання можна привести до звичайної транспортної задачі наступним чином. Позначимо через величину штрафу через незадоволення запитів на одиницю продукту в пункті B j .
Тоді потрібно мінімізувати
(1.15)
за умов
В
де - незадоволений попит.
Задачу (3.1.15) призводять до звичайної Т-задачі введенням фіктивного пункту виробництва А m +1 , з обсягом виробництва і транспортними витратами У такому випадку Т-завдання буде мати вигляд
мінімізувати
за умов
В
У знайденому рішенні х опт вважаємо всі перевезення з фіктивного пункту А m +1 рівними нулю, тобто . p> Розглянемо тепер другий випадок. Введемо фіктивний пункт B n +1 з обсягом попиту. Нехай - це збитки (штраф) у пункті А и за одиницю невивезеного продукту. Означимо через ці , n +1 = питомі транспортні витрати на перевезення одиниці продукту з А и у В n +1 . Тоді відповідна Т-завдання запишеться так:
мінімізувати (1.16)
за умов
(1.17) - (1.18)
У знайденому рішенні всі перевезення у фіктивний пункт В n +1 вважають рівними нулю.
Опорні плани Т-завдання
Опорним (базисним) планом Т-задачі називають будь-яке її допустиме, базисне рішення. Поняття опорного плану має наочну геометричну інтерпретацію.
Послідовність комунікацій
(1.19)
називають маршрутом, що з'єднує пункти (рис. 2).
...
В
В
. p> Рис. 2
Використовуючи маршрут, складений з комунікацій, можна здійснити перевезення продукту з пункту в пункт, проходячи через пункти.
У процесі цього руху комунікації, що стоять на парних місцях у (1.19), будуть пройдені в протилежному напрямку.
Маршрут (1.19), до якого додана комунікація називається замкнутим маршрутом або циклом.
Спосіб перевірки довільного плану Т-задачі на опорность, заснований на наступних двох теоремах (прямого і зворотного).
Теорема 4. Система, складена з векторів Т-задачі, є лінійно незалежної тоді і тільки тоді, коли з комунікацій, відповідних цим векторах, не можна скласти замкнутий маршрут.
Доказ. Необхідність . Нехай вектори лінійно незалежні. Якби існував замкнутий маршрут з комунікацій і, то, очевидно, починаючи рух з пункту і послідовно проходячи всі пункти за останньою комунікації ми повернемося в початковий пункт. Тоді справедливе рівність
(1.20)
яке вказує на лінійну залежність векторів
.
Отримане протиріччя доводить необхідність умов теореми 4.
Достатність . Припустимо, що з комунікацій, що відповідають векторам системи R, не можна скласти замкнутий маршрут. Доведемо, що в такому випадку R - лінійно незалежна система. Якщо припустити противне, тобто лінійну залежність векторів системи R , то існують такі числа, серед яких не усі нулі, для яких виконується умова
. (1.21)
Нехай, наприклад. Перенесемо тоді відповідний вектор вправо і отримаємо
, (1.22)
де Е 1 утворюється викреслюванням в Е пари індексів (). Компонента з номером у правій частині (3.1.22) не дорівнює нулю.
Отже, це ж відноситься і до лівої частини цього рівності, тобто серед
векторів знайдеться хоча б ...
