Реализация симплекс-метода в виде симплексных таблиц

Для реализации алгоритма симплекс-метода при подсчетах удобно использовать симплексные таблицы.

Для применения симплексных таблиц требуется найти начальный базисный план и преобразованиями системы ограничений добиться выполнения условия А_Б=Е. После этого можно заполнять начальную таблицу следующего вида.

Таблица 1.3.1

Правила составления симплекс-таблицы:

-вторая строка таблицы состоит из заголовков, которые обозначают, какую именно информацию будут содержать находящиеся ниже столбцы:

Б – перечень номеров базисных переменных; с_Б – коэффициенты целевой функции, соответствующие базисным переменным; 0 – вектор b, 1, …, n – номера столбцов матрицы ограничений.

-Каждая базисная переменная Б_i задает единственное уравнение-ограничение, в которое она входит. Это позволяет при помощи базисных переменных нумеровать координаты векторов, например, a(j,Б_i) – коэффициент перед j-й переменной в уравнении, содержащем базисную переменную с номером Б_i.

-в первой строке над столбцами 1, …, n записываются коэффициенты целевой функции, соответствующие всем переменным;

-в последней строке под столбцами 1, …, n вычисляются координаты вектора Δ (для базисных переменных – нули), под столбцом 0 – вычисляется значение целевой функции при выбранном плане.

Заметим, что поскольку в ходе решения мы имеем дело с базисными планами, и при этом А_Б = Е, то х_Б = А_Б^-1b = b, т.е. в столбце 0 будут содержаться значения базисных координат текущего плана. Остальные (небазисные) координаты плана, как и раньше, равны нулю.

Симплексная таблица представляет собой удобное средство для проведения всех вычислений симплекс-метода.

1) Для вычисления координат вектора Δ необходимо сначала найти скалярное произведение векторов с_Б и j-го столбца, а затем полученный результат вычесть из с_j (его значение находится над столбцом j). Нетрудно увидеть, что для базисных переменных результат всегда будет равен нулю.

2) Скалярное произведение вектора с_Б и столбца 0 дает значение целевой функции для найденного базисного плана.

3) Если компонента Δ_J>0, то J-ю переменную нужно ввести в базис. Согласно алгоритма симплекс-метода, чтобы найти переменную, выводимую из базиса, нужно координаты вектора b (столбец 0) разделить на соответствующие координаты столбца J (только для положительных координат столбца J) и среди всех этих отношений выбрать минимум. Выводимая из базиса переменная Б_I содержится в строке, которая дает минимальное отношение.

Для проведения дальнейших расчетов выделяем строку Б_I и столбец J.

Таблица 1.3.2

4) Заменим в базисе переменную Б_I на переменную J. Чтобы подготовить данные для заполнения новой симплексной таблицы, необходимо в системе ограничений вместо переменной Б_I выразить переменную J.

Для этого совершим два действия:

1.В уравнении Б_I коэффициент перед переменной J сделаем равным 1;

2.Из остальных уравнений переменную J исключим.

В результате для обновленного базиса опять выполняется условие А_Б=Е.

Другими словами, описанные действия означают:

1. В строке Б_I все коэффициенты столбцов 0,…,n делим на a(J,Б_i) и записываем в такую же строку новой таблицы. При этом в столбце Б помечаем, что данная строка уже соответствует базисной переменной J. Во второй столбец заносим соответствующий коэффициент целевой функции для этой переменной. В остальных строках содержимое первых двух столбцов не изменяется.

2. Чтобы получить новое содержание столбцов 0,…,n для оставшихся строк, например, для Б_k, нужно взять предыдущее значение коэффициента a(J, Б_k), домножить на него вектор, полученный в п.1. для строки J, и вычесть получившийся вектор значений из предыдущих значений 0,…,n.

Вычислительные формулы:

Пусть a(i, Б_j) – коэффициенты предыдущей таблицы, a*(i, Б_j) – коэффициенты для нового базиса, переменная Б_I выводится из базиса, J - вводится. Тогда

1. a*(j, J) = a(j, Б_I) / a(J, Б_I);

2. При Б_k≠J: a*(j, Б_k) = a(j, Б_k) – a(J, Б_k) a*(j, J).

Остается вычислить новый вектор Δ и повторить итерацию симплекс-метода.

Поиск по сайту: