Короткі теоретичні відомості

Відведений час: 4 год.

Мета: формувати у студентів уміння розв’язувати транспортні задачі.

Завдання для практичного заняття:

1. Пригадайте основні теоретичні питання теми.

2. Орієнтовні запитання та завдання:

- транспортна задача і її властивості;

- поняття опорного плану транспортної задачі;

- методи пошуку початкових опорних планів транспортної задачі.

3. Виконайте індивідуальне завдання.

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

Математична модель транспортної задачі має такий вигляд:

(2.24)

за обмежень

; (2.25)

; (2.26)

, (2.27)

де х_ij — кількість продукції, що перевозиться від і -го постачальника до j -го споживача; с_ij — вартість перевезення одиниці продукції від і -го постачальника до j -го споживача; а_i — запаси продукції і -го постачальника; b_j — попит на продукцію j -го спо­живача.

Транспортну задачу зручно записувати у вигляді таблиці 2.50.

Таблиця 2.50 – Вихідні дані

	В1	В2	…	Вj	…	Вn	Запас
А1	c11 x11	c12 x12		c1j x1j		c1n x1n	a1
А2	c21 x21	c22 x22		c2j x2j		c2n x2n	a2
…
Аi	ci1 xi1	ci2 xi2		cij xij		cin xin	ai
…
Аm	cm1 xm1	cm2 xm2		cmj xmj		cmn xmn	am
Потреби	b1	b2		bj		bn

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

, (2.28)

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

Планом транспортної задачі називають будь-який невід’єм­ний розв’язок системи обмежень (2.25)—(2.27) транспортної задачі, який позначають матрицею .

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

Теорема (умова існування розв’язку транспортної задачі). Необхідною і достатньою умовою існування розв’язку транспортної задачі є її збалансованість, тобто .

Дата добавления: 2017-02-01