12. Признак оптимальности. Определение начального базисного решения.

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

Он легко выводится из связи смежных решений. Пусть на k-й итерации получили базисное решение x^(k) с критерием L^(k). При смещении из этой вершины на ребро (см. рис.4.6 -а) решение изменяется согласно (4.11):

x^k+1_i=X^k_i-_ir, i=1, 2,…,m.

x^k+1_r=.

Используя приведенные соотношения, определим критерий в новом решении:

или, введя обозначения

(4.14)

(4.15)

получаем

(4.16)

Параметр Δ_r называют относительной оценкой переменной. Ее смысл очевиден, если вспомнить, что  - значение новой переменной. Δ_r показывает, как изменится значение критерия при введении единицы новой переменной (=1). Поэтому, если есть отрицательные оценки, текущее решение может быть улучшено при введении в число базисных соответствующей переменной.

Если же все оценки будут больше или равны нулю, то тогда ни одна переменная не может улучшить текущее решение, следовательно,

условие Δ_j0 и является признаком оптимальности.

Покажем, что для базисных переменных относительные оценки равны нулю. Так как базисный вектор не выражается через другие, то только один коэффициент _rr=1, остальные равны нулю. Из (4.14) следует z_r=C_r, а из (4.15) - Δ_r=0. Таким образом, достаточно проверять знаки оценок только небазисных переменных.

Полученным формулам можно дать экономическую интерпретацию.

Пусть рассматривается задача планирования, в которой Х_j – количество продукции j-го вида, C_j – стоимость единицы произведенной продукции.

Тогда X⁽⁰⁾ – план производства, включающий первые m видов продукции. Попытаемся изменить этот план. Включим в него еще один вид продукции r. Так как ресурсы не меняются, это возможно только при одновременном уменьшении продукции, входящей в план X⁽⁰⁾. Величина этого изменения определяется коэффициентами _ir Действительно, как следует из (4.11), _ir показывает, насколько должно измениться производство продукции i-го вида при введении в план единицы продукции r. В экономической литературе такой показатель называют маргинальной нормой замещения. Значит, объем выпуска каждого вида продукции сокращается на _ir, а суммарная стоимость на величину Поэтому Z_r трактуют как маргинальную цену (снижение стоимости произведенной продукции на каждую единицу продукции r). В то же время, единица продукции r дает прирост стоимости С_r, называемый маргинальным доходом. Очевидно, что если C_r>Z_r, то есть Δ_r<0, то такая корректировка плана выгодна.

Если несколько переменных имеют отрицательные оценки, то возникает необходимость выбора из них самой перспективной. Очевидно, что наибольшее улучшение критерия на очередном шаге даст переменная, для которой произведение ₀Δ_j минимально. Однако такой выбор требует большого объема вычислений, так как для каждой переменной с отрицательной оценкой требуется находить ₀, а таких переменных в реальной задаче могут быть тысячи. Поэтому обычно выбирают переменную с наименьшей оценкой.

Таким образом, укрупненно можно выделить следующие этапы симплекс-метода:

1. Построение начального неотрицательного базисного решения.

2. Анализ оценок. При этом возможны три ситуации:

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

б) имеются отрицательные оценки, но, по крайней мере, одной их них (например, Δ_j) соответствует вектор, для которого все коэффициенты разложения неположительны (_ij0). В этом случае  не ограничено сверху и, как следует из (4.16), критерий неограниченно возрастает. Решение прекращается.

в) для каждой отрицательной оценки есть _ij>0. Решение может быть улучшено выполнением 3 этапа.

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

Этапы 2 и 3 повторяются до выполнения одного из условий останова.

Из перечисленных этапов не раскрытым остался первый этап, рассматриваемый ниже.

Построение начального базисного решения

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

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

Рассмотрим возможные варианты построения начального решения.

1. Исходная модель представлена неравенствами “”:

.

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

Если положить x_j=0, j=1,2,…,n, то дополнительные переменные x_n+i=b_i0 (i=1,2,…,m) удовлетворяют всем требованиям допустимого базисного решения: выполняются все условия задачи и число базисных переменных равно m. Очевидно, что этому базисному решения соответствует единичный базис {A_i}⁽⁰⁾={A_n+1, A_n+2,…,A_n+m}. В этом случае не надо вычислять коэффициенты разложения небазисных векторов по базису. Действительно, в системе уранений

каждый коэффициент входит только в одно уравнение с множителем +1. Поэтому ее решением будет

_n+i,j= a_ij,

то есть коэффициенты разложения равны соответствующим компонентам раскладываемого вектора условий.

2. Исходная модель представлена неравенствами “”:

.

Тогда соответствующая каноническая модель

включает дополнительные переменные со знаком “минус”. Если из них образовать базисное решение, то оно будет недопустимым, так как из модели следует

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

В первом из них в каждое равенство канонической модели вводится искусственная переменная :

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

Этот прием очень простой, но приводит к значительному увеличению числа переменных. Второй вариант устраняет этот недостаток.

Найдем в канонической модели уравнение с наибольшей правой частью. Пусть таким будет последнее уравнение, то есть.

.

Вычитая из него по отдельности каждое уравнение (кроме его самого), получаем преобразованную систему

где

Е сли теперь положить x_j=0 (j=1,2,...,m) и x_n+m=0, то дополнительные переменные x_n+i=b^`_i0 (i=1,2,…,m-1) могут быть приняты в качестве базисных. Однако при этом нехватает одной базисной переменной и последнее уравнение не выполняется. Введем в него искусственную переменную x_m+n+1

которая и будет недостающей базисной переменной (x_m+n+1=b_m). Таким образом, получено искусственное базисное решение, содержащее независимо от числа ограничений только одну искусственную переменную. Соответствующий ему базис, как и ранее, является единичным:

.

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

, для первого варианта,

для второго варианта,

где М - большое положительное число, такое, что M>>max|C_j| (в задаче на минимум знак минус заменяется на плюс).

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

3.В исходной модели условия заданы в виде равенств

Для построения базисного решения введем в каждое равенство искусственную переменную:

Тогда базисное решение будет состоять из искусственных переменных базис – из единичных векторов при этих переменных, а исходный критерий модифицируется:

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

4.Исходная модель содержит все виды ограничений (общий случай).

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