I. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Прежде чем рассмотреть положения метода, необходимо ввести некоторые определения.

Считается, что задача линейного программирования записана в стандартной форме, если она имеет вид:

(9)

 

(10)

Поскольку задачи линейного программирования дают решение экономической задаче, то вместо слова «решение» будем использовать слово «план».

Определение 1. Решение системы ограничений (9), в котором свободные неизвестные приравнены нулю, называют базисным планом.

Определение 2. Любое неотрицательное решение системы ограничений задачи линейного программирования называют допустимым планом.

Определение 3. Допустимый базисный план называется опорным.

Определение 4. Допустимый план системы ограничений (9), при котором функция достигает наибольшего (наименьшего) значения, называется оптимальным.

Таким образом, суть задачи линейного программирования состоит в том, что среди всех допустимых планов необходимо выбрать оптимальный. Оптимальный план ищут с помощью симплекс-таблиц, которые заполняют по определенным правилам, в основу которых положен метод Жордана-Гаусса. Для этого начальную таблицу записывают в специальном виде. Задача (9)-(10) называется канонической.

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

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

2) свободные члены системы ограничений неотрицательные;

3) оптимизирующая форма зависит только от свободных неизвестных.

 

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

Свободными неизвестными считаются x₁, x₂, …, x_k, базисными – x_k+1, …, x_n. Тогда каноническая форма имеет вид:

(11)

 

(12)

 

Для того, чтобы базисный план системы ограничений (11) был опорным, необходимо и достаточно, чтобы все свободные члены были неотрицательными. Таким образом, чтобы свести задачу к каноническому виду, необходимо так подобрать базисные неизвестные, чтобы в общем решении системы ограничений не было отрицательных свободных членов. Следует напомнить, что в системе уравнений (9) разных наборов базисных неизвестных моет быть не больше от .

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

II. СИМПЛЕКС-ТАБЛИЦЫ И ПРАВИЛА РАБОТЫ С НИМИ

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

Пример 10.

(max) z₀=3x₁+2x₂;

(13)

Итерация I. Запишем форму z₀ в виде уравнения z₀-3x₁-2x₂=0. приведем исходную задачу к канонической форме (легко проверить, что (13) – каноническая форма) и заполним таблицу для итерации I.

Таблица 1

Номер строки	Базисные неизвестные	Опорный план	x1	x2	x3	x4
	z0			-2	-	-
	x3					-	12: 2=6
				-1	-		4: 2=2

 

Эта таблица заполняется формально по выбранной канонической форме:

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

Критерий оптимальности по симплекс-таблицам. Если форма максимизируется и в нулевой строке отсутствуют отрицательные числа (за исключением столбца «опорный план»), то опорный план оптимальный. При минимизации формы для оптимальности плана достаточно отсутствие положительных чисел в нулевой строке. Коэффициент нулевой строки можно интерпретировать как прирост функции z₀ при увеличении свободной неизвестной на единицу. Прирост положительный, если коэффициент отрицательный, и отрицательный – если коэффициент положительный. В этом случае есть два отрицательных числа (-3), (-2); берем наименьшее (-3), и столбец «x₁» будет разрешающим. Для выбора разрешающего элемента составим отношения свободных членов (чисел «опорный план») к соответствующим положительным числам разрешающего столбца:

1) 12: 2=6;

2) 4: 2=2

Второе отношение меньше, потому что число «2» второй строки – разрешающий генеральный элемент в таблице обозначим квадратом и переходим к итерации II.

Таблица 2.

Номер строки	Базисные неизвестные	Опорный план	x1	x2	x3	x4
	z0		-		-	3/2
			-			-	8: 4=2
	x1			-1/2	-	1/2	-

 

Последовательность заполнения этой таблицы такова:

1) вместо базисной неизвестной x₄ вводим базисную неизвестную x₁ (неизвестную разрешающего столбца);

2) формально заполняем базисные столбики (п.1 итерации I);

3) для заполнения разрешающей строки делим все соответствующие элементы на разрешающий элемент и располагаем на своих местах. Эта строка называется разрешающей (генеральной);

4) все другие строки заполняем методом Жордана-Гаусса, исключая x₁ последовательно из строк 0 и 1. Для этого достаточно строку 2 таблицы 2 сначала умножить на 3 и прибавить к строке 0 таблицы 1, а потом строку 2 таблицы 2 умножить на (-2) и прибавить к строке 1 таблицы 1.

Строки пункта 4 можно заполнить, используя следующие правила:

a) определяют строку, которую будем заполнять в таблице 1, и помечают в ней число 2 разрешающего столбца;

b) умножают все числа ячеек разрешающей строки на число, противоположное помеченному;

c) дополняют число строки, которая заполняется (см. таблицу 1) до соответствующих чисел, созданных в пункте 4b, и размещаем их на своих местах (таблица 2).

После заполнения таблицы 2 проверяем опорный план на оптимальность. Следует перейти к следующему опорному плану, поскольку в нулевой строке столбца «x₁» есть отрицательное число (-7/2). Отношение 8: 4 = 2 (во второй строке отношение не складывается, т.к. коэффициент (-1/2) отрицательный). Следовательно, разрешающим элементом следует взять число 4.

Итерация III. В таблице 3 вместо базисной x₃ ставим новую базисную x₂, разрешающей – строку 1. В таблице 3 выполняем те же операции, что и при итерации I. Таблицу 3 заполняем в следующей последовательности:

