Курсовая работа: Рішення задач цілочисленного програмування

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

Вектор , що задовольняє умовам (1–3) (відповідно (8–9)), називається припустимим рішенням задачі (1–4) (відповідно (8–10)). Припустиме рішення, при якому функція (4) (відповідно (10)) досягає найбільшого (найменшого) значення, називається оптимальним рішенням.

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

ПРИКЛАД. В області, певної умовами

– цілі

знайти максимум функції .

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

(мал. 1)

Однак нас цікавлять лише крапки із цілочисленними координатами, отже, ні А, ні Вне є припустимим рішенням задачі. Округляючи значення координат А, одержимо Але крапка А' не належить області пошуку. Можна показати, що цілочисленний оптимум досягається в крапках N (3; 2) і M (2; 3) і дорівнює 5. Обидві крапки усередині області пошуку.

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

2. Теоретичні основи методів відсікання

Запишемо загальну задачу цілочисленного програмування: в області, певної умовами

(11)

(12)

- цілі, (13)

максимізувати функцію

(14)

Назвемо для кратності задачу (11–14) (£^ц , C) – задачею. Відповідну їй задачу без вимоги цілочисленності змінних, тобто задачу (11, 12, 14) назвемо (£, C) – задачею. Порушимо питання: чи не можна рішення (£^ц , C) – задачі одержати шляхом рішення якоїсь спеціальним образом побудованої задачі без вимоги цілочисленності змінних і такий, що оптимальні рішення вихідної (£^ц , C) – задачі й задачі без вимог цілочисленності змінних будуть збігатися. Іншими словами: чи не можна добре вивчений апарат рішення задач лінійного програмування пристосувати до рішення цілочисленних задач. Принципова відповідь на це питання дає наступна теорема.

Теорема. Нехай £ – багатогранник, £^ц – множина його цілих крапок, R – опукла, лінійна оболонка множини £^ц , тоді:

1) R=R^ц – цілочисленний багатогранник;

2) R^ц = £^ц ;

3) R* – множина опорних рішень задачі (£^ц , C) утримується в багатограннику R^ц .

Доказ. Доведемо, що R – цілочисленний багатогранник. За умовою теореми £ – багатогранник, тому множина його цілих крапок (воно позначено через £^ц) звичайно. Оскільки R - опукла лінійна оболонка цієї кінцевої множини крапок, R - теж багатогранник.

По самому визначенню опуклої лінійної оболонки, вона містить всі опорні плани множини, на яке вона натягнута, тобто багатогранник R містить всі целочисленные крапки £^ц. Тому R – цілочисленний багатогранник. Позначимо його через R^ц . Перша частина теореми доведена.

Доведемо, що R^ц збігається з £^ц. Тому що R – опукла оболонка крапок множини £^ц , те £^ц ÍR^ц .

Покажемо, що справедливо також і протилежна нерівність-включення, т.е. R^ц Í£^ц. Для цього виберемо деякий довільний елемент х°ÎR^ц . Оскільки R^ц містить всі опорні рішення задачі (£^ц , C), те х° задовольняє умовам задачі (£^ц , C), тобто х°Î£^ц. Але оскільки довільний елемент із R^ц належить £^ц , те очевидно, що справедливо R^ц Í£^ц. Зіставляючи протилежні включення R^ц Í£^ц і £^ц ÍR^ц доходимо висновку: що £^ц =R^ц . Друга частина теореми також доведена.

Доказ 3-го пункти теореми є зовсім очевидним. Тому що R^* – множина опорних рішень задачі (£^ц , C), те R^* Í£^ц але £^ц =R^ц , тому R^* ÍR^ц