Зміст
1 Постановка задач лінійного програмування (ЗЛП). Приклади економічних задач, що зводяться до ЗЛП. Допустимі і оптимальні рішення
2 Алгоритм Флойда. Постановка завдання
1 Постановка задач лінійного програмування (ЗЛП). Приклади економічних задач, що зводяться до ЗЛП. Допустимі та оптимальні рішення
У загальному вигляді задача лінійного програмування (надалі ЗЛП) може бути сформульована як задача знаходження найбільшого значення лінійної функції
(1)
на деякій множині D ГЊ R n , де x ГЋ D задовольняють системі обмежень
(2)
і, можливо, обмеженням
(3)
He применшуючи спільності, можна вважати, що в системі (2) перші т обмежень є нерівностями, а наступні - l-рівняннями. Очевидно, цього завжди можна домогтися за рахунок простого переупорядоченія обмежень. Щодо направлення знака нерівності будемо припускати, що ліва частина менше або дорівнює правій. Домогтися цього можна, помноживши на (-1) обидві частини тих нерівностей, які мають протилежний знак. Обмеження (3), взагалі кажучи, можуть бути розглянуті як окремий випадок обмежень у формі нерівностей, але в силу особливої вЂ‹вЂ‹структури їх зазвичай виділяють окремо і називають умовами неотрицательности (або тривіальними обмеженнями).
Додатково слід зауважити, що вибір типу шуканого екстремуму (Максимуму або мінімуму) також носить відносний характер. Так, завдання пошуку максимуму функції
еквівалентна задачі пошуку мінімуму функції
Часто умови задачі (1) - (3), містить обмеження лише типу нерівностей, буває зручно записувати у скороченій матричній формі
де з і x - вектори із простору R n , b - вектор із простору R m , a А - матриця розмірності m 'п.
Завдання лінійного програмування, записану у формі (1) - (3), називають загальною задачею лінійного програмування (ОЗЛП).
Якщо всі обмеження в задачі лінійного програмування є рівняннями і на всі змінні x j накладені умови неотрицательности, то вона називається задачею лінійного програмування в канонічній формі, або канонічної задачею лінійного програмування (КЗЛП). У матричній формі КЗЛП можна записати в наступному вигляді:
Оскільки будь оптимізаційна задача однозначно визначається цільовою функцією f і областю D, на якій відшукується оптимум (максимум), будемо позначати цю задачу парою (D, f).
Умовимося щодо термінології, яка використовується в Надалі і є загальноприйнятою в теорії лінійного програмування.
Планом ЗЛП називається всякий вектор х з простору R n .
Допустимим планом називається такий план ЗЛП, який задовольняє обмеженням (1.2) - (1.3), тобто міститься в області D. Сама область D називається при цьому областю допустимих планів. Оптимальним планом х * називається такий допустимий план, при якому цільова функція досягає оптимального (в нашому випадку - максимального) значення, тобто план, що задовольняє умові
max f (x) = f (x * ).
Величина f * = f (x * ) називається оптимальним значенням цільової функції.
Рішенням задачі називається пара (х * , f * ), що складається з оптимального плану та оптимального значення цільової функції, а процес вирішення полягає у відшуканні безлічі всіх рішень ЗЛП.
Приклади економічних задач, що зводяться до ЗЛП.
Незважаючи на різноманіття задач математичного програмування, при їх вирішенні можна виділити деяку загальну послідовність етапів, через які проходить будь операційне дослідження. Як правило, це:
1.Постановка завдання.
2.Построеніе змістовної (Вербальної) моделі розглянутого об'єкта (процесу). На даному етапі відбувається формалізація мети управління об'єктом, виділення можливих управляючих впливів, що впливають на досягнення сформульованої мети, а також опис системи обмежень на керуючі впливи.
3.Построеніе математичної моделі, тобто переклад сконструйованої вербальної моделі в ту форму, в якій для її вивчення може бути використаний математичний апарат.
4.Решеніе завдань, сформульованих на базі побудованої математичної моделі.
5.Проверка отриманих результатів на їх адекватність природі досліджуваної системи, включаючи дослідження впливу так званих внемодельних факторів, і можлива коректування первинної моделі.
6.Реалізація отриманого рішення на практиці.
Математичне моделювання в дослідженні операцій є, з одного боку, дуже важливим і складним, а з іншого - практично не піддається наукової формалізації процесом. Зауважимо, що неодноразово предпринимавшиеся спроби виділити загальні принципи створення математичних моделей призводили або до декларування рекомендацій самого загального характеру, труднопріложімих для вирішення конкретних проблем, або, навпаки, до появи рецептів, застосовних в Насправді тільки до вузького кола завдань. Тому більш корисним представляється знайомство з технікою математичного моделювання на конкретних прикладах.
В якості таких прикладів наведемо кілька класичних економіко-математичних моделей і задач, які можуть бути сформульовані на їх основі.
Управління портфелем активів . Розглянемо проблему прийняття інвестором рішення про вкладення наявного у нього капіталу. Набір характеристик потенційних об'єктів для інвестування, мають умовні імена від А до F, задається наступною таблицею.
Назва
Прибутковість (в%)
Термін викупу (рік)
Надійність (в балах)
А
5,5
2001
5
В
6,0
2005
4
З
8,0
2010
2
D
7,5
2002
3
Е
5,5
2000
5
F
7,0
2003
4
Припустимо, що при ухваленні рішення про придбання активів повинні бути дотримані умови:
a. сумарний обсяг капіталу, який повинен бути вкладений, становить $ 100 000;
b.доля коштів, вкладена в один об'єкт, не може перевищувати чверті від усього обсягу;
c. більше половини всіх засобів повинні бути вкладені в довгострокові активи (припустимо, на аналізований момент до таких відносяться активи з терміном погашення після 2004 р.);
d.доля активів, що мають надійність менш ніж 4 бали, не може перевищувати третини від сумарного обсягу.
Приступимо до складання економіко-математичної моделі для даної ситуації. Доцільно почати процес з визначення структури керованих змінних. У розглянутому прикладі в якості таких змінних виступають обсяги коштів, вкладені в активи тієї або іншої фірми. Позначимо їх як х А , х В , х З , х D , х E , х F . Тоді сумарний прибуток від розміщених активів, яку отримає інвестор, може бути представлена ​​у вигляді
(1)
На наступному етапі моделювання ми повинні формально описати перераховані вище обмеження ad на структуру портфеля.
a) Обмеження на сумарний обсяг активів:
x A + x B + x З + x D + x E + x F
