Точка А

Точка В

Точка С

Небазисные переменные

(*1> *г)

х1 вводится

<>!> S2)

Базисные переменные

х2 вводится

si исключается s2 исключается Оптимум

Рис. 3.4. Вводимые и исключаемые переменные в симплекс-методе

3. На рис. 3.5 показано пространство допустимых решений трехмерной задачи ЛП с угловыми точками А, В, С, J.

a) Могут ли следующие пары угловых точек составить часть пути при успешном выполнении симплекс-метода: (А, В), (В, D), (Е, Н), (А, 1)7 Поясните ответ.

b) Предположим, что реализация симплекс-метода начинается в точке А и заканчивается в точке оптимума Н. Определите, какие из следующих последовательностей угловых точек могут привести к точке оптимума. Обоснуйте свой вывод.

i) А-> B->G-> Н.

ii) А->С->/->Я.

in) A->C->£->£->A->Z)->G->#.

Рис. 3.5. Пространство решений для задачи ЛП

4. Пусть в задаче ЛП, которой соответствует пространство допустимых решений, показанное на рис. 3.5, все ограничения являются неравенствами типа "<", а все переменные задачи (т.е. xv хг и х3) неотрицательны. Обозначим через s,, s2, s3 и s4 дополнительные (неотрицательные) переменные, ассоции-

руемые с ограничениями, представленными плоскостями CEIJF, BEIHG, DFJHG и IJH соответственно. Определите базисные и небазисные переменные для каждой угловой точки пространства допустимых решений.

5. Пусть в задаче ЛП, для которой пространство допустимых решений представлено на рис. 3.5, реализация симплекс-метода начинается в точке А. Определите вводимую переменную на первой итерации симплекс-метода, а также ее значение и значение целевой функции, если целевая функция имеет следующий вид.

a) Максимизировать г - х1- 2х2 + Зх3.

b) Максимизировать г = 5л:, + 2х2 + 4х3.

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

d) Максимизировать z - ху + х2 + х3.

3.3.2. Вычислительный алгоритм симплекс-метода

В этом разделе показаны вычислительные свойства алгоритма симплекс-метода, которые включают правила для определения вводимых и исключаемых переменных, а также условия достижения оптимального решения, при которых вычисления завершаются. Рассмотрим числовой пример.

Пример 3.3.1

Используем задачу о компании Reddy Mikks (пример 2.2.1) для рассмотрения деталей выполнения симплекс-метода. Эта задача в стандартной форме записывается так:

максимизировать z = 5дс, + 4х2 + 0s, + 0s2 + 0s3 + 0s4

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

6xi + 4х2 + si = 24 (ограничение на сырье М1), xi + 2x2 + s2 = 6 (ограничение на сырье М2), -*1 + Хг + вз = 1 (ограничение на спрос), хг + s4 = 2 (ограничение на спрос),

Хи Хг, Si, S2, S3, Si > 0.

Здесь sv s2, s3, st - дополнительные (остаточные) переменные, добавленные в неравенства для преобразования их в равенства.

Далее целевую функцию будем представлять в виде уравнения

z- 5х1- 4х2 = 0.

Задачу ЛП в стандартной форме можно представить в виде следующей компактной таблицы.

Таблица показывает множества базисных и небазисных переменных, а также решение, соответствующее данной (начальной) итерации. В разделе 3.3.1 указывалось, что начальная итерация симплекс-метода начинается из точки (*,, х2) = (0, 0). Это соответствует следующим множествам базисных и небазисных переменных.

Небазисные (нулевые) переменные: (jc,, х2).

Базисные переменные: (sv s2, s3, st).

Поскольку небазисные переменные хх,хг и коэффициенты при базисных переменных sv s2, s3, s4 в уравнении целевой функции равны нулю, а в формулах левых частей равенств-ограничений - 1, то отсюда сразу без дополнительных вычислений получаем, что z - 0,s1 = 24, s2 = 6, s3 = 1 и st = 2.

В таблице базисные переменные перечислены в левом столбце "Базис", а их значения приведены в правом столбце "Решение". Таким образом, в таблице текущая угловая точка определяется путем указания базисных переменных и их значений, а также вычисляется соответствующее значение целевой функции 2. Помните, что небазисные переменные (которые не приведены в столбце "Базис") всегда равны нулю.

Будет ли это начальное решение оптимальным? Конечно, нет, поскольку переменные хх и х2 здесь равны нулю, а возрастание этих переменных даже на единицу приводит к увеличению значения целевой функции z= 5хх + 4х, на 5 (при увеличении хх) или 4 (при увеличении х2). Поскольку коэффициент при переменной хх в формуле целевой функции больше, чем коэффициент при х2, переменную jc, следует ввести в число базисных (в этом случае она станет вводимой). Если обратиться к приведенной выше таблице, то вводимая переменная определяется среди множества небазисных как переменная, имеющая наибольший отрицательный коэффициент в z-строке (напомним, что тут решается задача максимизации). Если так случится, что все коэффициенты в z-строке будут неотрицательными, то дальнейшее увеличение значения целевой функции будет невозможно; это будет означать, что достигнуто оптимальное решение.

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

На рис. 3.6 видно, что неотрицательные отношения порождают точки пересечения на положительной полуоси хг Отношения (пересечения), соответствующие переменным s3 и st, исключаются из рассмотрения, поскольку для них точка пересечения лежит или на отрицательной полуоси, или на бесконечности.

Минимальное неотрицательное отношение соответствует базисной переменной sv тем самым определяя эту переменную как исключаемую (т.е. на следующей итерации ее значение будет равно нулю). Значение вводимой переменной х, в новом