Основы математического программирования (стр. 4 )

2. Если же существуют какие-то решения системы (6), для которых все х1, х2, …, xn неотрицательны, то каждое из них допустимое.

3. Далее необходимо найти среди допустимых решений оптимальное, т. е. такое решение, которого линейная функция (5) обращается в минимум.

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

1. Запись ОЗ в координатном виде:

Z = c1x1 + c2x2 + … + cnxn min

{	a11x1 + a12x2 + … + a1nxn = b1 (6) a21x1 + a22x2 + … + a2nxn = b2 ……………………………………………. am1x1 + am2x2 + … + avnxn = bn xj ≥ 0, j = 1, 2, …, n

Или

	n
Z (x) =	∑ cjxj min
	j=1
n
∑ aijxj =	bi i = 1, 2,…, m
j=1

xj ≥ 0, j = 1, 2, …, n

2. Векторная запись ОЗ

Z(X) = C∙X min

A1x1 + A2x2 + … + Anxn = B

Х ≥ ʘ, где

X= (х1, х2, …, xn) C = (c1, c2, …, cn) ʘ = (0, 0, …, 0)

Aj =	(	a1j a2j … amj	)	j = 1, 2, …, n
B=	(	b1 b2 … bm	)

3. Запись в матричной форме

Z(X) = CX min

АХ = В Х ≥ ʘ

2.5. Понятие и назначение симплекс-метода

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

Метод называется симплексным, т. к. области допустимых решений задач, которые рассматривались на начальном этапе развития метода, имели простейший вид (simple).

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных (базисные переменные), которые выразим через остальные неизвестные (свободные переменные). Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как:

К такому виду можно привести любую совместную систему, например, методом Жордана-Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

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

Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ≥ 0.

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода.

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

Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением.

Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение Z самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции Z не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

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

1. Имея систему ограничений, приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m < n), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще.

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

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

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

Таким образом, применение симплексного метода распадается на два этапа:

1. нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;

2. нахождение оптимального решения.

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

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

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X1, X2, ..., Xr и что при этом b1, b2,..., br ≥ 0 (соответствующее базисное решение является опорным).

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

Далее эта система оформляется в виде симплекс-таблиц:

Базисные переменные	Своб. члены	Коэффициенты при базисных и свободных переменных
Х1	Х2	…	Хr	Хr+1	Хr+2	…	Xn
Х1	b’1	1	0	…	0	a1,r+1	a1,r+2	…	a1,n
Х2	b’2	0	1	…	0	a2,r+1	a2,r+2	…	a2,n
…	…	…	…	…	…	…	…	…	…
Хr	b’r	0	0	…	1	ar, r+1	ar, r+2	…	ar, n
Z	J0	0	0	…	0	Jr+1	Jr+1		Jn

Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

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

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

3) Выбираем из небазисных переменных ту, которая способна при введении её в базис увеличить (уменьшить) значение целевой функции, т. е. переменную, стоящую в разрешающем столбце и отмечаем её звездочкой «*».

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

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

aij’ = aij – (akj*aip)/akp, где akp, разрешающий элемент.

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

Z(x) = 4x1 – 6x2 – 8x3 +10x4 min

x1 + x2 + x3 + x4 = 10

–x1 + x2 + 3 x3 – 3x4 = 2

xj ≥ 0 "j

m = 2, n = 4 r = 2

2 переменные базисные, 2 переменные свободные (например x3 и x4)

Сложим два уравнения: