Задачi для самостійної роботи

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

бензосховища
Заводи		1	2	3
	1	120	180	-
	2	300	100	80
	3	200	250	120

Задача 2. Розв’яжіть транспортну задачу методом потенціалів двічі: перший раз початковий розв’язок знайдiть методом північно-західного кута, другий – методом найменшої вартостi. Порівняйте їх.

	1		2
				5
	3		6
				10
	5		4
				20
8		37

Задача 3. Розв’яжіть транспортну задачу методом потенціалів двічі: перший раз початковий розв’язок знайдiть методом північно-західного кута, другий – методом найменшої вартостi. Порівняйте їх.

	1			2
					20
	3			1
					30
	8			7
					40
	5			0
					45
25		100

Задача 4. Розв’яжіть транспортну задачу методом потенціалів. Початковий розв’язок знайдіть методом північно-західного кута.

	2		3		5
						5
	3		5		1
						8
	6		2		4
						2
3		3		3

Задача 5. Розв’яжіть транспортну задачу методом потенціалів. Початковий розв’язок знайдiть методом найменшої вартостi.

	8		7		5		5
								7
	4		2		3		6
								14
	1		4		0		2
								7
	6		5		4		3
								6
8		4		5		17

Задача 6. Розв’яжіть транспортну задачу методом потенціалів та симплекс-методом, а також покажіть, що між ітераціями цих методів існує взаємооднозначна відповідність. Початковий розв’язок знайдiть методом північно-західного кута.

1	0	2	4
3	5	4	6
1	2	3	10
3	5	12

Задача 7. Розв’яжіть таку транспортну задачу:

	4		3		5
						10
	2		8		6
						20
	5		4		1
						5
15		25		10

Задача 8. Розв’яжіть транспортну задачу:

	4		5		4		6		0
										5
	1		4		8		7		0
										6
	9		8		10		7		4
										5
	2		10		3		11		5
										14
3		2		15		6		4

Задача 9. Розв’яжіть таку транспортну задачу:

	0		0		4		3
								7
	2		1		5		9
								10
	7		10		5		3
								8
	4		8		6		3
								10
14		10		7		4

Задача 10. Розгляньте оптимальну транспортну таблицю задачі 1 (табл. 5.9). У кожному з наведених випадків знайдіть зміни обсягу виробництва та попиту, за яких поточний розв’язок залишається допустимим.

1. вихідний пункт 1 – пункт призначення 1;

2. вихідний пункт 1 – пункт призначення 2;

3. вихідний пункт 2 – пункт призначення 2;

4. вихідний пункт 3 – пункт призначення 3.

Задача 11. Розв’яжiть задачу розподілу верстатів чотирьох різних типів за п'ятьма типами робіт. Нехай є 25, 30, 20 і 30 верстатів відповідних типів. П'ять типів робіт характеризуються 20, 15, 30, 10 і 25 операціями відповідно. На верстаті 4 не можна виконувати роботу 4. Виходячи з коефіцієнтів вартості операцій, наведених в таблиці, побудуйте модель оптимального розподілу верстатів за типами робіт.

Тип верстатів	Тип робіт
	1	2	3	4	5
1	10	2	3	15	9
2	5	10	15	2	4
3	15	5	14	7	15
4	20	15	13	-	8

Задача 12. У наведеній транспортній задачі сумарний попит переважає сумарний обсяг виробництва. Нехай штрафи за недопостачання одиниці продукції в пункти призначення 1, 2 і 3 дорівнюють 5, 3 і 2 відповідно. Знайдіть оптимальний розв’язок.

5	1	7	10
6	4	6	80
3	2	5	15
75	20	50

Задача 13. У деяких реальних умовах постановка транспортної задачi може ускладнюватися такими додатковими умовами:

а) з пункту в пунктперевезення здiйснити не можна;

б) з пункту виробництва в пункт споживаннятреба забезпечити перевезення точноодиниць продукцiї;

в) з пункту виробництва в пункт споживаннятреба завезти не менше ніжодиниць продукцiї;

г) з пункту виробництва в пункт споживаннятреба завезти не бiльше ніжодиниць продукцiї.

Для кожної з умов визначте, що треба зробити, щоб урахувати її при розв’язаннi транспортної задачi. Вiдповiдь подайте у виглядi транспортних таблиць.

Задача 14.У незбалансованій транспортній задачі призначається плата за зберігання кожної одиниці невивезеного товару з вихідного пункту й вантажу. Нехай коефіцієнти вартості зберігання вантажу у вихідних пунктах 1, 2 і 3 дорівнюють 5, 4 і 3 відповідно. Знайдіть оптимальний розв’язок, якщо весь обсяг вантажу вихідного пункту 2 має бути вивезений для того, щоб вивільнити місце для нової продукції.

1	2	1	20
0	4	5	40
2	3	3	30
30	20	20

Задача 15. Нехай у транспортній задачі розмірністю 3x3 через позначено кількість вантажу, що перевозиться зi в j, – коефіцієнт вартості відповідного перевезення. Обсяги виробництва у вихідних пунктах 1, 2 і 3 дорівнюють 15, 30 і 85 одиниць, а попит в пунктах призначення 1, 2 і 3 – 20, 30 і 80 одиниць. Припустимо, що початковий розв’язок, одержаний методом північно-західного кута, є оптимальним базисним розв’язком задачі. Відповідні значення потенціалів вихідних пунктів 1, 2 і 3 дорівнюють 2, 3 і 5, а значення потенціалів пунктів призначення 1, 2 і 3 – 2, 5 і 10.

1. Знайдіть сумарні транспортні видатки.

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

Задача 16. Визначте початковий розв’язок транспортної задачі за допомогою а) методу північно-західного кута; б) методу найменшої вартості; в) наближеного методу Фогеля. Знайдіть оптимальний розв’язок, виходячи з найкращого початкового розв’язку.

10	20	5	7	10
13	9	12	8	20
4	15	7	9	30
14	7	1	0	40
3	12	5	19	50
60	60	20	10

Задача 17. Повітряна лінія зв'язує два міста: А і В. Екіпаж, що формується в місті А (В) і вилітає у місто В (А), повинен здійснити зворотний рейс у місто А (В) в того самого або наступного дня. Екіпаж, що формується в А, можна призначити для зворотного рейсу в А за умови, якщо між часом прибуття у В і часом вильоту з В минуло не менше 90 хв. Задача полягає у складанні розкладу польотів, що мінімізує сумарний час простоїв усіх екіпажів. Розв’яжiть цю задачу про призначення, використовуючи такий розклад:

Рейс	Виліт з А	Приліт в В	Рейс	Виліт з В	Приліт в А
1	6:00	8:30	10	7:30	9:30
2	8:15	10:45	20	9:15	11:15
3	13:30	16:00	30	16:30	18:30
4	15:00	17:30	40	20:00	22:00

Задача 18. Знайдіть найкоротший шлях між вершинами 1 і 7 у мережі, зображеній на рис. 5.2, сформулювавши задачу з проміжними пунктами. Відстані між різними вершинами вказано на дугах мережі.

Рис. 5.2

Задача 19. Директор ресторану, складаючи план роботи на чергові N днів, повинен попіклуватися про щоденний запас чистих серветок. Потреба ресторану в серветках за ці N днів дорівнює b₁, b₂,..., b_N і може бути задоволена трьома різними шляхами:

1) покупкою нових серветок за ціною p₁ центів;

2) пранням використаних серветок у пральні з терміном виконання 24 год за ціною p₂ центів;

3) пранням використаних серветок у пральні з терміном виконання 48 год за ціною p₃ центів.

Сформулюйте цю задачу у виглядi транспортної.