9.1.1. Пример алгоритма ВСМ-СН
Допустим, мы должны решить задачу
При
Следует обратить внимание на то, что вместо максимизации мы должны минимизировать; значит, при вычислении оценок нужно вместо
пользоваться
Кроме того, целевая функция не является выпуклой.
После добавления двух дополнительных переменных
Предположим, что процедура фазы 1 дает
и соответствующую таблицу:
Здесь
входят в базис.
Обратите внимание на то, что
допустима для первоначальной задачи.
Шаг 0. Увеличиваем
от 0 на 1. (Для упрощения обозначений знаки транспонирования над векторами будут опущены.) Положим
Теперь применим выпуклый симплексный метод:
Так как
увеличиваем
Используя то, что
для всех небазисных переменных, за исключением
для всех базисных переменных, мы приходим к тому, что
.
Для получения
вычисляем
Но
, решая, получаем
Поэтому
и
Мы можем выбрать
в качестве базисных, и таблица останется такой, какой была.
Благодаря тому, что
имеем
Поэтому переходим к шагу I.
Шаг 1.
а. С помощью
и таблицы
шаг выпуклого симплексного метода дает
Преобразовывать таблицу опять не требуется.
б. Вследствие
Теперь вычисляем
Здесь мы пользуемся упр. 2.
Таким образом, для получения
вычисляем
Тогда
Поэтому
Кроме того,
, продолжая, переходим к (в).
Вычисляя, получаем
Далее
, продолжая, переходим к (г).
Переход к шагу 1 с
Шаг 1.
входят в базис. Поэтому соответствующая таблица имеет вид
где
Расширяющий шаг показывает, что
является решением со значением целевой функции
Иллюстрация шага 2. В предыдущем примере в целях сохранения ясности и краткости шаг 2 не был иллюстрирован. Теперь допустим, что в предыдущем примере на некоторой итерации мы пришли к шагу 2. Предположим, что
а переменное
и таблица
имеют вид
Здесь
Тогда