Постановка і основні властивості транспортної задачі
Транспортна задача (Т-задача) є однією з найбільш розповсюджених спеціальних задач ЛП. Приватні постановки задачі розглянуті поруч фахівців з транспорту, наприклад О.Н. Толстим [18; 59].
Перша сувора постановка Т-задачі належить Ф. Хичкоку, тому в зарубіжній літературі її називають проблемою Хічкока.
Перший точний метод вирішення Т-задачі розроблений Л.В. Канторовичем і М.К. Гавуріним.
Постановка Т-задачі. Нехай в пунктах А 1 , ..., A m виробляють деякий однорідний продукт, причому обсяг виробництва в пункті A i становить a i одиниць, i = 1, ..., m. Припустимо, що даний продукт споживають в пунктах B 1 ., B n , a обсяг споживання в пункті В j становить b j одиниць j = 1., N. Припустимо, що з кожного пункту виробництва можливе транспортування продукту в будь пунктпотребленія. Транспортні витрати по перевезенню одиниці продукції з пункту A i в пункт В j дорівнюють c ij (i = 1., M; j = 1., N). Завдання полягає у визначенні такого плану перевезень, при якому запити всіх споживачів У j повністю задоволені, весь продукт з пунктів виробництва вивезений і сумарні транспортні витрати мінімальні.
Умови Т-задачі зручно представити у вигляді табл. 1.1.
Таблиця. 1.1.
Пункт споживання
Пункт виробництва
B 1
B 2
.
B n
B j
a i
A 1
C 11
C 12
.
C 1n
a 1
-->>
A 2
C 21
C 22
.
C 2n
a 2
A m
C m1
C m2
.
C mn
a m
A i
b j
b 1
b 2
.
b n
Обсяг виробництва
Обсяг споживання
Нехай кількість продукту, перевозиться з пункту A i в пункт В j .
Потрібно визначити безліч змінних , i = 1., m, j = 1., n, що задовольняють умовам
(1.1)
(1.2)
і таких, що цільова функція
(1.3)
досягає мінімального значення.
Умова (1.1) гарантує повний вивіз продукту з усіх пунктів виробництва, а (1.2) означає повне задоволення попиту у всіх пунктах споживання.
Таким чином, Т-задача являє собою задачу ЛП з числом змінних, і (m + n) числом обмежень рівностей.
Змінні зручно задавати у вигляді матриці
(1.4)
Матрицю X , що задовольняє умовам Т-задачі (1.1) і (1.2) називають планом перевезень, а змінні - перевезеннями. План , при якому цільова функція мінімальна, називається оптимальним, а матриця З = - матрицею транспортних витрат.
Графічний спосіб завдання Т-задач показаний на рис. 1
Рис. 1
Відрізок A i B j називають комунікацією. На всіх комунікаціях ставлять величини перевезень x ij .
Вектор P ij , компоненти якого складаються з коефіцієнтів при змінних x ij в обмеженнях (3.1.1) і (3.1.2), називають вектором комунікацій:
Вводять також вектор виробництва-споживання P 0 , де
.
Тоді обмеження (3.1.1) і (3.1.2) можна записати у векторній формі
, (1.5)
Властивості транспортної задачі
1. Для розв'язання Т-задачі необхідно і достатньо, щоб виконувалася умова балансу
, (1.6)
тобто, щоб сумарний обсяг виробництва дорівнював обсягу споживання.
Доказ. Нехай змінні x ij , i = 1., M; j = 1., N задовольняють умовам (1.1), (1.2). Підсумовуючи (1.1) по , а (1.2) по , отримаємо:
. я
Звідси , що і доводить необхідність умови балансу Т-задачі.
Нехай справедливо умова (1.6). Позначимо , де .
Неважко довести, що х ij складає план задачі. Дійсно
Таким чином, доведена достатність умови балансу для рішення Т-задачі.
2. Ранг системи обмежень (1.1), (1.2) дорівнює
Доказ. Так як кількість рівнянь (1.1), (1.2) одно , то ранг цієї системи . Нехай, набір задовольняє всім рівнянням, крім перших. Покажемо, що він задовольняє також і першому рівнянню.
Очевидно
Так як
, то
, звідси
,
Враховуючи умову балансу (1.6), отримаємо
,
тобто перше рівняння системи (1.1) теж задовольняється.
Таким чином, ранг системи рівнянь (1.1), (1.2) .
Доведемо, що ранг системи рівнянь (1.1), (1.2) дорівнює точно . Для цього складемо матрицю з перших ( ) компонентів векторів
Очевидно, що ця матриця не вироджена. Тому вектори { } утворюють базис. Так як базис системи складається з ( ) векторів, то й ранг системи (1.1), (1.2) .
Двоїста транспортна задача ( - завдання). Для Т-задачі, як і для будь-якої задачі ЛП, існує двоїста задача до неї -завдання.
Змінні -задачі позначимо v 1 , v 2 ., v n , - u 1 , - u 2 ., - u m ...
Теорема 1. -задача має рішення і якщо X опт = ,
- оптимальні рішення T і -завдання відповідно, то
. (1.7)
Якщо врахувати, що u i - вартість одиниці продукції у пункті А І, а v j - вартість після перевезення в пункт B j , то сенс теореми буде такою:
Сумарні транспортні витрати при оптимальному плані перевезень дорівнюють приросту сумарної вартості продукції після її перевезення в пункти споживання.
Змінні u i і v j н...
