2. Приклади типових завдань, що виносяться на іспит

1. Розв’язати задачі лінійного програмування графічним методом:

а) Z = x₁ - 2x₂ (min) б) Z = x₁ + 3x₂ (max)

x₁ - x₂  1, x₁ - x₂  1,

x₁ + x₂  2, 2x₁ + x₂  2,

x₁ - 2x₂  0, x₁ - x₂  0,

x₁ 0; x₂  0. x₁ 0; x₂  0.

в) Z = 3x₁ + 2x₂ (min) г) Z = x₁ + x₂ (max)

3x₁ + 2x₂  6, x₁ + 2x₂  10,

x₁ + 4x₂  4, x₁ + 2x₂  2,

x₁ 0; x₂  0. 2x₁ + x₂  10,

x₁ 0; x₂  0.

д) Z = 2x₁ + 4x₂ (max) є) Z = 2x₁ + 4x₂ (min)

3x₁ + 2x₂  11, 3x₁ + 2x₂  11,

-2x₁ + x₂  2, -2x₁ + x₂  2,

-x₁ + 3x₂  0, x₁ - 3x₂  0,

x₁ 0; x₂  0. x₁ 0; x₂  0.

2. На виготовлення двох видів продукції (П₁ і П₂) витрачаються три види ресурсів Наявність ресурсів дорівнює відповідно: 361, 520, 248. Витрати ресурсів на одиницю продукції П₁ становлять відповідно:13, 7, 17; на одиницю продукції П₂ - 16, 4, 9. Ціна за одиницю продукції дорівнює відповідно: 11, 8. Побудувати модель лінійного програмування початкової й двоїстої задач. Знайти такий план виробництва, який би забезпечував найбільшу виручку. Дати економічне тлумачення розв’язків задач.

3. Знайти розв’язок наступних задач лінійного програмування шляхом графічного розв’язування двоїстої задачі й застосування теорем двоїстості:

а)

.

б)

.

4. Для плану визначити, чи він є оптимальним для наступних задач (застосовуючи теореми двоїстості й не розв’язуючи задачі симплексним методом):

а)

б)

5. У наведених далі задачах:

а) побудуйте економіко-математичні моделі початкової й двоїстої задач;

б) приведіть задачі до канонічного виду й дайте економічне тлумачення основних й допоміжних змінних двох задач;

в) з наведеної останньої симплексної таблиці початкової задачі запишіть оптимальні планиі ;

г) визначте дефіцитні й недефіцитні ресурси, рентабельну та збиткову продукцію;

д) знайдіть межі зміни обсягів дефіцитних ресурсів, в котрих оцінка ресурсу залишається сталою (аналіз двоїстих оцінок на стійкість);

е) знайдіть межі зміни обсягів недефіцитних ресурсів;

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

ж) в якому випадку розширення асортименту випуску за рахунок введення нової продукції буде доцільним, чи недоцільним?

5.1. Підприємство виготовляє три види продукції А, В і С, використовуючи для цього три види ресурсів I, II, III. Норми ви­трат усіх ресурсів на одиницю продукції та запаси ресурсів наведено в табл.1

Таблиця 1

І II III

18 6 5

15 4 3

12 8 3

360 192 180

Відома ціна одиниці продукції кожного виду: А - 9 ум.од., В -10 ум. од. і С - 16 ум.од. Визначити план виробництва продукції, що забезпечує підприємству найбільший доход.

Остання симплекс-таблиця даної задачі має такий вигляд (табл.2)

Таблиця 2

Базис	Сб	А0	9	10	16	0	0	0
			X1	X2	X3	X4	X5	X6
X2 X3 X6	10 16 0	8 20 96	1 1/4 5/4	1 0 0	0 1 0	1/9 -1/18 –1/6	-1/6 5/24 -1/8	0 0 1
		400	5	0	0	2/9	5/3	0

5.2. Підприємство виготовляє продукцію видів А, В і С, для чого використовує три види ресурсів І, II, III. Норми витрат усіх ресурсів на одиницю кожної продукції та обсяги ресурсів на під­приємстві наведено в табл.1.

Таблиця 1

Вид ресурсу	Норма витрат на одиницю продукції за видами			Запас ресурсу
	А	В	С
І II III	4 3 1 6 5	2 1 2 4 3	1 3 5 8 3	180 210 244 192 180

Відома ціна одиниці продукції кожного виду: А - 10 ум.од., В -14 ум.од. і С - 12 ум.од. Визначити план виробництва продукції, що забезпечує підприємству найбільший доход.

