Курсова робота на тему: «ОБРОБКА АЛГОРИТМІВ РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ В СЕРЕДОВИЩІ VISUAL BASIC .NET»

Зміст

Вступ    3

РОЗДІЛ І. Основні поняття математичного програмування    5

1.1. Мета і предмет математичного програмування.    5

1.2. Загальна постановка задачі математичного програмування (ЗМП).    6

1.3. Коротка класифікація моделей математичного програмування.    7

РОЗДІЛ ІІ. Симплекс метод розв’язування задач лінійного програмування.    9

2.1. Основні поняття симплекс-методу    9

2.2. Алгоритм симплексного методу    11

Висновки    23

Список використаної літератури    24

 

 

Вступ

Математичне програмування — це розділ прикладної математики, який вивчає задачі пошуку екстремуму функції
на певній множині М n-вимірного евклідового простору і розробляє методи їх розв’язання. Характерною особливістю задач математичного програмування є те, що оптимальне значення числової функції f, як звичайно, досягається на межі множини М, тому використати класичні методи пошуку екстремуму функції при розв’язанні таких задач практично неможливо.

Математичне програмування виникло у зв’язку з використанням математичних методів дослідження у різних галузях народного господарства, зумовленим прогресом обчислювальної техніки. Широке застосування математичних методів і сучасної обчислювальної техніки — один з важливих напрямів удосконалення управління народним господарством, важливий інструмент для обґрунтування рішень у всіх сферах цілеспрямованої людської діяльності.

Серед задач математичного програмування найпростішими (і найкраще вивченими) є так звані задачі лінійного програмування. Характерним для цих задач є те, що функція f лінійно залежить від елементів розв’язку , і обмеження, які накладаються на елементи розв’язку, мають вигляд лінійних рівнянь або нерівностей щодо . Такі задачі досить часто трапляються на практиці, наприклад, при розв’язанні проблем розподілу ресурсів, планування виробництва, керування різноманітними виробничими та технологічними процесами, організації роботи транспорту і т. ін.

Початком розвитку лінійного програмування вважається 1949 р., коли американський математик Дж. Данціг опублікував обчислювальний алгоритм для розв’язування задач лінійного програмування. З цього часу фактично розпочався феноменальний ріст інтересу до теорії і практики лінійного програмування. І вже досить швидко були одержані фундаментальні результати в лінійному програмуванні, які сьогодні стали класичними. Водночас дослідження в галузі лінійного програмування продовжуються. В останні роки з’явилася низка нових цікавих результатів, які стосуються лінійного програмування.

 

РОЗДІЛ І. Основні поняття математичного програмування

1.1. Мета і предмет математичного програмування.

Математичне програмування – складова частина прикладної математичної дисципліни «Дослідження операцій». До інших основних розділів цієї дисципліни відносяться теорія масового обслуговування, теорія ігор, методи мережевого планування. Мета дослідження операцій полягає в тому, щоб виявити оптимальний (найкращий) спосіб дій при розв’язанні задач керування системами, зокрема – економічними. Предметом вивчення математичного програмування є задачі пошуку оптимальних управлінських рішень, що математично зводяться до задач знаходження умовного екстремуму функції багатьох змінних.

Назва дисципліни походить від англійського “Programing”, що перекладається як процес пошуку найкращої програми (плану) дій. Слово “математичне” вказує на те, що такий пошук має проводитись із застосуванням математичних методів.

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

Загальна модель задачі математичного програмування має такий вигляд:


 У структурі моделі задачі математичного програмування можна виділити 3 елементи:

1) Набір керованих змінних x1, x2, … x n, значення яких підлягають оптимізації. Різні допустимі комбінації значень змінних відповідають можливим розв’язкам задачі.

2) Цільова функція z (x1, x2, … x n) – функція, що виражає залежність прийнятого критерію оптимальності від керованих змінних.

Критерій оптимальності є мірою наближення розв’язку до поставленої мети. В економічних задачах, як правило, таким критерієм виступає показник ефективності функціонування системи (наприклад, прибуток від реалізації продукції, продуктивність праці, таке інше) або показник витрат. Слід зазначити, що одній меті можуть відповідати декілька критеріїв оптимальності (багатокритеріальна задача); в цьому разі цільова функція має враховувати всі виділені критерії.

3) Умови або обмеження g (x1, x2, … x n), що накладаються на значення змінних або на співвідношення між ними.

ція моделей математичного програмування.

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

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

В залежності від характеру функцій, що входять до складу моделі, задачі МП можуть бути лінійними або нелінійними. Якщо цільова функція і функції всіх обмежень моделює лінійними, то дана задача являє собою задачу лінійного програмування (ЗЛП). В інших випадках, якщо хоча б одна функція в складі моделі є нелінійною, маємо справу із задачею нелінійного програмування (ЗНЛП). Зазначимо, що для ЗЛП розроблені універсальний і ціла низка часткових методів розв’язання. Навпаки, лише незначна частина ЗНЛП (а саме, задачі опуклого програмування) може бути ефективно розв’язана частковими методами. Оскільки в даному курсі будуть розглядатись тільки лінійні оптимізаційні моделі, то має сенс представити загальний вид задачі лінійного програмування, а саме:

Z= C1x1, C2x2, … Cnxn → max (min)

За типом змінних розрізняють задачі МП з неперервними та дискретними змінними. Останні створюють окремий клас задач дискретного програмування, підкласом якого є задачі цілочисельного програмування.

За фактором часу задачі математичного програмування поділяють на статичні та динамічні.

Нарешті, в залежності від того, якими є параметри моделі, – постійними чи імовірнісними величинами, – розрізняють ЗМП детерміновані та стохастичні.

Коротка класифікація моделей математичного програмування представлена на мал. 1.


Мал. 1. Класифікація моделей математичного програмування.

Математичне програмування займається вивченням екстремальних завдань і пошуком методів їх рішення. Завдання математичного програмування формулюються таким чином : знайти екстремум деякої функції багатьох змінних f ( x1, x2 …, xn ) при обмеженнях gi(x1, x2, …, xn ) bi, де gi – функція, що описує обмеження, – один з наступних знаків,,, а bi – дійсне число, i = 1 …, m. f називається кінцевою функцією ( цільова функція ).

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Obrobka Algor Rozv Zadach Lin Progr (563.5 KiB, Завантажень: 2)

Сторінка: 1 2 3 4 5 6
завантаження...
WordPress: 23.69MB | MySQL:26 | 0,328sec