Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2005
Тип роботи:
Посібник
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Придніпровська державна академія будівництва
та архітектури
МЕТОДИЧНИЙ ПОСІБНИК
до виконання семестрового завдання з дисципліни „Основи системного аналізу” для студентів фаху 6.092501.
„Прийняття рішень з використанням графічного способу розв’язання задачі лінійного програмування”.
М. Дніпропетровськ
2005 р.
УДК 389.14
Методичні вказівки до до виконання семестрового завдання з дисципліни „Основи системного аналізу” для студентів фаху 6.092501.Укл.: Бодня В. С., - м. Дніпропетровськ: ПДАБА, 2005 р. Укр. мовою.
Методичні вказівки призначені для надання допомоги студентам при виконанні семестрового завдання з дисципліни „Основи системного аналізу” і освоєння задачі прийняття рішення з використанням графічного способу розв’язання задач лінійного програмування.
Укладач: Бодня В. С., к. т. н., доцент
Відповідальний за випуск: Еріванцев І. М., д. т. н., професор
Рецензент: Мещеряков Л. І., к. т. н., доцент – викладач
кафедри Гірничої національної академії
Затверджено на засіданні кафеди автоматики та електротехніки
Протокол № від „ ” 2005 р
Затверджено на засіданні
методичної Ради академії
Протокол №____) від „___” 2005р
ЗМІСТ
Прийняття рішень з використанням графічного способу розв’язання задачі лінійного програмування.
Мета роботи: вивчити методику прийняття рішення з використан-ням графічного способу розв’язання задач ліній-ного програмування.
1. Прийняття рішень як вибір з множини альтернатив.
Системні дослідження, або системний аналіз спираються на системність будь-якої цілеспрямованої діяльності. Щоб здійснювати цю діяльність, необхідно побудувати певну систему моделей, за допомогою якої можливо узагальнювати, передавати та вдосконалювати досвід. Ці моделі можуть бути як добре формалізованими (з широким застосуванням математичних методів), так і неформальними, емпіричними, евристичними.
Досягнення певної цілі пов(язане з прийняттям рішення, як це зробити. Головною операцією в процесі прийняття рішення є вибір. Саме він є акцією, що надає діяльності цілеспрямованість, підпорядковуючи всю діяльність певній меті або ж деякій сукупності цілей.
Вибір здійснюється за умов, коли можливі різні варіанти дій, або, за іншою термінологією, альтернативи, що можуть приводити до різних наслідків, а здійснити можна лише одну з альтернатив, причому досить часто повернутися до ситуації, що була попереду, вже неможливо.
Здатність, сприймаючи всю складність ситуації, зробити вибір, прийняти певне рішення – одна з найцінніших якостей, притаманна людям у різній мірі. Великі полководці, видатні політики, геніальні вчені та інженери, талановиті адміністратори та управлінці відрізнялись від своїх колег або конкурентів насамперед вмінням приймати кращі рішення, робити кращий вибір.
Моделювання процесів прийняття рішень зображує типову картину, властиву моделюванню взагалі: повна формалізація, пошук найкращого (оптимального) рішення можливі лише для добре вивчених або добре структурованих задач, а для розв(язання слабко структурованих чи не досить вивчених задач повністю формальних алгоритмів не існує (звичайно, якщо не брати до уваги тривіального, але далеко не завжди слушного алгоритму перебирання варіантів, тобто так званого методу спроб та похибок). Звичайно, досвідчені, талановиті фахівці, спираючись на знання, досвід, інтуїцію, досить часто можуть робити добрий вибір, який більш-менш задовольняє практичні потреби.
Сучасна тенденція вибору полягає у поєднанні здатності людини розв’язувати складні, неформалізовані задачі з можливостями різних формальних методів та комп’ютерного моделювання.
Взагалі прийняття рішення є дією (операцією) над множиною альтернатив, що приводять до більш вузької підмножини обраних альтернатив. Інколи ця підмножина складається з однієї альтернативи.
Множину альтернатив можна звузити, якщо є спосіб порівняння альтернатив між собою та визначення найбільш переважних з них, тобто є критерій переваги.
Отже, для того, щоб прийняти рішення, здійснити вибір, потрібно: згенерувати множину альтернатив та мати визначеними цілі. Ситуації та варіанти вибору такі: 1) множина альтернатив може бути скінченою, зліченною або ж континуальною; 2) оцінка альтернативи може відбуватися за одним критерієм (однокритеріальний вибір) або за певною сім’єю критеріїв (багатокритеріальний вибір), причому окремі критерії можуть мати кількісний характер; 3) режим вибору може бути одноразовим (однократним) або ж багаторазовим, повторним, що дозволяє навчатися через досвід; 4) умови вибору, отже, його наслідки можуть бути точно відомі (вибір за умов визначеності); мати імовірнісний характер, коли відомі ймовірності можливих подій після вибору (вибір за умов ризику, або за умов стохастичного ризику); мати невизначений характер, що не дозволяє введення ймовірностей (вибір за умов невизначеності); 5) відповідальність за вибір може бути однобічною (індивідуальний вибір), або ж багатобічною(груповий або колективний вибір); 6) ступінь узгодженості цілей та умов багатобічного вибору може змінюватись у широких межах: від повної збіжності інтересів сторін (кооперативний вибір) до їх прямої протилежності (в разі конфлікту).
Різні сполучення варіантів та ситуацій зумовлюють велику різноманітність задач вибору.
Треба зауважити, що формальних методів вибору настільки багато, що орієнтуватися в них дуже важко навіть найдосвідченішим фахівцям. Кожний розділ сучасної математичної теорії прийняття рішень має свою систему основних понять та специфічних методів, пов’язаних з певним класом задач вибору. Таким чином утворюється досить велика різноманітність мов загальної формальної теорії прийняття рішень.
Методами розв(язання подібних задач займається і спеціальна математична дисципліна - лінійне програмування. Важливими задачами звичайної оптимізації є різноманітні задачі більш загальної дисципліни - математичного програмування та теорії оптимального управління.
Короткі теоретичні відомості.
Існують різні класи економічних оптимізаційних задач: задачі планування виробництва, складання сумішей (шихти, раціону, дієти), розкрій матеріалів, транспортні задачі й ін. У залежності від змісту економічної задачі складається її економіко-математична модель.
В усіх цих оптимізаційних задачах потрібне досягнення екстремального (мінімального або максимального) значення цільової функції при виконанні умов, зв'язаних з балансом виробництва і споживання (або забезпечення перспективного рівня виробництва), однозначним вибором варіантів з безлічі заданих, наявністю технологічних і транспортних умов. Ці умови дозволяють сформулювати єдину модель галузевої оптимізації, що охоплює всі елементи відомих у даний час моделей галузевої оптимізації.
Оптимальні динамічні моделі перспективного планування (моделі лінійного програмування), збалансовані на кожний рік планованого періоду, що враховують реалізацію досягнень науково-технічного прогресу і трудові ресурси, передбачають як функціонування, так і оптимальний розвиток економіки. Для дослідження лінійних динамічних моделей можуть успішно застосовуватися методи лінійного програмування.
У моделях лінійного програмування завдання полягає в тім, щоб знайти ненегативне рішення системи лінійних рівнянь або нерівностей, що мінімізує або максимізує лінійну форму. Ця оптимізація лінійної форми при лінійних обмеженнях називається основною математичною задачею лінійного програмування.
Основну математичну задачу лінійного програмування можна записати (у скороченому виді) у такий спосіб:
Знайти хjj=1,2,…,n)при обмеження типу
які мінімізують (або максимізують) лінійну форму
Якщо обмеження дані у виді нерівностей, то включення в ліву частину нерівності додаткової перемінної дає можливість перетворити кожна нерівність у рівняння. Будемо називати стандартною формою основної математичної задачі лінійного програмування задачу перебування рішення системи лінійних рівнянь у ненегативних числах, що мінімізують лінійну форму. У випадку bi<0 обидві частини рівняння збільшуються на –1.
Стандартну форму задачі математично виразимо так:
При цих умовах
Лінійна форма z називається також лінійною або цільовою функцією. Тут z – перемінна, котра мінімізується.
Будь-яка сукупність xj>=0, що задовольняє умовам (1) і (2), називається припустимим рішенням. Припустиме рішення, яке мінімізує лінійну форму z, називається оптимальним рішенням.
3. Тема 1. Сутність лінійного програмування.
Мета вивчення теми: одержати уяву про задачі лінійного програмування (математична модель, приклади).
Лінійне програмування - це напрямок математичного програмування, що вивчає методи рішення екстремальних задач, які характеризуються лінійною залежністю між перемінними і лінійним критерієм. Необхідною умовою постановки задачі лінійного програмування є обмеження на наявність ресурсів, величину попиту, виробничу потужність підприємства й інших виробничих факторів.
Математична модель будь-якої задачі лінійного програмування містить у собі:
- максимум або мінімум цільової функції (критерій оптимальності);
- систему обмежень у формі лінійних рівнянь і нерівностей;
- вимогу ненегативності перемінних.
Приклад № 1
Фірма виготовляє дві моделі А и В збірних книжкових полиць. Їхнє виробництво обмежене наявністю сировини (високоякісних дошок) і часом машинної обробки. Для кожного виробу моделі А потрібно 3 м2 дошок, а для моделі В - 4 м2. Фірма може одержувати від своїх постачальників до 1700 м2 дошок у тиждень. Для кожного виробу моделі А потрібно 12 хв. машинного часу, а для виробу моделі В - 30 хв. У тиждень можна використовувати 160 годин машинного часу. Скільки виробів кожної моделі варто випускати фірмі в тиждень, якщо кожен виріб моделі А приносить 2 дол. прибутку, а кожен виріб моделі В - 4 дол. прибутку?
Побудова математичної моделі.
Нехай x1 - кількість випущених за тиждень полиць моделі А, а x2 - кількість випущених полиць моделі В. Тоді:
3x1 - кількість м2 дошок необхідних на тиждень для виготовлення полиць моделі А;
4x2 – кількість м2 дошок необхідних на тиждень для виготовлення полиць моделі В;
3x1 + 4x2 – кількість м2 дошок необхідних на тиждень для виготовлення книжкових полиць двох моделей, а за умовою задачі це число не повинне перевищувати 1700 м2, отже, одержуємо перше обмеження:
3x1+ 4x2<=1700 (1)
Знайдемо обмеження на використання машинного часу (де 12 хв. складають 0,2 години, а 30 хв. - 0,5 години), у такий спосіб:
0,2x1 - кількість часу, необхідного на тиждень для обробки полиць моделі А;
0,5x2 - кількість часу, необхідного на тиждень для обробки полиць моделі В;
0,2x1 + 0,5x2 - кількість часу, необхідного на тиждень для обробки двох моделей, а за умовою задачі це число не повинне перевищувати 160 годин, отже, одержуємо друге обмеження:
0,2x1 + 0,5x2<=160 або 2x1 + 5x2<=1600 (2)
Крім того, оскільки x1 і x2 виражають щотижневий обсяг виробів, що випускаються, то вони не можуть бути негативними, тобто
x1>=0, x2>=0 (3)
Наше завдання полягає в тім, щоб знайти такі значення x1 і x2, при яких щотижневий прибуток буде максимальним. Складемо вирази для щотижневого прибутку:
2x1 - щотижневий прибуток, одержуваний від продажу полиць моделі А по 2$ за одиницю;
4x2 - щотижневий прибуток, одержуваний від продажу полиць моделі В по 4$ за одиницю
F=2x1 + 4x2 - щотижневий прибуток, що повинний бути максимальної. Таким чином, маємо наступну математичну модель для даної задачі.
F=2x1 + 4x2->max
Отримана модель є задачею лінійного програмування. Функція F - це цільова функція, вона є лінійною функцією своїх перемінних (x1 і x2). Обмеження на ці перемінні (1) і (2) теж є лінійними. Виконано умову ненегативності для перемінних x1 і x2.
Необхідно знайти значення перемінних x1 і x2, при яких дана функція F приймає максимальне значення, при дотриманні обмежень, що накладаються на ці перемінні.
Рішення, що задовольняють системі обмежень і вимогам ненегативності, є припустимими, а рішення, що задовольняють одночасно і вимогою мінімізації (максимізації) функції в цілому є оптимальними.
4. Тема 2. Двовимірні задачі лінійного програмування. Графічний метод рішення. Дослідження на можливість розв'язання.
Мета вивчення теми: навчитися вирішувати двовимірні задачі лінійного програмування графічним методом (двовимірна задача лінійного програмування, методи рішення).
Двовимірна задача лінійного програмування задача лінійного програмування, кількість перемінних якої дорівнює 2.
Перемінні прийнято позначати x1 і x2. Розглянута раніше задача лінійного програмування є двовимірною. У загальному виді двовимірну задачу лінійного програмування можна подати таким чином.
Визначити значення перемінних x1 і x2, при яких лінійна цільова функція F досягає максимуму (мінімуму)
F=с1x1+с2x2 -> max (min)
при обмеженнях на перемінні
Серед обмежень можуть одночасно зустрічатися знаки >= , <= і =. Коефіцієнти aij, bi, cj, i=1..m, j =1,2 будь-які дійсні числа (можливо і 0).
Двовимірні задачі лінійного програмування зазвичай вирішуються графічно.
Приклад 1.
Вирішимо отриману двовимірну задачу лінійного програмування графічно:
Рішення.
Побудова області припустимих рішень цільової функції F.
Побудуємо прямокутну систему координат, де вісь ОX позначимо як x1, а OY - як x2. Тому що, відповідно до умови (3) x1 і x2 ненегативні, то можна обмежиться розглядом першого квадранта.
Розглянемо перше обмеження: 3x1+4x2<=1700 (1)
Замінимо в даному обмеженні знак нерівності знаком рівності і побудуємо пряму:
3x1+4x2=1700 (1')
Для цього знайдемо дві точки, що належать даній прямій. Нехай, наприклад, x1=0, тоді підставивши 0 у (1') одержимо 4x2=1700 або x2=425. (0: 425) - координати першої точки, що належить прямій.
Нехай x2=0, тоді 3x1=1700, отже, x1=567. (567:0) - координати другої точки, що належить прямій. Відзначимо ці точки на числових осях.
Аналогічно, для другого обмеження:
2x1+5x2<=1600 (2)
2x1+5x2=1600 (2')
При x1=0, x2=320 (0; 320)
При x2=0, x1=800 (800; 0)
Побудуємо дані прямі (на малюнку 1 вони відповідно позначені (1') і (2'))
Тепер знайдемо на кресленні такі напівплощини, що відповідають нерівностям (1) і (2).
Пряма (1') 3x1+4x2=1700 поділяє координатну площину на дві напівплощини. Одна напівплощина розташована вище прямої, друга нижче. Щоб знайти ту напівплощину, що відповідає нерівності (1), необхідно взяти яку-небудь точку, що належить одній з напівплощин і підставити її координати в нерівність. Якщо нерівність буде вірною, то дана напівплощина і є шуканою .
Наприклад, візьмемо точку з координатами (0; 0) і підставимо її координати в нерівність (1) 3x1+4x2<=1700 або 0+0<=1700. Виходить 0<=1700 - дана нерівність є вірною, отже, нерівності (1) задовольняє напівплощина, що лежить нижче прямої (1').
Аналогічно, підійдемо для нерівності (2) 2x1+5x2<=1600. Візьмемо точку з координатами
(0; 0). Виходить 0<=1600 - дана нерівність вірна. Нерівності (2) задовольняє напівплощина, розташована нижче прямої (2').
Стрілки на кожній границі, з якої сторони прямої виконані обмеження. З огляду на, те що x1 і x2 є ненегативними, одержуємо, що чотирикутник ОАВС є областю, що містить точки, для яких виконані умови, що замкнуті у фігурні дужки.
Точки, що лежать усередині і на границі цієї області є припустимими рішеннями, але нам потрібні, тільки ті, при яких функція F буде приймати максимальне значення.
Побудова прямої рівня.
Візьмемо довільну точку, що належить області припустимих рішень - чотирикутникові ОАВС, наприклад, точку М с координатами (100; 100). Підставимо координати точки М в функцію F.
F(100; 100)=2*100+4*100=600.
Пряма рівня буде мати такий вигляд: 2x1+4x2=600.
Побудуємо отриману пряму. Для цього необхідно знайти координати двох довільних точок на цій прямій. Одна точка в нас уже є - це точка М(100; 100). Знайдемо ще одну точку. Нехай x2=0, тоді x1=300. Отже, координати додаткової точки (300; 0). Відзначимо отримані точки і побудуємо пряму рівня (на малюнку 1 вона позначена (3')).
Значення функції F будуть зростати в міру того, як пряма рівня віддаляється від початку координат у позитивному квадранті. Напрямок зростання функції F буде збігатися з вектором, координати якого є коефіцієнтами при перемінних x1 і x2 функції F. На малюнку 1- це вектор
a{2; 4}, відкладений від точки М.
Примітка. Зверніть увагу, що вектор a, що визначає напрямок зростання функції F, завжди буде перпендикулярний прямій рівня.
Мал. 1. Двовимірна задача лінійного програмування вирішена графічно.
Максимізація цільової функції F.
Для знаходження точки, у якій функція F досягне свого максимального значення, необхідно переміщати пряму рівня по напрямку вектора a до перетинання цієї прямої з граничною точкою області припустимих рішень. На нашому малюнку 1 - це точка В.
Знайдемо координати точки B. Дана точка розташована на перетинанні двох прямих (1') і (2'), тому, щоб знайти її координати необхідно вирішити наступну систему рівнянь:
З другого рівняння виразимо x1
і підставимо отримане значення в перше рівняння.
В(300; 200) - точка, що відповідає оптимальному рішенню задачі, отже, максимальний прибуток становить 2*300+4*200=1400 дол. у тиждень. Виходить, щоб дістати максимальний прибуток, фірмі необхідно випускати в тиждень 300 полиць моделі А і 200 полиць моделі В.
Алгоритм рішення задачі двовимірного лінійного програмування
графічним методом:
Будуємо область припустимих рішень функції F.
Для цього в обмеженнях знаки нерівності замінюємо знаками рівності і будуємо одержані прямі. Потім визначаємо ті напівплощини, які відповідають даним обмеженням і одержуємо область припустимих рішень, що лежить на перехресті всіх напівплощин.
Будуємо пряму рівня.
Для цього беремо довільну точку, що належить області припустимих рішень функції F і, підставивши координати цієї точки в функцію, одержуємо пряму рівня. Потім від вибраної точки М, відкладаємо вектор a, координати якого – це коефіцієнти при цільовій функції F.
Максимізуємо (мінімізуємо) цільову функцію F.
Для максимізації (мінімізації) функції F переміщуємо пряму рівня в напрямку ( в зворотному напрямку відносно) вектора a до пересічення з граничною точкою області припустимих рішень. Одержана точка є оптимальним рішенням, в якому функція досягає свого максимуму (мінімуму). Знаходимо координати цієї точки і підставляємо їх в функцію F.
Приклад 2
Вирішити графічним способом наступну двовимірну задачу лінійного програмування:
Рішення:
Побудова області припустимих рішень цільової функції F.
Побудуємо прямокутну систему координат (Мал.2). Тому що, x1 і x2 ненегативні, то можна обмежиться розглядом першого квадранта.
Розглянемо перше обмеження:
2x1+4x2<=8
Замінимо в даному обмеженні знак нерівності знаком рівності і побудуємо пряму.
2x1+4x2=8 (1)
Знайдемо дві точки, що належать даній прямій.
x1=0, отже, x2=2: координати (0; 2).
x2=0, отже, x1=4: координати (4; 0).
Розглянемо друге обмеження:
3x1+2x2<=6
3x1+2x2 =6 (2)
x1=0,отже, x2=3: координати (0; 3).
x2=0, отже, x1=2: координати (3; 0)
Розглянемо третє обмеження:
x1+x2<=1
x1+x2 =1 (3)
x1=0, отже, x2=1: координати (0; 1)
Якщо x2=0, то x1=-1, але ми розглядаємо тільки перший квадрант, тому візьмемо іншу точку, наприклад, x1=1, тоді x2=2: координати (1; 2)
Відкладемо отримані точки на числових осях і знайдемо напівплощини, що відповідають першим трьом обмеженням (на малюнку вони зазначені стрілками). Заштрихована область ОАВСD - область припустимих рішень функції F.
Побудова прямої рівня.
Візьмемо довільну точку, що належить області припустимих рішень - ОАВСD, наприклад, точку М с координатами (1; 1). Підставимо координати точки М в функцію F.
Виходить F(1; 1)=-3*1 - 1=- 4.
Пряма рівня буде мати такий вигляд: -3x1 - x2=- 4
Знайдемо дві точки цієї прямої - (1; 1) і (0; 4) (якщо x1=0, то x2=4). Побудуємо пряму рівня. Вектор а{-3; - 1}, відкладений від точки М указує напрямок зростання функції F. Мінімізуємо дану функцію F.
Мінімізація цільової функції F.
Тому що побудований вектор - є вектором а, що вказує напрямок зростання функції F, то пересування прямої рівня в напрямку, зворотному векторові а дозволить нам знайти точку мінімуму. У нашому випадку - це точка D. Координати точки D рівні (3; 0)
Підставляючи координати точки мінімуму у функцію F, одержимо
F(2; 0)= -3*3 - 0= -9
Відповідь: Мінімум функції F дорівнює - 9, і він досягається в точці з координатами (3;0)
Мал. 2. Побудова області припустимих рішень цільової функції F.
Тепер досліджуємо питання про можливість розв'язання двовимірної задачі лінійного програмування. Досліджуємо спочатку область припустимих рішень. Зрозуміло, що область припустимих рішень існує тільки тоді, коли обмеження не суперечливі. Якщо обмеження суперечливі, то область припустимих рішень не існує, отже, дана задача не має рішень.
Приклад 3
Вирішити графічним способом наступну двовимірну задачу лінійного програмування:
Рішення:
Побудова області припустимих рішень цільової функції F.
Перше обмеження:
x1+x2>=10
x1+x2 = 10 (1)
При x1=0, x2=10 (0; 10)
При x2=0, x1=10 (10; 0)
Друге обмеження:
3x1+5x2>=15
3x1+5x2 = 15 (2)
При x1=0, x2=3 (0; 3)
При x2=, x1=5 (5; 0)
Обмеження задачі суперечливі, тому області припустимих рішень не існує, отже, дана задача нерозв'язна.
Мал. 3. Побудова області припустимих рішень цільової функції F, приклад 3.
Розглянемо випадок, коли область припустимих рішень існує. Тут можливі два варіанти:
Область припустимих рішень обмежена з усіх боків (приклади №1,2);
Область припустимих рішень необмежена з якої-небудь сторони.
Примітка - Область припустимих рішень завжди є опуклою множиною. Множина S називається опуклою, якщо для будь-яких двох точок M і N цієї множини весь відрізок MN утримується в множині S. На малюнках зображені приклади опуклих (мал. 4) і неопуклих множин (мал. 5).
Мал. 4. Приклади опуклих множин.
Мал. 5. Приклади неопуклих множин.
Якщо область припустимих рішень обмежена (вона являє собою замкнутий опуклий N - косинець), то задача розв'язна й екстремальне значення досягається в будь - якій вершині області припустимих рішень. Виключення складає той випадок, коли пряма рівня рівнобіжна однієї зі сторін області припустимих рішень, і за умовою задачі її треба переміщати саме в напрямку цієї сторони. Тоді оптимальне рішення буде досягатися в будь-якій точці, що належить даній стороні.
Розглянемо цей випадок на прикладі.
Приклад 4.
Вирішити графічним способом наступну двовимірну задачу лінійного програмування:
Рішення.
Побудова області припустимих рішень цільової функції F.
Побудуємо прямокутну систему координат. Тому що, x1 і x2 ненегативні, то можна обмежиться розглядом першого квадранта (рис.6).
Розглянемо перше обмеження:
Розглянемо друге обмеження:
Відкладемо отримані точки на числових осях і знайдемо напівплощини, що відповідають першим трьом обмеженням (на малюнку вони зазначені стрілками). Заштрихована область ОАВС - область припустимих рішень функції F.
Побудова прямої рівня.
Візьмемо довільну точку, що належить області припустимих рішень - ОАВС, наприклад, точку М с координатами (1; 1). Підставимо координати точки М в функцію F.
F(1; 1)=-31 - 1=- 4
Пряма рівня буде мати такий вигляд: -3x1 - x2=- 4
Знайдемо дві точки цієї прямої - (1; 1) і (0; 4) (якщо x1=0, то x2=4). Побудуємо пряму рівня. Вектор a{-3; - 1}, відкладений від точки М указує напрямок зростання функції F. Мінімізуємо дану функцію F.
Мінімізація цільової функції F.
Тому що побудований вектор a - є вектором, що вказує напрямок зростання функції F, то пересування прямої рівня в напрямку, зворотному векторові a дозволить нам знайти точку мінімуму. Але тому що пряма рівня рівнобіжна прямій (2), то будь-яка точка на відрізку ВР є оптимальним рішенням. Зокрема у вершинах У(1,5 ; 1,5) і З(2; 0).
F(1,5; 1,5)= F(2; 0) = - 6
Відповідь: Мінімум функції F дорівнює - 6 і він досягається в будь-якій точці, що належить відрізкові ВР.
Мал. 6. Побудова області припустимих рішень цільової функції F, приклад 4.
Приклад 5
Вирішити графічним способом наступну двовимірну задачу лінійного програмування:
Рішення:
Побудова області припустимих рішень цільової функції F.
Побудуємо прямокутну систему координат. Тому що, x1 і x2 ненегативні, то можна обмежиться розглядом першого квадранта (мал. 7).
Розглянемо перше обмеження:
Розглянемо друге обмеження:
x2 =2 - пряма, що проходить через точку (0; 2) паралельно осі X1.
Відкладемо отримані точки на числових осях і знайдемо напівплощини, що відповідають першим двом обмеженням (на малюнку вони зазначені стрілками). Заштрихована область АВС - область припустимих рішень функції F.
Мал. 7. Побудова області припустимих рішень цільової функції F, приклад 5.
Побудова прямої рівня.
Візьмемо довільну крапку, що належить області припустимих рішень - АВС, наприклад, точку М с координатами (2,5; 1).
F(3; 1)=2,5+1=3,5
Пряма рівня буде мати такий вигляд: x1+x2=3,5
Знайдемо дві точки цієї прямої - (2,5; 1) і (0; 3,5) (якщо x1=0, то x2=3,5). Побудуємо пряму рівня. Вектор а {1; 1}, відкладений від точки М указує напрямок зростання функції F. Максимізуємо дану функцію F.
Максимізація цільової функції F.
Тому що область припустимих рішень необмежена в напрямку, у якому функція F зростає, то не існує кінцевої точки, у якій функція F досягала би максимуму. Таким чином, дана задача не має рішень.
Відповідь: Задача не має рішень.
Примітка - Якби в розглянутій вище задачі було потрібно мінімізувати функцію, при тих же обмеженнях, то мінімум досягався б у єдиній точці З(1; 0) і дорівнював би 1.
Таким чином, якщо область припустимих рішень необмежена множина, то задача може мати рішення, а може і не мати. Це залежить від того, у якому напрямку зростає (убуває) функція F, і чи збігається це напрямок з напрямком необмеженості області припустимих рішень.
Висновок: При рішенні двовимірних задач лінійного програмування можливі наступні ситуації (Мал. 8) (ОПР - область припустимих рішень):
Мал. 8. Можливі ситуації при рішенні двовимірних задач лінійного програмування.
Приклад 6.
Побудувати математичну модель формування плану виробництва. Вирішити її графічним методом.
Мається виробництво по виготовленню двох видів продукції А и В при обмеженому обсязі матеріалів трьох сортів, з яких виробляється продукція. Вихідні дані приведені в таблиці 1.
Таблиця 1
Види продукції
Норма витрат матеріалу на одиницю продукції
Прибуток на одиницю продукції
1
2
3
А
1
3
1
1
В
4
2
2
2
Обмеження на матеріали
320
360
180
?
Визначити обсяг виробництва продукції, що забезпечує одержання максимального прибутку.
Побудова математичної моделі.
Нехай x1 - кількість продукції виду А, а x2 - кількість продукції В. Тоді
x1+4x2 - кількість матеріалу сорту 1, необхідне на виготовлення продукції, а за умовою задачі це число не перевищує 320
x1+4x2<=320 (1)
3x1+2x2 - кількість матеріалу сорту 2, необхідне на виготовлення продукції, а за умовою задачі це число не перевищує 360
3x1+2x2<=360 (2)
x1+2x2 - кількість матеріалу сорту 2, необхідне на виготовлення продукції, а за умовою задачі це число не перевищує 180
x1+2x2<=180 (3)
Крім того, оскільки x1 і x2 виражають обсяг випуску продукції, то вони не можуть бути негативними, тобто
x1>=0, x2>=0 (4)
F=x1+2x2 - прибуток, що повинний бути максимальної. Таким чином, маємо наступну математичну модель для даної задачі.
Рішення:
Побудова області припустимих рішень цільової функції F.
Побудуємо прямокутну систему координат. Тому що, x1 і x2 ненегативні, то можна обмежиться розглядом першого квадранта.
Розглянемо перше обмеження:
Розглянемо друге обмеження:
Розглянемо третє обмеження:
Відкладемо отримані точки на числових осях і знайдемо напівплощини, що відповідають даним обмеженням (на малюнку вони зазначені стрілками). Заштрихована область ОАВС - область припустимих рішень функції F.
Побудова прямої рівня.
Візьмемо довільну точку, що належить області припустимих рішень - ОАВС, наприклад, точку М с координатами (20; 20).
F(20; 20)=20+2*20=60
Пряма рівня буде мати такий вигляд: x1+2x2=60
Знайдемо двох точок цієї прямої - (20; 20) і (60; 0) (якщо x2=0, то x1=60). Побудуємо пряму рівня. Вектор а {1; 2}, відкладений від точки М указує напрямку зростання функції F. Максимізуємо дану функцію F.
Максимізація цільової функції F.
Тому що побудований вектор a - є вектором, що вказує напрямок зростання функції F, то пересування прямій рівня в напрямку вектора a дозволить нам знайти точку максимуму. У нашому випадку - це точка В. Дана точка розташована на перетинанні двох прямих (1) і (3), тому, щоб знайти її координати необхідно вирішити наступну систему рівнянь:
Віднімемо з другого рівняння перше. Виходить 2x2=140 або x2 =70 . Підставимо знайдене значення x2 у перше рівняння: x1=180 - 140=40.
(40; 70) - точка, що відповідає оптимальному рішенню задачі, отже, максимальний прибуток становить 40+2*70=180. Виходить, щоб дістати максимальний прибуток, фірмі необхідно випускати сорок одиниць продукції виду А и сімдесят одиниць продукції виду В.
Відповідь: Для одержання максимального прибутку необхідно випускати 40 одиниць продукції виду А и 70 одиниць продукції виду В.
Мал. 9. Формування плану виробництва графічним методом, приклад 6.
Приклад 7.
Знайти мінімум цільової функції.
Задачі лінійного програмування можна дати геометричне тлумачення. Нехай потрібно знайти значення цільової функції (лінійної форми) z=2x1+3x2 при умовах
при цьому 0х13 і 0х22.
Як бачимо, перемінні х1 і х2 ненегативні, тому безліч точок (х1,х2), що є припустимим рішенням, буде знаходитися в першому квадранті. Крім того, значення х1 і х2 не повинні за умовою перевищувати відповідно чисел 3 і 2 на координатних осях Ох1 і Ох2. Нерівності визначають собою напівплощини. Таким чином, усі даного обмеження утворять опуклий багатокутник АМВСD (мал. 10).
17.03.2013 00:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора