4.3. Задачі лінійного програмування

магниевый скраб beletage

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

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

знайти значення x1,x*,...,xn змінних x1,x2,...,xn, за яких досягається

максимум (мінімум) функції

Z = 2 cjxjj=1

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

Zaijx, ^bi, і =1 щ;

j=1

2 ацХj ^ bt, i = m1 +1, m2

j=1

2 ayXj = bt, i = m2 +1, m;

j=1      

де Cj , ау , bi

Xj > 0, j = 1, n1 (n1 < n),

задані дійсні числа.

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

Один з варіантів задачі лінійного програмування взято за стандарт— канонічну форму задачі лінійного програмування, тобто коли в сис-темі обмежень усі bt (і = 1, m) невід'ємні; всі обмеження є рівностями,a n1 = n. Будь-яку задачу лінійного програмування можна звести доканонічного вигляду. Якщо якесь bt від'ємне, то, помноживши і-теобмеження на (— 1), дістанемо у правій частині відповідної рівностідодатне значення. Коли i-те обмеження має вигляд нерівностіai1 x1 + ai2 +... + ainxn < bt, то її завжди можна звести до рівності, ввів-ши додаткову змінну xn+1 > 0 : ai1 x1 + ai2 +... + ainxn + xn+1 = bi.

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

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

z = c1 x1 + c2x2 ^ max(min);

a 11 x1 a12x2 — b1;

am1 x1 + am2x2 ^ bm

x1 > 0, x2 > 0.

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

На основі обмежень задачі в площині змінних Ox1 x2 будуємо

прямі, рівняння яких мають вигляд ai1 x1 + ai2x2 - bt = 0, i = 1, m.

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

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

Будуємо вектор grad z = +——j = c1i + c2 j, що задає на-

dx1 dx2

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

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

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

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

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

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

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

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

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

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

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

Склавши симплекс-таблицю, дослідити наявний опорний план:

а) якщо в рядку симплекс-таблиці, що містить коефіцієнти цільової

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

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

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