Основная теорема линейного программирования (без доказательства). Основная идея симплекс-метода.

§ 2. Симплекс метод

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

Заметим, что число базисных решений хотя и конечно, однако может быть весьма большим, при больших размерах задачи. Поэтому если имеется некоторая базисная точка, то хотелось бы знать:

1.не является ли она оптимальной, и если это так, то просмотр остальных точек не целесообразен;

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

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

Чтобы ответить на эти вопросы, исследуем более подробно допустимое множество ЗЛП.

2.1. Общее решение ЗЛП.

Значение целевой функции на общем решении.

Имеется задача линейного программирования в канонической форме. Пусть матрица А имеет вид

.

В соответствии с разбиением матрицы на блоки произведем такое же разбиение векторов с и х

, .

запишем ЗЛП в виде

,

, ,

.

Тогда мы имеем базисное решение с значением целевой функции и общее решение

, (2.1.1)

здесь - базисные переменные, а - свободная переменная.

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

Будем называть

(2.1.2.)

оценкой вектора .

И, следовательно,

. (2.1.3)

Заметим, что оценки определены только для небазисных столбцов. Попробуем вычислить оценку небазисного вектора с помощью (2.1.2). Получим , где , но , где единица стоит на месте i. Тогда , то есть можно считать, что оценки определены для всех столбцов и для базисных они всегда равны нулю.

2.2. Основная теорема линейного программирования

Теорема: Пусть имеется базисное решение ЗЛП со значением целевой функции и для всех j найдены оценки . Тогда:

1. Если имеется для любых j, то базисное решение оптимально;

2. Если существует , то существует бесчисленное множество допустимых решений, для которых . При этом

2а. Если столбец , то задача неразрешима из-за неограниченности целевой функции;

2б. Если имеется , то существует новое базисное решение, значение целевой функции на котором больше, чем на исходном, то есть .

Замечание: Теорема справедлива, если базисное решение не вырождено, то есть .

Доказательство: 1. Пусть все . Чтобы доказать, что существующее решение оптимально нужно доказать, что для все выполнено .

Любое допустимое решение можно найти из формулы (2.1.1), подставив вместо какие-нибудь неотрицательные значения. Тогда обратимся к формуле (2.1.3) . Так как все , то при любом , где

.

2. Пусть . Возьмем в формуле (10) , где стоит на k-ом месте, при чем . Тогда значение базисных переменных примет вид: . Так как , то всегда найдется положительное такое, что . При этом получится новое частное решение ЗЛП:

,

стоит на k-ом месте.

Значение целевой функции на этом частном решении будет равно:

. (2.2.1)

Так как , а , то .

2а. Если , то для любого , тогда из (2.2.1) следует, что .

2б. Если существует , то не для любого . Выпишем неравенство

, (2.2.2)

где .

Если , то неравенство (2.2.2) для этого номера i выполняется при любом .

Если , то для этих i максимально возможное :

.

При этом , как следует из (2.2.1) .

Так как формула для определения , а также формула (2.2.2) совпадает с формулой перестроения базисного решения, то полученное новое решение является базисным.

На основе этой теоремы строится метод решения ЗЛП называемый симплекс-методом, который фактически является методом перестроения базисного решения с учетом оценок небазисных столбцов.

2.3. Алгоритм симплекс метода

Пусть имеется базисное решение со значением целевой функции .

Шаг 1: Вычислить оценки по формуле

при всех j.

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

Конец. Иначе шаг 3.

Шаг 3: Выбирается .

Шаг 4: Просматривается столбец , если , то выписывается ответ: Задача не разрешима из-за неограниченности целевой функции.

Конец. Иначе шаг 5.

Шаг 5: Алгоритм перестроения базисных решений ЗЛП.

Шаг 6: Переход к шагу 1.

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

,

.

Решение. Оформление задачи происходит аналогично предыдущему примеру.

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

Таблица 2.3.1

				-1		-2
			-1					-
	-2			-1
		-6
				-1
						-1

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

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

,

.

Таблица 2.3.2

				-1			-2
			-1		-1				-
	-2			-1
				-3
		-6		-3
					-1
				-1
				-2			-1
			-3	-3

На второй итерации получаем, что оценка , но в столбце А₂ нет поло­жительных элементов. Ответ: целевая функция не ограничена.