Симплексный метод решения задачи

Линейного программирования

 

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

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

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

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

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

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

2. Нахождение некоторого опорного базисного решения.

3. Проверка полученного опорного плана на оптимальность.

4. В случае неоптимальности опорного плана происходит переход к новому базисному решению, уменьшающему (или увеличивающему) значение целевой функции.

Выбор базисных решений происходит путем преобразования системы уравнений методом Гаусса.

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

Для задачи вида:

F =

Симплексная таблица выглядит следующим образом:

 

C j^С^j	Б	c1	c2	…	cn	c0
		х 1	х 2	…	х n	bi
ck	хk	a11	a12	…	a1n	bk
cl	хl	al1	al2	…	aln	bl
…	…	…	…	…	…
cm	xm	am1	am2	…	amn	bm
	D j

Вторая сточка и второй столбец являются заголовками: в строчке перечисляются все неизвестные, а в столбце те из них, которые образуют базисное решение (x_k, x_l,…,x_m). В первой строчке и первом столбце записываются коэффициенты целевой функции при соответствующих переменных. Последняя строка является вспомогательной и используется для полученных позже оценок оптимальности плана. Во все остальные строчки и столбцы записывается расширенная матрица системы.

Не нарушая общности рассуждений, рассмотрим симплекс-метод на конкретном примере.

Пример. Четыре изделия В₁, В₂, В₃, В₄ последовательно обрабатываются на двух станках. Данные, описывающие этот технологический процесс, приведены в таблице. При каком плане производства суммарная цена изделий будет максимальной?

	В1	В2	В3	В4	Максимальная
Станки	Время обработки (часы)	нагрузка (часы)
А1
А2
Цена 1 изделия

Составим математическую модель задачи:

Критерий эффективности - суммарная цена изделий, параметры управления x ₁, x _2, x ₃ и x ₄ – количества изделий каждого вида. Все переменные должны быть неотрицательны.

Ограничения на время работы первого станка:

.

Ограничения на время работы второго станка:

.

Целевая функция стремится к максимуму.

I шаг. Приведем систему к каноническому виду.

Так как левые части неравенств не превышают правые, то добавление неотрицательных переменных x ₅; x ₆ сведет неравенства к равенствам. Эти переменные играют роль неизрасходованной нагрузки станков. Математическая модель задачи в каноническом виде:

II шаг. Выберем первое опорное базисное решение. Так как система ограничений содержит два неравенства (без учета неотрицательности переменных), то базисных переменных может быть максимум две. По указанному выше правилу в нашем случае такими переменными являются x ₅, x ₆, так как они входят только в одно из уравнений с коэффициентами, равными единице.

Составим первую симплекс таблицу:

Cj^С^j	Б	30	30	10	15	0	0
		х 1	х 2	x 3	х 4	х 5	х 6	bi
0	х 5
0	х 6
	D j	-30	-30	-10	-15

Итак, если принять все свободные переменные x ₁, x ₂, x ₃, x ₄ равными нулю, то получим первый план (0, 0, 0,0, 500, 380). Обратим внимание, что если коэффициенты при базисных переменных равны 1, то их значения равны свободным членам и, следовательно, записываются в последнем столбце.

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

Например, D₁= 0×2+0×3−30 = –30.

Занесем значения оценок в таблицу.

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

У нас есть отрицательные оценки, следовательно, план неоптимальный.

В ячейке на пересечении последнего столбца и последней строки вычисляется значение целевой функции на базисном решении. Z = 0.

IV шаг. Перейдем к следующему плану. В качестве новой базисной переменной выбирают одну из тех, чья оценка отрицательна, например, х ₂. Столбец, в котором находится новая базисная переменная, называется ключевым. Для определения вместо какой переменной x ₅ или x ₆ выбирается переменная х ₂ выбираем минимум из отношений элементов столбца свободных членов и положительных элементов ключевого столбца.

. (2.8)

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

.

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

Преобразуем расширенную матрицу системы так, чтобы базисными переменными стали x ₂; x ₆. Для этого применим стандартный порядок преобразований.

1) Разделим ключевую строку на ключевой элемент.

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

C j^С^j	Б	30	30	10	15	0	0
		х 1	х 2	x 3	х 4	х 5	х 6	bi
30	х 2
0	х 6	1				–
	D j	–10						5000

Первая строка получена делением на 3 (преобразование 2 рода). Вторая строка получена прибавлением к ней новой первой строки, умноженной на –2 (преобразование 3 рода).

Новый план: (0; ; 0; 0; 0; ).

V шаг. Проверим план на оптимальность, вычислим оценки D _j.

Например, .

Значение целевой функции на этом плане:

.

VI шаг. В первом столбце – отрицательная оценка, следовательно, план неоптимальный. Выбираем этот столбец за ключевой. Составим отношения для выбора ключевой строки.

.

Следовательно, ключевая строка – вторая. Базисными переменными станут x ₁ и x ₂.

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

Cj ^С^j	Б	30	30	10	15	0	0
		х 1	х 2	x 3	х 4	х 5	х 6	bi
30	х 2						–
30	х 1			–1		–
	D j							5280

