3. Відкрита транспортна модель

У реальних умовах не завжди об'єм запасу рівний попиту. Така модель ТЗ називається відкритою моделлю. Однак транспортну модель завжди можна балансувати (привести до закритого вигляду):

- при > необхідно ввести додатковий пункт споживання, в якому потреба b_n+1 = - ;

- якщо < , то вводиться додатковий пункт- постачальник, запаси якого a_m+1 = –

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

Контрольні завдання:

1. Складіть опорні плани ТЗ всіма викладеними методами і порівняйте їх. Знайдіть оптимальний розв’язок задачі методом потенціалів і за допомогою “Пошуку рішень”.

Варіант 1

14	5	27	29	23	18
17	7	16	19	2	14
20	12	15	29	5	16
14	24	18	7	13	12
8	11	11	9	21

Варіант 2

15	1	22	19	1	20
21	18	11	4	3	20
26	29	23	26	24	20
21	10	3	19	27	20
19	19	19	19	4

Варіант 3

21	22	2	13	7	18
27	10	4	24	9	12
3	16	25	5	4	17
28	11	17	10	29	13
8	8	8	8	28

Варіант 4

30	24	11	12	25	21
26	4	29	20	24	19
27	14	14	10	18	15
6	14	28	8	2	25
15	15	15	15	20

Варіант 5

16	30	17	10	16	4
30	27	26	9	23	6
13	4	22	3	1	10
3	1	5	4	24	10
7	7	7	7	2

Варіант 6

17	20	29	26	25	15
3	4	5	15	24	15
19	2	22	4	13	15
20	27	1	17	19	15
11	11	11	11	6

Варіант 7

20	26	24	26	29	13
15	20	29	26	23	17
4	10	27	30	7	17
9	16	29	20	3	13
12	12	12	12	12

Варіант 8

5	15	3	6	10	9
23	8	13	27	12	11
30	1	5	24	25	14
8	26	7	28	9	16
8	9	13	8	12

2. Побудуйте математичну модель задачі і знайдіть її оптимальний розв’язок за допомогою Пошуку розв’язків.

1. Пісок для будівництва добувається в трьох кар'єрах та доставляється на чотири будівних майданчики. Відомі потужності кар'єрів за день: 60, 40 та 50 т, та споживи у піску будівних майданчиків: 40, 35, 20 та 45 т. Затрать на добування піску в шкіряному кар'єрі 2, 3, 1 грн. /т відповідно. Транспортні розходи задаються матрицею

С =

Визначити оптимальний план закріплення будівних майданчиків за кар’єрами.

Вказівка. Вирішувати як звичайну транспортну задачу, заздалегідь перетворювавши матрицю транспортних витрат в матрицю сумарних витрат ||c_ik||, де c_ik = c_ik + d_і.

2. Автомобілі перевозяться на трейлерах з трьох центрів розподілу п'яти продавцям. Вартість перевезення розраховується на основі відстаней між вихідними пунктами та пунктами призначення: 1 км путі пройдений трейлером обійтися у 10 долл. Відомі відстані між центрами розподілу та продавцями, а також величини, що характеризують щомісячний попит та об'єм виробництва (у кількостях автомобілей) , таблиця 11. Визначити кількості трейлерів, які треба відправити по кожному з маршрутів, щоб сумарні витрати на перевезення були б мінімальними. Також відомо, що один трейлер може перевезти до 18 автомобілей і вартість перевезення не залежить від того на скільки повно загружається трейлер.

Табліця 11

Центри розподілу	Продавці					Об'єми поставок
	1	2	3	4	5
1	100	150	200	140	35	400
2	50	70	60	65	80	200
3	40	90	100	150	130	150
Щомісячний попит	100	150	150	160	140

3. Три нафтопереробних заводи з максимальною потужністю виробництва 6, 5 та 8 млн. галонів бензину щодня снабжають чотири бензосховища, попит яких складає 4, 5, 6 та 3 млн. галонів. Бензин транспортується в бензосховища по трубопроводу. Вартість перекачки бензину на 1 км, враховуючи довжину трубопроводу, складає 1 цент на 100 галонів. У таблиці 12 задані відстані між заводами та бензосховищами

Таблиця 12

Заводи	Бензосховища
	1	2	3	4
1	130	90	80	215
2	135	101	100	108
3	95	105	102	68

Визначити план транспортування нафти, при якому будуть мінімальні витрати.

4. На трьох залізничних станціях А1, А2, А3 скупчилося 120, 110 і 130 незавантажених вагонів, Ці вагони необхідно перегнати на залізничні станції В1, В2, В3, В4 і В5. На кожній з цих станцій потреба у вагонах відповідно рівна 80, 60, 70, 90 і 50. Знаючи, що тарифи перегонки одного вагона визначаються матрицею

С = ,

Складіть такий план перегонок вагонів, щоб загальна вартість була мінімальною.

5. У області є три цементних заводи і п'ять споживачів їх продукції домобудівні комбінати. У таблиці 13 вказані добові обсяги виробництва цементу, добові потреби в ньому комбінати і вартість перевезення 1 т цементу від кожного заводу до кожного комбінату.

Таблиця 13

Заводи	Виробництво цемента (т/добу)	Вартість перевезень 1 т цемента (грн)
		Комб. 1	Комб. 2	Комб. 3	Комб.4	Комб. 5
1	60	10	15	25	20	15
2	50	20	25	30	15	10
3	70	10	10	15	25	35
Потреби в цементі (т/добу)		50	45	45	30	30

Потрібно скласти план добових перевезень цементу з метою мінімізації транспортних витрат.

6. На трьох хлібокомбінатах щодня виробляється 110, 190 та 90 т муки. Ця мука використовується чотирма хлібозаводами, щоденні споживи яких рівні відповідно 80, 60, 150 та 80 т. Тарифи перевезень 1 т муки з хлібокомбінатів до шкіряного з хліб заводів задаються матрицею

С =

Скласти такий план доставки муки, при якому загальна вартість перевезень є мінімальною.

7. Мається три ділянки землі, на яких може бути засіяно кукурудза, пшениця, ячмінь та просо. Площина кожної з ділянок відповідно рівна 550, 180 та 220 га. З урахуванням наявної кількості посівного матеріалу кукурудзою, пшеницею, ячменем та просом слід засіяти 290, 180, 110 та 420 га. Врожайність кожної з культур для кожної ділянки різна і задається матрицею

С =

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

Питання для самоконтроля:

1. Як формулюється транспортна задача по критерію вартості?

2. Напишіть математичну модель ТЗ.

3. Яка модель транспортної задачі називається закритої, а яка відкритої?

4. Чим відрізняється математичні моделі закритої і відкритої ТЗ?

5. Як відкриту модель перетворити в закриту?

6. Перерахуйте основні етапи знаходження оптимального розв’язання ТЗ.

7. Які існують методи побудови первинного опорного плану?

8. У чому укладається опорность плану транспортної задачі, умови якої записані в таблиці?

9. Скільки позитивних перевезень повинен містити невироджений опорний план і чому?

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

11. Коли опорний план транспортної задачі буде оптимальним?

Знаходження розв’язку транспортної задачі, що має деякі ускладнення (додаткові обмеження) в постановці.

Мета заняття: Познайомитися з видами спеціальних обмежень, що містяться в умові транспортної задачі і способами розв’язання таких задач.

Ключові слова: транспортна задача, блокування перевезень, пропускні спроможності