Математичне програмування в економіці

Математичне програмування

Тема 1. Предмет, особливості та сфери застосування математичного програмування в економіці. Класифікація задач

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

Загалом послідовність використання економіко-математичних моделей така:

формується економічна проблема;

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

розв'язується математична задача, перевіряється рішення;

перекладається розвиток на економічну мову і аналізується результат.

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

У загальному вигляді математична формулювання задачі виглядає таким чином:

необхідно знайти найбільше або найменше значення цільової функції f (x₁, x₂, x₃…, x_n);

якщо треба виконати умови g_i (x₁, x₂, x₃…, x_n) b_i, i = 1,2,3…,m;

де: f, g_i - відомі функції,

b_i - деякі дійсні числа, n m.

Задачу оптимізації з точки зору економіки можна сформулювати таким чином:

знайти такі значення змінних. що надають ефективності діяльності максимальне чи мінімальне значення;

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

Конкретна ціль, поставлена у економічній задачі, пояснюється цільовою функцією (критерієм ефективності), екстремум якої і треба знайти.

Обмеження відображають умови, при розв'язанні економічної задачі, наприклад, брак ресурсів, гранична вартість і таке інше. Змінні, з яких будується цільова функція, та на які накладаються обмеження, використовують як “інструмент”, за допомогою якого досягається той чи інший варіант цілі. Як змінні задовольняють усім обмеженням, так отриманий варіант називають припустимим (допустимим).

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

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

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

Класифікація моделей задач математичного програмування залежить від властивостей функції цілі та функцій обмежень.

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

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

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

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

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

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

Якщо у задачі математичного програмування відсутні усі обмеження. така задача має назву задачі безумовного програмування.

У якості прикладів економічних проблем, які доцільно розв'язувати. використовуючи методи та моделі математичного програмування, розглянемо такі:

Приклад 1. Задача про планування випуску продукції малого підприємства.

Планується виробляти жіночі та чоловічі костюми. На жіночій костюм потрібно 1 м. шерсті, 2 м. шовку та 1 людино-тиждень працевитрат. На чоловічий костюм потрібно 3,5 м. шерсті, 0,5 м. шовку і також 1 людино-тиждень працевитрат. Загалом підприємство має 350 м. шерсті, 240 м. шовку та 150 людино-тижнів працевитрат. За попередньою домовленістю із замовником мають виробити 110 костюмів жіночих та чоловічих загалом. Акціонери, які вклали гроші у підприємство та сировину (тканину), вимагають прибуток не менше, ніж 1400 грн. Замовник купує жіночий костюм на 10 грн. дорожче собівартості, чоловічий - на 20 грн. Потрібно з'ясувати: скільки необхідно виготовити жіночих та чоловічих костюмів, щоб задовольнити усім вимогам та отримати найбільший прибуток.

Розв'язок задачі: Позначимо кількість жіночих костюмів, які потрібно виготовити, через х₁; кількість чоловічих - х₂. Загальний прибуток (критерій оптимізації, мета, ціль) виробництва складає:

Z = f (x) = 10 x₁ + 20 x₂ ;

витрати: шерсті = 1 х₁ + 3,5 х₂;

шовку = 2 х₁ + 0,5 х₂;

трудомісткості = х₁ + х₂;

результати: кількість загальна костюмів х₁ + х₂;

прибуток 10 x₁ + 20 x₂.

Функціональні обмеження задачі мають вигляд:

х₁ + 3,5 х₂ 350;

2 х₁ + 0.5 х₂ 240; обмеження ресурсів

х₁ + х₂ 150;

х₁ + х₂ 110; обмеження планового завдання

10 х₁ + 20 х₂ 1400;

Нефункціональні обмеження вочевидь складають:

х₁ 0;

х₂ 0.

Розв'язок задачі математичного програмування у даному прикладі складає: х₁ = 70; х₂ = 80; f (x)_max = 2300 грн.

Приклад 2. Задача про постачання вантажів від постачальників до замовників.

Від трьох постачальників, розташованих у пунктах А₁, А₂, А₃ до чотирьох замовників, розташованих у пунктах В₁, В₂, В₃, В₄, треба перевезти однорідний вантаж. Наявність вантажу по пунктах постачальників: А₁= 50т, А₂ = 40 т, А₃ = 20т. Потреба у вантажі: В₁ = 30т, В₂ = 25т, В₃ = 35т, В₄ = 20т. Відстані між пунктами замовників та постачальників наведені у таблиці.

Таблиця

Замовники Постачальники	В1	В2	В3	В4	Запаси
А1	С11 3 х11	С12 2 х12	С13 4 х13	С14 1 х14	a1 = 50
А2	С21 2 х21	С22 3 х22	С23 1 х23	С24 5 х24	а2 = 40
А3	С31 3 х31	С32 2 х32	С33 4 х33	С34 4 х34	а3 = 20
Потреба	b1 = 30	b2 = 25	b3 = 35	b4 = 20	110

Розв'язок задачі. Позначимо x_ij - кількість вантажу. який буде перевезено з “i”-ого пункта постачання у “j”-ий пункт замовлення; c_ij - відстань від “i”-ого постачальника до “j”-ого замовника. Мета: розшукати вартість перевезення вантажів з найменшою витратою транспортного моменту.

Z = f (x) = C_ij X_ij

Задача збалансована, тобто наявність вантажу дорівнює потреби у вантажу:

X_ij = а_і, і = 1, 2, 3; - умова вивезення вантажу від кожного з трьох постачальників до 4 замовників;

X_ij = в_j; j - 1, 2, 3, 4; - умова отримання кожним замовником необхідної кількості вантажу.

Нефункціональні обмеження: х_ij 0.

Розв'язок задачі складає:

х₁₁ = 25; х₁₂ = 5; х₁₄ = 20; х₁₃ = 0;

х₂₁ = 5; х₂₃ = 35; х₂₂ = 0; х₂₄ = 0;

х₃₁ = 20; х₃₂ = 0; х₃₃ = 0; х₃₄ = 0;

f (x)_min = 190т.км.

Приклад 3. Задача про раціональний розкрій.

Підприємство одержує прут сталевого прокату довжиною l = 800 см. Треба виготовити деталі трьох (і) різновидів: l₁ = 250 см, а₁ = 150 штук; l₂ = 190 см, а₂ = 140 штук; l₃ = 100 см, а₃ = 48 штук.

Скласти раціональний план розкрою вихідного матеріалу (деталей) з найменшими виходами (залишками).

Розв'язок задачі. Побудуємо таблицю можливих варіантів розкрою.

Таблиця

Номер способу (j)	bij	Залишок cj	Кількість прутків за “j”-способом
	l1 = 250	l2 = 190	l3 = 100
j = 1	3	0	0	50	x1
j = 2	2	1	1	10	x2
j = 3	2	0	3	0	x3
j = 4	1	2	1	70	x4
j = 5	1	1	3	60	x5
j = 6	1	0	5	50	x6
j = 7	0	4	0	40	x7
j = 8	0	3	2	30	x8
j = 9	0	2	4	20	x9
j = 10	0	1	6	10	x10
j = 11	0	0	8	0	x11
Потрібна кількість деталей	а1 = 150	а2 = 140	а3 = 48	-	-
	і = 1	і = 2	і = 3

Позначимо:

“х_j” - кількість одиниць (прутків) первинного матеріалу, який буде розкроєно за “j” варіантом (способом);

а_і - потрібна кількість деталей “і”-ого різновиду (l_і - довжини);

с_j - залишок при розкрої одиниці первинного матеріалу (прутка) за “j”-тим способом (варіантом);

b_ij - кількість деталей “і”-ого виду, яку отримують при виготовлені з одиниці первинного матеріалу (прутка) за “j”-тим варіантом (способом).

Залишок за “j”-тим способом від розкрою = c_j x_j, загалом

n

Z = C_j X_j min,

j=1

за умов:

n

b_ij x_j a_j, i = 1,2,3…m;

j=1

x_j 0, j = 1,2,3…n.

Найбільш трудомістка частина задачі - визначення способів (варіантів) розкрою, яка здійснюється за формулою:

m

l_i bij + C_j l, j = 1,2,3…n;

і=1

0 C_j min (l_i).

Цільова функція:

Z = 50 х₁ + 10 х₂ + 0 х₃ + 70 х₄ + 60 х₅ + 50 х₆ + +40 х₇ + 30 х₈ + 20 х₉ + 10 х₁₀ + 0 х₁₁; min;

обмеження:

3х₁ + 2х₂ + 3х₃ + 1х₄ + х₅ + х₆ 150;

х₂ + 2х₄ + х₅ + 4х₇ + 3х₈ + 2х₉ + х₁₀ 140;

х₂ + 3х₃ + х₄ + 3х₅ + 5х₆ + 2х₈ + 4х₉ + 6х₁₀ + 8х₁₁ 48;

x_j 0, j = 1,2,3…11.

Розв'язок задачі складає:

Z* = 2300, x* = (8; 48; 0; 0; 0; 0; 23; 0; 0; 0; 0;).

Приклад 4. Задача комплектного розкрою деталей.

На розкрій поступають варіанти заготовок (t = 2) у обсязі “b_i” (i = 1,2,3…m) кожного. Потрібно виготовити комплекти деталей, які налічують по “l_k” штук (l₁ = 1 деталь, l₂ = 2 деталі) деталей кожного різновиду деталей. Кожна одиниця “і”-ого (одного з двох) різновидів заготовки може бути розкроєна n_i (j = 1,2…n_i) різними способами. При розкрої одиниці “t”-ого матеріалу заготовки “j”-тим способом отримаємо “a_tjk” одиниць “k” - а деталі. Потрібно скласти програму виготовлення якомога більше комплектів деталей, маючи вказані заготовки та задану комплектацію. Дамо конкретні дані: заготовки (t = 1) “А” мають довжину 5 м, кількість b₁ = 100 штук; заготовки (t = 2) “В” мають довжину 4 м, кількість b₂ = 175 штук; деталі D₁ мають довжину 2,0 м, деталі D₂ - довжину 1,25 м; до одного комплекту залучають одну (l₁ = 1) деталь D₁ та дві (l₂ = 2) деталі D₂. Треба виготовити якомога більше комплектів деталей.

Розв'язок задачі. Позначимо: x_tj - кількість одиниць “t”-ого різновиду заготовок, які розкроюваються “j”-тим способом; х - загальна кількість комплектів. Побудуємо таблицю варіантів розкрою заготовок.

Таблиця

Варіанти заготовок	Довжина заготов-ки, м	Спосіб розкрою	Розмір деталі	Кількість загото-вок, bi	План розкрою, xtj
			2 м (D1)	1,25 м (D2)
t = 1	5 м (А)	j = 1	1	2	b1=100	х11
		j = 2	2	0		х12
		j = 3	0	4		х13
t = 2	4 м (В)	j = 1	2	0	b2=175	х21
		j = 2	1	1		х21
		j = 3	0	3		х21
-	Комплект	l1 = 1	l2 = 2	-

Цільова функція: Z = x max;

обмеження:

по кількості заготовок:

