Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Задача сведена в табл. 4.3. Предположим, что исходная таблица

Тогда ars — ведущий элемент. Прибавим к другим столбцам s-й

Таким образом, кроме выбора между прямым и двойственным методом, существует выбор между исключением по строкам и по столбцам. Это предполагает наличие четырех типов процедур. Унифицировать все таблицы не так просто, и в этом нет необходи­ мости/ В практических задачах требуется, чтобы все ограничения

и сохраняет это условие для всех таблиц. Проверка отношения выявляет ведущий элемент ars при помощи критерия

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

же образом, если таблица не является прямо допустимой, то выби­ рается ведущая строка и производится проверка отношения эле­ ментов этой строки к элементам нулевой Строки. Если проверка отношения дает нуль, т. е.

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

Рассмотрим задачу: максимизировать

Задача (1) сведена в табл. 4.4. Заметим, что она соответствует минимизации функции— ш1), так что здесь a0j ^ 0. Это означает, что если положить все небазисные переменные yj — 0 (/ = 1, 2,

условие ai0 ^ 0 соответствует тому, что при равенстве нулю всех небазисных переменных ограничения выполняются.

Последовательные таблицы 4.5, 4.6 и 4.7 содержат результаты соответствующих итераций метода. Ведущий элемент преобразо­ вания в каждой таблице помечен звездочкой. Обратите внимание на то, что обозначения строк слева от таблиц не изменяются. Текущие небазисные переменные записываются сверху от таблицы.

Проверяя w = яЬ, получаем 13/2 = 1 *(2) + 1 -(4) + 1/2 (1) + + 0 (1).

Как было показано, исходную задачу можно записать в матрич­

П р и м , p e d i

множества небазисных переменных. Поэтому можно записать

"1- X = р X/

где х' —новые небазисные переменные и

“1

1

1

а тп

«

1

1

1_

Другими словами, А* умножается справа на Р.

Пусть в задаче линейного программирования ограничения имеют вид равенств, а переменные неотрицательны; тогда, если ограничений меньше, чем переменных, естественно использовать строчную таблицу, а в других случаях — столбцовую таблицу. Несмотря на то что свободную переменную всегда можно заменить двумя неотрицательными, поступать подобным образом не очень удобно, поскольку общее число переменных при этом увеличи­ вается г). Поэтому, если исходная задача содержит свободные переменные, большей частью бывает удобнее решать двойственную к ней задачу. Прежде чем записать двойственную задачу, полезно в исходной освободиться от ограничений в виде равенств, посколь­ ку они будут порождать свободные переменные в двойственной задаче. Для этой цели обычно используется техника преобразова­ ния линейной программы с ограничениями-равенствами в линей­ ную программу с ограничениями-неравенствами, после чего переходят к двойственной задаче. Преобразованная и исходная задачи должны быть эквивалентны в том смысле, что оптимальные значения их целевых функций равны и можно из преобразованной задачи восстановить величины переменных исходной задачи.

Имеется четыре следующих стандартных преобразования:

1. Замена уравнения, содержащего неотрицательную перемен­ ную х-г, неравенством. Предположим, имеется уравнение —2а:! +

+ 4а;2 — 2а:3 = 2 и a:t ^ 0. Тогда его можно заменить неравен­ ством 4а:2 — 2а:3 ^ 2 .

*) См. § 1,2.