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

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

õ Приклади задач

1. На трьох складах (I, II, III) знаходиться відповідно 90, 70, 50 тонн борошна, яке потрібно перевезти у магазини (1, 2, 3, 4) у кількості 80, 60, 40, 30 тонн. Необхідно скласти оптимальний план перевезення борошна, якщо вартість перевезення 1 тонни у магазини 1, 2, 3, 4 із складу I дорівнює відповідно 2, 1, 3, 2 грн., із складу II — 2, 3, 3, 1 грн., із складу III — 3, 3, 2, 1 грн. Записати умову задачі у вигляді таблиці й побудувати математичну модель.

Розв’язок.

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

Таблиця 1

Магазини					Відправлено тонн борошна
Склади
I	x₁₁ 2	x₁₂1	x₁₃3	x₁₄2
II	X₂₁ 2	X₂₂1	X₂₃3	X₂₄2
III	X₃₁ 2	X₃₂1	X₃₃3	X₃₄2
Одержано тонн борошна

Через x_ij позначимо кількість борошна у тоннах, перевезеного з i-го складу в j-ий магазин. Так, x₂₃ — кількість борошна, перевезеного зі складу II у 3-ій магазин, x₁₂ — із складу I у 2-ий магазин і т.д. Кількість борошна, вивезеного із складу I у магазини,

x₁₁+ x₁₂+ x₁₃+ x₁₄.

Ця сума дорівнює 90, оскільки зі складу I вивозиться все борошно

x₁₁+ x₁₂+ x₁₃+ x₁₄ = 90.

Аналогічно для складів II та III маємо

x₂₁+ x₂₂+ x₂₃+ x₂₄ = 70,

x₃₁+ x₃₂+ x₃₃+ x₃₄ = 50.

Оскільки потреба кожного з магазинів за умовою задачі повністю задовольняється кількістю борошна, одержаного зі складів I, II, III, то

x₁₁+ x₁₂+ x₁₃ = 80,

x₁₂+ x₂₂+ x₃₂ = 60,

x₁₃+ x₂₃+ x₃₃ = 40,

x₁₄+ x₂₄+ x₃₄ = 30.

Отже, змінні x_ij, де i = 1, 2, 3 та j = 1, 2, 3, 4 задовольняють наступну систему рівнянь (1) та нерівностей (систему обмежень).

Позначивши через F усі транспортні витрати, одержуємо так звану цільову функцію (2).

(1)

F = 2x₁₁ + x₁₂ + 3x₁₃ + 2x₁₄ + 2x₂₁ + 3x₂₂ + 3x₂₃ + x₂₄ +

+ 3x₃₁ + 3x₃₂ + + 2x₃₃ + x₃₄. (2)

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

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

2. Процес виготовлення двох видів виробів заводом потребує, по-перше, послідовної обробки на токарних та фрезерних верстатах, і, по-друге, затрат двох видів сировини: сталі й кольорових металів. Дані про потреби кожного ресурсу на одиницю виготовленого виробу й загальні запаси ресурсів розміщені у таблиці 2. Прибуток від реалізації одиниці виробу А — 3 тис.грн., одиниці виробу В — 8 тис. грн. Визначити такий план випуску продукції, який забезпечує максимальний прибуток за умови, що час роботи фрезерних верстатів повинен бути використаний повністю.

Таблиця 2

	Затрати на 1 виріб
А	В	Ресурси
Матеріали	Сталь (кг)
Кольорові метали (кг)
Обладнання	Токарні верстати (верстатогодин)
Фрезерні верстати (верстатогодин)
Прибуток на виріб (у тис. грн.)

Розв’язок

Побудуємо математичну модель задачі. Позначимо через x кількість виробів виду А, через y — кількість виробів виду В. На виготовлення всієї продукції піде (10x + 70y) кг сталі і (20x + 70y) кг кольорових металів. Оскільки запаси сталі не перевищують 320 кг, а кольорових металів — 420 кг, то

Час обробки всіх виробів на токарних верстатах дорівнює (300x + 400y) верстатогодин. З умови задачі випливає, що

Ураховуючи, що фрезерні верстати використовуються максимально, маємо

200x + 100y = 3400.

Отже, система обмежень цієї задачі така (3):

(3)

Загальний прибуток може бути виражений наступною функцією (4):

F = 3x + 8y. (4)

Виразимо y через x із рівняння 200x + 100y = 3400 і підставимо одержаний вираз замість y в останні обмеження (3) та функцію (4)

(5)