х₁₁ + х₁₂ + х₁₃ 100;

х₂₁ + х₂₂ + х₂₃ 175;

по комплектності:

х₁₁ + 2х₁₂ + 0х₁₃ + 2х₂₁ + х₂₂ + 0х₂₃ х;

2х₁₁ + 0х₁₂ + 4х₁₃ + 0х₂₁ + х₂₂ + 3х₂₃ 2х;

х_ij 0; х 0.

Оптимальний план складає:

Z* = 264; х* = (0; 0; 100; 132; 0; 43)

Приклад 5. Задача про складання суміші.

На підприємстві потрібно виготовити суміш, які містить 30% речовини П₁, 20% речовини П₂, 40% речовини П₃ та 10% речовини П₄. Для виготовлення суміші можливо використати три різновиди сировини М₁, М₂, М₃ з різними співвідношеннями речовин та різною вартістю. Потрібно скласти суміш з мінімальною вартістю та наданим складом речовин. Ісходні дані наведені у таблиці.

Таблиця

Речовини	Сировина	Кількість сировини у суміші
	М1	М2	М3
П1	0,3	0,1	0,6	0,3
П2	0,1	0,2	0,2	0,2
П3	0,5	0,6	0,1	0,4
П4	0,1	0,1	0,1	0,1
Вартість за одиницю сировини	4	2	3
-	х1	х2	х3

Розв'язок задачі. Позначимо “x_i” - кількість використаної сировини “M_i”.

Цільова функція:

Z = 4 x₁ + 2x₂ + 3x₃ min;

обмеження:

0,3х₁ + 0,1х₂ + 0,6х₃ 0,3;

0,1х₁ + 0,2х₂ + 0,2х₃ 0,2;

0,5х₁ + 0,6х₂ + 0,1х₃ 0,4;

0,1х₁ + 0,1х₂ + 0,1х₃ 0,1;

х_і 0.

Оптимальний план х* = (0; 0,6; 0,4); Z* = 2,4.

Тема 2. Загальна задача лінійного програмування та деякі з методів її розв'язування

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

Загальною задачею лінійного програмування зветься задача знаходження максимального (мінімального) значення функції

n

Z = C_j X_j ,

j=1

(Z = С₀ + С₁Х₁ + С₂Х₂ + . . . + С_nХ_n);

За умов функціональних обмежень:

n

a_ij x_j b_i , де і = 1,2, . . . , k;

j=1

а₁₁х₁ + а₁₂х₂ + . . . + a_1nx_n b₁ ,

а₂₁х₁ + а₂₂х₂ + . . . + a_2nx_n b_{2 ,}

а_k1х₁ + а_k2х₂ + . . . + a_knx_n b_{k ,}

n

a_ij x_j = b_i , де і = k +1, k + 2, . . . , m;

j=1

a_k+1;1x₁ + a_k+1;2x₂ + . . . + a_k+1;nx_n = b_k+1 ,

a_k+2;1x₁ + a_k+2;2x₂ + . . . + a_k+2;nx_n = b_k+2 ,

a_m;1x₁ + a_m;2x₂ + . . . + a_m;nx_n = b_m

нефункціональних обмежень:

x_j 0 , де j = 1,2,3,. . . n;

а також a_ij; b_i; c_j - задані постійні величини, а ще k m.

Цільову функцію можливо оптимізувати на “max”, або на “min” - це не є принципово, бо у точці х* функція Z = f (x*) - досягає мінімуму, а функція Z = - f (x*) - досягає максимуму. Таким чином ми завжди можемо мінімізувати цільову функцію, не втрачаючи загальності підходу.

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

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

x_j = - (x_j)^- , де (x_j)^- - від'ємне.

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

а) канонічну, якщо k = 0; l = n, де усі функціональні обмеження мають вигляд рівностей;

б) стандартну (симетричну), де k = m; l = n, де усі функціональні обмеження мають вигляд нерівностей.

Будь-які задачу лінійного програмування можливо звести до канонічної задачі шляхом перетворення функціональних обмежень нерівностей у обмеження рівності доданням до нерівностей невідомих невід'ємних величин:

a_i1x₁ + a_i2x₂ + . . . + a_inx_n + y_i = b_i ;

де y_i 0; новим невідомим дають назви відповідно x_n+1; x_n+2; . . . ; х_n+m; та відповідно x_j 0 , де j = 1,2,3 . . . n; n + 1 . . . n + m;

функціональні обмеження набувають вигляд

n

a_ij x_j + y_i = b_i , де і = 1, 2, 3 . . . , m;

j=1

a₁₁x₁ + a₁₂x₂ + . . . + a_1nx_n + x_n+1 = b₁ ,

a₂₁x₁ + a₂₂x₂ + . . . + a_2nx_n + x_n+2 = b₂ ,

a_m1x₁ + a_m2x₂ + . . . + a_mnx_n + x_n+m = b_m ,

кількість невідомих моделі x_j 0 збільшилась до n + m .

Слушне зауваження у підручнику - якщо знак нерівності , так додаткові невідомі треба віднімати від лівої частини нерівності.

Будь-яку задачу лінійного програмування можливо звести до стандартної задачі лінійного програмування шляхом віднімання з лівої частини рівняння додаткових невід'ємних невідомих частин.

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

x_i = u_i - v_i .

Система обмежень у вигляді рівностей сумісна, якщо є хоча б одно рішення; несумісна, якщо ранг матриці a_ij, i = 1,2,. . . n равен ( r ) , а ранг розширеної матриці (додан стовбець “b_i”) більше ніж ( r ); надмірна, якщо одне з рівнянь можливо отримати як лінійну комбінацію інших. У системі: n - кількість невідомих,

