……………… ………………
bk0- bks xm +s >0 илиxm+s < bko/bks
……………… ………………
bp0 – bps xm+s>0 xm+s < bpo/bps
т. е. приxm+s<min {bdo/bds; ...; bk0/bks; ...; bp0/bpS}.
Пусть наименьшая из дробей bio/bisсоответствует i = k, т.е.
min { bio/bis }= bk0/bks.
Тогда можно сказать, что пока xm+s не превышает величины bk0/bks, т. е. xm+s<bko/bks, все базисные переменные xi остаются неотрицательными. Если же xm+sположить равной bk0/bks >0, то переменная хk станет равной пулю: xk= bk0 — bksbko/bks =0, и тем самым будет произведено преобразование базиса Бо= {х1; ...; xk; ...; хm} в новый базис, при котором переменная xm+sиз группы свободных переходит в базисные, а переменная хk занимает место xm+sв группе свободных. При этом все остальные свободные переменные по-прежнему равны нулю, а остальные базисные переменные по-прежнему положительны. Следовательно, базисный план х1 в новом базисе Б1={х1; ...; xm+s; ...; xm} будет иметь mположительных компонент и m-n нулевых. В плане x1 некоторые базисные переменные могут принять нулевые значения в двух случаях:
1) когда в плане х0 имеются базисные переменные, равные нулю;
2) когда наименьшая из дробей bio/bisбудет соответствовать двум или нескольким номерам i.В нашем же случае она соответствует только i = k.
Переменная, подлежащая включению в базис, определяется отрицательным элементом f-строки. Из равенства f =boo– bosxm+s ясно, что при b0s<0 и фиксированном xm+s>0, значение f(х) зависит от абсолютной величины коэффициента b0s: чем больше |b0s|, тем большее значение получит f(х) в новом базисе. Но из этого равенства видно также, что значение целевой функции в новом базисе зависит и от величины, принимаемой новой базисной переменной xm+s. Будем выбирать переменную, вводимую в базис, ориентируясь лишь на отрицательные элементы f-строки. Поэтому, когда в f-строке несколько отрицательных элементов, в базис будем вводить переменную xm+j,соответствующую отрицательному элементу с наибольшей абсолютной величиной. Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу f-строки, мы обеспечиваем возрастание функции f.
Немного сложней определяется переменная, подлежащая исключению из базиса. Для этого составляют отношения свободных членов к положительным элементам разрешающего столбца (такие отношения называют симплексными) и находят среди них наименьшее, которое и определяет строку (разрешающую), содержащую исключаемую переменную. Выбор переменной, исключаемой из базиса (или выбор разрешающей строки), по минимальному симплексному отношению гарантирует положительность базисных компонент в новом опорном плане.
Итак, мы доказали, что при указанных в признаке условиях действительно можно перейти от одного опорного плана к другому с большим значением целевой функции f(х).
Отметим, что нам уже известно значение новой базисной переменной xm+sв новом опорном плане: оно равно bko/bks. Что же касается численных значений остальных базисных переменных в новом опорном плане и соответствующего значения f(х), то их можно найти лишь после того, как измененная система базисных переменных х1;..., xm+s; ...,хm будет выражена через измененную систему свободных переменных xm+1,…,xk,…, хn. Для этого установим; правила, по которым осуществляется преобразование условий задачи от одного базиса к другому.
Коэффициент bks= 0 при xm+s в этом уравнении называют разрешающим элементом. В равенстве (2.7) новая базисная переменная xm+sвыражена через свободные переменные, среди которых находится теперь и бывшая базисная переменная хk. Таким образом, переменные xm+sи xk поменялись ролями.
Аналогично выразим через новый набор свободных переменных и остальные базисные переменные. С этой целью значение xm+sиз подставим в остальные равенств (обозначим fчерез x0,тогда равенство будет входить в систему при i= 0)
Приведение системы к новому базису называется симплексным преобразованием. Если симплексное преобразование рассматривать как формальную алгебраическую операцию, то можно заметить, что в результате этой операции происходит перераспределение ролей между двумя переменными, входящими в некоторую систему линейных функций: одна переменная из зависимых переходит в независимые, а другая, наоборот, - из независимых в зависимые. Такая операция известна в алгебре под названием шага жорданова исключения.
4.3 Признак неограниченности целевой функции на множестве планов
Если в f-строке симплекс-таблицы, содержащей некоторый опорный план, есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то целевая функция неограничена на множестве планов, т. е. f→ .
Докажем это утверждение. Пусть в табл. 2, например, b0s<0, и все элементы s-го столбца неположительны, т.е. bis<0 (i=1, ..., m). Тогда, положив в уравнениях (2.4) и (2.5) все свободные переменные, кроме xm+s, равными нулю, получим
xi = bio - bis xm+s (i=1, ..., m)
f=boo- b0sxm+s.
Из равенств видно, что переменную xm+sможно произвольно увеличивать, не опасаясь нарушить условие неотрицательности базисных переменных xi ибо bi0>0, ( - bis)>0, а значит, и xi>0 при любых xm+s>0. В то же время, как видно, где (- b0s)>0, значение f(х) будет монотонно возрастать, и если
xm+.s→ , то и f→ .
4.4 Признак бесконечности множества оптимальных планов
Если в f-строке симплекс-таблицы, содержащей оптимальный план, есть хотя бы один нулевой элемент (не считая свободного члена), то задача линейного программирования имеет бесконечное множество оптимальных планов.
Докажем это утверждение. Допустим, что содержащийся в табл. 2 опорный план является оптимальным. Обозначим его через х1*. Пусть при этом элемент bosf-строки равен нулю, а все остальные элементы этой строки положительны. Тогда, подвергнув табл. 2 симплексному преобразованию с s-м разрешающим столбцом, мы придем к другой таблице с новым опорным планом, который также будет оптимальным, поскольку элементы f-строки не изменились (нулевой элемент bosf-строки расположен в разрешающем столбце). Обозначим этот новый опорный оптимальный план через х2*. В соответствии с основной теоремой линейного программирования утверждаем, что любой план х*, являющийся выпуклой линейной комбинацией планов х1* и х2*, тоже будет оптимальным.
Если в f-строке будет t(t< n - m) нулевых элементов, то описанным способом можно получить, кроме х1*, еще t оптимальных опорных планов х2*; …;хt+1*, и тогда все бесконечное множество оптимальных планов запишем так:
x*=λ1x1*+…+λt+1xt+1*, где λl>0 (l=1,…,t+1) и λ1 +…+λt+1=1
Все множество оптимальных планов можно записать в виде
х*=λх1* + (1- λ) х2*
4.5 Понятие о проблеме вырождения. Зацикливание
Рассматривая преобразование одного базиса в другой , мы предполагали, что среди симплексных отношений имеется только одно наименьшее, и поэтому вопрос о выборе переменной, исключаемой из базиса, решался однозначно. Но если допустить, что в разрешающем столбце minbi0/bis достигается для нескольких индексов, например для i = l и i = t, т. е.
blobts = btobls
и разрешающей выбрана l-я строка. Тогда в новом опорном плане базисная переменная xtв соответствии с формулой (2.8) будет равна
b'to=(btobls — blobts): bis
Отсюда получаем xt = b't0 = 0. Таким образом, новый опорный план будет вырожденным. Задача линейного программирования, имеющая хотя бы один вырожденный опорный план, называется вырожденной.
Если при решении вырожденной задачи на очередном шаге симплексных преобразований разрешающей окажется строка, в которой свободный план равен нулю, то нулю будет равна и новая базисная компонента очередного опорного плана, тогда как значения остальных базисных компонент и целевой функции останутся прежними. Как правило, после нескольких шагов, сопровождающихся постоянством значения f, приходят все же к опорному плану с большим, чем прежде, значением f, и решение задачи благополучно заканчивается. Вместе с тем не исключается случай, когда после нескольких итераций получают уже встречавшийся базис, обнаруживается явление зацикливания в схеме расчетов. Одно из правил, позволяющих предотвратить это нежелательное явление, формулируется так: если в процессе симплексных преобразований появляется несколько минимальных симплексных отношений, то выбирают ту строку, для которой будет наименьшим отношение элементов первого столбца к разрешающему. Если при этом снова оказывается несколько минимальных отношений, то составляются отношения элементов следующего (второго) столбца, и так до тех пор, пока разрешающая строка не определится однозначно.
Итак, если задача линейного программирования вырожденная, то зацикливание возможно. Однако и теоретические исследования и накопившийся опыт решения прикладных задач показывают, что зацикливание может возникнуть лишь при весьма маловероятном сочетании различных особых условий. Известны лишь несколько специально составленных примеров, в процессе решения которых возникает зацикливание.
Заключение
Анализируя всё вышеизложенное, мы приходим к выводу о том, что при решении задач линейного программирования «вручную» оптимально использовать симплекс – метод. Поскольку он позволяет при верном составлении опорного плана решения быстро найти результат. Для этого необходимо знать последовательность шагов при этом методе и уметь производить различные преобразования в симплекс- таблице.
Список литературы
1 Ашманов С.А., Линейное программирование. М.: Наука 1981.
2. Кузнецов А.В., Холод Н.И., Математическое программирование. Мн.: Высшая школа 1984
3. Кузнецов А.В., Холод Н.И., Костевич Л.С., Руководство к решению задач по математическому программированию. Мн.: 2001
4. Кузнецов А.В., Холод Н.И., Новикова Т.И. сборник задач по математическому программированию. Мн.: Высшая школа 1994
5. Кузнецов А.В., Холод Н.И., Сокович В.А.., Высшая математика. Математическое программирование. Мн.: Высшая школа 1987