Курсовая работа: Рішення задач цілочисленного програмування
Теорема. Якщо: коефіцієнти цільової функції дискретні; 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¢)