Етап побудова ліній рівня цільової функції і визначення точки максимуму - студопедія

Мета - знайти в побудованому многоугольнике AFEDCB точку, в якій функція мети Z = 2x1 + 3x2 приймає максимальне значення.

Проведемо пряму 2x1 + 3x2 = сonst (лінію рівня) так, щоб вона перетинала багатокутник AFEDCB (наприклад, Const = 10). Ця лінія рівня на малюнку зображена пунктирною лінією.

Якщо розглядати значення лінійної цільової функції Z на множині точок (x1, x2), що належать відрізку пунктирною прямий, розташованих у межах шестикутника, то всі вони дорівнюють одному і тому ж значенню (Const = 10).

Визначимо напрямок зростання функції. Для цього побудуємо лінію рівня з більшим значенням. Це буде пряма, паралельна з побудованої, але розташована правіше. Значить, в заданому напрямку значення цільової функції зростає, і в наших інтересах зрушити її якомога далі в цьому напрямку.

Зрушення можна продовжувати до тих пір, поки переміщувана пряма перетинає багатокутник допустимих рішень. Останнє положення прямої, коли вона має одну спільну точку з багатокутником AFEDCB (точка С), відповідає максимальному значенню цільової функції Z і досягається в точці С з координатами x1 = 4/3 ( »1.333), x2 = 10/3 (" 3.333) . При цьому Z = 38/3 ( »12.667).

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

Перше. Область допустимих рішень - кутника (Чому опуклий? Чи може область допустимих рішень являти собою порожня множина? Точку? Відрізок? Луч? Пряму? Якщо так, наведіть приклад системи обмежень).

Друге . Максимум цільової функції досягається в вершині багатокутника допустимих рішень

47. умова оптимальності рішення задач лінійного програмування

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

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

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

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

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

Завдання умовної оптимізації (2.1), (2.2) зазвичай записують у вигляді:

знайти максимум або мінімум функції

Умова (2.5) необов'язково, але його завжди при необхідності можна домогтися. Позначення говорить про те, що в конкретному обмеження можливий один із знаків ≤, = або ≥. Більш компактна запис:

Завдання (2.6) - (2.8) - спільне завдання оптимального (математичного) програмування, інакше - математична модель задачі оптимального програмування, в основі побудови (розробки) якої лежать принципи оптимальності, системності та адекватності.

Вектор (набір керуючих змінних хj. J = 1, 2. п) називається допустимим рішенням або планом завдання оптимального програмування, якщо його компоненти xj задовольняють системі обмежень. А той план (допустиме рішення), який доставляє максимум або мінімум цільової функції f (x1. Х2. Хn) називається оптимальним планом (оптимальним поведінкою, або просто рішенням) завдання оптимального програмування.

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

Вирішити задачу оптимального програмування (отримати рішення по оптимизационной економіко-математичної моделі) - це означає:

- по-перше, знайти оптимальний план,

який, з урахуванням інтерпретації його компонент, і визначає оптимальну поведінку в ситуації, що розглядається;

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

Іноді неможливо отримати рішення по оптимізаційної моделі: область допустимих рішень може виявитися порожнім безліччю (завдання суперечлива) або цільова функція є необмеженою на області визначення.

Перший випадок пов'язаний з неточностями в постановці економічної задачі або (і) розробленої економіко-математичної моделі (ЕММ). Наприклад, з наявним обсягом ресурсів свідомо неможливо виконати навіть ті мінімальні обсяги робіт, які закладаються в обмеження як необхідні мінімальні планові завдання. Якщо в даній ситуації все ж необхідно знайти рішення задачі, то слід побудувати непорожня множина допустимих рішень, виключивши одне або кілька обмежень, тобто фактично дотримати принцип альтернативності.

Другий випадок зазвичай означає, що ЕММ розроблена некоректно і деякі суттєві обмеження в ній відсутні.

Завдання оптимального програмування в найбільш загальному вигляді класифікують за такими ознаками.

1. За характером взаємозв'язку між змінними:

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

2. За характером зміни змінних:

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

3. По обліку фактора часу:

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

1. За наявності інформації про змінних:

а) завдання в умовах повної визначеності (детерміновані);

б) завдання в умовах неповної інформації;

в) завдання в умовах невизначеності.

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

2. За кількістю критеріїв оцінки альтернатив:

а) прості, однокритеріальних завдання;

б) складні, багатокритеріальні задачі.

У завданнях (а) економічно прийнятно використання одного критерію оптимальності або вдасться спеціальними процедурами (наприклад, "зважуванням пріоритетів") звести багатокритерійний пошук до однокритеріальних; приклади багатокритеріальних задач розглянуті в розділі 3.

Поєднання ознак 1-5 дозволяє групувати (класифікувати) в найзагальнішому вигляді завдання і методи оптимального програмування, наприклад: 1а) 2а) 3а) 4а) 5а) - завдання і методи лінійного програмування, 1б) 2а) 3а) 4а) 5а) - завдання і методи нелінійного програмування, 1а) 2б) 3а) 4а) 5а) - завдання і методи цілочисельного (дискретного) лінійного програмування і т.д.

Нові можливості для широкого практичного застосування методів оптимального програмування представляють сучасні офісні кошти. Широке коло фахівців у своїй повсякденній практиці використовує необхідний компонент фінансово-економічних розрахунків - Microsoft Excel (MS Excel), який містить спеціальний засіб - надбудову Пошук рішення, що дозволяє реалізовувати моделі лінійної, нелінійної та дискретної оптимізації. Технологія оптимізації за допомогою надбудови Пошук рішення з рішенням деяких типових задач оптимального програмування в середовищі MS Excel докладно розглянута, наприклад, в літературі.

48. Основні визначення теорії подвійності.

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

Розглянемо задачу теми 3.8 про планований випуск продукції.

Побудуємо двоїсту їй завдання за такими правилами.

Кількість змінних в двоїстої задачі дорівнює кількості нерівностей у вихідній.

Матриця коефіцієнтів двоїстої задачі є транспонованою до матриці коефіцієнтів вихідної.

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

Умовами невід'ємності змінних вихідної задачі відповідають нерівності-обмеження двоїстої, спрямовані в іншу сторону. І навпаки, неравенствам-обмеженням у вихідній відповідають умови невід'ємності в двоїстої.

Зауважимо, що рядки матриці завдання I є стовпцями матриці завдання II. Тому коефіцієнти при змінних yi в завданні II - це, відповідно, коефіцієнти i -го нерівності в завданні I.

Нерівності, з'єднані стрілками, будемо називати сполученими.