Материал: Економетрія - Навчальний посібник ( Лугінін О.Є.)


3.2. методи вирішення задачі лп та її додатки

 

 3.2.1. Методи вирішення задач ЛП

До методів вирішення задач ЛП відносяться такі:

графічний метод;

сімплекс-метод.

Графічний метод відрізняється простотою та ілюстративністю. Але він може бути практично використаний лише при двох змінних х1 та х2, коли система обмежень сумісна (має хоча б одне рішення). Використання методу надано у п. 2.2.2. Узагальнений алгоритм графічного методу такий: будується многокутник допустимих рішень на підставі заданої системи обмежень; знаходяться координати вершин многокутника, як точки пересікання слідів полуплощин обмежень; вершина, в якої цільова функція набуває екстремального значення (максимального або мінімального) відповідає рішенню задачі, а координати цієї вершини дають значення змінних у оптимальному рішенні.

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

Сімплекс-метод є аналітичним методом знаходження рішення задач ЛП.

Сучасна електронно-обчислювальна техніка у вигляді персональних комп'ютерів (ПК) має потужне математичне забезпечення, яке підтримує економіко-математичні задачі. У тому числі це стосується такої програмної системи загального призначення як середовище EXCEL, де можуть бути реалізовані сімплекс-методом задачі ЛП. Таблична програма EXCEL дозволяє зберігати та обробляти інформацію задач ЛП у формі електронних таблиць [22]. За допомогою ПК оптимізаційні економічні задачі ЛП можуть бути реалізованими практично з любою розмірністю. Але при невеликій кількості змінних у задачі ЛП [п < 6...8) вона може бути вирішена сімплекс-методом і ручним способом.

Алгоритм сімплекс-методу докладно описаний у посібнику [22], інформація про що рекомендується для використання у самостійній та науковій роботі студентів. В розглядаємій темі доцільно показати основні етапи алгоритму методу, підкріплені їх геометричною інтерпретацією.

У загальному випадку рішення основноїзадачі ЛП сімплекс-методом складаються з трьох частин:

а)         виключення обмежень-рівнянь, які у вхідних даних розглядаються як 0-рівняння;

б)         знаходження опорного (або допустимого) рішення;

в)         знаходження оптимального рішення.

У кожному з трьох частин використовується такий чисельний спосіб як модифіковані жорданові виключення [22]. Така схематизована операція складається із переміни ролями залежної змінної уг та незалежної хв в системі лінійних обмежень за певними правилами.

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

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

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

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

3.2.2. Двійчасті задачі ЛП та їх економічна інтерпретація

 

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

Нижче наведемо економіко-математичні моделі прямої основної та двійчастої задач ЛП. Розглянемо випадок обмежень у вигляді нерівностей.

 

Пряма задача:            Двійчаста задача:

n m

Z = XPjxj — max;      W = Xbiui — min; (3.11)

j=1 i=1

n m

Xayxj bi (i = 1-m);    Xaijui — pj (j=1-n); (3.12.)

j=1       i=1

xj 0 (j = 1...n);           ut 0 (і = 1...m), (3.13)

де W цільова функція двійчастої задачі; ui змінні у цій задачі.

Двійчаста задача може бути получена з основної за такими правилами:

праві частини обмежень основної задачі bu b2, bm виступають коефіцієнтами цільової функції двійчастої задачі, а коефіцієнти цільової функції основної задачі p1t p2, pn є правими частинами обмежень двійчастої задачі;

матриця коефіцієнтів обмежень двійчастої задачі A може бути полученою транспонуванням матриці коефіцієнтів основної задачі А;

знаки обмежень двійчастої задачі j—) протилежні

знакам обмежень основної задачі (-);

максимізація цільової функції Z основної задачі змінюється на мінімізацію цільової функції W двійчастої задачі;

кількість обмежень однієї задачі співпадає з кількістю змінних у другій задачі;

6) умови невід'ємності змінних зберігаються в обох задачах.

Вирішуя основну задачу ЛП, ми одночасно вирішуємо двійчасту їй задачу і навпаки. При цьому максимум цільової функції основної задачі Z співпадає зі значенням мінімума цільової функції двійчастої задачі Ж. Рішення обох задач проводиться сімплекс-методом, хоча існує і другий шлях вирішення двійчастих задач з використанням двійчастого сімплекс-методу, який описаний у спеціальній літературі.

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

