РЕФЕРАТ
Побудовата реалізація економіко–математичної моделі
Розрахунково–економічнаробота «Побудова та реалізація економіко–математичної моделі» містить 15сторінок тексту, 2 таблиці, 5 використаних джерел.
В роботірозглянута загальна модель задачі математичного програмування, задача лінійногопрограмування та особливості симплекс–методу для розв’язання задач лінійного програмування.Також побудована економіко–математична модель конкретної задачі, описанийалгоритм її вирішення за допомогою Exel та приведена таблиця з рішенням даної задачі.
Метою роботи єрозкриття поняття задачі лінійного програмування та її економіко–математичноїмоделі, опис функцій і команд у вирішенні задач лінійного програмуваннязасобами Exel, а також рішення конкретноїзадачі за допомогою ПК.
Вступ
Економетрія –комплекс економіко–математичних методів і побудованих на їх основі моделей длякількісного вимірювання взаємозв’язків між економічними факторами.
Економіко–математичнамодель – математичний опис економічного процесу або явища з метою йогодослідження та керування ним.
Під назвою«транспортна задача» об’єднується широке коло задач з єдиною математичною моделлю. Дані задачі відносяться до задач лінійногопрограмування і можуть бути вирішені симплексним методом. Проте матриця системиобмежень транспортної задачі настільки своєрідна, що для її рішення розробленіспеціальні методи, у тому числі, метод рішення за допомогою Exel. Ці методи, як і симплексний метод,дозволяють знайти початкове опорне решення, а потім, покращуючи його, отриматиоптимальне рішення.
Сутністьтранспортної задачі полягає в тому, щоб забезпечити мінімальні транспортнівитрати перевезень вантажу від постачальників до споживачів (цільова функція),і при цьому вантаж від постачальників має бути вивезеним (обмеження наспроможність постачальників), а потреби споживачів – задоволені (обмеження напотреби споживачів).
Метою роботи єрозкриття поняття задачі лінійного програмування та її економіко – математичноїмоделі, опис функцій і команд у вирішенні задач лінійного програмуваннязасобами Exel, а також рішення конкретноїзадачі за допомогою ПК.
1. Побудоваекономіко–математичної моделі
Загальнамодель задачі математичного програмування має такий вигляд:
/>
У структурі моделі (1.1) можна виділити 3 елементи:
1) Набір керованих змінних x1,x2,… x n, значення яких підлягають оптимізації. Різні допустимікомбінації значень змінних відповідають можливим розв’язкам задачі. 2) Цільовафункція z (x1, x2,… x n) — функція, що виражає залежність прийнятого критеріюоптимальності від керованих змінних. Критерій оптимальності є мірою наближеннярозв’язку до поставленої мети. В економічних задачах, як правило, такимкритерієм виступає показник ефективності функціонування системи (наприклад,прибуток від реалізації продукції, продуктивність праці, таке інше) абопоказник витрат. 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
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+1,…, 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 + 4X41 + 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 Матриця рішень Запаси 22 3 25 25 3 3 12 18 18 12 12 12 15 15 15 15 25 18 12 Цільова функція 15 25 18 12 223 Споживання
Висновки
Таким чином,представлена в даній розрахунково–економічній роботі транспортна задачавирішена із застосуванням комп’ютерноїпрограми Ms Excel. Цей метод дає можливість знайтиоптимальний план перевезень товару, щоб при цьому затрати були мінімальними.
Описана у роботізадача про оптимальні перевезення і метод її рішення – тільки окремий прикладвеликої множини задач лінійного програмування. Мета транспортної задачі –розробка найбільш раціональних шляхів і способів транспортування товарів,ліквідація надмірно далеких, зустрічних та повторних перевезень. Усе цескорочує час просування товарів, зменшує затрати підприємств, пов’язані з здійсненням процесівпостачання сировини, матеріалів, палива, обладнання тощо.
Перелік посилань
1. ГончаренкоЛ.С. Оформлення матеріалів самостійної роботи студентів: Навчальний посібник. –Херсон: МІБ, 1999. – 50 с.
2. Лугинин О.Е., БелоусоваС.В., Львов М.С. Єкономико – математические методы имодели: Учебное пособие. – Херсон: МИБ, 1998. – 212 с.
3. ЛугінінО.Є., Білоусова С.В., Білоусов О.М… Економетрія: Навчальний посібник. –Херсон: МІБ, 2002. – 251 с.
4. Лук’яненко І.Г., Красикова Л.І. Економетрика:Підручник. – К.: Товариство «Знання» КОО, 1998. – 212 с.
5. Методичнівказівки до самостійної роботи студентів усіх форм навчання при вивченнідисципліни «Економетрія» / Укл. О.Є. Лугінін. – Херсон: МІБ, 2000.- 25 с.