Курсовая работа: Последовательность решения задач линейного программирования симплекс-методом

1) какую из переменных следует вывести из прежнего базиса, чтобы освободить место для переменной xm+s;

2) какое значение должна принимать новая базисная переменная xm+s в новом опорном плане.

Для решения поставленных вопросов допустим, что в равенствах (2.4) все xm+j, кроме xm+s, равны нулю. Тогда

xi = bio-bis xm+s (i=l, ..., m)

Из этих равенств видно, что с возрастанием xm+s значения тех базисных переменных хi для которых коэффициенты bis <0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты bis можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых bis>0. С увеличением xm+s значения этих переменных станут уменьшаться, и наступит момент, после которого они будут принимать отрицательные значения и перестанет выполняться условие (2.3). Этого допустить нельзя. Поэтому выясним, до какого предельного значения можно увеличивать xm+s, не нарушая условия неотрицательности базисных переменных. С этой целью выпишем из системы (2.6) те равенства, в которых bis>0. Допустим, что это касается равенств с номерами i=d,…,k,…,p:

xd=bdo— bds xm+s,

…………………..

xk=bk0- bks xm+s,

………………….

xp=bp0 – bps xm+s.

Базисные переменные хd, ..., xk, ..., xp будут оставаться неотрицательными до тех пор, пока xm+s удовлетворяет системе неравенств

bdo - bds xm+s>0, xm+s<bdo/bds

……………… ………………

 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 — bks bko/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 – bos xm+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- b0s xm+s.

Из равенств видно, что переменную xm+s можно произвольно увеличивать, не опасаясь нарушить условие неотрицательности базисных переменных xi ибо bi0>0, ( - bis)>0, а значит, и xi>0 при любых xm+s>0. В то же время, как видно, где (- b0s)>0, значение f(х) будет монотонно возрастать, и если

xm+.s→ , то и f→ .

4.4 Признак бесконечности множества оптимальных планов

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

Докажем это утверждение. Допустим, что содержащийся в табл. 2 опорный план является оптимальным. Обозначим его через х1*. Пусть при этом элемент bos f-строки равен нулю, а все остальные элементы этой строки положительны. Тогда, подвергнув табл. 2 симплексному преобразованию с s-м разрешающим столбцом, мы придем к другой таблице с новым опорным планом, который также будет оптимальным, поскольку элементы f-строки не изменились (нулевой элемент bos f-строки расположен в разрешающем столбце). Обозначим этот новый опорный оптимальный план через х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 Понятие о проблеме вырождения. Зацикливание

Рассматривая преобразование одного базиса в другой , мы предполагали, что среди симплексных отношений имеется только одно наименьшее, и поэтому вопрос о выборе переменной, исключаемой из базиса, решался однозначно. Но если допустить, что в разрешающем столбце min bi0/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