Курсовая работа: Дискретное программирование

Из 18 следует, что если все хj, j=1: n являются целыми, то целым будет и выражение

стоящее в левой части 18, и, стало быть, правая часть данного уравнения:

также должна быть целой. Предположим, что

тогда, в силу того, что 0 ≤ {άi} < 1, а {αi,j} ≥ 0, xj ≥ 0, должно выполняться неравенство

Однако неравенства 19 и 20 противоречат требуемой целочисленности правой части 18 xj(β(q)). Следовательно, для целочисленных решений должно выполняться условие, противоположное неравенству 19, или, что то же самое,

В то же время 21 не выполняется для любого нецелочисленного базисного плана х. Действительно, небазисные компоненты плана равны нулю: хj =0 , j∊N(β(q)), и 21 приобретает вид {άi} ≤0 <=> {άi} =0, но это противоречит предположению о нецелочисленности плана х, т. к. в базисном плане хi = άi. Все сказанное позволяет утверждать, что ограничение 21 задает правильное отсечение.

Таким образом, с точки зрения организации техники, вычислений для осуществления правильного отсечения мы должны к системе ограничений нецелочисленной линейной задачи, решаемой на q-й итерации, добавить условие

где xn+1 ≥0 — фиктивная переменная, добавляемая для преобразования неравенства в строгое равенство. Ей соответствует нулевой коэффициент в целевой функции.

Данному преобразованию условий задачи будет соответствовать преобразование симплекс-таблицы, показанное на рис.2. На нем по соображениям обеспечения наглядности использованы обозначения 14 и предполагается, что текущий базис β(q) состоит из первых m столбцов.

Индекс i соответствует выбранной для формирования отсечения строке симплекс-таблицы, содержащей нецелочисленное значение bi(β(q)).

Как видно из рис.2, технически преобразование таблицы сводится к дописыванию одной строки и одного столбца. При этом легко убедиться, что модифицированные столбцы

совместно с добавленным столбцом

образуют сопряженный (двойственно допустимый) базис для сформированной задачи, а (ά1, ..., άm, -{άi}) являются ненулевыми компонентами соответствующего псевдоплана. Исходя из этого, приходим к тому, что для решения вновь полученной задачи может быть эффективно применена процедура двойственного симплекс-метода.

Поскольку в начальном псевдоплане имеется только одна отрицательная компонента (-{άi}), то из базиса должен быть выведен соответствующий ей вектор аn+1 . Далее, следуя рекомендациям алгоритма двойственного симплекс-метода, находим оптимальный план. Если он не является целочисленным, то описанные действия итеративно повторяются.

Если в ходе решения дополнительная переменная хn+1 вновь становится базисной, ее значение оказывается безразличным для основных переменных. Поэтому строку и столбец, отвечающие ей, вычеркивают. С геометрической точки зрения это можно обосновать так: если псевдоплан оказывается внутри полупространства хn+1 ≥0, то дополнительное ограничение, определяемое гиперплоскостью хn+1=0, становится несущественным и опускается.

4.2 Описание алгоритма

Приведем обобщенную схему алгоритма Гомори. Структурно он делится на так называемые большие итерации. Каждая большая итерация содержит этапы:

1) Решение "текущей" задачи методами линейного программирования (малые итерации). На первой итерации в качестве "текущей" задачи выступает нецелочисленный аналог исходной ЦЗЛП.