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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

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

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

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

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

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

(3.20)

Переменная x=k+i, для которой выполняется условие (3.20) переводится в состав свободных, а переменная xj, у которой коэффициент 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, положителен, то эта переменная (т.е. xj) должна быть переведена из свободных в базисные, а одна из базисных должна быть переведена в свободные.

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

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

Таблица 3.2

СП БП СЧ x 1 x 2 xj xk
L (x) g0 r1 r2 rj rk
xk +1 bk+1 nk+1,1 nk+1,2 nk+1,j nk+1,k
xk +2 bk+2 nk+2,1 nk+2,2 nk+2,j nk+2,k
xk+i bk+i nk+i,1 nk+i,2 nk+i,j nk+i,k
xk+m bk+m nk+m,1 nk+m,2 nk+m,j nk+m,k

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

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

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

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

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

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

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

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

(3.21)

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

4. Строится новая симплекс-таблица для новой системы свободных (xk +1, x 2,..., xk) и базисных (x 1, xk +2,..., xk+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. Если в конечной симплекс-таблице элементы первого столбца положительны, а элементы первой строки (кроме свободного члена g0) - отрицательны, задача линейного программирования имеет единственное оптимальное решение.

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

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

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

 



Поделиться:


Последнее изменение этой страницы: 2017-02-08; просмотров: 490; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.230.35.103 (0.015 с.)