презентация_Л2-3

Подставим это значение yk в остальные уравнения (7):

Итоговые соотношения для преобразования симплекс-таблицы при замене базиса

Сравнивая (7) и (8), преобразуем коэффициенты в симплекс-таблице при выводе переменной yk из числа

свободных, а переменной xr – из числа базисных:

Столбец с номером k – разрешающий столбец

Строка с номером r – разрешающая строка

Элемент srk – разрешающий элемент

ЭТАП 1

Решение системы уравнений m-го порядка (если из матрицы исходной системы нельзя выделить диагональную квадратную подматрицу), в результате этого решения некоторые из перемененных могут оказаться отрицательными.

С помощью процедуры Гаусса (прямой ход) матрицу системы привести к треугольному виду, определить свободные переменные и вывести их в правую часть

Оставшиеся базисные переменные выразить через свободные (обратный ход)

Положив свободные переменные = 0 и вычислив базисные, найти некоторое решение системы

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

Для замены переменных можно использовать алго-

ритм (9), добавив к нему правила выбора разре-

шающей строки и разрешающего столбца

Правило выбора разрешающего столбца

Проводится анализ столбца свободных членов. Пусть есть строка i0 таблицы sij (1 i0 m) такая,

что si 00 0 (отрицательный свободный член, указывающий, что решение недопустимо).

В строке i0 , начиная с первого столбца ищется отрицательный элемент. Пусть это элемент si 0,k . Тогда

k– номер разрешающего столбца.

Если все элементы строки i0 неотрицательны, кроме свободного числа, то задача не имеет допустимых решений

Правило выбора разрешающей строки

Для нахождения разрешающей строки рассматриваются отношения si0 / sik , i 1, m.

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

Строка, в которой стоит элемент, реализующий это отношение, берется в качестве разрешающей.

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

Когда ограничения в исходной задаче линейного программирования заданы в виде неравенств (1), преобразование этих неравенств в равенства (3) осуществляют посредством введения дополнительных переменных.

Именно эти дополнительные переменные удобно взять в качестве базисных и разрешить относительно них уравнения, поскольку каждая из дополнительных переменных входит только в одно уравнение.