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

Змістовий модуль 4.

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

Семінарське заняття 28

Тема 27. Основні поняття математичного програмування. Тема 28. Лінійне програмування. Геометричний і симплексний методи розв’язування ЗЛП

Питання для усного опитування та дискусії

27.1. Задача математичного програмування.

27.2. Цільова функція.

27.3. Ресурсні обмеження.

28.1. Лінійне програмування. Економічні приклади ЗЛП.

28.2. Геометричний спосіб розв’язування ЗЛП.

28.3. Симплекс-метод розв’язування ЗЛП.

Аудиторна письмова робота

Виконання студентами тестових завдань з питань теми заняття.

Методичні вказівки

Ключовими термінами, на розумінні яких базується засвоєння навчального матеріалу теми, є: математичне програмування, цільова функція, ресурсні обмеження, лінійне програмування, геометричний спосіб розв’язування ЗЛП, симплекс-метод, ключовий рядок, ключовий стовпчик, генеральний елемент.

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

Математичне програмування – один з головних інструментів теорії дослідження операцій; математичне програмування вивчає методи розв’язування оптимізаційних задач та дослідження їх розв’язків.

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

Провідне місце у математичному програмуванні посідає задача лінійного програмування (ЗЛП). ЗЛП характеризується лінійною цільовою функцією та лінійними ресурсними обмеженнями. ЗЛП формулюється так: максимізувати (чи мінімізувати) цільову функцію ƒ, що є лінійною формою відносно невідомих x₁, x₂,…,x_n:

ƒ = c₁x₁+c₂x₂+…+c_nx_n→max (min)

(або, що те саме, maxf (min f)) за умови виконання лінійних обмежень виду

(ці обмеження називають ресурсними) та характерних для економічних задач обмежень невід’ємності змінних: x₁≥0, x₂≥0,…,x_n≥0.

Розглянемо ЗЛП з цільовою функцією, вираженою у грошових одиницях, що лінійно виражається через невідомі х₁ та х₂, наприклад, у такий спосіб: .

Нехай ресурсні обмеження мають вигляд:

,

х ₁ ≥ 0, х ₂ ≥ 0.

Цю задачу можна розв’язати графічно (графічний метод розв’язання ЗЛП ефективний лише при п=2). Для цього побудуємо область, що визначається даними ресурсними обмеженнями (рис.1).

Рис. 1. Графічний розв’язок ЗЛП.

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

Щоб визначити координати точки М, розв’яжемо систему рівнянь:

Маємо: , .

При цьому цільова функція (грошових одиниць).

При n > 3 графічним способом знайти розв’язок ЗЛП неможливо. Існує ефективний симплексний метод, що дозволяє розв’язати ЗЛП аналітично при п 2. Вихідну задачу зводять до канонічного вигляду. Можна довести, що оптимальний розв’язок завжди знаходиться серед базисних. У пошуках оптимального значення цільової функції перехід від одного базисного розв’язку до іншого зручно здійснювати за допомогою симплексних таблиць – при цьому кожній таблиці відповідає певний базисний розв’язок.

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