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

14

РЕФЕРАТ

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

Розрахунково-економічна робота «Побудова та реалізація економіко-математичної моделі» містить 15 сторінок тексту, 2 таблиці, 5 використаних джерел.

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

Метою роботи є розкриття поняття задачі лінійного програмування та її економіко-математичної моделі, опис функцій і команд у вирішенні задач лінійного програмування засобами Exel, а також рішення конкретної задачі за допомогою ПК.

Вступ

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

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

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

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

Метою роботи є розкриття поняття задачі лінійного програмування та її економіко - математичної моделі, опис функцій і команд у вирішенні задач лінійного програмування засобами Exel, а також рішення конкретної задачі за допомогою ПК.

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

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

У структурі моделі (1.1) можна виділити 3 елементи:

1) Набір керованих змінних x₁, x₂, ... x _n, значення яких підлягають оптимізації. Різні допустимі комбінації значень змінних відповідають можливим розв'язкам задачі. 2) Цільова функція z (x₁, x₂, ... x _n) - функція, що виражає залежність прийнятого критерію оптимальності від керованих змінних. Критерій оптимальності є мірою наближення розв'язку до поставленої мети. В економічних задачах, як правило, таким критерієм виступає показник ефективності функціонування системи (наприклад, прибуток від реалізації продукції, продуктивність праці, таке інше) або показник витрат. 3) Умови або обмеження g (x₁, x₂, ... x _n), що накладаються на значення змінних або на співвідношення між ними. Зауважимо, що задача лінійного програмування спрямована на пошук найбільш вигідного способу розподілу обмежених ресурсів за декількома видами виробничої діяльності. У такій задачі представлено n видів виробничої діяльності, інтенсивності використання котрих (шукані величини) скаладають x₁, x₂, … x_n . Для здійснення усіх видів виробничої діяльності є в наявності m видів ресурсів, можливі обсяги споживання яких обмежені значеннями b₁, b₂, …, b_m. Витрати і-го ресурсу на одиницю продукції j-го виду виробництва дорівнюють a_ij. Тому сума , яка являє собою загальний обсяг і-го ресурсу, що використовується n видами виробництва, не може перевищувати величини b_i.

Структура цільової функції z відбиває внесок кожного виду виробничої діяльності в загальний результат, У випадку максимізації величинаC_j являє собою прибуток від j-го виду виробничої діяльності на одиницю відповідної продукції, а у випадку мінімізації C_j характеризує питомі витрати. Симплекс-метод -- метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану.

Описання методу

Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:

де X = (x₁, …, x_n) -- вектор змінних, C = (c₁, …., c_n), B = (b₁, …, b_m)^T, A_j = (a_1j, …, a_mj)^T, j = 1, …, n -- задані вектори, T -- знак транспонування, та відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану -- . Тоді

, (1.2)

(1.3),

де - значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь який із векторів умов A_j розкладається по ним єдиним чином:

, (1.5)

де x_ij коефіцієнт розкладання. Система умов

, (1.6)

z_k ? 0, x_j = 0, j = m + 1, …, n, j ? k (1.7) при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної x_k при русі по цьому проміню дорівнює и, тоді значення базисних змінних дорівнюють x_i(и). В цих позначеннях рівняння (1.6) можна представити в виді

. (1.8)

помноживши рівняння (1.4) на и при j = k та віднявши від рівняння (1.2), отримаємо

.(1.9)

Із рівнянь (1.8-1.9) отримаємо

. (1.10)

Оскільки x_i(и) при и = 0 визначають план задачі, то найбільше и, яке не порушує обмеження x_i (и) ? 0, визначається із умови

. (1.11)

де I = {i | x_ik > 0}.

В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та и > 0. Значення лінійної форми при и = и₀ визначається із рівнянь (1.10), (1.3), (1.4)

,

де Д_k = z_k -- c_k. Очевидно, Д_j = 0 для j = 1, …, m.

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

1. знайти Д_k = min_jД_j. Якщо Д_k = 0, тоді план, який розглядається оптимізовано; якщо Д_k < 0, вектор A_k вводиться в базис;

2. знайти и₀ та l, для якого

,

із формули (1.10). Якщо I = Л -- порожня множина, лінійна форма необмежена зверху; якщо I ? Л вектор A_l виводиться із базису;

3. по знайденим l, k обчислити нові значення елементів таблиці по формулам (1.11)

,

де та перейти до виконання операції (1.2) з новими значеннями всіх x_ij = x'_ij.

Перетворення (12) замінює вектор коефіцієнтів X_k = (x_1k, …, x_mk) на одиничний вектор X_k з x_lk = 1. В силу монотонного збільшення x₀ повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму. Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу

,

при обмеженнях

;

,

яка містить одиничний базис, який складається із векторів A_n+1, …, A_n+m. Цим векторам відповідають штучні змінні із значеннями , i = 1, …, m. Якщо в оптимальному розв'язку цієї задачі , вихідна задача не має розв'язку. Якщо ж та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які по формулам (1.11) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z₀ може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин b_i на b_i + е_i, де е_i достатньо малі, при вдалому виборі е_i не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.

Задача

Мається Аi постачальників вантажу (I = 1…m) та Bj споживачів цього вантажу (j = 1…n). Запаси вантажу у постачальників, попит споживачів та вартість перевезення одиниці вантажу від і - го постачальника до j - го споживача Cij у г.о. надані в таблиці. Належить скласти такий план перевезення вантажу, який забезпечив би мінімальні транспортні витрати.

Таблиця 1. - Вхідні дані до транспортної задачі

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

Цільова функція:

Z = 2X11 + 4X12 + 3X13 + 6X14 + 3X21 + 5X22 +7X23 + 5X24 + X31 + 8X32 + 4X33 + 5 X34 + 4 X41 + 3 X42 + 2 X43 + 8 X44 - min.

Обмеження:

X11 +X12 +X13 +X14 = 25,

X21 +X22 +X23 +X24 = 18,

X31 +X32 +X33 +X34 = 12,

X41 +X42 +X43 +X44 = 15,

X11 +X21 +X31 +X41 = 15,

X12 +X22 +X32 +X42 = 25,

X13 +X23 +X33 +X43 = 18,

X14 +X24 +X34 +X44 = 12,

Xij >= 0.

2. Розрахунок задачі лінійного програмування на ПК

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

Рішення транспортної задачі на ПК проводиться за таким алгоритмом.

1. Оформити шапку та заголовки рядків і стовпців у Exel.

2. Заповнити електронну таблицю: блоки «Запаси.», «Споживання» та «Матриця вартості».

3. Записати формулу цільової функції за допомогою Мастера функций, для чого:

3.1 натиснути на кнопку fx панелі інструментів Стандартная, ініціювати Мастер функцій;

3.2 вибрати функцію Математическая / СУММПРОИЗВ;

3.3 встановити курсор у полі Матриця вартості, відмітити відповідний блок та зафіксувати перший аргумент функції;

3.4 встановити курсор у полі Матриця рішення, відмітити відповідний блок та зафіксувати другий аргумент функції;

3.5 закінчити запис формули, клацнувши ОК.

4. В клітинках блоків Формули обмежень за запасами та Формули обмежень за споживанням записуються формули сумування змінних відповідно за запасами постачальників та потребою споживачів.

5. З'в'язати електронну таблицю з вікном «Поиск решения», для чого

5.1 відмітити клітинку «Цільова функція», відкрити вікно «Поиск решения»;

5.2 заповнити рядок «Установить целевую ячейку»;

5.3 встановити режим «Равной» у стан «Минимальному значению»

5.4 заповнити рядок «Изменения ячейки» посиланням на блок «Матриця рішення»;

5.5 Заповнити вікно «Ограничения» обмеженнями за рядками та стовпцями змінних, що відповідає запасам постачальників та потрабам споживачів;

5.6 у рядку «Знак» вибрати знак відношення розглядаємої транспортної задачі (>=, <=, =);

5.7 заповнення рядків вікна «Добавить» закінчити натиском кнопки ОК;

5.8 Натиснувши кнопку «Параметры», встановити у вікні «Параметры поиска решения» режим «Линейная модель» та «Неотрицательные значения»; натиснути кнопку ОК.

6. Ініціювати рішення задачі, натиснувши кнопку «Выполнить».

Таблиця 2. - Рішення задачі за допомогою Exel

Висновки

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

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

Перелік посилань

1. Гончаренко Л.С. Оформлення матеріалів самостійної роботи студентів: Навчальний посібник. - Херсон: МІБ, 1999. - 50 с.

2. Лугинин О.Е., Белоусова С.В., Львов М.С. Єкономико - математические методы и модели: Учебное пособие. - Херсон: МИБ, 1998. - 212 с.

3. Лугінін О.Є., Білоусова С.В., Білоусов О.М.. Економетрія: Навчальний посібник. - Херсон: МІБ, 2002. - 251 с.

4. Лук'яненко І.Г., Красикова Л.І. Економетрика: Підручник. - К.: Товариство «Знання» КОО, 1998. - 212 с.

5. Методичні вказівки до самостійної роботи студентів усіх форм навчання при вивченні дисципліни «Економетрія» / Укл. О.Є. Лугінін. - Херсон: МІБ, 2000.- 25 с.