0 1 2 3 4 5

Рис. 3.3. Итерационный процесс симплекс-метода

Этот раздел завершим описанием перевода небазисных переменных в базисные и наоборот при переходе от одной угловой точки к следующей. На рис. 3.4 показано, что в точке А переменные s, и s2 являются базисными, а переменные хх и хг - небазисными. Если переменная хх принимает положительное значение, мы переходим в угловую точку В, в которой изменяется состояние переменной хх из небазисной в базисную. Одновременно переменная s которая была базисной в точкеА, становится небазисной и принимает нулевое значение в точке В. Здесь существенно, что происходит одновременный обмен состояниями между небазисной переменной хг и базисной переменной s что приводит к новым базисным переменным (* s2) и небазисным переменным (s х2) в точке В. Скажем, что в точкеА переменная xt вводится в базисное решение, а переменная s, - исключается из базисного решения. В соответствии с терминологиейсимплекс-метода выбранная небазисная (нулевая) переменная называется вводимой (в базисное решение), а удаляемая (из базисного решения) базисная переменная- исключаемой. В точке В вводимой и исключаемой переменными будут соответственно переменные х2 и s2. Процесс изменения состояний переменных заканчивается в точке С, поскольку найдено оптимальное решение.

УПРАЖНЕНИЯ 3.3.1

1. На рис. 3.4 показана схема изменения базисных и небазисных переменных в соответствии с путем А-> В -> С в пространстве решений, представленном на рис. 3.3. Создайте аналогичную схему для пути А-> D -> С.

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

a) А->В->С.

b) А-> F -> Е -> D -> С.

Точка А

Точка В

Точка С

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

(*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.

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