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

Нехай f (x) – функція n змінних, визначена на множині V Rⁿ, підмножина Ω V. Оптимізаційна задача задається трійкою (f, V, Ω), де f (x) називається цільовою функцією, а Ω – множиною допустимих розв’язків оптимізаційної задачі; вона полягає у пошуку мінімуму (найменшого) або максимуму (найбільшого) значення цільової функції f (x) на допустимій множині Ω.

Означення 1. Оптимальним розв’язком задачі (f, V, Ω) називається таке х₀ є Ω, що f (x₀) ≤ f (x) (або f (x₀) ≥ f (x)) для всіх х є Ω. Оптимізаційну задачу називають нерозв’язною, якщо вона не має оптимальних розв’язків. Розв’язати оптимізаційну задачу означає або знайти всі її оптимальні розв’язки, або ж довести її нерозв’язність.

Зокрема, задача мінімізації (максимізації) (f, V, Ω) буде нерозв’язною, якщо f (x) не обмежена знизу (зверху) на допустимій множині Ω.

Методи розв’язування оптимізаційної задачі (f, V, Ω) часто називають методами математичного програмування. Сам термін програмування в цьому випадку зумовлений тим, що саме математичне програмування є підґрунтям мікроекономіки – одної з двох найважливіших складових економічної науки і шуканою у таких задачах насправді є деяка програма дій. Необхідною передумовою будь – якого використання методів обчислень є створення математичної моделі досліджуваного об’єкта чи явища. Першим кроком при розв’язуванні задач економіки є побудова їх економіко – математичної моделі, тобто такої математичної задачі, до розв’язання якої зводиться поставлена економічна задача. Розглянемо деякі приклади.

1. Для виготовлення продукції двох типів (А і Б) на заводі використовують сировину трьох видів (1, 2 и 3). Для виробництва кожного виробу типу А витрачається 10 одиниць сировини виду 1, 20 одиниць виду 2 і 15 виду 3; для кожного виробу типу Б – 20, 10 и 15 відповідно. Запаси сировини складають: 1 виду 100 одиниць, 2 виду – 100, 3 виду – 90. Скласти щоденний план виробництва, що забезпечує найбільший прибуток, якщо кожний виріб типу А дає 200 гривен прибутку, Б – 300 гривен.

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

 

Вироби	Прибуток	Сировина
А
Б
Запаси сировини

 

Побудуємо математичну модель цієї задачі. Позначимо через х_А та х_Б кількість одиниць продукції А і Б відповідно, яку передбачається виготовити по плану. За умовою задачі цільова функція f – прибуток, який треба максимізувати: f = 200х_А + 300х_Б. При цьому сировини 1 буде витрачено 10х_А + 20х_Б. Кількість витраченої сировини не може перевищувати її запасу, тому 10х_А + 20х_Б ≤ 100. Аналогічно для сировини 2 20х_А + 10х_Б ≤ 100, для сировини 3 15х_А + 15х_Б ≤ 90. Змінні х_А і х_Б повинні бути невід’ємними, оскільки це кількості продукції. Отже економіко – математична модель формулюється так: треба знайти такі значення змінних х_А та х_Б , за яких задовольняється система нерівностей

і цільова функція f = 200 х_А + 300 х_Б набуває найбільшого можливого значення.

Знайти такі х_А та х_Б і означає знайти план виробництва. Це простіший приклад задачі планування виробництва, яка найбільш традиційно формулюється так у загальному вигляді. Підприємство виробляє деяку однорідну продукцію і використовує для цього n різних технологічних засобів і m різних ресурсів. За одиницю часу використання j – го технологічного засобу виготовляється с_j одиниць продукції, при цьому витрати і – го ресурсу a _ij одиниць (і = 1, 2, …, m, j = 1, 2, …, n). Треба так спланувати роботу підприємства, щоби кількість продукції була найбільшою при умові, що витрати і – го ресурсу не можуть перебільшувати b_i одиниць (і = 1, 2, …, m).

Нехай х_j ≥ 0 (j = 1, 2, …, n) – час використання підприємством j – го технологічного засобу. Замість прибутку у попередньому прикладі тут цільова функція f – це кількість виробленої продукції: f = ; все інше так само, лише у загальному вигляді. За планом буде витрачено одиниць і–го ресурсу. Звідси ≤ b_i (і = 1, 2, …, m). Отже ми отримуємо таку економіко – математичну модель: треба знайти такі значення змінних х_j (j = 1, 2, …, n), за яких задовольняється система нерівностей

і цільова функція f = набуває найбільшого можливого значення.

2. Задача про раціон. У господарстві є два вида кормів вартістю 20 та 30 гривен за одиницю корму відповідно. У першому кормі міститься 2 одиниці вітаміну А та 3 одиниці вітаміну В, у другому 5 одиниць А та 2 одиниці В. Раціон повинен містити не менш як 9 одиниць А та 8 одиниць В. Скласти найдешевший раціон, який задовольняє цим вимогам.

Через х_А і х_В позначимо відповідно кількість першого і другого кормів у раціоні. Тут цільова функція f – це вартість раціону: f = 20х_А + 30х_В. За таким планом раціон містить 2х_А + 5х_В одиниць вітаміну А, за вимогою задачі 2х_А + 5х_В ≥ 9. Аналогічно для вітаміну В 3х_А + 2х_В ≥ 8. Змінні х_А і х_В повинні бути невід’ємними, оскільки це кількості продукції. Отже математична модель формулюється так: треба знайти такі значення змінних х_А та х_В , за яких задовольняється система нерівностей

і цільова функція f = 20х_А + 30х_В набуває найменшого можливого значення.

У загальному вигляді задача про раціон традиційно формулюється так. У господарстві є n різних кормів, кожен з яких містить m різних поживних речовин. Відомо, що одиниця j – го корму коштує с_j грошових одиниць (j = 1, 2, …, n) і містить a _ij одиниць і – ої поживної речовини (і = 1, 2, …, m). Треба скласти раціон так, щоб він задовольняв мінімальну потребу b_i (і = 1, 2, …, m) у кожній речовині при найменшій вартості раціону.

Позначимо кількість j – го корму в раціоні через х_j ≥ 0 (j = 1, 2, …, n), цільова функція f – це вартість раціону: f = . За таким планом раціон містить одиниць і – ої поживної речовини, звідки ≥ b_i (і = 1, 2, …, m). Отже ми отримуємо таку математичну модель: треба знайти такі значення змінних х_j (j = 1, 2, …, n), за яких задовольняється система нерівностей

і цільова функція f = набуває найменшого можливого значення.

3. Транспортна задача. Нехай з трьох пунктів відправлення Р₁, Р₂, Р₃ треба перевезти однорідний вантаж до трьох пунктів призначення М₁, М₂, М₃, в тому числі з пункту Р₁ – 12 т, з пункту Р₂ – 8 т, з пункту Р₃ – 10 т. Вантаж повинен надійти за призначенням у пункт М₁ – 6 т, пункт М₂ – 9 т, пункт М₃ – 15 т. Вартість перевезення тони вантажу з пункту Р_i до пункту М_j (i, j = 1,2,3) наведена у наступній таблиці.

 

Пункт відправлення	Пункт призначення
М1	М2	М3
Р1
Р2
Р3

 

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

Побудуємо математичну модель цієї задачі. Позначимо через х_ij вагу вантажу (в тонах), запланованого для перевезення з пункту Р_i до пункту М_j (i, j = 1,2,3). Вартість перевезення багажу дорівнює f = х₁₁ + 3х₁₂ + 4х₁₃ + 2х₂₁ + 5х₂₂ + 3х₂₃ + 6х₃₁ + 7х₃₂ + 4х₃₃ – цільова функція задачі. Весь вантаж буде вивезений з пунктів відправлення, якщо х₁₁ + х₁₂ + х₁₃ = 12, х₂₁ + х₂₂ + х₂₃ = 8, х₃₁ + х₃₂ + х₃₃ = 10. Попит пунктів призначення буде повністю задоволений, якщо х₁₁ + х₂₁ + х₃₁ = 6, х₁₂ + х₂₂ + х₃₂ = 9, х₁₃ + х₂₃ + х₃₃ = 15. Отже, серед невід’ємних розв’язків системи

треба знайти такий, за якого функція f набуває найменшого значення.

У загальному випадку транспортну задачу звичайно формулюють так. Нехай однорідний вантаж, що знаходиться у m постачальників у кількості а _i (і = 1, 2, …, m) одиниць відповідно, треба перевезти n споживачам у кількості b_j (j = 1, 2, …, n) одиниць. Вартість перевезення одиниці вантажу від і – го постачальника до j – го споживача становить с_ij одиниць. Спланувати перевезення вантажу так, щоби весь вантаж був вивезений від постачальників, повністю був задоволений попит споживачів і вартість перевезень була мінімальною.

Позначимо через х_ij кількість одиниць вантажу, запланованого для перевезення від постачальника і до споживача j. Математична модель транспортної задачі має такий вигляд. Знайти найменше значення функції f = за обмежень

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

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