Класична транспортна задача. Особливості транспортної задачі

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

Постачальники	Споживачі	Наявність вантажу
		…	п
		C11		C12	…		C1n	a1
X11		X12		X1n
		C21		C22	…		C2n	a2
X21		X22		X2n
…	...	...	.	...	...
m		C1m		C2m	…		Cmn	am
X		X		X
Потреба у вантажі	b1	b2	…	bn	Z Z

Позначення:

- номер постачальника; = 1, 2,3,… ;

- номер споживача; = 1, 2,3,… n;

Х - кількість вантажу, що перевозиться від -го постачальника до - споживача;

C - собівартість перевезення вантажу від з -го постачальника до - го споживача (або відстань між -им постачальником і -им споживачем);

а - наявність вантажу у -го постачальника;

b - потреба у вантажі -го споживача.

Задача полягає у відшуканні такого плану перевезень ,

який би забезпечував мінімум загальної вартості перевезень (або мінімум відстаней) при повному задоволенні запитів постачальників і споживачів.

Від таблиці переходимо до структурної моделі задачі, представленої в аналітичному вигляді.

Модель має вигляд:

При виконанні умов:

1. Умова повного задоволення постачальників:

2. Умова повного задоволення споживачів:

3. Умова позитивності змінних:

Для вирішення задачі необхідно зібрати наступну інформацію:

1. Кількість вантажу у кожного з постачальників

2. Кількість вантажу, яка необхідна кожному споживачу

Відстані між постачальниками і споживачами або тарифи (витрати на перевезення одиниці вантажу від i - го постачальника до j – ого споживача).

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

Через особливості транспортної задачі для її вирішення розроблені спеціальні методи: потенціалів, диференціальних рент, індексний, угорський, апроксимації Фогеля, загальний розподільний.

Особливості транспортної задачі полягають в наступному:

1. Коефіцієнтами при невідомих в обмеженнях обох типів є тільки одиниці.

2. Всі показники (техніко-економічні коефіцієнти і вільні члени) в обмеженнях обох типів мають одну і ту ж одиницю вимірювання, а коефіцієнти при невідомих в критерії оптимальності (відстань або вартість) задані з розрахунку на ту ж одиницю вимірювання (центнер, тонну).

3. Матриці, складені із змінних обох типів обмежень є транспонованими по відношенню одна до одної.

9.3. Постановка задачі по плануванню перевезення різних вантажів одним видом транспорту. 3ведення її до класичної задачі

Розглянемо різновиди транспортних задач і способи зведення їх до класичної транспортної задачі.

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

Тоді деяка частина потреб може бути задоволена наявними сортами вантажу, але в різних кількостях з урахуванням властивостей кожного виду вантажу і характеру потреб. Виникає необхідність рішення транспортної задачі для неоднорідного вантажу. Така задача приводиться до задачі про перевезення умовно однорідного вантажу. Розглянемо таку задачу.

Не порушуючи спільності міркувань, але з метою скорочення розмірів задачі включимо в неї 2 пункти відправлення A1 і A2 і два пункти споживання B1 і B2. Кожний з постачальників має два види вантажу (2 сорти пшениці), а кожний із споживачів вимагає певну кількість пшениці I і II сорту. Таким чином, кожний з пунктів - постачальників і споживачів можна розділити на 2 пункти по виду вантажу. Для постачальників це будуть підпункти A11, А12 і А21, А22, а для споживачів - В11 B12, В21, В22 - де перший індекс номер пункту, а другий номер вантажу.

Одержимо задачу, яку представляємо таблицею

Споживачі Постачальники	В1	В2	Наявність вантажу
В11	В12	В21	В22
А1	А11	С11	С11	С12	С12	а11
А12	С11	С11	С12	С12	а12
А2	А21	С12	С12	С22	С22	а21
А22	С12	С12	С22	С22	а22
Потреба у вантажу	в11	в12	в21	в22

