Оптимізаційні економіко-математичні моделі

Размещено на http://www.allbest.ru/

Тема 2. Оптимізаційні економіко-математичні моделі

Задачі лінійного програмування

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

економічний оптимізація математичний програмування

План лекції

1. Задачі економічного вибору. Сутність звичайної (однокритеріальної) оптимізації.

2. Економічна та математична постановка оптимізаційних задач.

3. Види оптимізаційних моделей.

4. Приклади економічних задач, які доцільно розв'язувати, використовуючи методи та моделі математичного програмування.

Опорні поняття: математичні методи, однокритеріальна оптимізація, оптимізаційна задача, задача лінійного програмування.

ВИКЛАД МАТЕРІАЛУ ЛЕКЦІЇ

1. Задачі економічного вибору. Сутність звичайної (однокритеріальної) оптимізації.

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

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

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

Задача математичного програмування формулюється таким чином: знайти значення змінних, при якому цільова функція F(x) буде приймати максимальне (мінімальне) значення за умов:

(1)

2. Економічна та математична постановка оптимізаційних задач

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

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

Кожна економічна система має мету (ціль) розвитку та функціонування F. Ступінь досягнення мети, здебільшого, має кількісну міру, тобто може бути описаний математично F = f (x₁, x₂, ..., x_n; c₁, c₂, ..., c_l).

В загальному вигляді задача математичного програмування формулюється так: знайти такі значення керованих змінних x_j, щоб цільова функція F набувала екстремального (максимального чи мінімального значення).

Отже, потрібно відшукати значення:

max (min) F= f (x₁, x₂, ..., x_n) (2)

Можливості вибору x_j завжди обмежені зовнішніми щодо системи умовами, параметрами економічної системи і т. ін.

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

g (x₁, x₂, ..., x_n) {?, =, ?}b (3)

x₁,…,n ? 0.

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

Система (3) називається системою обмежень, або системою умов задачі. Вона описує внутрішні економічні процеси функціонування й розвитку торговельно-економічної системи, а також процеси зовнішнього середовища, які впливають на результат діяльності системи. Для економічних систем змінні х_j мають бути невід'ємними.

Вектор X=(x₁, x₂…, x_n), який задовольняє обмеження задачі лінійного програмування називають її розв'язком або оптимальним планом.

Залежності (2)-(3) становлять економіко-математичну модель економічної системи, розробляючи яку необхідно дотримуватися наступних правил: модель має адекватно описувати реальні економічні процеси; у моделі потрібно враховувати лише все істотне в досліджуваному процесі; модель має бути зрозумілою для користувача, зручною для реалізації на комп'ютері.

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

3. Види оптимізаційних моделей

Перш за все треба розділяти задачі параметричної та структурної оптимізації.

Параметрична оптимізація є предметом, що розглядається в цій темі, де попередньо наведена постановка такої задачі. Структурна оптимізація - це задача синтезу оптимальної структури системи, причому зміна структур та перетворення однієї структури в іншу здійснюється за спеціальним алгоритмом синтезу.

Параметрична оптимізація об'єднує багато різних задач, що мають свої власні особливості та методи розв'язання.

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

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

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

4. Математичне програмування об'єднує задачі нелінійного програмування (цільова функція в загальному випадку нелінійна), стохастичного програмування (параметри - випадкова величина, або цільова функція - випадкова функція), динамічного програмування (оптимізація багатокрокових процесів пошуку рішення).

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

6. У випадку, коли цільова функція опукла, та область, де задані , теж опукла, то має місце задача опуклого програмування. Якщо цільова функція та умови лінійні-лінійного (кусково-лінійного) програмування; цільова функція квадратична, а умови лінійні-квадратичного програмування; цільова функція та умови - лінійні комбінації функцій однієї змінної - сепарабельного програмування; цільова функція та умови подані у вигляді поліномів - геометричного програмування.

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

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

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

Задача використання сировини

Припустимо, що деяке підприємство має запаси сировини трьох видів - S1, S2, S₃ відповідно в кількостях b₁, b₂, b₃ умовних одиниць. З цієї сировини може бути виготовлено два види продукції: P₁, P₂.

Відомо: a_ij - кількість одиницьS_i-го виду сировини, яка йде на виготовлення одиниці P_j-го виду продукції;

c_j - прибуток від реалізації одиниці кожного виду продукції.

Всі вказані величини покажемо в наступній таблиці:

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

Для побудови математичної моделі даної задачі введемо такі позначення:

x₁ - кількість одиниць продукції виду P₁,

x₂ - кількість одиниць продукції виду P₂, які може виготовляти підприємство.

