Алгоритм решения общей задачи линейного программирования

Шаг 1. Привести задачу к каноническому виду.

Шаг 2. Проверить наличие единичного базиса среди столбцов матрицы ограничений. Если единичный базис имеется, то перейти к шагу 5.

Шаг 3. Ввести в задачу искусственные переменные так, чтобы среди столбцов полученной матрицы появился единичный базис в пространстве R^m, где m - число ограничений задачи.

Шаг 4. Составить М - задачу: ввести искусственные переменные в целевую функцию с коэффициентами, равными - М.

Шаг 5. Составить исходную таблицу для оформления решения задачи. Если данный пункт выполняется после шага 2, то фрагмент таблицы завершается одной оценочной строкой, если после шага 4, то двумя строками для оценок  (первая - для чисел , вторая - для ).

Шаг 6. Вычислить оценки всех векторов-ограничений задачи по формулам  При наличии искусственных векторов в базисе получим выражения вида . Поместить   в первую оценочную строку,  - во вторую (нижнюю).

Шаг 7. При наличии двух оценочных строк проверить, если все 0, то перейти к шагу 11, иначе - к шагу 9 с числами . Если осталась одна оценочная строка, то проверить условие . Если это условие выполняется, то перейти к шагу 12.

Шаг 8. Просмотреть векторы-столбцы A_j, для которых <0. Если среди них существует такой, что все его координаты a_ij  0, то перейти к шагу 13, иначе - к шагу 9 с числами .

Шаг 9. Определить направляющий элемент для выполнения итерации по методуЖордана-Гаусса. Номер столбца k может быть выбран любым среди тех j, для которых < 0. Номер строки l определяется следующим образом:

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

Шаг 10. Перейти к новой базисной точке. Осуществить преобразования Жордана - Гаусса с направляющим элементом a_lk. Выбросить из рассмотрения искусственный вектор, если он на данной итерации стал небазисным. Перейти к шагу 6.

Шаг 11. Проанализировать значение целевой функции в данной базисной точке . Если , то проверить наличие искусственных векторов в базисе. Если искусственных векторов в базисе нет, то вычеркнуть вторую оценочную строку и перейти к выполнению шага 7. Если искусственные переменные имеются среди базисных (они при этом равны нулю), то проверить неравенство  для тех номеров , для которых .Если неравенства выполняются, то получено решение задачи. Перейти к шагу 15. Если среди , таких что  существуют такие, что , то перейти к шагу 8, где проверке будут подвергаться только те векторы , для которых , . Если в выражении   имеет место неравенство , то перейти к шагу 14.

Шаг 12. Проверка единственности решения.                                                         Если среди небазисных векторов есть такие, что = 0, то в задаче имеется бесчисленное множество решений. Исключение составляет случай, когда была сделана замена переменных x_s=x_s'-x_s''. В этом случае, если одна из переменных x_s' или x_s'' является базисной, то оценка второй обязательно равна нулю. Этот факт означает бесчисленное множество пар, с помощью которых может быть получено значение переменной x_{s .} Если среди небазисных векторов, кроме тех, о которых сказано выше, нет таких, которые имеют нулевые оценки, то в задаче существует единственное решение. Если имеет место случай, когда для всех небазисных векторов ³ 0, то задача имеет единственное решение. Перейти к шагу 15.

Шаг 13. Останов. Задача не имеет решения из-за неограниченности целевой функции на допустимом множестве. Перейти к шагу 15.

Шаг 14. Останов. Задача не имеет решения из-за пустоты исходного допустимого множества.

Шаг 15. Выписать ответ.

 

Пример 1. Решить ЗЛП.

Решение.

Так как в задаче нет начального базиса, составим М-задачу.

 

Запишем данные в таблицу.

 

B	CB		3	0	7	-1	-M	-M	-M	Θ
			A1	A2	A3	A4	z1	z2	z3
z1	-M	4	1	1	2	1	1	0	0	4
z2	-M	5	1	-2	3	0	0	1	0	5
z3	-M	13	3	0	7	2	0	0	1	4
α		0	-3	0	-7	1	0	0	0
β		-21	-5	1	-12	-3	0	0	0
x1	3	4	1	1	2	1		0	0	2
z2	-M	1	0	-3	1	-1		1	0	1
z3	-M	1	0	-3	1	-1		0	1	1
α		12	0	3	-1	4		0	0
β		-2	0	6	-2	2		0	0
x1	3	2	1	7	0	3			0
x3	7	1	0	-3	1	-1			0
z3	-M	0	0	0	0	0			1
α		13	0	0	0	3			0

 

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

Так как все Δ _j = α _j ≥ 0, то останов, найдена оптимальная точка . . Поскольку на небазисном векторе оценка , то в задаче имеется бесчисленное множество решений.

 

Пример 2. Решить ЗЛП.

2

                                        

                                             

Решение.

Так как в задаче присутствует только один базисный вектор A₃, составим М-задачу, добавив искусственные переменные в 1 и 2 ограничение.

 

2

                                             

.

Запишем данные в таблицу.

 

B	CB		1	0	3	-1	-M	-M	Θ
			A1	A2	A3	A4	z1	z2
z1	-M	9	2	4	0	-1	1	0	9/4
z2	-M	3	-3	2	0	3	0	1	3/2
x3	3	4	1	5	1	2	0	0	4/5
α		12	2	15	0	7	0	0
β		-12	1	-6	0	-2	0	0
z1	-M	4	1	0	2	1	1	0
z2	-M	7/5	-17/5	0	-2/5	11/5	0	1
x2	0	4/5	1/5	1	1/5	2/5	0	0
α		0	-1	0	-3	1	0	0
β		-36/5	11/5	0	6/5	2/5	0	0

 

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

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

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

 

2. Решить М- методом задачу ЛП.

 

;

 

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

 

1. Определение двойственной задачи линейного программирования 2. Правило построения двойственных задач 3. Свойства пары двойственных задач 4. Первая и вторая теоремы двойственности 5. Интерпретация симплекс-метода в терминах двойственных задач 6. Примеры применения теории двойственности к решению задач

Глава 3