F = 3x + 8(34 – 2x) = -13x + 272. (6)

Здійснимо перетворення системи (5)

(6)

Очевидно, що F = 272 – 13x набуває найбільшого значення, якщо x = 16

F_max = 272 - 13·16 = 64 (тис. грн.).

Розв’яжемо дану задачу графічно.

Математична модель цієї задачі представляється системою обмежень (3),

на множині розв¢язків якої потрібно знайти найбільше значення цільової функції

F = 3x + 8y. (7)

Потрібно знайти множину точок площини (множину допустимих планів), координати яких задовольняють систему обмежень (3) (рис. 14). Нерівності та показують, що множина допустимих планів розміщена у першому квадранті. Інші нерівності системи задають у першому квадранті фігуру OACKL (вона відмічена штриховкою). Рівняння 2x + y = 34 із прямокутника OACKL виділяє множину допустимих планів. Це точки відрізка EN. Серед точок цього відрізка виберемо таку, у якій цільова функція F досягає максимального значення. Для цього за допомогою рівняння 3x + 8y = С будуємо декілька прямих (лінії рівня F), надаючи C довільного значення (наприклад, 120, 240 і т д.). Так одержуємо сімейство паралельних між собою прямих.

Зі збільшенням значення С пряма 3x + 8y = C буде рухатися вгору —направо (рис. 14). Останньою точкою відрізка EN, якою торкнеться пряма 3x + 8y = C, буде точка E. Визначимо її координати. Для цього достатньо розв¢язати систему рівнянь

(8)

оскільки точка E є перетином прямих 2x + y =34 та 2x + 5y = 42. Розв’язком системи (8) є пара (16; 2). Цей розв’язок є оптимальним планом.

F_max = 3·16 + 8·2 = 64.

Рис. 14. Графічний розв’язок задачі

õ Завдання

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

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

План має враховувати, що 1-ий вид машин щодня може обробляти цю продукцію протягом 18-ти годин, 2-ий — 12-ти годин, 3-й — 12-ти годин, 4-й — 9-ти годин.

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

Завод від реалізації одного виробу виду I одержує 4 грн., а від реалізації одного виробу виду II — 6 грн. прибутку.

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

Таблиця 3

Види машин	1-й	2-й	3-й	4-й
Види виробів
I		0,5
II
Можливий час роботи машин (год)

2. Знайти максимальне значення цільової функції F_max = 4x₁ + 6x₂ на множині допустимих планів та розв’язати графічно

2. Відомо, що відгодівля тварин економічно вигідна за умови, що кожна тварина одержує у щоденному раціоні не менше 6-ти одиниць поживної речовини А, не менше 12-ти одиниць речовини В, не менше 4-х одиниць речовини С. Для відгодівлі тварин використовують два види кормів. У таблиці 4 показано, скільки одиниць кожної поживної речовини містить 1 кг кожного виду корму:

Таблиця 4

Корм	I	II
Поживні речовини
A
B
C

Ціна корму I дорівнює 5 грн. за кг, а ціна корму II — 6 грн. за кг. Яку кількість кожного виду корму необхідно витрачати, щоб затрати на нього були мінімальні?

õ Завдання для самостійної роботи

1. Швейний цех має 84 м тканини. На пошив одного халата потрібно 4 м тканини, а на одну куртку — 3 м. Скільки треба пошити халатів та курток для отримання найбільшого прибутку від реалізації продукції, якщо халат коштує 6 грн., а куртка — 3 грн.? Відомо, що халатів можна пошити не більше 15, а курток — не більше 20.

2. Знайти екстремальні значення функцій при заданих обмеженнях. Розв’язати графічно

1.1. 1.2. 1.3.

3. Потрібно виготовити суміш, яка містить три хімічні речовини А, В, С. Відомо, що створена суміш повинна містити речовини А не менше 6-ти одиниць, речовини В не менше 8-ми одиниць, речовини С не менше 12-ти одиниць. Речовини А, В, С містяться у трьох видах продуктів — I, II, III у концентрації, указаній у таблиці 5:

Таблиця 5

	Хімічні речовини
продукти	А	В	С
I
II
III		1,5

Вартість одиниці продуктів I, II, III різна: одиниця продукту I коштує 3 грн., одиниця II — 3 грн., одиниця III — 2,5 грн. Суміш потрібно виготовити так, щоб вартість використаних продуктів була найменшою.

4. Знайти екстремальні значення функцій при заданих обмеженнях. Розв’язати графічно

а) б)

Додаток 1

Таблиця 6