Алгоритм перехода к следующей таблице

1) просматривается нулевая строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов) выбирается наибольшее по модулю отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

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

3) среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой;

4) в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных:

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

· строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.

· в новой таблице все элементы ключевого столбца = 0, кроме разрешающего, он всегда равен 1.

· столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

· строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.

· в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы.

Контрольные вопросы

1. Объясните, каким образом выбирается разрешающий столбец.

2. Объясните, каким образом выбирается разрешающая строка.

3. При выполнении каких условий следует остановить симплекс-метод?

4. Каким образом составляется нормальная форма задачи линейного программирования?

5. Какие переменные относятся к базовым, а какие к свободным?

Литература

1. Ильенкова С.Д. Производственный менеджмент [Текст]/ С.Д. Ильенкова – М.: ЮНИТИ-ДАНА, 2000.

2. Орлов И.А. Менеджмент [Текст]/ И.А. Орлов – М.: Изумруд, 2003.