![]()
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ВСТУП. ЗАДАЧА 1. ЗАДАЧА 2. ЗАДАЧА 3. ЗАДАЧА 4. ЗАДАЧА 5. ПЕРЕЛІК ПОСИЛАНЬ ⇐ ПредыдущаяСтр 3 из 3
Вінницький національний технічний університет
Кафедра теплогазопостачання
РОЗРАХУНКОВА РОБОТА з дисципліни “ Математичні методи розв’язання інженерних задач ”
Виконав студент ___ курсу групи ___ _________________
Керівник ________________
Структура та оформлення відповідає вимогам ДСТУ 3008-95 ________________
Вінниця - 2013 ЗМІСТ ВСТУП 3 ЗАДАЧА 1 4 ЗАДАЧА 2 8 ЗАДАЧА 3 14 ЗАДАЧА 4 20 ЗАДАЧА 5 26 ПЕРЕЛІК ПОСИЛАНЬ 35
ВСТУП Математичне моделювання є галуззю різноманітних наук, які вивчають основні принципи та інструментарій постановки технічних та економічних задач, побудови їх математичних моделей, методів розв’язування та аналізу цих задач з метою подальшого використання отриманих результатів. Метою розрахункової роботи є вивчення методів розв’язування різних типів задач. В розрахункової роботі розглядаються основні методи розв’язування, аналізу та використання задач зі знаходженням екстремуму функції на множині допустимих варіантів у широкому спектрі теоретико-економічних та практичних проблем. ЗАДАЧА 1 Побудувати на площині множину розв’язків (багатокутник) системи лінійних обмежень-нерівностей й геометрично знайти найбільше та найменше значення лінійної функції в цьому багатокутнику (x1³ 0, x2³ 0). Розв’язання Задана економіко-математична модель є моделлю задачі лінійного програмування, що містить лише дві змінні, і тому може бути розв’язана графічно. Перший крок згідно з графічним методом полягає в геометричному зображенні допустимих планів задачі, тобто у визначенні такої області, де водночас виконуються всі обмеження моделі. Замінимо знаки нерівностей на знаки строгих рівностей і побудуємо графіки відповідних прямих (рис. 1. 1. ). Рисунок 1. 1 Кожна з побудованих прямих поділяє площину системи координат на дві півплощини. Координати точок однієї з півплощин задовольняють розглядувану нерівність, а іншої — ні. Щоб визначити необхідну півплощину (на рис. 1. 1 її напрям позначено стрілкою), потрібно взяти будь-яку точку і перевірити, чи задовольняють її координати зазначене обмеження. Якщо задовольняють, то півплощина, в якій міститься вибрана точка, є геометричним зображенням нерівності. Інакше таким зображенням є інша півплощина. Умова невід’ємності змінних х1 ≥ 0, х2 ≥ 0 обмежує область допустимих планів задачі першим квадрантом системи координат. Переріз усіх півплощин визначає область допустимих планів задачі — шестикутник OABCDE. Координати будь-якої його точки задовольняють систему обмежень задачі та умову невід’ємності змінних. Тому поставлену задачу буде розв’язано, якщо ми зможемо відшукати таку точку багатокутника OABCDE, в якій цільова функція Z набирає найбільшого та найменшого значення. Для цього побудуємо вектор Побудуємо лінію, що відповідає, наприклад, значенню Z=0. Це буде пряма 50х1 + 30х2 = 0, яка перпендикулярна до вектора Із рис. 1. 1 видно, що останньою спільною точкою прямої цільової функції та багатокутника OABCDE є точка С. Координати цієї точки є оптимальним планом задачі. Координати точки С є розв’язком системи рівнянь
звідси маємо: х1 = 50; х2 = 60. Отже, Виходячи з аналогічних міркувань, знаходимо, що Перевіримо правильність рішення задачі за допомогою MS Excel (див. рис. 1. 2-1. 6). Рисунок 1. 2 Рисунок 1. 3 Рисунок 1. 4 Рисунок 1. 5 Рисунок 1. 6 ЗАДАЧА 2 Симплексним методом знайти розв’язок задачі.
Розв’язання 2. 1 Знаходження першого опорного плану задачі Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні х5 та х6: У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю: Канонічну систему обмежень задачі запишемо у векторній формі: де Оскільки вектори Згідно з визначеними Оскільки додатні коефіцієнти х5 та х6 відповідають лінійно незалежним векторам, то за означенням є опорним планом задачі і для цього початкового плану 2. 2 Складання симплексної таблиці для першого опорного плану Складемо симплексну таблицю для першого опорного плану задачі. Елементи останнього рядка симплекс-таблиці є оцінками У стовпчику «План» оцінкового рядка записуємо значення цільової функції Z, якого вона набуває для визначеного опорного плану: 2. 3 Перевірка опорного плану на оптимальність Після обчислення всіх оцінок опорний план перевіряємо на оптимальність. Для цього продивляємось елементи оцінкового рядка. Якщо всі У цій задачі в оцінковому рядку дві оцінки 2. 4 Перехід від одного опорного плану до іншого Перехід від одного опорного плану до іншого здійснюють зміною базису, тобто через виключення з поточного базису якоїсь змінної та включення замість неї нової з числа вільних змінних. Для введення до нового базису вибираємо змінну х2, оскільки їй відповідає найбільша за абсолютною величиною оцінка з-поміж тих, які не задовольняють умову оптимальності (|–10|> |–8|). Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х2» знаходимо відношення Друга симплексна таблиця має такий вигляд: У цій таблиці спочатку заповнюємо два перших стовпчики «Базис» і «Сбаз», а решту елементів нової таблиці розраховуємо за розглянутими нижче правилами: 1. Кожний елемент розв’язувального (напрямного) рядка необхідно поділити на розв’язувальний елемент і отримані числа записати у відповідний рядок нової симплексної таблиці. 2. Розв’язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв’язувального елемента. 3. Якщо в напрямному рядку є нульовий елемент, то відповідний стовпчик переписують у нову симплексну таблицю без змін. 4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін. Усі інші елементи наступної симплексної таблиці розраховують за правилом прямокутника. Щоб визначити будь-який елемент нової таблиці за цим правилом, необхідно в попередній симплексній таблиці скласти умовний прямокутник, вершини якого утворюються такими числами: 1 – розв’язувальний елемент (число 1); 2 – число, що стоїть на місці елемента нової симплексної таблиці, який ми маємо розрахувати; 3 та 4 – елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника. Необхідний елемент нової симплекс-таблиці визначаємо за такою формулою:
Наприклад, визначимо елемент Тоді Аналогічно розраховуємо усі елементи нової симплексної таблиці, у тому числі й елементи стовпчика «План» та оцінкового рядка. Наявність двох способів зображення визначення оцінок опорного плану (за правилом прямокутника та за відповідною формулою) дає змогу контролювати правильність арифметичних обчислень на кожному кроці симплекс-методу. Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності Zj – сj ≥ 0 для другого опорного плану. Цей план також неоптимальний, оскільки В оцінковому рядку третьої симплексної таблиці немає від’ємних чисел, тобто всі або Х* = (48; 118; 0; 0; 0; 0); (2. 16) Перевіримо правильність рішення задачі за допомогою MS Excel (див. рис. 2. 1-2. 3). Рисунок 2. 1 Рисунок 2. 2 Рисунок 2. 3
ЗАДАЧА 3 Побудувати двоїсту задачу до заданої та знайти її розв’язок. Використовуючи теореми двоїстості знайти розв’язок прямої задачі. Задана пряма задача має вигляд: max Z = – 5x1 + 2x2; Розв’язання Двоїста задача утворюється за такими правилами: 1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі. 2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі. 3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі – на визначення найменшого значення (min), і навпаки. 4. Коефіцієнтами при змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі. Двоїстою до задачі max Z=c0 + (c, x), Ax=b, x³ 0, (записаній у векторно-матричній формі) є
де Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція Z максимізується і в системі обмежень є нерівності, то їх слід звести до виду « max Z = – 5x1 + 2x2; (3. 1) За наведеними вище правилами складемо двоїсту задачу: min F = – y1 + 5y2; (3. 3) Оскільки записані задачі симетричні (обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невід’ємних значень), то будь-яку з них можна розв’язати симплекс-методом. Наприклад, визначимо спочатку оптимальний план прямої задачі. Для цього застосуємо алгоритм симплекс-методу. 1. max Z = – 5x1 + 2x2 + 0x3 + 0x4; (3. 5) 2. Векторна форма запису системи обмежень має вигляд: де У системі векторів для утворення початкового одиничного базису відсутній один вектор. Тому введемо штучну змінну в перше обмеження. 3. Розширена задача лінійного програмування буде такою: max Z = – 5x1 + 2x2 + 0x3 + 0x4 – Мx5; (3. 8)
У цій задачі х4 та х5 – базисні змінні, а х1, х2, х3 – вільні. Нехай х1=х2=х3=0, тоді х4=5; х5=1. Перший опорний план задачі: X0=(0; 0; 0; 5; 1), Z0 = – M. (3. 10) 4. Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці: З останньої симплекс-таблиці запишемо оптимальний план прямої задачі: Х*=(0; 5/3; 2/3; 0), Zmax = 10/3. (3. 11) Згідно зі співвідношенням двоїстості за першою теоремою (якщо одна з пари спряжених задач має оптимальний план, то й друга задача також має розв’язок, причому для оптимальних розв’язків значення цільових функцій обох задач збігаються) можна зробити висновок, що оптимальний план двоїстої задачі існує і min F = max Z = 10/3. (3. 12) Компоненти вектора Y* (оптимальний план двоїстої задачі) визначимо за формулою: де Матриця D– 1 також міститься в останній симплекс-таблиці у стовпчиках змінних «x5» та «x4», які утворювали початковий базис. Отже, min F = – 1× 0 + 5× 2/3 = 10/3. (3. 16) Застосувавши для розв’язування прямої задачі симплекс-метод, ми знайшли її оптимальний план, а потім визначили оптимальний розв’язок двоїстої задачі за допомогою співвідношень першої теореми двоїстості. Перевіримо правильність рішення прямої задачі за допомогою MS Excel (див. рис. 3. 1-3. 3). Рисунок 3. 1 Рисунок 3. 2 Рисунок 3. 3 Перевіримо правильність рішення двоїстої задачі за допомогою MS Excel (див. рис. 3. 4-3. 6). Рисунок 3. 4 Рисунок 3. 5 Рисунок 3. 6 ЗАДАЧА 4 Компанія контролює три фабрики А1, А2, А3, здатні виготовляти відповідно 150, 60 та 80 тис. од. продукції щотижня. Вона уклала договір із чотирма замовниками В1, В2, В3, В4, яким потрібно щотижня доставляти відповідно 110, 40, 60 та 80 тис. од. продукції. Вартість транспортування 1 тис. од. продукції замовникам з кожної фабрики наведена в таблиці: Необхідно визначити оптимальний план перевезень продукції від кожної фабрики до замовників, що мінімізує загальну вартість транспортних послуг. Розв’язання 4. 1 Побудова математичної моделі Нехай xij – кількість продукції, що перевозиться з і-ої фабрики до j-го замовника min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24 + 2x31 + x32 ++ 4x33 +2x34 (4. 1) за умов:
4. 2 Знаходження першого опорного плану задачі Запишемо умови задачі у вигляді транспортної таблиці (табл. 4. 1) та складемо її перший опорний план у цій таблиці методом мінімальної вартості. Таблиця 4. 1 Загальна вартість перевезень продукції згідно з першим опорним планом визначається у такий спосіб: Z1 = 4× 110 + 5× 40 + 1× 60 + 1× 40 + 2× 40 = 820 (ум. од. ). (4. 3) Перший опорний план транспортної задачі вироджений, оскільки кількість заповнених клітинок у таблиці дорівнює п’яти, а (m+n–1) = 3+4–1=6. Для дальшого розв’язування задачі необхідно в одну з порожніх клітинок записати «нульове перевезення» так, щоб не порушити опорності плану, тобто можна зайняти будь-яку пусту клітинку, яка не утворює замкненого циклу із заповненими клітинами. Наприклад, заповнимо нулем клітинку А2В4. Тепер перший план транспортної задачі є невиродженим, і його можна перевірити на оптимальність методом потенціалів. 4. 3 Перевірка опорного плану на оптимальність На основі першої умови оптимальності ui + vj = cij складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану: Записана система рівнянь є невизначеною, і один з її розв’язків дістанемо, узявши, наприклад, v4 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1=5, u2=2, u3=2, v1= – 1, v2= – 1, v3= – 1. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю. Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці): А1B2: u1 + v2 = 5 + (–1) = 4 = 4; (4. 5) А1B3: u1 + v3 = 5 + (–1) = 4 > 2; (4. 6) А2B1: u2 + v1 = 2 + (–1) = 1 < 5; (4. 7) А2B2: u2 + v2 = 2 + (–1) = 1 < 3; (4. 8) А3B1: u3 + v1 = 2 + (–1) = 1 < 2; (4. 9) А3B3: u3 + v3 = 2 + (–1) = 1 < 4. (4. 10) Умова оптимальності не виконується для клітинки А1B3. Порушення D13=(u1+v3)–c13 = 4 – 2 = 2 записуємо в лівому нижньому кутку відповідної клітинки. Отже, перший опорний план транспортної задачі неоптимальний. Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці.
4. 4 Перехід від одного опорного плану до іншого Потрібно заповнити клітинку А1B3, в якій є єдине порушення умови оптимальності. Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А1B3, та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А1B3 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–». У даному разі Отже, другий опорний план транспортної задачі матиме такий вигляд (табл. 4. 2). Таблиця 4. 2 Розрахуємо значення цільової функції відповідно до другого опорного плану задачі: Z2 = 4× 110 + 2× 40 + 1× 20 + 2× 40 + 1× 40 + 2× 40 = 740 (ум. од. ). (4. 11) Новий план знову перевіряємо на оптимальність, тобто повторюємо описані раніше дії. Другий опорний план транспортної задачі також неоптимальний (має місце порушення для клітинки А3B1). За допомогою побудованого циклу, виконавши перехід до третього опорного плану транспортної задачі, отримуємо табл. 4. 3. Таблиця 4. 3 Визначимо загальну вартість витрат на транспортування продукції згідно з третім опорним планом: Z3 = 4× 90 + 2× 60 + 2× 60 + 2× 20 + 1× 40 + 2× 20 = 720 (ум. од. ). (4. 12) Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний. Тому: За оптимальним планом перевезень перший замовник отримує 90 тис. од. продукції з першої фабрики та 20 тис. од. — з третьої. Другий споживач задовольняє свій попит за рахунок виробництва та перевезення 40 тис. од. продукції з третьої фабрики і т. д. При цьому загальна вартість перевезень всієї продукції є найменшою і становить 720 ум. од. Перевіримо правильність рішення задачі за допомогою MS Excel (див. рис. 4. 1-4. 3). Рисунок 4. 1 Рисунок 4. 2 Рисунок 4. 3 ЗАДАЧА 5 Дані про роздрібний товарообіг і доходи населення в умовних грошових одиницях в деякій країні за 1996-2007рр. представлені в табл. 5. 1. Таблиця 5. 1 – Роздрібний товарообіг і доходи населення
Необхідно розрахувати методом найменших квадратів оцінки параметрів споживчої функції; перевірити достовірність вибраної лінії регресії методом аналізу дисперсій; оцінити лінійний коефіцієнт кореляції; визначити довірчі інтервали для Розв’язання 5. 1 Оцінка параметрів споживчої функції Зв’язок між роздрібним товарообігом і доходом населення носить прямолінійний характер, тому споживча функція має вигляд [3]: де
Для оцінювання параметрів Для знаходження де
Для зручності розрахунку моментів побудуємо таблицю 5. 2. Таблиця 5. 2 – Проміжні розрахунки
Таким чином, маємо споживчу функцію: 5. 2 Перевірка достовірності підібраної лінії регресії методом аналізу дисперсій за критерієм Фішера Розрахуємо критерій Фішера [3]:
де
де
Виходячи з даних міркувань: Таблиця 5. 3 – Таблиця аналізу дисперсій
Таблиця 5. 4 – Таблиця аналізу дисперсій стосовно даних задачі
Таким чином: де
5. 3. Оцінка лінійного коефіцієнту кореляції Оцінку лінійного коефіцієнта кореляції r виконаємо за такою формулою [3]: Високий лінійний коефіцієнт кореляції свідчить про тісний взаємозв’язок між роздрібним товарообігом та рівнем доходу. 5. 4 Побудова довірчих інтервалів для Побудова довірчого інтервалу b для кутового коефіцієнту кореляції де
Приймається якісна гіпотеза, відповідно до якої Формула для розрахунку Знайдений інтервал не має значень 0 та 1, тому результати регресії відповідають якісній гіпотезі, згідно до якої Побудову довірчого інтервалу де
До інтервалу входять як від’ємні, так і додатні значення, отже при 95% імовірності похибка при оцінюванні Побудову довірчого інтервалу де
Розподіл Тоді за таблицею Знаходимо Визначаємо при 95% рівні імовірності довірчі інтервали для Скориставшись знову таблицями
Отже Оцінка лінійного коефіцієнту кореляції є досить точною, а значить, тіснота зв’язку між роздрібним товарообігом та рівнем доходу громадян є дуже високою. 5. 5 Побудова знайденої лінії регресії на одному графіку з вихідними даними В кінці рішення задачі побудуємо на одному графіку вихідні дані та лінію регресії (рис. 5. 1): Рисунок 5. 1 – Вихідні дані та лінія регресії Висновок: Побудована споживча функція має вигляд: ПЕРЕЛІК ПОСИЛАНЬ 1. Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. – К.: КНЕУ, 2003. – 452 с. 2. Курицкий Б. Я. Поиск оптимальных решений средствами Ехсеl 7. 0. – СПб.: ВНV, 1997. – 384 с. 3. Наконечний С. І., Терещенко Т. О., Романюк Т. П. Економетрія: Підручник. – К.: КНЕУ, 1997. – 352с.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|