Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

РОЗДІЛ 2. ЗАГАЛЬНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА ДЕЯКІ З МЕТОДІВ ЇЇ РОЗВ’ЯЗУВАННЯ

«Тут все есть, коли нет обмана:
И черти, и любовь, и страхи, и цветы».

А. С. Грибоедов

2.1. Приклади побудови економіко-математичних моделей економічних процесів та явищ

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

Задача визначення оптимального плану виробництва: для деякої виробничої системи (цеху, підприємства, галузі) необхідно визначити план випуску n видів продукції Х = (х1, х2, …, хn) за умови найкращого способу використання її наявних ресурсів. У процесі виробництва задіяні m ресурсів: сировина, трудові ресурси, технічне оснащення тощо. Відомі загальні запаси ресурсів , норми витрат і-го ресурсу на виробництво одиниці j-ої продукції та прибуток з одиниці j-ої реалізованої продукції .

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

Позначимо через х1, х2, …, хn обсяги виробництва відповідно першого, другого і т. д. видів продукції.

Оскільки на одиницю продукції 1-го виду витрачається ресурсу першого виду, то на виробництво першого виду продукції обсягом х1 необхідно витратити а11х1 цього ресурсу. На другий вид продукції обсягом х2 витрати першого ресурсу дорівнюватимуть а12х2 і т. д. На виробництво всіх видів продукції буде використано такий обсяг першого ресурсу: а11х1 + а12х2 + … + + а1nxn. Ця величина має не перевищувати наявного обсягу першого ресурсу — b1. Отже, обмеження щодо використання першого ресурсу матиме вигляд: а11х1 + а12х2 + … + а1nxn ≤ b1. Аналогічно записують обмеження стосовно використання всіх інших виробничих ресурсів. Прибуток від реалізації виготовленої продукції всіх видів становитиме: с1х1 + с2х2 + … + сnxn.

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

за умов:

.

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

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

1.01 —31.01: витрати — 80 000 грн; необхідний запас на 31.01 — 300 000 грн;

1.02 —28.02: витрати — 30 000 грн; необхідний запас на 28.02 — 200 000 грн;

1.03 —31.03: витрати — 50 000 грн; необхідний запас на 31.03 — 190 000 грн.

Кредит терміном на 1 місяць дає 2 % прибутку, терміном на 2 місяці — 5 %, а терміном на 3 місяці — 8 %.

Вважатимемо, що кредити надаються першого числа кожного місяця і погашаються також першого числа відповідного місяця.

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

Кредити терміном на один місяць можна надавати кожного місяця протягом кварталу, тому позначимо через х11 суму кредиту, що надано на один місяць з 1.01, аналогічно х12,х13 — суми одномісячних кредитів, що надані відповідно в другому та у третьому місяцях.

Кредити терміном на два місяці протягом першого кварталу можна надавати лише в першому і другому місяцях, тому позначимо через х21 суму кредиту, що надано на два місяці в січні, х22 — суму кредиту, що надана в лютому на два місяці. Нарешті, кредит на три місяці можна надати лише один раз із 1.01, його позначимо через х31.

Розглянемо ситуацію на початку першого місяця кварталу: початкова сума 1 млн грн витрачатиметься на вкладення коштів у всі види кредитів, потреби в обігових коштах для господарської діяльності фірми становитимуть 80 000 грн, а на кінець місяця фірма бажає мати резерв обсягом 300 000 грн. Отже, використання коштів у січні можна описати у моделі так:

.

Наявні кошти в кінці місяця (окрім резерву) визначаються за формулою:

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

,

а наприкінці лютого обсяг наявних коштів становитиме:

.

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

.

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

.

Загалом математична модель цієї задачі має вигляд:

за умов:

На ринок поставляється картопля з трьох фермерських господарств за цінами відповідно 80, 75 та 65 коп. за 1 кг. На завантаження 1 т картоплі в господарствах відповідно витрачається по 1, 6 та 5 хвилин. Замовлено 12 т картоплі, і для своєчасної доставки необхідно, щоб на її завантаження витрачалося не більше сорока хвилин. Потрібно визначити, з яких фермерських господарств і в якій кількості необхідно доставляти картоплю, щоб загальна вартість закупівлі була мінімальною, якщо фермери можуть виділити для продажу відповідно 10, 8 та 6 т картоплі.

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

Позначимо: х1 — кількість картоплі, що буде закуплена у першому господарстві (т); х2, х3 — кількість картоплі, закупленої відповідно у другого та третього фермерів (т).

Поставка потрібної кількості картоплі описується рівністю:

,

наступне обмеження описує витрати часу на завантаження продукції:

,

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

Вартість продукції, що закуповується, визначається як сума добутків ціни на відповідні її обсяги. Ціни 1 т картоплі відповідно дорівнюють 800, 750 та 650 грн в даних трьох фермерських господарствах. Отже, цільову функцію можна записати так:

.

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

за умов:

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

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

Позначимо через x1, x2, …, xn — кількість відповідного j-го виду продукту . Система обмежень описуватиме забезпечення в раціоні кожної поживної речовини не нижче зазначеного рівня . Економіко-математична модель матиме вигляд:

за умов:

Аналогічно як у виробничій задачі, економіко-математична модель задачі про «дієту» (або про суміш) також може описувати інші економічні процеси. По суті цей тип задач дає змогу знаходити оптимальне поєднання деякого набору компонент в одне ціле, причому таке поєднання має задовольняти певні умови.

Стандартом передбачається, що октанове число бензину А-76 має бути не нижчим 76, а вміст сірки — не більшим, ніж 0,3 %. Для виготовлення такого бензину на заводі використовуються чотири компоненти. Дані про обсяги запасів компонентів, які змішуються, їх вартості, октанові числа та вміст сірки наведені в табл. 2.1:

Таблиця 2.1

ТЕХНІКО-ЕКОНОМІЧНІ ПОКАЗНИКИ КОМПОНЕНТ БЕНЗИНУ

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

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

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

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

.

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

,

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

.

Використання кожного компонента має не перевищувати його наявного обсягу:

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

.

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

за умов:

.

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

Таблиця 2.2

ХАРАКТЕРИСТИКИ ПРОДУКТІВ

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

Позначимо через х1, х2, х3, х4 масу (в кг) м’яса, борошна, молока і цукру відповідно.

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

,

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

.

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

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

;

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

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

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

.

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

за умов:

.

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

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

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

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

за умов:

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

Фермерське господарство спеціалізується на вирощуванні озимої пшениці і має три ділянки землі площею S1 = 40 га, S2 = 90 га, S3 = 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).

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

;

;

.

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

;

;

.

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

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

за умов:

.

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