Лінійне програмування.

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

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

При цьому враховуються певні обмеження, що накладаються на використання ресурсів умовами економічної ситуації.

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

Як було сказано раніше, лінійне програмування є одним із вдалих методів використання ДО.

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

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

Обмеження характеризують наявні можливості розв'язання завдання.

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

Рішення, що задовольняє умови завдання і відповідає поставленій меті, називається оптимальним планом.

Лінійне програмування (планування) служить для вибору найкращого плану розподілу обмежених однорідних ресурсів з метою розв'язання поставлених завдань.

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

В загальному вигляді постановка завдання лінійного програмування полягає в наступному.

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

де x_j — шукані величини, що містять розв'язання поставленого завдання; а_ij і b_i, — відомі постійні величини, що характеризують умови завдання.

Цільова функція (лінійна форма) надається у вигляді:

де c_j — постійні коефіцієнти (коефіцієнти вартості).

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

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

Загальне математичне формулювання завдання відповідає умовам (5.12) і (5.13)

Перший рядок системи рівнянь (5.12)

в даному прикладі це означає наступне:

a₁₁ — кількість одиниць ресурсів вигляду 1 на першому підприємстві,

а₁₂ — кількість одиниць ресурсів вигляду 1 на другому підприємстві і т.п.,

b₁ — загальний ресурс ресурсів вигляду 1 (для всіх підприємств),

x₁, х₂,іт.д. — шукана кількість підприємств типу 1,2 і т.д.

Другий рядок згаданої системи рівнянь містить аналогічні величини і ресурсів вигляду 2 і т.д. Функція мети відповідає формулі (5.16).

Треба повернути в мінімум величину

де с - показник, що характеризує витрати підприємств.

Нехай m — загальна кількість різних видів ресурсів, якими володіє власник, an — кількість типів підприємств, між якими ресурси повинні бути розподілені. При цьому відомо, яка кількість однорідних ресурсів різного виду (і = 1,2... m) може бути реалізована на кожному з підприємств даного типу (j = 1, 2... п), також загальна кількість ресурсів даного виду (b_і). Відомо також відносне значення витрат на кожному з підприємств (с_j).

Завдання полягає в тому, щоб найкращим (оптимальним чином розподілити наявні ресурси за підприємствами, тоді знайти невідомі величини х_j — потрібні для цієї кількості підпріємств даного типу.

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

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

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

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Завдання теорії корисності і підхід Байєса.	\|	Нелінійне програмування.

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

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