m - кількість рівнянь.

Якщо система сумісна та не є надмірною, так будемо вважати, що ранг її дорівнює (m); тоді:

m - базисні змінні,

(n - m) - вільні змінні, m n.

Система у даному випадку має нескінченну кількість розв'язків, так як ми маємо можливість надавати вільним змінним будь-які значення.

Рішення системи рівнянь (обмежень) має назву базисного рішення, якщо усі вільні змінні дорівнюють нулеві. Сукупність значень невідомих (чисел) задачі математичного програмування, які задовольняють усім обмеженням задачі, мають назву припустимого рішення або плану.

Сукупність усіх припустимих рішень системи рівнянь є опукла множина. Або множина розв'язків задачі лінійного програмування є опуклою.

Базисне припустиме рішення задачі лінійного програмування відповідає одній з вершин або граней множини розв'язків.

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

Геометрична інтерпретація множини допустимих розв'язків задачі лінійного програмування та графічний метод її розв'язування. /2/ стор. 165.

Розглянемо задачу лінійного програмування у формі стандартної задачі - з обмеженнями у вигляді нерівностей. З метою наочності розглянемо простіший випадок з двома невідомими змінними. Пригадаємо задачу про планування випуску продукції малим підприємством.

Z = 10 x₁ + 20 x₂ ; Z max;

х₁ + 3,5 х₂ 350;

2 х₁ + 0,5 х₂ 240;

х₁ + х₂ 150;

х₁ + х₂ 110;

10 х₁ + 20 х₂ 1400;

х₁ 0;

х₂ 0.

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

l₁ x₁ + 3,5x₂ = 350 ;

x₁ = 0, x₂ = 350 / 3,5 = 100 ; x₂ = 0, x₁ = 350.

Щоб з'ясувати, яка напівплощіна задовольняє нерівності, перевіримо, наприклад, чи включає точку (0,0) 0 + 3,5 0 350 напівплощіна нижче граничної прямої - нерівність виконується - напівплощіна нижче границі.

Таким же чином перевіримо та побудуємо інші нерівності:

l₂ 2x₁ + 0,5x₂ = 240 ;

x₁ = 0, x₂ = 240 / 0,5 = 480 ; x₂ = 0, x₁ = 240 / 2 = 120 ;

l₃ x₁ + x₂ = 150; x₁ = 0; x₂ = 150; x₂ = 0, x₁ = 150;

l₄ x₁ + x₂ = 110; x₁ = 0; x₂ = 110; x₂ = 0, x₁ = 110;

l₅ 10x₁ + 20x₂ = 1400;

x₁ = 0, x₂ = 1400 / 20 = 70; x₂ = 0, x₁ = 1400 / 10 = 140;

але точка (0,0) 10 0 + 20 0 = 0 1400 не відповідає нерівності, тому нам потрібна півплощіна вище граничної прямої.

Таким чином отриманий многокутник розв'язків, до речі - опуклий, як завжди.

З метою знаходження максимуму цільової функції

Z = 10 x₁ + 20 x₂ побудуємо лінію рівня цільової функції, поклавши Z = 0 ,

10 x₁ + 20 x₂ = 10; x₁ = 0, x₂ = 40; x₂ = 0; x₁ = 80;

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

Ця точка відповідає перетину прямих

х₁ + 3,5 х₂ = 350; - l₁ ( ) C (70; 80)

х₁ + х₂ = 250; - l₃

х₁ = 70, х₂ = 80,

Z_max (x) = 10 x₁ + 20 x₂ = 10 70 + 20 80 = 23000 грн.

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

У розглянутому випадку многокутник розв'язків не тільки опуклий, а ще і є замкненим. Можливі варіанти опуклого многокутника розв'язків, який є необмеженим.

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



Малюнок. Многокутник розв'язків несумісної системи обмежень

задачі лінійного програмування

Тема 3. Симплексний метод розв'язання задач лінійного програмування

Перша праця по лінійному програмуванню була надрукована Канторовичем у 1939 році, але лише після відкриття Данцігом у 1949 році симплекс-метода розв'язання задачі лінійного програмування до цього класу задач виникла зацікавленість. Симплекс-метод дає аналітичний розв'язок лінійної задачі математичного програмування.

Симплексний метод розв'язання задачі лінійного програмування ґрунтується на переході від одного опорного плану до іншого таким чином, що кожного разу значення цільової функції зростає (за умов, що задача має оптимальний план, та кожний з опорних планів не є надмірним). Під опорним планом мають на увазі невід'ємний базисний розв'язок задачі лінійного програмування. Нагадаємо - базисний план (розв'язок) - рішення системи обмежень. у якому усі вільні змінні дорівнюють нулеві, тобто геометрично базисний план відповідає одній з вершин або граней многокутника розв'язків.

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

х₁ + 3,5 х₂ 350;

2 х₁ + 0,5 х₂ 240;

х₁ + х₂ 150;

х₁ 0;

х₂ 0.

Z = f (x) = 10 x₁ + 20 x₂ ; Z max;

( -Z = - f (x) = - 10 x₁ - 20 x₂ - 0 x₄ - 0 x₅; min ).

Розв'язок задачі. Перетворимо функціональні обмеження-нерівності на обмеження-рівності шляхом введення у обмеження-нерівності невід'ємних вільних невідомих y₁, y₂, y₃ (хоча можливо було б і х₃, х₄, х₅ ).

х₁ + 3,5 х₂ + у₁ = 350; (1)

2 х₁ + 0,5 х₂ + у₂ = 240; (2)

