Змістовний опис симплекс-методу розв’язання задач ЛП

Нехай задача ЛП має оптимальний розв`язок. З геометричної точки зору це означає, що існує вершина багатокутника розв`язків, де лінійна функція досягає оптимального значення. Кожній вершині багатокутника відповідає опорний план. А кожний опорний план визначається системою m лінійно незалежних векторів, що містяться серед n векторів A₁, A₂,..., A_n системи обмежень. Щоб знайти оптимальний план, досить розглянути лише опорні плани. Їх кількість не перевищує Для великих значень m і n знайти серед них оптимальний простим перебором дуже важко. Тому необхідно мати такий аналітичний метод, що дає можливість цілеспрямовано розглядати опорні плани. Таким методом є симплексний метод. Виходячи з одного (початкового) опорного плану, симплексний метод забезпечує побудову нового опорного плану, що надає лінійній функції менші значення у порівнянні з попереднім планом. Цей процес продовжується поки не буде знайдено оптимальний план.

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

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

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

Знаходження початкового опорного плану

Щоб застосувати симплекс-метод для знаходження оптимального розв’язку задачі лінійного програмування, треба знайти відправну точку, тобто початковий опорний план. Якщо обмеження задачі ЛП задано у канонічному вигляді

AX = A₀, A₀ ³ 0, X ³ 0

і серед векторів A₁, A₂,..., A_n є одиничний базис, то початковим опорним планом буде вектор X = (b₁, b₂,..., b_m, 0,..., 0).

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

Якщо перше рівняння системи поділити на три, а друге – на два, то дістанемо систему:

Тут вектори A₁, A₂ i A₃ утворюють одиничний базис і всі вільні члени додатні. Поклавши, що x₄ = x₅ = x₆ = 0, знайдемо опорний план, який визначається як X = (2, 4, 5, 0, 0, 0).

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

Розв’язання. Застосуємо метод повного виключення Гауса. Результати обчислень наведено у табл. 2.1, де головний елемент узято у рамку. З таблиці видно, що після третьої ітерації перетворень системи методом повного виключення дістали одиничний базис: A₁, A₂, A₅ йому відповідає план X = (20, 6, 0, 0, 26).

Таблиця 2.1

Ітерація	A1	A2	A3	A4	A5	A0	S
					-1
					-1
			-1		-1
					-1
		-4	-1
			-2		-1	-6	-7

Якщо обмеження задачі ЛП задано у вигляді нерівностей:

A₁x₁ + A₂x₂ +... + A_nx_n £ A₀, X ³ 0, A₀ ³ 0,

то, додавши до лівої частини кожної нерівності за невід’ємною змінною x_n+1, x_n+2,..., x_n+m, дістанемо розширену систему лінійних обмежень

A₁x₁ +... + A_nx_n + A_n+1x_n+1 +... + A_n+mx_n+m = A₀, X ³ 0, A₀ ³ 0.

Змінні x_n+1, x_n+2,..., x_n+m називають додатковими змінними. У лінійну функцію вони входять з нульовими коефіцієнтами. Отже, початкова задача лінійного програмування перетворилась у розширену: знайти оптимальне значення лінійної функції

F = c₁x₁ + c₂x₂ +...+ c_nx_n + 0 * x_n+1 +...+ 0 * x_n+m

за обмежень (1.5.3). Додаткові вектори A_n+1, A_n+2,..., A_n+m утворюють одиничний базис m -вимірного векторного простору, а вектор X=(x₁=0;...; x_m=0; x_m+1=b₁;...; x_n+m = b_n+m) є опорним планом розширеної задачі.

Зазначимо, що розв’язок розширеної задачі, якщо він існує, буде також розв’язком початкової задачі. Якщо ж розширена задача розв’язку не має, то не має розв`язку і вихідна задача.

Застосовуючи симплекс-метод до розширеної задачі, поступово замінюють у системі базисних векторів додаткові вектори A_n+1, A_n+2,..., A_n+m векторами початкової системи обмежень. Якщо лінійна функція досягла свого екстремуму, а в системі базисних векторів є хоча б один додатковий вектор, наприклад A_n+i, то це означає, що i -те обмеження в початковій задачі має смисл строгої нерівності. Отже, початкова задача матиме оптимальний розв’язок (якщо його має розширена задача) і тоді, коли не всі додаткові вектори виключено із базису.

Часто, виділивши в системі обмежень одиничний базис і відповідний йому базисний розв’язок можна побачити, що знайдений розв’язок не є опорним планом системи обмежень, бо серед його змінних є і від’ємні. Для цілеспрямованого пошуку опорного плану треба від знайденого одиничного базису перейти до іншого. Для цього застосовують метод симплексного перетворення. Оскільки симплексні перетворення виконують над векторами A₁, A₂,..., A_n, A₀ системи обмежень, то ці вектори зведемо в табл. 2.2.

Таблиця 2.2

Рядки	A0	A1	A2	...	Aj	...	An	S	q
	b1	a11	a12	...	a1j	...	a1n
	b2	a21	a22	...	a2j	...	a2n
...	...	...	...	...	...	...	...	...	...
I	bi	ai1	ai2	...	aij	...	ain
...	...	...	...	...	...	...	...	...	...
M	bm	am1	am2	...	amj	...	amn

Нехай вектор A₀ ³ 0, тобто всі b_i ³ 0, (i = 1, 2,..., m). Цього можна досягти, помноживши рівняння з від’ємними членами на -1. Тепер у табл. 2.2 виділимо одиничний базис, не порушуючи невід’ємність компонент вектора A₀. Зробити це можна за таким алгоритмом.

1. З неодиничних векторів A₁, A₂,..., A_n взяти той, у якого є хоча б один додатний елемент. Нехай таким вектором буде A_j. Якщо такого вектора в таблиці немає, то це означає, що система обмежень несумісна і процес симплексного перетворення завершено.

2. Знайти відношення q _i елементів вектора A₀ до відповідних додатних елементів вектора A_j, записати їх у відповідному рядку стовпця q і взяти з них найменше. Нехай таким буде деяке відношення q = b_i / a_ij. Тоді елемент a_ij – головний, а рядок і стовпець таблиці, на перетині яких лежить a_ij, відповідно годовні рядок і стовпець.

3. Коефіцієнти головного рядка (крім q _i ) таблиці поділити на головний елемент і записати у відповідному рядку нової таблиці.

4. Елементи кожного наступного рядка нової таблиці дістають шляхом додавання відповідного рядка вихідної таблиці і рядка, записаного в п. 3, помноженого на таке число, щоб у головному стовпці при додаванні дістати нулі. На цьому заповнення нової таблиці завершується і перетворення нової таблиці починаються з п. 1.

Такі перетворення продовжуються доти, поки не буде виділено одиничний базис або ж не буде встановлено, що система обмежень несумісна. Стовпець S призначений для контролю обчислень, його елементи обчислюють так само, як і за методом повного виключення Гауса.

Приклад 2.5. Знайти початковий опорний план для системи обмежень

Розв’язання. Записуємо коефіцієнти системи обмежень у табл.2.3. За головний візьмемо перший стовпець, оскільки вектор A₁ має додатні компоненти. Знайдемо відношення q₁=6/1=6 i q₃=2. Менше з них знаходиться у третьому рядку. Отже, головний елемент a₃₁=1.

Над елементами вихідної системи виконаємо симплексні перетворення. Після першої ітерації перетворень одиничними є вектори A₁ і A₅. Намагаючись знайти базис з векторів A₂, A₃, A₄, візьмемо A₂, що має додатний елемент a₂₂ =2, який і буде головним. Виконавши симплексні перетворення, після другої ітерації маємо одиничний базис A₁, A₂, A₅ і опорний план X = (2; 2; 0; 0; 6), що йому відповідає.

Таблиця 2.3

Ітерація	Рядок	A0	A1	A2	A3	A4	A5	S	q
				-1		-1
					-1	-3
				-1	-1	-2
					-1	-3
					-3/2	-7/2
					-1/2	-3/2

Знаходження оптимального плану

Розглянемо симплекс-метод знаходження оптимального плану на прикладі задачі ЛП:

F = c₁x₁ + c₂x₂ +... + c_nx_n ® min

за обмежень

де

x_j 0, (j = 1, 2,...,n).

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

A₁x₁ + A₂x₂ +... + A_mx_m + A_m+1x_m+1 +...+A_nx_n = A₀, X 0,

де

, ,..., ,

,

,

.

Вектори A₁, A₂,..., A_m – лінійнонезалежні одиничні вектори m -ви­мір­ного простору, і тому вони утворюють базис цього простору. За базисні змінні в системі обмежень виберемо x₁, x₂,..., x_m, а вільні змінні x_m+1,..., x_n прирівнюємо до нуля. З урахуванням того, що b_i ³ 0 (i = 1,..., m), знаходимо початковий план

X₀ = (x₁ = b₁; x₂ = b₂;...; x_m = b_m; x_m+1 = 0;...; x_n = 0). (2.9)

Йому відповідає лінійна комбінація

x₁A₁ + x₂A₂ +... + x_mA_m = A₀ , (2.10)

у якій вектори A₁, A₂,..., A_m лінійно незалежні. Отже, побудований початковий план є опорним, що надає значення лінійній функції

F(X₀) = c₁x₁ + c₂x₂ +... + c_mx_m = f₀, (2.11)

яке залежить тільки лише від значень m перших компонент вектора C. Оскільки оптимальний план належить до опорних, то й оптимальне значення лінійної функції залежатиме від відповідних компонент вектора C.

Розглянемо тепер, яким чином, виходячи з початкового опорного плану (2.9), можна побудувати інший опорний план, який надасть лінійній функції значення меншого, ніж попередній план. Початковий опорний план визначається базисними векторами A₁, A₂,..., A_m.

Побудувати наступний опорний план, виходячи з початкового, можна завдяки переходу від базису A₁, A₂,..., A_m до нового базису. Такий перехід здійснюється за допомогою вибору вектора, який вводять у базис, і вибору вектора, який виводять з нього. Знайдемо критерій вибору таких векторів.

Оскільки вектори A₁, A₂,..., A_m утворюють базис m -вимірного простору, то будь-який вектор системи A₁, A₂,..., A_n однозначно лінійно визначається через базисні

A_j = x_1jA₁ + x_2jA₂ +... + x_mjA_m, j = 1, 2 ,...,n. (2.12)

Зауважимо, що коефіцієнти x_ij (i = 1, 2 ,..., m) є компонентами вектора A_j в базисі A₁, A₂,..., A_m. У виразі (2.12) вектора A_j відповідає єдине значення лінійної функції

f_j = c₁x_1j + c₂x_2j +... + c_mx_mj, j = 1, 2 ,...,n. (2.13)

де c_i (i = 1, 2 ,..., m) – коефіцієнти лінійної функції, що відповідають базисним векторам A_i (i = 1, 2 ,..., m).

Значення f_j знайдемо, якщо у вираз лінійної функції замість змінних підставимо відповідні коефіцієнти подання j -го вектора через базисні вектори. Нехай для деякого вектора, що не входить у базис, наприклад, A_k (k > m), хоча б один з коефіцієнтів x_ik у виразі

x_1k A₁ + x_2k A₂ +... + x_mk A_m = A_k (2.14)

є додатним. Виразу (2.14) відповідає значення лінійної функції

c₁x_1k + c₂x_2k +... + c_mx_mk = f_k. (2.15)

Задамо деяке, поки що невідоме додатне число q. Помножимо на нього обидві частини рівностей (2.14) і (2.15) і результати віднімемо від (2.10) і (2.11) відповідно:

(x₁ - q x_1k) A₁ + (x₂ - q x_2k) A₂ +... + (x_m - q x_mk) A_m + q A_k = A₀,

(x₁ - q x_1k) c₁ + (x₂ - q x_2k) c₂ +... + (x_m - q x_mk) c_m = f₀ - q _fk. (2.16)

В останній рівності до обох частин додамо q _ck:

(x₁ - q x_1k) c₁ + (x₂ - q x_2k) c₂ +... + (x_m - q x_mk) c_m + q c_k = f₀ - q (f_k - c_k). (2.17)

Лінійній комбінації відповідає новий план

X₁ = (x₁ - q x_1k; x₂ - q x_2k;...; x_m - q x_mk ; 0 ,..., q,..., 0),

якщо його коефіцієнти невід’ємні. Ті компоненти вектора X₁, до яких входять недодатні q x_ik, будуть невід’ємними, бо q > 0. Компоненти вектора X₁ з додатними x_ik (i = 1, 2 ,..., m) будуть невід`ємними, якщо

, (2.18)

де мінімум береться серед тих i, для яких x_ik > 0. Отже, під час виконання даної умови вектор X₁ буде опорним планом. Опорний план не може мати m+1 додатних компонент. Тому в плані X₁ треба хоча б одну з компонент перетворити в нуль. Це можна зробити, якщо q вибрати так:

. (2.19)

Оскільки розглядається невироджена задача, тобто всі її опорні плани містять рівно m додатних компонент, то мінімум в (2.19) досягатиметься для єдиного значення i. Нехай i = l (1 £ l ³ m). Тоді для q ₀ = x_l / x_lk відповідні коефіцієнт виразу (2.16) і компонента плану X₁ перетворяться в нуль. Підставивши значення q₀ в план X₁, дістанемо лінійну комбінацію

x’₁A₁ +... + x’_l-1A_l-1 + x’_l+1A_l+1 +... +x’_mA_m + x’_kA_k = A₀ ,

і відповідний їй опорний план

X₁ = (x’₁,..., x’_l-1, 0,x’_l+1,..., x’_m, 0 ,..., x’_k,..., 0),

де

(2.20)

План X₁ надає лінійній функції F значення f₀ - q ₀ (f_k - c_k).

Отже, дістали новий опорний план, базис якого складається з векторів A₁, A₂,..., A_l-1, A_l+1,..., A_m, A_k. Новий план X₁ надає лінійній функції F значення F(X₁) = f₀ - q₀ (f_k - c_k), яке буде менше від F (X₀), якщо f_k - c_k > 0. Величина різниці f_k - c_k називається оцінкою плану. Якщо для деякого вектора A_k оцінка плану f_k - c_k > 0, то план X₀ не є оптимальним і можна побудувати новий план X₁ такий, що F (X₁) <F (X₀).

План X₁ побудовано завдяки заміні вектора з початкового базису новим вектором. Критерій заміни векторів сформулюємо таким чином:

- у новий базис вводять вектор A_k, для якого оцінка плану додатна;

- із старого базису виводять той вектор A_i, для якого відношення x_i / x_ik з додатними x_ik набуває найменшого значення.

Процес заміни векторів продовжують доти, поки всі оцінки плану не стануть від’ємними або нулями, або для деякої оцінки f_j-c_j >0 усі x_ij стануть недодатними, що означає, що побудований план є оптимальним.

Якщо на деякому кроці заміни для будь-якого j оцінка f_j - c_j > 0 і усі x_ij £ 0, то це означає, що лінійна функція не обмежена знизу на багатокутнику розв’язків і її значення може бути як завгодно малим. Зазначимо, що коли є кілька додатних оцінок плану, то вибирають найбільшу з них і той вектор, який відповідає цій найбільшій оцінці, вводять у новий базис.

Якщо є кілька однакових найбільших оцінок, то можна вводити в новий базис будь-який з векторів, що відповідає цим найбільшим оцінкам. Якщо для деякого вектора A_j з додатною оцінкою плану є кілька однакових найменших відношень x_i / x_ij, то з базису можна вивести будь-який з відповідних векторів, однак, при цьому може виникнути явище зациклювання.

Нагадаємо, що компоненти нового плану можна обчислити за формулами (2.20). Для перевірки побудованого плану на оптимальність треба знайти компоненти усіх векторів A_j (j = 1, 2,..., n) у новому базисі. Їх можна обчислити за формулами:

a’_ij = a_ij - a_lj, i ¹ l, (2.21)

