Рішення задач цілочисленного програмування
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
оптимальному рішенні дорівнюють нулю, то рівність (31) приймає вид і буде негативним відповідно до умови теореми. Отже, , тобто умова відсікання не виконується.
Перевіримо умову правильності. Для цього покажемо, що будь-яке припустиме рішення задачі (27-30) задовольняє умовам (31, 32).
Запишемо розкладання для координати припустимого рішення задачі (27-30) по небазисним змінним
(34)
і розглянемо два випадки: a) ; б) . Уведемо позначення:
і представимо (34) у вигляді
де
Очевидно, тому що .
Розглянемо випадок а): , або що однаково, .
Звідси Але тому
(35)
Помножимо обидві частини (35) на ненегативну величину й складемо з ненегативною величиною :
(36)
Розглянемо випадок б): або, що однаково, Тому що по визначенню , то Помножимо обидві частини нерівності на ненегативну величину й на -1, одержимо . Додаючи до отриманого вираження нерівність , одержимо
(37)
Таким чином, в а) і в б) випадках прийшли до тому самому нерівності (36) і (37). Користуючись раніше уведеними позначеннями, їх можна записати
(38)
Формула (38) визначає правильні відсікання. Порівнюючи її з вираженням (3132), доходимо висновку, що коефіцієнти визначаються в такий спосіб:
Теорема доведена.
Алгоритм Дальтона - Ллевелина може бути описаний у такий спосіб.
1. Вирішується (k, C) задача (2730) (спочатку k = 0). Нехай x(k, C), k = 0, 1, 2,…оптимальне рішення (k, C) задачі, симплексна таблиця.
2. Перевіряється умова допустимості по всіх координатах оптимального вектора рішення х(k, C) (k, C) задачі. Якщо умова допустимості виконується, то отримане рішення є оптимальним рішенням вихідної задачі (27-30). Якщо умова допустимості не виконується хоча б по одній координаті, здійснюється перехід до 3.
3. Нехай не задовольняє умові допустимості. Тоді вибирається
i0 = min {i| 1<i<n1, хj0k не задовольняє (29)}.
4. Для обраного номера i=i0 будується правильне відсікання, тобто вводиться додаткова змінна
де визначається формулою (33),
5. Додаємо лінійне обмеження, що визначає правильне відсікання, до умов (k, C) задачі й одержуємо нову (k+1, C) задачу. Думаючи k = k + 1, переходимо до п. 1.
Приведемо без доказу теорему про кінцівку алгоритму.
Теорема. Якщо: коефіцієнти цільової функції дискретні; F(x) обмежена знизу на багатогранній множині ; задача (, C) має принаймні одне рішення; вибір рядка для побудови правильного відсікання виробляється за правилом мінімального номера й (k, C) задачі вирішуються методом послідовного уточнення оцінок, то алгоритм Дальтона й Ллевелина сходиться.
6. Алгоритм Данцига
Спосіб побудови правильних площин, що відтинають, запропонованим Данцигом значно простіше, ніж всі викладені вище способи. Але, як показали Гомори й Гофман, кінцівка алгоритму Данцига гарантується лише для дуже вузького класу задач. На прикладі алгоритму Данцига видно, наскільки тонким є питання про побудову правильних відсікань і як обережно варто підходити до різним спрощеним алгоритмам.
Розглядається повністю цілочисленна задача лінійного програмування:
Максимізувати
(39)
при умовах
(40)
(41)
цілі, (42)
Ранг матриці вважаємо рівним m.
Теорема. Нехай x(r, C)=xr є оптимальним опорним планом задачі (r, C) і xr не задовольняє умові цілочисленності, Nr множина індексів, що нумерують небазисні змінні, відповідні xr.
Тоді нерівність
(43)
є правильним відсіканням.
Правильне відсікання, що відтинає нецілочисленний оптимум x(r, C) задачі (r, C), можна записати в такий спосіб:
ціле.
Помітимо, що кожна із знову змінних однозначно визначається завданням змінних , так що .
Позначимо через упорядковані в порядку зростання компоненти плану x задачі (39) (41), так що
(44)
Покладемо
(45)
Лема. Якщо для деякого плану x задачі (39) - (41)
, (46)
те
(47)
Доказ проведемо по індукції. Спочатку доведемо, що
(47)
По визначенню
(48)
Тому що ранг матриці дорівнює m, те
де число елементів множини . З визначення чисел одержуємо
(49)
(50)
З (48), (49), (50) і (46) маємо
Лема доведена при р=1.
Тепер допустимо, що лема вірна при , і доведемо неї при :
Лема доведена.
Користуючись лемою, доведемо дві теореми.
Теорема 1. Якщо кожний оптимальний план задачі (39) (42) містить не менш (m+2) позитивних компонентів, то алгоритм Данцига не буде кінцевим.
Доказ. Допустимо, що на s-й ітерації алгоритму Данцига вийде шуканий оптимальний план . Розглянемо числа
(51)
Всі вони цілі й серед них повинне бути (n-m) нулів це небазисні змінні . Крім того, за умовою серед чисел , повинне бути принаймні (m+2) позитивні числа, тобто не більше чим (n-m-2) нулів.
По визначенню чисел звідси треба, що
а тому що повинне бути цілим, те
(52)
Але по визначенню чисел
(53)
З (52) одержуємо
(54)
і по лемі
(55)
З (52), (53) і (55) треба, що серед чисел (51) принаймні [1+(m+1)+s] = [m+2+s] позитивних, а ?/p>