Рішення задач цілочисленного програмування
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Курсова робота:
Рішення задач цілочисленного програмування
Зміст
Введення
1. Постановка лінійної цілочисленної задачі
2. Теоретичні основи методів відсікання
3. Перший алгоритм Гомори
4. Другий алгоритм Гомори
5. Алгоритм Дальтона й Ллевелина
6. Алгоритм Данцига
7. Деякі висновки
Висновок
Список літератури
Введення
Серед практично важливих задач відшукання умовного екстремуму лінійної функції важливе місце займають задачі з вимогою цілочисленності всіх (частини) змінних. Вони одержали назву задач цілочисленного програмування.
Історично першою задачею цілочисленного типу є опублікована угорським математиком Е. Егервари в 1932 р. задача про призначення персоналу.
Існують різні методи рішення таких задач, і помітне місце серед них займають методи відсікання. Розглянемо в цій роботі деякі з методів відсікання, попередньо більш докладно розібравшись із постановкою лінійних цілочисленних задач.
1. Постановка лінійної цілочисленної задачі
Серед сукупності п неподільних предметів, кожний i-і (i=1,2,…,п) з яких володіє по i-й характеристиці показником і корисністю знайти такий набір, що дозволяє максимізувати ефективність використання ресурсів величини .
Математична модель цієї задачі може бути представлена в такий спосіб:
в області, певної умовами
(1)
(2)
- цілі, . (3)
знайти рішення при якому максимізується (мінімізується) значення цільової функції
(4)
Якщо , то (14) є моделлю задачі цілочисленного програмування, якщо - моделлю задачі частково цілочисленного програмування.
Часткою случаємо задачі цілочисленного програмування є задача з булевими змінними. Її математична модель у загальному виді записується в такий спосіб:
в області, певної умовами
(5)
(6)
знайти рішення , при якому максимізується (мінімізується) значення функції
(7)
До класу задач цілочисленного програмування примикають задачі, у яких умова цілочисленності всіх або частини змінних замінено вимогою дискретності. А саме, для кожної j-і змінної заздалегідь визначений набір значень (не обовязково цілих), які вона може приймати: де .
Передбачається, що сільгоспкооперативи, тобто . Математична модель загальної задачі дискретного програмування може бути представлена в такий спосіб:
в області, певної умовами
(8)
(9)
знайти рішення , при якому максимізується (мінімізується) лінійна функція
(10)
Умова (9) визначило назву цього класу; задач. Якщо , то (810) називається задачею дискретного програмування; якщо , те (810) називається задачею частково дискретного програмування.
Неважко бачити, що умова (23) задачі (14) і умова (6) задачі (57) є часткою случаємо умови (9) задачі (810). Дійсно, (23) відповідає тому случаю, коли для . Умова (9) відповідає випадку, коли .
Для задач цілочисленного типу визначене поняття припустимого й оптимального рішення.
Вектор , що задовольняє умовам (13) (відповідно (89)), називається припустимим рішенням задачі (14) (відповідно (810)). Припустиме рішення, при якому функція (4) (відповідно (10)) досягає найбільшого (найменшого) значення, називається оптимальним рішенням.
Визначивши поняття припустимого й оптимального рішення, природно порушити питання про їхнє знаходження. Здавалося б, що природний шлях рішення цілочисленної задачі складається в рішенні відповідної лінійної задачі з наступним округленням компонентів її оптимального плану до найближчих цілих чисел. Насправді такий шлях у більшості випадків не тільки веде, від оптимуму, але навіть приводить іноді до неприпустимого рішення задачі.
ПРИКЛАД. В області, певної умовами
цілі
знайти максимум функції .
Вирішимо задачу геометрично (мал. 1). Область пошуку екстремума багатокутник ODABC, але тому що лінія рівня цільової функції паралельна стороні АВ багатокутника, екстремум досягається у вершинах і , а також у будь-якій крапці відрізка АВ, і дорівнює 7.
(мал. 1)
Однак нас цікавлять лише крапки із цілочисленними координатами, отже, ні А, ні В не є припустимим рішенням задачі. Округляючи значення координат А, одержимо Але крапка А не належить області пошуку. Можна показати, що цілочисленний оптимум досягається в крапках N (3; 2) і M (2; 3) і дорівнює 5. Обидві крапки усередині області пошуку.
Побудований нами приклад показав, що для рішення задач із вимогою цілочисленності необхідно розглянути особливі методи оптимізації; і, крім того, ми бачимо, що оптимальне рішення задач цілочисленного програмування не обовязково належить границі багатогранника (багатокутника) умов, що було характерно для задач лінійного програмування.
2. Теоретичні основи методів відсікання
Запишемо загальну задачу цілочисленного програмування: в області, певної умовами
(11)
(12)
- цілі, (13)
максимізувати функцію
(14)
Назвемо для кратності задачу (1114) (ц, C) задачею. Відповідну їй задачу без вимоги цілочисленності змінних, тобто задачу (11, 12, 14) назвемо (, C) задачею. Порушимо питання: чи не можна рішення (ц, C) задачі одержати шляхом рішення якоїсь спеціальним образом побудованої задачі без вимоги цілочи?/p>