Дослідження роботи методів лінійного програмування. Методичні вказівки до лабораторної роботи з Методи синтезу та оптимізації. Робота № 531317

Перехід до торгівельного партнера Binance

Дослідження роботи методів лінійного програмування

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

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

Кафедра:

Не вказано

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

Рік:

2008

Тип роботи:

Методичні вказівки до лабораторної роботи

Предмет:

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

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національній університет "Львівська політехніка" Дослідження роботи методів лінійного програмування МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи №2 з курсу "Методи синтезу та оптимізації" для студентів базового напряму 6.08.04 "Комп'ютерні науки" ЗАТВЕРДЖЕНО на засіданні кафедри САПР Протокол № 1 від 28.08 2008 р. ЛЬВІВ 2008 Дослідження роботи методів лінійного програмування. Методичні вказівки до лабораторної роботи №2 з курсу " Методи синтезу та оптимізації " для студентів базового напряму 6.08.04 "Комп'ютерні науки" /Укл. Андрійчук М. І., Теслюк В.М. - Львів: НУ"ЛП", 2008 р. Укладачі: Андрійчук Михайло Іванович, к. ф.-м. н., доц., Теслюк Василь Миколайович, к.т.н., доц. Відповідальний за випуск: Ткаченко С.П., к.т.н., доц. Рецензенти: Каркульовський В. І., к.т.н., доц., Стех Ю.В, к.т.н., доц. 1. МЕТА РОБОТИ Вивчити основні алгоритми розв’язку задач лінійної оптимізації. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Задачі оптимізації, в яких цільова функція є лінійною функцією незалежних змінних (тобто має вигляд z = c1 x1+ c2 x2+...+ cn xn, де c1, c2,..., cn - константи, x1, x2,..., xn - змінні, n-довільне натуральне число) і умови, які визначають допустимі значення цих змінних мають вигляд лінійних рівнянь і нерівностей, відносять до задач лінійного програмування. Лінійне програмування було розвинене в зв'язку із задачами економіки, з пошуком способів оптимального рішення і з використанням обмежених ресурсів. Розвиток і ускладнення економічних процесів, обчислювальної техніки стимулює широке використання математичних методів в управлінні, сприяє зростанню ролі лінійного програмування як одного з актуальних розділів прикладної математики. Так за оцінками американських експертів біля 75% від загального числа практичних оптимізаційних задач, відносяться до задач ЛП. Біля чверті машинного часу, затраченого в останні роки на проведення наукових досліджень, було відведено рішенню задач ЛП та їх чисельних модифікацій. 2.1. Стандартна форма представлення лінійних задач оптимізації Перед застосуванням симплекс-методу необхідною умовою є запис оптимізаційних задач в стандартній (канонічній) формі. Канонічна форма запису оптимізацій них задач передбачає, що: усі змінні мають бути не від’ємними; нерівності слід перетворити в рівності; праві частини рівнянь мають бути не від’ємними. Стандартна або канонічна постановка задачі лінійного програмування наступна: знайти такі значення змінних x1, x2,..., xn, які задовольняють наступну систему рівнянь: , (1) і дають найменше значення цільової функції : z = c1*x1+ c2*x2+. .. + cn*xn. 2.2. Графічне рішення задачі ЛП Розглянемо метод графічного рішення ЗЛП на прикладі задачі технічного контролю. Задача технічного контролю. У відділі технічного контролю (ВТК) деякої фірми працюють контролери першого та другого розрядів. Норма вироблення ВТК за 8 - годинний робочий день складає не менше ніж 1800 виробів. Контролер першого розряду перевіряє 25 виробів в годину, причому, не помиляється у 98% випадків. Контролер розряду 2 перевіряє 15 виробів в годину; його точність становить 95%. Заробітна плата контролера першого розряду рівна 4 грн. в годину, а контролер другого розряду отримує 3 грн. в годину. При кожній помилці контролера фірма несе збиток в розмірі 2 грн. Фірма може використати 8 контролерів розряду і 10 контролерів другого розряду. Керіництво фірми хоче визначити оптимальний склад ВТК, при якому загальні витрати на контроль будуть мінімальні. 2.2.1. Розробка моделі. Нехай x1 і x2 означають кількість контролерів першого та другого розрядів, відповідно. Число контролерів кожного розряду, які може використати підприємство обмежене, тобто мають бути включені наступні обмеження: x1 8 (разряд 1), x210 (разряд 2). Щодня необхідно перевіряти не менше 1800 виробів. Тому, слід записати наступну нерівність: 8*25*x1+8*15*x2=200*x1+1200*x2 1800, або 5*x1+3*x245. При побудові цільової функції потрібно мати на увазі, що витрати фірми, пов'язана з контролем, включають дві складові: зарплату контролерів; збитки, викликані помилками контролерів. Витрати на одного контролера першого розряду складають: 4 грн+2*25*0,02=5 грн/ч. Витрати на одного контролера другого розряду рівні: 3 грн+2*15*0.005=4,50 грн./ч. Отже, мінімізуюча цільова функція, що виражає щоденні витрати на контроль, має наступний вигляд: z=8*(5*x1+450*x2)= 40x1+36*x2min. Отже, в кінцевому випадку, можна сформулювати наступну задачу ЛП: Мінімізувати: z=40*x1+36*x2, при обмеженнях: x18, x210, 5*x1+3*x245, x10, x20. 2.2.2. Графічний розв’язок задачі. При розв’язку цієї задачі необхідно знайти значення змінних x1 і x2, які задовольняють усім обмеженням і, які забезпечують мінімальне значення цільової функції. Як перший крок рішення оптимізаційної задачі необхідно визначити всі можливі ненегативні значення змінних x1 і x2, які задовольняють обмеженням. Для прикладу, координати точки x1=8 і x2=10 позитивні і для цієї точки виконуються всі обмеження.Така точка називається допустимим рішенням. Безліч усіх допустимих рішень називається допустимою областю. Рішення задачі ЛП складається з знаходження найкращого рішення в допустимій області. Найкраще допустиме рішення задачі ЛП називається оптимальним. У прикладі, що розглядається оптимальне рішення являє собою допустиме рішення, що мінімізує цільову функцію 40*x1+36*x2. Значення цільової функції, відповідне оптимальному рішенню, називається оптимальним значенням задачі ЛП. Для зображення допустимої області рішення слід накреслити графіки всіх обмежень. Усі допустимі рішення розміщені в першому квадранті, оскільки значения змінних невід’ємні. В силу обмеження 5*x1+3*x245 усі допустимі рішення (x1, x2) задачі розміщені з однієї сторони від прямої, яка описується рівнянням 5*x1+3*x2=45. Неохідну напівплощину можна знайти, перевіривши, чи задовільняє початок координат разглядуваному обмеженню. Пряму 5x1+3*x2=45 зручно провести, з’єднуючи пару точок (для прикладу, x1=0, x2=15 и x1=9, x2=0). Оскільки початок координат не задовільняє обмеженню, необхідна напівплощина відмічена стрілкою, направленою перпендикулярно до прямої. Аналогічним чином представлені обмеження x1 8 и x2 10. На рис.4.1 допустима область (АВС) заштрихована. Зрозуміло, що в допустимій області розміщено нескінченне число допустимих точок. Необхідно знайти допустиму точку с наименьшим значением Z. Рис. 1. Графічне рішення задачі Якщо зазделегідь зафіксувати значення цільової функції Z=40*x1+36*x2, то відповідні йому точки будуть лежати на деякій прямій. При зміні величини Z ця пряма зазнає паралельного перенесення. Розглянемо прямі, які відповають різним значенням Z, що мають з допустимою областю хоч би одну загальну точку. Початкове значення Z покладемо рівним 600. При наближенні прямої до початку координат значення Z меншає. Якщо пряма має хоч би одну загальну точку з допустимою областю АВС, її можна зміщати в напрямі початку координат. Зрозуміло, що для прямої, яка проходить через кутову точку А з координатами х1=8, х2=1.6, подальший рух неможливий. Точка А являє собою найкращу допустиму точку, яка відповідає найменшому значенню Z, рівному 377.6. Отже, х1=8, х2=1.6 - оптимальне рішення і Z=377.6 - оптимальне значення задачі лінійного програмування, яка розглядається. Таким чином, при оптимальному режимі роботи ВТК необхідно використати вісім контролерів розряду 1 і 1.6 контролерів розряду 2. Дробове значення х2=1.6 відповідає використанню одного з контролерів розряду 2 протягом неповного робочого дня. При неприпустимості неповного завантаження контролерів дробове значення звичайно округляють, отримуючи наближене оптимальне цілочисельне рішення х1=8, х2=2. 2.3. Основи симплекс-методу 2.3.1. Основні поняття та визначення. Змінні в рівнянні (1), які входять з одиничним коефіцієнтом в одне рівняння системи і з нульовими – в інші, називаються базисними (або залежними). В канонічній системі кожному рівнянню відповідає рівно одна базисна змінна. Інші змінні n-m (де n - кількість змінних, а m - кількість рівнянь) називаються небазисними або незалежними змінними. Базисним рішенням системи в канонічному вигляді називається таке рішення, яке отримане при нульових значеннях небазисних змінних. Базисне рішення називається допустимим базисним рішенням, якщо значення базисних змінних, які внього входять невід’ємні. Для отримання суміжного допустимого базисного рішення симплекс-метод перетворює одну з базисних рішень в небазисну і вводить одну із небазисних змінних в базис. Необхідно вибрати базисну і небазисну змінні так, щоб заміна однієї на іншу давала максимальний приріст цільової функції. 2.3.2. Алгоритм симплекс-методу Алгоритм симплекс-методу включає наступні процедури: Крок 0. Використовуючи лінійну модель стандартної форми, визначається початкове допустиме базисне рішення шляхом прирівнювання до нуля небазисних n-m змінних. Крок 1. З числа поточних небазисних (рівних нулю) змінних вибирається змінну, яка буде включена в новий базис і збільшення якої забезпечує поліпшення значення цільової функції. Якщо такої змінної немає, то обчислення припиняються, оскільки поточне базисне рішення оптимальне. В іншому випадку здійснюється перехід до кроку 2. Крок 2. З числа змінних поточного базису вибирається змінна, яка виводиться зі списку базисних змінних і має прийняти нульове значення (стати небазисною) при введенні до складу базисних нової змінної. Крок 3. Знаходиться нове базисне рішення, відповідне новим складам небазисних і базисних змінних. Здійснюється перехід до кроку 1. 2.3.3. Приклад застосування симплекс-методу до розв’язку лінійних задач оптимізації Пояснимо процедури симплекс-методу на прикладі рішення лінійної задачі. Цільова функція : - max. Обмеження: . Спочатку необхідно представити цільову функцію і обмеження в стандартній формі: Цільова функція : - max. Обмеження: . Як було відзначено вище, як початкове пробне рішення використовується рішення системи рівнянь, в якій дві (= 6 - 4) змінні приймаються рівними нулю. Це забезпечує единість і допустимість рішення задачі. У випадку, що розглядається очевидно, що підстановка відразу ж призводить до наступного результату: . Отримані результати досить зручно зобразити у вигляді наступної таблиці: Базисні змінні z X1 X2 X3 X4 X5 X6 Рішення z 1 -3 -2 0 0 0 0 0 X3 0 1 2 1 0 0 0 6 X3-рівняння X4 0 2 1 0 1 0 0 8 X4-рівняння X5 0 -1 1 0 0 1 0 1 X5-рівняння X6 0 0 1 0 0 0 1 2 X6-рівняння Дана таблиця інтерпретується наступним чином. Стовпчик „Базисні змінні” містить змінні пробного базису , значення яких наведені в стовпці «Рішення». При цьому мається на увазі, що небазисні змінні (не представлені в першому стовпці) рівні нулю. Значення цільової функції (z=3*0+ 2*0+ 0*6+ 0*8+ 0*1+ 0*2) рівне нулю, що і показано в останньому стовпці таблиці. Для визначення чи є отримане пробне рішення оптимальним, слід провести аналіз z – рівняння. Не важко помітити, що дві змінні , які рівні нулю, включають від’ємні коефіцієнти. Оскільки ми маємо справу з максимізацією цільової функції, то її значення може бути покращене шляхом збільшення як коефіцієнта при , так і . Однак необхідно вибирати від’ємну змінну з найбільшим значенням за абсолютною величиною в z – рівнянні (оскільки практичний досвід обчислень показує, що в цьому випадку оптимум досягається швидше). Це правило складає основу умови оптимальності вичислювального процесу симплекс-методу. Основна ідея якої полягає в наступному, якщо в задачі максимізації всі не базисні змінні в z – рівнянні мають не відємні коефіцієнти, то отримане базисне рішення є оптимальним. В іншому випадку в якості нової базисної змінної необхідно вибрати ту, яка має найбільший за абсолютною величиною відємний коефіцієнт. Застосовуючи умову оптимальності до початкової таблиці, виберемо в якості змінної, яку включаємо в список базисних (змінна ). Змінна, яка виключається має бути вибрана з сукупності базисних змінних . Процедура вибору такої змінної передбачає перевірку умови допустимості, яка вимагає, щоб змінна, яка виключається вибиралася із змінних поточного базису і першою перетворювалаль в нуль при збільшенні включаємої змінної , аж до значення, відповідного суміжній екстремальній точці. Враховуючи вище сказане, необхідно визначити відношення постійної правої частини обмеження до коефіцієнта при зміній для кожного рівняння. Вибирається та змінна, для якої дане відношення має найменше значення. Якщо коефіцієнт при має негативне або нульове, то ця базисна змінна виключається з розгляду. Цікавляче нас відношення (фіксуюче шукану точку перетину і що ідентифікує змінну, яка виключається ) можна визначити безпосередньо з симплекс-таблиці. Для цього в стовпці, відповідному змінної , що вводиться, викреслюються негативні і нульові елементи обмежень. Потім обчислюються відношення постійних, фігуруючих в правих частинах цих обмежень, до елементів стовпця, які залишилися, відповідної змінної, яку вводять в базис . Змінною, яка виключається буде та змінна поточного базису, для якої вказане вище відношення мінімальне. Початкова симплекс-таблица для нашої задачі фирмы, яку отримаємо після перевірки умови допустимості (тобто після обчислення відповідних відношень та визначення виключаємої змінної), наведена нижче. Для зручності опису вичислювальних процедур, які слід провести на наступній ітерації, введемо ряд необхідних визначень. Стовпчик симплекс-таблицы, пов’язаний зі змінною, яка в вводиться в базис, будемо називати ведучим стовпчиком. Стрічку, яка відповідає виключає мій змінній – ведучою стрічкою, а елемент, який розміщений на перетині ведучої стрічки і ведучого стовпчика – ведучим елементом. Базисні змінні z X1 X2 X3 X4 X5 X6 Рішення z 1 -3 -2 0 0 0 0 0 відношення X3 0 1 2 1 0 0 0 6 6/1 = 6 X4 0 2 1 0 1 0 0 8 8/2 = 4 X5 0 -1 1 0 0 1 0 1 X6 0 0 1 0 0 0 1 2 Після того як визначені змінні, що включається і виключається (з використанням умов оптимальності і допустимості), наступна итерація (пошук нового базисного рішення) здійснюється методом виключення змінних, або методом Гаусса - Жордана. Цей процес зміни базису включає наступні обчислювальні процедури двох типів. Тип 1 (формування ведучого рівняння). Нова ведуча стрічка = Попередня ведуча стрічка / Ведучий елемент Тип 2 (формування всіх інших рівнянь, включаючи z-рівняння). Нове рівняння = Попереднє рівняння – (Нова ведуча стрічка)*(Коефіцієнт ведучого стовпчика попереднього рівняння) Виконання процедури типу 1 приводить до того, що в новому ведучому рівнянні ведучий елемент стає різним одиниці. Внаслідок здійснення процедури типу 2 всі інші коефіцієнти, які фігурують у ведучому стовпці, стають равньвш нулю. Це еквівалентно отриманню базисного рішення шляхом виключення змінної, що вводиться з усіх рівнянь, окрім ведучого. Застосовуючи до початкової таблиці процедуру 1, ми ділимо X4-рівняння на ведучий елемент, рівний 2. Так як у стовпці базисних змінних займає місце змінної X4, вказана процедура приводить до наступних змін початкової симплекс-таблиці. Базисні змінні z X1 X2 X3 X4 X5 X6 Рішення z X3 X1 0 1 1/2 0 1/2 0 0 8/2=4 X5 X6 Відмітимо, що в стовпці «Рішення» тепер фігурує нове значення змінної X1(=4), яке дорівнює мінімальній величині відношень, що аналізуються при перевірці умови допустимості. Щоб скласти нову симплекс-таблицю, виконаємо необхідні обчислювальні процедури типу 2. 1. z-рівняння Попереднє z-рівняння: ( 1 -3 -2 0 0 0 0 0 ) -(-3)*Нова ведуча стрічка: ( 0 3 3/2 0 3/2 0 0 12 ) = Нове z-рівняння: ( 1 0 -1/2 0 3/2 0 0 12 ) 2. X3-рівняння Попереднє X3-рівняння: ( 0 1 2 1 0 0 0 6 ) -(1)*Нова ведуча стрічка: ( 0 -1 -1/2 0 -1/2 0 0 -4 ) = Нове X3-рівняння: ( 0 0 3/2 1 -1/2 0 0 2 ) 3. X5-рівняння Попереднє X5-рівняння: ( 0 -1 1 0 0 1 0 1 ) -(-1)*Нова ведуча стрічка: ( 0 1 1/2 0 1/2 0 0 4 ) = Нове X5-рівняння: ( 0 0 3/2 0 1/2 1 0 5 ) 4. X6-рівняння. Нове X6-рівняння буде таким же, як і попереднє, оскільки відповідний коефіцієнт ведучого стовпця рівний нулю. Нова симплекс-таблиця, отримана за допомогою розглянутих операцій, має наступний вигляд: Базисні змінні z X1 X2 X3 X4 X5 X6 Рішення z 1 0 -1/2 0 3/2 0 0 12 X3 0 0 3/2 1 -1/2 0 0 2 2/(3/2)=4/3 X1 0 1 1/2 0 1/2 0 0 4 4/(1/2)=8 X5 0 0 1/2 0 1/2 1 0 5 5/(3/2)=10/3 X6 0 0 1 0 0 0 1 2 2/1=2 Значення z зросло з 0 до 12. Це збільшення зумовлене тим, що приріст X1 на одиницю забезпечує збільшення z на 3 одиниці; таким чином, приріст цільової функції z складає: 3*4 = 12. Помітимо, що нова симплекс-таблиця володіє такими ж характеристиками, як і попередня: тільки небазисні змінні X1 і X4 рівні нулю, а значення базисних змінних, як і раніше, представлені в стовпці «Рішенням. Це в точності відповідає результатам, що отримуються при використанні методу Гаусса-Жордана. З останньої таблиці слідує, що на черговій итерації відповідно до умови оптимальності змінна, яку вводимо потрібно вибрати X2, оскільки коефіцієнт при цій змінній в z-рівнянні рівний -1.2. Виходячи з умови допустимості, визначаємо, що змінної, що виключається буде X2. Відношення, яке фігурує в правій частини таблиці, показують, що в новому базисному рішенні значення змінної. X2, що включається буде дорівнювати 4/3 (= мінімальному відношенню). Це призводить до збільшення цільової функції на (4/3)*(1/2)=2/3. До отримання нової симплекс-таблиці, на відповідній новій итерації, приводять наступні обчислювальні операції методу Гаусса Жордана. 1) Нове ведуче X3-рівняння = Попереднє X3-рівняння / (3/2). 2) Нове z-рівняння = Попереднє z-уразнение - (-1/2) * Нове ведуче рівняння. 3) Нове. X3- Рівняння = Попереднє X3- Рівняння - (1/2) * Нове ведуче рівняння. 4) Нове X5-рівняння = Попереднє X5-Рівняння -(3/2) * Нове ведуче рівняння. 5) Нове X6-рівняння = Попереднє X6-рівняння - (1) * Нове ведуче рівняння. Внаслідок вказаних перетворень отримаємо наступну симплекс-таблицю. Базисні змінні z X1 X2 X3 X4 X5 X6 Рішення z 1 0 0 1/3 4/3 0 0 12 (2/3) X3 0 0 1 2/3 -1/3 0 0 4/3 X1 0 1 0 -1/3 2/3 0 0 10/3 X5 0 0 0 -1 1 1 0 3 X6 0 0 0 -2/3 1/3 0 1 2/3 У новому базисному рішенні та . Значення z збільшилося з 12 (попередня симплекс-таблиця) до (остання симплекс-таблиця). Цей результуючий приріст цільової функції зумовлений збільшенням від 0 до 4/3, оскільки з z - стрічки попередньої симплекс-таблиці слідує, що зростання даної змінної на одиницю відповідає збільшення цільової функції на 1/2. Остання симплекс-таблиця відповідає оптимальному рішенню задачі, оскільки в 2-рівнянні жодна з небазисних змінних не фігурує з негативним коефіцієнтом. Після отриманням цієї результуючої таблиці і завершуються обчислювальні процедури симплекс-методу. У розглянутому вище прикладі алгоритм симплекс-методу використаний при рішенні задачі, в якій цільова функція підлягала максимізації. У разі мінімізації цільової функції в цьому алгоритмі необхідно змінити тільки умову оптимальності: в якості нової базисної змінної потрібно вибирати ту змінну, яка в z – рівнянні має найбільший додатній коефіцієнт. Умови допустимості в двох випадках (максимізації та мінімізації) однакові. Доцільно дати кінцеве формулювання обох умов, які використовуються в симплекс-методі. У м о в а о п и м а л ь н о с т і. Змінною, яку вводять в базис у задачі максимізації (мінімізації) є та небазисна змінна, яка має в z – рівнянні найбільший від’ємний (додатній) коефіцієнт. У випадку рівності таких коефіцієнтів для декількох небазисних змінних вибір проводиться випадково. Якщо усі коефіцієнти при небазисних змінних в z – рівнянні не від’ємні (не додатні), то отримане рішення – оптимальне. У м о в а д о п у с т и м о с т і. В задачах максимізації і мінімізації в якості виключаємої змінної вибирається та базисна змінна, для якої відношення постійної в правій частині відповідного обмеження до (додатнього) коефіцієнта ведучого стовпчика мінімальне. У випадку рівності цього відношення для декількох базисних змінних вибір проводиться випадково. 3. КОНТРОЛЬНІ ЗАПИТАННЯ 4. ЛАБОРАТОРНЕ ЗАВДАННЯ 4.1. Набрати, скомпілювати та запустити програму задану викладачем. 4.2. Пояснити дії, які виконує програма. 4.3. Перевірити достовірність одержаного результату. 5. ЗМІСТ ЗВІТУ 5.1. Титульний лист. 5.2. Мета роботи, теоретичні відомості. 5.3. Лабораторне завдання. 5.4. Програма. 5.5. Висновок. 6. ЛІТЕРАТУРА Реклейтис Г., Рейвиндрон А., Рзгсдел К. Оптимизация в технике: В 2-х кн. Кн. 1. Пер. с англ. - М.: Мир, 1986. - 349 с. Шуп Т. Решение инженерных задач на ЭВМ. Практическое руководство. Пер. с англ. – М.: Мир, 1982. – 238 с. Реклейтис Г., Рейвиндрон А., Рзгсдел К. Оптимизация в технике: В 2-х кн. Кн.2. Пер. с англ. - М.: Мир, 1986. - 320 с. О. Коссак, О. Тумашова, О. Коссак. Методи наближених обчислень. Навчальний посібник. НУ «Львівська політехніка», 2003. - 168 с.

Методичні вказівки до лабораторної роботи Методи синтезу та оптимізації

horuktaras

17.07.2020 15:07-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись