Техніко-економічні показники компонентів бензину

Показник	Компонента бензину
	№ 1	№ 2	№ 3	№4
Октанове число	68	72	80	90
Вміст сірки, %	0,35	0,35	0,30	0,20
Наявний обсяг, т	700	600	500	300
Вартість, грош. од./т	40	45	60	90

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

Побудова економіко-математичної моделі.

Позначимо через х_j кількість j-го компонента в суміші (т), j = 1,2,3,4.

Перше обмеження забезпечує потрібне значення октанового числа в суміші:

.

Вміст сірки в суміші має не перевищувати 0,3 %:

,

а загальна маса утвореної суміші має дорівнювати 1000 т:

.

Використання кожного компонента має не перевищувати його наявного обсягу: x₁≤700; x₂≤600; x₃≤500; x₄≤300.

Собівартість суміші визначається за формулою:

.

Загалом, економіко-математична модель задачі має вигляд:

за умов:

.

У часник експедиції складає рюкзак, і йому необхідно розв'язати питання про те, які взяти продукти. У розпорядженні є м’ясо, борошно, сухе молоко, цукор. У рюкзаку залишилось для продуктів лише 45 дм³ об’єму, до того ж необхідно, щоб загальна маса продуктів не перевищувала 35 кг. Лікар експедиції рекомендував, щоб м’яса (за масою) було більше, ніж борошна принаймні удвічі, борошна не менше, ніж молока, а молока хоча б у вісім разів більше, ніж цукру. Скільки і яких продуктів потрібно покласти в рюкзак, щоб сумарна калорійність продуктів була найбільшою? Характеристики продуктів наведені в табл. 2.2.

Таблиця 2.2

Характеристики продуктів

Показники	Продукт
	м’ясо	борошно	молоко	цукор
Об’єм (дм3/кг)	1	1,5	2	1
Калорійність (ккал/кг)	1500	5000	5000	4000

Побудова економіко-математичної моделі.

Позначимо через х₁, х₂, х₃, х₄ масу (в кг) м’яса, борошна, молока і цукру відповідно.

Сумарна маса продуктів має не перевищувати 35 кг:

х₁+х₂+х₃+х₄ ≤35,

а об’єм, який вони мають займати, — не більше 45 дм³:

.

Крім того, мають виконуватися співвідношення стосовно пропорцій за масою продуктів:

а) м’яса принаймні удвічі більше, ніж борошна, отже: x₁≥2x₂;

б) борошна не менше, ніж молока: x₂≥x₃;

в) молока хоча б у вісім разів більше, ніж цукру: x₃≥8x₄.

Калорійність всього набору продуктів можна визначити так:

.

Отже, економіко-математична модель задачі має вигляд:

за умов:

.

Транспортна задача: розглядається m пунктів виробництва та n пунктів споживання деякої однорідної продукції. Відомі обсяги виробництва продукції у кожному i-му пункті – та потреби кожного j-го пункту споживання – . Також задана матриця розмірністю m×n, елементи якої є вартостями транспортування одиниці продукції з i-го пункту виробництва до j-го пункту споживання. Необхідно визначити оптимальні обсяги перевезень продукції з урахуванням наявності продукції у виробників та забезпечення вимог споживачів.

Критерій оптимальності: мінімальна сумарна вартість перевезень.

Позначимо через х_ij обсяг продукції, що перевозиться від i-го виробника до j-го споживача.

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

за умов:

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

Ф ермерське господарство спеціалізується на вирощуванні озимої пшениці і має три ділянки землі площею S₁ = 40 га, S₂ = 90 га, S₃ = 55 га. Враховуючи наявну кількість посівного матеріалу, є можливість засіяти всю площу озимою пшеницею трьох сортів. Кількість пшениці сорту «Миронівська-808» забезпечить посів на 80 га, «Безоста-1» — 60 га та «Одеська — 51» — 45 га. Урожайність сорту «Миронівська-808» на даних ділянках становить відповідно 41 ц/га, 40 ц/га, 46 ц/га. Аналогічно для сорту «Безоста-1» маємо: 38 ц/га, 41 ц/га, 45 ц/га, а для «Одеської-51» — 30 ц/га, 28 ц/га, 40 ц/га.

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

