5.Метод Жорано –гауса

 У різноманітних галузях людських знань (наука, виробництво, економіка, теорія масового обслуговування, тощо) часто виникають задачі, розв’язування яких приводить до систем лінійних рівнянь, в яких кількість рівнянь не обов’язково дорівнює кількості невідомих. Невідомих може бути більше або менше від кількості рівнянь. Для розв’язування таких систем розроблено ряд методів, у тому числі й за допомогою визначників. Але найпоширеніший з них - метод Жордана-Гаусса, який не потребує попередніх досліджень на сумісність або несумісність. У процесі розв’язування завжди стає ясно, має система розв’язки чи не має, єдиний її розв’язок чи ні. Оскільки для розв’язування системи рівнянь методом Жордана-Гаусса потрібно на порядок менше математичних операцій, ніж при розв’язуванні за формулами Крамера, то метод Жордана-Гаусса став основним при побудові стандартних програм для сучасних комп’ютерів.

Метод Жордана-Гаусса полягає в послідовному виключенні невідомих за допомогою елементарних перетворень: 1) множення рівняння на деяке число ; 2)заміна одного з рівнянь системи сумою з іншим рівнянням тієї ж системи, помножимо на деяке число; 3) видалення з системи рівнянь тотожностей . З допомогою перетворення 2) можна виключити деяке невідоме із усіх рівнянь системи, крім одного.

Виберемо для цього рівняння з номером 1), що містить невідоме : Це рівняння будемо називати ведучим, а - ведучим невідомим. Для виключення ведучого невідомого   з рівняння з номером додамо до нього ведуче рівняння, помножене на деяке число . Тоді одержимо Щоб виключити невідоме , прирівняємо до нуля коефіцієнт при , тобто Тоді рівняння матиме вигляд одержимо систему рівнянь, в якій невідоме міститиметься тільки в -му рівнянні, а в інших рівняннях невідомого не буде. Таким самим способом, приймаючи в ролі ведучого інше рівняння, можна з усієї решти рівнянь виключити ведуче вибране невідоме. Продовжуючи цей процес доти, поки кожне рівняння побуде ведучим тільки один раз, прийдемо до системи рівнянь вигляду У ролі ведучого послідовно бралися рівняння 1-ше та -те, а в ролі ведучого невідомого бралися послідовно . Якщо при цьому жодне рівняння не перетворювалося в тотожність , то зрозуміло, вони далі в процесі перетворення не беруть участі і тому виключаються з системи. У цьому випадку в системі кількість рівнянь буде меншою, ніж . Якщо описаний процес проводився в іншому порядку, то після його закінчення члени в рівняннях завжди можна переставити так, щоб система набрала вигляду У випадку, коли в процесі розв’язування системи рівнянь де-небудь ліва частина якогось рівняння перетворюється в нуль, а права-не дорівнює нулю, то це означає, що система несумісна і тому обчислення треба припинити. У рівнянні невідомі  називаються базисними, а решта змінних - небазисними. Базисний розв’язок складається з базисних змінних і нулів, причому нулям відповідають небазисні змінні. Якщо в базисі є стільки змінних, скільки рівнянь, то такий базис називається невиродженим. Якщо базисних змінних менше, ніж , то такий базис називається виродженим.

6.Завдання динамічного програмування і методи їх рішення.

Динамічне програмування являє собою математичний апарат, що дає змогу здійснювати планування багатокрокових керованих процесів, а також процесів, які розвиваються у часі.

Отже, динамічне програмування не є окремим методом розв’язування задач, а являє собою теорію, що поєднує ряд однотипних ідей та прийомів, які застосовуються для розв’язування досить різних за змістом задач.

До задач динамічного програмування належать такі, що пов’язані з оптимальним розподілом капіталовкладень, розподілом продукції між різними регіонами, визначенням найкоротшого шляху завезення товарів споживачам, задачі щодо заміни устаткування, оптимального управління запасами тощо.

Економічні процеси можна уявити складеними з кількох етапів (кроків). На кожному з них здійснюється вплив на розвиток всього процесу. Тому у разі планування багатоетапних процесів прийняття рішень на кожному етапі має враховувати попередні зміни та бути підпорядкованим кінцевому результату. Динамічне програмування дає змогу прийняти ряд послідовних рішень, що забезпечує оптимальність розвитку процесу в цілому.

Слід зазначити, що оптимальні плани стосовно окремих відрізків планового періоду не завжди є оптимальними для всього інтервалу планування. Наприклад, недостатньо визначити оптимальний план виробництва на один місяць і орієнтуватися на нього протягом тривалого часу. Досить ймовірно, що в наступні місяці виробництво за тим самим планом може стати неоптимальним, оскільки за його розроблення можливості дальшого розвитку не враховувались. Доцільніше визначати оптимальні плани на кожен місяць з урахуванням змін у попередніх періодах. Лише тоді річний оптимальний план виробництва буде сумарним результатом оптимальних рішень, що приймалися для кожного місяця.

Поставимо задачу динамічного програмування в загальному вигляді.

Нехай аналізується деякий керований процес, подання якого допускає декомпозицію на послідовні етапи (кроки), кількість яких n задана. Ефективність всього процесу Z може бути подана як сума ефективностей     окремих кроків, тобто:

,

що має назву адитивного критерію (або як добуток ефективностей     окремих кроків у вигляді:  , що має назву мультиплікативного критерію).

З кожним етапом (кроком) задачі пов’язане прийняття певного рішення, так званогокрокового управління     що визначає як ефективність даного етапу, так і всього процесу в цілому.

Розв’язування задачі динамічного програмування полягає в знаходженні такого управління  процесом у цілому, яке максимізує загальну ефективність:   (max  ).

Оптимальним розв’язком цієї задачі є управління   що складається з сукупності оптимальних покрокових управлінь:

і уможливлює досягнення максимальної ефективності: