Методы блочного програмирования

 
 ,                    (10.3.24) 
 
где 
 
 .                              
 
Выберем достаточно большие границы изменения переменных  и  : 
 
 . 
 
Можно показать, что задача (10.3.11), (10.3.12) в случае (10.3.21)-(10.3.24) сводится к игре двух лиц со стратегиями  где 
 
 
 
и функционал  имеет вид 

 
 . 
Окончательно мы приходим к задаче о нахождении седловой точки функции 
 . 
Эта задача решается методом фиктивной игры Брауна. Тогда первый игрок (минимизирующий функционал) на каждом шаге итеративного процесса решает задачу: 
 
минимизировать   
при ограничениях

 
где у_і - фиксированы.

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

 максимизировать                                  (10.3.25) 
 
при ограничениях

 
                                             (10.3.26) 
 
                            (10.3.27) 
 
где у_і - фиксированы.

 
Второй игрок рассматривается, как J независимых игроков (подсистем). Таким образом, метод Корнаи-Липтака  осуществляет декомпозицию на (j+m) подзадач. 
 
Поскольку итеративный процесс Брауна для матричных игр обладает очень медленной сходимостью, то для максимизации функций (10.3.25) целесообразно применить метод возможных направлений Зойтендейка (см.гл.6).  Рассмотрим задачу (10.3.11), когда исходная задача имеет вид (10.3.21)-(10.3.23). 
Можно показать [52], что функции   являются вогнутыми и кусочно-линейными, а точки излома функций соответствуют смене базиса в задачах (10.3.25)-(10.3.27). 
 
Применим схему возможных направлений Зойтендейка для данной задачи в простейшем случае, когда некоторым заданным величинам   соответствуют единственные оптимальные двойственные переменные  . 
 
Согласно основной теореме двойственности имеем:

 
 ,                                (10.3.28) 
 
Следующие значения величин y_j(y_j0) задаются в методе Зойтендейка в виде 
 
 ,                          (10.3.29) 
 
где z_j - m-меримый вектор возможных направлений, удовлетворяющий условию нормировки, например вида 
 
 , где  - параметр, определяющий величину шага (  ). 
 
Подставляя (10.3.29) в (10.3.11) с учетом (10.3.28) приходим к следующей задаче ЛП относительно неизвестных возможных направлений: 
 
Максимизировать   (10.3.30) при ограничениях  

 (10.3.31)                           (10.3.32) 
 
Задача (10.3.30)-(10.3.32) распадается на m независимых подзадач. Пусть для любого s имеют место равенства :

 
 
 
Тогда оптимальное решение (10.3.30)-(10.3.32) имеет вид

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

 
где -  максимальное значение  , при котором сохраняются все исходные базисы в задачах (10.3.25), (10.3.26), а  определяется максимизацией функции   при ограничениях 

 
 .  

 

 

Вывод :

 

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

определяется вместе с оптимальным распределением ресурсов.

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

Централизм методов  блочного программирования находит выражение в том, что критерий оптимальности и правые части ограничений локальных задач определяются алгоритмом решения  исходной задачи. Они «предписываются» локальному объекту,  представляя собой редукцию на локальный объект глобального  критерия (как в методе Данцига-Вулфа) или глобальных ограничений (как в методе Корнаи-Липтака), а не выявляются при его анализе как самоорганизующейся системы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

 

• Лопатников Л. И. Экономико-математический словарь: Словарь современной экономической науки. — 5-е изд 2003г

 

• АВТОМАТИЗИРОВАННЫЕ СИСТЕМЫ УПРАВЛЕНИЯ И ПРИБОРЫ АВТОМАТИКИ. Всеукраинский межведомственный научно-технический сборник. Основан в 1965 г.

 

• Институт новой экономики. А.Н. Азрилиян. 1997.

 

• кн.: Математические методы в планировании отраслей и предприятий. М., 1973.