Прийняття управлінських рішень - Петруня Ю.Є. - 4.3. Задачі лінійного програмування

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

Загальну задачу лінійного програмування визначимо так: потрібно

знайти значення х*,х*,...,х* змінних x1,x2,...,xn, за яких досягається максимум (мінімум) функції

z = 2 cjxj

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

п -

2 aijXj < Ьі , і = 1,77?!;

j=1

2 ауХ^ > Ьі , і = т1 +1, т2;

o j=1

п -

2 ауХ^ = Ьі , і = т2 +1, т;

;=1 _

хі > 0, j = 1, п < п),

де с-, а", Ьі - задані дійсні числа.

7 У 1

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

Один з варіантів задачі лінійного програмування взято за стандарт - канонічну форму задачі лінійного програмування, тобто коли в системі обмежень усі Ьі (і = 1, т) невід'ємні: всі обмеження є рівностями, а п1 = п. Будь-яку задачу лінійного програмування можна звести до канонічного вигляду. Якщо якесь Ьі від'ємне, то, помноживши і-те обмеження на (- 1), дістанемо у правій частині відповідної рівності додатне значення. Коли і-те обмеження має вигляд нерівності аі1 х1 + аі2 +... + аіпхп < Ьі, то її завжди можна звести до рівності, ввівши додаткову змінну хп+1 > 0 : аі1 х1 + аі2 +... + аіпхп + хп+1 = Ьі.

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

Припустімо, що задача лінійного програмування має такий вигляд:

і = с1 х1 + с2 х2 -" тах(тіп):

ацх1 ~т~ х2 - Ь1:

х1 > 0, х2 > 0.

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

1. На основі обмежень задачі в площині змінних Ох1 х2 будуємо

прямі, рівняння яких мають вигляд аі1 х1 + аі2х2 - Ьі = 0, і = 1, т.

2. Визначаємо ту частину площини, в якій виконується кожне з обмежень задачі.

3. Знаходимо багатокутник розв'язків задачі.

4. Будуємо вектор gradz = ^-i = cli + c2j, що задає на-

dxl <3x2

прям зростання цільової функції.

5. Проводимо пряму cl xl + c2 x2 = const, перпендикулярно до вектора grad z.

6. Рухаючи пряму clxl + c2x2 = const у напрямку вектора grad z (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв'язків, де цільова функція набуває екстремального значення.

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

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

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

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

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

1. Модель практичної задачі лінійного програмування звести до канонічного вигляду за умови пошуку найбільшого значення цільової функції.

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

3. За наявного опорного плану зобразити базисні змінні та цільову функцію через вільні змінні. Записати симплекс-таблицю.

4. Склавши симплекс-таблицю, дослідити наявний опорний план: а) якщо в рядку симплекс-таблиці, що містить коефіцієнти цільової

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

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

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