Линейное программирование. Геометрическая интерпретация и графический метод решения задачи линейного программирования, страница 12

Таблица 2.2

CB	XB	B	2	1	0
			A1	A2	A3
0	x3	6	2	3	1
	D	0	-2	1	0

Рассчитаем значения оценок:

D₁ = 0×2 – 2 = -2 ;  D₂ = 0×3 –1 = -1 ;  D₃  = 0×1 – 0 = 0 .

Поскольку не все D_j  ³ 0, то найденный опорный план неоптимален.

Наибольшее по абсолютной величине значение D₁= -2. Поэтому выбираем первый столбец в качестве ведущего (s=1). Поскольку в данной задаче в матрице ограничений имеется только одна строка, то принимаем ее в качестве ведущей. В соответствии с замечанием 2.18 будем вести нумерация строк по номерам базисных переменных. (Тогда  r =3). Ведущий элемент a₃₁ =2.

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

Таблица 2.3

В этой таблице в качестве базисной фигурирует переменная x₁. Вычисляем значения оценок:

D₁ = 2×1 – 2 = 0 ;  D₂ = 2×(3/2) –1 = 2 ;  D₃  = 2×(1/2) – 0 = 1.

Поскольку все D_j  ³ 0 , то найденный опорный план

X = (3 ; 0 ; 0 )

оптимален. Переходя к исходной задаче в стандартной форме, получаем оптимальный план

X_опт = (3 ; 0 ) .

При этом z_опт = 6.

Рис. 2.5 иллюстрирует геометрическую интерпретацию решения задачи симплекс-методом. Допустимое множество решений расширенной задачи представляет собой треугольник ABC. Его проекцией на подпространство исходных переменных (x₁0x₂) является многоугольник (треугольник) A0B. В результате выполнения одной итерации симплекс-метода был осуществлен переход от одного опорного плана   задачи (с базисной переменной x₃) к другому (с базисной переменной x₁ ). Геометрически это соответствует переходу от вершины C к вершине А.

Остановимся далее на некоторых вопросах решения задачи минимизации.

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

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

          2.6. Двойственность в линейном программировании.

С каждой задачей ЛП тесно связана другая задача, называемая двойственной. Первоначальная задача называется исходной. Рассматриваемые задачи называются также парой взаимодвойственных (или взаимно сопряженных) задач.

Рассмотрим стандартную задачу линейного программирования

                                 max z = c₁x₁+ c₂x₂+…+c_nx_{n  ,}

                                 a₁₁x₁+a₁₂x₂+…+a_1nx_n  £ b_{1  ,}

                                 a₂₁x₁+a₂₂x₂+…+a_2nx_n  £ b_{2  ,}

.  .   .   .   .   .   .   .   .   .   .                                      (2.25)

                                 a_m1x₁+a_m2x₂+…+a_mnx_n  £ b_{m ,}

                                 x₁ ³0, x₂ ³0, …, x_n ³0 .

или в матричной форме:

max CX ; AX £B ; X ³0.                                      (2.26)