- •Значення цільової функції повинно бути максимізовано.
- •Усі обмеження задачі повинні мати вигляд строгих рівнянь.
- •Так, в ліву частину нерівностей виду
- •Всі змінні задачі повинні бути невід’ємні.
- •Завдання для самостійного виконання
- •2. Знаходимо півплощини, що визначаються нерівностями.
- •3 . Знаходимо многокутник розв’язків. Він визначається як перетин усіх півплощин (рис.2).
- •5. Побудуємо лінію рівня lo , яка перпендикулярна до вектора напрямку і проходить через початок координат.
- •7. Визначаємо координати точок максимуму та мінімуму функції цілі, розв’язуючи системи відповідних рівнянь.
- •Геометричний метод розв’язування задач лінійного програмування
- •Приклад 2.
- •Розв’язання:
- •1. Будуємо прямі, рівняння яких отримуються внаслідок заміни в обмеженнях знаків нерівностей на знаки точних рівностей. Для нашого прикладу будуємо наступні прямі:
- •Знайдені розв’язки визначають оптимальні плани задачі, що розглядається.
- •8. Обчислюємо значення цільової функції в точках максимуму і мінімуму.
- •Розв’язування задач за допомогою симплекс-методу Приклад 3.
- •Розв’язання:
- •5. Записуємо робочу модель.
- •7. Алгоритм симплекс-методу.
- •З водимо систему обмежень до одиничного базису:
- •Виконуємо перерахунок елементів q-го ведучого рядка за формулою:
- •1. За допомогою симплекс-методу знайти такий план виробництва, який би забезпечував найбільший прибуток.
- •2. Скласти модель двоїстої задачі. Використовуючи відповідність між змінними прямої і двоїстої задач та симплексну таблицю для прямої задачі, записати оптимальний розв’язок двоїстої задачі.
- •3. Дати повний економічний аналіз основних і додаткових змінних обох задач.
- •Транспортна задача
- •Приклад 4. Для транспортної задачі, вихідні дані якої наведені в таблиці 2, знайти оптимальний план.
- •Розв’язання:
- •1. Визначаємо тип транспортної задачі.
- •2. Знаходимо опорний план транспортної задачі, використовуючи метод північно-західного (лівого верхнього) кута.
- •3. Перевіряємо опорний план тз на оптимальність за допомогою методу потенціалів.
- •4. Поліпшуємо опорний план.
1. За допомогою симплекс-методу знайти такий план виробництва, який би забезпечував найбільший прибуток.
2. Скласти модель двоїстої задачі. Використовуючи відповідність між змінними прямої і двоїстої задач та симплексну таблицю для прямої задачі, записати оптимальний розв’язок двоїстої задачі.
3. Дати повний економічний аналіз основних і додаткових змінних обох задач.
Варіант |
Ціна за одиницю продукції |
Запаси сировини |
Витрати сировини на кожен вид продукції |
||||||||
Р1 |
Р2 |
||||||||||
Р1 |
Р2 |
S1 В2 |
S2 |
S3 |
S1 В2 |
S2 |
S3 |
S1 В2 |
S2 |
S3 |
|
|
|
10 |
8 |
273 |
100 |
380 |
3 |
1 |
2 |
2 |
1 |
5 |
|
|
18 |
15 |
102 |
91 |
210 |
3 |
4 |
10 |
6 |
3 |
4 |
|
|
10 |
14 |
249 |
438 |
812 |
2 |
1 |
7 |
1 |
2 |
3 |
|
|
24 |
9 |
224 |
428 |
336 |
2 |
3 |
4 |
1 |
2 |
1 |
|
|
8 |
12 |
801 |
768 |
807 |
9 |
3 |
6 |
4 |
8 |
7 |
|
|
14 |
12 |
273 |
444 |
480 |
3 |
4 |
3 |
2 |
3 |
4 |
|
|
11 |
5 |
91 |
34 |
80 |
3 |
2 |
5 |
4 |
1 |
2 |
|
|
18 |
16 |
182 |
316 |
238 |
1 |
1 |
2 |
2 |
4 |
1 |
|
|
9 |
7 |
1455 |
1870 |
1815 |
11 |
9 |
15 |
5 |
10 |
4 |
|
|
12 |
21 |
131 |
505 |
348 |
1 |
2 |
3 |
1 |
5 |
2 |
|
|
32 |
16 |
48 |
93 |
18 |
4 |
7 |
1 |
1 |
4 |
1 |
|
|
9 |
6 |
552 |
567 |
392 |
7 |
9 |
2 |
8 |
5 |
8 |
|
|
12 |
8 |
196 |
567 |
552 |
1 |
9 |
7 |
4 |
5 |
8 |
|
|
7 |
9 |
60 |
195 |
175 |
2 |
6 |
4 |
2 |
9 |
9 |
|
|
16 |
12 |
520 |
248 |
361 |
16 |
9 |
7 |
17 |
4 |
13 |
|
|
40 |
32 |
80 |
75 |
32 |
5 |
5 |
2 |
2 |
1 |
1 |
|
|
16 |
20 |
235 |
140 |
130 |
8 |
2 |
4 |
7 |
8 |
6 |
|
|
12 |
8 |
864 |
945 |
864 |
3 |
9 |
6 |
8 |
4 |
7 |
|
|
9 |
15 |
113 |
161 |
285 |
3 |
7 |
2 |
4 |
2 |
15 |
|
|
10 |
30 |
290 |
420 |
561 |
1 |
1 |
2 |
2 |
4 |
3 |
|
|
27 |
41 |
84 |
91 |
98 |
3 |
3 |
2 |
4 |
6 |
5 |
|
|
9 |
8 |
45 |
144 |
96 |
3 |
9 |
3 |
1 |
4 |
4 |
|
|
24 |
36 |
18 |
93 |
48 |
1 |
4 |
1 |
1 |
7 |
4 |
|
|
27 |
24 |
101 |
99 |
37 |
3 |
2 |
1 |
2 |
3 |
1 |
|
|
25 |
12 |
379 |
197 |
335 |
4 |
5 |
11 |
13 |
6 |
5 |
|
|
12 |
9 |
48 |
100 |
225 |
2 |
1 |
4 |
1 |
5 |
15 |
|
|
20 |
15 |
126 |
30 |
120 |
2 |
1 |
6 |
7 |
1 |
1 |
|
|
21 |
18 |
400 |
49 |
220 |
14 |
1 |
9 |
15 |
2 |
5 |
|
|
10 |
7 |
324 |
60 |
500 |
11 |
1 |
15 |
6 |
2 |
14 |
|
|
15 |
10 |
175 |
65 |
60 |
9 |
3 |
2 |
4 |
2 |
2 |
|
|
8 |
10 |
273 |
100 |
380 |
2 |
1 |
5 |
3 |
1 |
2 |
|
|
30 |
10 |
290 |
561 |
420 |
2 |
3 |
4 |
1 |
2 |
1 |
|
|
12 |
10 |
125 |
83 |
152 |
5 |
2 |
1 |
2 |
3 |
8 |
|
|
15 |
21 |
58 |
143 |
197 |
2 |
7 |
3 |
2 |
2 |
8 |
|
|
9 |
7 |
34 |
105 |
91 |
2 |
2 |
3 |
1 |
5 |
4 |
|
|
15 |
18 |
280 |
62 |
260 |
14 |
2 |
2 |
3 |
2 |
13 |
|
|
6 |
9 |
51 |
120 |
300 |
1 |
4 |
2 |
2 |
1 |
15 |
|
|
12 |
15 |
68 |
80 |
91 |
4 |
5 |
3 |
4 |
2 |
2 |
|
|
14 |
10 |
500 |
60 |
324 |
14 |
2 |
6 |
15 |
1 |
11 |
|
|
10 |
12 |
80 |
58 |
75 |
2 |
2 |
3 |
3 |
2 |
2 |
|
|
12 |
10 |
83 |
125 |
152 |
2 |
5 |
1 |
3 |
2 |
8 |
|
|
15 |
30 |
196 |
350 |
68 |
4 |
5 |
2 |
7 |
14 |
1 |
|
|
10 |
6 |
187 |
143 |
29 |
3 |
7 |
1 |
8 |
2 |
1 |
|
|
9 |
12 |
37 |
100 |
360 |
1 |
4 |
5 |
1 |
1 |
12 |
|
|
22 |
12 |
335 |
379 |
591 |
11 |
4 |
15 |
5 |
13 |
18 |
|
|
15 |
12 |
80 |
91 |
68 |
2 |
4 |
2 |
5 |
3 |
4 |
|
|
10 |
18 |
98 |
84 |
91 |
2 |
3 |
6 |
5 |
4 |
3 |
|
|
15 |
18 |
75 |
58 |
80 |
3 |
2 |
2 |
2 |
2 |
3 |
|
|
12 |
9 |
37 |
360 |
100 |
1 |
12 |
1 |
1 |
5 |
4 |
|
|
15 |
20 |
30 |
126 |
120 |
1 |
7 |
1 |
1 |
2 |
6 |
|
|
18 |
15 |
62 |
260 |
280 |
2 |
13 |
3 |
2 |
2 |
14 |
|
|
14 |
10 |
60 |
324 |
500 |
2 |
6 |
14 |
1 |
11 |
15 |
|
|
7 |
9 |
34 |
105 |
91 |
1 |
5 |
4 |
2 |
2 |
3 |
|
|
30 |
20 |
65 |
70 |
235 |
3 |
4 |
7 |
2 |
1 |
8 |
|
|
12 |
10 |
58 |
75 |
80 |
2 |
2 |
3 |
2 |
3 |
2 |
|
|
15 |
18 |
58 |
75 |
80 |
2 |
3 |
2 |
2 |
2 |
3 |
|
|
18 |
10 |
98 |
84 |
91 |
5 |
4 |
3 |
2 |
3 |
6 |
|
|
21 |
15 |
58 |
143 |
197 |
2 |
2 |
8 |
2 |
7 |
3 |
|
|
10 |
14 |
500 |
60 |
324 |
15 |
1 |
11 |
14 |
2 |
6 |
|
|
18 |
21 |
49 |
220 |
400 |
2 |
5 |
15 |
1 |
9 |
14 |
|
|
14 |
12 |
99 |
101 |
74 |
3 |
2 |
2 |
2 |
3 |
2 |
|
|
15 |
30 |
68 |
196 |
350 |
2 |
4 |
5 |
1 |
7 |
14 |
|
|
9 |
7 |
34 |
91 |
105 |
2 |
3 |
2 |
1 |
4 |
5 |
|
|
12 |
25 |
197 |
379 |
335 |
6 |
13 |
5 |
5 |
4 |
11 |
|
|
10 |
15 |
65 |
60 |
175 |
2 |
2 |
4 |
3 |
2 |
9 |
|
|
12 |
22 |
335 |
379 |
591 |
5 |
13 |
18 |
11 |
4 |
15 |
|
|
6 |
9 |
300 |
120 |
51 |
2 |
4 |
1 |
15 |
1 |
2 |
|
|
15 |
9 |
113 |
161 |
285 |
4 |
2 |
15 |
3 |
7 |
2 |
|
|
18 |
10 |
84 |
91 |
98 |
4 |
3 |
5 |
6 |
2 |
3 |
|
|
7 |
10 |
324 |
60 |
500 |
6 |
2 |
14 |
11 |
1 |
15 |
|
|
12 |
15 |
91 |
80 |
68 |
3 |
5 |
4 |
2 |
2 |
4 |
|
|
8 |
12 |
266 |
136 |
88 |
14 |
5 |
1 |
3 |
4 |
4 |
|
|
6 |
10 |
29 |
143 |
187 |
1 |
2 |
8 |
1 |
7 |
3 |
|
|
18 |
15 |
75 |
58 |
80 |
2 |
2 |
3 |
3 |
2 |
2 |
|
|
14 |
12 |
99 |
74 |
101 |
3 |
2 |
2 |
2 |
2 |
3 |
|
|
30 |
20 |
235 |
70 |
65 |
7 |
4 |
3 |
8 |
1 |
2 |
|
|
7 |
9 |
1455 |
1870 |
1815 |
5 |
10 |
4 |
11 |
9 |
15 |
|
|
15 |
18 |
62 |
260 |
280 |
2 |
2 |
14 |
13 |
2 |
3 |
|
|
12 |
8 |
88 |
136 |
266 |
4 |
4 |
3 |
1 |
5 |
14 |
|
|
9 |
6 |
51 |
120 |
300 |
2 |
1 |
15 |
1 |
4 |
2 |
|
|
12 |
22 |
591 |
335 |
379 |
18 |
5 |
13 |
15 |
11 |
4 |
|
|
20 |
15 |
30 |
120 |
126 |
1 |
6 |
2 |
|
1 |
7 |
|
|
12 |
9 |
37 |
100 |
360 |
1 |
1 |
12 |
1 |
4 |
5 |
|
|
8 |
12 |
88 |
136 |
266 |
1 |
5 |
14 |
4 |
4 |
3 |
|
|
10 |
14 |
60 |
500 |
324 |
1 |
15 |
11 |
2 |
14 |
6 |
|
|
7 |
9 |
105 |
91 |
34 |
5 |
4 |
1 |
2 |
3 |
2 |
|
|
8 |
12 |
864 |
864 |
945 |
8 |
7 |
4 |
3 |
6 |
9 |
|
|
18 |
15 |
280 |
260 |
62 |
3 |
13 |
2 |
14 |
2 |
2 |
|
|
10 |
18 |
84 |
98 |
91 |
6 |
3 |
2 |
4 |
5 |
3 |
|
|
12 |
10 |
75 |
58 |
80 |
2 |
2 |
3 |
3 |
2 |
2 |
|
|
30 |
15 |
196 |
350 |
68 |
7 |
14 |
1 |
4 |
5 |
2 |
|
|
21 |
18 |
49 |
400 |
220 |
1 |
14 |
9 |
2 |
15 |
5 |
|
|
10 |
15 |
60 |
65 |
175 |
2 |
2 |
4 |
2 |
3 |
9 |
|
|
41 |
27 |
91 |
84 |
98 |
6 |
4 |
5 |
3 |
3 |
2 |
|
|
18 |
15 |
58 |
75 |
80 |
2 |
2 |
3 |
2 |
3 |
2 |
|
|
9 |
12 |
360 |
100 |
37 |
5 |
4 |
1 |
12 |
1 |
1 |
|
|
12 |
10 |
152 |
83 |
125 |
1 |
2 |
5 |
8 |
3 |
2 |
|
|
20 |
30 |
65 |
70 |
235 |
2 |
1 |
8 |
3 |
4 |
7 |
|
|
10 |
7 |
60 |
324 |
500 |
1 |
11 |
15 |
2 |
6 |
14 |
|
|
21 |
15 |
197 |
143 |
58 |
8 |
2 |
2 |
3 |
7 |
2 |