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

начальное допустимое решение задачи (2), то мы движемся в точ­ ку J и затем в точку D. Если начальное допустимое решение есть Н, то мы перемещаемся в точку G, затем в точку F, затем в D.

В прямом симплекс-методе элементарное преобразование свя­ зано с заменой в текущем базисе одного из векторов на небазисный.

от того, какой из векторов, АЕ или А С, составляет меньший угол с вектором (—Ь). В любом случае на следующем шаге будет до­ стигнута точка D. Если начальным допустимым решением являет­ ся точка В, то на следующем шаге может быть достигнута точка D (или С), поскольку и С и D принадлежат одной гиперплоскости

свектором нормали а6.

Упражнения

1.Рассмотрим задачу минимизировать

z = - 2 я 4 — 3*5

при условиях

* 1 — * 3 —j— * 4 - j - 3 * 5 — 3 ,

хъ+ хз + ~ 2 xi 4* 2*5 = 24

хз > о (/ = 1, . . . , 5).

Решите эту задачу, использовав в качестве начальных базисных переменных *л и *2, выбрав для ввода в базис лексикографически минимальный столбец. Проверяйте правильность решения посред­ ством вычисления на каждом шаге z = яЬ.

2.Рассмотрим задачу:

идвойственную к ней. Предположим, что В — матрица оптималь­ ного базиса. Покажите, что я = свВ -1 — оптимальное решение двойственной задачи, где вектор св состоит из компонент вектора с, отвечающих базисным переменным оптимального базиса. Исполь­ зуйте тот факт, что условие сх >. яЬ справедливо для любых допустимых решений х и я прямой и двойственной задач соответ­ ственно.

1 *

ГЛАВА б

МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

5Л. Введение (Данциг и Орчард-Хейс [43])

В симплекс-методе все элементы симплексной таблицы пере­ считываются на каждой итерации. Допустим, исходные ограниче­ ния задаются матрицей А размера т X п, а оптимальное решение получается после t-й итерации. Тогда, естественно, для решения задачи необходимо последовательно найти t (т + 1) (п -j- 1) чисел. При вычислениях, как только получена очередная таблица, можно переходить к следующей итерации. Все предыдущие таблицы, включая исходную, могут быть «забыты». Предположим, что исходная таблица сохраняется. Какой информацией необходимо располагать в этом случае, чтобы получить все элементы текущей таблицы? Пусть нас интересует 29-я таблица. Тогда достаточно знать матрицу В -1, соответствующую 29-й таблице, и индексы текущих базисных переменных. Все остальные элементы 29-й таблицы можно получить из элементов исходной таблицы и обра­ щения текущего базиса В 29-й таблицы. Заметим, что я = свВ -1, т. е. текущий вектор я получается умнояшнием вектора св из исходной таблицы на обращение текущего базиса В -1. (Индексы текущих базисных переменных указывают, какие компоненты

входят в св.) Вектор Ь задается произведением В _1Ь, где Ь берется из исходной таблицы; любой столбец а.) получается умножением В -1 на aj, где а} — столбец исходной таблицы и В -1 — обращение текущего базиса. Таким образом, если заданы В -1 и индексы базисных переменных, то, используя исходную таблицу, можно получить все элементы текущей таблицы.

Пусть заданы исходная таблица и матрица В -1, соответствую­ щая 29-й таблице. Какие элементы 29-й таблицы необходимы для того, чтобы получить матрицу В -1, соответствующую 30-й табли­ це? Такими элементами являются компоненты небазисного столбца

из 29-й таблицы, который доляшн быть введен в базис, и Ь из 29-й таблицы. Вектор а;- является кандидатом для вводив базис, если Cj < 0 *). Таким образом, необходимо вычислить с, данной (29-й) таблицы, выбрать среди них cs < 0 и затем вычислить as = B _1as и b = B -1b. Это дает возможность найти В -1 для сле-

г) Рассматривается задача минимизации.— Прим. ред.