Симплексные преобразования

Если перспективная переменная должна заменить в базисе переменную , то необходимо найти ее значение из уравнения

.

Получаем, что

и подставляем это выражение в остальные уравнения исходной системы ограничений. Так, вместо уравнения

,

получим:

откуда

Аналогично, при подстановке в выражение для целевой функции

получим:

и окончательно

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

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

2. Элементы остальных строк разрешающего столбца обнуляются:

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

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

Рис. 2.11

Соответствующие формулы для новой симплексной таблицы получаются из вышеприведенных соотношений и имеют вид:

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

Но величина – это наименьшее симплексное отношение, равное значению переменной в новой симплексной таблице, следовательно

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

Date: 2016-07-25; view: 647; Нарушение авторских прав