2 Варіанти практичних завдань
Тема 1 Лінійне програмування
Завдання 1 Розв´язання задачі лінійного програмування
У матричному вигляді задана задача лінійного програмування,З.Л.П., таблиця 1.
Методом Жордана-Гаусса
а) знайти початковий опорний план і обчислити Z( );
б) перейти до іншого опорного плану й обчислити Z( ).
Для одного з опорних планів виразити базисні змінні через вільні, перейти від рівностей в обмеженнях задачі до нерівностей і розв´язати задачу геометрично.
Виходячи з опорного плану з «гіршою» функцією мети замінити задачу лінійного програмування в канонічній формі та розв´язати її симплекс-методом.
Розв´язати вихідну задачу методом штучного базису.
Таблиця 1– Дані за варіантами
№ вар. |
Z |
Матриця А |
|
№ вар. |
Z |
Матриця А |
|
||||||||
1 |
max |
1 |
1 |
1 |
0 |
1 |
10 |
16 |
max |
3 |
4 |
1 |
0 |
0 |
12 |
1 |
2 |
3 |
3 |
4 |
30 |
-1 |
1 |
0 |
1 |
0 |
1 |
||||
-2 |
-1 |
1 |
5 |
2 |
8 |
2 |
3 |
1 |
2 |
1 |
17 |
||||
|
2 |
1 |
-1 |
0 |
4 |
- |
|
9 |
0 |
2 |
-1 |
0 |
- |
||
2 |
min |
1 |
2 |
1 |
-1 |
2 |
14 |
17 |
max |
2 |
1 |
1 |
1 |
1 |
11 |
-2 |
-3 |
1 |
7 |
0 |
0 |
-1 |
6 |
2 |
-1 |
3 |
15 |
||||
1 |
3 |
3 |
2 |
5 |
34 |
1 |
4 |
3 |
1 |
2 |
15 |
||||
|
-3 |
-4 |
1 |
-5 |
1 |
- |
|
-1 |
-3 |
0 |
0 |
0 |
- |
||
3 |
min |
-1 |
-1 |
2 |
2 |
-1 |
8 |
18 |
max |
3 |
4 |
1 |
0 |
0 |
12 |
2 |
0 |
1 |
2 |
1 |
17 |
3 |
2 |
1 |
1 |
1 |
16 |
||||
1 |
-5 |
-1 |
2 |
-2 |
-7 |
1 |
-3 |
0 |
0 |
1 |
3 |
||||
|
-3 |
1 |
2 |
1 |
1 |
- |
|
5 |
3 |
2 |
-1 |
1 |
- |
||
4 |
max |
1 |
-1 |
2 |
4 |
0 |
10 |
19 |
min |
-2 |
-1 |
-2 |
-1 |
-1 |
-18 |
1 |
-1 |
3 |
6 |
1 |
18 |
1 |
1 |
1 |
0 |
1 |
11 |
||||
Продовження таблиці 1
|
|
-2 |
3 |
-5 |
-11 |
0 |
-23 |
|
|
1 |
1 |
2 |
2 |
2 |
19 |
|
1 |
0 |
-1 |
1 |
2 |
- |
|
1 |
-2 |
1 |
-1 |
0 |
- |
||
5 |
min |
2 |
5 |
-1 |
-9 |
2 |
8 |
20 |
min |
1 |
-2 |
1 |
3 |
-2 |
-1 |
1 |
-2 |
1 |
3 |
-2 |
-2 |
1 |
-3 |
1 |
4 |
-3 |
-5 |
||||
-3 |
5 |
0 |
-2 |
8 |
26 |
2 |
-3 |
3 |
7 |
-2 |
10 |
||||
|
1 |
3 |
-1 |
1 |
2 |
- |
|
0 |
1 |
1 |
-1 |
2 |
- |
||
6 |
max |
1 |
-2 |
1 |
3 |
-2 |
-2 |
21 |
min |
-3 |
5 |
0 |
-2 |
8 |
23 |
1 |
-3 |
1 |
4 |
-3 |
-6 |
2 |
5 |
-1 |
-9 |
2 |
10 |
||||
2 |
-3 |
3 |
7 |
-2 |
8 |
1 |
-2 |
1 |
3 |
-2 |
-1 |
||||
|
0 |
0 |
1 |
-1 |
4 |
- |
|
2 |
-1 |
3 |
0 |
-1 |
- |
||
7 |
min |
-2 |
-1 |
-2 |
-1 |
-1 |
-16 |
22 |
min |
1 |
-1 |
2 |
4 |
0 |
11 |
1 |
1 |
1 |
0 |
1 |
10 |
1 |
-1 |
3 |
6 |
1 |
19 |
||||
1 |
1 |
2 |
2 |
2 |
18 |
-2 |
3 |
-5 |
-11 |
0 |
-26 |
||||
|
3 |
-2 |
0 |
1 |
2 |
- |
|
3 |
0 |
-1 |
1 |
-2 |
- |
||
8 |
max |
-1 |
2 |
1 |
0 |
0 |
2 |
23 |
min |
2 |
-1 |
3 |
5 |
0 |
18 |
3 |
5 |
1 |
1 |
2 |
14 |
1 |
1 |
-1 |
-4 |
-1 |
-5 |
||||
1 |
-1 |
0 |
0 |
1 |
1 |
3 |
2 |
-2 |
-9 |
-3 |
-11 |
||||
|
2 |
0 |
1 |
-1 |
1 |
- |
|
1 |
-2 |
-1 |
3 |
0 |
- |
||
9 |
max |
1 |
1 |
-1 |
-4 |
-1 |
-4 |
24 |
min |
-2 |
-3 |
1 |
7 |
0 |
-2 |
3 |
2 |
-2 |
-9 |
-3 |
-9 |
1 |
2 |
1 |
-1 |
2 |
15 |
||||
2 |
-1 |
3 |
5 |
0 |
17 |
1 |
3 |
3 |
2 |
5 |
35 |
||||
|
2 |
-1 |
1 |
0 |
-1 |
- |
|
0 |
-2 |
1 |
-1 |
1 |
- |
||
10 |
max |
-1 |
1 |
1 |
0 |
0 |
2 |
25 |
min |
1 |
2 |
3 |
3 |
4 |
31 |
5 |
2 |
1 |
1 |
1 |
11 |
-2 |
-1 |
1 |
5 |
2 |
6 |
||||
3 |
2 |
0 |
0 |
1 |
6 |
1 |
1 |
1 |
0 |
1 |
11 |
||||
|
6 |
-1 |
2 |
-1 |
1 |
- |
|
-1 |
2 |
1 |
0 |
-2 |
- |
||
11 |
max |
2 |
1 |
1 |
1 |
3 |
5 |
26 |
max |
1 |
-1 |
3 |
6 |
1 |
18 |
3 |
0 |
2 |
-1 |
6 |
7 |
-2 |
3 |
-5 |
-11 |
0 |
-24 |
||||
1 |
0 |
-1 |
2 |
1 |
2 |
1 |
-1 |
2 |
4 |
0 |
10 |
||||
|
0 |
0 |
3 |
-2 |
-1 |
- |
|
1 |
-4 |
1 |
0 |
-2 |
0 |
||
12 |
min |
3 |
-1 |
1 |
2 |
-1 |
2 |
27 |
max |
1 |
2 |
3 |
3 |
4 |
33 |
-5 |
3 |
2 |
-1 |
1 |
4 |
1 |
1 |
1 |
0 |
1 |
12 |
||||
1 |
-1 |
1 |
2 |
1 |
11 |
-2 |
-1 |
1 |
5 |
2 |
5 |
||||
|
-3 |
-2 |
1 |
-1 |
-2 |
- |
|
0 |
2 |
-1 |
2 |
-1 |
- |
||
13 |
max |
5 |
5 |
1 |
2 |
1 |
28 |
28 |
min |
-1 |
0 |
-2 |
1 |
0 |
2 |
-1 |
2 |
0 |
1 |
0 |
2 |
0 |
1 |
-1 |
2 |
0 |
1 |
||||
3 |
4 |
0 |
0 |
1 |
12 |
0 |
0 |
1 |
-1 |
1 |
5 |
Продовження таблиці 1
|
|
1 |
-4 |
1 |
1 |
1 |
- |
|
|
1 |
1 |
0 |
0 |
0 |
- |
14 |
min |
0 |
5 |
-2 |
1 |
-1 |
8 |
29 |
max |
-3 |
1 |
1 |
2 |
2 |
2 |
1 |
-2 |
1 |
1 |
1 |
3 |
1 |
1 |
1 |
-2 |
-2 |
-2 |
||||
1 |
-5 |
2 |
1 |
2 |
0 |
1 |
4 |
2 |
1 |
-1 |
9 |
||||
|
2 |
-1 |
3 |
-1 |
2 |
- |
|
1 |
1 |
-3 |
1 |
-1 |
- |
||
15 |
min |
1 |
7 |
-2 |
1 |
2 |
12 |
30 |
max |
1 |
-3 |
1 |
4 |
-3 |
-8 |
3 |
2 |
1 |
-1 |
2 |
3 |
1 |
-2 |
1 |
3 |
-2 |
-3 |
||||
1 |
0 |
1 |
-1 |
1 |
-1 |
2 |
-3 |
3 |
7 |
-2 |
7 |
||||
|
3 |
1 |
-1 |
2 |
-1 |
- |
|
1 |
-4 |
1 |
0 |
-2 |
- |
Література: [1, с. 37–68; 4, с. 49– 75; 7, с. 5– 31].
Завдання 2. Розв´язання задачі про розподіл ресурсів з економічним аналізом отриманих результатів
Підприємство може виготовляти чотири види продукції П-1, П-2, П-3, П-4. Збут будь-якого її обсягу забезпечений. Норми витрати ресурсів і прибуток від одиниці кожного виду продукції наведені в таблиці 2. Виконати економічний аналіз лінійної моделі:
побудувати модель вихідної та двоїстої задач, знайти оптимальні плани x0 і y0;
дати економічне тлумачення основних і додаткових змінних вихідної та двоїстої задач;
проаналізувати доцільне розширення асортименту продукції за рахунок включення нової продукції П5;
установити діапазони зміни вихідних даних за ресурсами і ціною од. продукції, за яких структура оптимального плану не змінюється.
Таблиця 2– Дані за варіантами
№ вар. |
Обсяг ресурсів: трудові, матеріальні, верстатні |
Норми витрат ресурсів на одиницю продукції |
Нова продукція П5 |
|||
П1 |
П2 |
П3 |
П4 |
|||
2.1 |
4000 |
3 |
4 |
4 |
5 |
5 |
4500 |
2 |
0 |
3 |
4 |
3 |
|
8000 |
10 |
12 |
10 |
8 |
8 |
|
Ціна од. продукції |
46 |
12 |
10 |
8 |
50 |
|
2.2 |
2500 |
4 |
3 |
2 |
4 |
4 |
Продовження таблиці 2
|
2800 |
3 |
2 |
0 |
5 |
5 |
5000 |
8 |
10 |
10 |
12 |
10 |
|
Ціна од. продукції |
36 |
40 |
42 |
45 |
48 |
|
2.3 |
3400 |
5 |
6 |
6 |
5 |
4 |
4000 |
2 |
0 |
3 |
4 |
6 |
|
8000 |
15 |
10 |
10 |
15 |
8 |
|
Ціна од. продукції |
50 |
45 |
52 |
48 |
54 |
|
2.4 |
3500 |
6 |
3 |
4 |
5 |
4 |
4200 |
2 |
0 |
3 |
5 |
5 |
|
10000 |
15 |
15 |
10 |
0 |
8 |
|
Ціна од. продукції |
45 |
48 |
45 |
50 |
55 |
|
2.5 |
3600 |
3 |
5 |
4 |
6 |
5 |
4500 |
0 |
4 |
4 |
7 |
6 |
|
10000 |
18 |
15 |
10 |
14 |
10 |
|
Ціна од. продукції |
50 |
54 |
52 |
50 |
54 |
|
2.6 |
3300 |
2 |
2 |
4 |
3 |
5 |
2600 |
6 |
6 |
0 |
5 |
7 |
|
5000 |
10 |
10 |
12 |
8 |
9 |
|
Ціна од. продукції |
50 |
55 |
52 |
53 |
60 |
|
2.7 |
3600 |
3 |
3 |
4 |
3 |
4 |
2800 |
0 |
5 |
4 |
6 |
5 |
|
4200 |
15 |
10 |
12 |
10 |
12 |
|
Ціна од. продукції |
45 |
40 |
40 |
45 |
50 |
|
2.8 |
3350 |
2 |
3 |
1 |
2 |
3 |
2550 |
4 |
5 |
5 |
3 |
6 |
|
5500 |
10 |
8 |
8 |
10 |
12 |
|
Ціна од. продукції |
40 |
45 |
40 |
42 |
50 |
|
2.9 |
2800 |
3 |
4 |
3 |
3 |
4 |
3000 |
2 |
0 |
2 |
4 |
5 |
|
8000 |
15 |
35 |
40 |
40 |
45 |
|
Ціна од. продукції |
30 |
35 |
40 |
40 |
45 |
|
2.10 |
3400 |
2 |
2 |
3 |
5 |
6 |
2500 |
4 |
4 |
0 |
7 |
8 |
|
7000 |
12 |
10 |
18 |
10 |
12 |
|
Ціна од. продукції |
45 |
40 |
42 |
48 |
50 |
|
2.11 |
3300 |
2 |
2 |
4 |
3 |
5 |
2600 |
6 |
6 |
0 |
5 |
7 |
|
5000 |
10 |
12 |
12 |
8 |
9 |
|
|
Ціна од. продукції |
50 |
55 |
52 |
53 |
60 |
2.12 |
3600 |
3 |
3 |
4 |
3 |
4 |
2800 |
0 |
5 |
4 |
6 |
5 |
|
|
4200 |
15 |
10 |
12 |
10 |
12 |
Ціна од. продукції |
45 |
40 |
40 |
45 |
50 |
|
2.13 |
3350 |
2 |
3 |
1 |
2 |
3 |
2550 |
4 |
5 |
5 |
3 |
6 |
|
5500 |
10 |
8 |
8 |
10 |
12 |
|
Ціна од. продукції |
40 |
45 |
40 |
42 |
50 |
|
2.14 |
2800 |
3 |
4 |
3 |
3 |
4 |
3000 |
2 |
0 |
2 |
4 |
5 |
Продовження таблиці 2
|
8000 |
15 |
35 |
40 |
40 |
45 |
Ціна од. продукції |
30 |
35 |
40 |
40 |
45 |
|
2.15 |
3400 |
2 |
3 |
3 |
5 |
6 |
2500 |
4 |
4 |
0 |
7 |
8 |
|
7000 |
12 |
10 |
18 |
10 |
12 |
|
Ціна од. продукції |
45 |
40 |
42 |
48 |
50 |
|
2.16 |
2400 |
2 |
3 |
4 |
5 |
4 |
2100 |
0 |
3 |
4 |
4 |
5 |
|
5000 |
8 |
10 |
6 |
8 |
8 |
|
Ціна од. продукції |
50 |
48 |
45 |
50 |
52 |
|
2.17 |
3000 |
3 |
4 |
5 |
4 |
3 |
2800 |
2 |
0 |
5 |
5 |
5 |
|
5000 |
10 |
8 |
8 |
9 |
10 |
|
Ціна од. продукції |
40 |
45 |
48 |
50 |
48 |
|
2.18 |
3200 |
1 |
3 |
4 |
3 |
4 |
4000 |
3 |
4 |
5 |
6 |
6 |
|
7000 |
12 |
8 |
10 |
10 |
12 |
|
Ціна од. продукції |
42 |
45 |
46 |
50 |
52 |
|
2.19 |
3500 |
4 |
3 |
2 |
4 |
5 |
2400 |
0 |
3 |
5 |
6 |
6 |
|
3800 |
11 |
12 |
10 |
0 |
10 |
|
Ціна од. продукції |
30 |
35 |
36 |
40 |
42 |
|
2.20 |
3000 |
3 |
1 |
0 |
4 |
5 |
5000 |
5 |
5 |
3 |
6 |
6 |
|
6000 |
10 |
10 |
12 |
10 |
12 |
|
Ціна од. продукції |
60 |
65 |
50 |
55 |
75 |
|
2.21 |
4260 |
4 |
6 |
4 |
8 |
6 |
4840 |
6 |
8 |
4 |
6 |
4 |
|
6020 |
8 |
10 |
12 |
10 |
8 |
|
Ціна од. продукції |
48 |
36 |
30 |
32 |
50 |
|
2.22 |
2620 |
6 |
8 |
4 |
6 |
6 |
2760 |
4 |
2 |
4 |
6 |
8 |
|
5400 |
10 |
8 |
12 |
10 |
12 |
|
Ціна од. продукції |
32 |
42 |
46 |
44 |
50 |
|
2.23 |
3600 |
8 |
9 |
9 |
7 |
6 |
4200 |
6 |
4 |
8 |
6 |
8 |
|
|
7800 |
12 |
10 |
10 |
14 |
9 |
Ціна од. продукції |
48 |
42 |
50 |
46 |
52 |
|
2.24 |
3750 |
8 |
4 |
6 |
6 |
4 |
4370 |
4 |
2 |
4 |
6 |
6 |
|
|
8500 |
16 |
12 |
10 |
2 |
6 |
Ціна од. продукції |
42 |
46 |
44 |
48 |
52 |
|
2.25 |
3800 |
6 |
9 |
4 |
8 |
10 |
4600 |
2 |
4 |
3 |
6 |
5 |
|
9200 |
12 |
10 |
8 |
14 |
12 |
|
Ціна од. продукції |
48 |
56 |
50 |
52 |
54 |
|
2.26 |
2400 |
2 |
3 |
4 |
5 |
4 |
2100 |
0 |
3 |
4 |
4 |
5 |
|
5000 |
8 |
10 |
6 |
8 |
8 |
Продовження таблиці 2
|
Ціна од. продукції |
50 |
48 |
45 |
50 |
52 |
2.27 |
3000 |
3 |
4 |
5 |
4 |
3 |
2800 |
2 |
0 |
5 |
5 |
5 |
|
5000 |
10 |
8 |
8 |
9 |
10 |
|
Ціна од. продукції |
40 |
48 |
45 |
50 |
48 |
|
2.28 |
3200 |
1 |
3 |
4 |
3 |
4 |
4000 |
3 |
4 |
5 |
6 |
6 |
|
7000 |
12 |
8 |
10 |
10 |
12 |
|
Ціна од. продукції |
42 |
45 |
46 |
50 |
52 |
|
2.29 |
3500 |
4 |
3 |
2 |
4 |
5 |
2400 |
0 |
3 |
5 |
6 |
6 |
|
3800 |
11 |
12 |
10 |
0 |
10 |
|
Ціна од. продукції |
30 |
35 |
36 |
40 |
42 |
|
2.30 |
3000 |
3 |
2 |
0 |
4 |
5 |
5000 |
5 |
5 |
3 |
6 |
6 |
|
6000 |
10 |
10 |
12 |
10 |
12 |
|
Ціна од. продукції |
60 |
65 |
50 |
55 |
75 |
Література: [1, с. 77–99; 4, с. 85– 102; 7, с. 5– 33].
Завдання 3 Розв´язання транспортної задачі з економічним аналізом отриманих результатів
Є три постачальники і чотири споживачі однорідного продукту. Потужності постачальників і попити споживачів, а також витрати на перевезення одиниці вантажу для кожної пари «постачальник-споживач» зведені в таблицю 3 постачань.
Задача полягає у наступному: знайти обсяги перевезень для кожної пари «постачальник-споживач» так, щоб:
1) потужності всіх постачальників були реалізовані;
2) попити всіх споживачів були задоволені;
3) сумарні витрати на перевезення були мінімальні.
Таблиця 3 – Дані для розв’язання транспортної задачі
1 a:={200, 270, 130} b:={120, 80, 240, 160}
|
16 a:={25, 25, 50} b:={15, 15, 40, 30}
|
2 a:={110, 190, 90} b:={80, 60, 170, 80}
|
17 a:={40, 27, 23} b:={30, 25, 15, 20}
|
3 a:={160, 140, 60} b:={80, 80, 60, 140}
|
18 a:={15, 58, 35} b:={30, 23, 35, 20}
|
4 a:={115, 145, 100} b:={70, 220, 40, 30}
|
19 a:={90, 60, 90} b:={24, 40, 80, 96}
|
5 a:={180, 100, 120} b:={110, 90, 120, 80}
|
20 a:={16, 28, 30} b:={22, 18, 13, 21}
|
6 a:={100, 150, 50} b:={75, 80, 60, 85}
|
21 a:={30, 25, 50} b:={15, 15, 45, 30}
|
Продовження таблиці 3
7 a:={45, 85, 20} b:={40, 30, 30, 50}
|
22 a:={50, 27, 23} b:={35, 30, 15, 20}
|
8 a:={50, 40, 20} b:={33, 22, 39, 16}
|
23 a:={25, 58, 35} b:={40, 23, 35, 20}
|
9 a:={35, 85, 60} b:={20, 60, 55, 45}
|
24 a:={85, 55, 90} b:={24, 40, 80, 86}
|
10 a:={16, 24, 30} b:={32, 14, 14, 10}
|
25 a:={20, 28, 30} b:={22, 18, 17, 21}
|
11 a:={180, 60, 80} b:={120, 40, 80, 80}
|
26 a:={100, 270, 130} b:={120, 80, 240, 60}
|
12 a:={80, 90, 70} b:={80, 50, 70, 40}
|
27 a:={110, 90, 60} b:={80, 60, 70, 50}
|
Продовження таблиці 3
13 a:={75, 200, 220} b:={180, 120, 90, 105}
|
28 a:={150, 140, 60} b:={70, 80, 60, 140}
|
14 a:={130, 80, 160} b:={70, 60, 120, 120}
|
29 a:={65, 85, 30} b:={50, 40, 30, 60}
|
15 a:={160, 140, 170} b:={120, 50, 190, 110}
|
30 a:={180, 200, 20} b:={110, 90, 120, 80}
|
Література: [1, с. 102–138; 4, с. 117– 139; 8, с. 5– 35].