1) числа первой строки таблицы 2 делим на 4;

2) строку 1 умножаем на 7/2 и прибавляем к нулевой строке таблицы 2;

3) строку 1, умноженную на 1/2, прибавляем ко второй строке таблицы 2.

Таблица 3.

Номер строки	Базисные неизвестные	Опорный план	x1	x2	x3	x4
	z0		-	-	7/8	5/8
	x2		-		1/4	-1/4
	x1			-	1/8	13/8

 

Результаты после операций пп. 1-3 располагаем в соответствующих ячейках строк 0, 1, 2 таблицы 3. В нулевой строке нет отрицательных чисел, поэтому опорный план таблицы 3 оптимальный. Выпишем его из столбца «опорный план»:

Примечание:

1. Каждой таблице соответствует своя каноническая форма записи. Например, по таблице 3 можно записать:

1. Правильность вычислений опорных планов и оптимального значения можно контролировать по исходной формуле . При решении задачи таблицы 1 – 3 последовательно записываются одна под одной. Запись имеет вид таблица 4.

Таблица 4.

Номер итерации	Номер строки	Базисные неизвестные	Опорный план	x1	x2	x3	x4
		z0			-2	-	-
	x3					-	12: 2=6
				-1	-		4: 2=2
		z0		-		-	3/2
			-			-	8: 4=2
	x1			-1/2	-	1/2
		z0		-	-	7/8	5/8
	x2		-		1/4	-1/4
	x1			-	1/8	3/8

 

III. МЕТОД НАХОЖДЕНИЯ НАЧАЛЬНОГО ОПОРНОГО ПЛАНА

(МЕТОД ИСКУССТВЕННОГО БАЗИСА)

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

С таким типом ограничений дополнительные неизвестные, которые введены, придают системе каноническую форму. С другой стороны, такая структура ограничений не охватывает всех возможных случаев, которые существуют в линейных оптимизационных моделях. Кроме того, есть такие задачи, которые не имеют ни одного допустимого плана. Например, задача

имеет базисные решения

ни одно из которых не является опорным.

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

Пусть задача линейного программирования

 

(14)

записана так, что все свободные члены . Этого всегда можно достигнуть, умноживши, если нужно, уравнение с отрицательным свободным членом на (-1).

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

(15)

К ней добавим искусственную форму

(16)

Задачи (15)-(16) являются задачами линейного программирования, которые записаны почти в канонической форме относительно базисных неизвестных . Остается в форме (16) из системы ограничений (15) выразить через свободные неизвестные

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

Для того, чтобы система ограничений (9) была совместной в области неотрицательных значений, необходимо и достаточно, чтобы на решениях (15) .

Если оптимальный план задачи (15)-(16) содержит хотя бы одну искусственную неизвестную , то исходная задача не имеет решения.

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

Пример 11.

Вводим искусственные неизвестные u₁, u₂:

искусственную форму

и заполняем таблицу для итерации 1.

Таблица 4.

Номер строки	Базисные неизвестные	Опорный план	x1	x2	x3	x4
	f			-1
	u1			-2
	u2
	z0		-2		-3

 

Примечание:

1. Чтобы найти опорный план, необходимо перевести искусственные неизвестные из базисных в свободные. Для этого в методе искусственного базиса используются редактированные таблицы, поскольку после перехода к свободной неизвестной искусственная будут не нужна.
2. Нулевую строку (строку оценок) заполняем по искусственной форме. Ее можно получить формальным добавлением чисел соответствующих столбцов системы ограничений.
3. Чтобы в конечном результате основная оптимизирующая форма также была выражена через свободные неизвестные, отводим ей последнюю строку в таблице и выполняем над ней те же преобразования, что и над другими строками.

Необходимые вычисления приведены в таблице 5 – итерации 2, 3.

В нулевой строке таблицы 5 нет положительных чисел, поэтому план оптимальный для задачи (15)-(16), а план - опорный план для исходной задачи. Выпишем данные итерации 3, где в нулевой строке стоят элементы формы z₀ (таблица 6), и решаем начальную задачу. План - оптимальный план; .

Таблица 5.

Номер итерации	Номер строки	Базисные неизвестные	Опорный план	x1	x2	x3	x4
		f			-1
				-2
	u2
	z0		-2		-3
		f	5/2			5/4	-5/4
	x1	9/2		-1/2	1/4	¾
		5/2			5/4	-5/4
	z0				-5/2	5/2
		f
	x1				1/2	1/2
	x2				1/2	-1/2
	z0				-5/2	5/2

 

Таблица 6.

Номер итерации	Номер строки	Базисные неизвестные	Опорный план	x1	x2	x3	x4
		z0					5/2
	x1				1/2	5/2
						-1/2
		z0
	x1			-1
	x3					-1

 

Для задачи, записанной ниже, метод искусственного базиса дает такой результат (таблица 7):

 

 

Таблица 7.

Номер итерации	Номер строки	Базисные неизвестные	Опорный план	x1	x2	x3	x4
		f			-2		-1
	u2			-3		-1
	x0		-2	-2		-
		f			-4	-1	-1
	x1
	u2			-4	-1	-1
	x0

 

Базисная неизвестная u₂ =1, f_min =1, поэтому система ограничений задачи не имеет ни одного допустимого плана. Это можно заметить из того, что оптимальный план итерации 2 содержит базисную неизвестную u₂, которая равна единице.

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