Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2010
Тип роботи:
Розрахункова робота
Предмет:
Методи синтезу та оптимізації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет «Львівська політехніка»
Кафедра САПР
Розрахункова робота
з курсу:
«Методи синтезу та оптимізації»
Завдання 1.
Оптимізація виробничих планів
Формалізувати задачу, як задачу лінійного програмування (ЛП);
Записати задачу ЛП в канонічній формі;
Розв'язати дану задачу ЛП використовуючи симплекс-метод.
Їдальня підприємства має 25 кг муки, 130 шт. яєць, 16 кг маргарину, 7 кг цукрового піску і 14 кг сметани. Витрата цих продуктів на один кондитерський виріб кожного виду вказана в таблиці (в кілограмах на 1 шт.).
Вид виробу
Мука
Яйця
Маргарин
Цукровий пісок
Сметана
Бісквіт
0,2
5
0
0,2
0
Пісочний торт
0,4
0
0,6
0,10
0,5
Кекс
1/3
25/3
1/3
1/3
0
Скільки кондитерських виробів кожного виду необхідно спекти, щоб сумарна їх кількість була максимальною, а весь маргарин витрачений?
ВИКОНАННЯ РОБОТИ
Ресурси (продукти)
X1
0,2
5
0
0,2
0
X2
0,4
0
0,6
0,1
0,5
X3
0,33
8,33
0,33
0,33
0
Приймемо - кількість бісквітів, - кількість пісочних тортів та - кількість кексів.
Цільова функція - max;
;
;
;
;
.
ЗАПИС ЗАДАЧІ ЛП В КАНОНІЧНІЙ ФОРМІ
Запишемо задачу у стандартній (канонічній) формі задач лінійного програмування (ЛП).
- max.
Оскільки є чотири обмеження то введемо чотири базові змінні: , , , і запишемо обмеження у нормальній формі:
Перше обмеження:
В кінцевому вигляді:
СИМПЛЕКС-МЕТОД
Запишемо початкову симплекс-таблицю.
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
1
-1
-1
-1
0
0
0
0
0
X4
0
0,2
0,4
0,33
1
0
0
0
25
- рівняння
X5
0
5
0
8,33
0
1
0
0
130
- рівняння
X6
0
0,2
0,1
0,33
0
0
1
0
7
- рівняння
X7
0
0
0,5
0
0
0
0
1
14
- рівняння
Ми можемо побачити, що в нас всі три не базові змінні мають однаковий коефіцієнт -1, тому ведучим стовпчиком буде любий, наприклад стовпчик, якому відповідає не базова змінна .
Визначаємо відношення величин стовпчика «Р» до коефіцієнтів стовпчика :
- рівняння: 25/0,2=125;
- рівняння: 130/5=26;
- рівняння: 7/0,2=35;
Отже ведучим буде рядок, який відповідає - рівняння.
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
1
-1
-1
-1
0
0
0
0
0
X4
0
0,2
0,4
0,33
1
0
0
0
25
125
X5
0
5
0
8,33
0
1
0
0
130
26
X6
0
0,2
0,1
0,33
0
0
1
0
7
35
X7
0
0
0,5
0
0
0
0
1
14
Після того як визначені змінні, що включається і виключається (з використанням умов оптимальності і допустимості), наступна ітерація (пошук нового базисного рішення) здійснюється методом виключення змінних, або методом Гаусса - Жордана. Цей процес зміни базису включає наступні обчислювальні процедури двох типів.
Тип 1 (формування ведучого рівняння).
Нова ведуча стрічка = Попередня ведуча стрічка / Ведучий елемент
Тип 2 (формування всіх інших рівнянь, включаючи z-рівняння).
Нове рівняння = Попереднє рівняння – (Нова ведуча стрічка)*(Коефіцієнт ведучого стовпчика попереднього рівняння)
Застосовуючи до початкової таблиці процедуру 1, ми ділимо - рівняння на ведучий елемент, рівний 5. Так як у стовпці базисних змінних займає місце змінної , вказана процедура приводить до наступних змін початкової симплекс-таблиці.
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
X4
X1
0
1
0
1,666
0
0,2
0
0
26
X6
X7
Відмітимо, що в стовпці «Р» тепер фігурує нове значення змінної (=26), яке дорівнює мінімальній величині відношень, що аналізуються при перевірці умови допустимості.
Щоб скласти нову симплекс-таблицю, виконаємо необхідні обчислювальні процедури типу 2.
1. Z - рівняння
Попереднє Z-рівняння:
( 1
-1
-1
-1
0
0
0
0
0 )
-(-1)*Нова ведуча стрічка:
( 0
1
0
1,666
0
0,2
0
0
26)
= Нове z-рівняння:
( 1
0
-1
0,666
0
0,2
0
0
26 )
2. X4-рівняння
Попереднє X4-рівняння:
( 0
0,2
0,4
0,33
1
0
0
0
25 )
-(0,2)*Нова ведуча стрічка:
( 0
-0,2
0
0,3332
0
-0,04
0
0
-5,2 )
= Нове X4-рівняння:
( 0
0
0,4
0,6632
1
-0,04
0
0
22,5)
3. X6-рівняння
Попереднє X6-рівняння:
( 0
0,2
0,1
0,33
0
0
1
0
7 )
-(0,2)*Нова ведуча стрічка:
( 0
-0,2
0
0,3332
0
-0,04
0
0
-5,2 )
= Нове X6-рівняння:
( 0
0
0,1
0,6632
0
-0,04
1
0
1,8 )
4. X7-рівняння. Нове X7-рівняння буде таким же, як і попереднє, оскільки відповідний коефіцієнт ведучого стовпця рівний нулю.
Нова симплекс-таблиця, отримана за допомогою розглянутих операцій, має наступний вигляд:
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
1
0
-1
0,666
0
0,2
0
0
26
X4
0
0
0,4
0,6632
1
-0,04
0
0
22,5
- рівняння
X1
0
1
0
1,666
0
0,2
0
0
26
- рівняння
X6
0
0
0,1
0,6632
0
-0,04
1
0
1,8
- рівняння
X7
0
0
0,5
0
0
0
0
1
14
- рівняння
Значення Z зросло з 0 до 26.
Ми можемо побачити, що в нас одна не базова змінна має коефіцієнт -1, тому ведучим стовпчиком буде стовпчик, якому відповідає не базова змінна .
Визначаємо відношення величин стовпчика «Р» до коефіцієнтів стовпчика :
- рівняння: 22,5/0,4=56,25;
- рівняння: 1,8/0,1=35;
- рівняння: 14/0,5=28;
Отже ведучим буде рядок, який відповідає - рівняння.
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
1
0
-1
0,666
0
0,2
0
0
26
X4
0
0
0,4
0,6632
1
-0,04
0
0
22,5
56,25
X1
0
1
0
1,666
0
0,2
0
0
26
X6
0
0
0,1
0,6632
0
-0,04
1
0
1,8
18
X7
0
0
0,5
0
0
0
0
1
14
28
Після того як визначені змінні, що включається і виключається (з використанням умов оптимальності і допустимості), наступна ітерація (пошук нового базисного рішення) здійснюється методом виключення змінних, або методом Гаусса - Жордана. Цей процес зміни базису включає наступні обчислювальні процедури двох типів.
Застосовуючи до початкової таблиці процедуру 1, ми ділимо - рівняння на ведучий елемент, рівний 0,1. Так як у стовпці базисних змінних займає місце змінної , вказана процедура приводить до наступних змін початкової симплекс-таблиці.
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
X4
X1
X2
0
0
1
6,632
0
-0,4
10
0
18
X7
Відмітимо, що в стовпці «Р» тепер фігурує нове значення змінної (=18), яке дорівнює мінімальній величині відношень, що аналізуються при перевірці умови допустимості.
Щоб скласти нову симплекс-таблицю, виконаємо необхідні обчислювальні процедури типу 2.
1. Z - рівняння
Попереднє Z-рівняння:
( 1
0
-1
0,666
0
0,2
0
0
26 )
-(-1)*Нова ведуча стрічка:
( 0
0
1
6,632
0
-0,4
10
0
18)
= Нове z-рівняння:
( 1
0
0
7,298
0
-0,2
10
0
44)
2. X4-рівняння
Попереднє X4-рівняння:
( 0
0
0,4
0,6632
1
-0,04
0
0
22,5 )
-(0,4)*Нова ведуча стрічка:
( 0
0
-0,4
2,6528
0
0,16
-4
0
-7,2)
= Нове X4-рівняння:
( 0
0
0
3,316
1
0,12
-4
0
15,3)
3. X7-рівняння
Попереднє X71-рівняння:
( 0
0
0,5
0
0
0
0
1
14 )
-(0,5)*Нова ведуча стрічка:
( 0
0
-0,5
-3,316
0
0,2
-5
0
-9)
= Нове X7-рівняння:
( 0
0
0
-3,316
0
0,2
-5
1
5 )
4. X1-рівняння. Нове X1-рівняння буде таким же, як і попереднє, оскільки відповідний коефіцієнт ведучого стовпця рівний нулю.
Нова симплекс-таблиця, отримана за допомогою розглянутих операцій, має наступний вигляд:
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
1
0
0
7,298
0
-0,2
10
0
44
X4
0
0
0
3,316
1
0,12
-4
0
15,3
- рівняння
X1
0
1
0
1,666
0
0,2
0
0
26
- рівняння
X2
0
0
1
6,632
0
-0,4
10
0
18
- рівняння
X7
0
0
0
-3,316
0
0,2
-5
1
5
- рівняння
Значення Z зросло з 26 до 44
Остання симплекс-таблиця відповідає оптимальному рішенню задачі, оскільки в 2-рівнянні жодна з небазисних змінних не фігурує з негативним коефіцієнтом. Після отриманням цієї результуючої таблиці і завершуються обчислювальні процедури симплекс-методу.
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора