Решение задач линейного программирования симплекс-методом.

Идея разработана русским ученым Канторовичем Л.В. в 1939 году. На основе этой идеи американский ученый Д. Данциг в 1949 году разработал симплекс-метод, позволяющий решить любую задачу линейного программирования.

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

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

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

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

Геометрическая интерпретация симплекс-метода:

 

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

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

· необходимо найти все опорные решения (точки многогранника), множество которых является конечным;

· Вычислить для каждого из опорных решений значение целевой функции;

· Сравнить значения целевой функции в каждом из опорных решений и выбрать оптимальное (максимальное или минимальное).

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

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

 

Необходим метод направленного перебора точек, для практического применения метода направленного перебора необходимо знать:

1. Алгоритм определения какого-либо первоначального, допустимого решения.

2. Алгоритм перехода к лучшему или к не худшему решению.

3. Признак, указывающий на то, что найденное решение оптимально.

 

Симплекс-метод является методом направленного перебора.

Геометрически интерпретация симплекс метода состоит в последовательном переходе от одной вершины многогранника к другой (от первоначально выбранной вершины к одной из соседних вершин, а именно к той, у которой линейная функция принимает лучшее, или по крайней мере, не худшее значение). Этот процесс происходит до тех пор пока не будет найдено оптимальное решение – вершина, где достигается оптимальное решение функции (если задача имеет конечный оптимум).

Задачу симплекс-методом можно решить и аналитически, рассмотрим алгоритм решения.

Алгоритм симплекс-метода:

1. Выделяем исходный допустимый базис и заполняем первую симплекс-таблицу.

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

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

4. Пусть среди просмотренных в п.3. чисел имеются положительные числа, для каждого из таких чисел a составляем отношение , где b – первое число в той же строке, т.е. свободный член. Из всех таких отношений выбираем наименьшее. Пусть оно соответствует строке для базисного переменного x_i , отмечаем эту строку горизонтальной стрелкой. Число , стоящее в отмеченной строке и столбце и называется разрешающим элементом таблицы.

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

6. С новой таблицей возвращаемся к выполнению пункта 2.

 

1. Рассмотрим пример решения задачи линейного программирования симплекс-методом.

f(x) = x₄ – x₅ min

Если в целевой функции нет базисных переменных, то выражаем ее

f(x) = x₄ – x₅ = 0

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

Базовые переменные	Свободный член	х1	х2	х3	х4	х5
х1						-2
х2					-2
х3
f(x)					-1

 

 

 

 

 

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

Базовые переменные	Свободный член	х1	х2	х3	х4	х5
х1					-3
х5					-2
х3	0,2		-0,2	0,2
f(x)	-2		-1

 

Третья симплекс-таблица

 

Базовые переменные	Свободный член	х1	х2	х3	х4	х5
х1	5,6		1,4	0,6
х5	2,4		0,6	0,4
х4	0,2		-0,2	0,2
f(x)	-2,2		-0,8	-0,2

 

 

Ответ:

f(x)_min = -2,2, при

х₁ = 5,6

х₂ = 0

х₃ = 0

х₄ = 0,2

х₅ = 2,4

 

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

Пусть целевая функция первоначально имеет следующий вид

f(x) = c₀ + c₁x₁ + c₂x₂ + … + c_nx_n min

Пусть мы выделили допустимый базис и заполнили симплекс-таблицу, кроме последней строки, допустим базис – х₁, х₂, х₃, остальные – свободные члены.

		с0	с1	с2	…	cn
	Базовые переменные	Сводные члены	x1	x2	…	xn
c1	x1
c2	x2
c3	x3
	f(x)				…
					…

 

Рассмотрим пример

f(x) = 2x₁ – x₂ min

 

~

 

 

				-1
	Базовые переменные	Сводные члены	x1	x2	x3	x4	x5
	x1				-1
	x4	6/2	0/0	3/1	-1/	1/	0/0
	x5
	f(x)				-2

 

 

 

				-1
	Базовые переменные	Сводные члены	x1	x2	x3	x4	x5
	x1				-2/3	-1/3
-1	x2				-1/3	1/3
	x5				4/3	-1/3
	f(x)				-1	-1

 

Ответ:

f(x)_min =2

x₁ = 2

x₂ = 2

x₃ = 0

x₄ = 0

x₅ = 4

 

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

где - коэффициенты при неизвестных

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

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

В этом случае если только одна оценка свободной переменной равна 0, то

, где

Если две оценки и более, например s свободных элементов равно 0, то оптимальное решение определяется по формуле

, где

 

Пример:

f(x) = 2x₂ – 4x₃ + 2x₅ min

					-4
	Базисныеые переменные	Сводные члены	x1	x2	x3	x4	x5
	x1				-1
	x4	12/3	0/0	-2/-0.5	4/1	1/0.25	2/0.5
	f(x)			-2			-2
					-4
	Базовые переменные	Сводные члены	x1	x2	x3	x4	x5
	x1	10/4	1/0.4	2.5/1		0.25/0.1	2.5/1
-4	x3			-0.5		0.25	0.5
	f(x)	-12				-1	-4

f(x)_min = -12, при

х₁ = 10

х₂ = 0

х₃ = 3

х₄ = 0

х₅ = 0

 

 

					-4
	Базовые переменные	Сводные члены	x1	x2	x3	x4	x5
	x2		0.4			0.1
-4	x3		0.2			0.3
	f(x)	-12				-1	-4

 

f(x)_min = -12, при

х₁ = 0

х₂ = 4

х₃ = 5

х₄ = 0

х₅ = 0

 

х₁ = 10 * t + (1 – t) * 0 = 10

х₂ = 0 * t + (1 – t) * 4 = 4 – 4t

х₃ = 3 * t + (1 – t) * 5 = 5 – 2t

х₄ = 0

х₅ = 0

 

f(x)_min = -12, при

,