Розділ 1. Лінійне програмування

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

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

1. Задача про розміщення капіталу. Допустимо, що інвестор повинен прийняти рішення про розміщення капіталу на певній групі об’єктів, характеристика яких задана таблицею.

Номер об’єкта	Дохідність, у %	Термін управління об’єктом, роки	Оцінка надійності, бали
1	5,0	2	6
2	6,5	5	4
3	8,0	10	3
4	7,0	4	3
5	5,5	4	5
6	7,5	3	2

Нехай прийняття рішень здійснюється за умов:

1. загальний об’єм інвестицій складає 1000000 грн.;

2. частка капіталу, вкладеного в один об’єкт не може перевищувати четвертої частини всього об’єму;

3. не менше 50 відсотків капіталу повинно бути вкладено в об’єкти, термін управління якими перевищує три роки;

4. частка капіталу, вкладеного в об’єкти з оцінкою надійності меншою чотирьох балів, не повинна перевищувати 30 відсотків.

Формалізуємо поставлену задачу, побудувавши її математичну модель.

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

; (1.1.1)

Умова 1 виражається рівністю

. (1.1.2)

Умова 3 дає:

, (1.1.3)

а умова 4 призводить до нерівності

. (1.1.4)

Сумарний доход від розміщення капіталу залежить від невідомих і виражається у вигляді

. (1.1.5)

Вирази (1.1.1) – (1.1.5) утворюють так звану математичну модель задачі. При цьому співвідношення (1.1.1) – (1.1.4) утворюють групу обмежень на інвестиції, а функція (1.1.5) може служити критерієм якості прийнятого рішення про об’єми інвестицій в кожний об’єкт.

Природно ставити задачу про визначення об’ємів так, щоб справджувались обмеження (1.1.1) – (1.1.4), а доход (1.1.5) при цьому набував максимального значення.

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

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

Отже, нехай:

– кількість необхідних харчових речовин;

– кількість різних видів кормів;

– кількість одиниць -ї необхідної речовини в одиниці -го корму;

– мінімальна потреба в -й харчовій речовині, наприклад, у добовому раціоні;

– вартість одиниці -го корму.

Зрозуміло, що

, . (1.1.6)

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

, . (1.1.7)

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

. (1.1.8)

Найкращим раціоном природно вважати такий набір кормів , який задовольняє умови (1.1.6) та (1.1.7) і надає найменшого значення затратам (1.1.8).

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

Якщо запланувати до випуску одиниць -ї продукції, то

, , (1.1.9)

а обмеженість ресурсів призводить до нерівностей

, . (1.1.10)

Доход від наміченої програми виробництва складатиме

. (1.1.11)

План виробництва доцільно складати так, щоб виконувались умови (1.1.9) та (1.1.10), а доход (1.1.11) був найбільшим.

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

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

, , . (1.1.12)

Якщо , , об’єм виробленої продукції в -му пункті, то

, . (1.1.13)

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

, . (1.1.14)

З точки зору замовника, план перевезень повинен задовольняти умови (1.1.12), (1.1.13), (1.1.14) і мати мінімальну загальну вартість

. (1.1.15)

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

. (1.1.16)

У цьому випадку транспортна задача ставиться так:

визначити план перевезень (, ) такий, що

, (, ),

, (),

, (),

а загальна вартість перевезень

набуває найменшого значення.

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

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

Загальні методи розв’язування ЗЛП лягли в основу методів розв’язування цих нових задач, отримані в лінійному програмуванні теоретичні результати стали підґрунтям при вивченні властивостей задач при наявності нових, додаткових умов.