МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»

Кафедра автоматизованих систем управління

Лабораторна робота №6

з дисципліни “Математичні методи дослідження операцій”

на тему

«Метод Гоморі»

Виконав:

студент групи КН-22

Муха Богдан

Прийняв:

старший викладач

Балич Б. І.

Львів – 2012

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

План

1. Короткі теоретичні відомості.

2. Постановка задачі

   1. Графічне вирішення задачі.

   2. Метод Гоморі розв’язаний за допомогою симлекс таблиць.

3. Розв’язання за допомогою пакету програм MS Exel

4. Розв’язання за допомогою власної програми.

Хід роботи

1. Короткі теоретичні відомості

Під завданням цілочисельного програмування (ЦП) розуміється завдання, в якому всі або деякі змінні повинні приймати цілі значення. У тому випадку,

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

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

Цілочисельне програмування виникло в 50-60-і роки нашого століття з потреб практики - головним чином в роботах американських математиків Дж.Данціга і Р.Гоморі. Спочатку цілочисельне програмування розвивалося незалежно від геометрії чисел на основі теорії і методів математичної оптимізації, перш за все лінійного програмування. Однак, в останні час

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

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

Цілочисловим (іноді його називають також дискретним) програмуванням

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

завдання, в яких на шукані змінні накладається умова

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

обсягу (наприклад, товарних запасів); в іншому випадку він може внести

значні спотворення в дійсно оптимальне рішення. Тому розроблені спеціальні методи вирішення цілочислових задач.

Рекомендації по формулюванню і рішенням ЦП:

Кількість цілочисельних змінних зменшувати настільки , наскільки можливо. Наприклад, цілочисельні змінні, значення яких повинно бути не менше 20, можна розглядати як безперервні.

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

Якщо немає гострої необхідності в знаходженні точного оптимального цілочисельного рішення, що відрізняється від безперервного рішення, наприклад, 3%. Тоді реалізацію методу гілок і меж для задачі максимізації можна закінчувати, якщо відношення різниці між верхньою і нижньою границями до верхньої межі менше 0,03.

Метод гілок і меж можна застосовувати для вирішення задач нелінійного

програмування.