Канонічна форма задачі лінійного програмування. Опорні розв’язки

За означенням 2 задача лінійного програмування поставлена, якщо задані

1) лінійна цільова функція f = ;

2) система обмежень

= b_i (i = 1, 2, …, m₁ ≤ m), ≤ b_i (i = m₁ + 1, …, m), x_j ≥ 0 (j = 1, 2, …, n₁ ≤ n);

3) визначено, до якого типу відноситься дана задача – максимізації або мінімізації.

Зазначимо, що нерівність ≥ b_i можна перетворити у ≤ b_i, змінивши знак у її коефіцієнтів; нерівності x_j ≥ 0 виділені окремо зважаючи на попередні приклади, бо це зручно для конкретних задач. Задачу мінімізації можна звести до задачі максимізації, якщо змінити знак у цільової функції, тобто замість f = (min) написати f = (max). Отже, будь – яку задачу лінійного програмування можна записати так:

f = (max),

= b_i (i = 1, 2, …, m₁ ≤ m),

≤ b_i (i = m₁ + 1, …, m), (1)

x_j ≥ 0 (j = 1, 2, …, n₁ ≤ n).

 

Зокрема, якщо m₁ = 0, то система обмежень складається лише з нерівностей; якщо m₁ = m, то з рівнянь, окрім останньої строки.

Означення 4. Матриця А системи (1) вимірності m × n

 

називається матрицею умов, стовпці А₁, А₂, …, А_n цієї матриці – векторами умов,

 

, ,..., ;

 

а вектор В називається вектором обмежень задачі (1).

Означення 5. Задача лінійного програмування має канонічну форму, якщо всі її змінні невід’ємні, а всі інші умови системи обмежень – рівняння (тобто у (1) m₁ = m, n₁ = n).

Отже, в канонічній формі задача лінійного програмування має вид:

f = (max) або (min),

= b_i (i = 1, 2, …, m)

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

 

У векторній формі систему обмежень задачі (2) можна записати так:

, x_j ≥ 0 (j = 1, 2, …, n),

де А₁, А₂, …, А_n – вектори умов, а В вектор обмежень цієї задачі. Будь – яку задачу лінійного програмування можна звести до канонічної форми. Справді, кожну змінну x_j задачі (1) (n₁ ≤ j ≤ n) замінимо на різницю y_j – z_j двох нових невід’ємних змінних y_j і z_j. Крім того, у нерівностях ≤ b_i (i = m₁ + 1, …, m) системи (1) введемо нові змінні t_i, вважаючи, що + t_i = b_i, звідки t_i ≥ 0 (i = m₁ + 1, …, m).

Приклад. Звести до канонічної задачу: знайти мінімум лінійної функції f = 2х₁ + 3х₂ + х₃ за обмежень

Розв’язання. Введемо в першу нерівність системи змінну х₄ ≥ 0, а в третю – х₅, х₅ ≥ 0:

Змінна х₂ не підпорядкована умові невід’ємності. Тому замінимо цю змінну різницею х₂ = х₆ – х₇, де х₆ ≥ 0, х₇ ≥ 0. Підставивши значення х₂ у цільову функцію і систему обмежень, дістанемо задачу у канонічній формі:

 

f = 2х₁ + 3х₆ – 3х₇ + х₃ (min)

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

Означення 6. 1) Опорним розв’язком задачі лінійного програмування у канонічній формі називають такий допустимий розв’язок її системи обмежень, у якому всі вільні змінні дорівнюють нулю.

2) Опорний розв’язок називають невиродженим, якщо всі його основні змінні додатні, в противному разі опорний розв’язок називають виродженим.

Традиційним є таке еквівалентне

Означення 6′. Опорним розв’язком задачі (2) називається її допустимий розв’язок, якщо вектори умов з номерами його додатних координат утворюють лінійно незалежну систему векторів.

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

Означення 7. Базисом опорного розв’язку називають такий базис векторів умов, який містить всі вектори умов, що відповідають додатним координатам цього розв’язку.

Отже, довільний опорний розв’язок має базис. У невиродженого опорного розв’язку він тільки один, його складають всі вектори умов, що відповідають додатним координатам цього розв’язку; вироджений може мати декілька базисів.

Приклад. В задачі лінійного програмування у канонічній формі

f = 3х₁ + 4х₂ – х₃ + х₄ (min)

α₁ = (0;0;1/2;5/2) і α₂ = (1;0;1;1) є допустимими розв’язками. Водночас вектори умов А₃ = та А₄ = утворюють, очевидно, лінійно незалежну систему векторів і базис векторів умов. Тому α₁ є невиродженим опорним розв’язком цієї задачі, вектори А₃ і А₄ складають базис цього опорного розв’язку. Вектори А₁ = , А₃ = та А₄ = лінійно залежні, тому α₂ не є опорним розв’язком.

Щоби знайти опорний розв’язок достатньо вибрати деякий базис векторів умов задачі так, щоби вектор обмежень В розкладався по ньому з невід’ємними коефіцієнтами. Якщо , , …, – такий базис і В = ∙ + ∙ + … + ∙ , ≥ 0, ≥ 0, …, ≥ 0, то α = (0;…; ;…; ;…; ;…; 0) є опорним розв’язком задачі. Так у прикладі 1/2 ∙ А₃ + 5/2 ∙ А₄ = 1/2 ∙ + 5/2 ∙ = = В.

При розв’язанні конкретних задач ми будемо користуватись означенням 6. Воно зручно також для встановлення геометричного змісту опорного розв’язку. А саме зазначимо, що опорний розв’язок є крайньою точкою опуклої множини Ω допустимих розв’язків задачі лінійного програмування. Справді, нехай опорний розв’язок х є опуклою комбінацією допустимих розв’язків y, z: х = λ ∙ y + μ ∙ z, де у,z є Ω, λ, μ ≥ 0, λ + μ = 1. Оскільки всі координати векторів y і z невід’ємні, а вільні координати вектора х дорівнюють нулю, то ці координати дорівнюють нулю також у векторів y і z. Але тоді вектори y і z є частковими розв’язками тої ж системи лінійних рівнянь, що й х, з тими ж значеннями вільних змінних, звідки х = y = z. Згідно з означенням 3 це й означає, що х є крайньою точкою множини допустимих розв’язків Ω. З іншого боку легко зрозуміти, що будь – який допустимий розв’язок х, що має додатну вільну координату буде опуклою комбінацією деяких допустимих розв’язків y, z ≠ х, тобто лише опорні розв’язки є крайніми точками Ω. Отже, враховуючи висновки попереднього параграфа, отримаємо

Висновки. 1. Опорні розв’язки задачі лінійного програмування у канонічній формі і тільки вони є вершинами множини Ω допустимих розв’язків, яка є многогранником у Rⁿ із скінченим числом вершин. Звідси

2. Якщо множина Ω не пуста, то задача лінійного програмування у канонічній формі має опорний розв’язок, кількість опорних розв’язків скінченна.

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

На цих висновках оснований симплекс – метод – найбільш поширений алгебраїчний метод розв’язування задач лінійного програмування (симплекс – синонім многогранника).

Якщо коротко, то суть його в тому, що достатньо шукати лише опорні розв’язки, а їх скінченна кількість і їх можна знайти методом Гаусса.

 

§4. Симплекс – таблиця

Основним об’єктом у симплекс – методі є симплекс – таблиця. Фактично це розширена матриця системи обмежень задачі лінійного програмування у канонічній формі, до якої додано рівняння нульового рівня цільової функції f = 0. Формально кажучи, для задачі

 

f = (max)

= b_i (i = 1, 2, …, m) (3)

x_j ≥ 0 (j = 1, 2, …, n)

 

симплекс – таблицею називають таку таблицю:

 

x1	x2	…	xn	b
а11 а21 . . . am1	а12 а22 . . . am2	… …   …	a1n a2n . . . amn	b1 b2 . . . bm
c1	c2	…	cn

 

 

Нехай α = (0;…; ;…; ;…; ;…; 0) – деякий опорний розв’язок задачі (3), а відповідні вектори умов , , …, утворюють його базис. Як відомо, методом Гаусса можна привести стовпці i₁, i₂, …, i_r до діагонального виду, а якщо отримані в результаті перетворень деякі рядки містять лише нулі, то вони відкидаються. Іншими словами можна знайти загальний розв’язок системи лінійних рівнянь, що відповідає симплекс – таблиці (тобто матриці системи обмежень), у якому основні змінні – це , , …, , всі решта вільні. Матриця такого розв’язку на стовпцях основних змінних є діагональною. Отже маємо:

 

	…		…		…		…		b