х₁ + х₂ + у₃ = 150; (3)

х₁ 0; х₂ 0; у₁ 0; у₂ 0; у₃ 0.

Перед початком виробництва х₁ = х₂ = 0 , тоді

у₁ = 350; наявність ресурсу - шерсть;

у₂ = 240; наявність ресурсу - шовк;

у₃ = 150; наявність ресурсу - трудомісткість.

Прибуток на початок справи Z = 10 0 + 20 0 = 0;

Кількість рівнянь-обмежень m = 3; кількість невідомих - х₁, х₂, у₁, у₂, у₃ n = 5; кількість вільних змінних - (n - m) = 5 - 3 = 2;

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

х (1) = (0; 0; 350; 240; 150) ; Z ( х(1) ) = 0;

де : х₁ = 0; х₂ = 0 - вільні змінні, відповідає рішенню задачі, коли продукція не виробляється. Надамо цю інформацію у вигляді симплекс-таблиці

Таблиця

х1	х2	х3
1 2 1	3,5 0,5 1	350 240 150	у1 - шерстяна тканина у2 - шовкова тканина у3 - наявність ресурсів праці
10	20	0	- Z = - дохід від виробництва

Z = 10х₁ + 20х₂ = 10 0 + 20 0 = 0; - Z = 0;

Виробництво чоловічих костюмів х₂ дає більший дохід, так почнемо його збільшувати, залишаючи х₁ = 0, але існують обмеження. З першої строки симплекс-таблиці (першого рівняння-обмеження на наявність шерстяної тканини) чоловічих костюмів можливо виготовити 350 / 3,5 = 100; з другої строки симплекс-таблиці (другого рівняння-обмеження на наявність шовкової тканини) чоловічих костюмів можливо виготовити 240 / 0,5 = 480 штук; з третьої строки симплекс-таблиці (третього рівняння-обмеження на наявність ресурсів праці) чоловічих костюмів можливо виготовити 150 / 1 = 150 одиниць. Визначальним є обмеження на шерстяну тканину, тобто найбільша кількість чоловічих костюмів (за умов відсутності жіночих - х₁ = 0) дорівнює найменшому з трьох значень 100; 480; 150; х₂ = 110. Визначальний елемент симплекс-таблиці - коефіцієнт у першому рівнянні при другій вільній змінній (х₂), який дорівнює3,5; та має назву центру (ключового елемента).

Як буде виготовлено 100 чоловічих костюмів, так х₂ = 100 і з першого рівняння-обмеження отримаємо (х₁ = 0)

у₁ = 350 - 3,5х₂ - х₁; (1)

у₂ = 240 - 0,5х₂ - 2х₁; (2)

у₃ = 150 - х₂ - х₁; (3)

що у₁ = 0, тобто ресурсів шерстяної тканини не буде; з другого рівняння-обмеження отримаємо у₂ = 240 - 0,5 100 - 2 0 = = 190 м шовкової тканини у запасах; з третього рівняння-обмеження отримаємо у₃ = 150 - 100 - 0 = 50 людино - тижнів трудомісткості у запасах.

Прибуток складає Z = 10 0 + 20 100 = 2000 грн.; - Z = - 2000.

Цільова функція Z = 10 х₁ + 20 х₂ через нові вільні змінні (х₁ = 0; у₂ = 0) має вираз

40 40 40 30

Z = 10 х₁ + 20 х₂ = 10 х₁ + 2000 - у₁ - х₁ = 2000 - у₁ + х₁,

7 7 7 7

бо (з першого рівняння-обмеження) маємо:

х₂ = 100 - у₁ / 3,5 - х₁ / 3,5.

Перетворимо систему рівнянь-обмежень, замінюючи х₂ на його вираз:

х₁ + 3,5 (100 - у₁ / 3,5 - х₁ / 3,5) + у₁ = 350; (1)

2 х₁ + 0,5 (100 - у₁ / 3,5 - х₁ / 3,50) + у₂ = 240; (2)

х₁ + (100 - у₁ / 3,5 - х₁ / 3,50) + у₃ = 150; (3)

х₂ + у₁ / 3,5 + х₁ / 3,5 = 100 (4)

Другий опорний план задачи таким чином складає

х(2) = (0; 100; 0; 190; 50; 100); Z (х(2) ) = 2000;

де: х₁ = 0; у₁= 0 - вільні змінні, відповідає розв'язку задачі, якщо виробляються виключно чоловічі костюми (х₂ = 100). Знов надамо цю інформацію у вигляді симплекс-таблиці.

Таблиця

х1	у1	bі
13 7	1 - 7	190	у2 - залишки шовкової тканини
5 7	2 - 7	50	у3 - залишки ресурсів праці
2 7	2 7	100	х2 - виробництво чоловічих костюмів
30 7	40 - 7	- 2000	- Z - цільова функція

Кожен з елементів симплекс-таблиці має своє значення:

у першому стовпці (х₁) 13 / 7 - потрібна кількість шовкової тканини, потрібної на один жіночий костюм; 5 / 7 - потрібна кількість праці на один жіночий костюм; 30 / 7 - прибуток від одного жіночого костюма;

Дивлячись на цільову функцію

30 40

Z = 2000 + х₁ - у₁ ,

7

бачимо, що збільшення виготовлення жіночих костюмів може збільшити прибуток, бо х₁ 0 , а також 30 / 7 0.

Пригадуючи, що у₁ = 0, знайдемо значення нової вільної змінної, яка задовольняє систему рівнянь-обмежень (2), (3), (1), а також у₂ 0 , у₃ 0 , х₂ 0 .

