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

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

4.3 Признак неограниченности целевой функции на множестве планов

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

Докажем это утверждение. Пусть в табл. 2, например, b_{0 s} <0, и все элементы s-го столбца неположительны, т.е. b_is <0 (i=1, ..., m). Тогда, положив в уравнениях (2.4) и (2.5) все свободные переменные, кроме x_{m + s} , равными нулю, получим

x_i = b_io - b_is x_m+s (i=1, ..., m)

f=b_oo - b_{0 s} x_{m + s} .

Из равенств видно, что переменную x_{m + s} можно произвольно увеличивать, не опасаясь нарушить условие неотрицательности базисных переменных x_i ибо b_{i 0} >0, ( - b_is )>0, а значит, и x_i >0 при любых x_{m + s} >0. В то же время, как видно, где (- b_{0 s} )>0, значение f(х) будет монотонно возрастать, и если

x_{m +. s} → , то и f→ .

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

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

Докажем это утверждение. Допустим, что содержащийся в табл. 2 опорный план является оптимальным. Обозначим его через х₁ *. Пусть при этом элемент b_os f-строки равен нулю, а все остальные элементы этой строки положительны. Тогда, подвергнув табл. 2 симплексному преобразованию с s-м разрешающим столбцом, мы придем к другой таблице с новым опорным планом, который также будет оптимальным, поскольку элементы f-строки не изменились (нулевой элемент b_os f-строки расположен в разрешающем столбце). Обозначим этот новый опорный оптимальный план через х₂ *. В соответствии с основной теоремой линейного программирования утверждаем, что любой план х*, являющийся выпуклой линейной комбинацией планов х₁ * и х₂ *, тоже будет оптимальным.

Если в f-строке будет t(t< n - m) нулевых элементов, то описанным способом можно получить, кроме х₁ *, еще t оптимальных опорных планов х₂ *; …;х_{t +1} *, и тогда все бесконечное множество оптимальных планов запишем так:

x*=λ₁ x₁ *+…+λ_{t +1} x_{t +1} *, где λ_l >0 (l=1,…,t+1) и λ₁ +…+λ_{t +1} =1

Все множество оптимальных планов можно записать в виде

х*=λх₁ * + (1- λ) х₂ *

4.5 Понятие о проблеме вырождения. Зацикливание

Рассматривая преобразование одного базиса в другой , мы предполагали, что среди симплексных отношений имеется только одно наименьшее, и поэтому вопрос о выборе переменной, исключаемой из базиса, решался однозначно. Но если допустить, что в разрешающем столбце minb_{i 0} /b_is достигается для нескольких индексов, например для i = l и i = t, т. е.

b_lo b_ts = b_to b_ls

и разрешающей выбрана l-я строка. Тогда в новом опорном плане базисная переменная x_t в соответствии с формулой (2.8) будет равна

b'_to =(b_to b_ls — b_lo b_ts ): b_is

Отсюда получаем x_t = b'_{t 0} = 0. Таким образом, новый опорный план будет вырожденным. Задача линейного программирования, имеющая хотя бы один вырожденный опорный план, называется вырожденной.

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

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

Заключение

Анализируя всё вышеизложенное, мы приходим к выводу о том, что при решении задач линейного программирования «вручную» оптимально использовать симплекс – метод. Поскольку он позволяет при верном составлении опорного плана решения быстро найти результат. Для этого необходимо знать последовательность шагов при этом методе и уметь производить различные преобразования в симплекс- таблице.

Список литературы

1 Ашманов С.А., Линейное программирование. М.: Наука 1981.

2. Кузнецов А.В., Холод Н.И., Математическое программирование. Мн.: Высшая школа 1984

3. Кузнецов А.В., Холод Н.И., Костевич Л.С., Руководство к решению задач по математическому программированию. Мн.: 2001