Классификация задач линейного программирования

     целочисленной задачи. В этом случае решение получается сразу, без использования

     ограничений целочисленности. Если а_i0≥ 0, но не все целые,

     добавим к ограничениям (1) еще одно. Новое  ограничение записывается внизу

     таблицы так, чтобы она перестала быть прямо допустимой, т. е. аi₀

     <О   для i == п + т + 1. Затем используется

     двойственный  симплекс-метод с целью сделать  все аi₀≥ 0. Если

     аi₀ получаются  нецелыми, в таблицу добавляются новые ограничения

     до  тех пор, пока аi₀ (i = 1, . . ., n, . . ., n + m) не станут все

     целыми  и неотрицательными.

     Если  после введения дополнительного  ограничения текущая таблица  перестает

     быть  прямо допустимой, то текущее решение, представляющее собой вершину

     многогранника решений, не удовлетворяет этому дополнительному ограничению.

     Другими словами, дополнительное ограничение отсекает часть пространства

     решений. Если дополнительные ограничения не отсекают ни одной целочисленной

     точки пространства решений исходной задачи, то, вполне вероятно, после

     введения  достаточного числа дополнительных ограничений вершины суженного

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

     можно получить оптимальное целочисленное  решение. Трудность состоит в

     систематическом получении дополнительных ограничений  и доказательстве

     конечности  алгоритма.

     Каждый  раз после проведения итерации симплекс-метода происходит изменение

     множества небазисных переменных. Таблица также меняется. Будем использовать

     t для обозначения t-й. таблицы. Матричное уравнение (2) запишется

     как

     Х^t = А^t (-х^t_n),

     (3)

     где х° — вектор-столбец с n + т + 1 компонентами, А° — матрица размера

     (п  + т + 1)*(n + 1) и (—х⁰_n) — вектор с компонентами

     (1, —x₁, . . ., —x_n), представляющими собой

     текущие небазисные переменные, взятые со знаком минус. Если в матрице А

     а0i≥0 (j = 1, . . ., n), а₀₀ ≡ 0 (mod 1) ¹

     } и а_i0 ≥ 0 (i=1, . . ., п+т) — целые

     неотрицательные числа, то получено оптимальное решение  целочисленной задачи.

     Если  а_i0 не все целые, введем дополнительное ограничение. Рассмотрим

     такое уравнение из (3), в котором а_i0m

     нецелое. Опуская индексы строки, имеем

     (4)            x=a₀+∑a_j(-x_j)

     где x_j в правой части — текущие небазисные переменные и a₀

     — нецелое. Поскольку требуется, чтобы  х было целым, или х

     ≡[1]0 (mod1), правая часть уравнения

     (4) также должна удовлетворять условию

     0≡a₀+∑a_j(-x_j)               (mod1).

     (5)

     Это условие должно выполняться при  допустимом целочисленном решении. Поскольку

     требуется, чтобы x_j ,были целыми, можно алгебраически складывать с

     (5) отношения 0≡f₀+∑_jf_i(-x_i

     ) (mod1) (0<f₀<1, 0≤f_j<1).

     (6)

     Условие (6) эквивалентно следующему:

     ∑f_jx_j≡f₀ (mod1).

     (7)

     В соотношении (7) f₀ – константа, меньшая единицы ,и поскольку f

     _j≥0 и x_j≥, левая часть всегда положительна. Т.к.

     (7) – отношение сравнения по модулю 1, левая часть может принрмать  только

     значения  вида f₀, f₀+1,.., т.е.

     ∑f_jx_j≥f₀                                                                                                       

     (8)

     Неравенство (8) можно представить в виде уравнения  с помощью введения

     неотрицательной целочисленности слабой переменной

     S=-f₀+∑f_jxj≥0.

     (9)

     Это уравнение можно приписать внизу  таблицы и использовать в качестве ведущей

     строки. Таким образом, переменная s войдет в базис с отрицательным значением

     (—fо)- После итерации слабая переменная s станет небазисной с нулевым

     значением. Ведущая строка превратится в  тождество s ≡ (—1) (—s) и может

     быть  исключена. Будем называть переменную s в уравнении (9) слабой переменной

     Гомори. Ниже будет обсуждено, что произойдет, если сохранять все

     дополнительные  строки, соответствующие слабым переменным Гомори.

     Дадим доказательство конечности алгоритма. Доказательство будет проведено  в

     предположении, что известна некоторая нижняя граница  значения Х₀, т.

     е. если существует целочисленное решение, то оно больше, чем наперед заданная

     величина  М (М может быть достаточно большой  по абсолютной величине

     отрицательной константой). Такое предположение не слишком обременительно и

     всегда  выполняется, если выпуклое множество, определяемое условиями (2),

     ограничено. Сначала изложим сам алгоритм.

     Шаг 1. Решить задачу целочисленного программирования так, как если бы это была

     линейная  программа, т. е. с помощью прямого  или двойственного симплекс-метода.

     Если  получено оптимальное решение задачи линейного программирования, то a_i

     ₀≥0 (i=1, . . ., m + n) и a_0i≥0(j = 1, .

     . ., n). Требуется также, чтобы а^t_j > 0 (j = 1, . . .,

     n).

     Шаг 2. Если а_i0 — все целые, то задача решена, и решение получено без

     использования дополнительных ограничений. В противном случае пусть а^t

     _i0 — первая нецелочисленная компонента в α^t₀.

     Тогда i-я строка называется производящей строкой. Записать внизу таблицы

     уравнение

     s=-f^t_i0-∑f^t_ij(-x^t

     _j).                                                           (10)

     Уравнение (10) называется отсечением Гомори. Проделать  шаг двойственного

     симплекс-метода, используя в качестве ведущей  строки отсечение Гомори (10). При

     этом  таблица останется двойственно допустимой. Повторять до тех пор, пока все

     а_i0 (i = 1, . . ., m+n) не станут целыми неотрицательными. Если а

     _i0 на некотором шаге остается отрицательным, следующий шаг двойственного

     метода  производится без введения отсечения  Гомори. (Если а_i0

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

     Если a₀₀  становится нецелым, следует выбрать нулевую строку в

     качестве  производящей.)

     Изменение элементов а_ij (i = 0, 1, . . ., n+m; j = 0, . . . . . ., n)

     в таблице за одну итерацию называется циклом. Для обозначения циклов

     используется  буква t. Для доказательства конечности не достаточно условий

     α^t₀ >α₀ ^t+1 >М,

     поскольку a₀₀ может изменяться каждый раз на ε(t), а ∑

     ε (t) = с.

     Примером  этого может служить ε (t) =1/2t.  Другой возможностью является то,

     что а₀₀ остается равным фиксированному значению, большему нижней

     границы, в то время как некоторое а_i0 неограниченно уменьшается.

     Чтобы увидеть, как преодолеваются эти  трудности, необходимо в деталях

     рассмотреть шаги итерации.

     При доказательстве будет показано, что  либо после конечного числа шагов  все

     компоненты 0-го столбца становятся неотрицательными целыми, либо не существует

     целого  решения. Если a₀₀ остается постоянным для всех t ≥ t

     ₀, то a^t₀₀ должно быть целым.

     Предположим, что а^t₀₀—нецелое. Пусть а^t₀₀

     =n^t₀₀+f^t_00,где n^t₀₀

     — целое и 0 < f^t₀₀ < 1. Тогда 0-я строка становится

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

     S=-f^t₀₀-∑f^t₀(-x^t_j).

     Если s-й столбец является ведущим, то

     a^t+1₀₀=a^t₀₀-a^t_0s* f^t₀₀/f^t_os

     или

         

     Другими словами, a₀₀ уменьшится по крайней мере до ближайшего целого.

     Следовательно, a₀₀  не может уменьшаться на ε(t) при

     ∑ε (t)<c

     Если a₀₀ каждый раз уменьшается до ближайшего целого или на целую

     величину, то после конечного числа шагов  оно станет меньше любого наперед

     заданного М (М — предполагаемая нижняя граница). Если алгоритм бесконечен, то

     a₀₀   должно оставаться некоторым фиксированным целым числом для

     t> t₀. Предположим, что это произошло.

     Тогда рассмотрим а₁₀ . Так же как и a₀₀, a₁₀ не

     может оставаться нецелым значением. Если бы это было так, то, поскольку a

     ₀₀ — целое, первая строка стала бы производящей и после введения отсечения

     Гомори  и итерации симплекс-метода мы получили бы

     A^t+1₁₀=a^t₁₀-a^t_1s*f^t₁₀/f^t_1s,

     где 0<f^t_1s<l и 0<f^t_1s<1.

     Здесь a^t_1s —неотрицательное число, большее f

     ^t_1s.  (Если a^t_1s

     —отрицательно и α^t_s—лексикографически положителен, то

     а^t_0s положительно и, следовательно, а^t

     ₀₀ не может

     не  измениться.) Отсюда

     a^t+1₁₀≤a^t₁₀-f^t₁₀=[a^t₁₀],

     т. е. а₁₀ уменьшается по крайней мере до ближайшего целого. Поэтому

     а₁₀ либо будет оставаться некоторым фиксированным целым числом,

     либо  после конечного числа шагов  станет отрицательным. Если а₁₀

     станет  отрицательным, то первая строка будет  ведущей и