Сборник задач по линейному программированию (стр. 11 )

В столбцах, соответствующим обозначениям в первых трёх строках записана наша система уравнений в предпочтительном виде; над символами прописаны значения коэффициентов целевой функции при соответствующих переменных 9,10,16,0,0,0.

В столбце-символы базисных переменных . Они расположены в соответствии с коэффициентами единичной матрицы системы уравнений.

В столбце - значения коэффициентов целевой функции для базисных переменных. Т. к. базисные переменные в исходной таблице есть , то соответствующим коэффициенты равны нулю.

Последняя четвёртая строка заполняется в последнюю очередь. Это строка F или индексная строка. Её коэффициенты получают по формуле.

для колонки b,

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

Например:

в строке в колонке значение –9 получается как

в колонке :  

в колонке :

Полученное число в строкеи колонке является значением целевой функции для данного базисного решения системы ограничения.

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

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

1) Пусть исходное задание решается на максимум. Если для некоторого опорного плана все элементы индексной строки неотрицательны, то такой план оптимальный.

2) Пусть исходная задача решается на минимум. Если для некоторого опорного плана все элементы индексной строки неположительные, то такой план оптимальный.

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

       Найдём в индексной строке число, наиболее сильно отличающегося от условия неотрицательности. Это –16 в колонке . Значит, столбец будет разрешающим. В этом столбце среди положительных элементов матрицы система, т. е. среди  чисел 12,8,3 найдём разрешающий элемент. Для этого найдём симплексное отношение для этих чисел, т. е. отношение вида , т. е. и найдём среди них минимальное. Это . Значит, число 8 есть разрешающий элемент и вторая строка сверху будет разрешающей. По разрешающей строке определяем,  что из разряда базисных переходит в разряд свободных переменных, а по разрешающему столбцу находим, что х3 из свободных переходит в базисные. Проводим преобразование старой симплекс-таблицы 6,а) в новую  6,б). Преобразования проводится по методу Жордана – Гаусса. Это и есть симплексное преобразование.

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

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

Тогда в новой матрице:

Например: число 18 в колонке преобразуется как ;

Число 5 в колонке преобразуется как .