(2) дає, якщо у₂ = 0, х₁ 102;

(3) дає, якщо у₃ = 0, х₁ = 70;

(1) дає, якщо х₂ = 0, х₁ =350;

Визначальними є обмеження на ресурси праці: , х₁ = 70, у₃ = 0 з рівняння (3).

Визначальний елемент симплекс-таблиці - це коефіцієнт у рівнянні (3), якій дорівнює (5/7), та відіграє роль нового центру, або ключового елементу.

Як буде виготовлено 70 жіночих костюмів, так х₁ = 70 з рівняння (3) отримаємо у₃ = 0 (нова базова змінна);

Третій опорний план задачі складає:

Х (3) = (70; 80; 0; 60; 0;); Z (3) = 2300 грн.;

Z (3) Z (1);

де: у₁ = 0; у₃ = 0 - вільні змінні, відповідає розв'язку задачі, якщо виробляється 70 жіночих та 80 чоловічих костюмів. Надамо цю інформацію у вигляді симплекс-таблиці.

Таблиця

у3	у1	Опорний розв'язок b1
13 5	21 - 35	60	у2 - залишки шовкової тканини
2 5	14 - 5	80	х2 - кількість чоловічих костюмів
5 - 7	2 5	70	х1 - кількість жіночих костюмів
- 6	28 - 7	-2300	- Z - цільова функція

Збільшити прибуток неможливо у зв'язку з тим, що вільні змінні (у_і 0), що наявні у цільовій функції мають від'ємні коефіцієнти у той же час, як самі вони додатні. Опорний план Х (3) є оптимальним.

Х* = ( х₁* = 70? х₂* = 80; у₁ = 0; у₂* = 60; у₃ = 0);

залишки шовкової тканини складають 60 метрів, прибуток складає 2300 грн., як буде виготовлено 70 жіночих та 80 чоловічих костюмів.

Надамо звичайний вигляд симплекс-таблиці розв'язку задачі.

Таблиця 1 ітерація

і	Базисні зміни	х1	х2	х3	х4	х5	bі	Симплекс = bі / аij	Контроль
1	х3	1 а11	3,5 а12	1 а13	0 а14	0 а15	350	350/3,5=100	355,5
2	х4	2 а21	0,5 а22	0 а23	1 а24	0 а16	240	240/0,5=480	143,5
3	х5	1 а31	1 а32	0 а33	0 а34	1 а17	150	150/1=150	153
4	Z (х)	+10 с1	+20 с2	0 ас3	0 с4	0 с5	0	-	+30

Z (х) = ( -Z); Z (х) - С₀ - С₁Х₁ - С₂Х₂ - С₃Х₃ - С₄Х₄ - С₅Х₅ = 0;

Z = С₀ + С₁Х₁ + С₂Х₂ + С₃Х₃ + С₄Х₄ + С₅Х₅ = 0 + 10Х₁ + 10Х₂ + 0 Х₃ + 0 Х₄+ 0 Х₅ = 0 Х₁ + 2 Х₂ ;

( -Z) = - 10 Х₁ - 20 х₂; min

Таблиця 2 ітерація

j	Базисні змінні	х1	х2	х3	х4	х5	bi	= bi / aij	Контроль
1	х2	2 / 7	1	2/ 7	0	0	100	100/(2/7)=350	101 4/7
2	х4	13 / 7	0	-1/ 7	1	0	190	190/(13/7)102	192 5/7
3	х5	5 / 7	0	-2/ 7	0	1	50	50/(5/7)=70	51 3/7
4	Z (x)	30 / 7	0	-40/ 7	0	0	-2000	-	-2001 3/7

х₂ = 100 - (2/7) х₁ - (2/7)х₃; Z (x) + (30/7) х₁ - (40/7)х₃ = -2000 ;

Z = 10х₁ + 20 (100 - (2/7)х₁ - (2/7)х₃ ) = 2000 + (30/7)х₁ - (40/7)х₃;

Z = - 2000 + (40/7)х₃ - (30/7)х₁ = - 2000;

Таблиця 3 ітерація

j	Базисні змінні	х1	х2	х3	х4	х5	bi	= bi / aij	Конт-роль
1	х2	0	1	14/ 35	0	-2/5	80	-	81
2	х4	0	0	21/35	1	-13/5	60	-	59
3	х1	1	0	-2/ 5	0	7/5	70	-	72
4	Z (x)	0	0	-28/ 7	0	-6	-2300	-

х₁ = 70 + (2/5) х₃ - (7/5)х₅; Z (x) - (28/7) х₃ - 6 х₅ = -2300 ;

Z = 2000 + (30/7) (70 + (2/5)х₃ - (7/5)х₅ ) - (40/7) х₃= 2300 - 6х₅ - (28/7)х₃;

Z = - 2300 + 6х₅ + (28/7)х₃ = - 2300; х₃ = х₅ = 0.

У цільовій функції усі вільні змінні від'ємні - опорний план Х* = (70; 80; 0; 60; 0) є оптимальним. Задача розв'язана.

Z*_max = (-Z*)_min = +2300.

Стереометрично ідея методу полягає у тому, що:

знаходять будь-яку вершину багатогранника розв'язків;

рухаються вздовж того з ребер, по якому функція зменшується (збільшується) до іншої вершини багатогранника розв'язків;

як потрапляють у вершину, з якої у всі боки функція зростає (спадає), так знаходять мінімум (максимум).

Нагадаємо ще раз:

якщо вектор розв'язків задовольняє усім обмеженням, так він має назву плану;

якщо план відповідає вершині багатогранника розв'язків (усі вільні змінні дорівнюють нулеві), так він має назву опорного плану;

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

