183814 (629937), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

hij = 0, если i-й ресурс не направляется в j-й регион,

1, если i-й ресурс направляется в j-й регион.

Необходимо распределить ресурсы по регионам таким образом (выбирать такие значения hij), чтобы величина полной вероятности достижения цели Рц была максимальной:

Рц = Pj 1 - (1-hijij = max.

Должно выполняться также ограничение

hij = 1, i = 1, 2,…m

Ограничение означает, что каждый из m ресурсов обязательно должен назначаться в какой-либо из регионов.

Динамическое программирование (планирование)

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

В общем виде постановка задачи динамического программирования сводится к следующему:

Имеется некоторая управляемая операция (целенаправленное действие), распадающаяся (естественно или искусственно) на m шагов – этапов. На каждом шаге осуществляется распределение и перераспределение участвующих в операции с целью улучшения ее результата в целом. Эти распределения в динамическом программировании называются управлениями операцией и обозначаются буквой U. Эффективность операции в целом оценивается тем же показателем, что и эффективность ее управления W (U).

При этом эффективность управления W(U) зависит от всей совокупности управлений на каждом шаге операции:

W = W(U) = W(U1, U2, ..., Um).

Управление, при котором показатель W достигает максимума, называется оптимальным управлением. Оптимальное управление обозначается буквой U.

Оптимальное управление многошаговым процессом состоит из совокупности оптимальных шаговых управлений:

U = (U1, U2, ..., Um).

Задача динамического программирования – определить оптимальное управление на каждом шаге Ui (i = 1, 2, …, m) и, тем самым, оптимальное управление всей операцией в целом.

В большинстве практических задач принимается, что показатель эффективности операции W в целом представляет собой сумму эффективности действий на всех этапах (шагах) операции:

W = i,

где i – эффективность операции на i-м шаге.

При этом в случае оптимального управления

W = max i

Существо решения динамического программирования заключается в следующем:

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

• На первом круге, идя от последующих шагов к предыдущим, находится так называемое условное оптимальное управление;

• Условное оптимальное управление выбирается таким, чтобы все предыдущие шаги обеспечивали максимальную эффективность последующего шага, иными словами, на каждом шаге имеется такое управление, которое обеспечивает оптимальное продолжение операции; этот принцип выбора управления называется принципом оптимальности;

• Так продолжается до первого шага, но поскольку первый шаг не имеет предыдущего, то полученное для него условное оптимальное управление теряет свой условный характер и становится просто оптимальным управлением, которое мы ищем;

• Второй круг оптимизации начинается с первого шага, для которого оптимальное управление известно.

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

Пусть имеется m типов различных грузов, которыми необходимо загрузить транспортное средство таким образом, чтобы общая ценность груза W была максимальной. Ценность груза является функцией отгрузоподъемности транспортного средства:

W = f (G)

Известны массы грузов i-го типа Рi и их стоимости Ci.

Необходимо загрузить транспортное средство таким образом, чтобы общая ценность груза была максимальной:

W = fm(G) = max xiCi,

где xi – число предметов груза i-го типа, загружаемых в транспортное средство; xi выступает здесь в качестве управления (Ui=xi)

Ограничивающими условиями являются:

xi Pi G

xi = 0, 1, 2...

Первое условие требует, чтобы общая масса груза не превышала грузоподъемности транспортного средства, а второе – чтобы предметы, составляющие груз различных типов, были неделимы.

Понятие критерия оптимальности

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

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

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

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

Возможна классификация моделей по временному аспекту, по способам формирования критериев, по типу применяемых измерителей, по способам использования критериев.

Сущность глобального и локального критериев оптимальности.

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

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

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

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

Сложность системы целей объясняется многообразием задач общественного развития и развития систем, а также тем, насколько обширны и интенсивны внешние связи данной системы.

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

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

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

Векторная оптимизация

Математическая формулировка задачи векторной оптимизации:

Пусть X = x1,…, x N (j = 1,N) - вектор переменных, обычно предполагается неотрицательность вектора переменных X0, функциональная взаимосвязь переменных устанавливается определенными соотношениями, на которые накладываются ограничения:

gi (X)bi (i = 1,M).

Функционирование системы оценивается определенными критериями, записываемыми в виде целевых функций fr(X) (r = 1,K). Множество критериев можно представить в виде векторной целевой функции

F(X) = f1(X),…>fr(X).

Чтобы минимизировать частный критерий fr(X), достаточно максимизировать -fr(X), так как min fr(X)=-max (-fr(X)). Поэтому в дальнейшем предполагается, что каждая компонента векторного критерия максимизируется. Задача многоцелевой оптимизации записывается как векторная задача математического программирования (ВЗМП)

F(X) = f1(X),…>fr(X) (max),

gi (X)bi (i = 1,M),

X0.

Будем рассматривать ВЗМП для случая, когда точки оптимума X*r(r=1,K), полученные при решении задачи по каждому критерию fr(r=1,K) не совпадают (случай их совпадения встречается крайне редко и такая задача не представляет интереса). Поэтому с математической точки зрения задача является некорректной, так как если один из критериев достигает своего оптимума, то улучшение по другим компонентам векторного критерия невозможно. Отсюда вытекает, что решением ВЗМП может быть только какое-то компромиссное решение.

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

Понятие предпочтительности плана. План X не хуже плана X`, если

fr(X) fr(X`) (r = 1,K). Если среди этих неравенств хотя бы одно строгое, то план X предпочтительнее (лучше) X`,т.е. при переходе от X к X`значение ни одного критерия не ухудшилось и хотя бы одного критерия улучшилось. План X оптимален по Парето (эффективен), если он допустим и не существует другого плана X`, для которого fr(X) fr(X`) (r = 1,K), и хотя бы для одного критерия выполняется строгое неравенство.

К общей формулировке многокритериальной задачи могут сводиться задачи различного содержания, которые можно подразделить на четыре типа.

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

2. Задачи оптимизации на множестве объектов, качество функционирования каждого из которых оценивается самостоятельным критерием. Если качество функционирования каждого объекта оценивается несколькими критериями (векторным критерием), то такая задача называется многовекторной. Примером может служить задача распределения дефицитного ресурса между несколькими предприятиями. Для каждого предприятия критерием оптимальности является степень удовлетворения его потребностей в ресурсе или другой показатель, например, величина прибыли. Для планирующего органа критерием выступает вектор локальных критериев предприятий.

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

4. Задачи оптимизации на множестве этапов функционирования. Рассматривается функционирование объектов на некотором интервале времени, разбитом на несколько этапов. Качество управления на каждом этапе оценивается частным критерием, а на множестве этапов – общим векторным критерием. Примером может служить распределение квартального плана цеха по декадам. В каждой декаде необходимо обеспечить максимальную загрузку. В результате получится критерий максимизации загрузки в каждой декаде квартала.

Многокритериальные задачи можно также классифицировать по другим признакам: по вариантам оптимизации, по числу критериев, по типам критериев, по соотношениям между критериями, по уровню структуризации, наличию фактора неопределенности.

Характеристики

Список файлов курсовой работы