a’_ij = a_ij / a_lk, i = l. (2.22)

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

Приклад 2.6. Знайти мінімум функції

F=2x₁+3x₂+x₃+4x₄

за такими обмеженнями:

Розв’язання. Відповідно загальним позначенням маємо

X = (x₁, x₂, x₃, x₄), C = (2; 3; 1; 4),

, , , , .

Система обмежень містить два одиничні лінійно незалежні вектори A₃ і A₄, які утворюють базис двовимірного векторного простору. Тоді вектори A_j (j = 1, 2,..., 4) описуються через базисні

A₀ = x₃A₃ + x₄A₄ = 70 A₃ + 45 A₄,

A₁ = x₃₁A₃ + x₄₁A₄ = 4 A₃ + 2.5 A₄,

A₂ = x₃₂A₃ + x₄₂A₄ = 11 A₃ + 8 A₄,

A₃ = x₃₃A₃ + x₄₃A₄ = 1 *A₃ + 0 *A₄,

A₄ = x₃₄A₃ + x₄₄A₄ = 0 *A₃ + 1 *A₄.

Поклавши у системі обмежень x₁=x₂= 0, дістанемо початковий опорний план X₀ = (0, 0, 70, 45). Значення цільової функції F дорівнює F (X₀) = = 2×0 + 3×0 + + 1×70 + 4×45 = 250. Знайдемо оцінки початкового опорного плану. Для цього обчислимо значення f_j (j = 1,..., 4) за формулою (2.13) як суму добутків компонент вектора Aj на компоненти вектора C, які відповідають базисним векторам

f₁ = 1 × 4 + 4 × 2.5 = 14; f₂ = 1× 11 + 4× 8 = 43;

f₃ = 1×1 + 4 × 0 = 1; f₄ = 1× 0 + 4× 1 = 4.

Тоді оцінки плану визначаться як f₁ - c₁ = 12, f₂ - c₂ = 40, f₃ - c₃ = 0, f₄ - c₄ = 0. Серед них є дві додатні. Більшою є оцінка f₂ - c₂, що відповідає вектору A₂. Отже, його вводимо в базис.

Щоб визначити, який з векторів A₃, A₄ треба вивести з базису, обчислимо відношення x_i / x_i2 (i =3, 4) для додатних x_i2, тобто поділимо компо­нен­ти вектора A₀ на відповідні додатні компоненти вектора A₂: , . Меншим з обчислених відношень є відношення x₄ / x₄₂, яке відповідає вектору A₄. Таким чином, замість вектора A₄ як базис вводимо вектор A₂. Новий базис утворюють вектори A₂ і A₃. У новому базисі вектори Aj (j = 0, 1,..., 4) мають такі вирази:

A₀ = ₂A₂ + ₃A₃,

A₁ = ₂₁A₂ + ₃₁A₃ ,

A₂ = ₂₂A₂ + ₃₂A₃ = A₂ + 0 × A₃,

A₃ = ₂₁A₂ + ₃₁A₃ = A₃ + 0 × A₂,

A₄ = ₂₁A₂ + ₃₁A₃ ,

де _i обчислюються за формулами (2.20), а _ij - згідно з формулами (2.21) і (2.22). Новий опорний план X₁, який визначається базисними векторами A₁ і A₂, має вигляд X₁ = ( 0, ₂, ₃, 0 ). Обчислимо його компоненти: , .

Отже,

, а F (X1) = c 2 2 + c 3 3 = .

Обчислимо тепер компоненти векторів A₁ i A₄ у новому базисі:

, ,

, .

Тепер знаходимо значення f_j (j = 1, 2, 3, 4):

, f₂ = 3× 1+ 1× 0 = 3,

f₃ = 1× 1 + 3× 0 = 1; .

Нарешті, визначимо оцінку плану X₁:

f₁ - c₁ =1 - 2= -1, f₂ - c₂ = 0, f₃ - c₃ = 0, f₄ - c₄ = -5.

Усі оцінки опорного плану X₁ недодатні. Це означає що побудований план є оптимальним, тобто мінімум функції F_min = 25 досягається за планом .