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

симплекс-алгоритм состоит из следующих шагов.

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

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

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

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

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

Z - X1 - 25X2 + 0S1 - 0S2 = 0 (Целевая функция)

5X1 + 100X2 + S1 = 1000 (Ограничение)

-X1 + 2X2 + S2 = 0 (Ограничение)

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

В рассматриваемом случае очевидно, что подстановка X1 = X2 = 0 сразу же приводит к следующему результату: S1 = 1000, S2 = 0 (т. е. решению, соответствующему точке А на рис. 1). Поэтому точку А можно использовать как начальное допустимое решение. Величина Z в этой точке равна нулю, так как и X1 и X2 имеют нулевое значение. Поэтому, преобразовав уравнение целевой функции так, чтобы его правая часть стала равной нулю, можно убедиться в том, что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение. Это имеет место во всех случаях, когда начальный базис состоит из остаточных переменных.

Полученные результаты удобно представить в виде таблицы:

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z		-1	- 25				Z – уравнение
S1							S1 –уравнение
S2		-1					S2 – уравнение

Эта таблица интерпретируется следующим образом. Столбец «Базисные переменные» содержит переменные пробного базиса S1, S2, значения которых приведены в столбце «Решение». При этом подразумевается, что небазисные переменные X1 и X2 (не представленные в первом столбце) равны нулю. Значение целевой функции Z = 1*0 + 25*0 + 0*1000 + 0*1 равно нулю, что и показано в последнем столбце таблицы.

Определим, является ли полученное пробное решение наилучшим (оптимальным). Анализируя Z - уравнение, нетрудно заметить, что обе небазисные переменные X1 и X2, равные нулю, имеют отрицательные коэффициенты. Всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента (в Z - уравнении), так как практический опыт вычислений показывает, что в этом случае оптимум достигается быстрее. Это правило составляет основу используемого в вычислительной схеме симплекс-метода условия оптимальности, которое состоит в том, что, если в задаче максимизации все небазисные переменные в Z - Уравнение имеют неотрицательные коэффициенты, полученное пробное решение является оптимальным. В противном случае в качестве новой базисной переменной следует выбрать ту, которая имеет наибольший по абсолютной величине отрицательный коэффициент.

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

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

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

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

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

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

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

Тип 2 (формирование всех остальных уравнений, включая Z - yравнение).

Новое уравнение = Предыдущее уравнение —

é Коэффициент ù

ê ведущего столбца ê * (Новая ведущая строка).

ê предыдущего ê

ë уравнения û

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

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z
S1
S2		-1/2			1/2

Чтобы составить новую симплекс-таблицу, выполним необходимые вычислительные процедуры типа 2

1. Новое Z - уравнение.

старое Z - уравнение: (1 -1 -25 0 0 0)

(- (-25) * (0 -1/2 1 0 1/2 0)

(1 -131/2 0 0 121/2 0)

2. Новое S1 - уравнение

старое S1 - уравнение: (0 5 100 1 0 1000)

(- 100) * (0 -1/2 1 0 1/2 0)

(0 55 0 1 -50 1000)

Новая симплекс-таблица будет иметь вид:

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z		-131/2			121/2		Z – уравнение
S1					-50		S1 –уравнение
X2		-1/2			1/2		X2 – уравнение

В новом решении X1 = 0 и S2 = 0. Значение Z не изменяется. Заметим, что новая симплекс-таблица обладает такими же характеристиками, как и предыдущая: только небазисные переменные X1 и S2 равны нулю, а значения базисных переменных, как и раньше, представлены в столбце «Решение». Это в точности соответствует результатам, получаемым при использовании метода Гаусса—Жордана.

Из последней таблицы следует, что на очередной итерации в соответствии с условием оптимальности в качестве вводимой переменной следует выбрать X1, так как коэффициент при этой переменной в Z-ypaвнении равен -131/2. Исходя из условия допустимости, определяем, что исключаемой переменной будет S1. Отношения, фигурирующие в правой части таблицы, показывают, что в новом базисном решении значение включаемой переменной X1 будет равно 1000/55 (= минимальному отношению). Это приводит к увеличению целевой функции на (1000/55) * (-131/2) = (2455/11).

К получению симплекс-таблицы, соответствующей новой итерации, приводят следующие вычислительные операции метода Гаусса—Жордана.

1) Новое ведущее S1 - уравнение = Предыдущее S1 - уравнение / (55).

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z
S1				1/55	- 50/55	1000/55
X2

2) Новое Z - уравнение = Предыдущее Z - уравнение - (-131/2) * Новое /ведущее уравнение:

(1 -131/2 0 0 121/2 0)- (-131/2)

* (0 1 0 1/55 -50/55 1000/55)

(1 0 0 27/110 5/22 2455/11)

3) Новое X2 - уравнение = Предыдущее X2 - уравнение - (-1/2) * Новое ведущее уравнение:

(0 -1/2 1 0 1/2 0)

- (- 1/2) * (0 1 0 1/55 -50/55 1000/55)

(0 0 1 1/110 1/22 91/11)

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

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z				27/110	5/22	2455/11
X1				1/55	-50/55	1000/55
X2				1/110	1/22	91/11

В новом базисном решении X1=1000/55 и X2=91/11. Значение Z увеличилось с 0 (предыдущая симплекс-таблица) до 2455/11 (последняя симплекс-таблица). Этот результирующий прирост целевой функции обусловлен увеличением X1 от О до 1000/55, так как из Z - строки предыдущей симплекс-таблицы следует, что возрастанию данной переменной на единицу соответствует увеличение целевой функции на(-131/2).

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

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

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

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

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

19. Нелинейное программирование

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

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

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

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

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

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

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

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

Существуют следующие методы нелинейного программирования:

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

- метод Монте-Карло, при котором определяется параллелепипед n-ой размерности, включающий в себя множество планов, для последующего моделирования случайных N-точек с равномерным распределением в данном параллелепипеде.

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

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

В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=(), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств

, i=1,2,…,m (1)

а переменные, т.е. компоненты вектора х, неотрицательны:

(2)

Иногда в формулировке задачи ограничения (1) имеют противоположные знаки неравенств. Учитывая, однако, что если, то, всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например, то их можно представить в виде пары неравенств,, сохранив тем самым типовую формулировку задачи.

20. Метод Кунера-Текера