3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач (тема 4)

   1. Побудувати двоїсту задачу. Дати економічну інтерпретацію прямої та двоїстої задач.

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

а)

б)

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

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

а)

б)

3.1.4 Визначити, чи є оптимальними такі плани сформульованої задачі лінійного програмування:

min Z = 12x₁ – 4x₂ + 2x₃;

а) Х = (8/7; 3/7; 0); б) Х = (0; 1/5; 8/5); в) Х = (1/3; 0; 1/3).

Відповідь: а) ні; б) так, Х* = (0; 1/5; 8/5), min Z = 12/5; в) ні.

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

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

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

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

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

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

3.1.5 До заданої задачі лінійного програмування записати двоїсту задачу. Розв’язавши двоїсту задачу графічно, визначити оптимальний план прямої задачі.

min Z = x₁ + 2x₂ + 2x₃;

Відповідь: min Z = max F = 14/3; Х* = (0; 5/3; 2/3); Y* = (– 2/3; 4/3)

2. Розв’язати задачу лінійного програмування двоїстим симплексним методом.

3.2.1

3.2.2 Побудувати двоїсту задачу до заданої задачі лінійного програмування. Визначити оптимальні плани прямої та двоїстої задач. Варіанти завдань

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
31	32	33
34	35	36
37	38	39
40	41	42
43	44	45
46	47	48
49	50	51

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

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

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

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

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

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

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

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

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

а) Підприємство виготовляє три види продукції А, В і С, використовуючи для цього три види ресурсів 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

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

Таблиця 1

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

Відома ціна одиниці продукції кожного виду: А - 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

3. Післяоптимізаційний аналіз задач лінійного програмування.

3.3.1 У наведених нижче задачах виконати такі дії:

1) записати математичні моделі прямої та двоїстої задач;

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

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

4) обчислити інтервали стійкості двоїстих оцінок стосовно зміни запасів дефіцитних ресурсів;

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

а) Підприємство виготовляє три види продукції: А, В і С, використовуючи для цього три види ресурсів 1, 2, 3. Норми витрат усіх ресурсів на виробництво одиниці продукції та запаси ресурсів наведені в таблиці:

Ресурс	Норма витрат ресурсу на виробництво одиниці продукції виду			Запас ресурсу
	А	В	С
1	18	15	12	360
2	6	4	8	192
3	5	3	3	180

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

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

Базис	Сбаз	План	9	10	16	0	0	0
			х1	х2	х3	х4	х5	х6
х2	10	8	1	1	0	1/9	–1/6	0
х3	16	20	1/4	0	1	–1/18	5/24	0
х6	0	96	5/4	0	0	–1/6	–1/8	1
Zj – cj ≥ 0		400	5	0	0	2/9	5/3	0

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

Ресурс	Норма витрат ресурсу на виробництво одиниці продукції виду				Запас ресурсу
	А	В	С
1	4	2	1	180
2	3	1	3	210
3	1	2	5	244

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

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

Базис	Сбаз	План	10	14	12	0	0	0
			х1	х2	х3	х4	х5	х6
х2	14	82	19/8	1	0	5/8	0	–1/8
х5	0	80	23/8	0	0	1/8	1	–5/8
х3	12	16	–3/4	0	1	–1/4	0	1/4
Zj – cj ≥ 0		1340	57/4	0	0	23/4	0	5/4