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

Шаг 1. Задана исходная базисная точка :

Вычислить оценки по формуле

Шаг 2. Проверить, если все Δ _j ≥0, то перейти к шагу 8.

Шаг 3. Проверить, если  то перейти к шагу 10.

Шаг 4. Выбрать k: Δ _k <0 и вектор A_k имеет хотя бы одну строго

положительную координату (возможен произвольный выбор такого номера k, например, ) 

Шаг 5. Вычислить параметр Θ по формуле

Шаг 6. Осуществить переход к новой базисной точке с помощью метода Жордана-Гаусса с направляющим элементом a _{l k}.

Шаг 7. Изменить исходную информацию:

Перейти к шагу 1.

Шаг 8. Если существует номер  ,то выписать ответ:  - оптимальная точка, в задаче имеется бесчисленное множество решений.

Шаг 9. Если для всех , то выписать ответ:  - единственное решение задачи.

Шаг 10. Выписать ответ: задача решений не имеет из-за неограниченности целевой функции на допустимом множестве:

Пример 1. Решить задачу

Решение. Оформим решение задачи в виде таблицы. В первом столбце поместим текущие базисные переменные, во втором - их коэффициенты в целевой функции, в третьем - базисные координаты текущей точки . Далее переписываем элементы матрицы  помещая над каждым столбцом коэффициент соответствующей переменной в целевой функции. Последний столбец предназначается для определения значения Θ. В отдельной строке вычисляются оценки векторов A_j. В ячейке, находящейся на пересечении оценочной строки и столбца , помещаем значение целевой функции в текущей базисной точке.

 

B	CB		2	-1	3	-2	1	Θ
			A1	A2	A3	A4	A5
x3	3	1	-1	1	1	0	0	―
x4	-2	1	1	-1	0	1	0	1
x5	1	2	1	1	0	0	1	2
		3	-6	7	0	0	0
x3	3	2	0	0	1	1	0
x1	2	1	1	-1	0	1	0
x5	1	1	0	2	0	-1	1
		9	0	1	0	6	0

 

Поскольку на первой итерации Δ₁ <0, в базис вводится вектор A₁. , т.е. в качестве направляющего элемента выбирается . Так как на второй итерации все Δ _j ≥0, то останов, получена оптимальная точка . Поскольку на небазисных векторах , то решение в задаче единственно.

 

Пример 2.  Решить задачу

Решение.

B	CB		2	-1	1	3	-2	1	Θ
			A1	A2	A3	A4	A5	A6
x4	3	1	-1	1	-1	1	0	0	―
x5	-2	1	1	-1	0	0	1	0	1
x6	1	2	1	-3	1	0	0	1	2
		3	-6	3	-3	0	0	0
x4	3	2	0	0	-1	1	1	0
x1	2	1	1	-1	0	0	1	0
x6	1	1	0	-2	1	0	-1	1
		9	0	-3	-3	0	6	0

 

На второй итерации получаем, что оценка Δ₂ <0, но в столбце A₂ нет положительных элементов. Это означает, что целевая функция не ограничена на допустимом множестве, т.е. .

Задачи для самостоятельного решения

 

1. Решить симплекс- методом задачу ЛП, предварительно приведя ее к каноническому виду.

;

	а	в	с		а	в	с		а	в	с		а	в	с
1	2	3	-1	6	5	2	3	11	2	1	2	16	3	3	1
2	3	1	1	7	4	3	6	12	3	3	4	17	4	1	2
3	4	2	-1	8	6	1	5	13	5	2	-1	18	3	1	0
4	7	2	3	9	2	2	2	14	7	1	5	19	4	1	3
5	8	3	4	10	5	3	7	15	6	3	8	20	5	2	6

2. Проверить, является ли точка  решением задачи ЛП:

3. Используя теорию симплекс- метода, найти все значения к, при которых точка  является решением задачи

;

 

Метод искусственного базиса и M-метод решения