Таким образом, максимальное значение вводимой переменной xk можно вычислить по следующей формуле.

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

УПРАЖНЕНИЯ 7.2.1

1. Дана следующая задача ЛП.

Векторы Р Р2, Р3 и Р4 показаны на рис. 7.4. Предположим, что текущим базисом является В = (Рр Р2).

a) Если вектор Р3 ввести в базис, какой вектор необходимо из него исключить, чтобы полученное базисное решение было допустимым?

b) Может ли вектор Р4 быть частью допустимого базиса?

2. Докажите, что для всех базисных переменных соответствующие разности гу - с\ равны нулю.

3. Докажите, что если в задаче максимизации (минимизации) для всех небазисных переменных х; выполняется неравенство г. - с. > О (< 0), то задача имеет единственное оптимальное решение. Если же для некоторых небазисных переменных х. выполняется равенство z.-c=Q, задача имеет альтернативное оптимальное решение.

4. Пусть начальное базисное решение задачи ЛП сформировано только из дополнительных остаточных переменных. С помощью матричного представления симплекс-таблицы покажите, что применение процедуры, описанной в разделе 3.3, где уравнение для целевой функции записано как

Максимизировать z - с,*, + с2х2 + с3х3 + с4х4

при ограничениях

РЛ+РЛ + РЛ + РЛ = Ь х хг, х3, х4>0.

Рис. 7.4. Векторы для упражнения 1

автоматически приведет к вычислению разностей г} - cj для всех переменных в начальной симплекс-таблице.

5. Пусть начальное базисное решение задачи ЛП сформировано только из искусственных переменных. Используя матричное представление симплекс-таблицы, покажите, что применение процедуры исключения искусственных переменных из целевой функции (для чего использовались ограничения-равенства), описанной в разделе 3.4.1, приведет к вычислению разностей zt - ct для всех переменных в начальной симплекс-таблице.

6. Пусть дана задача ЛП, в которой не накладываются ограничения на знак переменной хк. Докажите, что после замены хк=хк - хк , где х\ и х~к неотрицательны, невозможна ситуация, когда переменные х\ и хк заменяют одна другую в альтернативных оптимальных решениях.

7. Дана задача ЛП, записанная в стандартной форме и имеющая т ограничений (в виде равенств) и п неизвестных. Определите число смежных крайних точек, которые можно достичь из невырожденной крайней точки пространства решений. Почему здесь существенно условие невырожденности крайней точки?

8. Применяя условие допустимости симплекс-метода, предположим, что хг - базисная переменная, имеющая нулевое значение, а дс.- вводимая. Объясните, почему для того, чтобы переменную л:г исключить из базиса, необходимо выполнение неравенства (В 1Р;)г>0. Какие возникнут проблемы при выполнении неравенства (В-1РД.<0? {Подсказка. При ответе учитывайте, что переменная хг должна остаться неотрицательной.)

9. Что может указать на появление (впервые) вырожденного решения при реализации условия допустимости симплекс-метода? Какое условие приведет к повторению вырожденности решения на следующей итерации? Какое условие необходимо для того, чтобы вырожденность исчезла на следующей итерации? Обоснуйте ответы математически.

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

11. Дана следующая задача ЛП: максимизировать г = СХ при ограничениях АХ < b, X > 0, где b > 0. Предположим, что вводимый в базис вектор Ру таков, что по крайней мере один элемент вектора В~Ру положителен.

a) Пусть вектор Р, заменен на аР;, где а - положительное число, при этом переменная лгу остается переменной, вводимой в базис. Найдите соотношения между значениями переменной xjt соответствующими векторам Ру и ссР

b) Ответьте на вопрос предыдущего пункта, если дополнительно вектор b заменен на вектор рЧЬ, где (3 - положительное число.

12. Дана следующая задача ЛП: максимизировать z = СХ при ограничениях АХ<Ь, Х>0, где Ь>0. Предположим, что после получения оптимального решения возникла идея сделать небазисную переменную xt базисной (т.е. приносящей доход, если вспомнить экономическую интерпретацию задач ЛП) путем уменьшения ресурсов, расходуемых на единицу x/t до величины 1/а от исходного значения, где а- число, превышающее единицу. По-

скольку сокращено потребление ресурсов, ожидается, что доход на единицу Xj также уменьшится до величины 1/а от исходного значения. Может ли это изменение привести к рентабельности переменной xt? Каковы ваши рекомендации относительно того, чтобы сделать переменную х. приносящей доход?2

13. Дана следующая задача ЛП: максимизировать z = СХ при ограничениях (A, I)X = b, X > 0. Обозначим через Хв текущий базисный вектор, через Св - вектор коэффициентов целевой функции, соответствующих базисным переменным. Допустим, что вектор Св изменен на DB. Докажите, что в этом случае разности соответствующие базисному вектору Хв, останутся равными нулю. Дайте объяснение этому.

7.2.2. Вычислительная процедура модифицированного симплекс-метода

Имея условия оптимальности и допустимости, приведенные в разделе 7.2.1, можно описать последовательность вычислений, выполняемых в модифицированном симплекс-методе.

Шаг 0. Находится начальное базисное допустимое решение. Пусть В и Св - базис и вектор коэффициентов целевой функции, соответствующих базисным переменным.

Шаг 1. Каким-либо подходящим способом вычисляется обратная мат-рица В .

Шаг 2. Для каждой небазисной переменной х/ вычисляется величина

zrcrCBWlVrcr

Если для всех небазисных переменных х. величины zi - с}>0 в задаче максимизации или г. - с < 0 в задаче минимизации, то вычисления заканчиваются, так как получено оптимальное решение

хв = в-1ь,г = свхв.

Иначе на основе условия оптимальности определяется вводимая (в базис) переменная дс как небазисная переменная, которой соответствует наибольшая (по модулю) отрицательная величина zj - с/ в задаче максимизации или наибольшая положительная в задаче минимизации.

Этот вопрос можно переформулировать без экономического подтекста: при каких условиях переменная xt может быть представлена в оптимальном решении? - Прим. ред.

3 В большинстве руководств по линейному программированию, включая первые шесть изданий этой книги, приводится метод вычисления обратной матрицы на основе ее мультипликативного представления (см. раздел А.2.7). Поскольку в симплекс-методе последовательные базисы отличаются только одним вектор-столбцом, мультипликативное представление обратной матрицы позволяет не вычислять заново обратную матрицу на очередной итерации симплекс-метода, а получать ее из обратной матрицы предыдущей итерации, что значительно упрощает вычисления. Автор удалил описание этого метода получения обратной матрицы из данной главы, так как он не рассчитан на машинную реализацию вследствие возможных серьезных проблем, порождаемых ошибками округления. Обычно в программах, реализующих симплекс-метод, для вычисления обратной матрицы используются другие численные методы, такие как метод декомпозиции (разложения на две треугольные матрицы). В частности, программа TORA использует метод декомпозиции.