Область применимости.

Многие задачи линейного программирования сводятся к мини­мизации некоторой линейной функции. Задача минимизации переходит в задачу максимизации, если изменить знаки при всех коэффициентах в выражении для целевой функции. По отношению к полученной таким образом линейной форме крите­рий I (максимизация) по-прежнему оказывается применимым. Однако для целей дальнейшего рассмотрения представляется целесообраз­ным сформулировать критерий I и на тот случай, когда решается задача минимизации при сохранении целевой функции в ее перво­начальном виде.

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

Данную процедуру можно пояснить с помощью примера. Рассмо­трим следующую тривиальную задачу линейного программирования:

Минимизировать - 2x₁ + Зx₂ (1)

при условиях: 0 (2)

Можно приступить к решению этой задачи, изменив вначале как знаки в выражении (1), так и «смысл» оптимизации, т. е. написав вместо (1):

Максимизировать 2 x₁- 3х₂. (3)

При таком переходе оптимальные значения x₁ и х₂ не меняются. Тогда, действуя в соответствии с симплексным алгоритмом, изло­женным в предыдущем разделе, мы начали бы итерационный процесс с рассмотрения следующей системы уравнений:

х₀ - 2 x₁+3х₂ = 0 (строка 0),

1 x₁+ 1 x₃= 6 (строка 1), (4)

1x₂ +1х₄= 10 (строка 2).

При этом, согласно критерию I (максимизация), в базис вошла бы переменная x₁.

Однако, вместо того чтобы действовать по только что предложен­ной схеме, можно исходить непосредственно из (1) и после введения в рассмотрение переменной х₀ записать исходную систему уравнений в виде

х₀ +2 x₁-3х₂ = 0 (строка 0),

1 x₁+ 1 x₃= 6 (строка 1), (5)

1x₂ +1х₄= 10 (строка 2).

В этом случае был бы применим критерий I (минимизация) и на самой первой итерации переменная x₁ была бы выбрана в качестве базисной, так как в строке 0 коэффициент при х₁ равен +2.

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

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

1) симплексный алгоритм применим ко всем линейным оптими­зационным моделям;

2) ответ, полученный в результате заключительной итерации, является точным решением задачи.

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

Теорема о базисе. Если задача линейного программи­рования имеет конечное (ограниченное) оптимальное решение, то для нее существует базисное оптимальное решение.

Следует напомнить, что для линейной модели с т ограничениями базис представляет собой набор т переменных с однозначно опреде­ленными значениями, удовлетворяющими имеющимся ограничениям. При этом значения всех остальных переменных принимаются рав­ными нулю.

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

Откуда следует, что теорема о базисе справедлива? Доказатель­ство данной теоремы представляется излишним по той простой причи­не, что симплексный метод дает рецепт фактического построения оптимального базисного решения.

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

Не нашли, что искали? Воспользуйтесь поиском: