Оптимизационные модели. Метод искусственного базиса (М-метод)

Рассмотрим  суть симплекс-метода. Если в системе (2.2) m<n и все m уравнений линейно независимы, иначе ранг системы равен m. Тогда система имеет бесконечное множество решений.  Систему (2.2) можно разрешить относительно m переменных, которым в матрице системы соответствуют линейно независимые векторы-столбцы. Обозначив эти переменные через x₁,…,x_m ,выразим их через свободные переменные x_m+1,…,x_n :

x_i = b_i0 -∑ b_ij x_m+1    (i=1,..,m)                    (2.4)

Подставив значения x_i в целевую функцию (2.1), получаем:

f=b₀₀- ∑ b_0j x_m+j                                            (2.5)

Значения  базисных переменных x_i  и целевой функции f полностью определяются значениями свободных переменных x_m+j .

Положим, что в (2.4) все b_i0>0. Тогда план x₀=(b₁₀;…;b_m0;0…;0), полученный при нулевых значениях свободных переменных x_m+j, будет невырожденным опорным, а отвечающее ему значение функции f равно, как видно из (2.5), b_00.

Опорный план x₀ соответствует базису Б₀={x₁;…;x_m}.Для получения другого опорного плана преобразовывают базис Б₀  в новый базис Б₁ , удаляя из Б₀ одну переменную и вводя  вместо нее другую из группы свободных. При этом в базисе Б₁ опорному плану x₁ соответствует значение f(x₁), не меньшее   f(x₀)_. Действуя таким образом, переходят к близкому к оптимальному плану. Ввиду того что опорных планов не более С  ,через конечное число шагов либо приходят к оптимальному плану, либо устанавливают, что задача неразрешима.

2.2  Построение начального опорного  решения.

Решение задач линейного программирования вручную наиболее рационально можно  выполнять именно в табличной  форме. В таблицу вписывают систему ограничительных уравнений и целевую функцию в виде выражений (2.4), (2.5), разрешенных относительно начального базиса Б_о= {х₁; ...; х_т}  (табл. 2.). Левый столбец занимают базисные переменные и целевая функция, а верхнюю строку — свободные переменные . Нижнюю   строку,   в которую вписаны коэффициенты целевой функции f, называют f- строкой или строкой целевой функции.. За столбцом базисных переменных следует столбец свободных членов. Иногда f-строку помещают сразу же за заглавной строкой, а столбец свободных членов в конце; таблицы. Таблицы описанного вида называются симплексными.

                                                                                    Таблица 2

Используются  и другие формы симплексных таблиц, но принятая нами форма является наиболее компактной и наглядной. В ней содержится вся необходимая информация о ходе решения задачи. Если, как предполагалось выше, все b_i0>0, то при нулевых значениях верхних (свободных) переменных столбец свободных членов дает значения базисных переменных опорного плана x_о= (b₁₀;…;b_m0;0; ... 0) и соответствующее значение b₀₀ целевой функции: f(х₀) = b₀₀.

От табличной  записи легко перейти к обычной  записи уравнений. Для этого надо умножить элементы b_kj k-й строки на соответствующие переменные, стоящие в заглавной строке (-x_m+i), полученные произведения сложить и сумму приравнять x_kТогда b_ko*1   +  b_k1  (—x_m+l)+  … +b_ks{—x_m+s)+   ...   + b_k,_n-m(—x_n) =x_k  или    x_i = b_i0 -∑ b_ij x_{m+1   .}

2.3. Геометрическая интерпретация  симплексного метода.

Пусть область допустимых решений  изображается многоугольником AВCDECH Предположим, чтo его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать семь допустимых базисных решений, соответетвующих семи угловым точкам многоугольника из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем - к оптимальной точке С.

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

Идея последовательного улучшения  решения легла в основу универсального метода решения задач линейного  программирования - симплексного метода.

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

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

• способ определения какого-либо первоначального допустимого базисного решения задачи;

• правило перехода к лучшему (точнее, не худшему) решению;

• критерий проверки оnтимальности найденного решения.

Для использования  симплексного метода задача линейного  программирования должна быть приведена  к каноническому виду, т.е. система  ограничений должна быть представлена в виде уравнений.

2.4. Определение первоначального допустимого базисного решения

В рассмотренных выше примерах оптимальное  решение получено путем последовательного перехода от первоначального допустимого базисного решения к следуощему "лучшему", и так  до достижения критерия оптимальности. Однако нe всегда на первом же шаге получается допустимое базисное решение..

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

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

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

Сформулируем алгоритм получения первоначального допустимого базисного решения:

1. Если каждая дополнительная переменная входит в уравнение с тем же знаком, что и свободный член, стояший в правой части уравнения, то дополнительиые переменные можно брать в качестве основных на I шаге. При этом получится допустимое базисное решение.

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

3. Если  базисное решение недопустимое, а в уравнении, содержащем отрицательный свободный член, отсутствует неосновная переменная с положительным коэффициентом, то в этом случае допустимое базисное решение получить невозможно, т.е.  условия задачи противоречивы.

2.5. Симплексные таблицы

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

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