Реферат: Решение задачи линейного программирования симплекс-методом

(1)

(2)

(3)

(4)

При составлении симплекс-таблицы придерживаются следующих правил:

в крайнем левом столбце располагаются базисные переменные и ;

в крайнем правом столбце располагаются правые части ограничений;

в первой строке располагаются переменные в определённом порядке:

сначала , потом небазисные переменные, базисные переменные располагаются в последних столбцах перед правой частью (ПЧ). Запишем коэффициенты в СТ(0):

						ПЧ
	1	-	-	0	0	0	0
	0			1	0	0
	0			0	1	0
	0			0	0	1

Оптимальность любой из вершин определяется коэффициентами при небазисных переменных в – строке текущей симплекс-таблицы:

Для задачи максимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в – строке являются неотрицательными (>0);

Для задачи минимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в – строке являются неположительными (< 0).

Если в задаче максимизации (минимизации) у одной небазисной переменной в – строке коэффициент <0(>0), то текущая точка не является оптимальной и необходимо изменить базис. Для этого выбирают небазисную переменную, имеющую максимально отрицательный (положительный) коэффициент в – строке. Выбранная небазисная переменная будет включаться в новый базис, поэтому называется включаемой переменной. Базисная переменная, которая будет выведена из базиса, называется исключаемой переменной.

Исключаемой переменой будет та базисная переменная, которая первой обратится в "0" при переходе в смежную вершину после ввода включаемой переменной.

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

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

Пересечение разрешающего столбца и строки определяют разрешающий элемент (РЭ).

Чтобы определить исключаемую переменную необходимо:

разделить правые части всех базисных переменных (кроме - строки) на соответствующие положительные коэффициенты разрешающего столбца;

выбрать из полученных отношений наименьшее.

Делить на "0" и отрицательную величину нельзя, т. к. это приводит к отсутствию пересекающейся вершины или к вершине вне ОДР.

Для перехода в смежную вершину необходимо сформировать матрицу перехода B(0), которая определит связь между СТ(0) и СТ(1): СТ(1) = В(0) СТ(0).

Для произвольной квадратной матрице размерности n, имеющей в качестве (n - 1) столбца единичные орты, расположенные в соответствии с единичными ортами единичной матрицы, и одного произвольного столбца с ненулевым элементом на главной диагонали, обратная матрица находится по следующему правилу:

Каждый элемент j – столбца делится на РЭ и меняет знак на противоположный, кроме разрешающего элемента.

Искусственный начальный базис. М – метод.

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

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

Переменные R определяют начальный допустимый базис с точки зрения возможного дальнейшего перехода в одну из вершин ОДР. За использование искусственных переменных в целевой функции вводится штраф М. В задаче максимизации М отрицательное (М<<0), в задаче минимизации М положительное (М>>0).