Побудова економіко-математичної моделі.

Позначимо через х_ij площу (га) і-ої земельної ділянки, що буде засіяна j-м сортом озимої пшениці (домовимося, що сорти «Миронівська-808», «Безоста-1», «Одеська-51» відповідатимуть номерам 1, 2, 3), (і = 1, 2, 3), (j = 1, 2, 3).

Тоді використання земельних угідь описуватиме така система обмежень:

;

;

.

Використання посівного матеріалу формально можна описати так:

;

;

.

Валовий збір зерна розраховується як сума добутків урожайностей відповідних сортів пшениці на їх посівні площі, тобто:

Отже, економіко-математична модель задачі загалом буде мати вигляд:

за умов:

.

Наведені приклади економіко-математичних моделей еконо­мічних процесів та явищ є навчальними. Адекватні економіко-математичні моделі будуть значно складнішими.

2.2. Загальна економіко-математична модель задачі лінійного програмування

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

(2.1)

за умов:

(2.2)

(2.3)

Отже, потрібно знайти значення змінних x₁, x₂, …, x_n, які задовольняють умови (2.2) і (2.3), і цільова функція (2.1) набуває екстремального (максимального чи мінімального) значення.

Для довільної задачі математичного програмування у § 1.2 були введені поняття допустимого та оптимального планів.

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

Вектор Х = (х₁, х₂, …, х_n), координати якого задовольняють систему обмежень (2.2) та умови невід’ємності змінних (2.3), називається допустимим розв’язком (планом) задачі лінійного програмування.

Допустимий план Х = (х₁, х₂, …, х_n) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи (2.2) у вигляді рівностей, а також обмеження (2.3) щодо невід’ємності змінних.

Опорний план Х = (х₁, х₂, …, х_n), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений.

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

Задачу (2.1)—(2.3) можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (2.2) всі b_i (i = 1, 2, …, m) невід’ємні, а всі обмеження є рівностями.

Якщо якесь b_i від’ємне, то, помноживши i-те обмеження на (– 1), дістанемо у правій частині відповідної рівності додатне значення. Коли i-те обмеження має вигляд нерівності а_i1х₁+ а_i2х₂+…+а_inx_n ≤ b_i, то останню завжди можна звести до рівності, увівши додаткову змінну x_n+1: a_i1x₁+a_i2x₂+…+a_in x_n+x_n+1= b_i.

Аналогічно обмеження виду а_k1x₁ + a_k2x₂ + … + a_knx_n ≥ b_k зводять до рівності, віднімаючи від лівої частини додаткову змінну х_n+2, тобто: a_k1x₁+a_k2x₂+…+a_knx_n–x_n+2=b_k (х_n+1 ≥ 0, х_n+2 ≥ 0).

Доведемо, що заміна нерівностей рівняннями за допомогою введення додаткових змінних не змінить розв’язку початкової задачі. Розглянемо лінійну нерівність з n невідомими:

(2.4)

Для зведення нерівності (2.4) до рівняння необхідно до її лівої частини додати деяку невід’ємну величину х_n+1 ≥ 0. У результаті дістаємо лінійне рівняння, яке містить n+1 змінну:

a₁x₁ + a₂x₂ + … + a_nx_n + x_{n + 1} = b. (2.5)

Теорема 2.1. Кожному розв’язку нерівності (2.4) відповідає єдиний розв’язок рівняння (2.5), який одночасно є розв’язком нерівності (2.4), і, навпаки, кожному розв’язку рівняння (2.5) і нерівності (2.4) відповідає єдиний розв’язок нерівності (2.4).

Доведення: Нехай X^* — розв’язок нерівності (2.4), тоді підстановкою нерівність виконується:

.

Перенесемо ліву частину даної нерівності в праву і позначимо вираз у правій частині через , тобто:

