Математична структура Т-задач

Припустимо, що деякий однорідний продукт (вантаж), який зосереджено у m постачальників, по a_i одиниць у кожного (), потрібно перевезти n споживачам у кількості не менше як b_i одиниць кожному (). Відома вартість перевезення одиниці вантажу від і -го постачальника до j -го споживача c_ij. Необхідно знайти такий план перевезень продукції від постачальників до споживачів, за яким загальні витрати Z на транспортування були б мінімальними.

Для побудови математичної моделі такої задачі введемо матрицю плану перевезень X = (x_ij), елементи якої означають обсяг перевезень продукції від і -го постачальника до j -го споживача. Тоді для загальних транспортних витрат для обсягу продукції, що вивозиться від кожного поста­чаль­ника і для обсягу продукції, яка надходить до кожного із споживачів можна записати такі вирази:

Наведена система формул описує математичну модель класичної транспортної задачі. Згідно з економічним змістом транспортної задачі значення всіх сталих коефіцієнтів моделі, а саме запаси продукції у постачальників, потреби в продукції кожного споживача і транспортні витрати не можуть бути від’ємними, тобто

.

За такими припущеннями Т-задача завждимає розв’язок за умови, що загальний обсяг продукції у постачальників не менший від загальної потреби споживачів (теорема про розв’язність транспортної задачі):

Транспортна задача називається закритою, коли виконується балансова умова і, у відповідності з вищевказаною теоремою, завжди має розв’язок. В інших відпадках транспортну задачу називають відкритою, при цьому можливі такі два випадки.

1. Загальний запас продукції в постачальників перевищує загальні потреби з боку споживачів:

У даному випадку, якщо ввести до розгляду додаткового (n+1)-го фіктивного споживача з потребою

одиниць продук­ції, то відкрита транспортна задача перетвориться на закриту. При цьому питомі вартості перевезень за фіктивними маршрутами вважають такими, що дорівнюють нулю.

2. Загальний запас продукції в постачальників менший від загальних потреб з боку споживачів:

У таких випадках може виникати інша задача: як оптимальним чином перевезти наявну продукцію (можливо і недостатню для задоволення потреб). Така нова задача може бути розв’язана введенням фіктивного (m+1) постачальника із запасом продукції a_m+1. При цьому, питомі вартості перевезень за фіктивними маршрутами вважаються рівними нулю, а обсяги перевезень x_m+1,j за цими маршрутами розглядаються для відповідних споживачів як недопостачання продукції через її дефіцит. Умови транспортної задачі, зазвичай, записуються у табличному вигляді, як це показано у табл. 3.1.

Таблиця 3.1

Пункти відправлення (ПВ)	Пункти доставки (ПД)	Запаси аі
B1	…	Bk	…	Bn
A1	c11 x11	…	c1k x1k	…	C1n x1n	a1
…	…	…	…	…	…	…
Al	cl1 xl1	…	clk xlk	…	cln xln	aL
…	…	…	…	…	…	…
Am	cm1 xm1	…	cmk xmk	…	cmn xmn	am
Потреби bj	B1	…	bk	…	bn	a

3.2 Визначення початкового опорного плану Т-задачі

Розв’язання Т-задачі починається з побудови опорного плану. Опорний план містить не більше ніж m+n -1 (значення рангу системи обмежень Т-задачі) додатних компонент: невироджений план містить m+n- 1, а вироджений план – менше ніж m+n- 1. Є кілька простих способів знаходження початкового опорного плану Т-задачі, серед яких найпоширенішими є діагональний метод північно-західного кута, ме­тод мінімальної вартості і метод подвійних позначок.

Метод північно-західного кута. Назва методу пов’язана із тим, що на кожному кроці процедури алгоритму першою за­повнюється клітинка лівого верхнього кута незаповненої частини табли­ці. Алгоритм заповнення може бути описаний таким чином.

1. Знаходимо x₁₁ початкового плану, що дорівнює меншому з чисел a₁,b₁, тобто x₁₁=min(a₁,b₁), а всі інші елементи першого стовпця (якщо a₁>b₁, то x₁₁=b₁), або першого рядка (якщо a₁<b₁ то x₁₁=a_{1 )}, або і першого стовпця і першого рядка (якщо a₁=b₁, то x₁₁=a₁=b₁) матриці перевезень покладемо такими, що дорівнюють нулю. Визначимо a⁽¹⁾₁=a₁ - x₁₁, b⁽¹⁾₁=b₁ -x₁₁.

2. Далі розглянемо незаповнену частину таблиці після k ітера­цій, тобто ту частину, що містить ще не визначені елементи матриці пе­ревезень. Нехай її верхній лівий елемент є x_lm (l+m=k+2). Вико­наємо (k+1) ітерацію. Повторимо всі кроки першої ітерації, тобто знайдемо