Критерій оптимальності за симплекс-таблицею.

Якщо форма мінімізується (максимізується) і у рідку цільової функції відсутні додатні числа (від'ємні числа), за винятком стовпчика опорний розв'язок (b₁), так опорний план є оптимальним.

Коефіцієнти рядка цільової функції інтерпретують як приріст цільової функції при збільшенні вільної невідомої на одиницю. Приріст додатній, якщо коефіцієнт від'ємний, і навпаки від'ємний, якщо коефіцієнт додатній.

Стовпець “j” є вирішальним, як у цьому стовпцю, оцінка коефіцієнта при невідомій у цільовій функції найбільша за модулем, тобто

С_j = max.

Змінну “x_j” у вирішальному стовпцю знаходять за співвідношенням

b_i

min = , (f_ij 0; b_i 0);

a_ij

яке має назву симплекса , що і дає у свою чергу назву методу. Відповідний елемент a_ij назву ключового елемента, або центру таблиці.

Вільну змінну, яка відповідає вирішальному стовпчику, залучають до базисних змінних, а базисну змінну, яка відповідає мінімальному симплексу, відповідно перетворюють на вільну змінну.

Елементи симплексної строки нової таблиці дорівнюють елементам старої таблиці, поділеним на “ a_ij” - ключовий елемент (центр). Усі інші елементи вирішального стовпця прирівнюють до “0” (за виключенням ключового, якій дорівнює одиниці) шляхом жорданового перетворення; це стосується також цільової функції.

Можливі випадки розв'язку задачі лінійного програмування симплексним методом.

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

Необмеженість задачі лінійного програмування виникає, як у якомусь стовпчику змінних у випадку мінімізації “с_j” 0 , а усі елементи таблиці “а_ij” 0; у випадку максимізації “с_j” 0, а усі “а_ij” 0. Це позначає, що область припустимих розв'язків задачі не обмежена знизу (мінімізація) або зверхне (максимізація).

Послідовність використання симплекс-методу:

звести задачу лінійного програмування до задачі мінімізації у канонічній формі (обмеження-рівняння; b_і 0);

поділити змінні на базисні та вільні і отримати базисне припустиме рішення (базисні змінні невід'ємні; вільні змінні дорівнюють нулеві);

знайти вираз базисних змінних та цільової функції через вільні змінні;

за знаком коефіцієнтів при невідомих (с_j 0) у цільовій функції з'ясувати, чи є рішення оптимальне

Z = с₀ + с₁х₁ + с₂х₂ + . . . + с_nх_n ; (c_j 0 - мінімізація); або яку вільну змінну можливо підвищити від нуля та перевести у базис і відповідно, яку базисну змінну перевести у вільні змінні;

знайти мінімальне додатне співвідношення “b_i” вільних членів рівнянь-обмежень до коефіцієнтів “a_ij” при новій вільній змінній, тобто з'ясувати, яку базисну змінну необхідно перевести у вільні змінні;

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

Приклад.

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

Z = 4х₁ + 2х₂ - х₃,

за умов обмежень

х₁ + х₂ + х₃ 8;

х₂ + х₃ 10;

х₁ + х₂ + 2х₃ 30;

Перетворимо першу нерівність за допомогою змінної х₄

х₁ + х₂ + х₃ - х₄ 8;

До цих трьох обмежень додамо штучні змінні у₁, у₂, у₃ (х₅, х₆, х₇). Цільова функція набуває вигляду

Z = 4х₁ + 2х₂ - х₃ + 0 х₄;

обмеження:

х₁ + х₂ + х₃ - х₄ + у₁ + 0 у₂ + 0 у₃ = 8;

0 х₁ + х₂ + х₃ + 0 х₄ + 0 у₁ + у₂ + 0 у₃ = 10;

х₁ + х₂ + 2х₃ + 0 х₄ + 0 у₁ + 0 у₂ + у₃ = 30;

Вектори у₁ ( 0 ); у₂ ( 1 ); у₃ ( 0 ) утворюють базис

тримірний у загальному симівимірному просторі х₁, х₂, х₃, х₄, у₁, у₂, у₃.

Кількість невідомих n = 7; обмежень m = 3; вільних змінних n - m = 7 - 3 = 4.

Базові змінні у₁, у₂, у₃; вільні змінні х₁, х₂, х₃, х₄. Базове опорне рішення

х (0; 0; 0; 0; 1; 1; 1), Z (х) = 0.

Розв'язок задачі надамо у вигляді симплекс-таблиці.

Таблиця

і	базисні змінні	х1	х2	х3	х4	у1	у2	у3	bi	=bi/fij
1	у1	1	1	1	-1	1	0	0	8	8/1
2	у2	0	1	1	0	0	1	0	10	10/1
3	у3	1	1	2	0	0	0	1	30	30/1
4	-Z	4	2	-1	0	0	0	0	0
1	х2	1	1	1	-1	1	0	0	8	-8/1
2	у2	-1	0	0	1	-1	1	0	2	2/1
3	у3	0	0	1	1	-1	0	1	22	22/1
4	-Z	2	0	-3	2	-2	0	0	-16
1	х2	0	1	1	0	0	1	0	10	10/1
2	х4	-1	0	0	1	-1	1	0	2	2/-1
3	у3	1	0	1	0	0	-1	1	20	20/1
4	-Z	4	0	-3	0	0	-2	0	-20
1	х2	0	1	1	0	0	1	0	10	10/1
2	х4	0	0	1	1	-1	0	1	22	22/0
3	х1	1	0	1	0	0	-1	1	20	20/-1
4	-Z	0	0	-7	0	0	2	-4	-100
1	у2	0	1	1	0	0	1	0	10
2	х4	0	0	1	1	-1	0	1	22
3	х1	1	1	2	0	0	0	1	30
4	-Z	0	-2	-9	0	0	0	-4	-120

Х* (30; 0; 0; 22; 0; 10; 0); Z = 4х₁ + 2х₂ - х₃ = 4 30 = 120.

Z* = 120 - 2х₂ - 9х₃ - 4у₃ = 120.

Тема 4. Теорія двоїстості та двоїсті оцінки в аналізі розв'язків лінійних оптимізаційних моделей

Основна та двоїста задачі як пара взаємноспряжених задач лінійного програмування.

Дві задачі лінійного програмування називаються взаємно двоїстими, якщо виконуються такі умови:

матриці системи обмежень двох задач є транспонованим, одна відносно другої;

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

коефіцієнти оптимізуючої форми однієї задачі є вільними членами системи обмежень другої задачі і навпаки;

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

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

Економічна інтерпретація двоїстої задачі лінійного програмування

Розглянемо приклад виробничої задачі.

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

Таблиця

Ресурси	Продукція, хj	Обсяг ресурсів	Варт. од. ресурсу, уі
	х1	х2	х3
Робоча сила, людино-год.	15 а11	20 а12	25 а13	1200 b1	у1 (х4)
Сировина, m	2 а21	3 а22	2,5 а23	150 b2	у2 (х5)
Енерговитрати, кВт - год.	35 а31	60 а32	60 а33	3000 b3	у3 (х6)
Вартість одиниці продукції	300 с1	250 с2	450 с3	-	-

(у₄) (у₅) (у₆)

Потрібно знайти кількість кожного з різновидів продукції, які забезпечують найбільшу вартість загальної продукції. З економічної точки зору вартість ресурсів, використаних на виготовлення одиниці продукції, не може бути меншою, ніж вартість самої одиниці продукції, інакше це позначає, що вартість частини одиниці продукції виникає з повітря. Для якої завгодно виробничої програми вартість виробленої продукції не перевищує загальної вартістю наявних ресурсів. Проаналізуємо отримані результати. Розв'язок прямої задачі вказує на то, що необхідно виробити першої продукції х₁ = 60 одиниць, третьої продукції х₃ = 12 одиниць, другу продукцію виробляти непотрібно (х₂ = 0). Використані повністю ресурси робочої сили (х₄ = 0) та сировини (х₅ = 0), залишок енерговитрат складає х₆ = 180 кВт - год. Розв'язок двоїстої задачі вказує на те, що ресурси перший (у₁ 0) та другий (у₂ 0) використані повністю, третій ресурс надмірний (у₃ = 0). Додаток першого обмеженого ресурсу на одиницю збільшує цільову функцію прямої задачі на 12 одиниць (зростає вартість, бо у₁ = 12), другого обмеженого ресурсу на одиницю збільшує Z(x), цільову функцію, на 60 одиниць (у₂ = 60). Збільшення третього ресурсу (необмеженого) - енерговитрату околиці оптимального плану не викликає змін цільової функції. Як у_n = 0, у₆ = 0, так це позначає, що виробництво продукції першої та третьої не є збитковим; у₅ = 170 - це позначає, що виготовлення одиниці другої продукції викликає збиток у 170 грошових одиниць. перевіримо це таким чином: вартість ресурсів на другу продукцію складає

а₁₂у₁ +а₂₂у₂ + а₃₂у₃ = 20 12 + 3 60 + 60 0 = 420,

водночас вартість другого виробу складає 250; тобто збиток = 420 - 250 = 170.

Арифметична перевірка задач.

Основна задача:

15 60 + 20 0 + 2,5 12 = 1200;

2 60 + 3 0 + 2,5 12 = 150;

35 60 + 60 0 + 60 12 = 2820 3000№

х₄ = 0;

х₅ = 0;

х₆ = 180 0;

у₁ = 12 0;

у₂ = 60 0;

у₃ = 0;

Двоїста задача:

15 12 + 2 60 + 35 0 = 300;

20 12 + 3 60 + 60 0 = 420 250;

25 12 + 2,5 60 + 60 0 = 450;

у₄ = 0;

у₅ = 170 0;

у₆ - 0;

х₁ = 60 0;

х₂ = 0;

х₃ = 12 0.

Стійкість оптимальних планів прямої та двоїстої задач обумовлені зміною обмежень “ С₂ 170;” “С_j, які не викликають порушень умов оптимізму. У нашому прикладі b₃ = b₁ = 0. Це позначає, що збільшення без обмежень, та зменшення менш ніж на 180 енерговитрат не змінює оптимального плану задачі.

У оптимальному плані двоїстої задачі значення змінної (у_і*) чисельно дорівнює частковій похідній функції

_max (b₁,b₂, . . ,b_m) за аргументом “у_і”ю. тобто

_max = y_i*.

b_i

Це вочевидь співвідношення вказує на те, що зміна “bі” викликає зміну _max, яка визначається зміною “у_і”. Але на прикладі ми бачили, що як обмеження не є критичним, так зміна “bі” ресурсу у околиці оптимального плану не викликає зміни цільової функції. Тому важливо визначити інтервали зміни кожного з вільних членів системи обмежень основної задачі. або коефіцієнтів цільової функції двоїстої задачі, у яких оптимальний план двоїстої задачі не змінюється. Це має місце для усіх значень (b_i + b_i), при котрих стовпець вектора Р₀останньої симплекс-таблиці розв'язання основної задачі не містить від'ємних чисел, тобто коли серед компонентів вектора