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

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

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

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

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

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

x_i = b_io -b_is x_{m + s} (i=l, ..., m)

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

x_d =b_do — b_ds x_m+s ,

…………………..

x_k =b_k0 - b_ks x_m+s ,

………………….

x_p =b_p0 – b_ps x_m+s .

Базисные переменные х_d , ..., x_k , ..., x_p будут оставаться неотрицательными до тех пор, пока x_{m + s} удовлетворяет системе неравенств

b_do - b_ds x_m+s >0, x_m+s <b_do /b_ds

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

b_k0 - b_ks x_{m +s} >0 илиx_m+s < b_ko /b_ks

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

b_p0 – b_ps x_m+s >0 x_m+s < b_po /b_ps

т. е. приx_m+s <min {b_do /b_ds ; ...; b_k0 /b_ks ; ...; b_p0 /b_pS }.

Пусть наименьшая из дробей b_io /b_is соответствует i = k, т.е.

min { b_io /b_is }= b_k0 /b_ks .

Тогда можно сказать, что пока x_{m + s} не превышает величины b_{k 0} /b_ks , т. е. x_{m + s} <b_ko /b_ks , все базисные переменные x_i остаются неотрицательными. Если же x_{m + s} положить равной b_{k 0} /b_ks >0, то переменная х_k станет равной пулю: x_k = b_{k 0} — b_ks b_ko /b_ks =0, и тем самым будет произведено преобразование базиса Б_о = {х₁ ; ...; x_k ; ...; х_m } в новый базис, при котором переменная x_{m + s} из группы свободных переходит в базисные, а переменная х_k занимает место x_{m + s} в группе свободных. При этом все остальные свободные переменные по-прежнему равны нулю, а остальные базисные переменные по-прежнему положительны. Следовательно, базисный план х₁ в новом базисе Б₁ ={х₁ ; ...; x_{m + s} ; ...; x_m } будет иметь mположительных компонент и m-n нулевых. В плане x₁ некоторые базисные переменные могут принять нулевые значения в двух случаях:

1) когда в плане х₀ имеются базисные переменные, равные нулю;

2) когда наименьшая из дробей b_io /b_is будет соответствовать двум или нескольким номерам i.В нашем же случае она соответствует только i = k.

Переменная, подлежащая включению в базис, определяется отрицательным элементом f-строки. Из равенства f =b_oo – b_os x_{m + s} ясно, что при b_{0 s} <0 и фиксированном x_{m + s} >0, значение f(х) зависит от абсолютной величины коэффициента b_{0 s} : чем больше |b_{0 s} |, тем большее значение получит f(х) в новом базисе. Но из этого равенства видно также, что значение целевой функции в новом базисе зависит и от величины, принимаемой новой базисной переменной x_{m + s} . Будем выбирать переменную, вводимую в базис, ориентируясь лишь на отрицательные элементы f-строки. Поэтому, когда в f-строке несколько отрицательных элементов, в базис будем вводить переменную x_{m + j} ,соответствующую отрицательному элементу с наибольшей абсолютной величиной. Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу f-строки, мы обеспечиваем возрастание функции f.

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

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

Отметим, что нам уже известно значение новой базисной переменной x_{m + s} в новом опорном плане: оно равно b_ko /b_ks . Что же касается численных значений остальных базисных переменных в новом опорном плане и соответствующего значения f(х), то их можно найти лишь после того, как измененная система базисных переменных х₁ ;..., x_{m + s} ; ...,х_m будет выражена через измененную систему свободных переменных x_{m +1} ,…,x_k ,…, х_n . Для этого установим; правила, по которым осуществляется преобразование условий задачи от одного базиса к другому.

Коэффициент b_ks = 0 при x_{m + s} в этом уравнении называют разрешающим элементом. В равенстве (2.7) новая базисная переменная x_{m + s} выражена через свободные переменные, среди которых находится теперь и бывшая базисная переменная х_k . Таким образом, переменные x_{m + s} и x_k поменялись ролями.