Метод Гомори последовательных отсечений - Математическое моделирование экономических процессов

При решении многих задач (планирование мелкосерийного производства, распределение кораблей по путям сообщения, выработка суждений типа "да-нет" и т. п.) нецелочисленное решение не имеет смысла. Попытка тривиального округления до целых значений приводит либо к нарушению ограничений задачи, либо к недоиспользованию ресурсов. Как мы имели возможность убедиться, для произвольной линейной программы (за исключением программ типа классической транспортной задачи, где коэффициенты матрицы ограничений равны 1 или 0) гарантировать целочисленность решения невозможно.

В случае двухмерной задачи проблема решается относительно просто путем выявления всех целочисленных точек, близких к границе множества планов, построения "выпуклой целочисленной оболочки" (выпуклого множества планов, содержащего все целочисленные планы) и решения задачи над этим множеством.

B общем случае выдвигается идея последовательного отсечения нецелочисленных оптимальных планов: обычным симплексным методом отыскивается оптимальный план и, если он нецелочисленный, строится дополнительное ограничение, отсекающее найденный оптимальный план, но не отсекающее ни одного целочисленного плана.

Эта идея, принадлежащая Д. Данцигу и Р. Гомори, впервые была представлена в форме дополнительного ограничения:

(сумма небазисных компонент оптимального плана должна быть отлична от нуля; хотя бы одна из небазисных компонент должна быть ненулевой). В самом деле, оптимальный план с нулевыми значениями небазисных компонент этому условию не удовлетворяет, что подтверждает отсечение этого плана от исходного множества.

К сожалению, для абсолютного большинства задач скорость сходимости процесса таких отсечений мала. Потому Р. Гомори предложена другая форма дополнительного ограничения. Так, если компонента плана, определяемая k-ым уравнением системы ограничений, нецелочисленна, то добавляется ограничение

Где fK - дробная часть компоненты плана (правой части ограничения) и fKj - дробная часть коэффициента при XJ (целая часть числа - наибольшее целое, не превышающее это число; дробная часть числа равна разности между числом и его целой частью), S* - новая дополнительная переменная.

Например, если ограничение имеет вид

То дополнительное ограничение принимает вид

Можно уменьшить объем преобразований, если руководствоваться следующими правилами:

    1. выбирать в качестве базового для построения дополнительного ограничения уравнение, определяющее компоненту плана с наибольшей дробной частью; 2. для ввода в базис опорного плана расширенной задачи выбирать переменную, для которой достигается минимум из отношений абсолютных значений DJ к значениям fKj; 3. если одна из ранее введенных дополнительных переменных вошла в базис, ее и соответствующее ей уравнение можно отбросить (эта ситуация связана с появлением более жесткого условия, перекрывающего действие ранее введенного).

Появление дополнительного ограничения и дополнительной переменной вновь приводит к проблеме выбора начального опорного плана расширенной задачи и к использованию с этой целью искусственной переменной. Следует заметить, что если при поиске переменной, исключаемой из базиса, значениеQ (определяемое с учетом дополнительного ограничения) соответствует этому ограничению, то можно отказаться от использования искусственной переменной (она все равно выведется из базиса на этом же шаге решения).

Заметим, что для целочисленных программ может обнаружиться отсутствие целочисленных планов (противоречивость ограничений).

Для предложенного здесь метода доказана конечность процесса отсечений, но число этих отсечений непредсказуемо (вполне может обнаружиться быстрое решение задач с десятками переменных и ограничений и фантастически длительное для задач небольших размеров).

Похожие статьи




Метод Гомори последовательных отсечений - Математическое моделирование экономических процессов

Предыдущая | Следующая