- векторы выпуска ассортимента изделий из сырья каждого вида. Полученные ценовые балансовые соотношения:

    p1 = ( p1 1 ј p1 1)
    a1 1 ј a1 m
    ј ј ј
    an1 ј an m
    = p 2 a,

являются линейным преобразованием p 2 a= p 1 цен выпускаемых изделий в производственные ценности потребляемого сырья, двойственным осуществляемому той же матрицей выпуска изделийa количественному линейному преобразованию q 2 = a q 1 , сырья в изделия.

2. Ценовые условия равновесия. В условиях свободного доступа как производителей, так и потребителей товаров к сырью и технологиям, продажа всякого готового изделия его производителем становится возможной лишь при условии того, что приобретение готового изделия потребителем оказывается для него не дороже его самостоятельного изготовления. По этой причине допустимыми являются такие продажные ценыp2 выпускаемых изделий, при которых производственные ценности p1= p1(p2) сырья не превышают его закупочных цен p1 :

    p1 = p2 a Ј p1 .

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

Множество решений ценовых ограничений называется множеством допустимых цен.

3. Равновесные цены изделий. Доход производства, даваемый стоимостью продаваемых по ценам p2 1, ј , p2 n требуемых количеств q 21 , ј , q 2n выпускаемых изделий образует линейную функцию Ldual(p2) этих цен:

    Ldual(p2) = p2 1 q 21 + ј + p2 n q 2n = б p2 , q 2с,

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

    p2 : б p2 , q 2с = max б p2 , q 2с
    p2 Ѕ p2 a Ј p1
    .

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

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
    ,

есть векторы затрат сырья на выпуск изделия каждого вида. Ценовые балансовые соотношения p2 = p2(p1) = p1 c

описывают осуществляемое матрицей затрат двойственное линейное преобразование цен потребляемого сырья в цены производимых из них изделий. При заданных продажных ценах изделий вложенное в них сырье приобретает ценность, не меньшую ценности выпускаемых из него изделий:

    p2 = p1 c і p2 .

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

    Стоимость расходуемого сырья:
    Mdual(p1) = p1 1 q 11 + ј + p1 m q 1m є бp1 , q 1с ,

составляет расход производства. Ищутся допустимые цены сырья, сообщающие его стоимости наименьшее значение:

    p1 : б p1 , q 1с є min б p1 , q 1с
    p1 Ѕ p1 c і p2 .

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 2
    - и пару задач выпуска:
    p1
    с
    q 1
    :
    p2
    с прямой задачей оптимального планирования выпуска изделий:
    q 2 : max б p2 , q 2с при c q 2 Ј q 1 ,
    и ей двойственной задачей оптимального оценивания сырья:
    p1 : min б p1 , q 1с при p1 c і p2 .

Как мы видим, обе задачи обладают "перекрестной" симметрией и формально, то есть безотносительно к экономическому содержанию, прямая и обратная пары задач тождественны друг другу с точностью до - 1)- переобозначения своих величин и -2)- перестановки между собой их взаимно-двойственных частей:

min б p1 , q 1с при a q 1 і q 2 max б p2 , q 2с при c q 2 Ј q 1,

max б p2 , q 2с при p2 a Ј p1 min б p1 , q 1с при p1 c і p2 .

    Точная взаимозаменяемость задач достигается:
    - заменой технологических матриц:
    c « a ,
    - и переобозначением количественных и ценовых векторов:
    (p1; 2 )t « q 1; 2 .

При этом прямая часть задачи затрат становится равносильной двойственной части задачи выпуска, а двойственная часть первой - прямой части второй. Будем называть взаимно-двойственную пару задач прямого (затратного) вида с прямой (количественной) частью на минимум и двойственной (ценовой) частью на максимум:

    q 1
    q 1 : min б p1 , q 1с при a q 1 і q 2 ,
    p2
    a
    q 2
    :
    p1
    p2 : max б p2 , q 2с при p2 a Ј p1 .

- канонической парой линейных задач статического равновесия, а их переменные q 1 и p2 - канонически сопряженными переменными.

    1. 4. Задача равновесия

