Симплекс – метод

2.4.1.Формирование базиса

Прежде всего, формируем матрицу задачи, каждая строка матрицы отвечает одному ограничению, а последняя строка содержит коэффициенты целевой функции(целевая строка), каждый столбец матрицы отвечает одной переменной. Используя процедуру Гаусса, строим базис – такой набор столбцов (переменных), в каждом из которых одна единица, а все остальные – нули. При этом базисных столбцов (базисных переменных) столько, сколько строк в матрице. Каждой строке матрицы отвечает тот из базисных столбцов, у которого в этой строке единица. Если матрица получилась преобразованием из симметричной задачи, базис есть с самого начала.

Значение любой базисной переменной равно правой части той строки, в которой у базисного столбца единица(такая строка одна) Все небазисные переменные равны нулю. Следовательно построение базиса эквивалентно нахождению угловой точки (имеем k ограничений-равенств, кроме того, n-k небазисных переменных равны 0, значит n-k неравенств x_i ≥0 стали равенствами x_i =0, итого n равенств в n–мерном пространстве описывают точку-вершину).

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

2.4.2 Выбор нового базисного столбца

Новый базисный столбец (новая ненулевая переменная) выбирается из тех небазисных столбцов, у которых коэффициент в целевой строке больше нуля; если таких столбцов нет – задача решена.

Далее для каждого из таких столбцов вычисляем длину шага.

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

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

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

Это произведение равно возможному приросту целевой функции при условии, что данная переменная из небазисной (нулевой) станет базисной (получит ненулевое значение, равное длине шага).

Новым базисным столбцом (и, соответственно, новой базисной переменной) будет тот, кто обеспечивает наибольший прирост целевой функции.

Новый базисный столбец с помощью шага процедуры Гаусса превращаем в базисный (одна единица, остальные нули) причем единицей в новом базисном столбце становится ведущий элемент этого столбца(остальные станут нулями).

Процедура продолжается до тех пор, пока в самой нижней строке (строке целевой функции) остаются положительные элементы.