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

1) просматривают строку, отвечающую какому-либо отрицательному свободному члену, например t-строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему столбец принимают за разрешающий (предполагая, что ограничения задачи совместны);

2) составляют отношения элементов столбца свободных членов к соответствующим элементам разрешающего столбца, имеющим одинаковые знаки (симплексные отношения);

3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р -строка;

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

4.1 Признак оптимальности опорного плана

Если в симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этот опорный план является оптимальным.. Пусть в f-строке табл. 2.b0j> (i=1, ..., n m). В опорном плане х0, содержащемся в этой таблице, значения всех свободных переменных xm+j равны нулю и f(х0) =b00. Если же увеличивать какую-либо из свободных переменных xm+j, то, как видно из равенства (2.5), в силу неотрицательности b0j значение f(х) начнет уменьшаться. Следовательно, при xо функция f(х) достигает наибольшей величины, а значит, х0 действительно является оптимальным опорным планом.

4.2 Возможность переход от одного опорного плана к другому

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

Докажем этот признак. Установим правила выбора переменных для такого преобразования начального базиса Бо с опорным планом х0 в новый базис Б1 с опорным планом х1 при котором; значение функции f увеличивается, т. е. f(xi)>f(x0). Тогда по правилу пересчета элементов из симплекс-таблицы преобразуем к новому базису, что позволит найти компоненты нового опорного плана.

Допустим, что в табл. 2.1, например, b0s<0, а среди элементов bis s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные хm+j кроме xm+s, равными нулю, получаем f = boo — bos xm+s . Из этого равенства видно, что при увеличении xm+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых xm+s принимает положительные значения, а все остальные компоненты xm+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Бо в новый базис Б1. В самом деле, если переменная xm+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане xо она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной xm+s. Но здесь предстоит решить два вопроса:

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