    
Раздел: Документация
0 ... 36 37 38 39 40 41 42 ... 162 Доказательство. Выразим переменную уравнения (17.1): г,, что соответствует г-й строке si-таблицы (17.3). Исключим , Ь., переменную г., из /-го уравнения в (17.1) (/ -ф Г): После раскрытия скобок и приведения подобных членов получим: что соответствует /-и строке в si-таблице (17.3). Утверждение доказано. Вернемся к симплекс-методу и рассмотрим его второй и третий этапы (О реализации первого этапа- нахождения начального опорного плана- будет сказано ниже.) Предположим, что уже найден некоторый опорный план а = (а,,а„ 0, 0) задачи (16.1) - (16.2), причем известны также линейные зависимости, выражающие базисные переменные л-1, ...,Х, И целевую функцию / через свободные переменные х, , х„ (для упрощения обозначений считаем, что в опорном плане а именно первые t координат соответствуют базисным переменным): Запишем уравнения (17.4) в форме si-таблицы (17.5). (17.4)
(17.5) Эту таблицу будем называть si-таблицей, соответствующей опорному плану а. В таблице первый столбец называется столбцом базисных переменных, второй - столбцом свободных членов, последняя строка Теорема 17.1. Пусть задана si-таблица, соответствующая опорному плану а. Если в/строке si-таблицы все элементы, не счиття свободного члена/,>, неотрицательны, то план а оптимален. Доказательство. Поскольку /,. , >0, ...,/„>О, х, . , >0, х„>0, то f=f0-(/; lXl • J+ ... +j;x„)<f0 для любых неотрицательных значений свободных переменных.означает оптимальность плана а. Теорема 17.2. Пусть задана si-таблица, соответствующая опорному плану а= (а,,..., а„ 0,0). Если существует такой элемент/;., что/,<0 и все />„<0, / = !,.../, то целевая функция задачи ()6.1)-(16.2) неограниченно возрастает на множестве планов. Доказательство. Положив все свободные переменные, кроме хя, равными нулю, получим .*,=«,г =1,/=-/>,,. Рассмотрим точку а ~ (а1:, а,, 0,..,, а3,..., 0), где а.,- любое положительное число, a; = a,; - bjS av, / = 1, ...,/. Так как при любом а, > 0 значения a\> 0, то точка а является планом задачи. Значение целевой функции для этого плана/a)=f0-J-a, неограниченно растет с ростом Теорема доказана. Теорема 17.3. Пусть задана si-таблица, соответствующая опорному плану а= (а,,а,, 0, 0). Если существует такой отрицательный элемент fs, для которого найдется элемент 6,ч > 0 (I <i<(), то существует такой новый опорный план а , что .Да )>/а). (К этому плану можно перейти с помощью жордановой перестановки.) Доказательство. Среди положительных элементов столбца, содержащего/, выберем элемент Ь,., с минимально возможными значениями --. (Если выбор неоднозначен, то выбираем любой из таких элементов.) Произведем жорданову перестановку с разрешающим элементом br, . Покажем, что в столбце свободных членов новой si-таблицы все элементы aj, а, останутся неотрицательными, причем новый свободный член f„ в /-строке будет не меньше /0. Согласно утверждению 17.1, аибоПустьЕслито a = a--=6 (---) , Вследствие выбора элемента О выполняется неравен- К К К ство ---->0 и поэтому а >0 . Если bis<0, то-:--*->(), так как а, >0, 6г( > О, и поэтому а, >0. Мы доказали, что столбец свободных членов новой si-таблицы задает опорный план a. f а . Значение целевой функции для этого плана 0, 0. Теорема доказана. Из теоремы 17.3 следует, что с помощью жордановых перестановок в соответствующих si-таблицах можно построить такую последовательность опорных планов задачи (16.1)-(16.2) а, а ,а ", что Да) <Д а) < ,/(а") < .... Эта последовательность может быть конечной или бесконечной. В первом случае с помощью теорем 17.1 и 17.2 или будет установлена оптимальность плана, или будет доказана неограниченность целевой функции. Второй случай может произойти из-за неоднозначности выбора разрешающего элемента для жордановой перестановки. В такой ситуации неко- торый опорный план будет повторяться, поскольку число опорных планов конечно. Однако существуют правила выбора разрешающего элемента, позволяющие избежать зацикливания. Мы не будем здесь останавливаться на этом, так как зацикливание в практических задачах встречается чрезвычайно редко и известны лишь искусственные примеры такого явления. Слсдствие 17.!. Если целевая функция/в задаче ЛП ограничена сверху (снизу) на множестве планов, то эта задача имеет оптимальныймаксимизи- рующий (минимизирующий) функцию/ Доказательство следствия дано в задаче TI7.2. Л теперь вернемся к первому этапу симплекс-метода. Построение начального опорного плана задачиможноприменив симплекс-метод к вспомогательной задаче (16.5) - (16.6). Действительно, не теряя общности можно считать, что в (16.6)(в противном случае соответствующие уравнения умножа- ются на -!). Поэтому очевиден начальный опорный "план (0, 0, О, с,, с,„) вспомогательной задачи, так как очевиден базис переменных yt... у,,,. Целевая функция g ограничена снизу на множестве плановПоэтому в силу следствия задача (16.5)- (16.6) имеет оптимальный опорный план, который можно найти симплекс-методом. Но согласно задаче T16.ll при непустом множестве планов (16.2) оптимальный опорный план р = (р,, .... р,„ у„ .... у,„) задачи (16,5)-(16.6) определяет опорный план а = (рь .... р„) задачи (16.1) - (16.2). Суммируя предыдущие результаты можно предложить следующий алгоритм симплекс-метода решения задачи- (16.2). Алгоритм 1.Решить вспомогательную задачу (16.5) - (16.6) и найти ее оптимальный опорный план Р = (Рь---, Р„, уг У™)- Если g(P) < 0, то задача (16.1) - (16.2) планов не имеет. Если g(p) = О, то план a =(pi , Р,,) является опорным планом задачи (16.1) - (16.2). Составить si-таблицу, соответствующую этому плану. 2.Рассмотреть элементы f-строки si-таблицы. Если все элементы f-строки, не считая свободного члена ГО. неотрицательны, то опорный план а оптимален. 3.Если весть отрицательный элемент fs, то рассмотреть элементы столбца, элемент fs. Если все элементы этого столбца неположительны, то целевая функция (16.1) не ограничена на множестве планов. 4.Если в рассматриваемом столбце есть положительные элементы, то произвести жорданову перестановку. В качестве разрешающего выбрать элемент brs, для которого выполняется соотношение = mm -. 5.Описанный процесс повторять до тех пор, пока не будет найден оптимальный опорный план или не будет установлена неограниченность целевой функции. 1 Так -422 3 0 ... 36 37 38 39 40 41 42 ... 162 |
||||||||||||||||||||||
