Симметричные двойственные задачи
Разновидностью двойственных задач линейного , программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Исходная задача. Найти матрицу-столбец Х = (x1, x2, …, xn), которая удовлетворяет системе ограничений
(1.12). АХ>А0, Х>0
и минимизирует линейную функцию Z = СХ.
Двойственная задача. Найти матрицу-строку Y = (y1, y2, …, yn), которая удовлетворяет системе ограничений YA £ C, Y ³ 0 и максимизирует линейную функцию f = YA 0.
Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана.
Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.
Исходная задача. Найти минимальное значение линейной функции Z = x1 + 2x2 + 3x3 при ограничениях
2x1 + 2x2 - x3 ³ 2,
x1 - x2 - 4x3 £ -3, xi ³ 0 (i=1,2,3)
x1 + x2 - 2x3 ³ 6,
2x1 + x2 - 2x3 ³ 3,
|
|
Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1.
Двойственная задача. Найти максимум линейной функции f = 2y1+ 3y2 + 6y3 + 3y4 при ограничениях
2y1 - y2 + y3 + 2y4 £ 1,
2y1 + y2 + y3 + y4 ³ 2,
-y1+ 4y2 - 2y3 - 2y4 ³ 3,
Для решения исходной задачи необходимо ввести четыре дополнительные переменные и после преобразования системы - одну искусственную. Таким образом, исходная симплексная таблица будет состоять из шести строк и девяти столбцов, элементы которых подлежат преобразованию.
Для решения двойственной задачи необходимо ввести три дополнительные переменные. Система ограничений не требует предварительных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов.
Двойственную задачу решаем симплексным методом (табл. 1.3).
Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), fmax = 21/2.
Оптимальный план исходной задачи находим, используя оценки (m + 1)-й строки последней итерации, стоящие в столбцах A5, A6, A7 : x1 = 3/2 + 0 = 3/2; x2 = 9/2 + 0 = 9/2; x3= 0+ 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Zmin =21/2.
|
|
Т а б л и ц а 1.3
i | Базис | С базиса | A0 | 2 | 3 | 6 | 3 | 0 | 0 | 0 | ||||||||||
A1 | A2 | A3 | A4 | A5 | A6 | A7 | ||||||||||||||
1 2 3 | A5 A3 A7 | 0 0 0 | 1 2 3 | 2 2 -1 | -1 1 4 | 1 1 -2 | 2 -1 -2 | 1 0 0 | 0 1 0 | 0 0 1 | ||||||||||
m + 1 | Zi - Cj | 0 | -2 | -3 | -6 | -3 | 0 | 0 | 0 | |||||||||||
1 2 3 | A3 A6 A7 | 6 0 0 | 1 1 5 | 2 0 3 | -1 2 6 | 1 0 0 | 2 -1 2 | 1 -1 2 | 0 1 0 | 0 0 1 | ||||||||||
m + 1 | Zi - Cj | 6 | 10 | -9 | 0 | 9 | 6 | 0 | 0 | |||||||||||
1 2 3 | A3 A2 A7 | 6 3 0 | 3/2 ½ 2 | 2 0 3 | 0 1 0 | 1 0 0 | 3/2 -1/2 4 | ½ -1/2 5 | ½ ½ 3 | 0 0 1 | ||||||||||
m + 1 | Zi - Cj | 21/2 | 10 | 0 | 0 | 9/2 | 3/2 | 9/2 | 0 | |||||||||||
Виды математических моделей двойственных задач
На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов.
Н е с и м м е т р и ч н ы е з а д а ч и
(1) Исходная задача Двойственная задача
Zmin = CX; fmax = YA0;
AX = A0; YA £ С .
X ³ 0.
(2) Исходная задача Двойственная задача
Zmax = CX; fmin = YA0;
AX = A0; YA ³ С .
X ³ 0.
|
|
С и м м е т р и ч н ы е з а д а ч и
(3) Исходная задача Двойственная задача
Zmin = CX; fmax = YA0;
AX ³ A0; YA £ С .
X ³ 0. Y ³ 0.
(4) Исходная задача Двойственная задача
Zmax = CX; fmin = YA0;
AX £ A0; YA ³ С .
X ³ 0. Y ³ 0.
Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений исходной задачи необходимо привести к соответствующему виду. Запишем, например, математическую модель двойственной задачи для следующей исходной.
Найти минимальное значение линейной функции Z = 2x1 + x2 + 5x3 при ограничениях
x1 – x2 – x3 £ 4,
x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).
2x1 – x2 + 3x3 ³6,
Рассматриваемая задача относится к симметричным двойственным задачам на отыскание минимального значения линейной функции. Для того чтобы было можно записать двойственную задачу, ее модель должна иметь вид (3). Переход осуществляется умножением первого неравенства на -1.
Исходная задача:
Zmin = 2x1 + x2 + 5x3 при ограничениях
-x1 + x2 + x3 ³ -4,
x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).
|
|
2x1 – x2 + 3x3 ³6,
Двойственная задача:
fmin = -4x1 + 5x2 + 6x3 при ограничениях
-y1 + y2 + 2y3 £ 2,
y1 – 5y2 - y3 £ 1, yi ³ 0 (i = 1, 2, 3).
2y1 + y2 + 3y3 £ 5,
Приведем без доказательства следующую теорему. Теорема 1.1. Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.
Если i-я компонента оптимального плана двойственной задачи положительна, то i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.
Дата добавления: 2019-07-15; просмотров: 181; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!