2.1.1. Симплекс-метод


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 

Загрузка...

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

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

Алгоритм симплекс-методу

1.         Знайти початковий базис і пов'язані з ним допустимі розв'язки.

2.         Обчислити симплекс-різниці для кожної змінної, які не вхо-дять в базовий розв'язок, за формулою:

Якщо всі  Д. >0, то процес розв'язування задачі закінчено.

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

Якщо серед A . є від'ємні, то виконується наступний крок.

3.         З’ясувати, чи є хоча б одна оцінка Ау<0, для якої всі

%щ < 0    (к = 1,2,..., т).

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

4.         Вибрати найменшу з Д. <0 (нехай це буде As), обчислити

відношення 0^ = —— для всіх к, для яких хь > 0 і знайти мініма-

хь льне 3 цих відношень.

Нехай min   —— = 0,.

хь>0       х,

KS

5.         Здійснити перехід до нового опорного розв'язку, базис яко-

го одержують заміною х1 змінною xs.

Для запису формул перерахунку симплекс-таблиці введемо додаткові визначення.

Змінна, якій відповідає найменше Ау <0, визначає головний стовпчик (в нашому алгоритмі це s).

Змінна, яку виводять з базисного розв'язку, визначає головний рядок (в нашому алгоритмі це /).

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

Розширену матрицю умов після к -ої ітерації позначимо

 

p

і запишемо формули для побудови А(рк+1) - - розширеної матриці для (к +1) -ої ітерації:

елементи головного рядка /

(к)

(к+і) _   ь_       / = о, 1   ..., п ,           (2.4)

a

ік}

елементи головного стовпчика

а(*;1) =0;    / = йп,   j Ф s,   af;X) = 1,           (2.5)

всі інші елементи матриці А(к+1) розраховуються за формулою:

 

a

h

ш.

Реалізація симплекс-методу розглянута в розділі 3.1 стосовно задачі оптимального розподілу виробничих ресурсів [12].

Досить часто при розв'язуванні задачі ЛП область пошуку до-пустимих розв'язків G маєвигляд:

п                    

Т*аііхі = & j ■>   j = hm ■      (2-7)

1=1

Необхідно знайти

хі > 0,   і = \,п, (2-8)

при яких максимізується функція цілі

п

f(x) = Yjcixi ■  (2-9)

і=\

Для застосування симплекс-методу в систему обмежень (2.7)

вводять штучні змінні у. > 0,   j = 1, т , які включають в цільову

функцію з коефіцієнтами М, де М— деяке досить велике позити-вне число. Задача (2.7)—(2.9) приймає вигляд:

п                    

Xаііхі + УІ — bj,j = \,tn,         (2.7')

г=і

хі > 0,   і = \,п,   уj > 0,    j = \,т,         (2-8')

F(x,y) = ХСіХ! — М^у. —> max .(2.9')

Роль Мінтуїтивно зрозуміла: додатки з позитивними уs істо-тно зменшують значення цільової функції, а тому, якщо задача (2.7')—(2.9') має допустимі розв'язки, в яких всі уj дорівнюють

нулеві, то в оптимальному розв'язку при великих Мвсі уj будуть дорівнювати нулеві. Але, якщо в такому розв'язку відкинути

штучні змінні, то одержимо допустимии розв язок початкової за-дачі (2.7')—(2.9'), який і буде її оптимальним розв'язком [19].

Реалізація цього методу (який одержав назву М-методу, або метод штучного базису) показана на прикладі розв'язку задачі визначення оптимальних технологічних способів виробництва в розділі 3.2.