1. Задачі оптимізації споживання. Методи розв'язку та післяоптимізаційного аналізу

Задача оптимізації споживання це задача знаходження такого набору товарів х^*, які належать простору товару х^*ЄХ, відповідає бюджетному обмеженню і корисність якого є найбільшою

Відповідає бюджетному обмеженню і на які накладаються інші обмеження, крім бюджетного.

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

Всі традиційні види функцій корисності є випуклими функціями, тому задача оптимізації споживання є задачою опуклого програмування.

Задача вирішується методом опуклого програмування

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

Розглянемо задачу лінійного програмування

(3.36)

(3.37)

(3.38)

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

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

2. Основні методи лінійного програмування

Метод потенціалів — розроблений в 1940 радянськими вченими Канторовичем та Гавуріним Л. В. в застосуванні до транспортної задачі;

Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.

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

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

Близький зв'язок між лінійним програмуванням та теорією ігор дозволяє використовувати для розв'язання задач лінійного програмування чисельні методи теорії ігор.

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

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

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

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