. . .	… …     …	. . .	… …     …	. . .	… …     …	. . .	… …     …	. . .	. . .
	…		…		…		…

 

У стовпці вільних членів b системи лінійних рівнянь у відповідних рядках отримані значення опорного розв’язку: якщо всі вільні змінні дорівнюють нулю, то звідси = (k = 1,2,…,r). Віднімемо від останнього рядка отриманої таблиці перший рядок, помножений на , другий рядок, помножений на , …, r – й рядок, помножений на . В результаті дістанемо нову таблицю,

	…		…		…		…		b
. . .	… …     …	. . .	… …     …	. . .	… …     …	. . .	… …     …	. . .	. . .
	…		…		…		…

 

де = = … = = 0, δ₀ = = – f (α) (значення цільової функції на опорному розв’язку α з протилежним знаком).

Означення 8. Отриманутаблицю називають симплекс – таблицею, приведеною до базису , , …, опорного розв’язку α, а числа δ_j – оцінками цього базису або оцінками її основних (базових) змінних , , …, .

Зміст оцінок δ_j у тому, що це коефіцієнти цільової функції, вираженої через вільні змінні опорного розв’язку α. Справді, δ_j = с _j (j=1,2,…,n), δ₀ = . З другого боку виразимо через інші змінні з рядка 1 , з рядка 2, …, з рядка k , (k = 1,2,…,r). Підставимо ці вирази замість (k = 1,2,…,r) у цільову функцію

f = = ) = = = + = = f (α) + =

= – δ₀. Отже, рівняння нульового рівня цільової функції f = 0, виражене через вільні змінні опорного розв’язку α виглядає так: = δ₀. Саме воно і записано у нижньому рядку симплекс – таблиці.

Теорема 1. (Ознака оптимальності). 1) Якщо всі оцінки деякого базису опорного розв’язку α недодатні, то α є оптимальним розв’язком задачі лінійного програмування у канонічній формі (3).

2) Для оптимального опорного розв’язку задачі лінійного програмування у канонічній формі (3) завжди існує базис, всі оцінки якого недодатні.

Справді, нехай δ_j – оцінки деякого базису опорного розв’язку α, звідки f = + f (α), δ_j ≤ 0. Якщо α₁ = (u₁, u₂, …, u_n) – деякий інший опорний розв’язок, u_j ≥ 0 (j=1,2,…,n), то f (α₁) = + f (α) ≤ f (α), тобто розв’язок α є максимальним.

Навпаки, нехай α – невироджений опорний розв’язок (а у невиродженого опорного розв’язку базис тільки один). Нехай існує така оцінка δ_p базису опорного розв’язку α, що δ_p > 0. Для деякого θ > 0 покладемо (k = 1,2,…,r), = θ, всі інші вільні змінні = 0. Такий набір значень змінних задовольняє системі обмежень: у кожному рядку k симплекс – таблиці, приведеної до базису опорного розв’язку α, маємо = = + = () + = . Оскільки всі > 0 (розв’язок є невиродженим), то й всі > 0 при достатньо малому θ > 0. Отже, такий набір значень змінних є набором координат деякого допустимого розв’язку β. Але f (β) = + f (α) = δ_pθ + f (α) > f (α). Це означає, що не вироджений опорний розв’язок не є максимальним, якщо існує оцінка δ_p > 0 його базису. Отже, невироджений опорний розв’язок є оптимальним тоді і тільки тоді, коли всі оцінки його базису недодатні. Але будь – який опорний розв’язок можна як завгодно точно наблизити невиродженим. Оцінки базисів деякої послідовності таких наближень збігаються до оцінок деякого базису даного розв’язка і отже всі оцінки довільного оптимального опорного розв’язку недодатні.

Теорема 2. (Умова необмеженості цільової функції). Нехай симплекс – таблиця задачі лінійного програмування приведена до базису деякого опорного розв’язку α. Якщо серед оцінок цього базису існує додатна δ_s > 0, а решта елементів s – го стовпця недодатні, то цільова функція не обмежена зверху. Якщо ж існує оцінка δ_s < 0, а решта елементів s – го стовпця невід’ємні, то цільова функція не обмежена знизу.

Справді, для довільного θ > 0 покладемо (k = 1,2,…,r), = θ, всі інші вільні змінні = 0. Такий набір значень змінних задовольняє системі обмежень: у кожному рядку k симплекс – таблиці, приведеної до базису опорного розв’язку α, маємо = + = () + = . Оскільки всі ≤ 0, то й > 0 для довільного θ > 0. Отже, такий набір значень змінних є набором координат деякого допустимого розв’язку β. Але f (β) = + f (α) = δ_sθ + f (α) необмежено зростає із зростанням θ > 0, оскільки за умовою δ_s > 0. Другий випадок доводиться аналогічно.

Приклад. Розглянемо опорний розв’язок α = (1;0;0;0) задачі

f = – 10x₁ + x₂ – 9x₃ + 6x₄ (min),

.

 

Змінивши знак у цільової функції, отримаємо f = 10x₁ – x₂ + 9x₃ – 6x₄ (mах). Відповідна симплекс – таблиця:

 

x1	x2	x3	x4	b
	– 1	– 1
	– 1		– 6

 

Приведемо симплекс – таблицю цієї задачі до базису А₁, А₂ опорного розв’язку α:

x1	x2	x3	x4	b
			– 1
			– 17	– 10

x1	x2	x3	x4	b
			– 1
	– 1		– 6

x1	x2	x3	x4	b
	– 2	– 4
	– 1		– 6

Серед оцінок є додатна δ₃ > 0. Отже, на цьому етапі не можна стверджувати, що α є оптимальним розв’язком. З іншого боку розглянемо базис А₁, А₃ того ж опорного розв’язку α. Так само приведемо симплекс – таблицю до цього базису:

 

x1	x2	x3	x4	b
	– 1/2 1/2		3/2 – 1/2
	– 1/2		– 33/2	– 10

 

Всі оцінки недодатні. Отже, α є оптимальним розв’язком цієї задачі, вектори А₁ і А₃ складають його базис.

 

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

На цих теоремах і ґрунтується симплекс – метод. Він дає спосіб на кожному кроці від неоптимального згідно з теоремою 1 опорного розв’язку перейти до наступного, ближчого до оптимального, ніж попередній, тобто поліпшити його. Тому симплекс – метод називають ще методом послідовного поліпшення опорного розв’язку. Цей алгоритм закінчує роботу, якщо встановлюється оптимальність отриманого опорного розв’язку згідно з теоремою 1 або ж відсутність оптимального розв’язку згідно з теоремою 2. Пояснімо його спочатку на конкретному прикладі.

Приклад. Для виготовлення продукції використовують три вида сировини і чотири способи виробництва. Запаси сировини, її витрати на одиницю продукції та кількість виготовляємої продукції по кожному способу (за годину роботи) наведені у таблиці.

 

 

Сировина	Спосіб виробництва	Запаси
Кількість продукції

 

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

Це приклад задачі планування виробництва, розглянутий в §1. Як там показано, позначивши через х_j час використання j – го способу виробництва (j = 1,2,3,4), дістанемо таку задачу лінійного програмування.

f = 12x₁ + 7x₂ + 18x₃ + 10x₄ (max),

.

Ввівши нові змінні х₅, х₆, х₇, зведемо цю задачу до канонічної:

f = 12x₁ + 7x₂ + 18x₃ + 10x₄ (max)

.

Складемо її симплекс – таблицю:

 

х1	x2	x3	x4	x5	х6	х7	b

 

Симплекс – таблиця виявляється приведеною до базису А₅, А₆, А₇ опорного розв’язку α₁ = (0; 0; 0; 0; 18; 30; 40), f (α₁) = 0. Це видно з того, що матриця такого розв’язку на стовпцях змінних х₅, х₆, х₇ є діагональною і отже відповідна система лінійних рівнянь у звичайній формі загального розв’язку має вигляд:

.

