Матрична форма запису

Форми запису О.З.Л.П.

3.2.1. Запис за допомогою знаків підсумовування.

min

(8)

X_j≥0

Векторна форма запису.

(9)

де

Матрична форма запису.

(10)

де

3.3 Основні визначення О.З.Л.П.

Визначення 1. Планом чи припустимим рішенням О.З.Л.П. називається =(X₁,...X_n), що задовольняє (6-7).

Визначення 2. План називається опорним, якщо вектори , що входять у розкладання (9) з позитивними X_j (X_j>0) лінійно незалежні.

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

Визначення 3. Опорний план * не вирождений, якщо він містить m позитивних компонентів, якщо <m позитивних компонентів, те * вирождений.

Визначення 4. Оптимальним планом О.З.Л.П. ⁰ називається план, що доставляє мінімум функції мети Z.

3.4. Властивості рішень З.Л.П.

Усі теореми, наведені нижче, даються без доказу. Вони дані в [ 1 ]

Теорема 1. Безліч усіх планів З.Л.П.

Безліч усіх планів З.Л.П., якщо воно не пусто, називається багатогранником рішень.

Теорема 2. Функція мети З.Л.П. досягає свого мінімального значення в кутовій крапці багатогранника рішень.

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

Визначення 5. Точка X* опукла лінійна комбінація точок X₁, X₂,-, X_k,

якщо

Теорема 3. Якщо система векторів Ā₁; Ā₂;…Ā_k(k≤n)у розкладанні (9) лінійно незалежна

Ā₁X₁+Ā₂X₂+…+Ā_kX_k=

де всі X_j ≥0, то X=(X₁;X₂,…,X_k,0,…,0) є кутовою точкою багатогранника рішень.

Теорема 4. Якщо =(X₁;X₂,…,X_n) -кутова точка багатогранника рішень, то вектори Ā_j у розкладанні (9), що відповідають X_j>0, є лінійно незалежними.

Наслідок 1. Кутова точка багатогранника рішень не може мати більше m позитивних компонентів

Наслідок 2. Кожній кутовій точці багатогранника рішень відповідає k≤m лінійно незалежних векторів системи Ā₁, Ā₂,…,Ā_n з (9).

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

Проілюструємо геометрично наведені вище теоретичні положення рішення З.Л.П. Для цього застосуємо графічний метод.

3.5. Графічний метод рішення З.Л.П

Він застосовується, в основному, при рішенні З.Л.П. на площині й рідко в тривимірному просторі.

Загальний вид двовимірної З.Л.П., тобто такої що містить дві перемінні

min(max) Z=C₁X₁+C₂X₂ (11)

(12)

X₁≥0; X₂≥0 (13)

Кожна нерівність з обмежень задачі (12-13) задає на площині X₁ 0 X₂ напівплощина, границею якої є пряма, що задається відповідного рівністю, тому що X₁≥0, X₂≥0 задають 1 чверть, то сфера припустимих чи рішень планів З.Л.П., що є перетинанням цих напівплощин, якщо вона не порожня, знаходиться в I-ої чверті й являє собою багатокутник закритий чи відкритий. Функція мети Z задає сім’я рівнобіжних прямих, перпендикулярних вектору нормалі =(C₁;C₂), причому для всіх точок кожної з цих прямих, вона набуває того самого значення. При русі прямої із сім’ї в напрямку вектора це значення зростає, у протилежну - убуває.

Можуть бути різні випадки, зображені на рисунку.

X2 C X2

B

D

_ A _

N N

0 X1 0 X1

рис.1. рис.2.

a) б) в)

ℓ1

X2 X2 X2

A

_ _ _ ℓ2

N N N

B

0 X1 0 X1 0 X1

рис.3.

Випадок 1. Якщо багатокутник рішень обмежений (рис.1), то min і max функції мети кінцеві; причому min Z = Z(B), а max Z = Z(D).

Випадок 2. Багатокутник рішень не обмежений. У цьому випадку функція мети може бути:

2.1. Не обмежена ні зверху, ні знизу (рис.2), тому що прямі сім’ї, що задається функцією мети, будуть мати загальні точки з багатокутником рішень при русі їх як завгодно далеко від початку координат як у напрямку вектора N, так і в протилежну сторону N.

2.2. Не обмежена знизу, тобто min Z = -∞, а max Z = Z(A) (рис.3,а)

2.3. Не обмежена зверху, тобто max Z = ∞, а min Z = Z(B) (рис.3,б)

2.4. Кінцева, причому max Z = Z(ℓ₁₎, а min Z = Z(ℓ₂₎, тобто екстремуми досягаються не в одній точку, а на всіх точках двох граничних прямих, перпендикулярних

Зауваження 4. Якщо система обмежень З.Л.П. містить n невідомих і m лінійно незалежних рівнянь і n-m = 2, то така З.Л.П. може бути вирішена за допомогою графічного методу з використанням методу Жордана-Гаусса.

Розглянемо алгоритм рішення такої задачі:

(14)

n – m = 2 (15)

X_j ³0

1) Використовуємо метод Жордана-Гаусса, метод повного виключення невідомих.

Виключення невідомих на кожному кроці проводиться за формулами

(16)

Причому а_io=b_i. i=1,…m

Перетворення по формулами (16) доцільно проводити в таблиці.

2) Після m кроків, пророблених за (16), приведемо систему обмежень до виду

(17)

(18)

3) Виражаючи з (17) базисні через вільні змінні X_m+1, X_n і підставляючи X_i у (14) одержуємо вираження Z через X_m+1,X_n

(19)

4) З огляду на, що , одержуємо з (17), відкидаючи X_i, систему обмежень з нерівностей

(20)

X_m+1≥0, Xn≥0

Ця задача (19-20) містить два невідомих і зважується графічно.

Приклад 3. Дана З.Л.П.

minZ=3X₁-X₃+X₄-2X₅

X₁-X₂+2X₃+4X₄=11

X₁-X₂+3X₃+6X₄+X₅=19

-2X₁+3X₂-5X₃-11X₄=-26

1. Методом Жордана-Гаусса знайти початковий опорний план.

2. Для цього плану обчислити функцію мети.

3. Перейти до іншого опорному плану методом Жордана-Гаусса.

4. Вирішити задачу геометрично.

Рішення.

1) Усі обчислення за методом Жордана-Гаусса будемо робити в таблиці, попередньо помноживши 3-і рівняння на – 1, що б b₃=26>0 Позначимо

№ кроку	Ā1	Ā2	Ā3	Ā4	Ā5	Ā0
		-1
		-1
		-3
		-1
		-1
				-2
				-1
		-1
				-2
	-1

Вибравши a₁₁=1 елементом, що дозволяє, застосуємо формулу (16), і перерахуємо елементи нової таблиці на 1-ому кроці. При виборі елемента, що дозволяє, враховуємо дві умови: компоненти A ₀ у новій таблиці повинні бути 0 і для спрощення рахунку елемент, що дозволяє, повинен бути ближче до 1, а найкраще дорівнює 1. Тому після 1-го кроку, для перерахування таблиці, що дозволяє елемент a₃₃=1, тому що в 1-ому і 2-ому рівняннях уже є базисні змінні X₁ і X₅ (вектори Ā₁ і Ā₅ одиничні). У результаті 2-го кроку були отримані три базисні змінні X₁, X₅ і X₃, яким відповідають базисні одиничні вектори ₁, Ā₅, Ā₃. Узявши вільні перемінні X₂ = X₄ =0, одержимо початковий опорний план З.Л.П. *=(3;0;4;0;4), якому відповідає функція мети Z₁=3·3-4·1-2·4=-3

3. Перейдемо на 3-ому кроці до іншого опорного плану. Для цього треба замість якої-небудь базисної перемінної ввести іншу. Наприклад, замість X₁ X₂. При цьому елемент, що дозволяє, a₁₂= 1 і усі компоненти A ₀ у новій таблиці > 0. У результаті перерахування таблиці одержали після 3-го кроку нові базисні перемінні X₂, X₅, X₃ (базисні одиничні вектори Ā₂, Ā₅, Ā₃) і новий опорний план _on=(0;3;7;0;1), що забезпечує функцію мети Z₂=0·3+3·0-7·1+0-2·1= -9

5. Вирішимо задачу геометрично. Це можливо, тому що n – m = 5 – 3 = 2. З огляду на результати, отримані на 3-ем кроці, з таблиці маємо систему рівнянь

