Главная | Обратная связь | Поможем написать вашу работу!

Математичне програмування

Навчальний посібник

Рецензенти: Нікішов В.І. – член-кор. НАНУ, доктор фіз.-мат наук, професор, заступник директора Інституту гідромеханіки НАНУ

Кіфоренко Б.М. – доктор фіз.-мат наук, професор кафедри механіки суцільних середовищ Київського національного університету ім. Тараса Шевченка

Харитонов О.М. – кандидат фіз.-мат наук, доцент кафедри механіки суцільних середовищ Київського національного університету ім. Тараса Шевченка

Шевченко К.Л. – кандидат технічних наук, доцент, завідувач кафедри автоматизації та комп’ютерних систем Київського національного університету технологій і дизайну

Бех О.В., Городня Т.А., Щербак А.Ф. Математичне програмування:

Навчальний посібник. – Кривий Ріг, КЕІ КНЕУ, 2006 – 240с.

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

Крім теоретичного матеріалу в навчальному посібнику розглядається практична сторона вивчення математичного програмування. У кінці кожного розділу наводяться висновки та контрольні запитання, які доцільно використовувати для перевірки рівня засвоєння теоретичного матеріалу та практичного використання алгоритмів розв’язування задач оптимізації.

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

ПЕРЕДМОВА

Навчальний посібник адресується студентам економічних спеціальностей і усім фахівцям, які цікавляться використанням методів оптимізації в економічних процесах.

Автори прагнули до того, щоб матеріал посібника був доступним широкому колу читачів. Тому математична підготовка читачів не потребує спеціальних знань, які виходять за межі середньої школи та елементарного знайомства з елементами лінійної алгебри, диференційованого числення та теорії ймовірності. З цих позицій викладання матеріалу ведеться на достатньо простому рівні і може використовуватися не тільки для первісного знайомства з математичними методами, а й для повторення матеріалу по декотрим забутим питанням будування та використання математичних моделей в економіці.

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

Щиру подяку автори висловлюють Керді Г.Д., яка виконала коректуру та комп’ютерний набір остаточного варіанта посібника до видання.

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

Автори будуть щиро вдячні за слушні і корисні зауваження щодо матеріалу даного навчального посібника.

Автори.

ВСТУП

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

Вибір такого варіанта – надзвичайно складний процес, пов’язаний зі значними розрахунковими операціями. Проте, незважаючи на труднощі з точки зору розрахунків, перехід до користування оптимальними методами планування, цілком очевидно, підвищує темп росту економічного потенціалу нашої країни та якість керування економічними явищами. Розрахунки свідчать про те, що в разі застосування неоптимальних розв’язків втрачається значна частка коштів і матеріальних ресурсів, які йдуть на розвиток народного господарства. Статистичні дані свідчать, що зменшення запасів сировини на 1% дає змогу додатково залучити до обігу в народному господарстві матеріальних ресурсів на суму понад 2 млрд. грн. Мінімізація запасів, розмір яких цілком забезпечить процес виробництва, є головною задачею, яку ефективно можна розв’язати тільки комплексно із застосуванням ЕОМ та економіко-математичних методів.

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

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

знайти значення змінних

при яких цільова функція

набуває оптимального значення (min, max) за умови виконання обмежень

при усіх або їх цілочисловості.

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

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

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

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

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

Коротко охарактеризуємо основні класи задач математичного програмування.

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

Основними методами розв’язування задач лінійного програмування є симплексний метод та його модифікації.

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

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

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

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

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

РОЗДІЛ 1