Отыскание начального опорного плана методом искусственного базиса

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

Пусть исходная ЗЛП имеет каноническую форму записи:

;

где ,

.

Если ни одно из ограничений не имеет предпочтительной переменной, то М-задача запишется так:

;

,

,

.

Тогда начальный опорный план этой задачи: .

Если некоторое уравнение имеет предпочтительный вид, то в него не следует вводить искусственную переменную.

Например, воспользуемся канонической формой записи ЗЛП примера 2 и найдем начальный опорный план методом искусственного базиса.

Составим М-задачу:

;

Тогда начальный опорный план: , значение целевой функции на этом плане:

.

Отыскание начального опорного плана путем преобразования таблицы Жордана

Для заполнения таблицы Жордана каноническую форму ЗЛП преобразовываем к следующему виду:

(2.11)

(2.12)

где все .

Таблица Жордана содержит столбцов, где – число переменных, – число переменных в предпочтительном виде и строк, где – число ограничений-равенств. В столбце «БП» записываются базисные (предпочтительные) переменные. Если ограничение не имеет предпочтительной переменной, то записывается 0. Столбец «1» – столбец свободных членов системы ограничений (2.12) а в -строке – элемент из (2.11). Остальные столбцы «СП», в основной части которых находится элементы из системы (2.12). В -строке, в столбцах «СП», записываются коэффициенты при свободных переменных, стоящие в скобках выражения (2.11). Каждому ограничению-равенству из системы (2.12) соответствует строка основной части таблицы. Целевой функции (2.11) соответствует последняя строка таблицы (таблица 4).

Таблица 4

				СП
БП	1		…		...
0			…		...
...	...	...	…	...	....	...
0			…		...
...	...	...	…	...	...	...
0			…		...
			…		...

Для нахождения начального опорного плана необходимо в результате Жордановых преобразований избавиться от нулей в первом столбце таблицы.

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

Пусть s-ый столбец будет разрешающим, тогда если для , то – разрешающий элемент.