Постановка та основні властивості транспортної задачі
Транспортна задача (Т-завдання) є однією з найбільш розповсюджених спеціальних завдань ЛЗ. Приватні постановки завдання розглянуті поруч фахівців з транспорту, наприклад О.Н. Толстим [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) числом обмежень рівностей. p> Змінні зручно задавати у вигляді матриці
(1.4)
Матрицю X , що задовольняє умовам Т-задачі (1.1) і (1.2) називають планом перевезень, а змінні - перевезеннями. План, при якому цільова функція мінімальна, називається оптимальним, а матриця З = - матрицею транспортних витрат.
Графічний спосіб завдання Т-задач зображений на рис. 1
В
Рис. 1
Відрізок A i B j називають комунікацією. На всіх комунікаціях ставлять величини перевезень x ij . p> Вектор 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). Підсум...
