14. Постановка транспортної задачі, її мат. Модель та властивості.

Припустимо,існує m пунктів відправлення продукції:A1...Am у яких сконцентровано запаси певного вантажу в к-ті a1...am та n пунктів призначення B1...Bn з потребами b1...bn .Загальні запаси=занальним потребам. (1)

Задана матриця, С=(С ij), де С ij-вартості перевезень одиниці вантважу від і-го постачальника j-му споживачеві. Матрицю Сij задано у вигляди:

Треба скласти такий план перевезень, щоб забезпечити виконання всіх замовлень, і щоб сумарна вартість перевезень була мінімальна (2), де Xij – це к-ть товару, що перевозиться з пункту Аі в пункт Bj

Мат модель ТЗ:

L=

1)cумарна велечина вантажу, який напр.. з кожного пункту відправлення в усі пункти призначення має дорівнювати запасам вантажу в данному пункті

2)сумарна к-ть вантажу, що перевозиться в кожний пункт призначення з усіх пунктів відправлення має дорівнювати за замовленням для даного пункту

3)дозволяє спростити її розв’язання

15. Властивості т-задачі

1)Сума перевезень у кожному рядку таблиці має дорівнювати запасу данного ПВ

2)сума перевезень у кожному стовпчику табл.. має дорівнювати розміру замовлення відповідного ПП

3)Сумарна вартість перевезень мінімальна

20. Виродження у т-задачах

Невиродженій план- це коли кількість базових клітинок у таблиці дорівнює n+m-1.

Вироджений план- це такий план, коли деякім змінні дорівнюють нулю.

Тобто кількість базових елементів не співпадає з рангом. В цьому випадку вводяться нульові базові змінні. Дійсно, те, що в базових клітинках перевезення строго додатні, є не суттєво: достатньо, щоб вони були невід’ємними.

Алгоритм вирішення виродженої Т-задачі такй же як і для невиродженої.

Тобто побудова опрного плану, перетворення планів Т-задач, використання методу потенціалів

для всіх базових клітинок;

для всіх вільних клітинок.

16. Побудова початкового опорного плану.

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

Покажемо, як можна побудувати опорний план перевезення вантажу. Для цього використовують різні способи.

2 найпошириніші методи:

1. Пн-Зх кута

2. Мінімальної вартості

Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел а1 та b1. Далі переходять до наступної клітини в цьому ж рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнення таблиці у правій нижній клітинці. У такий спосіб значення поставок будуть розташовані по діагоналі таблиці.

ПП ПВ	В1	В2	В3	В4	В5	В6	Запаси ai
А1	c11 q1	c12 q2	с13	c14	с15	с16	a1
А2	c21	c22 q3	с23	c24	с25	с26	a2
А3	с31	с32 q4	с33 q5	с34 q6	с35	с36	а3
А4	с41	с42	с43	с44 q7	с45 q8	с46 q9	а4
А5	с51	с52	с53	c54	с55	с56 q10	а5
Замовлення bj	b1	b2	b3	b4	b5	b6

Як видно з табл. розподіл запасів закінчено: кожен пункт призначення одержав вантаж згідно зі своїм замовленням. Це випливає з того, що сума перевезень у кожному рядку дорівнює відповідному запасу, а у стовпчику – замовленню.

Таким чином, складено план перевезень, що задовольняє балансові рівняння вигляду.

та

Одержаний розв’язок не тільки допустимим, а й опорний розв’язок ЗТТ.

Клітинки таблиці , в яких стоять ненульові перевезення – базові, їх кількість задовольняє умову r= n+m-1=10. Інші клітинки – вільні (порожні), їх кількість (m-1)(n-1)=20. Отже, план опорний і поставлене завдання побудови опорного плану виконане.

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

План перевезень складають так, щоб задовольнялись рівняння:

та

Кількість базових клітинок задовольняється за умови r= n+m-1 та вільних -(m-1)(n-1).