Початкові дані

Математична формалізація транспортної задачі

Математична постановка транспортної задачі формулюється наступним чином: найти таке невід’ємне рішення системи лінійних рівнянь:

Х₁₁ + … + Х_1j + … + Х_in = A₁

Х₂₁ + Х_2j + … + Х_2n = A₂

------------------------------------------------------------------------------------

Х_m1 + … + Х_mj + … + Х_mn = A_m

Х₁₁ + Х₂₁ + … + Х_m1 = B₁

------------------------------------------------------------------------------------

Х_1j + Х_2j + … + Х_mj = Bj

-------------------------------------------------------------------------------------

Х_1n + Х_2n + … + Х_mn = B_n

Х_1i> 0; Х_1n> 0; Х₂₁> 0; … Х_2n> 0; … Х_m1> 0; … Х_mn> 0

при якому функція мети, матиме мінімального значення:

С_min = (С₁₁Х₁₁ + С₁₂Х₁₂ + … + С_1jХ_1j + С_1nХ_1n +) +

(СХ₂₁ + СХ₂₂ + … + С_2jХ_2j) + … + (С_i1 Х_i1 + С_i2 Х_i2 + … + С_ij Х_ij +

+ С_in Х_in) +… + (С_m1Х_m1 + С_m2Х_m2 + … + С_mjХ_mj + … + С_mnХ_mn)

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

Таблиця 2.25

Робоча таблиця транспортної задачі (РТ)

Постачальники	Споживачі	Наявність (Ai)
		…	j	…	n
	Х11 ; С11	Х12 ; С12	…			Х1n; С13	А1
	Х21 ; С21	Х22 ; С22				Х2n; С2n	А2
…	…	…	…	…	…	…	…
i	Хi1 ; Сi1	Хi2 ; Сi2		Хij; Сij		Хin; Сin	Аi
…	…	…		…	…	…	…
m	Хm1; Сm1	Хm2 ; Сm2		Хmj; Сmj		Хmn; Сmn	Аm
Потреби, Вj	В1	В2	…	Bj	…	Вn	В

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

Приклад 1. Визначити такий маршрут перевезень, чи скласти такий варіант транспортування сіна, щоб загальні витрати на його перевезення були мінімальними. Вихідні дані транспортної задачі наведені у табл. 2.26.

Таблиця 2.26

Номер скирти	Номер ферми	∑ J j=1
	1 Х11	2 Х12	1 Х13
	4 Х21	2Х22	3 Х23
	2 Х31	1 Х32	4 Х33
	5Х41	2Х42	3 Х43
∑ I і=1

Собівартість 1 т/км при перевезенні сіна в середньому по господарству складає 50 коп. Відстані від скирд до ферм (км) вказані в таблиці 2.27.

Таблиця 2.27

Дата добавления: 2014-11-29