что переменным Л, и R2 соответствуют ненулевые коэффициенты (-М, -М) в строке г (сравните с начальным решением в примере 3.3.1, где дополнительным переменным соответствуют нулевые коэффициенты в z-строке). Чтобы сделать эти коэффициенты нулевыми, следует умножить элементы строк Л, и R2 на величину М, и затем сложить эти строки с z-строкой. (Обратите внимание на подсвеченные единицы в этих строках - если бы эти коэффициенты были отличны от единиц, то необходимо было бы сначала разделить все элементы этих строк на данные коэффициенты.) Кратко это действие можно записать следующим образом.

Новая z-строка = старая z-строка + М х /?,-строка + М х /?2-строка

Измененная симплекс-таблица примет следующий вид (проверьте!).

Отметим, что теперь z = 9М, что соответствует базисному решению Л, = 3, R2 = 6 и х4-4.

Последняя таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости, описанных в разделе 3.3.2. Поскольку мы минимизируем целевую функцию, находим наибольший положительный коэффициент в z-строке. Наибольший коэффициент -4 + 7М соответствует переменной д- которая и будет вводимой. Условие допустимости указывает на переменную Л, в качестве исключаемой.

Поскольку вводимая и исключаемая переменные определены, новую симплекс-таблицу можно вычислить с помощью метода Гаусса-Жордана. Заметим, что вычисления в z-строке, где присутствует М, следует проводить алгебраически. Так, для получения новой г-строки надо новую ведущую строку умножить на -(-4 + 7М) и сложить с текущей z-строкой. В результате получим следующую таблицу.

Отметим, что уже первая итерация исключила из базисного решения искусственную переменную Rlt что является результатом включения штрафа в целевую функцию.

Последняя таблица показывает, что следующими (вводимой и исключаемой) переменными будут д:2 и R2 соответственно. Конечно, для получения оптимального решения может потребоваться больше двух итераций. В данной задаче оптимальным решением будет хх = 2/5, л\, = 9/5, х3 = 1 и z = 17/5.

При использовании М-метода следует обратить внимание на следующие два обстоятельства.

1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации по крайней мере одна искусственная переменная будет иметь положительное значение. Это индикатор того, что задача не имеет допустимого решения. В разделе 3.5.4 показана такая ситуация.

2. Теоретически применение М-метода требует, чтобы М-Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Как понимать термин достаточно большая - это открытый вопрос. Величина М должна быть настолько большой, чтобы выполнять роль штрафа , но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении вычислений, в которых совместно участвуют как большие, так и малые числа.

УПРАЖНЕНИЯ 3.4.1

1. Завершите решение задачи из примера 3.4.1 и получите оптимальное решение.

2. Найдите решение задачи из примера 3.4.1 с помощью программы TORA (файл ch3ToraMmethodEx3-4-l.txt), используя команду Iterations1M-method (ИтерацииМ-метод). Сравните решения при М=1,М=10иМ = 1000. Какое заключение можно сделать из этого эксперимента?

3. В примере 3.4.1 найдите начальную симплекс-таблицу для каждого из следующих (независимых) случаев и подсчитайте коэффициенты z-строки после определения всех искусственных переменных.

a) Третье ограничение имеет вид л:, + 2х2 > 4.

b) Второе ограничение имеет вид 4л:, + Зх2 < 6.

c) Второе ограничение имеет вид 4л:, + Зх2 = 6.

d) Целевая функция имеет вид: максимизировать z = 4л:, + х2.

4. Существует следующее множество ограничений.

Для каждой из следующих задач найдите коэффициенты z-строки симплекс-таблицы после введения искусственных переменных.

a) Максимизировать z = 5л:, + 6л:2 при ограничениях (1), (3) и (4).

b) Максимизировать z = 2л:, - 7х2 при ограничениях (1), (2), (4) и (5).

c) Минимизировать z = Зл:, + 6л;2 при ограничениях (3), (4) и (5).

-2xi + Зх2 = 3,

4xi +5х2> 10, xi + 2X2 < 5, 6x1 + 7х2 < 3, 4xi + 8x2 > 5,

(1) (2) (3) (4) (5)

X1, X2>0.

d) Минимизировать z = 4х, + 6х2 при ограничениях (1), (2) и (5).

e) Минимизировать z = Зх, + 2х2 при ограничениях (1) и (5).

5. Дано следующее множество ограничений:

X j т~ Х *т~ g ~~ 7

2х, - 5х2 + х3 > 10, х х2, х3>0.

При этих ограничениях решите задачи ЛП для следующих целевых функций.

a) Максимизировать z = 2х, + Зх2 - 5х3.

b) Минимизировать z = 2х, + Зх2 - 5х3.

c) Максимизировать z = х, + 2х2 + х3.

d) Минимизировать z = 4х, - 8х2 + Зх3.

6. Дана следующая задача.

Максимизировать z = 2х, + 4х2 + 4х3 - Зх4 при ограничениях

Xj ~\~ Х *т~ >

х, + 4х2 + х4 = 8, х Х2, Х3, Х4 0.

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

7. Без применения искусственных переменных решите следующую задачу, используя в начальном базисном решении переменные х3 и х4.

Минимизировать z = Зх, + 2х2 + Зх3

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

х, + 4х2 + х3 > 7, 2х, + х2 + х4 > 10, х х2, Х3, х4 0.

8. Дана следующая задача.

Максимизировать z = х, + 5х2 + Зх3

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

х, + 2х2 + х3 = 3, Х2 4)

Xt) х2$ 3 -

В первом равенстве переменная х3 может войти в базисное решение вместо искусственной переменной. Однако во втором равенстве искусственная переменная R2 необходима. Используя начальное базисное решение, состоящее из переменных х3 и R2, найдите оптимальное решение этой задачи.

9. Покажите, как с помощью М-метода можно определить, что следующая задача не имеет допустимого решения.