32. Двойственная задача линейного программирования. Нахождение допустимых базисных решений. Метод искусственных переменных.

Нахождение допустимых базисных решений. Определение начального допустимого базисного решения (ДБР) в общем случае представляет значительные трудности. Поэтому для поиска ДБР разработаны специальные методы.

Метод искусственных переменных. Пусть ограничения задачи ЛП имеют вид

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

В общем случае, когда некоторые ограничения имеют знак , например

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

(1.1)

Свободные переменные {xn+1,.,xn+m} в этом случае уже невозможно использовать в качестве начального базиса, так как xn+1<0,.,xn+m<0. Поэтому в уравнения (1.1) дополнительно вводят искусственные переменные xn+m+1,.,xn+m+k. Эти переменные не имеют ничего общего с реальной задачей, и потому их надо вывести из базиса как можно быстрее. Для этого перед началом итераций искусственным переменным в целевой функции приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где .

В случае решения задач минимизации искусственные переменные вводят в целевую функцию с большими положительными коэффициентами (+М).

Знаки искусственных переменных xn+m+1,.,xn+m+k должны совпадать со знаками соответствующих свободных членов. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения, то есть ее ограничения противоречивы.

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

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

Ф ормулировка задачи нелинейного программирования. Задача нелинейного программирования в общем виде формулируется следующим образом. Найти

max f( x1, x2, ... , xn)

(34)

при условиях

где функции в общем случае нелинейны. Задачи условной оптимизации нелинейного программирования бывают двух типов: когда в ограничениях (34) имеют место 1) знаки равенства и 2) знаки неравенства. Рассмотрим вначале задачу условной оптимизации с ограничениями в виде равенств.

Ограничения в виде равенств. Начнем изложение метода условной оптимизации с рассмотрения примера максимизации функции двух переменных z=f(x,y), где на x и y наложено ограничение, задаваемое уравнением g(x,y)=0. Разрешим уравнение g(x,y)=0 относительно y и решение представим в виде зависимости y от x , т. е. y=h(x). Предположим, что функции g(x,y) и h(x) дифференцируемы, тогда можно определить производную функции h(x). Она будет иметь вид:

(35)

Далее представим целевую функцию z как функцию одной независимой переменной z=f(x,y)=f(x,h(x)). Необходимым условием минимума функции z будет соотношение

Подставляя в данное выражение формулу (35) и производя перегруппировку параметров, получаем

(36)

Выражение, стоящее в скобках, обозначим следующим образом:

(37)

Тогда можно отметить, что в точке максимума должны выполняться соотношения

Первое выражение – это ограничение, которое указано в постановке задачи, второе следует непосредственно из (36) путем замены переменных (37), и, наконец, третье выражение получается из (37), умножением правой и левой частей на знаменатель выражения и переносом сомножителей в левую часть. Получить эти три необходимых условия можно также, используя функцию Лагранжа F( x, y, )=f ( x, y )+ g( x, y ), которая представляет собой сумму целевой функции и произведения сомножителя на функцию ограничения. Коэффициент называется множителем Лагранжа. Тогда необходимые условия максимума функции f(x,y) при наличии ограничений могут быть записаны в виде

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

Необходимые условия задачи нелинейного программирования могут быть обобщены для функции n переменных при наличии m ограничений в виде равенств. Рассмотрим задачу условной оптимизации функции

z=f(X)=f(x₁,x₂,…,x_n),где на вектор X наложены ограничения g₁ (X)=0 , g₂ (X)=0, …,g_m (X)=0 . Определим для этой задачи функцию Лагранжа в виде

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