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

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

где все bt неотрицательны.

Если ввести искусственные переменные xf и новую целевую функцию

т

1 = 2 х?,

г= 1

то получим задачу: минимизировать

4 " 0 ,m lx i 4“ &m2x 2 4 “ • • • 4“ ®тппх п — Ът ,

Система (3) является диагональной формой относительно —Е, —z, х°, . . Хт. Первая фаза симплекс-метода состоит в минимиза­ ции | при условиях (3). На знак z ограничений не накладывается. В процессе вычислений, как только искусственная переменная становится небазисной и ее коэффициент в |-форме положителен, сама переменная и соответствующий ей вектор-столбец из даль­ нейших вычислений исключаются. Посмотрим, почему это воз­ можно.

Заметим, что все таблицы, получающиеся при работе алгорит­ ма, эквивалентны х). В процессе вычислений на первой фазе имеем

I = £о+ 2 djXj + 2 dtXi,

где dj -g 0 и dt > 0. Если положить небазисные переменные Xj и х?

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

1. Ранг матрицы А меньше т, т. е. любая система т столбцов матрицы А линейно зависима. Используя те же рассуждения, что и в теореме 1.9, можно показать, что в этом случае, если существу­ ет базисное решение, то существует вырожденное базисное решение.

2. Ранг матрицы В равен т, но Ь лежит в выпуклом конусе, натянутом на подмножество векторов из В.

Рассмотрим систему уравнений

Ах = Ь (А есть (т X и)-матрица, т <С.п)

без искусственных переменных. Если система уравнений избыточна и совместна, это означает, что ранг строк матрицы А равен рангу строк матрицы [А, Ь] и меньше т. В частности, ранг строк под­ матрицы В меньше т. Поскольку ранг строк матрицы равен рангу)*

*) То есть описывают одну и ту же задачу.— Прим, ред.

на исходные путем эквивалентного преобразования. Если после преобразования все искусственные переменные из базиса выведе­ ны, то полученный вырожденный базис служит начальным базисом для второй фазы. Если же искусственную переменную ж? невоз­ можно вывести из базиса преобразованием из-за того, что аг] = О для всех /, то это означает, что исходная система избыточна.

Для примера рассмотрим такие два уравнения:

Система, состоящая из этих уравнений, очевидно, избыточна. Используем искусственные переменные для исследования избы­ точности системы. Получим

х° (г — 1, 2) войдет в базис с нулевым значением. Преобразование не сможет вывести из базиса переменную х % , поскольку a rj — 0

для / = 3, 4, 5, что и показывает избыточность системы урав­ нений.

Рассмотрим стандартные приемы получения начального допу­ стимого базисного решения. Не теряя общности, мы можем рас­ сматривать ограничения задачи линейного программирования в следующем виде:

где Ьг ^ 0.

Если ограничение представляет собой равенство

^ ] a i j X j = bi , j

то можно добавить искусственную переменную

X i + ' 2 i a i j X j =bi - j

Если ограничение представляет собой неравенство

S d i j X j ^ b i ,

з

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

^Icij j X j Ч~Si —b j .

з