9.1.1. Пример алгоритма ВСМ-СН

Допустим, мы должны решить задачу

При

Следует обратить внимание на то, что вместо максимизации мы должны минимизировать; значит, при вычислении оценок нужно вместо пользоваться Кроме того, целевая функция не является выпуклой.

После добавления двух дополнительных переменных

Предположим, что процедура фазы 1 дает и соответствующую таблицу:

Здесь входят в базис.

Обратите внимание на то, что допустима для первоначальной задачи.

Шаг 0. Увеличиваем от 0 на 1. (Для упрощения обозначений знаки транспонирования над векторами будут опущены.) Положим

Теперь применим выпуклый симплексный метод:

Так как увеличиваем

Используя то, что для всех небазисных переменных, за исключением для всех базисных переменных, мы приходим к тому, что .

Для получения вычисляем

Но , решая, получаем Поэтому

и

Мы можем выбрать в качестве базисных, и таблица останется такой, какой была.

Благодаря тому, что имеем

Поэтому переходим к шагу I.

Шаг 1.

а. С помощью и таблицы шаг выпуклого симплексного метода дает Преобразовывать таблицу опять не требуется.

б. Вследствие

Теперь вычисляем Здесь мы пользуемся упр. 2.

Таким образом, для получения вычисляем

Тогда

Поэтому

Кроме того, , продолжая, переходим к (в).

Вычисляя, получаем

Далее , продолжая, переходим к (г).

Переход к шагу 1 с

Шаг 1.

входят в базис. Поэтому соответствующая таблица имеет вид

где

Расширяющий шаг показывает, что является решением со значением целевой функции

Иллюстрация шага 2. В предыдущем примере в целях сохранения ясности и краткости шаг 2 не был иллюстрирован. Теперь допустим, что в предыдущем примере на некоторой итерации мы пришли к шагу 2. Предположим, что а переменное и таблица имеют вид

Здесь Тогда

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

Ясно, что и отсюда Тогда увеличивается до 3. Так же Тогда переходим к Но Поэтому уменьшаем Процесс уменьшения аналогичен случаю в выпуклом симплексном методе. Используя обозначения случая находим

Кроме того,

получаем, определяя

Тогда . Полагаем . В преобразовании таблицы нет необходимости, и

Нетрудно видеть, что Полагаем Тогда от шага 2а возвращаемся к шагу 0 и продолжаем, как было описано ранее.