Вычислим оценки плана и внесем их в таблицу. Отрицательных оценок нет, следовательно, план (28; 148; 0;0;0;0) оптимальный. Максимальное значение целевой функции 5280.

Итак, суммарная цена изделий будет максимальной и равной 5280, если производить 28 изделий В₁, 148 изделий В₂ и не производить изделия В₃, В₄. Такой вывод не должен вызывать удивление, так как у нас всего два ограничения, следовательно, только две базисные переменные, поэтому только два параметра могут принимать положительные значения, остальные равны нулю.

Рассмотрим пример, в котором определение первого опорного плана не так тривиально.

Найдите наибольшее значение функции , если

Приведем задачу к каноническому виду: к левой части второго неравенства прибавим неотрицательную переменную x ₄, чтобы уравнять ее с правой частью, а из левой части третьего неравенства, напротив, вычтем неотрицательную переменную x ₅, чтобы также уравнять с правой частью.

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

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

Рассуждения проводятся следующим образом: какой из столбцов можно привести к виду (1; 0; 0) – только второй или третий, так как элементы а ₁₂ и а ₁₃ положительны, выберем из них тот, который соответствует правилу (2.8), то есть минимум отношения свободного члена к соответствующему элементу матрицы был бы в первой строке.

Þ и .

Видим, что это справедливо для обоих столбцов, поэтому любой из них можно выбрать за первый базисный вектор. Решим задачу дважды, сначала выберем второй столбец и преобразуем систему: к третьей строке прибавим первую, умноженную на –1.

.

В качестве второй базисной переменной выберем x ₄, так как столбец уже имеет базисный вид (0; 1; 0). Третьей базисной переменной может быть только x ₁, так как в последней строке только один элемент положителен. Проверим, выполняется ли для него правило (2.8).

.

Минимум соответствует третьей строке, значит, x ₁ может быть базисной переменной с неотрицательным значением. Разделим третью строку на 2. Затем вычтем ее из второй строки и прибавим к первой.

Итак, базис (x ₂, x ₄, x ₁). Составим симплексную таблицу и проверим план на оптимальность.

Cj ^С^j	Б	-3	1	2	0	0
		х 1	х 2	x 3	х 4	х 5	bi
1	х 2			1,5		-0,5
0	x 4			1,5		0,5
-3	х 1			-0,5		–0,5
	D j						-2

Все оценки неотрицательны, следовательно, сразу получен оптимальный план (2, 4, 0, 4, 0), наибольшее значение целевой функции –2. Напомним, что две последние переменные вспомогательные, следовательно, оптимальное решение (2, 4, 0).

Повторим решение системы, взяв за первую базисную переменную - x ₃. Преобразуем матрицу, приведя этот столбец к виду (1,0,0).

Разделим первую строку на элемент а ₁₃,затем вычтем получившуюся строку из второй и третьей.

Þ

В качестве второй базисной переменной можно взять x ₄, тогда последнюю базисную переменную нужно выбрать из x ₁ или x ₂. Составим отношения (2.8) для каждого из этих столбцов:

; ,

первый результат соответствует второй строке, а второй результат - первой строке, следовательно, ни первый, ни второй столбец не удастся привести к виду (0, 0, 1) так, чтобы свободные члены остались неотрицательны. Следовательно, предыдущий выбор был ошибочным, за вторую базисную переменную следует взять x ₁, так как для первого столбца минимум отношений соответствует второй строке.

Приведем первый столбец к виду (0, 1, 0). Разделим вторую строку на 1,5. Затем получившуюся строку, умножив на 0, 5, прибавим к первой и, умножив на –1,5, прибавим к третьей.

.

За третью базисную переменную необходимо взять x ₂. Соотношение (2.8) для второго столбца минимально именно в третьей строке.

Прибавим ко второй строке третью, деленную на 3, и к первой строке - третью, деленную на –3.

.

Итак, выбрали базисные переменные x _3, x ₁ и x ₂.

Первый базисный план . Проверим его на оптимальность.

Cj ^С^j	Б	– 3	1	2	0	0
		х 1	х 2	x 3	х 4	х 5	bi
2	х 3				2/3	1/3	4/3
– 3	x 1				1/3	–1/3	8/3
1	х 2				–1	–1
	D j				–2/3	2/3	– 10/3

Опорный план не оптимален, так как есть отрицательные оценки. Выберем четвертый столбец за ключевой, составим для него соотношение (2.8).

.

Ключевая строка – первая. Следовательно, вместо базисной переменной x ₃ в базис войдет переменная x ₄. Преобразуем четвертый столбец к виду (1; 0; 0). Ключевую строку разделим на ключевой элемент , затем прибавим ее к третьей строке и, разделив на –3, прибавим ко второй.

Cj ^С^j	Б	– 3	1	2	0	0
		х 1	х 2	x 3	х 4	х 5	bi
	х 4			3/2		1/2
–3	x 1			–1/2		–5/6
	х 2			3/2		–1/2
	D j						– 2

Второй план (2, 4, 0, 2, 0), проверив его на оптимальность, получаем неотрицательные оценки, следовательно, он оптимален. Мы получили то же решение, только более длинным путем.