В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 6
Текст из файла (страница 6)
Он применим в случае отсутствия вырождения. Это означает, что в полиэдре M , задаваемом уравнениями и неравенствами (26), из каждой вершины выходятn − r ребер (одномерных граней), где r – ранг матрицы (aij ).Это означает, что в каждой системе координат, если системанеравенств имеет вид (26), то b1 , . .
. , bm > 0.ПЕРВЫЙ ЭТАП – НАХОЖДЕНИЕ ВЕРШИНЫ ПОЛИЭДРАM.ШАГ 1.Составим матрицу из коэффициентовx1a11...am1am+1,1...............xna1n...amnb1...bmam+1,nbm+1(27)ШАГ 2.Если в некотором i-ом уравнении все коэффициентов aij 60, i = 1, . . . , m, то полиэдр M , задаваемый ограничениями (26)пуст. Действительно, в i-ом уравнении левая часть неположительна, а правая равна bi > 0.ШАГ 3.Пусть в i-ом уравнении коэффициент air > 0. Зафиксируем столбец с номером r и среди всех положительных коэффициентов этого столбца выберем тот, на котором достигаетсяЛинейное программированиеµminmj=1asr .43¶bj.
Предположим, что этот минимум достигается наajrДеля s-ое уравнение на asr можно считать, что asr = 1.Это означает, что все элементы s-ой строки матрицы (27) делятся на asr . Далее из каждой строки номером t = 1, . . . , s −1, s + 1, . . . , m + 1 вычитаем s-ую строку, умноженную на atr .В новой таблице переменная xr входит в коэффициентом 1 вs-уравнений, в остальные же уравнений и в z она входит с нулевым коэффициентом.Предложение 2.2.
При указанных преобразованиях, всесвободные члены уравнений, т.е. µкоэффициентыbi остаются¶bjнеотрицательными. Если minmдостигается на одномj=1ajrэлементе asr из r-го столбца, то все bi остаются положительными.Доказательство. Свободный член в t-ой строке имеетbsвид bt − at,r bs . Если t 6 m, то в силу выбора s имеем=asrbt. Поэтому если at,r > 0, то bt − at,r bs > 0. Еслиbs 6aµtr ¶bjminmдостигается на одном элементе asr , то при t 6= sj=1ajrполучаем bt − at,r bs > 0.Если же at,r 6 0, то bt − at,r bs > bt > 0.¤Таким образом, совершая многократно ШАГ 3 мы можемкак и методе Гаусса привести таблицу (27) к ступенчатому виду,т.е. каждое уравнение с номером j = 1, .
. . , m является выражением j-го главного неизвестного через свободные. При этомфункция в последней строек ненулевые коэффициенты стояттолько при свободных неизвестных.Придадим свободным неизвестным нулевые значения. Тогда значения главных неизвестных равны свободным членами потому положительны. Таким образом, построенное решениеX системы лежит в полиэдре M . По следствию 1.25 решение Xявляется вершиной полиэдра M и из решения X как вершиныполиэдра M выходит n − r ребер.44В. А.
АртамоновПредложение2.3. Пустьвсекоэффициентыam+1,1 , . . . , am+1,n > 0, причем если неизвестная xj главная,то am+1,j = 0. Тогда в точке X функция z(x) достигаетмаксимума, равного bm+1 .Доказательство. Заметим, что z = z(x) = −am+1,1 x1 −· · · − am+1,n xn + bm+1 , причем ненулевые коэффициенты стояттолько при свободных неизвестных. Это означает, что для любой точки u ∈ M имеем z(u) 6 z(X) = bm+1 . Максимальноезначение bm+1 достигается при нулевых значениях свободныхнеизвестных. При этом, если главная неизвестная xj находитсяв k-ом уравнении, то ее значение равно bk .¤Предположим теперь, что am+1,r < 0 для некоторого r.
Вэтом случае переходим ко второму этапу (см. ниже ШАГ 4).ВТОРОЙ ЭТАП – НАХОЖДЕНИЕ max z.ШАГ 4.Пусть am+1,r < 0. Рассмотрим коэффициенты при r-ой переменной.Предложение 2.4. Если все коэффициенты a1r , . . . , amrматрицы (27) отрицательны, то максимума у функции zнет.Доказательство. Придадим свободной переменной xrпроизвольное значение k > 0, а всем остальным свободнымпеременным придадим нулевое значение. Тогда значение главного неизвестного из i-го уравнения равно bi − air k > 0. Таким образом, получаем точку X(k) ∈ M . При этом z(X(k)) =−am+1,r k принимает сколь угодно большие значения.
Следовательно, функция z не имеет минимума на M .¤Пусть am+1,r < 0 и air > 0 для некоторого i = 1, . . . , m.Переходим в ШАГУ 3. Это соответствует выбору новых свободных и главных переменных.Предложение 2.5. При каждом преобразовании из ШАГА 3 значение свободного члена bm+1 увеличивается.Доказательство. Как и в предложении 2.2 свободныйчлен в z заменяется на bm+1 − am+1,r bs для некоторого s. Ноam+1,r < 0, а bs > 0. Поэтому bm+1 − am+1,r bs > bm+1 .¤Линейное программирование45Итак, мы совершаем различные выборы свободных и главных переменных, т.
е. получаем вершины из M . При этом мыникогда не вернемся к выбранной ранее вершине, поскольку накаждом шаге значение целевой функции z увеличивается. Итак,совершив конечное число шагов, мы перейдем к вершине M , вкоторой функция z достигает максимума, либо выясним, чтозадача не имеет решения.1.1. Пример. Решим задачу линейного программированияz = −2x1 + x2 + 3 → max2x1 + 3x2 > 7;x1 + x2 6 3;x1 , x2 > 0.Запишем ограничения в виде системы системы уравнений2x1 + 3x2 − x3 = 7;x1 + x2 + x4 = 3;x1 , x2 , x3 , x4 > 0.Таким образом, задача линейного программирования имеет видz = −2x1 + x2 + 3 → max2x1 + 3x2 − x3 = 7;x1 + 2x2 + x4 = 3;x1 , x2 , x3 , x4 > 0.(28)При этом свободные члены в системе ограничений, являющихсяуравнениями, должны быть положительными.ШАГ 1.
Составим таблицу из коэффициентовx1212x231-1x3-100x4010733ШАГ 2. Выбираем переменную x2 , чтобы в столбце коэффициентов, соответствующей этой переменной, присутствовал положительный коэффициент в какой-то строке, кроме последней.Далее во втором столбце выбираем такой коэффициент, чтобы46В. А. Артамоновотношение свободного члена к этому коэффициенту было быположительным и минимальным.
В данном случае берем коэффициент 3 из первой строки. Разделив элементы первой строкина 3, получаемx12/312x211-1x3 x4-1/3001007/333Вычтем из остальных строк первую строку, умноженную на соответствующий коэффициент. Как и при решении систем линейных уравнений, получаемx12/31/38/3x2100x3 x4-1/301/31-1/307/32/316/3ШАГ 3. Выбираем теперь третий столбец.
Находим аналогичный элемент 1/3 во второй строке. Умножим третью строку на1. Получаемx12/318/3x2100x3 x4-1/3013-1/307/3216/3Затем из остальных строк вычитаем вторую, умноженную насоответствующие коэффициенты. Получаемx1113x2100x3010x4131326Линейное программирование47Если при этом в последней строке все коэффициенты неотрицательны, то максимальное значение равно последнему элементу6 в последней строке.
При этом главными неизвестными в системе уравнений являются x2 , x3 , а свободными – x1 , x4 . Отсюдаmax f = 6. Этот экстремум достигается при x2 = 3, x3 = 2, x1 =x4 = 0.2. Симплекc-метод. Второй вариантВ этом разделе изложим другой вариант алгоритмасимплекс-метода.
Пусть система ограничений, задающих полиэдр M , имеет видx1 > 0, . . . , xn > 0;Pyi = fn+i (x) = j aij xj + bj > 0, 1 6 i 6 m(29)Необходимо найти min z, где z = p1 x1 + . . . + pn xn + q. Изложимдругой алгоритм решения этой задачи. Он также применим вслучае отсутствия вырождения.ПЕРВЫЙ ЭТАП – НАХОЖДЕНИЕ ВЕРШИНЫ ПОЛИЭДРАM . ШАГ 1.Составим матрицу из коэффициентовy1...ymzx1a11...am1p1...............xna1n...amnpmb1...bmq(30)ШАГ 2.Если все коэффициенты b1 , . . . , bm > 0, то точка O =(0, .
. . , 0) является вершиной. В этом случае переходим ко второму этапу (см. ниже ШАГ 6).ШАГ 3.Пусть br < 0 для некоторого r. Если все элементы r-ойстроки ar1 , . . . , arn матрицы (30) неположительны, то системанеравенств (29) несовместна и потому задача не имеет решения.ШАГ 4.48В.
А. АртамоновПусть br < 0 и ars > 0 для некоторого s. Выберем такой инbjдекс j, чтобы число − ajsбыло бы положительным и минимальным. В силу отсутствия зацикливания такой индекс j найдетсяоднозначно.ШАГ 5.Из j-го уравнения выразим xs черезx1 , . . . , xs−1 , yj , xs+1 , . . . , xn ,(31)и выразим все остальные функцииy1 , . .
. , yj−1 , yj+1 , . . . , ym , zчерез неизвестные (31).Предложение 2.6. При преобразовании, совершенном вшаге 5, для i 6= j все положительные коэффициенты bi остаются положительными, а отрицательные – отрицательными. Кроме того, значение свободного члена br увеличивается,а свободный член в j-ом уравнении становится положительным.Доказательство.
Пусть yj = aj1 + · · · + ajn xn + bj . Тогдаxs =aj1 x1ajn xnbjyj−− ··· −−.ajsajsajsajsЕсли же взять k-ую строку матрицы (30), k 6= j, то она имеетвид yk = ak1 + · · · + akn xn + bk . Переписав yk через неизвестные(31), получаем свободный членbk + aks (−bj).ajsЕсли bk > 0 и aks > 0, тоbk + aks (−bj) > bk > 0.ajsЕсли bk > 0 и aks < 0, тоbk + aks (−bj)>0ajs(32)Линейное программирование49в силу выбора j и отсутствия вырождения.
Если же bk < 0, топри aks < 0bjbk + aks (−) < bk < 0.ajsЕсли bk < 0 и aks > 0, тоbjbk + aks (−) < 0.ajsв силу выбора j и отсутствия вырождения. Кроме того, приk = r 6= j по (32) получаемbj0 > br + ars (−) > br ,ajsпоскольку br < 0 и ars > 0. Кроме того, коэффициент bj замеbjняется на − ajs> 0. Отсюда вытекает утверждение.¤По предложению 2.6 получаем, что после ШАГА 5 коэффициент br увеличивается, причем если j = r, то коэффициент br становится положительными. При этом от набораx1 , . . . , xs , . . . , xn в верхней строке (30) мы перешли у набору x1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