Остання симплекс-таблиця, що містить оптимальний план задачі, має такий вигляд (табл.2)

Таблиця 2

Базис	Сб	А0	9	10	16	0	0	0
			X1	X2	X3	X4	X5	X6
X2 X5 X3	14 0 12	82 80 16	19/8 23/8 -3/4	1 0 0	0 0 1	5/8 1/8 -1/4	0 1 0	-1/8 -5/8 1/4
		1340	57/4	0	0	23/4	0	5/4

6. На основі умовно-оптимального плану цілочисельної задачі побудувати допоміжне обмеження Гоморі, приєднати його до умовно-оптимального плану, показаного у наведений нижче таблиці, і знайти цілі значення змінних задачі лінійного програмування.

а)

І	Базис	Сб	А0	-4	1	2	0	3
				А1	А2	А3	А4	А5
1	Х1	-4	7/2	1	-5/2	0	5/2	-3/2
2	Х3	2	5/2	0	1/2	1	31/2	11/2
			-9	0	10	0	21	14

б)

І	Базис	Сб	А0	1	-1	3	4	2
				А1	А2	А3	А4	А5
1	Х1	1	14/3	1	-2/3	0	5/3	1/3
2	Х3	3	11/3	0	1/3	1	7/3	1
			47/3	0	4/3	0	14/3	11/3

7. Розв’язати наступну задачу: компанія контролює три фабрики А₁, А₂, А₃, здатні виготовляти 150, 60 та 80 тис.од. продукції щотижня. Компанія уклала договір з чотирма замовниками В₁, В₂, В₃, В₄, яким потрібно щотижня відповідно 110, 40, 60 та 80 тис.од. продукції. Вартість виробництва та транспортування 1000 од. продукції замовниками з кожної фабрики наведено в таблиці.

Фабрика	Вартість виробництва і транспортування 1000 од. продукції за замовниками
	В1	В2	В3	В4
А1	4	4	2	5
А2	5	3	1	2
А3	2	1	4	2

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

8. Розв’язати графічним методом задачу нелінійного програмування; знайти глобальний екстремум:

а)

.

б)

,

.

9. Використовуючи метод множників Лагранжа, знайти точки умовного екстремуму наступної задачі нелінійного програмування:

10. Користуючись теоремою Куна-Таккера, скласти функцію Лагранжа та записати необхідні і достатні умови існування сідлової точки наступної задачі нелінійного програмування:

11. Розв’язати градієнтним методом наступну задачу нелінійного програмування, почавши процес з точки :

12. Розв’язати графічним методом наступну задачу дробово-лінійного програмування:

за умов

13. Фірма спеціалізується на виробництві офісних меблів, зокрема випускає дві моделі збірних книжкових полиць: А та В. Полиці обох моделей обробляють на двох верстатах: шліфувальному та полірувальному. Тривалість обробки у хвилинах однієї полиці кожної моделі відома:

Тип верстату	Тривалість обробки однієї полиці, хв.
	А	В
Шліфувальний	15	40
Полірувальний	50	30

Час роботи обох верстатів обмежений і становить: для шліфувального 600 хв., для полірувального – 900 хв. на тиждень.

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

Прибуток фірми від реалізації однієї полиці моделі А становить 300 грн., а моделі В – 400 грн.

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

Необхідно: 1) розв’язати задачу графічним методом; 2) визначити двоїсту оцінку для ресурсу – час роботи шліфувального верстату.

14. В приведеній нижче таблиці (табл.1) містяться величини можливого збільшення продукції чотирьох нафтопереробних заводів при здійсненні додаткових капіталовкладень на їх реконструкцію та модернізацію.

Таблиця 1

Капіталовкладення тис. грн	Збільшення виробництва продукції, млн. грн. заводи
s	1	2	3	4
50	25	30	36	28
100	60	70	64	56
150	100	90	95	110
200	140	122	130	142

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

Таблиця 2

	j=4		j=3		j=2		j=1
s
50	50	28	50	36	0	36
100	100	56	50,100	64	100	70
150	150	110	0	110	0	110
200	200	142	50	146	0	146	0	146

15. Дві конкуруючі фірми (гравці) реалізують на ринку продукцію, котра швидко псується. Кожний з гравців прагне зайняти по два сегмента ринку (має дві стратегії). Відомі прибуток (виграш) або збиток (програш) для кожного гравця і кожного сегмента ринку, які наведені в платіжній матриці С. Розв’язати гру , знайти пару оптимальних стратегій і ціну гри.

а) С = ;б) С =

в)С = ;г)