У прямій задачі ЛП потрібно було знайти кількість випускаємої продукції кожного виду ху (у=1..м) при наявності обмежених ресурсів Ьі (1=1..ж), щоб підприємство отримало максимальний прибуток 2тах від реалізації цієї продукції.

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

Змінними у двійчастій задачі иі (ї=...т) позначимо ціни за одиницю ресурсів г-го виду. Тоді кожна складова прибутку у обмеженнях (3.12) аіуЧі може розглядатися як прибуток від реалізації г-го виду ресурсів, який пішов би на виготовлення у-го виду одиниці продукції. Ліва частина обмежень (3.12) це прибуток від реалізації всіх т ресурсів, які призначені для виготовлення одиниці у-го виду продукції. Ясно, що підприємство не стане продавати ресурси, якщо прибуток від цієй продажі буде менше прибутку ру від переробки ресурсів на виготовлення одиниці продукції у-го виду. Цей факт ілюструється у цілому кожним обмеженням (3.12) двійчастої задачі. З другої сторони, загальна вартість усіх запасів ресурсів, які  організація  хоче  придбати,   складає   IV.   В результаті формується економіко-математична модель двійчастої задачі за формулами (3.11)-(3.13).

 

3.2..3. Методи вирішення транспортної задачі та її моделі

 

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

Введемо позначення: ху змінні, які підлягають розшуку та виражають кількість вантажу, який перевозиться від г-го постачальника до у-го споживача (і=1...т, у=1...гі); Су вартість перевезення одиниці вантажу від г-го постачальника до у-го споживача; аі кількість одиниць вантажу у г-го постачальника; Ьу кількість одиниць вантажу, яка потрібна у-му споживачу.

На практиці при перевезенні вантажів може виникнути одна з трьох ситуацій.

1. Кількість одиниць вантажу у постачальників відповідає попиту з боку споживачів, що відображається в умові балансу

т п

а, =Х Ьу. (3.14)

і=1       у=1

Така економіко-математична модель транспортної задачі називається закритою та з урахуванням умови (3.14) вона має

вид:

тп

г = ХХС,уХу   тіп; (3.15)

і=1 у =1

пт

XХіу= аі (і = 1...1П); XХіу= Ьу 0 = 1...п)>' (3.16)

у=1 =1

ху > 0 {і = 1...т,у = 1...п). (3.17)

Дана транспортна задача є збалансованою.

У наведених виразах формула (3.15) відповідає цільовій функції з мінімізації транспортних витрат. Формули (3.16) є обмеженнями задачі: перша формула характеризує те, що весь вантаж від постачальників має бути вивезеним; друга формула відтворює той факт, що попит споживачів задовільнений. Формули (3.17) є умовою невід'ємності змінних.

Кількість вантажу у постачальників більше попиту у ньому з боку споживачів:

т п

а, >ХЬ}. (3.18)

і=і      і =і

Це означатиме, що частина вантажу у постачальників залишиться, а споживачі отримають весь потрібний їм вантаж. Тому знак у першому обмеженню (3.16) зміниться з "=" на "<". Інші формули розглянутої моделі (3.15)-(3.17) залишаться такими ж.

Кількість вантажу у постачальників менше попиту в ньому у споживачів:

тп

а, <ХЬі. (3.19)

і=1       і=1

Це означатиме, що кожен постачальник увесь свій вантаж вивезе, а частина споживачів отримає вантажу менше відповідної кількості. Тому друге обмеження у формулах (3.16) буде мати знак " <". Інші формули моделі (3.15)-(3.17) залишаться без зміни.

Економіко-математичні моделі у ситуаціях 2і 3 називаються відкритими, а самі задачі незбалансованими.

У всіх трьох розглянутих моделях кількість основних змінних складає т*п, а кількість обмежень (т+п).

Найбільш простою та часто використовуємою є закрита модель (3.15)-(3.17). З особливостями реалізації відкритих моделей можна познайомитися у спеціальній літературі [22].

До методів реалізації транспортної задачі можуть бути віднесені методи з двох груп:

спеціальні методи вирішення транспортної задачі;

сімплекс-метод.

До спеціальних методів вирішення транспортної задачі відносяться такі: метод північно-західного кута; метод мінімального елементу; метод потенціалів. Вони докладно описані у посібнику [10] і призначені, в основному, для

реалізації ручним способом при невеликої кількості постачальників (m) та споживачів (n).

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