Основные понятия теории оптимизации

 

с

Модель:

максимизировать целевую  функцию

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

На – пространство решений. Каждую точку можно определить с помощью

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

Анализируя , заметим, что 

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

 

Экстр.	переменные
точка	нулевые	ненулевые
A
B
C
D
E
F

 

Из таблицы выделим  закономерности:

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

Если линейная модель стандартной формы содержит уравнений и неизвестных, то все допустимые экстремальные точки определяются как все однозначные неотрицательные решения системы уравнений, в которых m-n переменных равны нулю. Однозначные решения такой системы – базисные решения. Если они удовлетворяют требованию неотрицательности правых частей, то это – допустимое базисное решение. Переменные, равные нулю – небазисные, остальные – базисные. Каждую следующую экстремальную точку можно определить определить путём замены одной из текущих небазисных переменных текущей базисной переменной. В нашем примере при переходе из т. A в т. B необходимо увеличивать небазисную переменную от исходного нулевого значения до значения, соответствующего т. B. В т. B s2 обращается в нуль (становится небазисной). Т.о., происходит взаимообмен xE и s2 между небазисными и базисными переменными.

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

Вычислительные  процедуры симплекс-метода

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

Шаг 0: Используя линейную модель стандартной формы, определяют НДБР путём приравнивания к нулю n-m (небазисных) переменных.

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

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

Шаг 3: Находится новое  базисное решение, соответствующее новым составам базисных и небазисных переменных. Переход к Шагу 1.

Если xE=xI=0, то

(соответствует точке  A Ha ) – начальное допустимое решение.

 

								Решение
		-3	-2
			2					6
		2						8
		-1
								2

 

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

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

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

 

								Решение	Отношение
		-3	-2						-
			2					6
		2						8
		-1							-
								2	-

 

Столбец, ассоциированный  с вводимой переменной – ведущий  столбец; строка, соответствующая исключаемой переменной – ведущая строка; на их пересечении – ведущий элемент.

Поиск нового базисного  решения осуществляется методом  исключения переменных (метод Жордана-Гаусса). Этот процесс включает в себя вычислительные процедуры двух типов.

Тип 1. Формирование ведущего уравнения

Новая ведущая строка = предыдущая ведущая строка/ведущий  элемент

Тип 2. Формирование остальных  уравнений

Новое уравнение = предыдущее уравнение – (коэффициент ведущего столбца предыдущего уравнения)*(новая  ведущая строка)

Новая симплекс-таблица, полученная после проведения рассмотренных  операций:

 

								Решение	Отношение
									-
									-
									-
									-
									-
									-

 

xI – вводимая переменная (т.к. коэффициент в -уравнении -1/2). Исключаемая переменная s1, (отношение 4/3 – минимальное). Снова проведём вычисления двух типов. Последняя симплекс-таблица соответствует оптимальному решению задачи, т.к. в -уравнении ни одна из небазисных переменных не фигурирует с отрицательными коэффициентами.

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

Искусственное начальное решение

Для получения начального базисного решения мы использовали остаточные переменные. Однако когда  исходное ограничение записано в виде равенства или имеет знак, нельзя сразу же получить НДБР. Поэтому были разработаны два метода, в которых используется «штрафование» искусственных переменных.

1. Метод больших штрафов (М-метод)

Рассмотрим  линейную модель, приведённую к стандартной  форме:

минимизировать

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

В первом и втором уравнениях нет переменных, исполняющих  роль остаточных. Поэтому введём в  каждое из этих уравнений по одной  из искусственных переменных R1 и R2:

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

минимизировать

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

Теперь если

,то начальное  допустимое решение: 

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

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

получим выражение  для  :

Решение представлено в сводной таблице:

 

Итерация								Решение	Отношение
									-
									-
									-
									-
									-
									-
									-
									-