Страница: 5/9
мы получили ее прямую и двойственную части:
q 1 : min áp1 , q 1ñ при a q 1 ³ q 2
и
p2 : max áp2 , q 2ñ при p2 a £ p1 .
Обе они, несмотря на различные "сопряженные" наборы искомых неизвестных: в одной q 1, а в другой p2 ,- объединены одними и теми же наборами параметров a, q 2 и p1 и обладают определенной двойственной симметрией, позволяющей по одной части задачи востановить ей двойственную часть и наоборот.
Действительно, сравнивая между собой обе подзадачи, мы можем установить правила соответствия между ними. Эти правила состоят в замене
1) знака ограничений с ³ на £ ,
2) действия оптимизации функции стоимости c min на max ,
3) параметров ограничений на параметры функции стоимости c q 2 на p1 ,
4) количественных переменных на им сопряженные ценовые: c q 1 на p2 , и наоборот,
и позволяют по известной одной части задачи тут же написать ей двойственную.
Заметим , также, что "сопряженные" количественные q 1 и ценовые p2 переменные обеих подзадач относительно количеств товаров имеют взаимно обратные количественные размерности штук и обратных штук товара:
[ q 1k ] = штуки и [ p2 l] = рубли / штуки,
и их балансовые соотношения взаимно обратны в том смысле, что в прямых - количества сырья преобразуются в количества изделия, а в двойственных - наоборот: цены изделий преобразуются в цены сырья:
q 2 = a q 1 и p2 a = p1 .
5.Транспонирование. Соблюдаемое нами во взаимно двойственных подзадачах различение строчных и столбцовых векторов устраняется действием транспонирования. Транспонированием матрицы называется действие замены ее строк столбцами или, что то же самое,- столбцов строками, и обычно обозначается значком “t” сверху:
|
а t = |
a1 1 ¼ a1 m ¼ ¼ ¼ an1 ¼ an m |
t º |
a1 1 ¼ an 1 ¼ ¼ ¼ a1 m ¼ an m |
. |
В частности:
|
(q 1) t = |
q 11 ¼ q 1m |
t = ( q 11 ¼ q 1m) и (p1) t = ( p1 1 ¼ p1 m) t = |
p1 1 ¼ p1 m |
. |
Транспонирование произведения матриц доопределяется произведением транспонированных матриц, взятых в обратном порядке:
(a c )t = (c )t (a )t;
в частности:
( p2 a ) t = a t (p2) t и (a q 1) t = (q 1) t a t ,
а также
(áp1 , q 1ñ) t = á(q 1) t, (p1) tñ .
Теперь, двойственная часть задачи равновесного управления, полученная нами в строчных векторах p1 и p2 с умножением на матрицу a справа:
p2 : max áp2 , q 2ñ при p2 a £ p1 ,
в транспонированном виде записывается подобно своей прямой части
q 1 : min áp1 , q 1ñ при a q 1 ³ q 2
в столбцовых векторах (p1)t и (p2)t с умножением на транспонированную матрицу a t слева:
(p2 )t : max á(q 2)t, (p2)tñ при a t (p2) t £ (p1 )t.
1.Табличное представление. Задача выпуска является "обратной" по отношению к предыдущей задаче затрат задачей равновесного производственного управления. Процессом производства в ней является процесс сборки ряда взаимозаменяемых сложных изделий из нескольких видов простого сырья. Примерами задачи выпуска являются задачи оптимального планирования сборки изделий из нескольких видов комплектующих узлов, в частности:
- строительства из нескольких видов строительных материалов
- времени работы нескольких видов промышленного оборудования,
- времени работы рабочих нескольких специальностей,
и им подобные задачи.
При использовании m видов сырья для производства n видов изделий во всех задачах выпуска процесс производства описывается матрицей затрат c, составляющие которой
ci j [количество i-сырья / на единицу j-изделия] ³ 0 ,
имеют обратные количественные размерности по отношению к количественным размерностям матрицы выпуска a : [ aj i] = количество j-изделий / на единицу i-сырья.
Реферат опубликован: 19/11/2009