X₁+X₂ -2X₄=3 X₂=3-X₁+2X₄≥0

-X₁ +X₄+X₅=1 => X₅=1+X₁-X₄≥0 (21)

X¹ +X₃+X₄=7 X₃=7-X₁-X₄≥0

X_i≥0 j=1,…,5 X₁≥0; X₄≥0

Виразимо Z через X₁ і X₄, з огляду на отримані вираження базисних змінних X₂, X₅, X₃ через вільні X₁ і X₄

Z=3X₁-(7-X₁-X₄)+X₄-2(1+X₁-X₄)=-9+2X₁+4X₄

Тоді розв'язувана З.Л.П. має вид

minZ=-9+2X₁+4X₄; -9+minZ1=2X₁+4X₄

X₁-2X₄≤3

-X₁+X₄≤1 X₁≥0

X₁+X₄≤7 X₄≥0

Побудуємо багатогранник рішень на площині X₁OX₄ у 1-ої чверті.

Граничні прямі: будуємо по двох точкою

X1
X4	-1,5

X₁-2X₄≤3: => X₄ ³

X1		-1
X4

X₄≤1+X₁ => ℓ₂: X₄=7-X₁;

X1
X4

X₄≤7+X₁ => ℓ₃: X₄=7-X₁;

Шукані напівплощини позначимо штрихами. У результаті перетинання напівплощин одержуємо багатокутник рішень ОАВСД.

Для відшукання min Z₁ будуємо нормальний вектор N = (2;4) і сім’ю рівнобіжних прямих, що задаються Z ₁, перпендикулярних N

Як випливає з мал.4 min Z₁ = Z₁ (0) = Z₁ (0;0) = 2*0+4*0 = 0, тобто min Z = Z(0) = -9. Для відшукання оптимального плану вихідної задачі підставимо знайдені оптимальні

X°₁=X°₄=0 у (21)Одержимо X°₁=0; X°₂=3; X°₃=7’ X°₄=0 X°₅=1

4. Симплексний метод рішення З.Л.П.

У попередньому розділі показано, що оптимальне рішення З.Л.П., якщо функція мети обмежена, досягається хоча б в одній з вершин багатогранника рішень і що кожній вершині відповідає опорний план З.Л.П., що задається системою m лінійно незалежних векторів із системи векторів Ā₁, Ā₂,…,Ā_n обмежень задачі. Тому оптимальний план рішення З.Л.П. можна знайти перебором усіх опорних планів (вершин) З.Л.П., яких не більше ніж число сполучень . При великих n і m велике і такий перебір недоцільний. Данциг запропонував процедуру цілеспрямованого перебору опорних планів зі зменшенням (збільшенням) функції мети. Таку процедуру він назвав симплексним методом, що дозволяє за кінцеве число кроків, починаючи з початкового опорного плану, одержати її оптимальний план. Якщо задача не має плану чи її функція мети не обмежена на багатограннику рішень, то симплексний метод дозволяє установити це у процесі рішення.

4.1. Вимоги до З.Л.П. для можливості її рішення симплексом-методом.

З вищевикладеного випливає, що застосування симплекса-методу вимагає наявності початкового опорного плану З.Л.П. При канонічній формі зображення З.Л.П. з обмежень задачі легко одержати такий опорний план. Канонічна форма З.Л.П. задовольняє трьом вимогам:

1) обмеження – у виді рівностей;

2) праві частини b_i≥0

3) кожне обмеження містить базисну перемінну. Загальний вид З.Л.П. у канонічній формі

( 22)

Тоді початковий опорний план: базисні перемінні X₁=bi , вільні перемінні

(23)

-план, тому що

X₁· ₁+X_{2 2}+....+X_{m m}= _o= (24)

План опорний, тому що вектори Ā₁,…,Ā_m із системи (22)

(25)

одиничні, а, отже, лінійно незалежні, тобто базисні, і X₁, X₂,…X_{m у} розкладанні (24) ненегативні.

4.2 Побудова опорних планів.

Розглянемо, як, виходячи від початкового опорного плану (23) перейти до іншого опорного плану. Вектори Ā₁, Ā₂,…,Ā_m -базис у m-мірному просторі, тому будь-який вектор з (25) можна зобразити

(26)

Нехай Ā_m+1 не входить у базис і в його розкладанні

