Навігація
Головна
Геометрична інтерпретація задачіФорми запису задачі лінійного програмування та її економічна...Технологія аналізу психічних процесів суб'єкта праці, заснована на...ЗАСТОСУВАННЯ ГЕОМЕТРИЧНИХ ПОБУДОВКопенгагенська та ансамблева інтерпретації квантової механікиІнтерпретації XX вКвазітеологічна інтерпретація Ж. ЕллюляФормально-символічна інтерпретація Е. КассірераАнтропологічна інтерпретація X. Ортеги-і-ГассетаРомантико-символічна інтерпретація Е. Каппа
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

Геометрична інтерпретація задачі

Розглянемо задачу ЛП в стандартній формі запису:

(2.18)

при обмеженнях

(2.19)

(2.20)

Розглянемо цю задачу на площині, тобто при п = 2. Нехай система нерівностей (2.19), (2.20) сумісна (має хоча б одне рішення):

Кожне нерівність цієї системи геометрично визначає полуплоскость з граничній прямій. Умови невід'ємності визначають півплощини, відповідно, з граничними прямими,. Система сумісна, тому півплощини, як опуклі множини, перетинаючись, утворюють спільну частину, яка є опуклим множиною і являє собою сукупність точок, координати кожної з яких є вирішенням даної системи. Сукупність цих точок називають багатокутником рішень.

Він може бути точкою, відрізком, променем, багатокутником, необмеженої багатокутної областю.

Якщо в системі обмежень (2.19) - (2.20) n = 3, то кожне нерівність геометрично представляє півпростір тривимірного простору, гранична площина якого. Умови невід'ємності визначають півпростору з граничними площинами, відповідно. Якщо система обмежень сумісна, то ці півпростору, як опуклі множини, перетинаючись, утворюють в тривимірному просторі загальну частина, що називається многогранником рішень.

Нехай в системі обмежень (2.19) - (2.20) п> 3, тоді кожне нерівність визначає півпростір n -мірного простору з граничною гиперплоскостью, а умови невід'ємності - півпростору з граничними гіперплоскостямі.

Якщо система обмежень сумісна, то, за аналогією з тривимірним простором, вона утворює спільну частину "-мірного простору, звану многогранником рішень, так як координати кожної його точки є рішенням.

Таким чином, геометрично задача лінійного програмування (2.18) - (2.20) являє собою відшукання такої точки багатогранника рішень, координати якої доставляють лінійної функції мети максимальне (мінімальне) значення, причому припустимими рішеннями є всі крапки багатогранника рішень.

Якщо в ЗЛП обмеження задані у вигляді нерівностей з двома змінними, то вона може бути вирішена графічно. Графічний метод розв'язання ЗЛП складається з наступних етапів.

Етап 1. Спочатку па координатної площини x 10 x 2 будується допустима багатокутна область (область допустимих рішень, область визначення задачі), відповідна обмеженням. Далі будується вектор-градієнт лінійної функції в якій-небудь точці, що належить допустимої області:

(2.21)

Етап 2. Пряма, звана лінією рівня і перпендикулярна вектору-градієнту, пересувається в напрямку цього вектора у разі максимізації до тих пір, поки не покине меж області допустимих рішень (ОДР). Гранична точка (або точки) області при цьому русі і є точкою максимуму.

Етап 3. Для знаходження координат точки максимуму достатньо спільно вирішити два рівняння прямих, одержуваних з відповідних обмежень і дають в перетині точку максимуму. Значення, знайдене в одержуваної точці, є максимальним.

У разі мінімізації пряму треба переміщати в напрямку, протилежному вектору-градієнту. Ясно, що якщо пряма при своєму русі не покидає ОДР, то відповідний максимум або мінімум не існує (область визначення завдання - незамкнутий багатокутник).

Приклад 2.6. Вирішити графічним методом наступну ЗЛП:

Рішення. Прямі обмеження означають, що область рішень буде лежати в першій чверті декартової (прямокутної) системи координат; відзначимо штрихуванням цю область на рис. 2.4.

Етап 1. Визначимо безліч рішень першого нерівності. Воно складається з рішення рівняння і строгої нерівності. Рішенням рівняння служать точки прямий. Побудуємо пряму по двох точках (0; 7) і (21; 0), які легко отримати в результаті послідовного обнулення однієї із змінних. На рис. 2.4 позначимо її цифрою I.

data-override-format="true" data-page-url = "http://stud.com.ua">

Безліч рішень строгої нерівності - одна з півплощини, на які ділить площину побудована пряма. Яка з них є шуканої, можна з'ясувати за допомогою однієї контрольної точки. Якщо в довільно взятої точці, що не належить прямій, нерівність виконується, то воно виконується і у всіх точках тієї півплощині, якій належить контрольна точка, і не виконується в усіх точках інший полупло-

Рішення ЗЛП графічним методом

Мал. 2.4. Рішення ЗЛП графічним методом

скостити. В якості такої точки зручно брати початок координат. Підставами координати (0; 0) в нерівність, отримаємо -21 <0, тобто воно виконується. Отже, областю рішення нерівності служить нижня напівплощина.

Аналогічним чином побудуємо області вирішення двох інших нерівностей.

(на рис. 2.4 пряма II);

при виконується, береться нижня напівплощина.

(на малюнку пряма III);

при виконується, береться нижня напівплощина.

Заштріхуем загальну область для всіх нерівностей, позначимо вершини багатокутника латинськими літерами і визначимо їх координати, вирішуючи систему рівнянь двох пересічних відповідних прямих. Наприклад, визначимо координати точки С, що є точкою перетину другої і третьої прямої:

