Методические указания и варианты индивидуальных заданий для студентов заочного факультета, страница 3

Таблица 1

			....
			....
			....
....	....	....	....	....	....
F			....

Здесь  имена базисных переменных. Последняя строка таблицы соответствует равенству .

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

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

Легко убедиться в верности следующих условий допустимости и оптимальности базисных решений

Условие допустимости.

Базисное решение, порождаемое базисной симплекс-таблицей, допустимо, если все элементы столбца свободных членов неотрицательны: , .

Условие оптимальности.

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

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

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

при ограничениях (12) и .

Решение. Соответствующая симплекс таблица будет иметь вид:

Таблица 2

Базисным решением задачи будет матрица . Оно будет допустимым, если  и оптимальным, если . При выполнении этих условий минимальное значение функции F будет равно .

Преобразование симплекс таблиц

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

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

Проверка оптимальности и выбор генерального элемента симплекс таблицы

·  Если все элементы последней строки таблицы, кроме последнего, неположительные, то таблица порождает оптимальное базисное решение.

·  За генеральный столбец берётся тот столбец таблицы, кроме последнего, в последней строке которого стоит положительный элемент.

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

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