Задачі для самостійного розв’язання

№1.1. Розрахувати максимальний прибуток цеху від продажу виробів №1 та №2, якщо задані ресурси (листи металу, пластмаса, деревина, гроші, трудові ресурси), норми витрат та прибуток від одного виробу.

Таблиця 1.1.

Дані для складання математичної моделі по випуску виробів №1, №2.

Вид ресурсу	Запаси ресурсів	Норми витрат
		Виріб №1	Виріб №2
Листи металу Пластмаса Деревина Гроші Трудові ресурси	4N 7N 2,5N 8N 4N	0,08-0,003*А 0,095-0,003*A 0,05 0,42+0,01*А 0,1	0,1 0,35-0,02*А 0,083 - 0,13
Кількість виробів, шт.	X1	X2
Прибуток за 1 виріб, грн/шт.	1,2*A	1,6*A

№1.2. Розрахувати максимальний прибуток цеху від продажу радіоприймачів №1 та №2, якщо задані ресурси (мікросхеми, транзистори, резистори, гроші, трудові ресурси), норми витрат та прибуток від одного приладу.

Таблиця 1.2.

Дані для складання математичної моделі по випуску радіоприймачів №1, №2.

Вид ресурсу	Запаси ресурсів	Норми витрат
		Радіо №1	Радіо №2
Мікросхеми Транзистори Резистори Гроші Трудові ресурси	20N 30N 25N 14N 10N	0,9 5+0,4*А 0,9	6-0,3*А 0,8-0,02*A 1,1 3,5+0,3*А 0,4
Кількість радіоприймачів, шт.	X1	X2
Прибуток за 1 радіоприймач, грн/шт.	0,5*A	A

№1.3. Розрахувати, скільки сільськогосподарському підприємству потрібно купити добрив №1 та №2 для отримання з них загальної суміші, якщо задані по кожному з добрив: скільки в одному кілограмі вміщується аміаку, суперфосфату, калію, натрію та вартість одного кілограма добрива. Отримати мінімальну потрібну загальну вагу та вартість добрив №1 та №2 у суміші, яка повинна вміщувати не менше заданої потрібної кількісті компонентів (аміаку, суперфосфату, калію, натрію).

Таблиця 1.3.

Дані для складання математичної моделі по випуску суміші добрив №1, №2.

Види матеріалів	Загальна вага добрива в суміші, кг	Ціна 1 кг добрива, грн/кг	Вага компонентів [у.о.] в одному кг добрива
			Аміак	Суперфосфат	Калій	Натрій
Добриво №1 Добриво №2	Х1   Х2	0,8N   0,7N	0,9   0,1	0,5   A+1	4+0,2*А 1,2	А   –
Потрібна вага компонента в суміші, у.о.	8N	8N	2N+5	N

№1.4. Розрахувати, скільки сільськогосподарському підприємству потрібно використати кормів №1 та №2 для отримання з них загальної суміші, якщо задані по кожному з кормів: скільки в одному кілограмі вміщується білка, вітаміну А, вітаміну В, вітаміну С та вартість одного кілограма корму. Отримати мінімальну загальну вагу та вартість кормів №1 і №2 у суміші, яка повинна вміщувати не менше заданої потрібної кількості компонентів (білка, вітаміну А, вітаміну В, вітаміну С).

Таблиця 1.4.

Дані для складання математичної моделі по випуску суміші кормів №1, №2.

Види матеріалів	Загальна вага корму в суміші, кг	Ціна 1 кг матеріала, грн/кг	Вага компонентів [у.о.] в одному кг корму
			Білок	А	В	С
Корм №1 Корм №2	Х1 Х2	0,5N 0,6N	0,2-0,01*А 0,24	0,3-0,03*А 0,6	-	1,3 3+0,3*А
Потрібна вага компонента в суміші, у.о.	2N	5N	А	4N

№1.5. Розрахувати, скільки сім’ї потрібно використати для споживання продуктів №1 та №2, якщо задані по кожному з продуктів: скільки в одному кілограмі вміщується білка, вітаміну А, вітаміну В, вітаміну С та вартість одного кілограма продуктів. Отримати мінімальну загальну вагу та вартість продуктів №1 та №2 у суміші, за умови, що у сукупності всі продукти повинні вміщувати не менше заданої потрібної кількості компонентів (білка, вітаміну А, вітаміну В, вітаміну С).

