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

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

a_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.Исходная модель содержит все виды ограничений (общий случай).

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