3.5. Перевір себе

3.5.1. Контрольні запитання

1. Сформулюйте економічну постановку та математичну модель транспортної задачі.

2. Яка умова є необхідною та достатньою для розв’язуваності транспортної задачі?

3. Як звести незбалансовану транспортну задачу до збалансованої?

4. Які існують методи знаходження початкового опорного плану транспортної задачі?

5. Дайте економічну інтерпретацію методів мінімальної вартості та Фогеля.

6. Якою повинна бути кількість базисних змінних транспортної задачі?

7. Який ви знаєте метод перевірки опорного плану транспортної задачі на оптимальність?

8. Назвіть етапи методу потенціалів.

9. Наведіть приклади модифікованих моделей транспортної задачі.

10. У чому полягає задача про призначення?

11. Назвіть особливості математичної моделі задачі про призначення. До якого типу задач вона відноситься?

12. Яким методом розв’язується задача про призначення?

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

14. Чи обов’язково матриця витрат в задачі про призначення повинна мати квадратну форму?

15. Поясніть поняття терміну „динамічне програмування”.

16. Дайте характеристику задач, для розв’язування яких може бути застосований метод динамічного програмування.

17. Яка загальна ідея методу динамічного програмування?

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

19. Виведіть основне рекурентне співвідношення методу динамічного програмування.

20. З яких етапів складається алгоритм методу динамічного програмування?

21. Сформулюйте економічну постановку задачі про заміну обладнання.

22. За яких умов визначається максимальний прибуток на кожному кроці в задачі про заміну обладнання?

23. Поясніть застосування методу динамічного програмування для задач з двома видами ресурсів.

24. Задачі з блочно-діагональною структурою, її елементи.

25. Наведіть економічний приклад задачі з блочно-діагональною структурою.

26. Ідея методу декомпозиції Данцига-Вульфа.

27. Правила побудови головної задачі в методі Данцига-Вульфа.

28. Критерій оптимальності опорного плану в методі Данцига-Вульфа.

29. Особливості методу Данцига-Вульфа з задач з декількома діагональними блоками.

30. Формування оптимального опорного плану в методі Данцига-Вульфа.

3.5.2 Завдання та приклади для самостійної роботи

Розв’язати транспортні задачі 3.1 – 3.7

3.1. Автотранспортне підприємство здійснює доставку цегли з трьох заводів до трьох об’єктів будівництва. Виробничі потужності заводів дорівнюють: 500 тис. штук, 300 тис. штук та 400 тис. штук. Потреби об’єктів у цеглі складають 600 тис. штук, 250 тис. штук та 350 тис. штук. Вартість перевезення однієї тисячі штук цегли з заводів до об’єктів будівництва наведено у таблиці 3.27.

Таблиця 3.27.

Заводи	Вартість перевезення 1 тис. штук цегли
	І	ІІ	ІІІ
А	50	30	20
В	40	60	50
С	10	20	40

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

3.2. Підприємство роздрібної торгівлі має чотири магазини, розташованих у різних районах міста. Доставка продукції в ці магазини здійснюється з двох торгівельних складів А та В, площі яки вміщають по 40 одиниць продукції щодня.

У майбутньому планується розширити площі магазинів, тому їх потреби у продукції з торгових складів відповідно складуть 50, 25, 30 та 35 одиниць на день.

Щоб задовільнити потреби магазинів, планується побудувати третій склад, площа якого дозволить зберігати в ньому 60 одиниць продукції щодня. Розглядаються два варіанти його розташування. У таблиці 3.28 наведені дані про транспортні витрати за одиницю продукції з існуючих складів А та В і два варіанти розміщення нового складу.

Таблиця 3.28.

Торговий склад	Транспортні витрати (грн./од. )
	I	ІІ	ІІІ	IV
А	7	8	5	12
В	8	9	9	11
Варіант I	7	8	9	9
Варіант ІІ	10	9	6	8

Необхідно прийняти рішення відносно кращого варіанту розташування нового складу.

3.3. Автомобілі перевозять на трейлерах з трьох заводів до п’яти центрів продажу. Вартість перевезення розраховується в залежності від відстані між вихідними пунктами та пунктами призначення. Вартість не залежить від того на скільки повно завантажений трейлер. У таблиці 3.29 наведені дані щодо відстані між пунктами, а також щомісячний попит та об’єм виробництва. Один трейлер може перевозити до 18 автомобілів. Знайти оптимальний варіант доставки автомобілів, враховуючи що вартість 1 км. для кожного трейлера складає 50 грн.

Таблиця 3.29.

Заводи	Центри продажу					Об’єм виробництва (шт.)
	І	ІІ	ІІІ	ІV	V
А	100	150	200	140	35	400
В	50	70	60	65	80	200
С	40	90	100	150	130	150
Попит (шт.)	100	200	150	160	140

3.4. Цегла зберігається на трьох будівельних складах. Послугами складів користується холдінгова компанія „Київміськбуд”, яка одночасно веде будівництво на трьох об’єктах, потреби яких відповідно складають 2, 1 та 3 млн. шт. цеглин на місяць.

Об’єми складів дозволяють забезпечити попит тільки на 80%. Перший склад може забезпечити 2 млн. шт., другий – 1,5 млн. шт., а третій – решту.

Розглядається два варіанти розміщення нового складу. У таблиці 3.30 наведені дані про витрати на доставку цегли зі складів до об’єктів будівництва (грн. за одну тис. шт.)

Таблиця 3.30.

Склади	Об’єкти будівництва
	І	ІІ	ІІІ
А	100	150	90
В	120	80	110
С	70	50	60
І варіант	40	40	50
ІІ варіант	30	50	50

Визначити оптимальний варіант будівництва нового складу.

3.5. У транспортній задачі попит перевищує пропозицію. Тому встановлені штрафи за недопостачання одиниці продукції, які дорівнюють на першому об’єкті 5 грн., на другому – 3 грн., а на третьому – 2 грн. Попит на об’єктах відповідно дорівнює 40, 50 та 10 одиниць продукції. Можливості трьох постачальників обмежені: 10, 60 та 20 одиниць продукції. Знайти оптимальний розподіл продукції.

3.6. Розв’язати незбалансовану транспортну задачу з прикладу 3.1. за умови, що попит на першому об’єкті збільшиться на 100 тис. штук.

3.7. У транспортній задачі пропозиція перевищує попит. Тому встановлено плату за збереження невивезеної продукції зі складів, яка за кожну одиницю продукції дорівнює 10 грн. на першому складі, 8 грн. на другому та 5 грн. на третьому. Запаси продукції на складах дорівнюють відповідно 200, 400 та 500 одиниць продукції, а попит кожного з споживачів – 300, 400, 100 та 200 одиниць продукції. Знайти оптимальний план доставки продукції.

Розв’язати задачі про призначення 3.8 – 3. 12.

3.8. Асоціація вчених отримала повідомлення щодо отримання грантів на проведення досліджень за чотирма проектами. Директор асоціації має призначити керівника на кожен проект. Термін виконання кожного проекту залежить від досвіду та здібності дослідника, якому буде доручено виконання проекту. Оцінки терміну виконання кожного проекту кожним ученим наведені в таблиці 3.31.

Таблиця 3.31.

Учений-дослідник	Термін виконання проектів (днів)
	І	ІІ	ІІІ	IV
Іванов	80	120	60	104
Петров	72	144	48	110
Коваленко	96	148	72	120
Азаркін	60	108	52	92

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

3.9. Компанія отримала замовлення на чотири види продукції: бокали, чашки, вази та тарілки. У розпорядженні компанії є чотири види обладнання, на кожному з яких можна виготовляти будь-які з вказаних видів продукції. Витрати по виробництву кожного виду продукції залежать від виду обладнання. У таблиці 3.32 наведені витрати на кожну одиницю продукції на кожному обладнанні.

Таблиця 3.32.

Обладнання	Витрати (грн. / од.)
	Бокали	Чашки	Вази	Тарілки
А	12	13	11	14
В	14	13	15	16
С	11	10	13	14
D	12	14	12	13

Знайти такий варіант виробництва продукції, щоб загальні витрати були найменшими.

3.10. Авіалінія зв’язує 2 міста А і Б. Екіпаж, що формується у місті А та вилітає у місто Б повинен здійснити зворотній рейс у місто А у той же чи на наступний день. Формуємий в А екіпаж може бути призначений на зворотній рейс в А тільки, якщо між часом прибуття в Б та часом виліту із Б пройшло не менше 2 год. Задача полягає у складанні розкладу польотів екіпажів, який мінімізує загальний час простою екіпажів. Розв’язати задачу про призначення, використовуючи наступний розклад польотів (табл. 3.33).

Таблиця 3.33.

Рейс	Відправлення з м. А	Прибуття в м. Б	Рейс	Відправлення з м. Б	Прибуття в м. А
А1	5:00	7:00	Б1	7:00	9:00
А2	8:00	10:00	Б2	9:00	11:00
А3	10:00	12:00	Б3	16:00	18:00
А4	16:00	18:00	Б4	20:00	22:00

3.11. Фірма прийняла на роботу п’ять робітників для виконання п’яти видів робіт. Кожен з них має різні здібності та досвід роботи і тому може виконати будь-який з видів робіт раніше запланованого строку на певну кількість днів. Дані щодо економії днів наведені у таблиці 3.34.

Таблиця 3.34.

Робітники	Економія днів
	Робота І	Робота ІІ	Робота ІІІ	Робота IV	Робота V
А	25	16	15	14	13
В	25	17	18	23	15
С	30	15	20	19	14
Д	27	20	22	25	12
Е	29	19	17	32	20

Знайти таке призначення робітників на роботи, щоб всі роботи були виконані за найменшу кількість днів.

3.12. Агрофірма має 5 однакових по площі земельних ділянок для вирощування овочів – огірків, капусти, помідор, баклажанів та цибулі. Урожайність кожного виду культур залежить від вибраної ділянки. Для полегшення обробки рослин на кожній ділянці має вирощуватися тільки одна культура. Агрофірма має намір поставляти на ринок всі п’ять видів овочів. Дані про урожайність культур наведені у таблиці 3.35.

Таблиця 3.35.

Овочеві культури	Урожайність культур (ц/га)
	Ділянка І	Ділянка ІІ	Ділянка ІІІ	Ділянка IV	Ділянка V
Огірки	20	22	21	18	24
Капуста	50	45	48	52	51
Помідори	25	28	27	30	32
Баклажани	24	26	29	27	30
Цибуля	30	32	33	28	35

Знайти такий план розподілу земельних ділянок, щоб зібрати найбільший урожай.

Побудувати математичні моделі задач 3.13-3.18 та розв’язати їх методом динамічного програмування:

3.13. Фірма-інвестор для фінансування трьох різних проектів виділила 7 млн.грн. Кожен з проектів характеризується величинами витрат та прибутків, які наведено у таблиці 3.36:

Таблиця 3.36.

Проект	Витрати (млн.грн.)	Прибуток (млн.грн.)
1	3	7
2	2	5
3	1	2

Визначити оптимальний спосіб розподілу коштів між проектами.

3.14. Літак відправляється у спецрейс для доставки приладів експедиції. Максимальна вантажопідйомність літака — 5 т. Експедиції необхідні 3 види приладів. Вага, попит та збитки від недопостачання одного приладу наведено у таблиці 3.37:

Таблиця 3.37.

Прилад	Вага (т)	Попит (одиниць)	Втрати (тис.грн.)
1	2	2	65
2	3	1	80
3	1	3	30

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

3.15. Розв’язати задачу 3.14 за умови, що вантажопідйомність літака — 4 т.

3.16. Фірма має можливість рекламувати свою продукцію, використовуючи радіо та телемережі, а також пресу. Витрати фірми на рекламу обмежуються 10 тис.гривень щомісяця. Кожна хвилина радіореклами коштує 200 грн., теле — 500 грн., одне рекламне повідомлення у пресі — 300 грн. Досвід минулих місяців показав, що обсяг реалізації продукції за рахунок однієї хвилини радіореклами збільшується у 5 разів, телереклами — у 13 разів, а одне рекламне повідомлення у пресі сприяє збільшенню реалізації у 8 разів. Визначити оптимальний розподіл коштів на рекламу.

3.17. Власнику ресторану необхідно регулювати кількість робітників протягом п’яти місяців шляхом їх найму та звільнення. Мінімальні потреби у робочій силі на кожний місяць складають відповідно: 5, 7, 8, 4, 6 робітників. Найом нового робітника коштує 300 грн., збитки від зайвих робітників, пов’язані з необхідністю виплати їм заробітної плати, складають 200 грн. На початок першого місяця у ресторані працює 5 робітників. Визначити оптимальний план регулювання чисельності робітників.

3.18. Розв’язати задачу 3.17 за умови, що початкова кількість робітників — 3 особи.

Використовуючи метод Данцига-Вульфа, знайти оптимальний розв’язок задач 3.19-3.20 .

3.19.

3.20.

3.21. Для виробництва двох видів продукції А та В на двох підприємствах може бути використано 240 одиниць ресурсу. Норми витрат ресурсу дорівнюють 5 та 6 одиниць відповідно на перший та другий вид продукції. Прибуток від реалізації одиниці продукції складає 10 та 15 грн.

У виробництві використовуються два види технологічного обладнання. Витрати часу на виробництво одиниці продукції та ліміт використання обладнання наведені у табл.3.38.

Таблиця 3.38.

Тип обладнання	Витрати часу на виробництво одиниці продукції (год./од.)				Ліміт використання обладнання (год.)
	1-е підприємство		2-е підприємство
	А	В	А	В	1-е підприємство	2-е підприємство
І	2	1	3	2	120	150
ІІІ	5	4	6	8	140	200

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

169