Штучна цільова функція при цьому має вигляд

W = x₅ + x₆ ® min.

Для того, щоб скласти початкову симплексну таблицю для розв’язування допоміжної задачі – пошуку мінімуму функції W, треба отримати рівняння для функції W, у якому коефіцієнти при базисних змінних (x₅ і x₆) дорівнюють нулю. Для цього від рівняння

- W + x₅ + x₆ = 0

треба послідовно відняти рівняння

4x₁ + 5x₂ + x₅ = 20,

якому відповідає базисна (штучна) змінна x₅, і

3x₁ + 8x₂ - x₄ + x₆ = 24,

якому відповідає базисна (штучна) змінна x₆.

Перетворення виразу для цільової функції W мають вигляд

- W + x₅ + x₆ = 0

4x₁ + 5x₂ + x₅ = 20

- W - 4x₁ - 5x₂ + x₆ = -20

3x₁ + 8x₂ - x₄ + x₆ = 24

- W - 7x₁ - 13x₂ + x₄ = - 44

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

Табл.7.1.

Баз. змінні	Праві част.	x1	x2	x3	x4	x5	x6
x3
x5
x6					-1
-F
-W	-44	-7	-13
x3		13/8			1/8
x5		17/8			5/8
x2		3/8			-1/8
-F	-15	41/8			5/8
-W	-5	-17/8			-5/8
x3	20/17				-6/17
x1	40/17				5/17
x2	36/17				-4/17
-F	-460/17				-15/17
-W

Для того, щоб після визначення мінімуму функції W, отримати приведену симплекс-таблицю відносно функції F будемо на етапі розв’язування допоміжної задачі виконувати симплексні перетворення над матрицею, що містить два індексних рядка – для F і для W, але ведучий стовпчик визначатимемо за рядком для W.

Остання симплекс-таблиця визначає опорний план для вихідної задачі:

x₁ = 40/17, x₂ = 36/17, x₃ = 20/17, x₄ = 0. Оскільки індексний рядок для функції F не містить додатніх коефіцієнтів, цей опорний план – оптимальний. Якби індексний рядок містив додатні коефіцієнти, то треба було продовжити застосування симплекс-методу.

М-метод

Застосування методу штучної цільової функції призводить до того, що задача лінійного програмування розв’язується у два етапи: спочатку розв’язується допоміжна задача, а потім – основна. Сумістити обидва етапи дозволяє так званий М-метод.

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

-M x_j

j Ni

при пошуку максимуму, і виразу

M x_j

j Ni

при пошуку мінімуму.

У цих виразах N_i - множина індексів штучних змінних, а M – велике абстрактне число, що більше будь-якого конкретного.

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

F = 7x₁ + 5x₂ - Mx₅ - Mx₆ ® max,

2x₁ + x₂ + x₃ = 8,

4x₁ + 5x₂ + + x₅ = 20,

3x₁ + 8x₂ -x₄ +x₆ = 24,

x₁, …, x₆ ³ 0.

Запобігання зацикленню симплекс-методу

При застосуванні симплекс-методу поточний опорний план може виявитися виродженим. У цьому випадку існує базисна змінна (можливо і не одна), припустимо, x_r, що відповідає рядку s і дорівнює нулю. Це означає, що у поточній симплекс-таблиці b^’_s = 0. Оскільки симплексне відношення є невід’ємною величиною, то у рядку s воно приймає мінімальне значення, і може статися так, що змінна x_r, буде вилучена з числа базисних, а замість неї уведена в число базисних змінна x_t. Змінна x_t очевидно буде мати нульове значення, і наступний опорний план, як і попередній, виявляється виродженим. На наступній ітерації замість x_t може бути уведена у число базисних змінна x_r, і у результаті виникає зациклення – відбувається повернення до опорного плану, що відповідає одній з попередніх ітерацій. Зациклення може виникнути і у випадку, коли поточний опорний план має декілька нульових базисних змінних, і повторення опорного плану відбувається через декілька ітерацій. Тому необхідні спеціальні засоби запобігання виникненню циклів у послідовності опорних планів, що проглядаються при реалізації симплекс-методу.

