Новини освіти і науки:

G+

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

Економічно сутність і постановка задач НЛП.

ЗАДАЧІ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ. ОСНОВНІ МЕТОДИ ЇХ РОЗВ’ЯЗУВАННЯ ТА АНАЛІЗУ.

ТЕМА 8.

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

за умов

де і - нелінійні функції.

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

У точках і значення собівартості для обох розглядуваних функцій однакові, але в усіх інших точках ці значення відрізняються, причому в точці х₂ значною мірою:

Отже, лінеаризація нелінійних процесів є досить складною математичною задачею.

Для лінійних задач можна завжди знайти оптимальний розв'я зок універсальним методом — симплексним. При цьому немає проблеми з доведенням існування такого розв'язку. Адже в ре зультаті розв'язування задачі симплексним методом завжди діс таємо один із варіантів відповіді: 1) знайдено розв'язок; 2) задача суперечлива, тобто її розв'язку не існує; 3) цільова функція не обмежена, отже, розв'язку також немає.

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

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

Для розв'язування нелінійних задач застосовують наближені методи, стикаючись із проблемою локальних і глобальних оптимумів. Наприклад, на рис. 6.4. маємо на відрізку локальні оптимуми в точках , а глобальний — у точці і .

Більшість наближених методів дають змогу знаходити локальний оптимум. Визначивши всі локальні оптимуми, методом порівняння можна знайти глобальний. Проте для практичних розрахунків такий метод не є ефективним. Часто наближені методи не «вловлюють» глобального оптимуму, зокрема тоді, коли глобальний оптимум лежить досить близько до локального. Якщо відрізок розіб'ємо на десять підвідрізків і глобальний оптимум потрапить у відрізок (див. рис. 6.4), а ліворуч від та праворуч від крива підніматиметься, то глобальний оптимум буде пропущеним. Звернемо увагу ще на один дуже важливий момент. У задачах лінійного програмування точка оптимуму завжди була граничною. Для нелінійних задач точка, яка є оптимальним планом, може бути граничною або такою, що міститься всередині допустимої області розв'язків (планів).

8.2. Класичний метод оптимізації задач МЛП та базі використання множників Лагранжа та їх економічна інтепритація.

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

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

Оптимізаційні задачі, на змінні яких не накладаються обмеження, розв'язують методами класичної математики. Оптимізацію з обмеженнями-рівностями виконують методами зведеногоградієнта, скажімо методом Якобі, та множників Лагранжа. У задачах оптимізації з обмеженнями-нерівностями досліджують необхідні та достатні умови існування екстремуму Куна—Танкера.

Розглянемо метод множників Лагранжа на прикладі такої за дачі нелінійного програмування:

(6.15)

за умов

(6.16)

де функції і диференційовані.

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

(6.17)

де — не визначені поки що величини, так звані множники Лагранжа.

Знайшовши частинні похідні функції L за всіма змінними і прирівнявши їх до нуля:

запишемо систему

(6.18)

що є, як правило, нелінійною.

Розв'язавши цю систему, знайдемо і — стаціонарні точки. Оскільки їх визначено з необхідної умовиекстремуму, то в них можливий максимум або мінімум. Іноді стаціонарна точка є точкою перегину (сідлова точка). Отже, для визначення достатніх умов екстремуму та діагностування його типу існує спеціальний алгоритм [15].

Розв'яжемо методом множників Лагранжа наведену далі задачу.

Задача 1. Акціонерне товариство з обмеженою відповідальністю відвело 1200 га ріллі під основні рослинницькі культури — озиму пшеницю та цукрові буряки.

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

Показник	Площа, га, відведена
під озиму пшеницю,	під цукровий буряк,
Урожайність, т/га
Ціна, грн./т
Собівартість, грн./т

Знайти оптимальну площу посіву озимої пшениці та цукрових буряків.

Нехай — площа ріллі, відведена під сотні га озимої пшениці; — площа ріллі, відведена під цукрові буряки, сотні га.

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

Запишемо економіко-математичну модель. За критерій оптимальності візьмемо максимізацію валового прибутку:

за умов

Запишемо функцію Лагранжа:

Візьмемо частинні похідні і прирівняємо їх до нуля:

Із цієї системи визначимо сідлову точку. З першої та другої рівностей знайдемо вирази для і прирівняємо їх:

або

(6.19)

Із останнього рівняння цієї системи маємо:

Підставивши значення у (6.19), дістанемо:

або

Розв’язавши це квадратне рівняння, дістанемо

Відповідно дістанемо:

Тобто сідловими точками є такі:

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

Отже, цільова функція набуває максимального значення, якщо озима пшениця вирощується на площі 647 га, а цукровий буряк — на площі 553 га.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Основні методи розвязування здач ДЛП і аналіз оптимальних планів	\|	Опукле програмування. Необхідні та достатні умови існування сідлової точки. Теорема Куна-Такера.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.