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

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

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

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

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

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

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

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

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

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

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

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

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

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

………………………………………………

j = 1, 2, …, n; i = 1, 2, …, m; m < n; xj ≥ 0, (5.12)

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

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

j = 1, 2, …, n, (5.13)

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

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

(5.14)

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

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

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

(5.15)

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

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

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

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

х1, x2, т д. — шукана кількість підприємств типу 1,2 і т.д. Другий рядок згаданої системи рівнянь містить аналогічні величини для ресурсів вигляду 2 і т. д. Функція мети відповідає формулі (5.13). Треба повернути в мінімум величину

, (5.16)

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

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

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

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

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

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

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