Рядки-обмеження довільної симплекс-таблиці належать до множини векторів n+1-вимірного лінійного векторного простору Rⁿ⁺¹. Кожний такий рядок a_i можна уявити у вигляді a_i = (a_i0, a_i1, …,a_in), де a_i0 – права частина обмеження.

Будемо говорити, що довільний вектор a = (a₀, a₁, …, a_n) Rⁿ⁺¹ лексикографічно більше нульового вектора 0 Rⁿ⁺¹ (і позначати це як a 0), якщо a 0, і перша ненульова координата вектора a додатня, тобто a_q > 0, де q = min {j | a_j 0}.

Вектор a лексикографічно більше вектора b (a b), якщо a – b 0. Іншими словами a b, якщо a b, і a_q > b_q, де q = min {j | a_j b_j}.

Відмітемо дві важливі властивості відношення:

а) для будь-яких двох векторів a, b Rⁿ⁺¹ має місце одна з трьох можливостей: a b, a = b, b a;

б) відношення транзитивне, тобто якщо a b і b c, то a c.

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

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

Будемо вважати, що початковий опорний план x⁰ статечно допустимий, бо цього завжди можна досягти вибором порядку змінних.

Нехай на поточній ітерації визначено ведучий стовпець s. Для визначення ведучого рядка будемо розглядати рядки поточної симплекс-таблиці, що містять додатні елементи у стовпчику s. Кожний такий рядок a^’_r поділемо на елемент a^’_rs, розташований у цьому рядку і у ведучому стовпчику. Ведучий рядок визначимо як той, якому відповідає лексикографічно найменше значення результату ділення.

Якщо позначити через L множину рядків з додатнім елементом у ведучому стовпчику, а через i шуканий номер ведучого рядка, то правило вибору ведучого рядка приймає вигляд

a^’_r /a^’_rs a^’_i /a^’_is, i,r L, i r. (*)

Якщо ведучий стовпець містить додатній елемент, за правилом (*) завжди однозначно визначається ведучий рядок. Дійсно, якби існували два різні рядки з номерами p і q такі, що a^’_p /a^’_ps = a^’_q /a^’_qs, це б суперечило лінійній незалежності рядків-обмежень симплекс-таблиці.

Теорема 7.1 (Про властивість статечно допустимого опорного плану) Якщо поточний опорний план статечно допустимий, і вибір ведучого рядка здійснюється за правилом (*), то наступний опорний план статечно допустимий, і індексний рядок наступної симплекс-таблиці лексикографічно більше індексного рядка поточної симплекс-таблиці.

Доведення. Оскільки ведучий елемент a^’_is > 0, то ведучий рядок після симплексного перетворення більше нуля: a^’’_i = a^’_i /a^’_is 0.

Якщо індекс r (r i) такий, що a^’_rs £ 0, то r-й рядок після симплексного перетворення лексикографічно більше нуля

a^’’_r = a^’_r - a^’_rs a^’_i /a^’_is 0,

бо - a^’_rs ³ 0, a^’_i /a^’_is 0 і сума двох векторів a^’_r та -a^’_rs a^’_i /a^’_is, що лексикографічно більше нуля, є вектор, що також лексикографічно більше нуля.

Якщо індекс r (r i) такий, що a^’_rs > 0, то

a^’_r /a^’_rs a^’_i /a^’_is.

Звідки маємо

a^’_r a^’_rs a^’_i /a^’_is, або a^’’_r = a^’_r - a^’_rs a^’_i /a^’_is 0.

При цьому індексний рядок перетворюється за формулою

c^’’ = c^’ - c^’_s a^’_i /a^’_is,

і оскільки при пошуку мінімуму c^’_s < 0,

- c^’_s a^’_i /a^’_is 0, або c^’’ c^’.

Цим і завершується доведення теореми.

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

Доведення. Якщо застосування симплекс-методу починається зі статечно допустимого плану, то на кожній ітерації утворюється статечно допустимий план. Припустимо, що має місце зациклення. Тоді послідовність отриманих опорних планів можна уявити у вигляді x⁰, x¹, …, x^p, …, x^q, …, x^p, …. Тоді згідно з теоремою 8.1 x⁰ x¹ … x^p … x^q … x^p …, або x^p x^p, що суперечить властивості а) відношення “ ”. Цим завершується доведення.

Дата добавления: 2014-01-13