Таблиця 1.5.

Дані для складання математичної моделі суміші продуктів №1, №2.

Види матеріалів	Загальна вага корму в суміші, кг	Ціна 1 кг матеріала, грн/кг	Вага компонентів [у.о.] в одному кг продуктів
			Білок	А	В	С
Продукт №1 Продукт №2	Х1   Х2	1,5N   0,9N	16+A   1-0,1*А	0,09	4+0,1*A   –	–   7+0,1A
Потрібна вага компонента в суміші, у.о.	10N	4N	N	N

 

Таблиця 1.6

Дані для складання математичної моделі суміші продуктів №1, №2.

Види матеріалів	Загальна вага корму в суміші, кг	Ціна 1 кг матеріала, грн/кг	Вага компонентів[у.о.] в одному кг продуктів
			Білок	А	В	С
Продукт №1 Продукт №2	Х1   Х2	2,5N   1,6N		25+A   1,6	-	0,5-0,02*A
Потрібна вага компонента в суміші, у.о.	7N	3N+7	5N

 

№1.6. Розрахувати максимальний прибуток підприємства від продажу сумішей (пального №1 та №2), якщо задані ресурси (бензин, керосин, дизельне пальне, трудові ресурси), норми витрат та прибуток від кілограма суміші.

Таблиця 1.7.

Дані для складання математичної моделі випуску пального №1, №2.

Вид ресурсу	Запаси ресурсів, кг	Норми витрат на 1 кг пального
		Пальне №1	Пальне №2
Бензин Керосин Дизельне пальне Трудові ресурси	70N 300N 200N   12N	0,1 N 0,5 0,4   0,04	0,3 N 0,7 -   0,016+0,001*А
Вага пального, кг	X1	X2
Прибуток за 1кг пального, грн/кг	0,01(N+2)	0,01(N+4)

 

№1.7. Розрахувати максимальний прибуток підприємства від продажу сумішей (добрив №1 та №2), якщо задані ресурси (аміак, суперфосфат, калій, натрій, трудові ресурси), норми витрат та прибуток від кілограма суміші. Аміак, суперфосфат, калій, натрій вимірюються в у.о.

Таблиця 1.8.

Дані для складання математичної моделі випуску добрива №1, №2.

Вид ресурсу	Запаси ресурсів, кг	Норми витрат на 1 кг добрив
		Добриво №1	Добриво №2
Аміак Суперфосфат Калій Натрій Трудові ресурси	9N 5N 20N 3N 12N	0,1+0,1*A 0,4+0,05*А - 0,44 0,3+0,01*A	0,08+0,01*A 0,04 0,35 - 0,15+0,01*A
Вага добрива, кг	X1	X2
Прибуток за 1кг добрива, грн/кг	N+1	N+2

№1.8. Розрахувати максимальний прибуток підприємства від продажу сумішей (комбікормів для худоби №1 та №2), якщо задані ресурси (зерно, сіно, висівки, добавки, трудові ресурси), норми витрат та прибуток від кілограма суміші.

 

Таблиця 1.9

.Дані для складання математичної моделі випуску комбікормів №1, №2.

Вид ресурсу	Запаси ресурсів, кг	Норми витрат на 1 кг суміші
		Комбікорм №1	Комбікорм №2
Зерно Сіно Висівки Добавки Трудові ресурси	15N 1,5N 3,5N 3N N	0,15 0,05 0,08-0,002*А 0,12-0,005*А 0,015	0,5 0,02 0,1 - 0,016+0,001*А
Вага комбікорму, кг	X1	X2
Прибуток за 1кг комбікорму, грн/кг	N+4	N+А

 

№1.9. Розрахувати максимальний прибуток їдальні від продажу порцій печені та котлет, якщо задані ресурси (м’ясо, крупа, картопля, гроші, трудові ресурси), норми витрат та прибуток від однієї порції кожної страви.

Таблиця 1.10.

Дані для складання математичної моделі по випуску страв.

