4.Правила двойственного соответствия. Итак, для одной и той же задачи затрат:
| q 1 | |||
| p2 | a | q 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
в столбцовых векторах (p1)t и (p2)t с умножением на транспонированную матрицу a t слева:
(p2 )t : max á(q 2)t, (p2)tñпри 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 2n | ||
| p1 1 ¼ p1 m | c1 1¼c1 n ¼¼¼ cm1¼cm n | q 11 ¼ q 1m |
| p21¼p2 n |
Формальным отличием приведенной таблицы от таблицы предыдущей задачи является, как мы видим, замена сырьевых переменных "издельными" и наоборот.
2.Количественная часть задачи выпуска. В условиях затрат ci jединиц i-сырья на каждую единицу производимого j-изделия, на выпуск q 21 , ¼ , q 2n единиц изделий всех n видов потребуется q 11 , ¼ , q 1m :
q 11 = c1 1 q 21 + ¼ + c1 n q 2nºác1 , q 2ñ ;
. . .
q 1m = cm 1 q 21 + ¼ + cm n q 2nºácm , q 2ñ ,
единиц сырья каждого вида. n-мерные строки матрицы затрат, служащие коэффициентами балансовых соотношений:
c1 = ( c1 1¼ c1 n );
. . .
cm = ( cm 1¼ cm n ),
есть векторы затрат сырья каждого вида на весь ассортимент производимых из него изделий. Матричное представление полученных балансовых соотношений:
q 1 = q 1(q 2) = c q 2 ,
описывает линейный процесс пересчета предложения выпускаемых изделий в спрос на потребляемое для их производства сырье.
Допустимым является такое предложение изделий, при котором спрос на потребляемое сырье не превосходит его предложения:
q 1 = c q 2£ q 1.
Доход такого производства, выражаемый стоимостью M(q 2) продаваемых по ценам p2 предлагаемых количеств изделий:
M(q 2) = p2 1 q 21 + ¼ + p2 n q 2nºáp2 , q 2ñ,
называется функцией стоимости количественной части обратной задачи. Сама же задача состоит в том, чтобы на множестве ее допустимых планов производства найти план наибольшей стоимости:
| q 2 : áp2 , q 2ñ= max á p2 , q 2ñ q 2½c q 2£ q 1 | . |
В сущности, все задачи равновесного управления являются определениями равновесных значений своих искомых неизвестных.
3.Ценовая часть задачи выпуска. Одновременно, затраты на каждую единицу j-изделия ci jединиц сырья всех m видов по ценам p1 i: i=1, ¼ , m, сообщают выпускаемым изделиям цены p2 1 , ¼ , p2 n :
p2 1 = p1 1 c1 1 + ¼ + p1 m cm 1ºáp1 , d 1ñ ;
. . .
p2 n = p1 1 c1 n + ¼ + p1 m cm nºáp1 , d nñ .
m-мерные столбцовые векторы матрицы затрат:
d 1º | c1 1 ¼ cm 1 | , ¼ , d nº | c1 n ¼ cm n | , |
есть векторы затрат сырья на выпуск изделия каждого вида. Ценовые балансовые соотношения