Отже, розв’язок задовольняє рівняння (2.5) і водночас нерівність (2.4). Дійсно, і при підстановці в рівняння маємо:

Навпаки, нехай Y^* задовольняє рівняння (2.5) і нерівність (2.4), тобто:

і .

Тоді, відкидаючи в лівій частині рівності невід’ємну величину , отримаємо нерівність:

.

2.3. Форми запису задач лінійного програмування

Задачу лінійного програмування зручно записувати за допомогою знака суми «». Справді, задачу (2.1)—(2.3) можна подати так:

за умов:

(2.6)

Ще компактнішим є запис задачі лінійного програмування у векторно-матричному вигляді:

max(min) Z = CX

за умов:

АХ = А₀; (2.7)

Х ≥ 0,

де

є матрицею коефіцієнтів при змінних;

— вектор змінних; — вектор вільних членів;

С = (с₁, с₂, …, с_п) — вектор коефіцієнтів при змінних у цільовій функції.

Часто задачу лінійного програмування зручно записувати у векторній формі:

max(min)Z = CX

за умов:

A₁x₁ + A₂x₂ + … + A_nx_n = A₀; (2.8)

X ≥0,

де

є векторами коефіцієнтів при змінних.

2.4. Геометрична інтерпретація задачі лінійного програмування

Розглянемо на площині х₁Оx₂ сумісну систему лінійних нерівностей:

(2.9)

Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою a_i1x₁ + a_i2x₂ = b_i (i = 1, 2, ...,т). Умови невід’ємності змінних визначають півплощини з граничними прямими х₁ = 0 та х₂ = 0. Система сумісна, тому півплощини як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожної з яких є розв’язком даної системи (рис. 2.1).

С

Рис. 2.1

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

Якщо в системі обмежень (2.9) буде три змінних, то кожна нерів­ність геометрично визначатиме півпростір тривимірного простору, граничними площинами кот­рого будуть a_i1x₁ + a_i2x₂ + a_i3x₃ = b_i (i = 1, 2, ...,т), а умови невід’єм­ності — півпростори з гранич­ними площинами х_j = 0 (j = 1, 2, 3), де і — номер обмеження, а j — номер змінної. Якщо система обмежень сумісна, то ці півпростори як опуклі множини, пере­тинаючись, утворять у тривимірному просторі спільну частину, що називається багатогранником розв’язків. Він може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.

Нехай у системі обмежень (2.9) кількість змінних більша, ніж три: х₁, х₂,… х_n; тоді кожна нерівність визначає півпростір n-вимірного простору з граничною гіперплощиною а_i1x₁ + a_i2x₂ + a_i3x₃ + … +a_inx_n = b_i (i = 1, 2, ...,т). Кожному обмеженню виду (2.9) відповідають гіперплощина та напівпростір, який лежить з одного боку цієї гіперплощини, а умови невід’ємності — півпрос­тори з граничними гіперплощинами х_j = 0 (j = 1, 2, 3, ..., n).

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

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

Цільову функцію

в п-вимірному просторі основних змінних можна геометрично інтерпретувати як сім’ю паралельних гіперплощин, положення кож­ної з яких визначається значенням параметра Z.

Розглянемо геометричну інтерпретацію задачі лінійного про­грамування на прикладі. Нехай фермер прийняв рішення вирощу­вати озиму пшеницю і цукрові буряки на площі 20 га, відвівши під цукрові буряки не менше як 5 га. Техніко-економічні показники вирощування цих культур маємо у табл. 2.3:

Таблиця 2.3

ПОКАЗНИКИ ВИРОЩУВАННЯ СІЛЬСЬКОГОСПОДАРСЬКИХ КУЛЬТУР

Показник (із розрахунку на 1 га)	Озима пшениця	Цукрові буряки	Наявний ресурс
Затрати праці, людино-днів	5	25	270
Затрати праці механізаторів, людино-днів	2	8	80
Урожайність, тонн	3,5	40	—
Прибуток, тис. грн./га	0,7	1	—

Критерієм оптимальності є максимізація прибутку.

Запишемо економіко-математичну модель структури виробницт­ва озимої пшениці та цукрових буряків, ввівши такі позначення:

х₁ — шукана площа посіву озимої пшениці, га;

х₂ — шукана площа посіву цукрових буряків, га.

Задача лінійного програмування має такий вигляд:

max Z = 0,7x₁ + x₂ (2.10)

за умов:

x₁ + x₂ ≤ 20; (2.11)

5x₁ + 25x₂ ≤ 270; (2.12)

2x₁ + 8x₂ ≤ 80; (2.13)

x₂ ≥ 5; (2.14)

x₁ ≥ 0, x₂ ≥ 0. (2.15)

Геометричну інтерпретацію задачі зображено на рис. 2.2.

Область допустимих розв’язків цієї задачі дістаємо так. Кожне обмеження, наприклад х₁ + х₂ 20, задає півплощину з граничною прямою х₁ + х₂ = 20. Будуємо її і визначаємо півплощину, яка описується нерівністю х₁ + х₂ 20. З цією метою в нерівність х₁ + х₂   20 підставляємо координати характерної точки, скажімо, х₁ = 0 і х₂ = 0. Переконуємося, що ця точка належить півплощині х₁ + х₂   20. Цей факт на рис. 2.2 ілюструємо відповідною напрямленою стрілкою.

Рис. 2.2. Область допустимих розв’язків задачі

Аналогічно будуємо півплощини, які відповідають нерівностям (2.11)—(2.15). У результаті перетину цих півплощин утворюється область допустимих розв’язків задачі (на рис. 2.2 — чотирикутник ABCD). Цільова функція Z = 0,7x₁ + x₂ являє собою сім’ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z = 0, то маємо 0,7х₁ + х₂ = 0. Ця пряма проходить через початок системи координат. Коли Z = 3,5, то маємо пряму 0,7х₁ + х₂ = 3,5.

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

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

Властивість 1. (Теорема 2.2) Множина всіх планів задачі лінійного програмування опукла.

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

Властивість 3. (Теорема 2.4) Якщо відомо, що система векторів A₁, A₂, …, A_k (k ≤ n) у розкладі A₁x₁ +A₂x₂ + … + A_nx_n = A₀, X ≥ 0 лінійно незалежна і така, що A₁x₁ + A₂x₂ + … + A_kx_k = A₀, де всі x_j ≥ 0, то точка X = (x₁, x₂, …, x_k, 0, …, 0) є кутовою точкою багатогранника розв’язків.

Властивість 4. (Теорема 2.5) Якщо X = (x₁, x₂, …, x_n) — кутова точка багатогранника розв’язків, то вектори в розкладі A₁x₁ + + A₂x₂ + … + A_nx_n = A₀, X ≥ 0, що відповідають додатним x_j, є лінійно незалежними.

Доведемо сформульовані теореми.

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

Доведення. Необхідно довести, що коли X₁ та X₂ — плани задачі лінійного програмування (2.1)—(2.3), то їх опукла комбінація X = λ₁X₁ + λ₂X₂, λ₁ ≥ 0, λ₂ ≥ 0, λ₁ + λ₂ = 1 також є планом задачі.

Так як X₁ і X₂ — плани задачі, то виконуються такі співвідношення:

AX₁ = A₀, X₁ ≥ 0; AX₂ = A₀, X₂ ≥ 0.

Якщо підставити в систему обмежень значення X, то отримаємо:

AX = A(λ₁X₁ + λ₂X₂) = λ₁AX₁ + λ₂AX₂ = λ₁A₀ + λ₂A₀ = (λ₁ + λ₂)A₀ = A₀.

Отримали, що X задовольняє систему обмежень задачі лінійного програмування (2.2), і оскільки Х₁ ≥ 0, Х₂ ≥ 0, λ₁ ≥ 0, λ₂ ≥ 0, то й Х ≥ 0, тобто задовольняють і умову (2.3). У такий спосіб доведено, що Х — план задачі лінійного програмування.

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

