Знаходження розв'язку задачі нелінійного програмування методом Франка-Вульфа

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

при наступних обмеженнях:

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

Читати повністю

Метод множників Лагранжа. Розв'язок задачі нелінійного програмування з обмеженнями-рівностями

Ідея методу множників Лагранжа при знаходженні розв'язку задачі нелінійного програмування, полягає в заміні початкової задачі дещо простішою. Для цього цільову функцію замінюють іншою, з більшою кількістю змінних і яка включає в себе умови, що подані як обмеження. Після такого перетворення подальше розв'язування задачі полягає в знаходженні екстремуму нової функції, на змінні якої не накладено ніяких обмежень. Тобто від початкової задачі пошуку умовного екстремуму переходимо до задачі відшукання безумовного екстремального значення іншої функції, яке визначається з допомогою необхідної умови існування екстремуму. Тобто, для розв'язування задачі необхідно знайти вирази частинних похідних нової цільової функції за кожною змінною і прирівняти їх до нуля. В результаті отримаємо систему рівнянь. Її розв'язок визначає так звані стаціонарні точки, серед яких є і шукані екстремальні значення функції.

Далі, розглянемо даний процес більш детально, та застосуємо метод множників Лагранжа для розв’язування задачі нелінійного програмування, що має вигляд:

Читати повністю

Графічний метод. Знаходження розв'язку задачі нелінійного програмування графічним методом

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

Після того, як формулювання задачі нелінійного програмування з двома невідомими та в загальному вигляді відоме, перейдемо до розгляду основних етапів її розв'язку з допомогою графічного методу:

Читати повністю

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

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

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

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

Читати повністю

Знаходження початкового опорного плану транспортної задачі методом плаваючих зон

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

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

Читати повністю

Розв'язок транспортної задачі розподільчим методом

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

Читати повністю

Використання методу диференціальних рент для знаходження оптимального плану транспортної задачі

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

  1. У кожному стовпчику транспортної таблиці знаходимо мінімальний тариф. Знайдені тарифи позначаємо колами, що їх оточують, і заповнюємо відповідні комірки максимально можливими перевезеннями. Таким чином, отримуємо розподіл, що в загальному може не задовільняти обмеженням транспортної задачі (якщо отриманий таким чином розподіл задовільняє обмеженням задачі, то він вважається оптимальним, і алгоритм методу диференціальних рент на цьому закінчується).
  2. Скорочуємо нерозподілені поставки продукту так, щоб при цьому загальна вартість перевезень залишалась мінімальною. Для цього виконуємо наступні кроки:
    1. визначаємо надлишкові та недостатні рядки (рядок є недостатнім (від'ємним), якщо запаси відповідного пункту відправлення розподілені повністю, а потреби пунктів призначення не задоволені; рядок є надлишковим (додатним), якщо потреби задоволені і при цьому залишився товар у відповідному пункті відправлення);
    2. для кожного стовпчика знаходимо різницю між тарифами у колі та найближчим до нього тарифом, який записаний в надлишковому рядку. Якщо тариф у колі знаходиться в позитивному (надлишковому) рядк, то  різницю не визначаємо; серед різниць знаходимо найменшу — проміжну ренту;
    3. переходимо до нової таблиці — додаємо до відповідних тарифів, які знаходяться у від'ємних (недостатніх) рядках, проміжну ренту. Інші елементи не змінюємо.

Читати повністю

« Попередня сторінкаНаступна сторінка »