Виразимо весь вантаж через вантаж II сорту. Для цього введемо коефіцієнт взаємозамінності ג L, що показує скільки одиниць вантажу 1 сорту відповідає одиниці вантажу 2 сорту. Так, якщо J одиниць вантажу I сорту можна замінити L одиницями вантажу II сорту, тоді а₁₁ одиниць вантажу I сорту будуть рівні jla₁₁ одиницям вантажу сорту. Але у такому разі вартість перевезення одиниці вантажу сорту (або відстань) зменшиться в ג раз і стане рівною;

Задача має вигляд:

Споживачі Постачальники	В1	В2	Наявність вантажу
В11	В12	В21	В22
А1	А11	С11/ג	М	С12/ג	М	גа11
А12	М	С11	М	С12	а12
А2	А21	С12/ג	М	С22/ג	М	גа21
А22	М	С12	М	С22	а22
Потреба у вантажу	גв11	в12	גв21	в22

Задача зведена до звичайної транспортної задачі з блокуваннями - заборонами даного виду перевезень (M, - дуже велика собівартість перевезення, або дуже велика відстань) по перевезенню немов однорідного вантажу одним видом транспорту і може бути вирішена будь-яким з методів рішення класичної транспортної задачі. Після рішення задачі необхідно перейти до вантажу першого сорту, помноживши на ג поставки вантажу першого сорту, виражені через вантаж II сорту.

Постановка задачі по плануванню перевезення різних вантажів різними видами транспорту

При плануванні перевезень вантажів різних видів різними видами транспорту задача ускладнюється. Проте її можна звести до звичайної транспортної задачі.

Як і в попередньому случає, маємо два пункти постачальників A1, A2,, AІ – де І номер постачальника, С - вид транспорту, j - номер споживача, l - вид вантажу.

Розділимо кожний з пункту постачальників на два підпункти A11, A12, А21, А22 по видам транспорту, а кожний з пунктів покупців на два підпункти B11, B12, В21 і В22 по видах вантажу. Біля підпунктів постачальників перший індекс - номер пункту, другий - вид транспорту, біля підпунктів споживачів перший індекс-номер пункту, другий - вид вантажу.

Задача має вигляд:

Споживачі Постачальники	В1	В2	Наявність вантажу
В11	В12	В21	В22
А1	А11	а1111 с1111 х1111	а1112 с1112 х1112	а1121 с1121 х1121	а1122 с1122 х1122	а11
А12	а1211 с1211 х1211	а1212 с1212 х1212	а1221 с1221 х1221	а1222 с1222 х1222	а12
А2	А21	а2111 с2111 х2111	а2112 с2112 х2112	а2121 с2121 х2121	а2122 с2122 х2122	а21
А22	а2211 с2211 х2211	а2212 с2212 х2212	а2221 с2221 х2221	а2222 с2222 х2222	а22
Потреба у вантажу	в11	в12	в21	в22

На відміну від попередньої задачі в цій відома ще величина а_ikjl - вантажопідйомність транспорту по видах і залежно від вантажу.

Для того, щоб звести цю задачу до класичної транспортної задачі, необхідно зробити наступне:

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

2. Різні вантажі через коефіцієнт замінюванності зводяться умовно до одного виду (у разі однорідності вантажів) або задача розпадається на два самостійних (у разі неоднорідності вантажів).

3. Від чотирьохіндексної задачі переходять до двохіндексної шляхом заміни змінних типу: II - I, 21 - II; 12 - III; 22- IV. і т.д. В цьому випадку і для позначення змінних вибирається інший символ.

Задача прийме вигляд:

Споживачі Постачальники	В1	В2	Наявність вантажу
В11	В12	В21	В22
А1	АІ	а11 с11 х11	а12 с12 х12	а13 с13 х13	а14 с14 х14
АІІ	а21 с21 х21	а22 с22 х22	А23 с23 Х23	А24 с24 Х24
А2	АІІІ	А31 с31 Х31	А32 с32 Х32	А33 с33 Х33	А34 с34 Х34
АІV	А41 с41 Х41	А42 с42 Х42	А431 с43 Х43	А44 с44 Х44
Потреба у вантажу	в1	в2	в3	в4

Задача розв'язується будь-яким з методів рішення класичної транспортної задачі. Після рішення задачі необхідно перейти до первинних позначень.