Реферат: Линейное программирование

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

 

4.2. Симплекс-метод

Общую идею симплекс-метода проиллюстрируем на примере модели для задачи фирмы Reddy Mikks. На исходная точка алгоритма – начало координат (т. A) – начальное решение. От исходной точки осуществляется переход к некоторой смежной угловой точке (т. B или т. F). Её выбор зависит от коэффициентов целевой функции. Т.к. коэффициент при x­E больше коэффициента при xI, а целевая функция подлежит максимизации, требуемое направление перехода соответствует увеличению x­E (т. B). Далее указанный процесс повторяется для выяснения, существует ли другая экстремальная точка, соответствующая лучшему допустимому решению.

Правила выбора экстремальной точки:

1.         Каждая последующая угловая точка должна быть смежной с предыдущей.

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

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

Геометрическое определение (графический метод)	Алгебраическое определение (симплекс-метод)
Пространство решений	Ограничения модели стандартной формы
Угловые точки	Базисные решения задачи в стандартном виде

4.2.1. Представление пространства решений стандартной задачи ЛП.

Модель:

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

Если x­E=xI=0, то

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

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

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

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

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

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

Страницы: 1, 2, 3, 4