2. Основи оптимального управління
|
|
Скачати 0.71 Mb.
|
|
3.3. Графічний розв’язок систем т лінійних нерівностей з двома змінними Дано систему т лінійних нерівностей з двома змінними  (3.1)Знак деяких або всіх нерівностей може бути „  ”.Розглянемо першу нерівність системи (3.1) у системі координат  . Побудуємо пряму  , яка є граничною прямою. Ця пряма ділить площину на дві півплощини (1) і (2).  (2) (1) Напівплощина (1) вміщує початок координат. Для визначення, з якого боку від граничної прямої розміщена задана напівплощина необхідно взяти довільну точку на площині (краще початок координат) і підставити координати цієї точки у нерівність. Якщо нерівність справедлива, то напівплощина звернена у бік цієї точки, якщо не справедлива – то у протилежний бік від точки. Напрямок напівплощини на малюнку позначається стрілкою. Розв’язком кожної нерівності системи є напівплощина, яка вміщує граничну пряму і розміщена по одну сторону від неї. Перетином напівплощин, кожна з яких визначається відповідною нерівністю системи, називається областю розв’язків системи (ОР). Область розв’язків системи, яка задовольняє умовам невід’ємності (  ), називається областю невід’ємних або припустимих розв’язків (ОПР).Приклад. Знайти ОР і ОПР системи нерівностей і визначити координати кутових точок ОПР.  Знайдемо ОР системи. Для цього побудуємо граничну пряму  і підставимо координати точки  у нерівність (1):  Координати точки не задовольняють нерівності (1), тому розв’язком цієї нерівності є напівплощина, що не вміщує точки . (1)  При  При  (2)  При  При  (3)  При  При  (4)  При  При  Областю розв’язків і областю припустимих розв’язків є чотирьохкутник  . Знайдемо кутові точки чотирьохкутника.   . ;  .   .   .3.4. Графічний метод Найбільш простим і наочним методом лінійного програмування є графічний метод. Він застосовується для розв’язання задач лінійного програмування, які задано у неканонічній формі і багатьма змінними у канонічній формі при умові, що вони вміщують не більше двох вільних змінних. З геометричної точки зору у задачах лінійного програмування відшукується така кутова точка або набір точок із припустимої множини розв’язків, на якій досягається сама верхня (нижня) лінія рівня, розміщена далі (ближче) інших у напрямку найбільш швидкого зростання. Для знаходження екстремального значення цільової функції при графічному розв’язанні задач лінійного програмування використовують вектор  на площині .З курсу вищої математики відомо, що для функції двох змінних  , що є диференційованою у точці  , градієнтом функції  називається вектор, координатами якого є значення частинних похідних у точці  . Градієнт функції характеризує напрямок і величину максимальної швидкості зростання цієї функції у точці. Для визначення геометричного змісту градієнта функції введемо поняття поверхні рівня. Поверхнею рівня функції  називається поверхня, на якій ця функція зберігає постійне значення. Градієнт функції у даній точці ортогональний до цієї поверхні. У випадку функції двох змінних, замість поверхні рівня будуть фігурувати лінії рівня. Надалі будемо позначати градієнт цільової функції  . Цей вектор показує напрямок найшвидшої зміни цільової функції. ,де  - одиничні вектори за осями  та  відповідно.Таким чином  . Координатами вектора  є коефіцієнти цільової функції  .Алгоритм розв’язання задачі 1. Знаходимо область припустимих розв’язків системи обмежень задачі. 2. Будуємо вектор .3. Проведемо лінію рівня  , яка ортогональна до вектора .4. Лінію рівня переміщуємо за напрямком вектора для задач на максимум і в напрямку протилежному - для задач на мінімум.Переміщення лінії рівня здійснюється до тих пір, доки у неї не буде тільки однієї спільної точки з областю припустимих розв’язків. Ця точка визначає єдиний розв’язок задачі лінійного програмування і буде точкою екстремуму. Якщо ж лінія рівня буде паралельною одній з сторін області припустимих розв’язків, то у цьому випадку екстремум розглядається у всіх точках відповідної сторони, а задача лінійного програмування буде мати нескінчену множину рішень. У цьому випадку говорять, що така задача має альтернативний оптимум і її розв’язок знаходиться за формулою  де  , а  ,  - оптимальні рішення у кутових точках області припустимих розв’язків.Задача лінійного програмування може бути нерозв’язаною, коли обмеження, що її визначають, будуть суперечними. 5. Знайдемо координати точки екстремуму і значення цільової функції в ній. 3.5. Симплексний метод Симплексний метод є універсальним, оскільки дозволяє розв’язати практично будь-яку задачу лінійного програмування, яка записана у канонічному вигляді. Ідея симплекс-методу або методу послідовного покращення плану полягає у тому, що починаючи з деякого початкового опорного рішення здійснюється послідовно спрямоване переміщення по опорним рішенням задачі до оптимального. Значення цільової функції при цьому переміщенні для задач на максимум не спадає. Оскільки число опорних рішень є скінченим, то через скінчене число кроків одержують оптимальний опорний розв’язок. Опорним розв’язком називають базисний невід’ємний розв’язок. Алгоритм симплексного методу 1. Математична модель задачі повинна бути канонічною. 2. Відшукується вихідний опорний розв’язок і здійснюється перевірка його на оптимальність. Для цього заповнюється симплексна таблиця. Всі рядки таблиці першого кроку за виключенням рядка  (індексний рядок) заповнюються за даними системи обмежень та цільової функції.БЗ – базисна змінна. Індексний рядок для змінних визначається за формулою  ,  ,
для вільного члена за формулою  .Можливі наступні випадки при розв’язанні задачі на максимум: - якщо всі оцінки  , то знайдений розв’язок є оптимальним;- якщо хоча б одна оцінка  , але при відповідній змінній немає жодного додатного коефіцієнта, розв’язання задачі припиняється, тому що  , тобто цільова функція є необмеженою у області припустимих розв’язків;- якщо хоча б одна оцінка від’ємна, а при відповідній змінній є хоча б один додатній коефіцієнт, то необхідно переходити до другого опорного розв’язку; - якщо від’ємних оцінок в індексному рядку декілька, то у стовпець базисної змінної (БЗ) вводять ту змінну, якій відповідає найбільша за абсолютною величиною від’ємна оцінка. Якщо хоча б одна оцінка  , то  -й стовпець приймається за ключовий. За ключовий рядок приймається такий, якому відповідає мінімальне відношення вільних членів  до додатних елементів -го стовпця. Елемент, який знаходиться на перетині ключових рядка і стовпця називається ключовим елементом.3. Заповнюється симплексна таблиця другого кроку: - переписується ключовий рядок, з діленням кожного його елемента на ключовий елемент; - заповнюється базисний стовпець, при цьому всі елементи окрім ключового дорівнюють нулю; - решта коефіцієнтів таблиці знаходяться за правилом прямокутника. Наприклад, якщо  є ключовим елементом, тоді у симплексній таблиці другого кроку .Альтернативний оптимум При розв’язанні задач лінійного програмування симплексним методом за критерій оптимальності приймають умову: оцінка вільних змінних  для задач на максимум і умова  для задач на мінімум.Якщо на будь-якому кроці хоча б одна з оцінок вільної змінної  , а решта для задач на максимум (для задач на мінімум), то прийнявши за ключовий стовпець той стовпець, де та знайдемо новий оптимальний розв’язок, при якому значення цільової функції не змінюється. У цьому випадку задача має альтернативний оптимум.Критерієм альтернативного оптимуму при розв’язанні задач симплексним методом є рівність нулю хоча б однієї оцінки вільної змінної .Якщо тільки одна оцінка вільної змінної дорівнює нулю, тоді розв’язок задачі знаходиться за формулою  , де .Якщо дві оцінки і більше, наприклад  , вільних змінних дорівнюють нулю, тоді оптимальний розв’язок знаходиться за формулою , де  |
||||||||||||||||||||||||||||||||||||||||||||||
Схожі:
| Календарно-тематичний план "Основи кадрового менеджменту" для професії... Теоретико-методологічні основи управління персоналом. Концепція управління людськими ресурсами |
ПЛАН-КОНСПЕКТ проведення заняття з психологічної підготовки з начальницьким... Тема 2 Формування оптимального рівня стану соціально-психологічного клімату в |
| 3. Управління та організаційна структура готельного комплексу Поняття... Організація як функція координації структурних підрозділів готельного комплексу. (для самостійного вивчення на основі повторення... |
Модуль Теоретичні основи стратегічного управління Семінарське заняття... Семінарське заняття №2 Концептуальні засади стратегічного управління підприємством |
| 1. Законодавчо-правові основи управління безпекою життєдіяльності Правова система формує передумови створення, функціонування, удосконалення системи управління безпекою життєдіяльності. Правова система... |
Урок із спецдисциплін операторів комп’ютерного набору Урок-конкурс «Найкращий оператор!» ... |
| ТЕОРЕТИЧНІ ОСНОВИ УПРАВЛІННЯ ДІЯЛЬНІСТЮ СПОРТИВНИХ ОРГАНІЗАЦІЙ Воронова В. А. Пути совершенствования управления физкультурным движением. М.: ФиС,1975 -95с |
Молдован В. В. Основи держави і права. Курс лекцій «Фінанси і кредит», 030509 «Облік і аудит», 030502 «Економічна кібернетика», 030505 «Управління персоналом та |
| РОЗДІЛ ПЕРШИЙ ЦИВІЛЬНИЙ ЗАХИСТ (ЦИВІЛЬНА ОБОРОНА) УКРАЇНИ ТА ОСНОВИ ЇЇ ВЕДЕННЯ Органи управління, аварійно-рятувальні підрозділи Оперативно-рятувальної служби цивільного захисту |
Міністерство освіти і науки України Сумський державний університет... РОЗДІЛ ТЕОРЕТИЧНІ ОСНОВИ УПРАВЛІННЯ ПОРТФЕЛЕМ ІННОВАЦІЙНИХ ПРОЕКТІВ ПІДПРИЄМСТВА |
При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
bibl.com.ua
звернутися до адміністрації
bibl.com.ua