Курсовая работа: Методы отсечения

является правильным отсечением.

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

– целое.

Заметим, что каждая из вновь вводимых переменных однозначно определяется заданием переменных , так что .

Обозначим через упорядоченные в порядке возрастания компоненты плана x задачи (39) – (41), так что

(44)

Положим

(45)

Лемма. Если для некоторого плана x задачи (39) – (41)

, (46)

то

(47)

Доказательство проведем по индукции. Сначала докажем, что

(47¢)