- •Міністерство освіти і науки України
- •Сумський державний університет
- •Конотопський інститут
- •Методичні вказівки
- •Завдання для практичних робіт
- •Тема 1. "Побудова математичних моделей задач лінійного програмування". Задача 1.
- •Задача 2.
- •Задача 3.
- •Задача 4.
- •Задача 5.
- •Задача 6.
- •Задача 7.
- •Задача 8.
- •Приклади розв’язування задач.
- •Задача 1.
- •Задача 2.
- •Задачі для самостійної роботи.
- •Задача 1.
- •Задача 2
- •Задачі для самостійної роботи.
- •Тема: "Транспортна задача. Метод потенціалів" Задача 1
- •Задача 2
- •Тема. Метод множників Лагранжа до задач нелінійного програмування (знп), система умов якого включає й обмеження нерівності.
- •Розрахункова робота №1 (рр) з "Економіко-математичного моделювання"
Задача 2
На виготовлення двох видів продукції виділяється три види ресурсів. Запаси ресурсів: 273, 100 та 380 у.о., відповідно, норми їх витрат: 3 та 2 у.о. – 1 ресурсу; 1 та 1 у.о. – 2 ресурсу; 1 та 2 у.о. – 3 ресурсу відповідно на одиницю продукції кожного виду та прибутку 10 і 8 у.о. від реалізації одиниці продукції кожного виду приведені в таблиці. Знайти симплекс-методом такий план виробництва, який би забезпечував найбільший прибуток. Скласти подвійну задачу до вихідної і виписати її оптимальний план із симплекс-таблиці розв‘язку вихідної задачі.
Розв‘язання:
Відповідно до умови задачі отримаємо наступну математичну модель:
z = 10x1 + 8x2 max,
(1)
Опорний розв‘язок (2) отримаємо, наприклад, при х3 = х4 = 0;
Канонічний вид задачі (1):
z = 10x1 +8x2 max,
(2)
тоді х1 = 73; х2 = 27; х5 = 253, тобто х* (73; 27; 0; 0; 273).
Основна матриця системи обмежень (2):
має ранг r (A) = 3, бо, наприклад, .
Так як опорний розв‘язок має три додатні координати, то він є невиродженим. Базис опорного розв‘язку складають вектори .
Базисна матриця .
Будуємо обернену матрицю . Визначник
Алгебраїчні доповнення:
Обернена матриця
Перевірка:
Розкладаємо небазисні вектори по векторам базисаДля скорочення запису зробимо це у вигляді однієї матричної формули:
Запишемо симплекс-таблицю, яка відповідає даному опорному розв’язку:
-
№
Ба - зис
Сі базис
10
8
0
0
0
Сі
1
10
73
1
0
1
-2
0
2
8
27
0
1
-1
3
0
3
0
253
0
0
1
-4
1
4
946
0
0
2
4
0
Знаходимо:
Оцінки:
Усі оцінки невід’ємні (). Даний опорний розв’язок оптимальний.
при оптимальному плані Подвійна задача до (1):
Із останньої симплекс-таблиці , то базисні змінні
,тоді:
Відповідь: при
Задачі для самостійної роботи.
Розв’язати ЗЛП симплекс – методом.
1. 2.
Відповідь: Відповідь:
3. 4.
Відповідь:Відповідь:
5. 6.
Відповідь: Відповідь:
Тема: "Транспортна задача. Метод потенціалів" Задача 1
Знайти оптимальний план транспортної задачі за даною таблицею, де - матриця вартості перевезення одиниці вантажу;- запаси,- потреби вантажу (у.о.), де.
.
Розв‘язання:
Знаходимо:
Так як , то маємо відкриту транспортну задачу (ТЗ). Для перетворення її в закриту ТЗ вводимо фіктивного виробниказ об’ємом виробництваі нульовими елементами матриці вартості. Запишемо цю ТЗ у вигляді таблиці:
b а |
220 |
190 |
310 |
170 |
400 |
11 150 |
10 ө 20 |
7 60 |
9 170 |
250 |
8 |
5
|
4 ө 250 |
13 |
170 |
4 |
3 170 |
14 |
15 |
70 |
0 70 |
0 |
0 |
0 |
Базис складають вектори:
Він невироджений, бо що дорівнює кількості базисних векторів.
Для визначення оптимальності розв’язку застосуємо метод потенціалів.
Система для визначення потенціалів має вигляд:
Задаючи отримаємо розв’язок системи:
Обчислимо оцінки небазисних векторів:
Так як оцінка >0, то даний опорний розв’язок є неоптимальним. Вводимо в базис вектор. Невідомий об’єм переведень за маршрутомпозначимо. Складаємо компенсаторний ланцюг. ВизначаємоНова таблиця, яка відповідає новому опорному розв’язку, має вигляд:
b a |
220
|
190 |
310 |
170 |
400 |
11 ө 150 |
10 |
7 80 |
9 170 |
250 |
8
|
5 20 |
4 ө 230 |
13 |
170 |
4
|
3 ө 170 |
14 |
15 |
70 |
0 70 |
0 |
0 |
0 |
Звідси отримаємо:
Оцінки небазисних векторів:
У базис вводимо вектор
Нова таблиця, яка відповідає новому опорному розв’язку, має вигляд:
b a |
220
|
190 |
310 |
170 |
400 |
11
|
10 |
7 230 |
9 170 |
250 |
8
|
5 170 |
4 80 |
13 |
170 |
4 150 |
3 20 |
14 |
15 |
70 |
0 70 |
0 |
0 |
0 |
Система для потенціалів має вигляд:
Звідси:
Оцінки небазисних векторів:
Всі оцінки недодатні. Даний опорний розв’язок оптимальний. Оптимальне значення функції мети:
.
Перевіряємо нульову оцінку на оптимальність. В базис вводимо вектор (4,4). Нова таблиця, яка відповідає новому опорному розв’язку, має вигляд:
b a |
220
|
190 |
310 |
170 |
400 |
11
|
10 |
7 250 |
9 150 |
250 |
8
|
5 190 |
4 60 |
13 |
170 |
4 170 |
3
|
14 |
15 |
70 |
0 50 |
0 |
0 |
0 20 |
Відповідь: при слідуючих оптимальних планах перевезень: І план -при цьому I споживач не отримає 70 одиниць продукції;
ІІ план – при цьому I споживач не отримає 50 одиниць продукції, а ІІ - 20.