Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Симплекс метод
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКНІ
Факультет:
Комп’ютерні науки
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2014
Тип роботи:
Лабораторна робота
Предмет:
Методи синтезу та оптимізації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
/
Звіт
до лабораторної роботи № 2
з курсу: «Методи синтезу та оптимізації»
на тему:
«Дослідження роботи методів лінійного програмування»
Мета роботи: вивчити основні алгоритми розв’язку задач лінійної оптимізації: розв'язати дану задачу ЛП використовуючи симплекс метод.
1.Короткі теоретичні відомості:
Задачі оптимізації, в яких цільова функція є лінійною функцією незалежних змінних (тобто має вигляд z = c1 x1+ c2 x2+...+ cn xn, де c1, c2,..., cn - константи, x1, x2,..., xn - змінні, n-довільне натуральне число) і умови, які визначають допустимі значення цих змінних мають вигляд лінійних рівнянь і нерівностей, відносять до задач лінійного програмування.
Лінійне програмування було розвинене в зв'язку із задачами економіки, з пошуком способів оптимального рішення і з використанням обмежених ресурсів. Розвиток і ускладнення економічних процесів, обчислювальної техніки стимулює широке використання математичних методів в управлінні, сприяє зростанню ролі лінійного програмування як одного з актуальних розділів прикладної математики.
Перед застосуванням симплекс-методу необхідною умовою є запис оптимізаційних задач в стандартній (канонічній) формі. Канонічна форма запису оптимізацій них задач передбачає, що:
усі змінні мають бути не від’ємними;
нерівності слід перетворити в рівності;
праві частини рівнянь мають бути не від’ємними.
Алгоритм симплекс-методу включає наступні процедури:
Крок 0. Використовуючи лінійну модель стандартної форми, визначається початкове допустиме базисне рішення шляхом прирівнювання до нуля небазисних n-m змінних.
Крок 1. З числа поточних небазисних (рівних нулю) змінних вибирається змінну, яка буде включена в новий базис і збільшення якої забезпечує поліпшення значення цільової функції. Якщо такої змінної немає, то обчислення припиняються, оскільки поточне базисне рішення оптимальне. В іншому випадку здійснюється перехід до кроку 2.
Крок 2. З числа змінних поточного базису вибирається змінна, яка виводиться зі списку базисних змінних і має прийняти нульове значення (стати небазисною) при введенні до складу базисних нової змінної.
Крок 3. Знаходиться нове базисне рішення, відповідне новим складам небазисних і базисних змінних. Здійснюється перехід до кроку 1.
2.Індивідуальне завдання:
13. Продукція може виготовлятися на будь-якому з трьох видів обладнання А, В, С. Трудоємкості (нормо-год.) і собівартість (у.о.) виробництва центнера продукції на цьому обладнанні виражаються відповідно числами 10, 9, 12 і 20, 17, 22. Скільки центнерів продукції потрібно виготовляти на кожному з видів обладнання, щоб сумарна собівартість продукції була б мінімальною, при умові, що сумарна трудомісткість не має перевищувати 660 нормо-год, а загальна кількість продукції не має бути менше 70 ц.?
3.Результат виконання:
F(X) = 20x1 + 17x2 + 22x3
x1 + x2 + x3≥70
10x1 + 9x2 + 12x3≤660
Запишемо систему в канонічному вигляді, ввівши додаткові змінні x4 , x5 , x6 :
1x1 + 1x2 + 1x3-1x4 + 0x5 + 1x6 = 70
10x1 + 9x2 + 12x3 + 0x4 + 1x5 + 0x6 = 660
Функцію мети запишемо так:
F(X) = 20x1+17x2+22x3+Mx6 → min
З рівнянь отримуємо:
x6 = 70-x1-x2-x3+x4 і
F(X) = 20x1 + 17x2 + 22x3 + M(70-x1-x2-x3+x4) → min
F(X) = (20-M)x1+(17-M)x2+(22-M)x3+(M)x4+(70M) → min
Отримана матриця коефіцієнтів:
Розв’яжемо систему рівнянь відносно базових змінних: x5, x6 ; взявши вільні змінні = 0 , отримаємо :
X1 = (0,0,0,0,660,70)
Базис
B
x1
x2
x3
x4
x5
x6
x6
70
1
1
1
-1
0
1
x5
660
10
9
12
0
1
0
F(X0)
70M
-20+M
-17+M
-22+M
-M
0
0
Оскільки базисне рішення негативне, переходимо до основного алгоритму:
Ітерація 1.
1. Перевірка на критерій оптимальності:
Даний опорний план неоптимальний, оскільки в індесному рядку знаходяться позитивні коефіцієнти.
2. Визначення нової базисної змінної
Новою базисною змінною виберемо стовпець з x2 , оскільки це найбільший елемент.
3. Визначення нової вільної змінної:
Вираховуємо значення Di=bi / ai2 , і виберемо мінімум:
min (70 : 1 , 660 : 9 ) = 70
Звідси 1 рядок стає ведучим. Ведучий елемент = 1.
Базис
B
x1
x2
x3
x4
x5
x6
min
x6
70
1
1
1
-1
0
1
70
x5
660
10
9
12
0
1
0
731/3
F(X1)
70M
-20+M
-17+M
-22+M
-M
0
0
0
4. Перерахунок симплекс-таблиці:
Рядок, що відповідає змінній x2 в плані 1, отриманий дленням всіх елементів рядка x6 плану 0 на ведучий елемент ВЕ=1. На місці ведучого едементу в плані 1 отримуємо 1. В інших клітинках стовпця x2 пишемо нулі.Решта елементів визначаються за правилом прямокутника. Новий елемент:
НЕ = СЕ - (А*В)/ВЕ
СЕ – старий елемент, ВЕ – ведучий елемент, А і В – елементи старого плану.
Отримуємо:
B
x 1
x 2
x 3
x 4
x 5
x 6
70 : 1
1 : 1
1 : 1
1 : 1
-1 : 1
0 : 1
1 : 1
660-(70 • 9):1
10-(1 • 9):1
9-(1 • 9):1
12-(1 • 9):1
0-(-1 • 9):1
1-(0 • 9):1
0-(1 • 9):1
(0)-(70 • (-17+M)):1
(-20+M)-(1 • (-17+M)):1
(-17+M)-(1 • (-17+M)):1
(-22+M)-(1 • (-17+M)):1
(-M)-(-1 • (-17+M)):1
(0)-(0 • (-17+M)):1
(0)-(1 • (-17+M)):1
Отримуємо нову симплекс-таблицю:
Базис
B
x1
x2
x3
x4
x5
x6
x2
70
1
1
1
-1
0
1
x5
30
1
0
3
9
1
-9
F(X1)
1190
-3
0
-5
-17
0
17-M
Ітерація 2.
1. Перевірка критерію оптимальності.
Серед значень індексного рядка нема позитивних значень, тому дана таблиця визначає оптимальний план:
Базис
B
x1
x2
x3
x4
x5
x6
x2
70
1
1
1
-1
0
1
x5
30
1
0
3
9
1
-9
F(X2)
1190
-3
0
-5
-17
0
17-M
Оскільки штучні змінні рівні нулю, то дане рішення є допустимим.
Отриманий оптимальний план:
x2 = 70
F(X) = 17•70 = 1190
Висновок: на цій лабораторній роботі я ознайомився з основними алгоритмами розв’язку задач лінійної оптимізації, розв’язав задачу ЛП симплекс методом.
14.05.2016 10:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора