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

Загальна модель задачі математичного програмування, задача лінійного програмування та особливості симплекс–методу для розв’язання задач лінійного програмування Економіко–математична модель конкретної задачі, алгоритм її вирішення за допомогою Exel.
Краткое сожержание материала:

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. - Вхі...