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

 

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

 

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

Модель:

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

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

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

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

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

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

 

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

 

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

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

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

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

 

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

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

Шаг 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 – минимальное). Снова проведём вычисления двух типов. Последняя симплекс-таблица соответствует оптимальному решению задачи, т.к. в -уравнении ни одна из небазисных переменных не фигурирует с отрицательными коэффициентами.

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

 

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

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

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

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

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

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

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

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

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

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

Теперь если

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

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

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

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

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

 

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