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

Предполагаем, что все добавочные переменные имеют  тот жe знак, что и свободные члены.

II. Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком:b_i=-c_i. В левом столбце таблицы записываем основные переменные (базис), в первой строке таблицы - все переменные (отмечая при этом основные), во втором столбце - свободные члены расширенной системы b₁, b₂, ... ,b_m. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты а_ij при переменных из расширенной системы. Далее таблица преобразуется пo определенным правилам.

Проверяем выполнение критерия оптимальности  при решении задачи на максимум - наличие в последней строке отрицательных коэффициентов b_i < 0 (с_i > 0). Если таких нет, то решение оптимально, достигнут mах F = с₀ (в левом нижнем углу таблицы), основные переменные принимают значения а_i0 (второй столбец), основные переменные равны 0, т.е. получаем оптимальное базисное решение.

IV. Если критерий оптимальности нe выполнен, то наибольший пo модулю отрицательный коэффициент b_i < 0 в последней строке определяет разрешаюший столбец s.

Составляем  оценочные ограничения каждой строки пo следующим правилам:

1) , если b_i и a_iS имеют разные знаки;

2) , если b_i = 0 и a_iS < 0;

3) , если а_is = 0;

4) 0, если b_i = 0 и a_iS > 0;

5) , если а_iо и a_iS имеют одинаковые знаки.

Определяем min { }. Если конечного минимума нет, то задача не имеет конечного оптимума ( F„,_nx = ). Если минимум конечен, то выбираем строку q, на которой он достигается (любую, если их несколько), и называем ее разрешающей строкой. На пересечении разрешающих строки и столбца находится разрешающий элемент a_qs.

V. Переходим к следующей таблице пo правилам:

а) в левом  столбце записываем новый базис: вместо основной переменной х_q - переменную x_s;

б) в столбцах, соответствующих основным переменным, проставляем нули и единицы: 1 - против "своей" основной переменной, 0 - против "чужой" основной переменной, 0 - в последней строке для всех основных переменных;

в) новую  строку с номером q получаем из старой делением на разрешающий элемент a_qs;

г) все  остальные элементы вычисляем пo правилу nрямоугольника:

Далее переходим к п. III алгоритма.

 

 

 

 

 

2.6. Метод искусственного базиса.

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

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

Симплекс-таблица, которая составляется в процессе решения, используя метод  искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F, а другая – для составляющей M. При составлении симплекс таблицы полагают что исходные переменные являются небазисными, адополнительные (x_n+m) и искусственные (R_i)- базисными.

Исходная таблица для "Метода искусственного базиса" имеет следующий  вид:

 

Элементы дополнительной строки M расчитываются как сумма соответствующих  коэффициентов условий-равенств (условий  в которые после приведения к  каноническому виду введены переменные R_i) взятая с противоположным знаком.

 

2.6.1 Каноническая форма.

Для применения симплекс-метода задачу следует записать в канонической форме:

 

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

Переход к канонической форме записи производиться  с помощью следующих простых  действий.

1. Если требуется найти минимум f, то заменяя f на –f, переходя к задаче максимизации, так как min f =- max (-f).
2. Если ограничение содержит неравенство со знаком <=, то от него переходя к уравнению, добавляя в левую часть ограничения дополнительную неотрицательную переменную.
3. Если ограничение содержит неравенство со знаком >=, то от него переходя к уравнению, вычитая из левой части ограничения дополнительную неотрицательную переменную.
4. Если в задаче какая либо из переменных произвольна, то от нее избавляются, заменяя ее разностью двух других неотрицательных переменных. Например, для произвольной переменной x_k,   x_k= , где >=0, >=0.

Предположим, что все уравнения  (1) линейно  независимы, то есть выражают независимые  друг от друга условия задачи. Если это не так, то лишние уравнения нужно  просто исключать. Задачу (1) имеет смысл  решать, когда число уравнений  в системе ограничений (1) меньше числа входящих в них неизвестных: m < n.

В противном  случае, если m = n, то система (1) переопределена и не имеет решений.

Если  m < n, то система (1) имеет бесконечное множество решений и среди них можно выбрать оптимальное, доставляющее максимум функции (1).

Задача (1) называется основной задачей линейного  программирования (ОЗЛП).

ОЗЛП  не всегда имеет решение.

Во-первых, уравнения (1) могут оказаться несовместными (cистема линейных уравнений называется несовместной, если она не имеет решений).

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

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

2.6.2. Алгоритм метода искусственного базиса.

Подготовительный этап

Приводим задачу ЛП  к каноническому виду

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n+x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n+x_n+2=b₂

.........................................

a_i,1x₁+a_i,2x₂+...a_i,nx_n+R_i=b_i

.......................................