Міністерство вищої та професійної освіти РФ
Тульський державний університет
КАФЕДРА ПРИКЛАДНОЇ МАТЕМАТИКИ ТА ІНФОРМАТИКИ
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсового проекту з дисципліни
«Варіаційне числення та ОПТИМАЛЬНЕ УПРАВЛІННЯ»
на тему:
«Методи відсікання»
Тула 2003
Зміст
Введення
1. Постановка лінійної целочисленной завдання
2. Теоретичні основи методів відсікання
3. Перший алгоритм Гоморі
4. Другий алгоритм Гоморі
5. Алгоритм Дальтона і Ллевеліна
6. Алгоритм Данцига
7. Деякі висновки
Висновок
Список літератури
Додаток
Введення
Серед практично важливих задач відшукання умовного екстремуму лінійної функції важливе місце займають задачі з вимогою целочисленности всіх (частини) змінних. Вони отримали назву завдань цілочисельного (частково цілочисельного) програмування.
Історично першим завданням цілочисельного типу є опублікована угорським математиком Е. Егерварі в 1932 р. завдання щодо призначення персоналу.
Існують різні методи вирішення таких завдань, і помітне місце серед них займають методи відсікання. Розглянемо в цій роботі деякі з методів відсікання, попередньо більш детально розібравшись з постановкою лінійних цілочисельних завдань.
1. Постановка лінійної целочисленной завдання
Серед сукупності п неподільних предметів, кожен i-та (i = 1,2, ..., п) з яких має по i-й характеристиці показником і корисністю
знайти такий набір, який дозволяє максимізувати ефективність використання ресурсів величини
.
Математична модель цієї задачі може бути представлена наступним чином:
в області, визначеної умовами
(1)
(2)
- Цілі,
. (3)
знайти рішення при якому максимізується (мінімізується) значення цільової функції
(4)
Якщо , то (1-4) є моделлю задачі цілочислового програмування, якщо
- Моделлю завдання частково цілочисельного програмування.
Окремим випадком задачі цілочислового програмування є задача з булевими змінними. Її математична модель в загальному вигляді записується наступним чином:
в області, визначеної умовами
(5)
(6)
знайти рішення , При якому максимізується (мінімізується) значення функції
(7)
До класу задач цілочисельного програмування примикають завдання, в яких умова целочисленности всіх або частини змінних замінено вимогою дискретності. А саме, для кожної j-і змінної заздалегідь визначений набір значень (не обов'язково цілих), які вона може приймати:
де
.
Передбачається, що ранжовані, тобто
. Математична модель загальної задачі дискретного програмування може бути представлена наступним чином:
в області, визначеної умовами
(8)
(9)
знайти рішення , При якому максимізується (мінімізується) лінійна функція
(10)
Умова (9) визначило назву цього класу; завдань. Якщо , то (8-10) називається завданням дискретного програмування; якщо
, То (8-10) називається завданням частково дискретного програмування.
Неважко бачити, що умова (2-3) завдання (1-4) і умова (6) завдання (5-7) є окремим випадком умови (9) завдання (8-10). Дійсно, (2-3) відповідає тому випадку, коли для
. Умова (9) відповідає випадку, коли
.
Для задач цілочисельного типу визначено поняття допустимого і оптимального рішення.
Вектор , Що задовольняє умовам (1-3) (відповідно (8-9)), називається допустимим рішенням задачі (1-4) (відповідно (8-10)). Допустиме рішення, при якому функція (4) (відповідно (10)) досягає найбільшого (найменшого) значення, називається оптимальним рішенням.
Визначивши поняття допустимого і оптимального рішення, природно поставити питання про їхнє перебування. Здавалося б, що природний шлях вирішення целочисленной завдання полягає у вирішенні відповідної лінійної задачі з наступним округленням компонент її оптимального плану до найближчих цілих чисел. Насправді такий шлях у більшості випадків не тільки веде, від оптимуму, але навіть призводить іноді до неприпустимого вирішення завдання.
ПРИКЛАД. В області, визначеної умовами
- Цілі
знайти максимум функції .
Вирішимо задачу геометрично (рис. 1). Область пошуку екстремуму - багатокутник ODABC, але так як лінія рівня цільової функції паралельна стороні АВ багатокутника, екстремум досягається в вершинах і
, А також у будь-якій точці відрізка АВ, і дорівнює 7.
(Рис. 1)
Однак нас цікавлять лише точки з цілочисельними координатами, отже, ні А, ні В не є допустимим рішенням завдання. Округляючи значення координат А, отримаємо Але точка А 'не належить області пошуку. Можна показати, що цілочисельний оптимум досягається в точках N (3, 2) і M (2, 3) і дорівнює 5. Обидві точки всередині області пошуку.
Побудований нами приклад показав, що для вирішення завдань з вимогою целочисленности необхідно розглянути особливі методи оптимізації, і, крім того, ми бачимо, що оптимальне рішення задач цілочислового програмування не обов'язково належить кордоні багатогранника (багатокутника) умов, що було характерно для задач лінійного програмування.
2. Теоретичні основи методів відсікання
Запишемо загальну задачу цілочисельного програмування: в області, визначеної умовами
(1 1)
(1 2)
- Цілі,
(1 3)
максимізувати функцію
(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 ц
Теорема доведена.
Наслідком з цієї теореми є той висновок, що оптимальне рішення задачі, областю визначення якої є опукла оболонка, натягнута на область пошуку цілочисельного рішення, збігається з оптимальним рішенням вихідної целочисленной завдання.
Доведена теорема і наслідок з неї показують принципову можливість заміни рішення задачі типу (£ ц, C) деякої процедурою побудови і рішення допоміжної завдання типу (£, C), однак не дають алгоритму рішень. До того ж побудова опуклої оболонки множини £ ц реальних завдань - надзвичайно складна, а часом практично нерозв'язна задача,
У 1954 р. Дж. Данциг висловив ідею про те, що побудова опуклої оболонки целочисленной області для задачі (£ ц, C) можна здійснювати поетапно і вирішувати одержувані при цьому завдання. Однак при цьому виникли питання як будувати обмеження нового завдання і як забезпечити кінцівку процесу.
Відповідь на ці питання був вперше отриманий Р. Гоморі, який запропонував алгоритми рішення цілочисельних і. частково цілочислових задач.
Алгоритм Р. Гоморі складається з наступних процедур:
Вирішується (£, C) - завдання, відповідна вихідної (£ ц, C) - завданню.
Отримане оптимальне рішення (£, C) - завдання, якщо воно існує, перевіряється на цілочисельність. Якщо умова целочисленности виконується по всім змінним, то оптимальне рішення (£, C) - завдання є оптимальне рішення (£ ц, C) - завдання. Якщо умова целочисленности не виконується хоча б по одній координаті, то переходять до третього етапу. Якщо (£, C) - завдання, виявляється нерозв'язною, то (£ ц, C) - завдання теж рішення не має.
Будується додаткове обмеження, що володіє тим властивістю, що з його допомогою відсікається частина області, в якій міститься оптимальне рішення (£, C) - завдання і не міститься жодного допустимого рішення (£ ц, C) - завдання. Процес побудови додаткових обмежень і рішення одержуваних при цьому (£, C) - завдань триває до тих пір, поки не отримаємо цілочисельного рішення або не переконаємося в нерозв'язності завдання.
При цьому властивості, якими має володіти кожен з додаткових обмежень при переході від однієї задачі до іншої наступні:
додаткове обмеження повинно бути лінійним, щоб залишатися в області застосування апарату лінійного програмування;
додаткове обмеження повинно відсікати частина області, в якій не міститься допустимих рішень целочисленной (£ ц, C) - завдання, але є знайдене оптимальне рішення нецілочисельне (£, C) - завдання, тобто обмеження повинно мати властивість правильності, яке не дозволяє втратити оптимальне рішення вихідної (£ ц, C) - завдання.
Нехай х (£, C) - оптимальне рішення (£, C) - завдання, яке є неприпустимим рішенням для (£ ц, C) - завдання. Нерівність
(1 5)
визначає правильне відсікання, якщо задовольняє
а) умові відсікання: x (£, C) задовольняє нерівності (15)
б) умові правильності: всі допустиме рішення задачі (£ ц, C), задовольняє нерівності (15).
Методи, засновані на використанні процедури побудови правильних відсікань, отримали назву методів відсікання.
3. Перший алгоритм Гоморі
Слідуючи загальній схемі методів відсікання, вирішимо (£, C) - завдання (11, 12, 14), відповідну (£ ц, C) - задачі (11-14). Нехай x (£, C) - її оптимальне рішення. Проаналізуємо координати x (£, C) на цілочисельність. Якщо всі координати вектора x (£, C) цілі, то x (£, C) = x (£ ц, C). Якщо хоча б одна координата, нехай x i, буде нецілої, поступимо таким чином.
Позначимо через N сукупність небазисних змінних і на підставі останньої симплексного таблиці запишемо розкладання x i по небазисних змінним x i, j Î N
(1 6)
Так як x i - неціле величина, позначимо найближчим ціле число, не перевершує x i, через [x i] і визначимо дробову частина: {x i} = x i - [X i]. Очевидно, (x i)> 0.
Покажемо, що за i-й рядку симплексного таблиці (£, C) - завдання (у якій стоїть неціле координата рішення) можна визначити додаткове лінійне обмеження, що володіє властивостями правильності.
Теорема. Нехай - Допустиме рішення (£ ц, C) - завдання, тоді співвідношення
, (1 7)
,
- Ціле,
визначають правильне відсікання.
Доказ.
Запишемо вираз (1 6) у вигляді:
Використовуючи для цього виразу формулу (17), отримаємо:
або
На підставі припущень теореми про допустимість рішення
(£ ц, C) - завдання x i - ціле. Величини [x io], - Цілі за визначенням, отже, z i - теж ціле.
Отже, z i певне формулою (17), ціле. Доведемо що . Доказ будемо вести від протилежного. Нехай
.-
Це означає, що . За визначенням дробової частини
. За умовою теореми x - допустиме рішення (£ ц, C) - завдання, тому
. Отже,
Тоді повинно виконуватися:
Отже, з припущення заперечності z i, відразу ж отримуємо тобто z i - неціле. Оскільки раніше було показано, що z i, певне формулою (17), є цілим, то тим самим ми прийшли до протиріччя. Отже, припущення, що z i <0, невірне. Теорема доведена.
Слідство. Будь оптимальне рішення x (£, C) (£, C) - з Адачі, яка не є допустимим рішенням (£ ц, C) - завдання, не задовольняє умові правильного відсікання (17).
Доказ. Нехай х (£, C) - оптимальне рішення (£, C) - завдання, x i 0 - дробове.
Покажемо, що х (£, C) не задовольняє умові відсікання. Оскільки план оптимальний, все небазисних змінні x i, для j Î N дорівнюють нулю. Тому . Враховуючи це, підставимо x io у формулу (1 7):
z i (x (£, C)) = - {x i 0} +0 <0,
що суперечить умові неотрицательности z i. Слідство доведено.
Очевидно, що кількість додаткових обмежень буде наростати в міру вирішення допоміжних (£, C) - завдань, оптимальні плани яких будуть містити нецілі координати, тобто виникає проблема розмірності.
Р. Гоморі запропонував прийом, що дозволяє обмежити розміри розглянутих симплексних таблиць допоміжних завдань величиною (n +2) (k +1), де n - кількість змінних (£, C) - завдання, k - число небазисних змінних її. Цей прийом грунтується на тому, що нас цікавить додаткове обмеження лише як спосіб відсікання нецілочисельне оптимального рішення допоміжної завдання, отриманої на даному кроці, і перейти до наступного завдання.
Послідовність (£, C) - завдань пометим індексом k = 0,1, ..., відповідним номером ітерації в послідовному наближенні до вирішення вихідної (£ ц, C) - завдання, і позначимо (£ k, C). При цьому (£ 0, C) - завдання відповідає (£, C) - задачі (задачі без вимоги целочисленности).
Змінну z i, яка визначається додатковим лінійним обмеженням (7) і будується за деякою нецілочисельне координаті оптимального рішення (£ k, C) - завдання (k = 0, 1, 2, ...) позначимо x n + k + l.
Щоб розмірність послідовності (£ k, C) - завдань не зростала, викреслимо з симплекс-таблиці змінну, по якій побудовано додаткове лінійне обмеження.
Після зроблених зауважень перейдемо безпосередньо до викладу обчислювальної схеми.
1. Вирішимо (£ k, C) - завдання (спочатку k = 0) методом послідовного поліпшення плану.
Нехай в базис оптимального рішення увійшли вектори A s 1, ..., A sm. Параметри останньої симплексного таблиці позначимо через x ij:
.
Якщо, все базисні складові оптимального рішення x (£ k, C) (£ k, C) - завдання цілі, то x (£ k, C) = x (£ ц, C). Якщо деяка координата x io оптимального рішення x (£ k, C) неціле, то перейдемо до п. 2.
2. Якщо серед сукупності координат оптимального рішення x (£ k, C) є єдина неціле координата, то додаткове лінійне обмеження (17) будується по цій координаті. Якщо нецілих координат в x (£ k, C) більше однієї, то виберемо координату з найменшим номером. Хай нею виявилася x i 0. Складемо додаткове лінійне обмеження
(18)
(19)
3. Додамо умови (18, 19) до умов (£ k, C) - завдання. Отримаємо нову (£ k +1, C) - задачу. Так як оптимальне рішення x (£ k, C) (£ k, C) - завдання визначало одну з вершин багатогранника умов, то воно може бути вибрано як первинний опорного рішення для знову отриманої завдання. А це означає, що останню симплексних таблицю (£ k, C) - завдання можна взяти в якості вихідної для (£ k +1, C) - завдання, доповнивши її умовою (18).
Отже, симплексная таблиця для (£ k +1, C) - завдання виходить з останньої симплексного таблиці для (£ k, C) - завдання шляхом облямівки (i +1) - м рядком з елементами:
де - Небазисних змінні (£ k, C) завдання.
Отримаємо нове завдання, змінними якої є . Умови цього завдання дозволені щодо x sl, ..., x sm змінних і нової змінної x n + k +1, а лінійна форма виражена через небазисних змінні (£ k, C) - завдання. Так як ми займаємося максимізацією F (x) і рішення х * для (£ k, C) - завдання оптимально, то все D i> 0. Тому процес переходу до нового рішення (£ k +1, C) - завдання не може бути здійснений за методом уточнення плану. У той же час
і тому вектор А 0 симплексного таблиці не є опорним рішенням для (£ k +1, C) - завдання, так як рішенням називається вектор, всі координати якого ненегативні і задовольняють умові приналежності області £ k + l. Тому назвемо отриманий вектор
псевдорішення завдання (£ k +1, C) і перейдемо до подальшого перетворення симплекс-таблиці.
Позначимо через k номер псевдорішення (£ k, C) - завдання; тоді направляючої рядком є i + k +1- й рядок, k = 0, 1, 2, .... Тому на кожному етапі перетворення таблиці вектор A i + k + i буде виводитися з таблиці. Можна довести, що через кінцеве число кроків або буде знайдено цілочисельне рішення, або буде виявлено її нерозв'язність, а тим самим нерозв'язність (£ ц, C) - завдання.
Якщо рішення (£ k, C) - завдання завершується побудовою оптимального цілочисельного рішення x *, то m, перших його компонент визначають рішення целочисленной завдання; якщо серед координат х * є дробові, то одна з дрібних компонент (раніше визначеного правила) породжує додаткове обмеження і процес рішення повинен бути продовжений з новою окаймляющей рядком. Рядок, використовувана раніше для облямівки, викреслюється і більше для побудови розширених завдань не відновлюється.
Процедуру рішення (£ k, C) - завдання (k = 0, 1, ...) та аналізу отриманого рішення назвемо великий итерацией. Номер великої ітерації збігається з номером розв'язуваної (£ k, C) - завдання.
Результатом великої ітерації є перехід до нової (£ k +1, C) - завданню або закінчення виконання завдання.
Зробимо деякі пояснення до блок-схемі алгоритму.
Введемо: 1) клітинку i, в якій будемо запам'ятовувати номер рядка, на підставі якої будується чергове додаткове лінійне обмеження, 2) лічильник r, що відповідає номеру проведеної великий ітерації. Позначимо x * (£ r, C) оптимальне рішення (£ r, C) - завдання. Зауважимо, що позначення (£ r, C) - завдання, еквівалентну (£ r, C), введено в блок-схемі для зручності запису.
При деяких умовах вдається довести теорему про кінцівки першого алгоритму Гоморі, яку ми наведемо без докази.
Теорема. Нехай безліч оптимальних планів завдання (£ 0, C) обмежено і виконуються наступні умови:
1) з i - цілі коефіцієнти цільової функції F (x) (i = 1,2, ..., n), рядок цільової функції в симплексного таблиці враховується при виборі рядка для побудови правильного відсікання;
2) справедливо одне з двох тверджень: або цільова функція обмежена знизу на С o, або завдання (£ ц, C) має хоча б один план х '.
Тоді перший алгоритм Гоморі вимагає кінцевого числа великих ітерацій.
4. Другий алгоритм Гоморі
Другий алгоритм Р. Гоморі призначається для вирішення завдань, в яких вимога целочисленности накладено на деякі змінні (зокрема й на все). Ми його розглянемо стосовно завдань частково цілочисельного типу, розуміючи, що обчислювальна схема буде справедливою і для завдань, повністю цілочисельних.
Нехай в області, визначеної умовами:
(2 0)
(2 1)
- Цілі,
(2 2)
потрібно максимізувати функцію
(23)
Метод рішення задачі (20-23) грунтується на тій же ідеї, що і метод рішення повністю цілочисельних завдань. А саме: будується область £ k, яка при k = 0 визначається умовами (20-21); вирішується отримана при цьому завдання лінійного програмування (20-21, 23). Якщо завдання (20-21, 23) виявляється можливо розв'язати, то отримане оптимальне рішення її аналізується на допустимість для вихідної задачі цілочислового програмування (20-23). Якщо знайдене рішення виявляється цілочисельним, то одночасно воно буде оптимальним для (20-23). Якщо оптимальне рішення (£ k, C) - завдання виявляється неприпустимим для вихідної завдання (20-23), то здійснюється побудова правильного відсікання і перехід до вирішення нового завдання,
Другий алгоритм Р. Гоморі формулюється у вигляді такої теореми:
Теорема. Нехай х (£ k, C) - оптимальне рішення (£ k, C) - завдання, - Елементи відповідної йому симплексного таблиці. Якщо
- неціле
, То
(2 4)
- Ціле, (2 5)
де
(2 6)
визначає правильне відсікання. Блок-схема другого алгоритму Р. Гоморі аналогічна блок-схемою першого алгоритму Р. Гоморі і відрізняється лише правилом побудови коефіцієнтів правильного відсікання.
Правило побудови правильного відсікання
Нехай x (£ k, C) не задовольняє умові целочисленности, - Елементи симплексного таблиці, відповідної отриманому оптимальному рішенню (£ k, C) - завдання. Виберемо i 0 = min {i | i Î (1, 2, ..., n), x i 0 k - неціле} і будуємо правильне відсікання по формулам (24 - 26).
Умови кінцівки другий алгоритм Гоморі:
1) Цільова функція F (x) задовольняє умові целочисленности. Це враховується при виборі рядка k для побудови правильного відсікання.
2) Виконано принаймні одне з двох умов:
2 ') цільова функція обмежена знизу на багатогранному множині £ = £ 0;
2 ») задача (£ 0 ц, C) має принаймні один план.
За допомогою другого алгоритму Гоморі можна (у разі n 1 = n) вирішувати і повністю целочисленную завдання лінійного програмування. Однак у цьому випадку немає підстав для порівняння ефективності другого і першого алгоритмів Гоморі.
5. Алгоритм Дальтона і Ллевеліна
Другий алгоритм Гоморі має справу з частково цілочисельними завданнями лінійного програмування. Дальтон і Ллевелін розглядають 0 олее широкий клас завдань - частково дискретні задачі лінійного програмування і стосовно до них модифікують другий алгоритм Гоморі.
Нагадаємо, що рішенням задачі дискретного програмування будемо називати вектор, координати якого належать £ ц області види:
(2 7)
(2 8)
(2 9)
і максимізує значення функції
(3 0)
Будемо припускати, що проранжовано, тобто
і є наперед заданими числами.
Теорема. Нехай x (£ k, C) - оптимальне рішення задачі (27-28, 30), - Елементи симплексного таблиці, відповідної йому.
Якщо x (£ k, C) є неприпустимим рішенням задачі (27-3 0) і , Тоді, використовуючи i-й рядок симплексного таблиці, можна побудувати відсікання, що володіє властивістю правильності за формулами:
(3 1)
(32)
де
(3 3)
Доказ. Перевіримо спочатку умова відсікання. Нехай в оптимальному рішенні x (£ k, C) координата не задовольняє умові (29). Покажемо, що в цьому випадку вектор х (£ k, C) не задовольняє умовам (31, 32). Оскільки N k - безліч індексів небазисних змінних x i, які в оптимальному рішенні дорівнюють нулю, то рівність (31) набуває вигляду
і буде негативним згідно з умовою теореми. Отже,
, Тобто умова відсікання не виконується.
Перевіримо умову правильності. Для цього покажемо, що будь-допустиме рішення задачі (27-30) задовольняє умовам (31, 32).
Запишемо розкладання для координати допустимого рішення задачі (27-30) за небазисних змінним
(3 4)
і розглянемо два випадки: a) ; Б)
. Введемо позначення:
і представимо (3 4) у вигляді
де
Очевидно, так як
.
Розглянемо випадок а): , Або що все одно,
.
Звідси Але
тому
(35)
Домножити обидві частини (35) на неотрицательную величину і складемо з неотрицательной величиною
:
(36)
Розглянемо випадок б): або, що все одно,
Так як по визначенню
, То
Помножимо обидві частини нерівності
на неотрицательную величину
і на -1, одержимо
. Додаючи до отриманого виразу нерівність
, Одержимо
(37)
Таким чином, в а) і в б) випадках прийшли до одного і того ж нерівності (36) і (37). Користуючись раніше введеними позначеннями, їх можна записати
(38)
Формула (38) визначає правильні відсікання. Порівнюючи її з виразом (31-32), приходимо до висновку, що коефіцієнти визначаються наступним чином:
Теорема доведена.
Алгоритм Дальтона - Ллевеліна може бути описаний таким чином.
1. Вирішується (£ k, C) - завдання (27-30) (спочатку k = 0). Нехай x (£ k, C), k = 0, 1, 2, ... оптимальне рішення (£ k, C) - завдання, - Симплексная таблиця.
2. Перевіряється умова допустимості по всіх координатах оптимального вектора рішення х (£ k, C) (£ k, C) - завдання. Якщо умова допустимості виконується, то отримане рішення є оптимальним рішенням вихідної завдання (27-30). Якщо умова допустимості не виконується хоча б по одній координаті, здійснюється перехід до 3.
3. Нехай не задовольняє умові допустимості. Тоді вибирається
i 0 = min {i | 1 <i <n 1, х j 0 k - не задовольняє (29)}.
4. Для обраного номеру i = i 0 будується правильне відсікання, тобто вводиться додаткова змінна
де визначається формулою (3 3),
5. Додаємо лінійне обмеження, що визначає правильне відсікання, до умов (£ k, C) - завдання і отримуємо нову (£ k +1, C) - задачу. Вважаючи k = k + 1, переходимо до п. 1.
Наведемо без доведення теорему про кінцівки алгоритму.
Теорема. Якщо: коефіцієнти цільової функції дискретні; F (x) обмежена знизу на багатогранному множині £; завдання (£, C) має принаймні одне рішення; вибір рядка для побудови правильного відсікання проводиться за правилом мінімального номери і (£ k, C ) - завдання вирішуються методом послідовного уточнення оцінок, то алгоритм Дальтона і Ллевеліна сходиться.
6. Алгоритм Данцига
Спосіб побудови правильних відтинають площин, запропонований Данцигом значно простіше, ніж усі зазначені вище способи. Але, як показали Гоморі і Гофман, кінцівку алгоритму Данцига гарантується лише для дуже вузького класу задач. На прикладі алгоритму Данцига видно, наскільки тонким є питання про побудову правильних відсікань і наскільки обережно варто підходити до різних спрощеним алгоритмам.
Розглядається повністю целочисленная завдання лінійного програмування:
Максимізувати
(3 9)
за умов
(4 0)
(4 1)
- Цілі,
(4 2)
Ранг матриці вважаємо рівним m.
Теорема. Нехай x (£ r, C) = x r є оптимальним опорним планом задачі (£ r, C) і x r не задовольняє умові целочисленности, N r - безліч індексів, нумерують небазисних змінні, відповідні x r.
Тоді нерівність
(4 3)
є правильним відсіканням.
Правильне відсікання, що відтинають нецілочисельне оптимум x (£ r, C) завдання (£ r, C), можна записати наступним чином:
- Ціле.
Зауважимо, що кожна з нововведених змінних однозначно визначається завданням змінних
, Так що
.
Позначимо через впорядковані у порядку зростання компоненти
плану x задачі (39) - (41), так що
(4 4)
Покладемо
(45)
Лемма. Якщо для деякого плану x завдання (39) - (41)
, (46)
то
(4 7)
Доказ проведемо по індукції. Спочатку доведемо, що
(7 квітня ¢)
За визначенням
(4 8)
Так як ранг матриці дорівнює m, то
де - Число елементів множини
. З визначення чисел
отримуємо
(4 9)
(5 0)
З (4 8), (4 9), (5 0) і (4 6) маємо
Лема доведена при р = 1.
Тепер припустимо, що лема вірна при , І доведемо її при
:
Лемма доведена.
Користуючись лемою, доведемо дві теореми.
Теорема 1. Якщо кожен оптимальний план задачі (39) - (42) містить не менше (m +2) позитивних компонент, то алгоритм Данцига не буде кінцевим.
Доказ. Припустимо, що на s-й ітерації алгоритму Данцига вийде шуканий оптимальний план . Розглянемо числа
(5 1)
Всі вони цілі і серед них має бути (n - m) нулів - це небазисних змінні . Крім того, за умовою серед чисел
, Має бути принаймні (m +2) позитивних числа, тобто не більше ніж (n - m -2) нулів.
За визначенням чисел звідси випливає, що
а так як має бути цілим, то
(52)
Але за визначенням чисел
(53)
З (5 2) отримуємо
(5 4)
і по лемі
(55)
З (52), (53) та (55) випливає, що серед чисел (51) принаймні [1 + (m +1) + s] = [m +2 + s] позитивних, а отже, не більше ніж [n + s - (m +2 + s)] = (n - m -2) нулів. Але вище було зазначено, що серед чисел (51) повинно бути (n - m) нулів. Вийшло протиріччя. Теорема 1 доведена.
Слідство (з теореми 1). Для того щоб алгоритм Данцига був кінцевим, необхідно, щоб шуканий оптимальний план лежав на ребрі багатогранного безлічі (40) - (41) (передбачається, що задача (39) - (41) невироджених).
Хоча ця умова і є досить жорстким, йому задовольняють, наприклад, всі (невироджені) завдання наступного вигляду.
Максимізувати
(5 6)
за умов
(5 7)
(5 8)
(5 9)
- Ціле,
(6 0)
А це важливий клас задач.
Однак наведене в слідстві необхідна умова кінцівки алгоритму Данцига не є достатнім. Дійсно, має місце наступна
Теорема 2. Якщо для деякого оптимального плану x 'завдання (39) - (42) і деякого плану x »завдання (39) - (41) мають місце нерівності
(6 1)
і
(6 2)
то алгоритм Данцига не буде кінцевим.
Доказ. Припустимо, що алгоритм Данцига кінцевий. Тоді з (61) випливає, що точка x » була відсічена на деякій (скажімо, р-й) ітерації, так що
(63)
Але з (62) і леми отримаємо
(64)
Порівнюючи (6 3) і (6 4), отримуємо протиріччя. Теорема 2 доведена.
Отже, спрощений алгоритм Данцига буде кінцевим лише в дуже рідкісних випадках.
7. Деякі висновки
Спробуємо охарактеризувати поведінку алгоритмів методу відсікання при вирішенні задач цілочисельного лінійного програмування. В якості міри тривалості обчислень можуть розглядатися кількість симплексних ітерацій I і кількість правильних відсікань (додаткових лінійних обмежень) D.
Для першого алгоритму Гоморі та різних його узагальнень I і D також тісно пов'язані між собою (як показує експеримент, в більшості випадків рішення окремого завдання (£, С) вимагає порівняно невеликої кількості симплексних ітерацій).
Переходимо до викладу окремих властивостей алгоритмів методу відсікання.
Числа I і D мають (в середньому) тенденцію до зростання зі збільшенням числа змінних і обмежень, зростанням порядку коефіцієнтів завдання і збільшенням заповнювання матриці .
Це явище здається природним, але досвід показує, що в дискретному програмуванні «природне» і «правдоподібне» не завжди виявляється правильним. Точніше кажучи, досвід, накопичений на завданнях лінійного програмування, не можна механічно переносити на задачі цілочислового лінійного програмування.
Перш за все, звертає на себе увагу «нерегулярність», «непередбачуваність» поведінки алгоритмів методу відсікання. Для ряду завдань оптимальне рішення не вдавалося отримати після багатьох тисяч ітерацій, в той час як інші завдання вирішувалися за кілька десятків ітерацій.
Не вдається встановити безпосередній зв'язок між розмірами завдань (тобто числом обмежень m і змінних n) і числом ітерацій: невдачі були зафіксовані навіть для невеликих завдань (m ≤ 1 0, n ≤ 10), а успіхи - для задач досить великого розміру (m = 215, n = 2600). Можливо, втім, що спроба встановлення подібної зв'язку - це неправомірне перенесення результатів лінійного програмування в область цілочисельного лінійного програмування.
Бути може, більш природною характеристикою завдання (£, С) є не число m лінійних обмежень, які задають багатогранне безліч £, а число m ц - лінійних обмежень, які задають багатогранне безліч V (£) *). Між тим легко привести приклади, коли при невеликих m і n число m ц буде досить велика.
«Нерегулярність» позначається і в наступному факті, помічена поруч дослідників: іноді вдається істотно скоротити число ітерацій за рахунок перенумерації змінних.
Нарешті, має місце немонотонність наближення псевдоплана Х r до оптимального плану X * - з ростом r відстань ρ (Х r, X *) не обов'язково зменшується і лише на останній ітерації обов'язково стає рівним нулю.
Великий вплив на кількість ітерацій надає правило вибору породжує рядка. Тут також має місце «нерегулярність» - у той час коли одне правило призводить до успіху за десятки ітерацій, інше не дає рішення після тисяч ітерацій.
При вирішенні завдань цілочисельного лінійного програмування за методом відсікання є як успіхи, так і невдачі.
До найбільш успішним робіт слід віднести:
1) Завдання покриття, у тому числі завдання, пов'язані з мінімізацією булевих функцій.
2) Застосування до задач оптимального кодування.
3) Застосування до задачі оптимального добування інформації з паралельних систем пам'яті.
Найбільш характерними завданнями, для яких мала місце невдача, є:
2) Завдання теорії розкладів.
3) Деякі з узагальнених задач покриття.
На даний момент відсутній вичерпне пояснення удач або невдач різних обчислювальних експериментів. Все ж для задачі комівояжера і задачі теорії розкладів є правдоподібним таке міркування.
Формулювання цих завдань мовою цілочисельного лінійного програмування є «неприродної». Для завдання порівняно невеликий у «природною» формулюванні, в моделі цілочисельного лінійного програмування фігурує велика кількість обмежень і змінних. Можливо, що для цих завдань більш перспективними є комбінаторні методи (наприклад, метод гілок і меж для задачі комівояжера). Втім, останнє твердження є спірним, тому що комбінаторні методи дуже чутливі до специфіки завдань, введенню додаткових умов і т.п.
Мабуть, успіх у вирішенні завдань покриття пов'язаний з тим, що вдалося напасти на клас завдань, практично важливих і в той же час успішно вирішуються. Було б дуже цікаво точно охарактеризувати клас задач покриття, добре розв'язуваних за методом відсікання. Це тим більше цікаво, що побудовані приклади узагальнених задач покриття, для яких виникають значні обчислювальні труднощі.
І взагалі, виділення окремих класів ефективно розв'язуваних завдань - важлива і цікава проблема.
Висновок
Підіб'ємо деякі підсумки. Метод відсікання знаходиться в стадії розвитку і вдосконалення. При реалізації цього методу виникають труднощі, що носять, мабуть, не тільки технічний, але і принциповий характер. На даний момент можна говорити про рішення за допомогою методу відсікання завдань не більш ніж середнього розміру (сотні змінних і десятки обмежень).
Найбільш перспективними для подальших досліджень за методом відсікання подаються такі напрямки:
1) Дослідження будови множин £ ц і V (£ ц).
2) Дослідження властивостей правильних відсікань.
3) Вказівка нових способів побудови правильних відсікань.
4) Розвиток нових класів алгоритмів методу відсікання (наприклад, прямих алгоритмів).
5) Виділення окремих класів ефективно розв'язуваних завдань.
Список літератури
1. Корбут А.А., Фінкельштейн Ю.Ю. Дискретне програмування, М.: Наука, - 1969.
2. Лященко І.М. Лінійне і нелінійне програмування, М.: Наука, - 1985.
3. Сановича К.М. Дослідження операцій, М.: Наука, - 1989.
Додаток
ПРОГРАМА, реалізує перший АЛГОРИТМ Гоморі
# Include <ctype.h>
# Include <string.h>
# Include <conio.h>
# Include <stdio.h>
# Include <math.h>
# Include <stdlib.h>
class simplex {int n; / / число змінних +1
int m; / / число обмежень
int * basis;
int * mi;
float * mc;
int flag;
public: simplex (int m1, FILE * fp, int f);
~ Simplex ()
{If (mi) free (mi);
if (mc) free (mc);
if (basis) free (basis);
}
void printsimtable (int g);
void iterac ();
void resultat ();
};
simplex: simplex (int m1, FILE * fp, int f)
{FILE * fp1;
int fl, i;
if ((fp1 = fopen («hell1», «w +»))== NULL) {printf (« Помилка виділення пам'яті! ");
exit (1);
};
m = m1;
n = 0;
basis = NULL;
flag = f;
fl = 1;
do {fread (& c, sizeof (struct koef), 1, fp);
if (! feof (fp))
{Do {fread (& i, sizeof (int), 1, fp1);
if (! feof (fp1) & & i == c.ind)
{Fl = 0;
break;
}
} While (! Feof (fp1));
if (fl) {fwrite (& c.ind, sizeof (int), 1, fp1);
n + +;
fflush (fp1);
}
else fl = 1;
rewind (fp1);
}
} While (! Feof (fp));
rewind (fp);
if (m> n -1) {printf («Число обмежень більше або дорівнює числу змінних»);
getch ();
exit (1);
}
mi = (int *) malloc (sizeof (int) * n);
mc = (float *) malloc (sizeof (float) * n * (m +1));
if (! mc | |! mi) {printf («Помилка виділення пам'яті!");
getch ();
exit (1);
}
fread (mi, sizeof (int), n, fp1);
qsort (mi, n, sizeof (int), sort);
fclose (fp1);
remove («hell1»);
for (fl = 0; fl <m +1; fl + +)
for (i = 0; i <n; i + +)
* (Mc + fl * n + i) = 0;
fl = m;
do {fread (& c, sizeof (struct koef), 1, fp);
if (! feof (fp))
{If (c.ind)
{For (i = 1; i <n; i + +)
if (c.ind ==* (mi + i))
{* (Mc + fl * n + i) =* (mc + fl * n + i) + c.coef;
break;
}
}
else {* (mc + fl * n) = c.coef;
if (fl == m) fl = 0;
else fl + +;
}
}
} While (! Feof (fp));
}
void simplex: iterac ()
{Int i, j, fl, fl1, k, l;
float s, min;
for (i = 1; i <n; i + +)
{If (* (mc + m * n + i)! = 0)
{Fl = 1;
for (j = 0; j <m; j + +)
if (* (mc + j * n + i)! = 0) {fl = 0;
break;
}
if (fl) {printf («Не все перменние цільової функції входять в обмеження»);
getch ();
exit (1);
}
}
}
basis = (int *) malloc (sizeof (int) * m);
if (! basis) {printf («Помилка виділення пам'яті»);
getch ();
exit (1);
}
for (i = 0; i <m; i + +)
* (Basis + i) = 0;
i = 0;
do
{Fl = 1;
fl1 = 0;
for (j = 1; j <n; j + +)
if (* (mc + i * n + j)> 0) {fl = 0;
break;
}
if (fl) {printf («Змінні повинні бути позитивні»);
getch ();
exit (1);
}
s =* (mc + i * n + j);
for (l = 0; l <n; l + +)
* (Mc + i * n + l) =* (mc + i * n + l) / s;
for (l = 0; l <= m; l + +)
if (l! = i) {s =* (mc + l * n + j);
for (k = 0; k <n; k + +)
* (Mc + n * l + k) =* (mc + l * n + k) - s * (* (mc + i * n + k));
}
for (l = 0; l <m; l + +)
{S = 0;
for (k = 1; k <n; k + +)
s = s + fabs (* (mc + l * n + k));
if (s == 0) {if (* (mc + l * n) == 0) printf («Рівняння лінійно залежні»);
else printf («Система обмежень несовместна»);
getch ();
exit (1);
}
}
* (Basis + i) = j;
for (l = 0; l <m; l + +)
if (* (mc + l * n) <0)
for (k = 0; k <n; k + +)
* (Mc + l * n + k) = - (* (mc + l * n + k));
for (l = 0; l <m; l + +)
if ((* (basis + l) == 0 )||(*( mc + l * n + (* (basis + l))) <0)) {i = l; fl1 = 1; break;}
} While (fl1);
printsimtable (0);
do {min = 100000;
fl = 0;
for (l = 1; l <n; l + +)
{If (* (mc + m * n + l)> 0) {fl = 1;
fl1 = 1;
for (k = 0; k <m; k + +)
if (* (mc + k * n + l)> 0)
{Fl1 = 0;
s =* (mc + k * n )/(*( mc + k * n + l));
if (s <min) {min = s;
i = k;
j = l;
}
}
if (fl1) {printf («Рішення ні »);
getch ();
exit (1);
}
break;
}
}
if (fl) {s =* (mc + i * n + j);
for (l = 0; l <n; l + +)
* (Mc + i * n + l) =* (mc + i * n + l) / s;
for (l = 0; l <= m; l + +)
if (l! = i) {s =* (mc + l * n + j);
for (k = 0; k <n; k + +)
* (Mc + l * n + k) =* (mc + l * n + k) - s * (* (mc + i * n + k));
}
printsimtable (0);
* (Basis + i) = j;
}
} While (fl);
}
void simplex: resultat ()
{Int i, j, fl;
if (flag ==- 1) printf ("Мінімальне значення функції мети одно% 8.2 f \ n», * (mc + m * n));
else printf («Максимальне значення функції мети одно% 8.2 f \ n», - (* (mc + m * n)));
printf («Оптимальний план:»);
for (i = 1; i <n; i + +)
{Fl = 0;
for (j = 0; j <m; j + +)
if (* (mi + i )==*( basis + j)) {fl = 1;
break;
}
if (fl) printf ("x% 02d =%-5.2f \ n», * (mi + i), * (mc + j * n));
else printf («x% 02d = 0 \ n», * (mi + i));
printf («»);
}
}
void simplex: printsimtable (int g)
{Int i, j, k, v = g, raz;
clrscr ();
raz = n-1-6 * (v +1);
if ((raz <= 0) & & (abs (raz) <6)) raz = 6 + raz;
else if (raz> 0) raz = 6;
else return;
for (j = 0; j <3; j + +)
{If (j! = 1) {printf («* * *»);
for (i = 0; i <raz; i + +)
printf (»*»);
if (raz <6) printf ("\ n");
}
else {if (* (mc + m * n)> = 0) printf («* *% 8.2f *»,*( mc + m * n));
else printf («* * -%-7.2f *», - (* (mc + m * n)));
for (i = 1; i <= raz; i + +)
if (* (mc + n * k +6 * v + i)> = 0) printf ("% 8.2f *»,*( mc + n * k +6 * v + i));
else printf («-%- 7.2f * », - (* (mc + n * k +6 * v + i)));
if (raz <6) printf ("\ n");
}
}
for (i = 0; i <20 + raz * 10; i + +)
printf («*»);
getch ();
rewind (fp);
simplex ob (no, fp, f);
gomori ();
ob.iterac ();
ob.resultat ();
}