Симплекс метод. Лабораторна робота з Методи синтезу та оптимізації. Робота № 528397

Симплекс метод

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

ІКНІ

Факультет:

Комп’ютерні науки

Кафедра:

Кафедра САПР

Інформація про роботу

Рік:

2016

Тип роботи:

Лабораторна робота

Предмет:

Методи синтезу та оптимізації

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» / Звіт до лабораторної роботи № 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:32

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись