РЕФЕРАТ
Побудова та реалізація економіко–математичної моделі
Розрахунково–економічна робота «Побудова та реалізація економіко–математичної моделі» містить 15 сторінок тексту, 2 таблиці, 5 використаних джерел.
В роботі розглянута загальна модель задачі математичного програмування, задача лінійного програмування та особливості симплекс–методу для розв’язання задач лінійного програмування. Також побудована економіко–математична модель конкретної задачі, описаний алгоритм її вирішення за допомогою Exel та приведена таблиця з рішенням даної задачі.
Метою роботи є розкриття поняття задачі лінійного програмування та її економіко–математичної моделі, опис функцій і команд у вирішенні задач лінійного програмування засобами Exel, а також рішення конкретної задачі за допомогою ПК.
Вступ
Економетрія – комплекс економіко–математичних методів і побудованих на їх основі моделей для кількісного вимірювання взаємозв’язків між економічними факторами.
Економіко–математична модель – математичний опис економічного процесу або явища з метою його дослідження та керування ним.
Під назвою «транспортна задача» об’єднується широке коло задач з єдиною математичною моделлю. Дані задачі відносяться до задач лінійного програмування і можуть бути вирішені симплексним методом. Проте матриця системи обмежень транспортної задачі настільки своєрідна, що для її рішення розроблені спеціальні методи, у тому числі, метод рішення за допомогою Exel. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне решення, а потім, покращуючи його, отримати оптимальне рішення.
Сутність транспортної задачі полягає в тому, щоб забезпечити мінімальні транспортні витрати перевезень вантажу від постачальників до споживачів (цільова функція), і при цьому вантаж від постачальників має бути вивезеним (обмеження на спроможність постачальників), а потреби споживачів – задоволені (обмеження на потреби споживачів).
Метою роботи є розкриття поняття задачі лінійного програмування та її економіко – математичної моделі, опис функцій і команд у вирішенні задач лінійного програмування засобами Exel, а також рішення конкретної задачі за допомогою ПК.
1. Побудова економіко–математичної моделі
Загальна модель задачі математичного програмування має такий вигляд:
У структурі моделі (1.1) можна виділити 3 елементи:
1) Набір керованих змінних x1
, x2
, ... x n
, значення яких підлягають оптимізації.Різні допустимі комбінації значень змінних відповідають можливим розв’язкам задачі. 2) Цільова функція z (x1
, x2
, ... xn
) - функція, що виражає залежність прийнятого критерію оптимальності від керованих змінних. Критерій оптимальності є мірою наближення розв’язку до поставленої мети. В економічних задачах, як правило, таким критерієм виступає показник ефективності функціонування системи (наприклад, прибуток від реалізації продукції, продуктивність праці, таке інше) або показник витрат. 3) Умови або обмеження g (x1
, x2
, ... x n
), що накладаються на значення змінних або на співвідношення між ними.Зауважимо, що задача лінійного програмування спрямована на пошук найбільш вигідного способу розподілу обмежених ресурсів за декількома видами виробничої діяльності. У такій задачі представлено n видів виробничої діяльності, інтенсивності використання котрих (шукані величини) скаладають x1
, x2
, … xn
. Для здійснення усіх видів виробничої діяльності є в наявності mвидів ресурсів, можливі обсяги споживання яких обмежені значеннями b1
, b2
, …, bm
. Витрати і-го ресурсу на одиницю продукції j-го виду виробництва дорівнюють aij
. Тому сума
, яка являє собою загальний обсяг і-го ресурсу, що використовується n видами виробництва, не може перевищувати величини bi
.
Структура цільової функції z відбиває внесок кожного виду виробничої діяльності в загальний результат, У випадку максимізації величинаCj
являє собою прибуток від j-го виду виробничої діяльності на одиницю відповідної продукції, а у випадку мінімізації Cj
характеризує питомі витрати. Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану.
Описання методу
Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:
де X = (x1
, …, xn
) — вектор змінних, C = (c1
, …., cn
), B = (b1
, …, bm
)T
, Aj
= (a1j
, …, amj
)T
, j = 1, …, n — задані вектори, T — знак транспонування, та відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану — . Тоді
, (1.2)
(1.3),
де - значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь який із векторів умов Aj
розкладається по ним єдиним чином:
, (1.5)
де xij
коефіцієнт розкладання. Система умов
, (1.6)
zk
≥ 0, xj
= 0, j = m + 1, …, n, j ≠ k (1.7) при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної xk
при русі по цьому проміню дорівнює θ, тоді значення базисних змінних дорівнюють xi
(θ). В цих позначеннях рівняння (1.6) можна представити в виді
. (1.8)
помноживши рівняння (1.4) на θ при j = k та віднявши від рівняння (1.2), отримаємо
.(1.9)
Із рівнянь (1.8-1.9) отримаємо
. (1.10)
Оскільки xi
(θ) при θ = 0 визначають план задачі, то найбільше θ, яке не порушує обмеження xi
(θ) ≥ 0, визначається із умови
. (1.11)
де I = {i | xik
> 0}.
В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та θ > 0. Значення лінійної форми при θ = θ0
визначається із рівнянь (1.10), (1.3), (1.4)
,
де Δk
= zk
— ck
. Очевидно, Δj
= 0 для j = 1, …, m.
Нехай — початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розв'язання задачі лінійного програмування складається із наступних операцій:
1. знайти Δk
= minj
Δj
. Якщо Δk
= 0, тоді план, який розглядається оптимізовано; якщо Δk
< 0, вектор Ak
вводиться в базис;
2. знайти θ0
та l, для якого
,
із формули (1.10). Якщо I = Λ — порожня множина, лінійна форма необмежена зверху; якщо I ≠ Λ вектор Al
виводиться із базису;
3. по знайденим l, k обчислити нові значення елементів таблиці по формулам (1.11)
,
де та перейти до виконання операції (1.2) з новими значеннями всіх xij
= x'ij
.
Перетворення (12) замінює вектор коефіцієнтів Xk
= (x1k
, …, xmk
) на одиничний вектор Xk
з xlk
= 1. В силу монотонного збільшення x0
повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму. Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу
,
при обмеженнях
;
,
яка містить одиничний базис, який склад
, …, An+m
. Цим векторам відповідають штучні змінні із значеннями , i = 1, …, m. Якщо в оптимальному розв'язку цієї задачі , вихідна задача не має розв'язку. Якщо ж та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які по формулам (1.11) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z0
може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин bi
на bi
+ εi
, де εi
достатньо малі, при вдалому виборі εi
не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.
Задача
Мається Аiпостачальників вантажу (I = 1…m) та Bj споживачів цього вантажу (j = 1…n). Запаси вантажу у постачальників, попит споживачів та вартість перевезення одиниці вантажу від і – го постачальника до j – го споживача Cijу г.о. надані в таблиці. Належить скласти такий план перевезення вантажу, який забезпечив би мінімальні транспортні витрати.
Таблиця 1. – Вхідні дані до транспортної задачі
Постачаль- ники |
Запаси вантажу |
Споживачі та їх попит | |||
| В1=15 | В2=25 | В3=18 | В4=12 | ||
| А1 | 25 | 2 | 4 | 3 | 6 |
| А2 | 18 | 3 | 5 | 7 | 5 |
| А3 | 12 | 1 | 8 | 4 | 5 |
| А4 | 15 | 4 | 3 | 2 | 8 |
Економіко – математична модель задачі:
Цільова функція:
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
| Транспортна задача | |||||
| Матриця вартості | |||||
| 2 | 4 | 3 | 6 | ||
| 3 | 5 | 7 | 5 | ||
| 1 | 8 | 4 | 5 | ||
| 4 | 3 | 2 | 8 | ||
| Матриця рішень | Запаси | ||||
| 0 | 22 | 3 | 0 | 25 | 25 |
| 3 | 3 | 0 | 12 | 18 | 18 |
| 12 | 0 | 0 | 0 | 12 | 12 |
| 0 | 0 | 15 | 0 | 15 | 15 |
| 15 | 25 | 18 | 12 | Цільова функція | |
| 15 | 25 | 18 | 12 | 223 | |
| Споживання | |||||
Висновки
Таким чином, представлена в даній розрахунково–економічній роботі транспортна задача вирішена із застосуванням комп’ютерної програми MsExcel. Цей метод дає можливість знайти оптимальний план перевезень товару, щоб при цьому затрати були мінімальними.
Описана у роботі задача про оптимальні перевезення і метод її рішення – тільки окремий приклад великої множини задач лінійного програмування. Мета транспортної задачі – розробка найбільш раціональних шляхів і способів транспортування товарів, ліквідація надмірно далеких, зустрічних та повторних перевезень. Усе це скорочує час просування товарів, зменшує затрати підприємств, пов’язані з здійсненням процесів постачання сировини, матеріалів, палива, обладнання тощо.
Перелік посилань
1. Гончаренко Л.С. Оформлення матеріалів самостійної роботи студентів: Навчальний посібник. – Херсон: МІБ, 1999. – 50 с.
2. Лугинин О.Е., Белоусова С.В., Львов М.С. Єкономико – математические методы и модели: Учебное пособие. – Херсон: МИБ, 1998. – 212 с.
3. Лугінін О.Є., Білоусова С.В., Білоусов О.М.. Економетрія: Навчальний посібник. – Херсон: МІБ, 2002. – 251 с.
4. Лук’яненко І.Г., Красикова Л.І. Економетрика: Підручник. – К.: Товариство «Знання» КОО, 1998. – 212 с.
5. Методичні вказівки до самостійної роботи студентів усіх форм навчання при вивченні дисципліни «Економетрія» / Укл. О.Є. Лугінін. – Херсон: МІБ, 2000.- 25 с.