Якщо a^(k)< b^(k) то заповнюємо нулями l -й рядок, починаючи з (m+1)-го елемента. Якщо ж a^(k) >b^(k) то заповнюємо нулями m -й стовпець. Коли ж х_lm=a^(k)=b^(k), то нулями заповнюються як l -й рядок, так і m -й стовпець. Обчислюємо , . На цьому (к+1) ітерація закінчується.

Через обмеженість числа елементів a_i, i=1,m та b_j, j=1,n описаний алгоритм скінченний. Так, наприклад, для задачі, вихідні дані якої задані в табл. 3.2, початковий опорний план, побудований методом північно-західного кута, ілюструється у табл. 3.3.

Метод мінімальної вартості. Метод полягає в тому, що на першому кроці всі клітинки транспортної таблиці, де на­ведені елементи матриці вартостей, нумерують, починаючи з найменшого в порядкуїх зростання (цифри в дужках). На другому кроці заповнюємо клітинку перевезеннями, починаючи з клітинки з найменшою цифрою, потім заповнюємо клітинку, яка має найменший номер після другого кроку і т.д. При цьому для відповідних вибраних клітинок правила заповнення рядків і стовпців аналогічні методу північно-західного кута.

Таблиця 3.2

ПВ	ПД	ai
B1	B2	B3	B4
A1
A2
A3
bj

Таблиця 3.3

ПВ	ПД	ai
B1	B2	B3	B4
A1
A2
A3
bj

Опорний план Т-за­дачі для попереднього прикладу, і який побудовано методом мінімаль­ної вартості, наведено у табл. 3.4.

Таблиця 3.4

ПВ	ПД	ai
B1	B2	B3	B4
A1	(10)7	(6)4	(3)2	(4)3
A2	(1)1	(7)5	(8)6	(2)2
A3	(5)3	(12)8	(11)7	(9)6
bj

Метод подвійних позначок. Суть методу полягає в тому, що на першому кроці в кожному рядку транспортної таблиці позначають зірочкою найменший елемент с_ij, а потім позначають зірочкою найменший елемент у кожному стовпці цієї таблиці. Таким чином, маємо клітинки з двома позначками, з однією позначкою та без позначок.

На другому кроці знаходимо перевезення для однієї із клітинок з двома позначками, потім, якщо їх вже не вистачає, для клітинок із однією позначкою, а на останніх кроках для клітинок, які мають найменшу вартість.

У табл. 3.5 наведено опорний план, що побудований за вищенаведеним методом подвійних позначок.

Таблиця 3.5

ПВ	ПД	ai
B1	B2	B3	B4
A1		* 4	** 2
A2	** 1			* 2
A3	* 3
bj

Слід відзначити, що методи мінімальної вартості та подвійних позначок є модифікацією діагонального методу і в більшості випадків дають ближчий до оптимального початковий план.

3.3 Властивості опорних планів Т-задач

Ланцюгом називають будь-яку послідовність клітинок таблиці Т-за­да­чі, якщо кожна пара клітинок міститься або в одному рядку, або ж в одному стовпці таблиці так, що жодні три чи більше клітинок послідовності не є клітинками одного рядка або одного стовпця. Ланцюг, перша та остання клітинки якого знаходяться в одному рядку або в одному стовпці, утворюють цикл.

Сукупність усіх базисних клітинок та однієї вільної клітинки транспортної задачі завжди утворює цикл. Позначимо приєднану небазисну клітинку знаком «+», наступну в утвореному циклі (базисну клітинку) – знаком «-», третю – знаком «+» тощо. Оскільки число клітинок циклу парне, то він розпадається на два півцикли з однаковою кількістю клітинок – від’ємний півцикл, утворений клітинками із знаком «-», і додатний, утворений клітинками із знаком «+».

Серед базисних клітинок від’ємного півциклу виберемо ту, яка містить найменше перевезення q. Якщо тепер змінити величини перевезень у клітинках циклу на цю величину (в усіх додатних клітинках перевезення збільшити перевезення на значення q, а в усіх від’ємних клітинках зменшити перевезення на значення q), то у результаті дістанемо новий опорний план. Йому буде відповідати і нове значення загальної вартості перевезень.

Метод викреслювання. Метод застосовується під час побудови циклу. На кожному кроцi методу в транспортній таблиці викреслюється або рядок, або стовпець, які в подальшому ігноруються. Викреслювати належить рядки (стовпцi), які мають тільки одну базисну клітинку. Невикресленi клітинки транспортної таблиці утворюють цикл.