Рішення задач цілочисленного програмування (стр. 4 из 5)

Якщо x(£_k, C) є неприпустимим рішенням задачі (27–30) і

, тоді, використовуючи i-ю рядок симплексної таблиці, можна побудувати відсікання, що володіє властивістю правильності по формулах:

(31)

(32)

де

(33)

Доказ. Перевіримо спочатку умову відсікання. Нехай в оптимальному рішенні x(£_k, C) координата

не задовольняє умові (29). Покажемо, що в цьому випадку вектор х(£_k, C) не задовольняє умовам (31, 32). Оскільки N_k – множина індексів небазисних змінних x_i, які в оптимальному рішенні дорівнюють нулю, то рівність (31) приймає вид і буде негативним відповідно до умови теореми. Отже, , тобто умова відсікання не виконується.

Перевіримо умову правильності. Для цього покажемо, що будь-яке припустиме рішення задачі (27-30) задовольняє умовам (31, 32).

Запишемо розкладання для координати припустимого рішення задачі (27-30) по небазисним змінним

(34)

і розглянемо два випадки: a)

; б) . Уведемо позначення:

і представимо (34) у вигляді

де

Очевидно,

тому що .

Розглянемо випадок а):

, або що однаково, .

Звідси

Але тому

(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₀= min {i| 1<i<n₁, х_j0^k – не задовольняє (29)}.

4. Для обраного номера i=i₀ будується правильне відсікання, тобто вводиться додаткова змінна

де

визначається формулою (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)=x^r є оптимальним опорним планом задачі (£_r, C) і x^r не задовольняє умові цілочисленності, N_r – множина індексів, що нумерують небазисні змінні, відповідні x^r.

Тоді нерівність

(43)

є правильним відсіканням.

Правильне відсікання, що відтинає нецілочисленний оптимум x(£_r, C) задачі (£_r, C), можна записати в такий спосіб:

– ціле.

Помітимо, що кожна із знову змінних

однозначно визначається завданням змінних

, так що

.

Позначимо через

упорядковані в порядку зростання компоненти

плану x задачі (39) – (41), так що

(44)

Покладемо

(45)

Лема. Якщо для деякого плану x задачі (39) - (41)

, (46)

те

(47)

Доказ проведемо по індукції. Спочатку доведемо, що

(47¢)

По визначенню

(48)

Тому що ранг матриці

дорівнює m, те