Нахождение начального допустимого базисного решения

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

(1)

(2), , .

1. Составим расширенную матрицу из коэффициентов системы ограничений: . Методом Жордана - Гаусса приведем расширенную матрицу к разрешенному виду. Предположим, что в качестве разрешающих элементов выбраны коэффициенты соответствующие переменным . Тогда разрешенная матрица примет вид: .

Если количество ненулевых строк (ранг) полученной расширенной и основной (без столбца свободных членов) матрицы совпадает, то система (1) совместна (имеет решение).

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

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

4. Предположим, что после первого применения метода Жордана – Гаусса оказалось, что система (1) совместна, её ранг равен и все свободные члены неотрицательны. Тогда система ограничений, соответствующая разрешенной матрице примет вид:

(3)

Выразим переменные через остальные переменные :

(4)

Вид (3) и (4) называется допустимым для системы ограничений (2). При этом неизвестные называется базисным, а весь набор - базисом. Остальные переменные называются свободными.