Задача математичного програмування Тема 1 Питання термінології, історіографія назв
Тема 8л Графічний метод вирішенню задачі ЛП. Загальний підхід до
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Графічний метод розвязання задачі ЛП
| Тема 8л Графічний метод вирішенню задачі ЛП. Загальний підхід до
вирішеня ЛОЗ Тепер після введення поняття опуклості лінійної оболонки множини і градієнта цільової функції ми можемо розглянути найпростіші ідеї, що лежать в основі вирішення ЛП завдань і проілюструвати це геометричним методом (ГМ). Хоча ГМ і є частковим підходом до вирішення ЛПЗ, але на ньому можливо простежити деякі ідеї і логіку роботи більш загальних методів, а головне побудувати геометричні аналоги багатовимірних моделей, які ми будемо оптимізувати. Графічний метод розв'язання задачі ЛП Впорядковані набори n чисел можна геометрично інтерпретувати як точку або вектор n-мірного простору. Тому далі плани завдання лінійної оптимізації Х =(х1,х2,…,хn) будемо інтерпретувати як точки або вектори. У найпростішому випадку, коли число змінних дві, зручний наочний графічний метод. Розглянемо модель виду (*) з двома змінними f =с1х1 +с2х2 max а11х1 + а12х2 b1 а21х1 + а22х2 b2 (*) ……………………………. аm1х1 + аm2х2 bm х1 0, х2 0 На координатній площині Ох1х2 лінійні рівняння виду аijхj+аijхj=bi це прямі а лінійні нерівності аijхj+аijхj bi чи аijхj+аijхj bi - це півплощини. Умови х1 0, х2 0 дають полуплощини с граничными прямими х1=0 и х2=0. Варіанти області допустимих рішень ОДР на рис.: опуклий багатокутник (а), необмежена опукла багатокутна область (б), едина точка (в), луч (г), відрізок (д), пуста множина - нема ОДР (е). а) Якщо система обмежень сумісна, то півплощини як опуклі множини, перетинаючись, утворюють загальну частину, яка теж є опуклою множиною і являє собою ОДРЗ б) Якщо ОДРЗ порожня, то ЗЛП реш-я не має. в) Якщо ОДРЗ складається з єдиної точки х , то ця (x) і буде являтися рішенням ЗЛП. Нехай система нерівностей утворює ОДР у вигляді багатокутника рішень (рис1). Придамо ЦФ значення k. Отримаємо рівняння с1х1 + с2х2 = k. Це рівняння прямої лінії, в кожній точці якої ЦФ зберігає значення k. Якщо тепер k вважати параметром, то ми отримаємо сімейство паралельних прямих, званих лініями рівня цільової функції. Знайдемо далі напрямок зростання і зменшення цільової функції. Знайдемо часткові похідні цільової функції по змінним х1 і х2: . Рис 1. Вони показують швидкість зростання цільової функції вздовж осей х1 і х2 відповідно. Вектор С = (С1, С2) показує напрямок найшвидшого зростання цільової функції і називається вектором-градієнтом ЦФ. Вектор (-С) = (- С1; С2) називають антіградіентом і він вказує напрямок найшвидшого убування ЦФ. Вектор С = (С1, С2) перпендикулярний до прямих сімейства f = const. Т.ч., геометрично задача лінійної оптимізації (*) є пошук такої точки багатогранника рішень, координати якої доставляють лінійної функції f =с1х1 +с2х2 найбільше (найменше) значення, причому припустимими рішеннями є всі точки багатогранника рішень. жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|