Вид ресурсу	Запаси ресурсів	Норми витрат на 1 страву
		Печеня	Котлети
М’ясо Крупа Картопля Гроші Трудові ресурси	5N 6N 4N 3N N	0,4 0,2 0,25 0,15+0,01*A 0,06	0,15 0,3 0,2 0,2+0,001*A 0,04+0,001*A
Кількість страв, шт.	X1	X2
Прибуток від 1 страви, грн/шт.	А+2	А+1,4

№1.10. Розрахувати максимальний прибуток ковбасного цеху від продажу ковбас №1 та №2, якщо задані ресурси (м’ясо, сало, спеції, гроші, трудові ресурси), норми витрат та прибуток від одного кілограма кожної з ковбас.

Таблиця 1.11.

Дані для складання математичної моделі по випуску ковбас.

Вид ресурсу	Запаси ресурсів	Норми витрат на 1 кг ковбаси
		Ковбаса №1	Ковбаса №2
М’ясо Сало Спеції Гроші Трудові ресурси	10N 5N 0,5N N 2N	0,7 0,55 0,025 0,02+0,0015*A 0,2 +0,001*A	1,3 0,3 0,1 0,04 0,5
Вага ковбаси, кг	X1	X2
Прибуток від 1 кг ковбаси, грн/кг	0,8N	1,2N

 

№1.11. Розрахувати максимальний прибуток бару від продажу бутербродів №1 та №2, якщо задані ресурси (хліб, м’ясо, гроші, трудові ресурси), норми витрат та прибуток від одного бутерброда.

 

 

Таблиця 1.12.

Дані для складання математичної моделі по випуску бутербродів.

Вид ресурсу	Запаси ресурсів	Норми витрат на 1 бутерброд
		Бутерброд №1	Бутерброд №2
Хліб М’ясо Гроші Трудові ресурси	2N 6N N 3N	0,05 0,15+0,001*A 0,06+0,001*A 0,1+0,01*A	0,1 0,6 –0,001*A 0,04+0,001*A 0,12+0,01*A
Кількість бутербродів, шт.	X1	X2
Прибуток від 1 бутерброду, грн/шт.	А+4	А+10

№1.12. Розрахувати максимальний прибуток цеху від продажу іграшок №1 та №2, якщо задані ресурси (шкіра, вата, фарба, гроші, трудові ресурси), норми витрат та прибуток від однієї іграшки.

Таблиця 1.13.

Дані для складання математичної моделі по випуску іграшок.

Вид ресурсу	Запаси ресурсів	Норми витрат на 1 іграшку
		Іграшка №1	Іграшка №2
Шкіра Вата Фарба Гроші Трудові ресурси	10N 8N 2N 3N 5N	0,1+0,015*A 0,4-0,012*A 0,08 0,1-0,01*A 0,15	0,2+0,01*A 0,08-0,01*A 0,03 0,035 0,05+0,01*A
Кількість іграшок, шт.	X1	X2
Прибуток від 1 іграшки, грн/шт.	А	1,5*А

№1.13. Розрахувати максимальний прибуток цеху від продажу чоловічого та жіночого взуття, якщо задані ресурси (шкіра, гума, гроші, трудові ресурси), норми витрат та прибуток від однієї пари взуття.

Таблиця 1.14.

Дані для складання математичної моделі по випуску взуття.

Вид ресурсу	Запаси ресурсів	Норми витрат на 1 пару взуття
		Чоловіче взуття	Жіноче взуття
Шкіра Гума Гроші Трудові ресурси	12N 9N 4N 5N	0,1+0,02*A 0,3+0,01*А 0,1 0,1	0,3-0,02*А 0,09-0,012*А 0,06 0,08
Кількість пар взуття, пара	Х1	Х2
Прибуток від 1 пари взуття, грн/пара

№1.14. Визначити максимальну можливу кількість гідролокаторів №1 та №2, яку може випускати підприємство при таких даних:

▪ мінімальна припустима надійність обох гідролокаторів – 95%.

▪ виробництво є рентабельним, якщо випускає не менше 5А гідролокаторів (тут , де - порядковий номер студента у групі);

▪ максимальна виробнича потужність підприємства – не більша за 30А гідролокаторів;

▪ надійність гідролокаторів (якщо іх випускати не більше 10 шт): 96,5% для гідролокатора №1 та 97,5% для гідролокатора №2;

▪ на кожні А шт. додаткових гідролокаторів (які випускаються понад 10 шт.) надійність знижується: на 0,1% для гідролокатора №1 та на 0,15% для гідролокатора №2.

 

№1.15. Розрахувати максимальний прибуток від продажу виробів №1 та №2. Дані для розрахунків наведені у табл.1.16.1та 1.16.2. Наявні ресурси є випадковою величиною з рівномірним розподілом у вказаних межах. Знайти графо-аналітичним методом значення змінних за ймовірності P=(0,8 – 0,01*N) у забезпеченні наявності потрібних ресурсів.

 

Таблиця 1.16.1.

Дані для складання математичної моделі продажу приладів.

Вид ресурсу	Запаси ресурсів	Норми витрат на 1 прилад
Прилад №1	Прилад №2
Мідь Залізо Гроші	2N–4N 3N–7N 4N–8N	0,06-0,002*A 0,095-0,01*А 0,1	0,1 0,4-0,02*А 0,06
Кількість приладів, шт.	Х1	Х2
Прибуток від продажу 1 приладу, грн/шт.

 

Таблиця 1.16.2.

Дані для складання математичної моделі продажу приладів.

Вид ресурсу	Запаси ресурсів	Норми витрат на 1 прилад
Прилад №1	Прилад №2
Мідь Залізо Гроші	3N–5N 2N–6N 3N–6N	0,5+0,02*A 0,085-0,01*А 0,15	0,3 0,3+0,01*А 0,07
Кількість приладів, шт.	Х1	Х2
Прибуток від продажу 1 приладу, грн/шт.

 

№1.16. Показати особливості математичної моделі задачі стохастичного програмування.

Свиноферма може купувати три види збіжжя, яке може мати 4 інгредієнти (А, В, С, Д згідно з табл.1.17). Мінімальні потреби у компонентах А, В, С, Д є випадковими величинами, розподіленими рівномірно у відповідних інтервалах, умовних одиниць (у.о). Мінімальну потребу у кількості компонентів потрібно забезпечити з ймовірністю не нижче за 0,8.

Завдання: скласти математичну модель (без ії рішення) для визначення ваги потрібного збіжжя по видах та для визначення мінімальних витрат на збіжжя.

Таблиця 1.17.

Визначення мінімальних витрат на комбікорми.

Інгредієнти у складі суміші	Уміст інгредієнтів у збіжжі виду (у.о./кг)	Мінімальна потреба у компонентах на запланований термін, у.о.
А				130–150
В				30–230
С				800–140
Д				25–75
Вага збіжжя, кг	Х1	Х2	Х3	-
Вартість збіжжя				-

 

 

№1.17. Показати особливості математичної моделі задачі стохастичного програмування.

Ливарному підприємству потрібно чотири види металів (М1, М2, М3, М4 згідно з табл.1.18), які містяться у трьох видах сплавів. Розрахунок проводять в умовних одиницях (у.о). Мінімальні потреби у металах М1, М2, М3, М4 є випадковими величинами, розподіленими рівномірно у відповідних інтервалах в умовних одиницях. Мінімальну потребу у кількості металів потрібно забезпечити з ймовірністю не нижче за 0,8.

Завдання: скласти математичну модель (без рішення) для визначення ваги потрібних сплавів по видах та мінімальних витрат на сплави.

Таблиця 1.18.

Визначення мінімальних витрат на сплави.

Елементи у складі сплаву	Уміст металів в одиниці сплаву виду, у.о./кг	Мінімальна потреба у металах М1-М2 на запланований термін, у.о.
М1				20–140
М2				60–180
М3				45–105
М4				30–130
Вага сплавів, кг	Х1	Х2	Х3	-
Вартість сплавів, грн/кг				-

№1.18. Показати особливості математичної моделі задачі стохастичного програмування.

Для виробництва медикаменту потрібно чотири види елементів (Е1, Е2, Е3, Е4 згідно з табл.1.19, які містяться у трьох видах сировини. Розрахунок проводять в умовних одиницях (у.о.). Мінімальні потреби у елементах Е1, Е2, Е3, Е4 є випадковими величинами, розподіленими рівномірно у відповідних інтервалах в умовних одиницях. Мінімальну потребу у кількості елементів потрібно забезпечити з ймовірністю не нижче за 0,9.

Завдання: скласти математичну модель (без ії рішення) для визначення ваги потрібної сировини по видах та мінімальних витрат на сировину.

Таблиця 1.19.

Визначення мінімальних витрат на сировину для медикаменту.

Елементи у складі сировини	Уміст елементів в одиниці сировини виду, у.о./кг	Мінімальна потреба у елементах Е1-Е4 для медикаменту, у.о.
Е1				40–100
Е2				50–200
Е3				40–120
Е4				35–300
Вага сировини, кг	Х1	Х2	Х3	-
Вартість сировини, грн/кг				-

ТЕСТИ

1. Умовний образ об'єкта управління – це:

а) план

б) модель

в) метод

2. Що впливає на час розробки моделі, прийняття?

а) час існування проблеми

б) час розробки методів

в) розробка моделі

3. Абстрактна модель – це:

а) концептуальна

б) матеріальна

в) фізична

г) всі відповіді правильні

4. Моделі з конкретними числовими значеннями – це:

а) математичні

б) макроекономічні

в) мікроекономічні

г) числові

5. Моделі, які описують економіку, пов'язуючи між собою матеріальні і фінансові показники – це:

а) дискретні

б) нормативні

в) мікроекономічні

г) макроекономічні

6. Моделі, що описують взаємодію структурних і функціональних складових, або поведінку окремої фірми – це моделі:

а) макроекономічні

б) теоретичні

в) прикладні

г) мікроекономічні

д) нормативні

7. Моделі, що дозволяють вивчити загальні властивості економіки та її характерних елементів за допомогою дедукції висновків із формальних передумов – це моделі:

а) теоретичні

б) числові

в) висновкові

г) рівноважні

8. Моделі, що дають можливість оцінити параметри функціонування конкретного економічного об'єкта і сформулювати рекомендації для прийняття практичних рішень – це моделі:

а) практичні

б) теоретичні

в) прикладні

г) емпіричні

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

а) мікроекономічні

б) нульові

в) рівноваги

10. В яких моделях знаходиться найкраще рішення на основі конкретного критерію оптимальності?

а) оптимістичних

б) оптимізації

в) стохастичних

г) статичних

11. В яких моделях описується стан економічного об'єкта в конкретний момент або період часу?

а) динамічних

б) стохастичних

в) детермінованих

г) статичних

12. Які моделі включають взаємозв'язки змінних у часі?

а) детерміновані

б) динамічні

в) стохастичні

г) статистичні

13. Моделі, які передбачають жорсткі функціональні зв'язки між змінними моделі?

а) статичні

б) детерміновані

в) стохастичні

г) статичні

14. Моделі, які припускають наявність випадкового впливу на показники, що досліджуються – це моделі:

а) оптимізації

б) статичні

в) стохастичні

г) динамічні

д) детерміновані

15. Які параметри необхідно визначити при побудові схеми моделі?

16. Перечисліть основні етапи побудови моделі

Тема 2. ЦІЛОЧИСЕЛЬНЕ ПРОГРАМУВАННЯ

Цілочисельне програмування – це розділ математичного програмування, який використовує змінниі лише у цілочисельному вигляді в тому числі і в окремому випадку, коли змінні є бінарними (0; 1). Цілочисельне програмування є розділом більш загального дискретного програмування, яке має справу у більш широкому значенні з неподільностями, комбінаторними задачами, множинами, діапазонами значень. Наприклад, у роботі розглянуті питання дискретної оптимізації у САПР. З математичної точки зору задачі цілочисельного програмування можуть бути лінійними або нелінійними. Ми будемо розглядати лінійні задачі, які мають стандартну форму:

 

(2.1)

 

 

Таким чином, зовнішній вигляд задачі лінійного цілочисельного програмування практично не відрізняється від звичайної задачі ЛП, за виключенням того, що на рішення ЛП накладається додаткове обмеження: визначення лише цілих значень змінних. Припустимо, що ми розв’язали задачу ЛП згідно з моделлю (рис. 1.1) (але без вимоги цілозначності) і отримали область рішень ABCD (рис. 1.1). Цілі значення змінних x_j на рис. 1.1 позначені точками. Ці точки і є метою визначення задач цілочисельного програмування. В результаті задача цілочисельного програмування має область рішень OKLMPN, тобто внутрішню відносно області OABCD звичайної задачі ЛП (на рис. 1.1 область ЛЦП заштрихована).

Задачі лінійного цілочисельного програмування (ЛЦП) вирішують проблеми із змінними, які визначають: кількість одиниць неподільної продукції; розподіл завдань між підприємствами; планування роботи при різних номенклатурах продукції та інш. Встановлено, що округленням лінійного рішення неможливо отримати цілочисельне рішення. Методи рішення задач цілочисельного програмування можна поділити на дві групи:

1. Метод відсічень (відсікаючих площин; метод Гоморі);

2. Комбінаторні методи (метод гілок та меж; аддитивний метод з бінарними змінними).

Метод відсікаючих площин існує у двох варіантах:

1. Перший алгоритм Гоморі для рішення цілком цілочисельних задач;

2. Другий алгоритм Гоморі для рішення частково цілочисельних задач.

Вони відрізняються способом формування відсічення. Ідея розрахунків методом відсікаючих площин для рішення цілком цілочисельних задач (1-ий метод Гоморі) полягає у такому підході:

1. Лінійна задача (9.1) розв’язується без врахування цілочисленності x_j будь-яким симплекс-методом (наприклад, прямим симплекс-методом). В результаті отримують оптимальний опорний план, який має канонічний вигляд:

(2.2)

2) Якщо серед рівнянь-обмежень (2.2) є дробові значення базисних змінних x_i = b_i, то обирають серед них таке значення, яке має найбільш у дрібну частину. Це рівняння записують і у вигляді:

і перетворюють їх у додаткову нерівність

(2.3)

 

 

Правила обрання чисел:

1. Якщо дробове число a_ij або b_i є додатнім числом, то [ a_ij ] та [ b_i ] є цілими додатніми числами і дорівнюють цілій частині числа a_ij або b_i. Наприклад:

a_jj=2,3; [a_ij]=2; a_ij=a_ij – [a_ij]=2,3 – 2=0,3

b_i=1,25; [b_i]=1; b_i=b_i – [b_i]=1,25 – 1=0,25

2. Якщо дробове число a_ij або b_i є від’ємним числом, то [ a_ij ] та [ b_i ] є від’ємним цілим числом, яке по абсолютному значенню на “1” більше за абсолютне значення цілої частини числа a_ij або b_i. Наприклад:

3. Додаткова нерівність (2.3) має лише додатні коефіцієнти. Вона множенням на “-1” спочатку приводиться до вигляду, який повинна мати нерівність у симплекс-методі згідно із стандартною формою:

а потім за допомогою додаткової змінної x_n+1 перетворюється у рівняння:

яке додається до оптимального опорного плану-системи (2.2) і сумісно з ним створює псевдоплан (він так називається, бо має одне від’ємне значення.

4. Цей псевдоплан розв’язується двоїстим симплекс-методом. В результаті отримують новий оптимальний опорний план (з додатніми значеннями b_i та a_0j). Якщо в новому оптимальному опорному плані існують базисні змінні x_j = b_i, які мають дробові значення, то знов додають одне додаткове обмеження, і процес розрахунків повторюється до отримання цілочисельних значень базисних змінних.

Ознакою відсутності рішення задачі є наявність в таблиці хоча б одного рядка з цілими величинами a_ij та вільним дробовим членом b _i, що вказує на відсутність рішення у цілих числах (наприклад, 5x₁ + 10x₂ – 6x₃=7/3). На відміну від задач ЛП, задачі ЛПЦ вимагають значно більшого об’єму обчислень навіть при малих і= m та j = n. Як показала практика, жоден з варіантів методу відсікаючих площин не забезпечує високої ефективності.