Знаючи кількість сировини кожного виду, яка йде на виготовлення одиниці продукції, і запаси сировини, можна скласти систему обмежень, яка визначає область можливих значень x₁ і x₂:

Отримана система обмежень означає, що кількість сировини, яка йде на виготовлення всіх видів продукції, не може перевищувати запасів, які є в наявності на підприємстві. Виходячи з економічного змісту задачі, на змінні накладаються додаткові обмеження, які вимагають невід'ємності їх значень: x₁?0, x₂?0 (x₁ і х₂ будуть дорівнювати нулю, якщо відповідний вид продукції не випускається). Тоді прибуток, який підприємство отримує від реалізації х₁ одиниць продукції Р₁ і х₂ - одиниць продукції Р₂ складе F=3x₁+2x₂, якщо вважати, що прибуток від реалізації одиниці продукції P₁ дорівнює 3 (c₁), а від реалізації одиниці продукції - P₂-2(c₂).

Остаточно задача формулюється так. Знайти такий вектор X=(x₁, x₂), при якому цільова функція F=3x₁+2x₂ досягає максимуму і виконуються наступні обмеження:

В загальному випадку математична модель такої задачі має вигляд: знайти вектор X=(x₁, x₂,…,x_n), який максимізує функцію F=c₁x₁+c₂x₂+…+c_nx_n, при обмеженнях:

……… ………. ……… …………

Задача про рюкзак. Найпростішою задачею цілочислового програмування, а саме задачею лише з одним обмеженням, є задача про рюкзак (або ранець). Така задача має багато прикладів практичного застосування. Назва «задача про рюкзак» пов'язана з інтерпретацією задачі вибору найкращого складу предметів, що задовольняють певні умови гіпотетичної проблеми туриста щодо вибору для походу оптимальної кількості речей.

Турист може вибирати потрібні речі із списку з n предметів. Відома вага кожного j-го предмета . Визначена також цінність кожного виду предметів w_j. Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.

Позначимо через x_j - кількість предметів j-го виду в рюкзаку. Тоді математична модель задачі матиме вигляд:

Приклад задачі. Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Він може купити добрива в упаковках по 35 кг вартістю 14 ум. од. або по 24 кг вартістю 12 ум. од. Метою фермера є закупівля не менше, ніж 107 кг добрив з мінімальними витратами. Причому потрібно купувати або цілу упаковку, або не купувати її зовсім, бо частину упаковки придбати неможливо.

Розв'язання. Позначимо кількість упаковок вагою 35 кг та вагою 24 кг відповідно змінними x₁ та x₂. Маємо модель цієї задачі:

У результаті розв'язування задачі: Х^*(х₁=1, х₂=3), F_min.=50. Отже, за оптимальним планом найменші витрати, що дорівнюють 50 ум. од., можливі у разі закупівлі однієї упаковки добрив вагою 35 кг та трьох вагою по 24 кг.

Задача складання раціону. Для відгодівлі худоби використовують деякі корми, що містять у певній кількості поживні речовини. Відомо, скільки одиниць кожної поживної речовини міститься в одиниці кожного корму, мінімальна добова потреба у кожній поживній речовині при відгодівлі худоби, а також вартість одиниці кожного корму.

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

Складемо математичну модель задачі.

Нехай m - кількість поживних речовин, що містяться в кормах;

n - кількість кормів, які використовуються для відгодівлі худоби;

a_ij - кількість одиниць і- ї поживної речовини, що міститься в одиниці j-го корму;

b_i - мінімальна добова потреба в і-й поживній речовині при відгодівлі худоби;

c_j - вартість одиниці j-го корму;

x_j - кількість одиниць j-го корму, що планується використати в добовому раціоні (шукані величини).

Загальна кількість і-ї поживної речовини, яка міститься в кормах раціону, становить a_i1x₁+a_i2x₂+…+a_inx_n, i=1,…,m.

Оскільки ця кількість одиниць не може бути меншою, ніж добова потреба в і-й поживній речовині, то a_i1x₁+a_i2x₂+…+a_inx_n?b_i, i=1,…,m.

Очевидно, x_j?0, (j=1,…,n).

Вартість одиниць j-го корму становить c_jx_j, а загальна вартість добового раціону L=c₁x₁+ c₂x₂+…+ c_nx_n.

Таким чином, математична модель задачі є такою: знайти вектор X=(x₁, x₂,…,x_n), який мінімізує функцію за умов (i=1,…,m), x_j?0, (j=1,…,n).

Висновок

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

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

Размещено на Allbest.ru