Симплексный метод решения ЗЛП»

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

Для использования симплексного метода ЗЛП должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.

Оптимизационные исследования ЗЛП удобно проводить, пользуясь симплекс-таблицами. Существует достаточно большое количество форм симплекс-таблиц. Воспользуемся одной из форм, по которой рекомендуется следующий порядок решения ЗЛП:

1. Математическая модель задачи приводится к канонической форме с помощью дополнительных неотрицательных переменных.

2. Определяется начальное базисное допустимое решение. Для этого переменные разбивают на две группы – основные (базисные) и неосновные. В качестве основных переменных следует выбрать (если возможно) переменные, каждая из которых входит только в одно из уравнений системы ограничений. Дополнительные переменные удовлетворяют этому правилу.

3. Составляется исходная симплекс-таблица (таблица 1), в которую записывают параметры, соответствующие начальному базисному допустимому решению:

3.1. Весовые коэффициенты c_j при переменных x_j (j = 1,...,n) целевой функции (строка C).

3.2. Весовые коэффициенты c_i при базисных переменных x_i (i = 1,...,m) целевой функции (столбец C _b).

3.3. Переменные x_i (i = 1, ... ,m) , которые входят в текущий базис (столбец A_b ).

3.4. Свободные коэффициенты b_i (i =1, ... ,m) уравнений ограничений (столбец B). В этом же столбце находим оптимальный план задачи.

3.5. Элементы a _ij (i = 1, ... ,m ; j = 1, ... ,n) матрицы условий задачи (столбцы A₁, .., A_n ).

Таблица 1

3.6. Оценки S_j (j=1, ... ,n) векторов условий A_j , которые определяются по формуле:

где c_i - весовые коэффициенты при базисных переменных.

Из этой формулы следует, что коэффициенты z_j вычисляются для каждого столбца как сумма почленных произведений коэффициентов c_i на одноименные коэффициенты j-го столбца. При заполнении симплекс-таблицы при условии, что рассматривается задача максимизации целевой функции, необходимо иметь в виду:

• если S_j ³ 0 для всех j = 1, ..., n, то полученное решение является оптимальным;

• если имеются S_j < 0и в столбцах A_j, соответствующих этим отрицательным оценкам, существует хотя бы один элемент a_ij > 0, то возможен переход к новому решению, связанному с большим значением целевой функции;

• Из отрицательных оценок выбирают ту, у которой значение по абсолютной величине больше. Если имеется несколько одинаковых отрицательных оценок, то выбирают ту, которой соответствует максимальный коэффициент целевой функции c_i.

• если имеются S_k<0 и в столбце A_k все элементы a_ik £ 0, то в области допустимых решений целевая функция не ограничена сверху.

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

5. Определяется вектор, который нужно вывести из базиса, используя равенство:

Это условие позволяет найти направляющую строку. Переменная x_r, соответствующая этой строке, выводится из базисного решения и заменяется переменной x_k направляющего столбца. Элемент a_rk, который стоит на пересечении направляющего столбца и направляющей строки, называется разрешающим элементом.

6. Заполняется таблица соответствующая новому базисному решению. В этой таблице, прежде всего заполняются клетки строки r с вводимой переменной x_k. Для этого все элементы этой строки делятся на направляющий элемент. Получаются элементы новой строки:

b_r/a_rk, a_r1/a_rk , ... , a_rn/a_rk.

Остальные элементы новой таблицы определяются по правилу прямоугольника:

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

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