Физическое содержание задачи равновесия. В трехмерном случае: m, n Ј 3, наша задача имеет простое физическое истолкование. Во внешнем силовом поле постоянной во времени и пространстве напряженностиp1 скалярная линейная функция координат L(q 1): L(q 1) = бp1 , q 1с ,

является потенциальной энергией находящегося в точке q 1 пробного тела единичной массы (заряда). Все налагаемые на перемещения пробного тела дополнительные ограничения называются в механикесвязями. Ограничения нашей задачи

    q 1: a q 1 і q 2

задают в пространстве ее переменной q 1 выпуклую многогранную областьдопустимых перемещений. В итоге, каноническая задача оптимального производственного управления:

    q 1: min б p1 , q 1с при a q 1 і q 2 - ?

- физически представляет собою задачу вычисления в ограниченной области пространства координат q 1 точки наименьшей потенциальной энергии L(q 1) пробного тела единичной массы в постоянном внешнем силовом поле p1 . Точка наименьшей потенциальной энергии называется точкой статического равновесия и задача ее определения - задачей статического равновесия. По этой причине линейную задачу оптимального производственного планирования мы будем называть так, как об этом заявлено в названии, а именно -линейной задачей статического равновесия. Особенностью линейных задач является независимость их свойств от геометричеких размерностей их величин. Это обстоятельство используется для распространения трехмерной терминологии на линейные задачи равновесия любой пространственной размерности.

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

Так, условие невыкатывания шарика из области ограничений под действием приложенной к нему внешней силы являетсяпризнаком существованиярешения задачи равновесия. Геометрически он состоит в условии принадлежности вектора силыp1 выпуклой оболочке коэффициентных векторов всех ограничений. Точка равновесия, если она существует, располагается на границе области допустимых перемещений и, более того, - в одной из угловых точек границы. Выпуклая области имеет выпуклую границу и наоборот. Физически, это обстоятельство равносильно условию свободного перемещения шарика по границе в поисках точки своего равновесия. Способ последовательного приближения к точке равновесия посредством движения по ребрам граничной поверхности называется "симплекс-методом" решения задачи линейного программировани. Задача оптимизации заданной функции на заданной поверхности называется в механике задачей управления. Грани точки равновесия называются равновесными гранями. В точке равновесия со стороны каждой равновесной грани на шарик действует сила реакции опоры, направленная прямоугольно этой грани вдоль вектора ее нормали. Признак равновесиявыражает собою содержание третьего закона Ньютона, по которому в точке равновесия вес пробного тела уравновешивается суммой сил реакций опор. Равновесные цены выпускаемых изделий являются коэффициентами p2 этого разложения. Если некоторая грань является равновесной, то она проходит на нулевом расстоянии от точки равновесия и, потому, с ее стороны на шарик действует ненулевая сила реакции опоры; если же грань неравновесна, то она располагается на строго положительном расстоянии от точки равновесия и, потому, сила реакции с ее стороны равняется нулю. В теории задачи равновесия эта пара свойств получила названиедополняющей нежесткости.

Отсутствие вырожденияв виде прямоугольности вектора напряженности силового поля одной из равновесных граней служитпризнаком единственностирешения задачи равновесия. При непрерывных значениях параметров точная пропорциональность координат вектораp1 и какого-то вектора al нормали грани невероятна и может быть лишь следствием округления численных значений их координат. Такое вырождение задачи называется случайным и легко снимается малыми изменениями или “шевелением” параметров. Отношения, сохраняющиеся при шевелении их параметров, называются случаем общего положения или, по-просту, - общим случаем.

    Основная литература

1. Л. В. Канторович. Экономический расчет наилучшего использования ресурсов. М. , 1960

2. Дж. Данциг. Линейное программирование, его применения и обобщения. М. , “Прогресс”, 1966

3. Д. Б. Юдин и Е. Г. Гольштейн. Линейное программирование: теория, методы и приложения. М. , “Наука”, 1969

4. М. Интрилигатор. Математическкие методы оптимизации и экономическая теория. М. , “Прогресс”, 1975

Страницы: 1, 2