4.2. СООТНОШЕНИЯ МЕЖДУ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧАМИ
Изменение коэффициентов целевой функции и ограничений задачи ЛП влияет на оптимальность и допустимость текущего оптимального решения. Поэтому необходимо выяснить, как вычисления в симплекс-методе зависят от изменений коэффициентов исходной задачи. В частности, следует выяснить, как от этих изменений зависят оптимальность и допустимость решения, представленного в виде симплекс-таблицы.
Наиболее компактный способ записи вычислений, производимых при симплекс-методе, заключается в использовании матриц. Для этого в начале данного раздела приведем краткий обзор действий над матрицами, а затем рассмотрим соотношение между оптимальными решениями прямой и двойственной задач.
4.2.1. Обзор простых матричных операций
Нам необходимы только три элементарные матричные операции: умножение вектор-строки на матрицу, умножение матрицы на вектор-столбец и умножение скаляра (числа) на матрицу. Для удобства мы сформулируем определение этих операций, а также некоторые другие основополагающие определения.1
1. Матрица А порядка тхп - это прямоугольный массив элементов с т строками и п столбцами.
2. Вектор-строка V размерности п - матрица порядка 1 х п.
3. Вектор-столбец Р размерности т - матрица порядка mxl.
Эти определения математически можно представить следующим образом.
| | | | а12 . | | | |
V = (i | ,,v2,. | ••.v„), А = | «2. | а21 . | а2п | , Р = | |
| | | | ат2 | | | |
Теперь определим три матричные операции умножения.
1. Умножение вектор-строки V на матрицу А: V х А. Эта операция определена только тогда, когда количество элементов в вектор-строке V равно числу строк в матрице А.
Например,
(11,22,33) 3 4
ч5 6)
VxA = Xv,,£vyi,2,...,£v,a,,
= (1x11 + 3x22 + 5x33, 2x11+4x22 + 6x33) = (242,308).
2. Умножение матрицы А на вектор-столбец Р: А х Р. Эта операция определена только тогда, когда количество столбцов матрицы А равно количеству элементов вектор-столбца Р.
1 В приложении А приведен более полный обзор теории матриц.
АхР =
Например,
1 3 5
2 4 6
11x1 + 22x3 + 33x5 11x2 + 22x4 + 33x6
242 308
Умножение скаляра на матрицу. При умножении скаляра (константы) а на матрицу А, ссА, получаем матрицу порядка т х п, у которой (i, ;)-й элемент равен aatj. Например, для а = 10 имеем
Л 2 Ъ\ (10 20 301 (10)
4 5 6) {40 50 60
В общем случае ссА = Аа. Этим же свойством обладает операция умножения вектора на скаляр: aV = Va и aP = Pa.
УПРАЖНЕНИЯ 4.2.1
1. Даны следующие матрицы.
fl 4
V,-(ll,22), V2 = (-1,-2,-3).
В каждом из ниже перечисленных примеров укажите, допустима ли такая матричная операция, и если допустима, вычислите ее результат.
a) AV,.
b) АР,.
c) АР2.
d) V,A.
e) V2A. О Р,Р2. g) V.P..
4.2.2. Структура симплекс-таблицы
В главе 3 мы ввели стандартную форму для симплекс-таблиц. Такой формат симплекс-таблиц будет использоваться и в этой главе.
На рис. 4.1 показано схематическое представление структуры начальной и общей симплекс-таблиц. В начальной таблице коэффициенты ограничений под базисными переменными образуют единичную матрицу (в единичной матрице все ко-
эффициенты на главной диагонали равны 1, а все внедиагональные - 0). Сохраняя ту же структуру таблицы, после серии симплекс-преобразований методом Га-усса-Жордана получим то, что называется обратной матрицей. Как будет показано далее в этой главе, обратная матрица играет ключевую роль при вычислении всех элементов симплекс-таблиц.
z-строка целевой функции
Начальные базисные переменные
Столбцы коэффициентов < ограничений
□
(Начальная таблица)
Единичная матрица
z-строка целевой функции
Начальные базисные переменные
Столбцы коэффициентов < ограничений
Обратная матрица
□
(Общая таблица)
Рис. 4.1. Схематическое представление начальной и общих симплекс-таблиц
УПРАЖНЕНИЯ 4.2.2
1. Вернитесь к таблице с оптимальным решением примера 3.3.1.
a) Определите в этой таблице обратную матрицу.
b) Покажите, что вектор значений в столбце "Решение" (без значения z-строки) равен произведению обратной матрицы на вектор правых частей исходных ограничений.
2. Повторите упражнение 1 для последней таблицы примера 3.4.1.
4.2.3. Оптимальное решение двойственной задачи
Прямая и двойственная задачи так тесно взаимосвязаны, что оптимальное решение одной задачи можно получить непосредственно (без дополнительных вычислений) из симплекс-таблицы, представляющей оптимальное решение другой. Покажем два метода получения этого результата.
Единичная матрица без дополнительных преобразований образуется только тогда, когда начальный базис составляют дополнительные остаточные переменные. - Прим. ред.