Правила двойственного соответствия.
Итак, для одной и той же задачи затрат q 1p2aq 2,p1мы получили ее прямую и двойственную части 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 в столбцовых векторах p1t и p2t с умножением на транспонированную матрицу a t слева p2 t max q 2t, p2t при a t p2 t p1 t. 1.3. Задача выпуска 1.Табличное представление.
Задача выпуска является обратной по отношению к предыдущей задаче затрат задачей равновесного производственного управления.
Процессом производства в ней является процесс сборки ряда взаимозаменяемых сложных изделий из нескольких видов простого сырья. Примерами задачи выпуска являются задачи оптимального планирования сборки изделий из нескольких видов комплектующих узлов, в частности - строительства из нескольких видов строительных материалов - времени работы нескольких видов промышленного оборудования времени работы рабочих нескольких специальностей, и им подобные задачи.
При использовании m видов сырья для производства n видов изделий во всех задачах выпуска процесс производства описывается матрицей затрат c, составляющие которой ci j количество i-сырья на единицу j-изделия 0 , имеют обратные количественные размерности по отношению к количественным размерностям матрицы выпуска a aj i количество j-изделий на единицу i-сырья.
В условиях заданного вектора предложения сырья q 1 и заданных цен p2 на производимые изделия в количественной прямой части обратной задачи ищется наиболее доходное предложение план производства изделий q 2 , а в ценовой двойственной части - наименее расходные цены p1 потребляемого сырья q 21 q 2np1 1 p1 mc1 1 c1 n cm1 cm nq 11 q 1mp21 p2 n Формальным отличием приведенной таблицы от таблицы предыдущей задачи является, как мы видим, замена сырьевых переменных издельными и наоборот. 2.