Алгоритм табличного симплекс-метода

↑

▷ Содержание

⇐ ПредыдущаяСтр 8 из 27Следующая ⇒

Алгоритм симплекс-метода сводится к следующему:

1. Выбираются k=n-m свободных переменных.

2. Базисные переменные и целевая функция выражаются через свободные в виде (3.18) и (3.19).

3. определяется опорное решение задачи ЛП, для чего все свободные переменные полагаются равными нулю. Если все свободные члены b _{k +i} положительны, то полученное решение будет допустимым.

4. Допустимое решение проверяется на оптимальность. Если все коэффициенты r _j в (3.19) отрицательны, то полученное допустимое решение является оптимальным.

5. Пусть коэффициент r_j (3.19) имеет положительное значение. Среди коэффициентов n _k+i,j (i =1, m; j =1, k) ищутся такие, которые имеют одинаковый знак со свободными членами b _{k +i}. Для всех таких коэффициентов находятся отношения и определяется минимальное из них, т.е.

(3.20)

Переменная x=k+i, для которой выполняется условие (3.20) переводится в состав свободных, а переменная x_j, у которой коэффициент r _j в (3.19) положителен - в состав базисных.

Далее выполняются п.п.2-5 до тех пор, пока не будет найдено оптимальное решение. Таким образом, признак допустимости решения один (все b _{k +i} положительны), а признаков оптимальности решения два:

- все b _k+i положительны, i = i,m;

- все r _j отрицательны, j = i,k. Далее, для того, чтобы L (x) достигала максимума необходимо, чтобы в (3.19) значения всех коэффициентов при переменных были отрицательными. В том случае, если хотя бы один из коэффициентов, например, r _j, положителен, то эта переменная (т.е. x_j) должна быть переведена из свободных в базисные, а одна из базисных должна быть переведена в свободные.

Исходными данными при заполнении первой симплекс-таблицы служат свободные члены и коэффициенты при переменных в выражениях (3.18) и (3.19). Симплекс-таблица содержит m +1 строк и k +1 столбцов. В первой строке записываются коэффициенты, содержащиеся в выражении (3.19) для целевой функции L (x).

Остальные строки служат для записи соответствующих коэффициентов в выражениях для базисных переменных (3.18). Первый столбец симплекс-таблицы содержит свободные члены выражений (3.18) и (3.19), а остальные столбцы - коэффициенты при свободных переменных. На основании (3.18) и (3.19) заполним первую (исходную) симплекс-таблицу.

Таблица 3.2

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

Для проверки этого решения на оптимальность обратимся к элементам первой строки симплекс-таблицы. Если все элементы этой строки (за исключением свободного члена g₀) отрицательны, то полученное решение оптимально. В том случае, когда один или несколько элементов в первой строке положительны, решение не оптимально и его можно улучшить.

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

1. Среди положительных элементов первой строки симплекс-таблицы выбирается тот, который имеет наибольшее значение. Пусть это будет r₁ при x ₁. Это значит, что переменная x₁ должна быть переведена из свободных в базисные. Столбец, в котором находится наибольший положительный коэффициент, назовем разрешающим столбцом.

2. В разрешающем столбце определяются те элементы, которые имеют одинаковый знак с соответствующими свободными членами.

Пусть это будут коэффициенты n _{k +1,1} и n _{k +2,1}.

3. Рассчитываются отношения соответствующих свободных членов к коэффициентам n _{k +1,1} и n _{k +2,1}.

Пусть выполняется следующее неравенство:

(3.21)

Тогда строку, соответствующую переменной x_{k +1}, для которой выполняется неравенство (8), назовем разрешающей строкой. Элемент n _{k +1,1} лежащий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. Базисная переменная x_{k +1} должна быть переведена в состав свободных переменных.

4. Строится новая симплекс-таблица для новой системы свободных (x_{k +1}, x ₂,..., x_k) и базисных (x ₁, x_{k +2},..., x_k+m) переменных.

Элементы новой симплекс-таблицы заполняются следующим образом.

5. Вычисляется обратная величина 1/ν _{k +1,1} разрешающего элемента исходной таблицы и это значение записывается в соответствующей клетке новой симплекс-таблицы.

6. Все элементы разрешающего столбца исходной симплекс-таблицы делятся на разрешающий элемент. Полученные значения с обратным знаком записываются в соответствующих клетках новой симплекс-таблицы.

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

8. Остальные элементы новой симплекс-таблицы рассчитываются в соответствии с правилом прямоугольника, которое состоит в следующем.

Пусть необходимо рассчитать значение элемента новой симплекс-таблицы стоящего на пересечении i строки и j -го столбца, т.е. n’ _ij. Составим из элементов исходной симплекс-таблицы прямоугольную матрицу 2x2.

где n _lk - разрешающий элемент. l – разрешающая строка, k – разрешающий столбец.

Тогда

(3.22)

В общем виде новая симплекс-таблица представлена таблицей 3.3.

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

Таблица 3.3

СП БП	СЧ	xk+1	x2	…	xk
L(x)				…
x1				…
xk+2				…
…	…	…	…	…	…
xk+m				…

Перечислим без доказательства некоторые правила анализа симплекс-таблиц:

1. Если в конечной симплекс-таблице элементы первого столбца положительны, а элементы первой строки (кроме свободного члена g₀) - отрицательны, задача линейного программирования имеет единственное оптимальное решение.

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

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

Разработанный симплекс-метод имеет достаточно много лишних вычислений, не несущих информации. С целью сокращения машинного времени решения задачи был разработан модифицированный метод (Данцин, 1953 г.). По идее он близок к табличному симплекс-методу, но обладает тем преимуществом, что вычисляет действительно нужные величины. При этом количество вычислений напрямую связано с количеством ограничений, а не с количеством переменных, которых значительно больше. Недостатком МСМ следует считать большую потребность в машинной памяти.

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология