- •Конспект лекцій Частина і з дисципліни “Числові методи і моделювання на еом”
- •Лекция 1 числові методи алгебри. Особливості алгоритмування обчислювальних задач. Елементи теорії похибок обчислень та аналізу помилок округлення. Порядок виконання операцій
- •1.1. Про наближені обчислення
- •1.2. Лінійні заміни змінних
- •1.3. Системи лінійних алгебраїчних рівнянь
- •2.1. Апроксимація функції по Фур'є.
- •2.1.1. Перетворення Фур'є
- •2.2. Зворотна матриця
- •3.1. Метод ділення відрізка навпіл для розв'язання рівнянь
- •3.2. Метод хорд для рішення рівнянь
- •3.3. Метод дотичних для розв'язання рівнянь
- •3.4. Методика рішення алгебраїчного рівняння
- •Метод простих ітерацій
- •Метод Зейделя
- •Метод ітерацій для рішення рівнянь
- •4.4. Метод ітерацій для рішення систем нелінійних алгебраїчних і
- •Лекция 5 звернення матриць. Подвійність у лінійному програмуванні. Одночасне рішення пари двоїстих задач лінійного програмування.
- •Лекція 6
- •6.1. Чисельне диференціювання функції однієї змінної.
- •6.2. Чисельне інтегрування функції однієї змінної.
- •6. 3. Постановка задачі про чисельне рішення звичайного диференціального рівняння.
- •6.5. Метод Рунге-Кутта чисельного рішення звичайного диференціального рівняння.
- •6.6. Підхід до чисельного рішення системи звичайних диференціальних
- •Лекция 7 методи розв’язку диференціальних рівнянь та їх систем. Розв'язання систем лінійних алгебричних рівнянь із допомогою жорданових виключень
- •Лекция 8 чисельне диференціювання та інтегрування. Основна задача лінійного програмування. Дослідження її окремих випадків. Модифікований варіант жордановых винятків
- •8.1. Постановка основної задачі лінійного програмування (озлп)
- •8.2. Екстремальні задачі, що зводяться до озлп заміною змінних
- •8.3. Лінійна заміна змінних і її використання в дослідженні основної
- •8.4. Модифікований варіант жордановых виключень як спосіб організації лінійної заміни змінних
- •Лекция 9 диференціювання інтерполяційних формул. Мова « n-мірних» точок. Геометрія задачі лінійного програмування. Опорне рішення й оптимальне рішення. Загальні установки симплекса-методу
- •9.1.Мова n-мірних точок.
- •9.2. Геометрія задачі лінійного програмування.
- •Опорне рішення й оптимальне рішення. Загальні установки симплекс-методу
- •Підготовка озлп до рішення симплекс-методом.
- •Список рекомендованої літератури
Лекция 9 диференціювання інтерполяційних формул. Мова « n-мірних» точок. Геометрія задачі лінійного програмування. Опорне рішення й оптимальне рішення. Загальні установки симплекса-методу
9.1.Мова n-мірних точок.
Прийнято використовувати ряд геометричних термінів у контексті задачі лінійного програмування. Всі вони виникли в аналітичній геометрії й лінійній алгебрі. Ми нагадаємо тут їхнього визначення.
Набір чисел називається точкою -мірного простору або просто - крапкою. Коли =2 або 3 ми маємо точку звичайної площини або звичайного тривимірного простору. У задачі лінійного програмування мова, отже, іде про пошук точки, у якій деяка функція досягає максимуму.
9.2. Геометрія задачі лінійного програмування.
Розглянемо обмеження в ОЗЛП. Кожне з них має вигляд:
.
Це означає, що кожне з них виділяє тільки такі точки, які цій умові задовольняють. Коли =2, ці крапки являють собою напівплощину. Отже, при =2 всі умови в сукупності вказують на точки площини, що належать відразу декільком напівплощинам. Ця область може являти собою звичайний багатокутник, може являти собою необмежену множину із прямолінійно - ломаній границею, може бути
порожньою множиною; в останньому випадку говорять, що ОЗЛП - суперечливо.
Ці ж терміни прийнятий переносити й на -мірний випадок, у якому, отже, мова йде про крапку, що дає максимум функції щодо значень цієї функції на перетинанні півпросторів (слово півпростір заміняє слово напівплощина).
Опорне рішення й оптимальне рішення. Загальні установки симплекс-методу
Можна довести, що якщо вже в ОЗЛП рішення є, то розташовано воно на границі тої багатокутної області, що задають обмеження й, більше того - в одній з вершин цієї багатокутної границі. Коли =2 все сказане має природний геометричний зміст (і багатокутна границя, і її вершина). У загальному ж - мірному випадку сказане означає, що якщо необхідна точка максимуму існує, то вона обертає хоч одне обмеження в рівність.
Є класичний симплекс-метод рішення ОЗЛП, що складає в тім, що спочатку відшукується хоч якась точка, що задовольняє всім обмеженням і, притім, що обертає хоч одне з обмежень у рівність. Ця точка відшукується безвідносно до цільової функції. Якщо з'ясовується, що такої точки ні, то говорять, що задача суперечлива (обмеження не здійсненні одночасно). Якщо така точка відшукується, то неї називають опорним рішенням ОЗЛП.
Потім, відповідно до симплекс-методом, проводиться спеціальний відбір опорних рішень для того, щоб знайти серед них точку максимуму. Якщо така відшукується, то ОЗЛП вирішена й знайдена точка називається оптимальним рішенням. Якщо з'ясовується, що такої точки ні, то це означає, що цільова функція необмежена в заданої обмеженнями області.
Коли =2, неважко намалювати приклади ОЗЛП, що є суперечливої, або має необмежену цільову функцію або, нарешті, що має конкретне рішення й, навіть, не одне.
Підготовка озлп до рішення симплекс-методом.
Ми сформулюємо тут дії, які необхідно зробити перед включенням
симплекс-методу. Отже, є ОЗЛП:
при обмеженнях:
.
Установимо, є чи серед обмежень такі, які мають такий вигляд:
.
Якщо таких обмежень ні, то ніякої підготовки до симплекс-методу не потрібно. Якщо ж такі є, то з кожним з них треба провести наступні дії. Треба розглянути знак числа u; якщо , те обмеження заміняється на наступне:
.
Якщо , то зробимо заміну: , тобто всюди замінимо на . Саме обмеження замінимо на . У результаті такої підготовки в системі обмежень всі змінні ( і ) розподіляться на дві групи: в одній групі будуть змінні, на знак яких накладене обмеження (типу ); вони будуть називатися невільними; в іншу групу ввійдуть всі інші змінні; вони будуть називатися вільними. На цьому підготовка до включення симплекс-методу закінчена.