Меню
Головна
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

Лекція 2 Основи лінійного програмування

- Принцип оптимальності в плануванні та управлінні, загальна задача оптимального програмування

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

- Математичний апарат лінійного програмування

- Геометрична інтерпретація задачі

- Симплексний метод розв'язання задачі

Після вивчення цієї глави студенти повинні:

знати:

o загальні принципи оптимального планування та управління в економіці:

o основні поняття лінійного програмування:

o методи розв'язання задач лінійного програмування (ЗЛП);

вміти:

o формулювати загальну постановку ЗЛП;

o уявити ЗЛП в різних формах запису;

o дати економічну інтерпретацію отриманих результатів на всіх етапах графічного і симплексного методів розв'язання ЗЛП;

володіти:

o математичним апаратом лінійного програмування;

o практичними навичками формулювання і рішення ЗЛП.

Принцип оптимальності в плануванні та управлінні, загальна задача оптимального програмування

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

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

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

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

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

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

(2.1)

(2.2)

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

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

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

(2.3)

при обмеженнях

(2.4)

.............................

(2.5)

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

(2.6)

(2.7)

(2.8)

Завдання (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 докладно розглянута, наприклад, у літературі.

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

Постановка завдання. Пропонується п інвестиційних проектів, ретельна економічна експертиза яких дозволяє отримати для кожного з проектів досить переконливі економічні оцінки очікуваного ефекту від їх реалізації з1, с2, ..., зn і необхідних капіталовкладень р1, р2, ..., pn. Загальний обсяг можливих капіталовкладень обмежений величиною Ст. Необхідно так розпорядитися наявними фінансовими ресурсами, щоб максимізувати сумарний ефект від інвестицій.

Математична модель. Введемо необхідні позначення, нехай хj (j = 1, 2, ..., п):

Таким чином, формально інвестиційний план - це вектор Х=(х1, х2, ..., хn). З урахуванням цих позначень задача за критерієм "максимум економічного ефекту" математично запишеться наступним чином:

Наведена задача (модель) є задачею дискретного лінійного програмування з булевими операторами змінними (змінні, які можуть приймати тільки два значення: 1 і 0, інакше "так" або "ні"), тобто відноситься до класу задач 1а)2б)3а)4а)5а). Ця задача може бути вирішена, наприклад, відомим методом Балаша.

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

Розвиток і вдосконалення методів розв'язання задач оптимального програмування йде від випадків типу (а) до випадків типу (б), (в).

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

Саме ці завдання в подальшому розглядаються в даній главі.