Отже, змінні х₅, х₆, х₇ є основними, решта вільні. Вільні змінні опорного розв’язку х₁ = х₂ = х₃ = х₄ = 0, звідси х₅ = 18, х₆ = 30, х₇ = 40. Оцінки основних змінних дорівнюють нулю, отже цільова функція виражена через вільні змінні опорного розв’язку α₁, f = 0. Серед оцінок базису є додатні, тож α₁ не є оптимальним згідно з ознакою оптимальності (теорема 1). Процедура його поліпшення, до розгляду якої ми переходимо, і є кроком симплекс – методу.

Виберемо будь – яку з додатних оцінок, скажімо δ₁ = 12. (Найчастіше вибирають найбільшу, але це не обов’язково). Тим самим обрані змінна х₁ і стовпець 1 симплекс – таблиці (з номером оцінки). Якщо знайти новий опорний розв’язок α₂, у якому змінна х₁ стане основною (замість вільної у α₁), а тим самим додатною, то й значення цільової функції f = 12x₁ + 7x₂ + 18x₃ + 10x₄ збільшиться на 12x₁ і стане додатним. Отже f (α₂) ≥ f (α₁), такий α₂ ближче за α₁ до оптимального. Фактично процедура знаходження α₂ така.

Розглянемо відношення вільних членів до відповідних елементів обраного стовпця (в даному прикладі це 18/1, 30/1, 40/1) і серед них виберемо найменше. Тим самим обрані рядок (у прикладі теж перший) і елемент на перетині обраних рядка і стовпця (тут а₁₁ = 1). Насправді це обрано місце, де елемент стовпця змінної х₁ у симплекс – таблиці нового опорного розв’язку α₂ буде дорівнювати одиниці, решта елементів повинна дорівнювати нулю, оскільки для α₂ змінна х₁ стане основною, а її стовпець частиною діагональної матриці. Обрані елемент, рядок і стовпець називають ведучими для наступного жорданова перетворення: як і у методі Гаусса, операціями над рядками симплекс – таблиці (тобто матриці) ведучий елемент роблять одиницею, а решту елементів ведучого стовпця нулями. У цьому прикладі вже а₁₁ = 1, тож достатньо відняти перший рядок від другого і третього, від останнього рядка треба відняти перший, помножений на 12. В результаті отримаємо таку симплекс – таблицю:

х1	x2	x3	x4	x5	х6	х7	b
	– 1			– 1 – 1
	– 17			– 12			– 216

 

В результаті змінна х₁ стала основною (що і було метою перетворення), натомість змінна х₅ стала вільною, отже новий набор основних змінних – це х₁, х₆, х₇ ; новий загальний розв’язок, відповідний симплекс – таблиці, має вигляд

;

отже новий опорний розв’язок α₂ = (18; 0; 0; 0; 0; 12; 22); цільова функція, виражена через новий набір вільних змінних має вигляд f = 216 – 17x₂ + 6x₃ + 10x₄ – 12x₅; f (α₂) = 216 > f (α₁) = 0. На цьому завершується перший крок симплекс – метода.

Зазначимо, що у цій процедурі обирався лише рядок (по критерію мінімуму відношень), все інше випливало з цього автоматично. Спробуємо у якості ведучого обрати рядок 2 замість рядка 1. Тоді ведучий елемент а₂₁ = 1, отже для жорданова перетворення достатньо відняти другий рядок від першого і третього, від четвертого рядка треба відняти другий, помножений на 12. Маємо:

х1	x2	x3	x4	x5	х6	х7	b
		– 1	– 1		– 1 – 1		– 12
	– 5	– 6	– 2		– 12		– 360

 

В результаті набір основних змінних: х₁, х₅, х₇ ; опорний розв’язок (30; 0; 0; 0;–12; 0;10; 0). Він не є допустимим, оскільки х₅ = – 12. Так само станеться, якщо обрати рядок 3 у якості ведучого. Зміст критерію мінімуму відношень у тому, що лише за таким вибором новий опорний розв’язок виявиться допустимим, тому його називають умовою допустимості. Це буде доведено при розгляді симплекс – метода у загальному вигляді, зараз продовжимо розгляд приклада.

Другий крок. У симплекс – таблиці, отриманій на першому кроці, залишилось дві додатні оцінки: 6 і 10. Обираємо серед них більшу: як ми бачили, ця оцінка є множником для величини збільшення цільової функції на кроці, тож можна сподіватись, що в такому разі і ця величина виявиться найбільшою (хоч насправді це не завжди так). Тим самим обрані змінна х₄ і відповідний стовпець симплекс – таблиці. Якщо знайти новий опорний розв’язок α₃, у якому змінна х₄ стане основною (замість вільної у α₂), а тим самим додатною, то й значення цільової функції f = 216 – 17x₂ + 6x₃ + 10x₄ – 12x₅ збільшиться, на 10х₄. Отже f (α₃) ≥ f (α₂), такий α₃ поліпшить α₂ .

Як і на першому кроці, розглянемо відношення вільних членів до відповідних елементів обраного стовпця: 12/1, 22/2; виберемо серед них найменше 22/2 (лише додатні елементи стовпця у розгляді: доведення умови допустимості далі при розгляді симплекс – методу у загальному вигляді). Тим самим обрані ведучий рядок 3 і ведучий елемент а₃₄ = 2 для жорданова перетворення. Отже поділимо рядок 3 на 2, а отриманий рядок віднімемо від другого та помноживши на 10 від четвертого. Маємо:

 

х1	x2	x3	x4	x5	х6	х7	b
	– 3/2 1/2			– 1/2 – 1/2		– 1/2 1/2
	– 22	– 4		– 7		– 5	– 326

 

В результаті змінна х₄ стала основною, змінна х₇ стала вільною, новий набір основних змінних – це х₁, х₃, х₆ ; отже новий опорний розв’язок α₃ = (18; 0; 0; 11; 0; 1; 0), цільова функція, виражена через новий набір вільних змінних має вигляд f = 326 – 22х₂ – 4х₄ – 7х₅ – 5х₇, f (α₃) = 326 > f (α₂) = 216. Нарешті всі оцінки не додатні. Згідно з теоремою 1 на цьому симплекс – метод завершує роботу. Якщо знайти новий опорний розв’язок, у якому будь – яка вільна змінна х₂, х₄, х₅ або х₇ стане основною (замість вільної у α₃), а тим самим додатною, то значення цільової функції f зменшиться. Отже α₃ є оптимальним розв’язком задачі лінійного програмування у канонічній формі. Щодо початкової задачі, то відкидаємо три останні додані змінні. Відповідь її така. Для виготовлення найбільшої кількості продукції при даних запасах сировини необхідно застосовувати на протязі 18 годин перший спосіб виробництва та на протязі 11 годин – четвертий. В результаті буде виготовлено 326 одиниць продукції.

Нарешті сформулюємо симплекс – метод у загальному вигляді.

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

2. Знайти деякий початковий опорний розв’язок задачі (3), привести симплекс – таблицю до базису цього розв’язку, зокрема обчислити оцінки δ_j всіх його основних змінних.

3. Згідно з ознакою оптимальності (теорема 1), якщо всі оцінки δ_j ≤ 0, то цей розв’язок є оптимальним і на цьому симплекс – метод завершує роботу. Якщо ж серед оцінок є додатні, то виконується процедура його поліпшення, яка і є кроком симплекс – метода.

1) Вибираємо довільну додатну оцінку, скажімо δ_s. Тим самим обрані змінна х_s і стовпець з номером s симплекс – таблиці.

2) Якщо всі елементи стовпця s, окрім самої оцінки δ_s > 0, недодатні, то цільова функція не обмежена зверху (умова необмеженості цільової функції, теорема 2), тобто оптимального розв’язку задачі (3) не існує і на цьому симплекс – метод припиняє роботу.

3) Якщо у стовпці s є додатні елементи, то серед відношень вільних членів d_i до відповідних додатних елементів a_is стовпця s обираємо найменше

Θ = ; Θ (4)

для деякого рядка з номером k. Умову (4) на рядок k називають умовою допустимості.

4) На перетині обраних рядка k і стовпця s ведучий елемент а_ks наступного жорданова перетворення. Поділивши рядок k на ведучий елемент а_ks, дістанемо одиницю у стовпці s і Θ у стовпці вільних членів. Отриманий рядок віднімемо від кожного іншого рядка і, помноживши на а_is, від рядка цільової функції, помноживши на δ_s.