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

Симплекс-метод основан на переходах от одного допустимого базисного решения к другому (смежному). Как показано ранее, базисное решение включает 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.Исходная модель содержит все виды ограничений (общий случай).

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