Обчислимо значення цільової функції в цій точці:

Аналогічно поступимо для інших точок, які є вершинами замкнутого опуклого багатокутника OABCD, що представляє собою область допустимих рішень розглянутої ЗЛП. Координати цих вершин мають такі значення:

O (0; 0), А (0; 7), B (3; 6), С (5; 3), D (6; 0).

Етап 2. Дорівняємо цільову функцію постійній величині а:.

Це рівняння є множиною точок, в якому цільова функція приймає значення, рівне а. Міняючи значення а, отримаємо сімейство паралельних прямих, кожна з яких називається лінією рівня. Нехай а = 0, обчислимо координати двох точок, що задовольняють відповідному рівнянню В якості однієї з цих точок зручно взяти точку Про (0; 0), а так як при буде, то в якості другої точки візьмемо точку G (2; -1).

Через ці дві точки проведемо лінію рівня (пунктирна пряма на рис. 2.4).

Слід помститися, що в багатьох випадках зручно брати значення а одно не нулю, а цілому числу, що поділяється без залишку на коефіцієнти при невідомих у цільовій функції задачі. Наприклад, у розглянутій задачі можна було б брати рівняння лінії рівня вигляді; тоді легко б визначалися дві точки перетину лінії рівня з координатними осями.

Етап 3. Для визначення напрямку руху до оптимуму побудуємо вектор-градієнт, координати якого (відповідно до (2.21)) є приватними похідними функції, тобто. Щоб побудувати цей вектор, потрібно з'єднати точку (30; 60) з початком координат . При максимізації цільової функції необхідно рухатися в напрямку вектора- градієнта, а при мінімізації - у протилежному напрямку. Для зручності можна будувати вектор, пропорційний вектору. Так, на рис. 2.4 зображений вектор

У нашому випадку рух лінії рівня (геометрично вона перпендикулярна вектору-градієнту) будемо здійснювати до її перетину з точкою В, далі вона виходить з області допустимих рішень. Отже, саме в цій точці досягається максимум цільової функції. Звідси легко записати рішення вихідної ЗЛП: і досягається при

Якщо поставити завдання мінімізації функції при тих же обмеженнях, лінію рівня необхідно зміщувати паралельно самій собі в напрямку, протилежному вектору-градієнту. Як це видно на рис. 2.4, мінімум цільової функції досягається в точці O (0; 0), отже, можна записати і досягається при

При вирішенні деяких ЗЛП графічним методом може зустрітися випадок, коли лінія рівня паралельна однієї зі сторін опуклого багатокутника допустимих рішень, причому ця сторона розташована в напрямку зсуву лінії рівня при прагненні цільової функції до свого оптимуму. У цьому випадку оптимальне значення цільової функції досягається не в одній, а в двох кутових точках (вершинах) багатокутника рішень і, отже, у всіх точках відрізка, що з'єднує ці вершини, тобто задача матиме незліченна безліч рішень (перший особливий випадок).

Цей особливий випадок рішення ЗЛП (випадок неєдиним рішення) ілюструється, наприклад, наступним завданням:

Графічне рішення цієї задачі показано на рис. 2.5.

Лінія рівня паралельна одній з ліній по межі області допустимих рішень

Це означає, що завдання має нескінченну безліч оптимальних рішень (його задають координати точок відрізка НД), серед яких два оптимальних рішення - в кутових точках В (0; 8) і С (5/3; 20/3).

Точки відрізка НД задаються рівнянням, де. При цьому максимальне значення цільової функції дорівнює 80.

Випадок неєдиним розв'язком ЗЛП

Мал. 2.5. Випадок неєдиним розв'язком ЗЛП

Завдання лінійного програмування не матиме рішень у випадку, коли область допустимих рішень є пусте безліч, тобто система обмежень ЗЛП містить суперечливі нерівності та на координатній площині пет жодної точки, що задовольняє цим обмеженням (другий особливий випадок).

Очевидно також, якщо область допустимих рішень задачі є незамкнутим опуклим багатокутником в напрямку оптимізації цільової функції, то цільова функція буде необмеженою і ЗЛП не матиме рішень; в цьому випадку умовно можна записати, що, наприклад, (третій особливий випадок).

Зазначені вище два випадки відсутності рішень в ЗЛП ілюструються рис. 2.6 і 2.7, на яких графічно представлені, відповідно, завдання:

Як видно з малюнків, перша з наведених ЗЛП не має рішення, оскільки її безліч допустимих ре-

Суперечливість системи

Мал. 2.6. Суперечливість системи

Необмеженість ЦФ обмежень

Мал. 2.7. Необмеженість ЦФ обмежень

шений - порожня множина, друга - оскільки не існує кінцевого максимуму на необмеженій безлічі припустимих рішень.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
data-override-format="true" data-page-url = "http://stud.com.ua">

Cхожі теми

Геометрична інтерпретація задачі
Форми запису задачі лінійного програмування та її економічна інтерпретація
Технологія аналізу психічних процесів суб'єкта праці, заснована на інтерпретації його фахових задач
ЗАСТОСУВАННЯ ГЕОМЕТРИЧНИХ ПОБУДОВ
Копенгагенська та ансамблева інтерпретації квантової механіки
Інтерпретації XX в
Квазітеологічна інтерпретація Ж. Еллюля
Формально-символічна інтерпретація Е. Кассірера
Антропологічна інтерпретація X. Ортеги-і-Гассета
Романтико-символічна інтерпретація Е. Каппа
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук