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

Начальное базисное решение может быть получено из модели, представленной в канонической форме. При этом выбор базисных переменных зависит от вида условий исходной модели, каждому условию соответствует своя базисная переменная (предполагается линейная независимость 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. Исходная модель - “³”: . каноническая модель:

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

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

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

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

При переходе от одного базисного решения к другому допустимое решение достигается только тогда, когда все искусственные переменные станут равными нулю. Для ускорения вывода этих переменных из числа базисных (обнуления) рекомендуется придавать им большой негативный вес путем модификации критерия: , для 1 варианта, для 2 варианта, где М - большое положительное число, такое, что M >>max| C _j|. Если при выполнении признака оптимальности хотя бы одна искусственная переменная останется положительной - задача неразрешима из-за противоречивости условий: не выполняться будут те условия, в которые входят ненулевые искусственные переменные.

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

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

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

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

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

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