X_1m+1 Ā₁+X_2m+1 Ā₂,…,X_mm+1Ā_m=Ā_m+1 (27)

є хоча б один X_im+1>0

Візьмемо Θ>0, помножимо (27) на Θ і віднімемо цей добуток з (24). Одержимо

(X₁-ΘX_1m+1) Ā₁+(X₂-ΘX_2m+1)Ā₂+…+(X_m-ΘX_mm+1)Ā₂+ΘĀ_m+1=Ā₀ (28)

Переносячи ΘĀ_m+1 у ліву частину одержимо, що вектор

=(X₁-ΘX_1m+1,X₂-ΘX_2m+1,..,X_m-ΘX_mm+1,Θ,0,..,0) (29)

є планом, якщо його компоненти ≥0, тому що Θ≥0, то для всіх компонентів з X_im+1³0 ця умова буде дотримуватися. Тому розглянемо дотримання цієї умови для компонентів з X_im+1>0, тобто

X_i - ΘX_im+1≥0 при X_im+1>0 (30)

З (30) випливає, що при

(31)

умова незаперечності компонент нового плану буде дотримуватися. Щоб цей план став опорним, треба, щоб ≥0 компонент у стало m. А в (29) їх m+1. Тому необхідно принаймні один компонент зробити нулем. Це досягається за умови

(32)

У результаті план (29) стане опорним.

Виключення одного вектора з базису і включення замість нього іншого за допомогою Θ₀ відповідає переходу від одного базису до іншого за допомогою методу Жордана-Гаусса.

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

Зауваження 5.

Якщо вектор Ā_m+1 підлягає включенню в базис, а в його розкладанні (27) усі X_im+1≤0, то не можна вибрати Θ>0, яке б виключало один з векторів у розкладанні (28). У цьому

випадку план містить m+1 позитивний компонент, а система векторів Ā₁, Ā2,…,Ā_m+1 є лінейнозависиму (їх >m) і визначає не кутову, а внутрішню точку багатогранника рішень, у якій функція мети не може досягати мінімального значення.

4.2. Умови оптимальності опорного плану.

Нехай З.Л.П. має плани і кожен опорний план не вироджений. У випадку опорного плану (23) =(X₁,X₂,..,X_m,0,..,0)

X₁Ā₁+X₂Ā₂+…+X_mĀ_m=A₀ (33)

Z(X₀)=X₁C₁+X₂C₂+..+X_mC_m (34)

причому всі X_j>0

Вектори Ā₁,Ā₂,..,Ā_m- базис, тому будь-який Ā

X_1j1+X_2j2+..+X_mj=Ā_j (35)

і Z_j=X_1j1+X_2j2+…+X_mjC_m (36)

Тоді вірні наступні твердження:

Теорема 5. Якщо для деякого Ā_j виконується умова ∆_j=Z_j-C_j>0, то план X_on не є оптимальний і можна побудувати план X, для якого Z(X)<Z(X_on)

Доказ.

Помножимо (35) і (36) на Θ>0 і віднімемо їх, відповідно, з (33) і (34). Одержимо

(X₁-ΘX_1j)Ā₁ +(X₂-ΘX_2j)Ā₂+…+(X_m-ΘX_mj)Ā_m +ΘĀ_j = Ā_o (37)

(X₁-ΘX_1j)C₁+(X₂-ΘX_2j)C₂+…+(X_m-ΘX_mj)C_m+ΘC_j=Z(X_on)-Θ(Z_j-C_j) (38)

Вибравши Θ>0, так щоб у (37) коефіцієнти були ≥0 ми одержимо новий план = (X₁-ΘX_1j,X₂-ΘX_2j,…,X_m-ΘX_mj,Θ,0....,0)

якому відповідає значення функції мети (38)

(39)

Тому що ∆j=Z_j-C_j>0 і Θ>0, те (X)< (Xon), ∆j=Z_j-C_j називаються оцінками плану.

З теореми 5 випливає, що критерієм введення вектора Ā_j (перемінної X_j) у базис є ∆_j>0

Наслідок 4. Якщо для деякого плану оцінки для всіх його векторів Ā_j ∆j≤0 (j=1,..,n), то план оптимальний.

Для З.Л.П. з функцією мети на max справедлива теорема.