Нахождение начального допустимого базисного решения.

Алгоритм симплекс – метода предполагает известным начальное допустимое базисное решение. В простых задачах оно очевидно или его можно легко получить. В практических задачах, содержащих большое число ограничений и переменных, это оказывается весьма сложным. Нахождение начального допустимого базисного решения выполняется путем решения самим же симплекс – методом вспомогательной задачи. Последняя формируется введением неотрицательных искусственных переменных с коэффициентом +1 в ограничения исходной задачи в виде неравенств со знаком и в ограничения в виде равенств со знаком =. Пусть n – количество основных переменных исходной задачи. Обозначим GC – количество ограничений в виде неравенств со знаком ; ЕС - в виде равенств со знаком = и LC в виде неравенств со знаком и пусть они расположены именно в таком порядке. Обозначим N= n+ GC+ LC – количество переменных после приведения исходной задачи к стандартной форме (сумма GC+ LC есть число дополнительных переменных). Вспомогательная задача имеет вид:

(2.21)

(2.22)

_{Функция w называется искусственной целевой функцией. Решение вспомогательной задачи известно заранее, если существует решение исходной задачи. Это нулевое значение w при нулевых значениях искусственных переменных, поскольку сумма неотрицательных искусственных переменных не может быть меньше нуля. При нулевых значениях искусственных переменных измененные ограничения (2.22) равносильны исходным (2.4). Поэтому базисное допустимое решение, минимизирующее функцию w, может быть использовано как начальное базисное допустимое решение для решения исходной задачи – минимизации функции z. Если после завершения решения вспомогательной задачи хотя бы одна из искусственных переменных отлична от нуля, исходная задача не имеет решения из-за противоречивости ограничений. То же можно сказать, если хотя бы одна искусственная переменная в итоговой симплекс – таблице осталась в базисе.}

_{Начальное базисное допустимое решение для вспомогательной задачи легко находится. Для этого искусственные переменные и LС последних дополнительных переменных полагаются базисными и начальным допустимым базисным решением будет столбец правых частей ограничений b.}

Таким образом, решение задачи ЛП симплекс – методом состоит из двух этапов. На 1 этапе в соответствии с изложенным формируется расширенная таблица размером . Искусственная целевая функция w является суммой искусственных переменных и хранится в строке расширенной матрицы А. Выраженная через небазисные переменные, она имеет вид

,

где коэффициент состоит из отрицательного значения суммы, взятой по первым GC + ЕС строкам коэффициентов при расширенной матрицы ограничений. Величина равна сумме правых частей, взятой с противоположным знаком.

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

Этап 1 завершается минимизацией функции w и переходят к этапу 2 или делается вывод об отсутствии решения исходной задачи. На этапе 2 минимизируется целевая функция z изложенным выше образом.

Пример

Минимизировать функцию

при ограничениях ,

,

,

,

Это - пример 1 из разд.1.2, решенный графически без всяких затруднений. В стандартной форме с неотрицательными дополнительными переменными ограничения принимают вид

,

,

, (2.22)

.

Однако при попытке применить симплекс-метод оказывается, что нет очевидного базисного допустимого решения. Базисное решение, получаемое приравниванием дополнительных переменных значениям в правых частях, недопустимо. Этим решением является точка = =0, = -10, =- 5, = 20, = 20, и в нем и оказываются отрицательны.

Изменим первые два ограничения введением в левую часть искусственных переменных и (неотрицательных) . Измененные ограничения запишутся так:

,

, (2.23)

.

и для них базисное решение очевидно. Это решение = = = = 0 (небазисные переменные), = 10, = 5, = 20, = 20. Затем симплекс-метод используется для минимизации функции

(2.24)

Этап I задачи состоит в минимизации функции .

Предположим, что ограничения (2.22) имеют допустимое решение и, следовательно, базисное допустимое решение (это не всегда так) ; тогда решение этапа I задачи закончится тем, что функция обратится в 0 и при этом и тоже будут нулевыми. Но когда и равны нулю, измененные ограничения (2.23) равносильны исходным (2.22). Базисное допустимое решение, минимизирующее функцию , может быть использовано как начальное базисное допустимое решение для минимизации функции на этапе II задачи. Начиная с этого момента, нулевые значения и игнорируются.

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

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

Итера-ция	Базис	Значе-ние
0		10	1*	0	-1	0	.	.	1	.
		5	0	1	0	-1	.	.	.	1
		20	1	1	0	0	1	.	.	.
		20	-1	4	0	0	.	1	.	.
		0	-3	-4	0	0	.	.	.	.
		-15	-1	-1	1	1	.	.	.	.
1		10	1	0	-1	0	.	.	1	.
		5	.	1*	0	-1	.	.	0	1
		10	.	1	1	0	1	.	-1	.
		30	.	4	-1	0	.	1	1	.
		30	.	-4	-3	0	.	.	3	.
		-5	.	-1	0	1	.	.	1	.
2		10	1	.	-1	0	.	.	.	0
		5	.	1	0	-1	.	.	0	1
		5	.	.	1	1	1	.	-1	-1
		10	.	.	-1	4	.	1	1	-4
		50	.	.	-3	-4	.	.	3	4
		0	.	.	0	0	.	.	1	1

На этой стадии минимизирована функция , переменные и небазисные и потому равны 0. Заметим, что можно было бы пренебречь , еще на итерации 1 и уж точно с настоящего момента можно пренебречь и , и . Переменная сохранена просто для того, чтобы показать, что в оптимальное решение для функции и , и входят с коэффициентом 1, когда значение функции равно 0( ). Поскольку выражение для функции , приведенной к данному базису, сохраняется, можно минимизировать функцию по-настоящему. Сейчас мы находимся в точке Р (рис. 1.2). Этап I задачи завершен, и конечная таблица без последних двух столбцов и без последней строки является входной для этапа II. Таблицы этапа II имеют следующий вид:

Итера-ция	Базис	Значе-ние
2		10	1	.	-1	0	.	.
		5	.	1	0	-1	.	.
		5	.	.	1	1	1	.
		10	.	.	-1	4	.	1
		50	.	.	-3	-4	.	.
3		10	1	.	-1	.	.	0
		15/2	.	1	-1/4	.	.	1/4
		5/2	.	.	5/4*	.	1	-1/4
		5/2	.	.	-1/4	1	.	1/4
		60	.	.		.	.	1
4		12	1	.	.	.	4/5	-1/5
		8	.	1	.	.	1/5	1/5
		2	.	.	1	.	4/5	-1/5
		3	.	.	.	1	1/5	1/5
		68	.	.	.	.	16/5	1/5

Последовательные таблицы 2, 3, 4 соответствуют точкам Р, Q, R (рис. 1.2). Последняя таблица оптимальна, так что минимум функции равен -68 при = 12, =8, =2, =3.

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