Программирования.

 

Постановка задачи линейного программирования в общей форме имеет вид:

(з)

Здесь – заданные величины, – неизвестные переменные.

Задачей линейного программирования в канонической форме называется следующая задача:

. (з_к)

Здесь – неизвестная переменная, и – заданные векторы, – заданная матрица размера со столбцами .

Задачей линейного программирования в нормальной форме называется следующая задача:

. (з_н)

Задачи линейного программирования в различных формах можно свести друг к другу путем введения дополнительных координат, изменения матрицы , изменения знака целевой функции . Например, задача (з_н) сводится к задаче (з_к) путем введения дополнительных координат :

,

где – единичная матрица размера .

Более подробно рассмотрим задачу линейного программирования в канонической форме. Множество допустимых точек задачи (з_к) имеет вид:

и представляет собой выпуклый многогранник в пространстве .

Определение. Точка выпуклого множества называется крайней (угловой), если не существует точек и числа таких, что . ▲

У многогранников крайними точками являются вершины. Поэтому, если существует экстремум линейной функции, то он достигается в крайней точке выпуклого многогранника. Число крайних точек множества , задаваемого в виде конечного числа линейных равенств и неравенств, конечно. Таким образом, для решения задачи линейного программирования (если оно существует) достаточно перебрать значение целевой функции во всех крайних точках множества . Но нахождение всех этих крайних точек и перебор значений целевой функции в них – операция довольно трудоемкая.

Симплекс‑метод решения задачи линейного программирования позволяет, начиная с некоторой исходной точки, переходить к другой по направлению наибольшего возрастания функции .

Определение. Задача (з_к) называется невырожденной, если любая крайняя точка множества содержит ровно положительных координат. ▲

Пусть – крайняя точка в невырожденной задаче (з_к). Вектор можно представить в виде , где – базисный вектор, – небазисный вектор. Аналогично, матрицу можно представить в виде , где – матрица, состоящая из первых столбцов матрицы .

Столбцы матрицы линейно независимы, т.е. матрица является невырожденной. Действительно, допустим противное, что столбцы линейно зависимы. Тогда существует ненулевой набор множителей такой, что . Значит для вектора . Поэтому точка при малых как больших нуля, так и меньших нуля. Это означает, что точка не является крайней. Получили противоречие.

 

Правило решения задач по симплекс‑методу.

1) Привести задачу к канонической форме.

2) Найти крайнюю точку , .

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

В первой строке, начиная с 4‑го столбца, располагаются элементы .

Во второй строке, начиная с 3‑его столбца – векторы . Под ними – разложения этих векторов по базису .

а) Так как , то . Это означает, что разложением вектора по базису является вектор .

б) Предположим, что векторы имеют следующее разложение по базису :

,

где – столбец коэффициентов разложения вектора по базису . Тогда .

Для разложения векторов тривиальны: , следовательно, вектор‑столбец представляет собой единичный вектор. При неизвестные вектор-столбцы отыскиваются с помощью обратной матрицы.

в) В предпоследней строке под вектором выписывается – значение целевой функции в крайней точке. Под векторами в предпоследнюю строку записываются значения . Очевидно, что при .

г) В последнюю строку, начиная с 4‑го столбца, заносится разность между элементами предпоследней строки и элементами первой строки:

.

 

				…			…		…
базис				…			…		…
				…			…		…
…	…	…	…	…	…	…	…	…	…	…	…
				…			…		…
…	…	…	…	…	…	…	…	…	…	…	…
				…			…		…
				…			…		…
				…			…		…

 

4) Исследовать симплексную таблицу.

а) Если , то крайняя точка является решением задачи, .

б) Если для некоторого имеют место неравенстваи , то .

в) Пусть в строке имеются отрицательные числа, а соответствующие столбцы содержат положительные числа и . Тогда столбец индексом является разрешающим. Введем обозначение: . Эти значения ставим соответственно в последнем столбце таблицы. Пусть . Тогда строка с номером является разрешающей, а разрешающим элементом симплексной таблицы является элемент .

Далее необходимо из числа базисных векторов исключить вектор , и вместо него взять вектор . Значение целевой функции при этом возрастает на величину .

5) Построить новую симплексную таблицу для базиса , т.е. векторы разложить по новому базису.

Элементы таблицы , не лежащие в разрешающем столбце и разрешающей строке, вычисляются по правилу прямоугольника:

.

Элементы разрешающей строки делятся на разрешающий элемент:

.

Далее перейти к исследованию новой симплексной таблице, т.е. к пункту 4).

Симплекс‑метод позволяет решать точно также и вырожденные задачи линейного программирования. Число положительных координат крайней точки в таких задачах меньше , но число базисных векторов всегда равняется рангу матрицы . Перейти от вырожденной задачи к невырожденной можно путем сколь угодно малого изменения начальных данных задачи. В вырожденных задачах возможны холостые шаги симплекс‑метода, т.е. шаги, в результате которых значение целевой функции не изменяется. При этом теоретически возможно и зацикливание, т.е. бесконечное повторение холостых шагов. Для того чтобы избежать зацикливания, разработаны специальные алгоритмы – антициклины (см., например, Ф.П. Васильев «Методы оптимизации». М.: Факториал Пресс, 2002). На практике зацикливание происходит крайне редко, поэтому в данном курсе антициклины не рассматриваются.

 

Пример 1. Решить задачу линейного программирования в канонической форме с заданной начальной крайней точкой , используя симплекс‑метод:

;

,

,

.

Решение: Данная задача задана в канонической форме, также задана начальная крайняя точка. Построим симплексную таблицу. Матрица системы ограничений имеет вид:

.

Базисная матрица задачи состоит из третьего и четвертого столбцов матрицы , соответствующих положительным координатам начальной крайней точки:

.

Так как базисная матрица в данной задаче является единичной, то , .

Построим и заполним симплексную таблицу:

 

			-1		-1	-1
базис
	-1		-1
	-1
		-6		-2	-1	-1
				-4

 

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

 

			-1		-1	-1
базис
			-1
	-1				-1
			-4			-1
			-3

 

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

 

			-1		-1	-1
базис
	-1
			-1

 

Так как , то точка является решением задачи и . ●

 

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

;

,

,

,

.

Матрица системы ограничений и базисная матрица имеют вид:

, .

Найдем матрицу, обратную к , например, методом присоединенной матрицы. Для этого найдем определитель матрицы и алгебраические дополнения элементов этой матрицы:

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

.

Тогда обратная матрица к имеет вид:

.

Далее находим разложения векторов по базису :

.

Разложением вектора является вектор ненулевых координат крайней точки. Составим симплексную таблицу:

 

базис

 

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

 

базис

 

Последняя строка новой таблицы содержит один отрицательный элемент, соответствующий вектору . В соответствующем столбце только одно число является положительным. Это число соответствует вектору . На следующем этапе из числа базисных векторов исключаем вектор и вводим вместо него вектор . Строим новую симплексную таблицу:

 

базис

 

Так как , то точка является решением задачи и . ●