27.3.4Замечание к решению задачи на максимум

Если в задаче на максимум в m + 1 строке есть хотя бы одна оценка

fj cj < 0

то найденный опорный план не оптимален.

Если отрицательных оценок несколько, то в базис включается вектор, которому соотвествует

min[ oj(fj cj)]

j

где минимум берется по тем индексам j, для которых оценки

fj cj < 0.

Остальные действия такие же, как при решении задачи на минимум.

28 Методы искусcтвенного базиса

28.1Метод больших штрафов

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

f = c1x1 + c2x2 + ::: + cnxn (9:1)

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

8

>a11x1 + a12x2 + ::: + a1nxn = b1

>

>

<a21x1 + a22x2 + ::: + a2nxn = b2

(9:2)

>:::

>

>

:am1x1 + am2x2 + ::: + amnxn = bm

xj > 0 j = 1; 2; :::; m (9:3)

в которой все bi > 0 и система (9:2) не содержит единичной матрицы.

Прибавим к левой части единичного равенства по одной переменной xn+i > 0, которые назовем искусственными.

Рассмотрим расширенную задачу: найти минимум ф-и

f = c1x1 + c2x2 + ::: + cnxn + Mxn+1 (9:4)

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

8

>a11x1 + a12x2 + ::: + a1nxn + xn+1 = b1

>

>

<a21x1 + a22x2 + ::: + a2nxn + xn+2 = b2

(9:5)

>:::

>

>

:am1x1 + am2x2 + ::: + amnxn + xn+m = bm

xj > 0 j = 1; 2; :::; n + m (9:6)

Величина M выбирается очень большим положительным числом, а единичные векторы

An+1; :::; An+m

образуют искусственный базис.

Теорема. Если в оптимальном плане X = (x1; x2; :::; xn; 0; :::; 0) задачи (9:4) (9:6) все искусственные переменные равны 0, то план X является оптимальным планом исходной задачи. Если оптимальное решение задачи (9:4) (9:6) содержит хотя бы одно xn+i > 0, то исходная задача не имеет решения (она несовместна и не обладает планами)

57

28.2Двухэтапный метод

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

Пусть дана исходная задача (9:1) (9:3) (на минимум).

1.Ввводятся искуственные переменные для получения первоначального опорного плана. (Получается система равенств (9:5). Записывается новая целевая ф-я

f1 = xn+1 + xn+2 + ::: + xn+m (9:7)

предусматривающая минимзацию суммы искуственных переменных при ограничениях:

8

>a11x1 + a12x2 + ::: + a1nxn + xn+1 = b1

>

>

<a21x1 + a22x2 + ::: + a2nxn + xn+2 = b2

(9:8)

>:::

>

>

:am1x1 + am2x2 + ::: + amnxn + xn+m = bm

xj > 0 j = 0; 1; 2; :::; n (9:10)

Если в оптимальном плане задачи (9:7) (9:9) все искуственные переменные xn+1; xn+2; :::; xn+m равны 0 (в этом случае fmin = 0), то исходная задача имеет допустимое решение. В противном случае исходная задача не имеет допустимых решений и процесс вычислений на этом заканчивается.

2.Оптимальны план задачи (9:7) (9:9) полученный на этапе 1 используется в кач-ве первоначального опорного плана для решения исходной задачи (9:1) (9:3).

58

Часть VI

Вариационное исчисление

Определение 1. Функционалами называются переменные величины, значения которых определяются выбором одной или нескольких ф-ий. Например, функционалом является длина дуги l плоской или пространственной кривой, соединяющей две заданные точки: A(x0; y0) и B(x1; y1). Если задано у-ние кривой, то длина дуги равняется

x1

p

l[y(x)] = 1 + (y0)2dx

x0

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

Начало развиваться с 1696 года и оформилось в самостоятельную функциональную дисциплину после работ Л. Эйлера.

29 Вариация и ее свойства

Определение 1. Переменная величина v называется функционалом, зависящим от функции y(x), если каждой ф-и y(x) из некоторого класса ф-ий соотвествует значение v. Обозначается функционал как v = v[y(x)]. Аналогично определяются и функционалы, зависящие от нескольких ф-ий и функционалы, зависящие от функций нескольких независимых переменных.

Определение 2. Приращение или вариацией y аргумента y(x) функционала v называется разность между двумя ф-ями

y = y(x) y1(x)

При этом предполагается, что y(x) меняется произвольно в некотором классе функций. Определение 3. Функицонал v[y(x)] называется непрерывным, если малому измению y(x) соотвест-

вует малое изменение функционала v[y(x)].

Понятие малого изменения ф-и y(x) или близости кривых y(x) и y1(x) конкретизируется следующим образом.

Кривые y = y(x), y = y1(x) близки в смысле близости нулевого порядка, если модули разности

y(x) y1(x)

малы.

Кривые y = y(x), y = y1(x) близки в смысле близости первого порядка, если модули разности

y0(x) y10 (x)

малы.

Кривые y = y(x), y = y1(x) близки в смысле близости k-отого порядка, если модули разности

y(k)(x) y1(k)(x)

малы.

Теперь можно уточнить понятие непрерывности функционалов. Функционал v = v[y(x)]

непрерывен при y = y0(x) в смысле близости k-отого порядка, если для любого " существует такое> 0, что при выполнении условий

jy(x) y0(x)j <

jy0(x) y00 (x)j <

...

jy(k)(x) y0(k)(x)j <

имеет место неравенство

59

jv[y(x)] v[y0(x)]j < "

При этом подразумевается, что ф-я y(x) берется из класса ф-ий, на котором функционал v[y(x)] определен.

Определение 4. Линейным функционалом называется функционал L[y(x)], удовлетворяющий следующим условиям

L[cy(x)] = cL[y(x)]

где c - произвольная постоянная. И условию такому

L[y1(x) + y2(x)] = L[y1(x)] + L[y2(x)]

Определение 5. Если приращение функционала

v = v[y(x) + y] v[y(x)]

можно представить в виде

v = L[y(x); y] + [y(x); y] maxj yj

где L[y(x); y] - линейный по отношению к y функционал, maxj yj - максимальное значение модуляy и [y(x); y] ! 0, maxj yj ! 0, то линейная по отношению к y часть приращения функционала т.е. L[y(x); y] называется вариацией функционала и обозначается v.

Определение 6. Вариация функционала равна

@@ v[y(x) + y]

при = 0.

Функционал v[y(x)] достигает на кривой y = y0(x) максимума, если значение функционала v[y(x)] на любой близкой к y = y0(x) кривой небольше, чем v[y0(x)]

v = v[y(x)] v[y0(x)] 6 0

Аналогично определяется кривая, на которой функционал достигает минимума.

Теорема 8.1. Если функционал v[y(x)], имеющий вариацию, достигает минимума при y = y0(x), где y0(x) внутренняя точка области определения функционала, то при y = y0(x) вариация v = 0.

Док-во. При фиксированных y0(x) и y функционал

v[y0(x) + y] = ( )

является ф-ей , которая при = 0 по предположению достигает максимума или минимума. Следовательно, производная

0(0) = 0

или

@@ v[y0(x) + y] = 0

Это означает, что на кривых, на которых достигает максимум функционала его вариация равна 0. Все приведенны определения и теорема (8:1) почти без изменений переносятся на функционалы, зави-

сящие от нескольких неизвестных ф-ий.

v[y1(x); y2(x); :::; yn(x)]

или зависящие от одной или нескольких ф-ий многих переменных т.е.

v[z1(x1; x2; :::; xn)]

v[z1(x1; :::; xn); z2(x1; :::; xn); :::; zm(x1; :::; xn)]

60