Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

-2/3 -1/3 1/3

Из этой же итерации следует С* = (— 3; —1; 1). Таким образом

2
1 0

Y = С*D-1 = (-3; -1; 1) ( -1/3 1/3 2/3

-2/3
-1/3 1/3

Y*=(-19/3; -11/3; -1/3), т. е. yi = С*Хi, где Хi — коэффициенты разложения последней итерации, стоящие в столбцах векторов первоначального единичного базиса.

Итак, i-ю двойственную переменную можно получить из значения оценки (m
+ 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базиc, если к ней прибавить соответствующее значение коэффициента линейной функции: у1 = — 19/3 + 0 = — 19/3; y2 = -11/3 + 0 = -11/3; у3 = -1/3+0 = -1/3.
При этом плане max f = -46/3.

3. Симметричные двойственные задачи

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

Исходная задача. Найти матрицу-столбец Х = (x1, x2, …, xn), которая удовлетворяет системе ограничений

(1.12). АХ>А0, Х>0 и минимизирует линейную функцию Z = СХ.

Двойственная задача. Найти матрицу-строку Y = (y1, y2, …, yn), которая удовлетворяет системе ограничений YA ( C, Y ( 0 и максимизирует линейную функцию f = YA0.

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

Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.

Исходная задача. Найти минимальное значение линейной функции 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).

Рекомендуем скачать другие рефераты по теме: реферат на тему закон, учет реферат.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата