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

(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.}