Д

Рис. 2.3. Багатокутник розв’язків задачі у двовимірному просторі

оведення. Припустимо, що багатогранник розв’язків задачі обмежений і має скінченну кількість кутових точок. Позначимо його через Q. У двовимірному просторі Q має вид багатокут­ника, що зображено на рис. 2.3. Позначимо кутові точки через Х₁, Х₂, ..., Х_р, а оптимальний план — Х₀.

Задача (2.1) — (2.3) розв’я­зується на максимум, отже, при будь-якому Х із Q для значення Х₀ виконується нерівність F(X₀) ≥ F(X). Якщо Х₀ — кутова точка, то перша частина теореми доведена. Припустимо, що Х₀ не є кутовою точкою, тоді Х₀ є точкою, яка належить опуклій множині (дове­дено в попередній теоремі). Отже, її можна подати як опуклу лінійну комбінацію кутових точок множини Q, тобто

X₀ = λ₁X₁ + λ₂X₂ + … + λ_pX_p,

.

У зв’язку з тим, що F(X) — лінійна функція, отримаємо:

(2.16)

У такому розкладі серед значень F(X_i) вибираємо най­більше (припустимо, що воно відповідає кутовій точці і позначимо його через m, тобто . Замінимо в (2.16) кожне значення F(X_i) цим найбільшим значенням. Оскільки , то

.

За припущенням Х₀ — оптимальний план, отже, з одного боку, F(X₀) ≥ F(X_k) = m, а з другого, доведено, що F(X₀) ≤ m, значить, F(X₀) = m = F(X_k), де X_k — кутова точка. Отже, лінійна функція досягає максимального значення в кутовій точці (X_k).

Для доведення другої частини теореми припустимо, що F(X) набирає максимальних значень більше, ніж в одній кутовій точці, наприклад у точках Х₁, Х₂, ..., Х_q, (1 ≤ q ≤ p), тоді F(X₁) = F(X₂) = … = F(X_q) = m. Якщо Х опукла лінійна комбінація цих кутових точок, то:

Рис. 2.4. Багатокутник розв’язку задачі у двовимірному просторі з необмеженою областю

тобто лінійна функція F набирає максимальних значень у довільній точці Х, яка є опуклою лінійною комбінацією кутових точок Х₁, Х₂, ..., Х_q.

Зауваження. Якщо багатокут­ник розв’язків — необмежена область (рис. 2.4), то не кожну то­чку можна подати у вигляді опук­лої лінійної комбінації її кутових точок. У такому разі задачу ліній­ного програмування з багатокут­ником розв’язків, що є необмеже­ною областю, можна звести до за­дачі з обмеженою областю, ввів­ши в систему додаткове обмежен­ня х₁ + х₂ ≤ L, де L — достатньо велике число. Введення цього об­меження означає відтинання пря­мою х₁ + х₂ = L від багатокутної необмеженої об­ласті обмеженого багатокутника, для якого виконується наведена теорема.

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

Теорема 2.4. Якщо відомо, що система векторів (k ≤ n) у розкладі , лінійно незалежна і така, що , де всі x_j ≥ 0, то точка X = (x₁, x₂, …, x_k, 0, …, 0) є кутовою точкою багатогранника розв’язків.

Доведення. Припустимо, що точка Х не є кутовою. Тоді вона може бути виражена опуклою лінійною комбінацією двох інших точок Х₁ та Х₂ багатокутника розв’язків, тобто:

Компоненти векторів Х₁ та Х₂, значення λ₁ і λ₂ невід’ємні і останні n – k компонентів вектора Х дорівнюють нулю, тому відповідні n – k компонент векторів Х₁ та Х₂ також мають дорівнювати нулю, тобто

,

.

Оскільки Х₁ та Х₂ — плани, то

,

.

Віднімаючи від першого рівняння друге, отримаємо:

.

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

.

Звідси:

Отже, Х неможливо подати як опуклу лінійну комбінацію двох інших точок багатокутника розв’язків. Значить, Х — кутова точка.

Теорема 2.5. Якщо — кутова точка багатогранника розв’язків, то вектори в розкладі , , що відповідають додатним , є лінійно незалежними.

Доведення. Не порушуючи загальності, можна вважати нерівними нулю перші k елементів вектора Х, отже,

.

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

.

За умовою

.

Задамо деяке число , помножимо на нього першу рівність, далі результат спочатку додамо до другого, а потім віднімемо від другого рівняння:

,

.

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

.

Всі х_і > 0, тому число можна вибрати настільки малим, що всі перші компоненти та набуватимуть додатних значень, тоді та — плани. При цьому , тобто Х — опукла лінійна комбінація точок Х₁ та Х₂, що суперечить умові теореми, оскільки Х — кутова точка.

Припущення стосовно лінійної залежності векторів привело до суперечності. Отже, воно є неправильним, а система векторів — лінійно незалежна.

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

Наслідок 2. Кожній кутовій точці багатокутника розв’язків відповідає k≤m лінійно незалежних векторів системи .

З наведених властивостей можна висновувати:

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

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

2. кожний опорний план відповідає кутовій точці багато­гранника розв’язків.

Тому для розв’язання задачі лінійного програмування необ­хідно досліджувати лише кутові точки багатогранника (опорні плани), не включаючи до розгляду внутрішні точки множини допустимих планів.

2.6. Графічний метод розв’язування задач лінійного програмування

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

Розглянемо задачу.

Знайти

(2.17)

за умов:

(2.18)

. (2.19)

Припустимо, що система (2.18) за умов (2.19) сумісна і багатокутник її розв’язків обмежений.

Згідно з геометричною інтерпретацією задачі лінійного програмування (§ 2.4) кожне і-те обмеження-нерівність у (2.18) визначає півплощину з граничною прямою (і = 1, 2, …, т). Системою обмежень (2.18) графічно можна зобразити спільну частину, або переріз усіх зазначених півплощин, тобто множину точок, координати яких задовольняють всі обмеження задачі — багатокутник розв’язків.

Умова (2.19) невід’ємності змінних означає, що область допустимих розв’язків задачі належить першому квадранту системи координат двовимірного простору. Цільова функція задачі лінійного програмування геометрично інтерпретується як сім’я паралельних прямих с₁х₁ + с₂х₂ = const.

Скористаємося для графічного розв’язання задачі лінійного програмування властивостями, наведеними в § 2.5:

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

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

Алгоритм графічного методу розв’язування задачі лінійного програмування складається з таких кроків:

1. Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (2.18) знаків нерівностей на знаки рівностей.

2. Визначаємо півплощини, що відповідають кожному обмеженню задачі.

3. Знаходимо багатокутник розв’язків задачі лінійного програмування.

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

5. Будуємо пряму с₁х₁ + с₂х₂ = const, перпендикулярну до вектора .

6. Рухаючи пряму с₁х₁ + с₂х₂ = const в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника роз­в’язків, де цільова функція набирає екстремального значення.

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

У разі застосування графічного методу для розв’язування задач лінійного програмування можливі такі випадки:

1. Цільова функція набирає максимального значення в єдиній вершині А багатокутника розв’язків (рис. 2.5).

2. Максимального значення цільова функція досягає в будь-якій точці відрізка АВ (рис. 2.6). Тоді задача лінійного програмування має альтернативні оптимальні плани.

Рис. 2.5 Рис. 2.6

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

4. Задача лінійного програмування має оптимальний план за необмеженої області допустимих розв’язків (рис. 2.9 і 2.10). На рис. 2.9 у точці В маємо максимум, на рис. 2.10 у точці А — мінімум, на рис. 2.11 зображено, як у разі необмеженої області допустимих планів цільова функція може набирати макси­мального чи мінімального значення у будь-якій точці променя.

Рис. 2.7 Рис. 2.8

Рис. 2.9 Рис. 2.10

Р

Рис. 2.11

озв’язувати графічним мето­дом можна також задачі лінійно­го програмування n-вимірного простору, де , якщо при зведенні системи нерівностей задачі до системи рівнянь шляхом введення додаткових змінних кількість змінних n на дві більша, ніж число обмежень m, тобто n−m=2.

Тоді, як відомо з курсу вищої математики, можна дві з n змінних, наприклад х₁ та х₂, вибрати як вільні, а інші m зробити базисними і виразити через вільні. Припустимо, що це зроблено. Отримаємо рівнянь вигляду:

Оскільки всі значення , то мають виконуватись умови:

,

(2.19.1)

Розглянемо, як можна зобразити ці умови геометрично. Візьмемо, наприклад, першу з них:

Узявши величину х₃ рівною своєму крайньому значенню — нулю, отримаємо рівняння:

.

Це рівняння прямої. Для такої прямої , по одну сторону від неї , а по другу — . Відмітимо ту сторону прямої , де .

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

У такий спосіб отримують n – 2 прямі та дві осі координат ( , ). Кожна з них визначає півплощину, де виконується умова . Частина площини в належить водночас всім півплощинам, утворюючи багатокутник допустимих розв’язків.

Припустимо, що в задачі необхідно знайти максимальне значення функціонала:

F = c₁x₁+c₂x₂+…+c_nx_n.

Підставивши вирази для x₃, x₄, x₅, ..., x_n з (2.19.1) у цей функціонал, зведемо подібні доданки і отримаємо вираз лінійної функ­ції F всіх n змінних лише через дві вільні змінні x₁ та x₂:

,

де — вільний член, якого в початковому вигляді функціонала не було.

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

Р озв’язати графічним методом задачу лінійного програмування

.

Розв’язання. Маємо n = 7 — кількість змінних, m = 5 — кількість обмежень. Виберемо як вільні змінні х₁ та х₂ і виразимо через них всі інші базисні змінні. З першого рівняння маємо:

(2.19.2)

З третього рівняння:

, (2.19.3)

а з четвертого:

. (2.19.4)

Підставляючи (2.19.2) в друге рівняння системи і (2.19.4) в останнє, розв’язуємо їх відносно х₄ та х₇. Отримаємо:

;

.

Далі за алгоритмом беремо х₁ = 0 та х₂ = 0 — координатні осі; інші обмежуючі прямі знаходимо, узявши х₃ = 0, х₄ = 0, х₅ = 0, х₆ = 0, х₇ = 0. Багатокутник допустимих розв’язків зображено на рис. 2.12.

Рис. 2.12

Знайдемо вигляд функціонала, вираженого через х₁ та х₂. Для цього знайдені щойно вирази для х₃, х₄, х₅, х₆ та х₇ через вільні змінні х₁ і х₂ підставимо у функціонал і, звівши подібні члени, отримаємо: . Відкидаючи вільний член, маємо: . Будуємо вектор (–5, –2), перпендикулярно до нього — пряму F^'. Рухаючи пряму F^' в напрямку, протилежному (необхідно знайти мінімальне значення функції F), отримаємо точку мінімуму — А (рис. 2.13).

Рис. 2.13

У точці А перетинаються дві обмежуючі прямі: х₆ = 0 та х₇ = 0. Отже, для відшукання її координат необхідно розв’язати систему рівнянь:

Розв’язком системи є = 8,5; = 5. Підставивши ці значення у відповідні вирази, знайдемо оптимальні значення базисних змінних:

= 0,5; = 16,5; = 17,5; = 0; = 0.

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

.

2.7. Приклади розв’язування задач графічним методом

Розглянемо застосування графічного методу для розв’язуван­ня деяких економічних задач.

Ф ірма спеціалізується на виробництві офісних меблів, зокрема вона випускає два види збірних книжкових полиць — А та В. Полиці обох видів виготовляють на верстатах 1 та 2. Тривалість обробки деталей однієї полиці кожної моделі подано в табл. (2.4).

Таблиця 2.4