WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     || 2 | 3 |

«Нижегородский государственный университет им. Н.И. Лобачевского ЗАДАЧИ И МЕТОДЫ КОНЕЧНОМЕРНОЙ ОПТИМИЗАЦИИ Учебное пособие Часть 3. Д.И. Коган Динамическое программирование и дискретная многокритериальная оптимизация ...»

-- [ Страница 1 ] --

Министерство образования Российской Федерации

Нижегородский государственный университет им. Н.И. Лобачевского

ЗАДАЧИ И МЕТОДЫ КОНЕЧНОМЕРНОЙ

ОПТИМИЗАЦИИ

Учебное пособие

Часть 3.

Д.И. Коган

Динамическое программирование и дискретная

многокритериальная оптимизация

Издательство Нижегородского университета Нижний Новгород 2004 УДК 519.6 Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация: учебное пособие.

Нижний Новгород: Изд-во Нижегородского ун-та, 2004. 150 с.

Рецензенты:

Часть 3 посвящена задачам дискретной оптимизации и методу динамического программирования как одному из наиболее эффективных инструментов их решения.

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

Пособие предназначено для студентов, специализирующихся в области прикладной математики и информатики.

ВВЕДЕНИЕ

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

Конструируются соотношения, позволяющие различными способами строить оптимальные траектории.

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

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

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

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

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

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

Пособие в компактной форме излагает материал, имеющийся в известных, но зачастую труднодоступных монографиях и учебниках по динамическому программированию [3, 4, 5, 24]. Дополнительно рассматриваются вопросы применения метода динамического программирования к решению многокритериальных задач;



сответствующие теоретические результаты получены недавно и изложены только в журнальных публикациях и сборниках статей (см., например, [2, 11, 26].).

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

1.1. Принцип динамического программирования.

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

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

Формально дискретную управляемую систему определяем как совокупность где D – множество состояний системы (множество D конечно); x0 – начальное состояние; F – множество финальных состояний, x0 D, x0 F, F D; V(x) – конечное множество возможных в состоянии х управлений, xD\F; f(х, v) – функция переходов (из состояния x под воздействием управления v система переходит в состояние f(х,v)), x D\F, vV(x), f(х, v)D; s(х,v) – функция платежа, здесь x D\F, vV(x); значения функции платежа считаются неотрицательными.

Состояние x системы называем промежуточным, если оно не является ни начальным, ни финальным.

Конечную последовательность Т = {x0, x1, x2, …, xn} состояний системы именуем траекторией системы, если выполняются условия:

Состояние x0 – начальное состояние траектории Т, а состояние xn – ее конечное состояние. Состояния x2, x3…, xn-1 из Т являются промежуточными состояниями данной траектории.

Траекторию называем полной, если начальным ее состоянием является начальное состояние системы, а конечным – одно из финальных состояний этой системы. Таким образом, для полной траектории Т = {x0, x1, x2, …, xn} имеет место x0=x0 и xnF. Траекторию Т = {x0, x1, x2, …, xn} называем заключительной xтраекторией, если x0=x и xnF. Заключительная x -траектория, имея своим начальным состоянием произвольное состояние x системы, заканчивается в одном из финальных состояний системы. Траекторию Т = {x0, x1, x2, …, xn} называем начальной xтраекторией, если x0=x0 и xn=x. Начальная x-траектория, имея своим конечным состоянием x, начинается от начального состояния системы.

На множестве состояний системы введем бинарное отношение достижимости Р(х,у): считаем, что произвольные состояния х и у удовлетворяют этому отношению, если существует траектория Т, имеющая своим начальным состоянием х, а конечным – состояние у. Отметим, что введенное бинарное отношение обладает свойствами рефлексивности (для любого состояния х имеет место Р(х,х)) и транзитивности (для любых x, y, z из того, что имеют место Р(х,у) и Р(y,z) следует, что имеет место и Р(х,z)). Дополнительно предполагаем, что отношение Р(х,у) антисимметрично (из Р(х,у) и Р(у,х) вытекает х = у). Антисимметричность бинарного отношения достижимости означает, что в любой своей траектории система не может реализовывать циклы (возвращаться в состояния, в которых она уже была). Обладая свойствами рефлексивности, транзитивности и антисимметричности, бинарное отношение Р(х,у) является отношением частичного порядка.

Состояние х системы именуем достижимым, если имеет место Р(х0, х).

Отметим, что начальное состояние х0 достижимо по определению. Состояние х системы именуем продуктивным, если для некоторого финального состояния f имеет место Р(х, f). Финальные состояния системы продуктивны по определению.

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

Избавление от недостижимых и непродуктивных состояний способствует сокращению объемов выполняемых вычислений.

Пусть Т = {x0, x1, x2,…, xn} – произвольная траектория системы, причем x t = f(x t - 1,v t), где v t V(x t - 1), t = 1, 2,…, n. Стоимость С(Т) траектории Т определяем следующим образом:

Таким образом, стоимость траектории – это сумма пошаговых платежей, имеющих место при реализации траектории.

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

стоимости.

Дополнительно введем в рассмотрение совокупность частных задач А(x), где x принадлежит D\F.

Задача А(x). Для системы и ее состояния x найти заключительную xтраекторию минимальной стоимости.

Решения сформулированных экстремальных задач А и А(x) именуем оптимальной полной траекторией и оптимальной заключительной x-траекторией соответственно.

В основе метода динамического программирования лежит принцип оптимальности, сформулированный американским математиком Ричардом Беллманом следующим образом: "Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, являющегося результатом первого решения".

Следующая теорема выражает принцип Беллмана в применении к задачам построения оптимальных траекторий.

Т е о р е м а 1.1. Если траектория Т= {x0, x1, x2, …, xn} оптимальна, то любая ее заключительная часть Тk = {xk, xk+1,…, xn} также оптимальна.

Теорема легко доказывается методом от противного. Предположим, что траектория Т= {x0, x1, x2,…, xk, xk+1, …, xn} оптимальна, а ее заключительная часть Тk = {xk, xk+1,…, xn} оптимальной не является. Стоимость траектории Т представим как С (Т) x -траекторию запишем в виде µ iV(уk+i-1),i=1,2,…, m-k; уm F. Пусть R = s(уk+i-1, µi). Так как уk-траектория Т1k оптимальна, то R< Q. Рассмотрим траекторию Т*= {x0, x1, x2, …, xk, уk+1, уk+2, …, уm}.

Как очевидно, С(Т*) = P + R. Далее имеем С(Т*) = P + R < P + Q = С(Т). Таким образом, С(Т*) < С(Т). Последнее неравенство означает, что траектория Т неоптимальна. Справедливость теоремы вытекает из полученного противоречия.

Стоимость оптимальной в задаче А полной траектории обозначим символом ВА. Стоимость заключительной x-траектории, оптимальной в задаче А(x), обозначим В(х). Функция В(х) называется функцией Беллмана. Отметим, что ВА = В(x0).

Очевидны следующие равенства:

Пусть x - произвольное нефинальное состояние системы. В этом состоянии можно реализовать любое принадлежащее множеству V(x) управление. Предположим, что выбрано управление v, vV(x). Данное управление влечет платеж s(х,v), а следующим состоянием системы оказывается f(х, v). Если далее реализуется оптимальная заключительная f(х, v)- траектория, то суммарная величина последующих платежей оказывается равной В(f(x,v)). Из принципа Беллмана получаем:

Вычисление значений функции Беллмана по соотношениям (1.1) - (1.2) выполняется поэтапно в следующем порядке. На первом этапе фиксируются значения В(x) =0 для всех x F. Далее на каждом следующем этапе вычисление очередного значения функции Беллмана выполняется для произвольного состояния x такого, что В(x) неизвестно, но значения В(y) для всех непосредственно следующих за x состояний y уже найдены (состояние y системы относим к числу непосредственно следующих за состоянием х, если пара {x, y} является траекторией системы ). Последним в процессе счета определяется значение В(0).

Для синтеза оптимальной полной траектории системы при выполнении определяемой соотношениями (1.1)-(1.2) процедуры счета следует дополнительно составить список оптимальных переходов (СОП). Каждая запись этого списка имеет вид [xi, xj], где xi – произвольное нефинальное состояние, а xj = f(xi, v*) – состояние, в которое система переходит из xi под воздействием управления v*, возможного в состоянии xi и обращающего в минимум правую часть (1.2); если таких управлений несколько, фиксируется любое из них (нашей целью считаем построение любой из оптимальных траекторий, но не всех таких траекторий). Записи СОП взаимно однозначно соответствуют нефинальным состояниям системы, при этом запись[xi, f(xi, v)] считается соответствующей состоянию xi. Составленный СОП полагаем упорядоченным по возрастанию индексов первых компонент входящих в него записей.

Чтобы построить оптимальную траекторию, из СОП извлекаем последовательность записей W, первым элементом которой является запись, соответствующая состоянию x0; каждая следующая запись последовательности W имеет своей первой компонентой вторую компоненту предыдущей записи этой последовательности. В последней записи последовательности W второй компонентой является некоторое финальное состояние системы. Из составленного СОП последовательность W извлекается однозначно.

Пусть W = {[x0, y1], [y1, y2],[y2, y3],…,[ym-1, ym]}, здесь ym F. Тогда Т = {x0, y1, y2, y3,…, ym} – искомая оптимальная траектория.

Уравнения (1.1) – (1.2) – рекуррентные соотношения динамического программирования для решения задачи А. Основанный на этих соотношениях метод решения задачи А называется методом динамического программирования.

Пусть N – число состояний системы. Тогда верхняя оценка числа вычисляемых значений функции Беллмана в процессе решения задачи А равна N.

Число элементарных операций, выполняемых при определении по формуле (1.2) каждого конкретного значения этой функции не превышает СN, где С - некоторая не зависящая от N константа. Таким образом, верхней оценкой числа элементарных операций, выполняемых при решении задачи А методом динамического программирования является СN2, где N – число состояний системы, а С – не зависящая от N константа. Для запоминания в процессе вычислений всех найденных значений функции Беллмана необходим объем памяти, пропорциональный N; объем памяти такого же порядка нужен для создания списка оптимальных переходов. В итоге получаем, что объем памяти, нужной для решения задачи А методом динамического программирования, линейно зависит от N.

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

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

Вначале положим, что вершины названы именами соответствующих состояний.

Вершину x0 именуем начальной; вершины, соответствующие состояниям подмножества F, называем финальными. В графе G() дуга, идущая из произвольной вершины x в вершину y, проводится тогда и только тогда, когда в системе для некоторого возможного в состоянии x управления v* (v*V(x)) имеет место y = f(х, v*); вес этой дуги полагаем равным s(х, v*). Вершину х называем непосредственно предшествующей вершине у, если в графе имеется дуга (x, y). В графе G() путь из произвольной вершины х, х D, в вершину у, у D, имеется тогда и только тогда, когда выполняется бинарное отношение Р(х,у). Так как Р(х,у) – отношение частичного порядка, граф G() – ациклический. Из свойств транзитивности и антисимметричности бинарного отношения Р(х, у) и сделанного предположения о достижимости любого состояния системы вытекает, что в графе G() нет дуг, входящих в вершину x0. По определению системы, достигнув финального состояния, она прекращает функционировать; поэтому в графе отсутствуют дуги, исходящие из финальных вершин.

Вершины графа G() нумеруем целыми неотрицательными числами. Вершине x0 (начальной вершине) присваиваем номер 0. Далее реализуется многоэтапная процедура, на каждом шаге которой из совокупности пока непронумерованных выбирается какая-либо вершина, для которой все непосредственно предшествующие вершины уже пронумерованы; выбранной вершине присваивается следующий (в порядке возрастания) номер. Введенные номера далее будем считать новыми наименованиями вершин графа и соответствующих им состояний системы. Отсюда имеем следующее: если для некоторых состояний i, j и управления v, vV(i), имеет место j = f(i, v), то j>i.

При выполненной нумерации в вычислительной процедуре, определяемой соотношениями (1.1) - (1.2), значения функции Беллмана для состояний системы вычисляются последовательно, в порядке убывания их номеров. Поэтому в ситуации, когда для состояния i по соотношению (1.2) определяется значение В(i), все значения В(f(i,v)) при vV(i) уже известны. Последней в процедуре вычисляется величина В(0) оптимальное значение критерия в решаемой задаче А.

определяющий ее граф G(1) представлен на рис. 1.1. Начальным является состояние 0, множество финальных состояний одноэлементно: F={9}. Требуется найти полную траекторию минимальной стоимости.

Для состояний системы 1 (вершин графа G(1)) вычисляем значения функции Беллмана. На основании (1.1) фиксируем В(9)=0. Далее, пользуясь (1.2), последовательно получаем: В(8)=1; В(7)= min[3, 1+В(8)] = 2; В(6)=1+В(7)=3;

В(5)=min[1+ В(6), 3+В(7), 7+В(8] = min[4, 6, 8] = 4; В(4)=min[2+ В(5), 3+В(8), 5+В(9)] = min[6, 4, 5] = 4; В(3)=min[3+ В(5), 4+В(4)] = min[7, 8] = 7; ; В(2)=min[1+ В(3), 5+В(5)] = min[8, 9] = 8; В(1)=min[9+ В(6), 6+В(2)] = min[12, 14] = 12; В(0)=min[1+ В(1), 5+В(2), 4+В(3] = min[13, 13, 11] = 11. Таким образом, минимальная из стоимостей полных траекторий в рассматриваемой задаче равна 11.

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

Рисунок 1.1.Граф G(1) Рисунок 1.2. Граф G(1) с выделенными дугами.

Как показывают выделенные дуги, на первом такте процесса управления следует выполнить переход из вершины 0 в вершину 3, на втором такте - из вершины в вершину 5, на третьем такте - из вершины 5 в вершину 6, на четвертом такте - из вершины 6 в вершину 7, на пятом такте - из вершины 7 в вершину 8, на шестом, заключительном такте - из вершины 8 в вершину 9. Таким образом, оптимальной по критерию суммарной стоимости полной траекторией является Т = {0,3,5,6,7,8,9}.

Далее введем совокупность частных задач следующего вида.

траекторию минимальной стоимости.

Оптимальное решение задачи А*(x) именуем оптимальной начальной xтраекторией системы.

Имеет место следующий факт.

Т е о р е м а 1.2. Если траектория Т= {x0, x1, x2, …, xn} оптимальна, то любая ее начальная часть также оптимальна.

Доказательство данной теоремы идентично доказательству теоремы 1.1.

Стоимость начальной х-траектории, оптимальной в задаче А*(x), обозначим В*(х). Очевидно, что В системе произвольное состояние х непосредственно предшествует состоянию у, если пара {x, y} является траекторией системы. Управление, переводящее систему из состояния х непосредственно в состояние у, обозначим v[х, у]. Множество состояний системы, непосредственно предшествующих состоянию у, обозначим Г(у). Основываясь на теореме 1.2, запишем соотношение, позволяющее организовать процесс вычислений значений функции В*(у) для всех состояний у, отличных от начального:

Отметим, что Вычисление значений функции В*(у) на основе рекуррентных соотношений (1.3) - (1.4) выполняется поэтапно в следующем порядке. На первом этапе фиксируется значение В*(x0) = 0. Далее на каждом следующем этапе вычисление очередного значения функции В* выполняется для произвольного состояния у такого, что В*(у) неизвестно, но значения В*(х) для всех состояний x, непосредственно предшествующих состоянию y, уже найдены.

Метод решения задачи А, основанный на соотношениях (1.3) – (1.5), – прямой метод Беллмана. В отличие от него, метод, основанный на соотношениях (1.1) – (1.2), носит название обратного метода Беллмана. Функции В*(x) и В(x) будем именовать функциями Беллмана для прямого и обратного счета соответственно. Реализация как обратного, так и прямого метода Беллмана для решения задачи А требует квадратично зависящего от числа состояний системы количества элементарных операций.

Иногда прямой и обратный метод Беллмана, подразумевая, что задача решается с использованием соотношений динамического программирования, называют методами прямого и обратного счета соответственно.

определяющий ее граф G(1) представлен на рис. 1.1. Начальным является состояние 0, множество финальных состояний одноэлементно: F={9}. Методом прямого счета требуется найти полную траекторию минимальной стоимости.

Для состояний системы 1 (вершин графа G(1)) вычисляем значения прямой функции Беллмана. На основании (1.3) фиксируем В*(0)=0. Далее, пользуясь (1.4), последовательно получаем: В*(1)=1; В*(2)= min[5, В*(1)+6] = 5; В*(3)= min[4, В*(2)+1] = 4; В*(4)= В*(3)+4 = 8; В*(5)=min[В*(2)+ 5, В*(3)+ 3, В*(4)+2] = 7;

В*(6)=min[В*(1)+ 9, В*(5)+ 1] =8; В*(7)=min[В*(6)+ 1, В*(5)+3] =9; В*(8)=min[В*(5)+ 7, В*(7)+1] =10; В*(9)=min[В*(7)+ 3, В*(8)+1, В*(4)+5] =11.

При вычислении значений функции Беллмана в графе G(1) для каждой вершины у, отличной от начальной, специально выделяем (рисуем жирной линией) дугу (x, y), где x - вершина для которой значение правой части (1.4) при подсчете В*(у) оказывается минимальным (этот способ выделения дуг с учетом используемого метода счета называем прямым; способ выделения, использованный в решении предыдущего примера, именуем обратным). Полученный результат представлен на рис. 1.3. Как показывают выделенные дуги, на последнем такте процесса управления следует выполнить переход из вершины 8 в вершину 9, при этом переход в вершину реализуется из вершины 7, в вершину 7 - из вершины 6, в вершину 6 - из вершины 5, в вершину 5 - из вершины 3, в вершину 3 - из вершины 0. Оптимальной является траектория {0,3,5,6,7,8,9}.

Полученные в результате решения примеров 1.1 и 1.2 оптимальные в системе траектории совпали.

Рисунок 1.3. Граф G(1) с выделенными дугами (способ выделения - прямой).

Отметим следующее обстоятельство. Пусть в процессе вычислений по соотношениям (1.3) - (1.4) для некоторого финального состояния x* оказалось найденным значение В*(x*); полную траекторию стоимости В*(x*), имеющую своим конечным состоянием x*, обозначим Т*. Если каждая из остальных траекторий имеет в своем составе как минимум одно состояние из некоторого подмножества состояний Q, причем все значения В*(x) при xQ уже вычислены и оказались не меньшими В*(x*), то Т*.– полная оптимальная траектория. Сделанное утверждение нередко дает возможность ограничить объем требуемых вычислений.

Подмножество промежуточных состояний М системы назовем разрезающим, если каждая полная траектория Т этой системы имеет в своем составе состояния из М.

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

Основанный на данном факте метод решения задачи синтеза полной траектории минимальной стоимости называется методом встречного счета.

Для системы 1, определяемой представленным на рис. 1.1 графом G(1), минимальным разрезающим является, в частности, подмножество вершин-состояний М* ={4, 5, 6}. При решении задачи синтеза оптимальной по стоимости полной траектории методом встречного счета выполняем следующие действия. Прямым счетом последовательно определяем: В*(1)=1; В*(2)= 5; В*(3) = 4; В*(4)= 8; В*(5) = 7;

В*(6) = 8. Обратным счетом находим: В(8)=1; В(7) = 2; В(6) =3; В(5)= 4; В(4) = 4. Для принадлежащих подмножеству М* состояний находим: В*(4)+ В(4)= 12; В*(5)+ В(5)= 11; В*(6)+ В(6)= 11. Получаем, что минимальная из стоимостей полных траекторий системы 1 равна 11.

Оптимальные полные траектории системы 1 (их, в принципе, может быть несколько) проходят через вершины 5 и 6. При выполненном подсчете значений функции В*(х), см. решение примера 1.2, определено, что оптимальной начальной 5траекторией системы 1 является Т*(5) = {0,3,5}, а оптимальной начальной 6траекторией этой системы является Т*(6) = {0,3,5,6}. При подсчете значений функции В(х), см. решение примера 1.1, установлено, что оптимальной заключительной 5траекторией системы 1 является Т(5) = {5,6,7,8,9}, а оптимальной заключительной 6траекторией этой системы является Т(6) = {6,7,8,9}. Получаем, что единственной оптимальной полной траекторией системы 1 является Т ={0,3,5,6,7,8,9}.

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

Выше траектории системы оценивались по показателю суммарной стоимости. В некоторых задачах целесообразной оценкой каждой траектории Т = {x0, x1, x2,…, xn} является величина максимального из пошаговых платежей в ходе реализации этой траектории. Введем показатель и рассмотрим задачу синтеза полной траектории с минимальным значением этого показателя. Обозначим через Т() совокупность всех полных траекторий системы.

Сформулированная задача записывается в виде Оптимальную в задаче (1.7) траекторию будем именовать минимаксной полной траекторией системы.

Идентичным образом вводится понятие минимаксной заключительной x траектории системы.. Имеет место следующий факт.

Т е о р е м а 1.3. Если Т= {x0, x1, x2,…, xk, xk+1,…, хn} – минимаксная полная траектория, а Т' = {у1, у2, …, уm} – минимаксная заключительная xk - траектория, здесь у1 = xk, то траектория {x0, x1, x2,…, xk, у2, …, уm} – минимаксная полная траектория.

Доказательство данной теоремы легко выполняется методом от противного.

Из теоремы 1.3 вытекает Следствие 1.1. В системе имеется минимаксная полная траектория, любая заключительная часть которой также минимаксна.

Максимальный из пошаговых платежей при реализации минимаксной полной траектории Т системы обозначим В'. Максимальный из пошаговых платежей при реализации минимаксной заключительной х-траектории системы обозначим В'(х).

Функция В'(х) – функция Беллмана для рассматриваемой минимаксной задачи.

Очевидны следующие равенства:

Пользуясь следствием из теоремы 3, запишем общее уравнение Формулы (1.8)-(1.9) – рекуррентные соотношения динамического программирования для задачи синтеза минимаксной полной траектории в системе. В вычислительной процедуре, определяемой этими соотношениями, значения функции Беллмана для нефинальных состояний системы вычисляются последовательно, в порядке убывания их номеров. В ситуации, когда для состояния xi по формуле (1.9) определяется значение В'(xi), все значения В'(f(xi,v)) при vV(xi) уже известны.

Последней в реализации процедуры вычисляется величина В'(x0) – оптимальное значение критерия в решаемой задаче (1.7). Синтезируемая с использованием рекуррентных соотношений (1.8)-(1.9) минимаксная полная траектория такова, что любая ее заключительная часть также минимаксна. Количество элементарных операций, необходимых для решения изложенным способом задачи (1.7) квадратично зависит от от числа состояний системы.

Идентичным образом вводится понятие максиминной полной траектории и записываются соотношения динамического программирования для ее синтеза.

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

программирования дискретных оптимизационных задач.

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

Задача оптимального распределения капиталовложений (ЗОРК). Имеются денежная сумма (капитал) C и возможные сферы вложений S1, S2,…,Sn. Считается, что в каждую сферу St может быть вложен целочисленный вклад, не превосходящий константы Сt. Для каждой сферы St полагается известной монотонно возрастающая в нестрогом смысле функция ft(u), определяющая величину дохода, получаемого при вложении в данную сферу вклада u. Требуется определить обеспечивающее максимальный суммарный доход распределение суммы С или ее части по сферам вложений.

Математическая модель задачи следующая:

при условиях:

Покажем, что сформулированную задачу можно трактовать как задачу поиска полной траектории, обеспечивающей максимальный суммарный доход в соответствующим образом построенной дискретной управляемой системе. Исходные данные ЗОРК определяют систему (ЗОРК), управления в которой осуществляется в дискретном времени t=0, 1, 2, …, n-1 (в момент t определяется вклад в сферу St+1).

Состояния системы - пары (t, U), где t – момент дискретного времени, а U – сумма, которая к данному моменту еще не распределена, здесь t {0,1,…, n}, U{0,1,…, С}.

Начальное состояние системы (0,C); финальными являются состояния вида (n, U). В любом нефинальном состоянии (t, U) выбор реализуемого в этом состоянии управления ut+1 осуществляется из совокупности V(t,U) ={0,1,…, min (Сt+1,U)}; выбранная величина ut+1 - размер вклада в сферу St+1 Под воздействием управления ut+1 система(ЗОРК) из состояния (t, U) переходит в состояние (t + 1, U - ut+1), получаемый при этом доход равен ft+1(ut+1 ). Каждая последовательность управлений, переводящая систему из начального состояния в одно из финальных состояний, определяет некоторое допустимое решение ЗОРК (распределение (u1, u2, …, un) капиталовложений).

Исходную ЗОРК трактуем как задачу отыскания траектории системы (ЗОРК), обеспечивающей максимальный суммарный доход.

Функция Беллмана для системы (ЗОРК) определяется соотношениями здесь t {0,1,, …, n -1}, U{0,1,, …, С}.

При реализации обратного метода Беллмана процесс вычислений реализуется в соответствии с записанными соотношениями. Зная, что В(n, U) = 0 при всех U, по формуле (1.11) находим все значения В(n-1, U) при U{0,1,…, S}; здесь оказывается справедливым тождество В(n-1, U) = fn(min(Сn, U)). Далее, имея вычисленными значения В(n-1, U), по той же формуле (1.11) определяем все значения В(n-2,U), где U{0,1, …, S}, и т.д. до тех пор, пока не окажется найденной величина В(0, С) оптимальное значение критерия в решаемой ЗОРК. В процессе вычислений, с целью обеспечения возможности определить оптимальное распределение капиталовложений, после отыскания каждого следующего значения В(t, U), где t {0,1,, …, n -1} и U{0,1,…, С}, для пары (t, U) отдельно фиксируем значение ui+1, на котором достигается максимум правой части (1.11).

Прямой метод Беллмана для решения ЗОРК заключается в последовательном вычислении значений функции В*(t, U) в порядке возрастания значений первого аргумента. При этом здесь t{0,1,…, n-1}, U{0,1,, …, С}. Основанные на формуле (1.13) вычисления заканчиваются отысканием величин В*(n, U), где U{1, 2,…, С}; максимальная из найденных величин – оптимальное значение критерия в решаемой ЗОРК.

ПРИМЕР 1.3. Имеются сферы капиталовложений S1, S2, S3, S4; в каждую из них может быть внесен целочисленный вклад, не превосходящий 5. Величина подлежащего распределению капитала равна 6. Функции, определяющие доходы, получаемые при вложении в различные сферы вклада u, заданы таблицей 1.1. Требуется найти оптимальное распределение капитала между сферами вложений.

Решение данного примера можно выполнить как прямым, так и обратным методом Беллмана. Будем основываться на рекуррентных соотношениях (1.10) - (1.11), т.е. применим обратный метод. Отыскиваемые в процессе счета значения функции В(t, U) вносим в таблицу 1.2. В каждую заполняемую клетку (t, U) этой таблицы (параметр t определяет столбец, параметр U – строку) одновременно с В(t, U) вносится и записанное в квадратных скобках значение ui+1, на котором достигается максимум правой части (1.11) при подсчете В(t, U); если таких значений несколько, вносится любое из них (нашей целью является отыскание какого-либо из оптимальных решений, а не полной их совокупности).

В связи с тем, что В(4, U) тождественно равно нулю, процесс вычислений начинаем с определения значений В(3, U) при всех возможных значениях U. Из равенства (1.11) следует, что В(3, U) = f4(U) при U = 0,1,2,3,4,5 и В(3, 6) = f4(5). Так заполняется Таблица 1.1. Значения функций дохода ft(u).

Таблица 1.2. Значения функции В(t, U).

последний столбец таблицы 1.2. То же равенство (1.11) дает возможность последовательного (справа налево) заполнения остальных столбцов. Заметим, что для решения задачи в первом столбце достаточно найти только один, нижний элемент. В рассматриваемом примере оказалось, что В(0,6) = 0,8. Это оптимальное значение критерия (максимально возможный доход). В клетке (0,6) в квадратных скобках записано число 1. Значит, в оптимальном распределении капиталовложений взнос в первую сферу должен равняться единице. В таком случае суммарный взнос в остальные сферы не превосходит 5. В клетке (1,5) в квадратных скобках записано число 3. Значит, в синтезируемом оптимальном распределении капиталовложений взнос во вторую сферу равняется трем. Получаем, что суммарный взнос в третью и четвертую сферы не превосходит 2. В клетке (2,2) в квадратных скобках записано число 2. В оптимальном распределении взнос в третью сферу должен равняться двум. В итоге получаем, что оптимальное распределение делит сумму С = 6 между первой, второй и третьей сферами капиталовложений; вносимые в них вклады равны соответственно 1, 3, 2. При этом первая сфера приносит доход 0,2; вторая сфера дает доход 0,4 и третья сфера - доход 0,2. Суммарный доход действительно равен 0,8.

Задача о выборе траектории набора высоты и скорости(ЗВТНВС).

Летательный аппарат, в начальный момент имеющий скорость V0 и высоту Н0, должен быть поднят на высоту Н1, а скорость его должна достигнуть значения V1; здесь V1>V0 и H1>Н0. Считаются известными функции F(V, Н) и G(V, Н), определяющие соответственно дополнительный расход горючего при увеличении скорости полета с V до V+1 при неизменной высоте полета Н и при увеличении высоты полета от Н до Н+ при неизменной скорости полета V. Требуется найти режим набора высоты и скорости, при котором общий расход горючего будет минимальным.

Вводим дискретизацию объекта. Считаем, что числа V0, Н0, V1, Н1 - целые и что процесс набора высоты и скорости можно разбить на ряд последовательных этапов, результатом каждого из которых является увеличение на единицу одного из параметров полета, высоты или скорости. В таком случае функция F(V, Н) определена для значений V{V0, V0+1, V0+ 2,…, V1 – 1}и Н{Н0, Н0+1, Н0+ 2,…, Н1}; функция G(V, Н) определена для значений V{V0, V0+1, V0+ 2,…, V1 }и Н{Н0, Н0+1, Н0+ 2,…, Н1– 1};

можно считать эти функции заданными таблично. Исходные данные рассматриваемой задачи определяют систему (ЗВТНВС), управление которой осуществляется в дискретном времени; управление определяет, значение какого параметра полета, высоты или скорости, следует увеличить на единицу. Состояния системы – пары целых чисел (V,Н), где V – достигнутая скорость, а Н – имеющаяся высота полета. Начальное состояние системы (V0, Н0); финальным является состояние (V1, Н1). Пусть В(V,Н) минимально возможный расход горючего, при котором значения скорости и высоты полета могут быть увеличены от V и Н до V1 и Н1 соответственно; здесь V{V0, V0+1, V0+ 2,…, V1} и Н{Н0, Н0+1, Н0+ 2,…, Н1}. Очевидно, что В(V, Н1)= F(V, Н1) + В(V+1, Н1), V{V0, V0+1, V0+ 2,…, V1-1}; (1.15) В(V1, Н)= G(V1, Н)+ В(V1, Н+1), Н{ Н0, Н0+1, Н0+ 2,…, Н1-1}. (1.16) В общем случае, для V{V0, V0+1, V0+ 2,…, V1-1} и Н{Н0, Н0+1, Н0+2,…,Н1имеем:

Равенства (1.14)-(1.17) являются рекуррентными соотношениями динамического программирования, позволяющими определить оптимальную траекторию набора высоты и скорости летательного аппарата. Если в ситуации, характеризуемой парой (V,Н), в правой части последнего записанного соотношения минимум достигается на первой компоненте, то следует на единицу увеличить скорость объекта; если же минимум достигается на второй компоненте, то на единицу следует увеличить высоту полета.

Вычисления по записанным рекуррентным соотношениям можно представить как процесс заполнения таблицы 1.3, строки которой соответствуют имеющимся значениям высоты, а столбцы – имеющимся значениям скорости. В каждую клетку, стоящую в пересечении столбца Н и строки V вносятся: 1) соответствующее значение функции В(V,Н); 2) заключенный в квадратные скобки символ v или h; внесение символа v (символа h) означает, что в ситуации, определяемой парой (V,Н), на единицу следует увеличить значение скорости (высоты) полета. Заполнение таблицы осуществляется в следующем порядке. Сначала на основании равенств (1.14)-(1.16) заполняются клетки нижней (последней) строки и крайне правого (последнего) столбца. Дальнейшее заполнение реализуется на основании формулы (1.17);

заполняются клетки предпоследней строки и предпоследнего столбца, и т.д. Если в (1.17) минимум правой части реализуется на первой компоненте, то в заполняемую клетку в качестве второй компоненты вносится [v], в противном случае в заполняемую клетку вносится [h].

Таблица 1.3. Значения функции В(V,Н).

Дадим оценку вычислительной сложности предложенной процедуры счета.

Число вычисляемых значений функции Беллмана В(V,Н) оценивается произведением (V1-V0) (Н1-Н0). Каждое очередное значение этой функции вычисляется по записанным рекуррентным соотношениям посредством выполнения нескольких элементарных операций. Общая оценка числа выполняемых для решения задачи элементарных операций С(V1- V0)(Н1- Н0), где С - достаточно малая натуральная константа (оценка 10 для С является верхней). В случае, например, V1- V0 = Н1- Н0 =10 число выполняемых при синтезе оптимальной траектории элементарных операций не превышает 1 000.

Примем следующие обозначения: V1- V0= р, Н1- Н0=q. Сумма р+ q - общее число этапов, на каждом из которых на единицу возрастает значение V или Н. Если ЗВТНВС решать методом полного перебора, то общий расход горючего придется подсчитать для C p + q различных траекторий набора высоты и скорости полета (через C как обычно, обозначается число сочетаний из n по m). В случае V1- V0 = Н1- Н0 = различных траекторий.

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

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

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

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

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

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

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

Граф G называется полным, если для любой упорядоченной пары i, j его вершин в G имеется дуга (i, j). Гамильтоновы циклы имеются не во всяком графе. Граф G именуется гамильтоновым, если гамильтонов цикл в нем есть. В полном n- вершинном ориентированном графе имеются (n-1)! гамильтоновых циклов.

Если G – взвешенный ориентированный граф; то весом произвольного цикла этого графа называется сумма весов дуг, входящих в состав этого цикла.

Классическая задача коммивояжера (ЗК) формулируется следующим образом:

имеется полный взвешенный ориентированный граф без петель G с множеством вершин N = {1, 2,…, n}; веса всех дуг неотрицательны; в этом графе требуется найти гамильтонов цикл минимального веса.

Исходную информацию по ЗК считаем представленной в виде (nxn)- матрицы S={sij}, где sij – вес дуги (i,j) графа G, i =1, n, j =1, n, i j; все элементы главной диагонали матрицы S являются нулями.

В типовой интерпретации вершины 1, 2,…, n графа G – это города. Дуги отображают возможные элементарные переходы. Коммивояжеру, изначально находящемуся в городе 1, необходимо обойти все остальные города, побывав в каждом из них ровно по одному разу, и затем вернуться в город 1. Веса дуг графа трактуются как длины соответствующих элементарных переходов. Требуется найти имеющий минимальную длину допустимый (т.е. удовлетворяющий наложенным требованиям) маршрут коммивояжера. С учетом других возможных интерпретаций, на матрицу S требование симметричности не налагается, не считается обязательным и выполнение неравенства треугольника.

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

Пусть i – произвольный город (iN), а V – любое подмножество городов, не содержащее города 1 и города i. Через М(i, V) обозначим совокупность путей, каждый из которых начинается в городе i, завершается в городе 1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Через В(i, V) обозначим длину кратчайшего пути множества М(i, V). Для решаемой задачи В(i, V) – функция Беллмана. Как очевидно, В(1, {2, 3,…,n}) – искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все города.

Если V – одноэлементное множество, V ={j}, где j 1 и j i, то совокупность М (i, V) состоит из единственного пути = (i, j, 1). Поэтому Предположим, что значения функции В(i, V) для всех i N \ {1} и всех возможных k-элементных (k < n-1) множеств V уже вычислены. Тогда значение В(i, V'), где V' – произвольное (k+1)-элементное подмножество совокупности N \ {1, i}, вычисляется по формуле Уравнения (1.18)-(1.19) – рекуррентные соотношения динамического программирования для решения задачи коммивояжера, они реализуют обратный метод Беллмана.

ПРИМЕР 1.4. Решить задачу коммивояжера, определяемую матрицей Сначала, пользуясь формулой (1.18), определяем значения В(i, {j}):

В(2, {3}) = 4; В(2, {4}) = 8; В(3, {2}) = 6; В(3, {4}) = 5; В(4, {2}) = 7; В(4, {3}) = Далее по формуле (1.19) последовательно получаем (в левой части каждого из ниже записанных равенств подчеркнуты те значения параметра j, на которых при подсчете реализуется указанный в правой части (1.19) минимум):

Итак, оптимальное значение критерия в рассматриваемом примере равно 10.

Выполненные подчеркивания позволяют определить оптимальный маршрут. Он следующий:

Для записи соотношений, по которым реализуется прямой метод Беллмана, введем новые обозначения. Пусть М'(V, i) - совокупность путей, каждый из которых начинается в городе 1, проходит в качестве промежуточных только через города подмножества V, заходя в каждый из них ровно по одному разу, и завершается в городе i; здесь, как и ранее, i - произвольный город (i N), а V - любое подмножество N, не содержащее городов 1 и i. Длину кратчайшего пути множества М'(V, i) обозначим В*(V, i). Как очевидно, В*({2, 3,…,n},1) - искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все города. Если V одноэлементное множество, V ={j}, где j 1 и j i, то совокупность М'(V, i) состоит из единственного пути =(1, j, i). Поэтому Предположим, что значения функции В*(V, i) для всех iN и всех возможных k- элементных (k < n-1) множеств V уже вычислены. Тогда значение В*(V',i), где V' – произвольное (k+1)- элементное подмножество совокупности N\{1, i}, вычисляется по формуле Уравнения (1.20)-(1.21) – рекуррентные соотношения динамического программирования для решения классической задачи коммивояжера, они реализуют прямой метод Беллмана.

Заметим, что при решении задачи коммивояжера обратным методом состояния моделирующей системы – пары вида (i, V), где i – город, в котором сейчас находится коммивояжер, а V – множество городов, которые ему еще предстоит обойти перед тем, как вернуться в исходный город 1. При решении задачи коммивояжера прямым методом состояния моделирующей системы – пары вида (V, i), где i – город, в котором коммивояжер находится сейчас, а V – множество городов, которые коммивояжер уже обошел после того, как вышел из города 1. По сути, (i, V) и ({2,3,…,n} \ (V{i}),i) – это разные обозначения одной и той же ситуации. Данный факт используется при решении рассматриваемой задачи методом встречного счета.

ПРИМЕР 1.5. Методом встречного счета решить задачу коммивояжера, определяемую матрицей (заметим, что матрица S в данном примере та же, что и в предыдущем).

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

Реализуя метод обратного счета, определяем:

В(2, {3}) = 4; В(2, {4}) = 8; В(3, {2}) = 6; В(3, {4}) = 5; В(4, {2}) = 7; В(4, {3}) = 5.

Реализуя метод прямого счета, получаем:

В*({4}, 2) = 9; В*({3},2) = 5; В*({4},3) = 8; В*({2},3) = 8; В*({3},4) = 3; В*({2},4) = 10.

Минимальное, равное 10, значение правая часть принимает в пятом равенстве.

Отсюда следует: а) оптимальное значение критерия в рассматриваемой задаче равно 10;

б) оптимальная траектория системы проходит через состояние ({3},4) или, что то же самое, через состояние(4, {2}). Последнее дает возможность установить оптимальный маршрут коммивояжера:

Применение метода встречного счета в сравнении с прямым или обратным счетом тем более выгодно, чем больше размер решаемой задачи.

Задача коммивояжера с минимаксным критерием (ЗК ММК). Считается заданным полный взвешенный ориентированный граф без петель G с множеством вершин N = {1, 2,…, n}; веса всех дуг неотрицательны. Для каждого цикла С этого графа определена характеристика (С), значение которой равно максимальному из весов дуг, данный цикл образующих. В рассматриваемой задаче требуется найти гамильтонов цикл С графа G, имеющий минимально возможное значение характеристики (С). Исходную информацию по задаче считаем представленной в виде (nxn)- матрицы S={sij}, где sij – вес дуги (i, j) графа G, i =1, n, j =1, n, i j; все элементы главной диагонали матрицы S нулевые.

Придерживаемся прежней интерпретации: вершины графа G – это города, которые коммивояжеру необходимо обойти. Пусть i – произвольный город (i N), а V – любое подмножество городов, не содержащее города 1 и города i. Как и ранее, через М(i, V) обозначаем совокупность путей, каждый из которых начинается в городе i, завершается в городе 1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Каждый путь характеризуем показателем () – максимальным из весов дуг, которые образуют данный путь. Минимальное значение показателя () для путей множества М(i, V) обозначим В'(i, V). Как очевидно, В'(1, {2, 3,…,n}) – искомое оптимальное значение критерия в решаемой ЗК ММК.

Если V – одноэлементное множество, V ={j}, где j 1 и j i, то совокупность М (i, V) состоит из единственного пути = (i, j, 1). Поэтому Предположим, что значения функции В'(i, V) для всех iN и всех возможных kэлементных (k < n-1) множеств V уже вычислены. Тогда значение В'(i, V'), где V' – произвольное (k+1)-элементное подмножество совокупности N \ {1, i}, вычисляется по формуле Уравнения (1.22) - (1.23) – рекуррентные соотношения динамического программирования для решения ЗК ММК.

Отметим, что изложенным алгоритмом может решаться вопрос определения по произвольному n-вершинному ориентированному графу G, является ли он гамильтоновым. С этой целью по графу G строим полный взвешенный ориентированный граф без петель G* с множеством вершин N = {1, 2,…, n}. Веса дуг графа G* назначаем по следующему правилу: вес sij дуги (i, j) равен 1, если дуга (i, j) в исходном графе G имеется; вес sij дуги (i, j) равен 2 в противном случае. Далее решаем определяемую графом G* задачу коммивояжера с минимаксным критерием. Если оптимальное значение этого критерия оказывается равным 1, то граф G гамильтонов; в противном случае оптимальное значение критерия равно 2, и граф G гамильтоновым не является.

Задача инкассации. Задача определяется полным ориентированным графом без петель G с множеством вершин N = {1, 2,…, n}.Каждая дуга и каждая вершина этого графа, кроме вершины 1, имеет определенный вес. В интерпретации вершины 2,3,…, n – это объекты, которые инкассатору необходимо обойти по замкнутому маршруту, посетив каждый из них ровно по одному разу. При этом считаем, что маршрут начинается и заканчивается в вершине 1 (банке). Веса дуг графа G трактуются как длины реализуемых по ним переходов, веса вершин 2, 3,…, n – это денежные суммы, которые соответствующими объектами передаются инкассатору для транспортировки в банк. Из банка инкассатор выходит без денег, в банк он возвращается со всей собранной по объектам множества {2, 3,…, n} денежной суммой.

С целью упрощения обозначений будем считать, что вершина 1 также имеет вес, он равен нулю. Исходную информацию по задаче считаем представленной (n n)матрицей S={s(i, j)}и n-мерным вектором d = (d(1), d(2),…,d(n)), где s(i, j) – вес дуги (i,j), а d(i) – вес вершины i графа G, i =1, n, j =1, n, i j. Все элементы главной диагонали матрицы S считаются нулевыми, первая координата вектора d равна нулю. Каждый гамильтонов цикл C =(1, i2, i3,…,in, 1), здесь (i2, i3,…,in) – некоторая перестановка чисел 2, 3,…,n, оцениваем показателем (С) = d(i2) s(i2,i3) + (d(i2)+d(i3)) s(i3,i4) + (d(i2)+ d(i3) + d(i4)) s(i4,i5)+… Задача инкассации состоит в отыскании гамильтонова цикла с наименьшим значением показателя (С).

В интерпретации (С) – общее количество "деньго-километров" при реализации гамильтонова цикла С. Введенный показатель (С) можно считать характеристикой безопасности маршрута. Чем меньше (С), тем безопаснее маршрут.

Пусть i – произвольная вершина графа (i N), а V – любое подмножество его вершин, не содержащее вершины 1 и вершины i. Как и ранее, через М(i, V) обозначаем совокупность путей, каждый из которых начинается в вершине i, завершается в вершине 1 и проходит в качестве промежуточных только через вершины множества V, заходя в каждую из них ровно по одному разу. Каждый путь характеризуем показателем (), общим числом деньго-километров в его реализации; при этом считаем, что в начальной вершине i пути из множества М(i, V) инкассатор имеет денежную сумму именно эта сумма собрана инкассатором в не принадлежащих множеству V пунктах.

Минимальное значение показателя () для путей множества М(i, V) обозначим В(i, V).

Как очевидно, В(1, {2, 3,…,n}) – искомое оптимальное значение критерия в решаемой задаче инкассации.

Если V – одноэлементное множество, V = {j}, где j 1 и j i, то совокупность М(i, V) состоит из единственного пути = (i, j, 1). Поэтому В(i, {j}) = R(N \ {j}) s(i, j)+ R(N) s( j,1), iN, j{2, 3,…, n}, j i. (1.24) Предположим, что значения функции В(i, V) для всех iN и всех возможных kэлементных (k < n-1) подмножеств V уже вычислены. Тогда значение В(i, V'), где V' – произвольное (k+1)-элементное подмножество совокупности N \{1, i}, вычисляется по формуле Уравнения (1.24) - (1.25) – рекуррентные соотношения динамического программирования для решения задачи инкассации. Отметим, что в рассмотренной задаче на оценку гамильтонова цикла C =(1, i2, i3,…,in,1) никак не влияет значение s(1,i2), т.е. длина первого реализуемого перехода; это вызвано тем, что в данном переходе транспортируется нулевая денежная сумма. В главе 4 будет рассмотрена бикритериальная задача инкассации, где один критерий – суммарная длина (стоимость) маршрута, а другой – количество деньго-километров.

Задача двух коммивояжеров. Математическая постановка задачи следующая.

Имеется полный взвешенный ориентированный граф без петель G с множеством вершин N = {1, 2,…, n}; веса всех дуг неотрицательны. Требуется найти пару циклов этого графа, имеющую минимальный суммарный вес и удовлетворяющую условиям:

а) вершина 1 – единственная вершина, через которую проходит как цикл C1, так и цикл C2;

б) через каждую вершину множества N \ {1} проходит либо цикл C1, либо цикл C2.

Исходную информация по задаче представлена (nxn)-матрицей S={sij}, где sij – вес дуги (i, j) графа G, i =1, n, j =1, n, i j; все элементы главной диагонали матрицы S нулевые.

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

Вершины графа G – это города, которые коммивояжерам необходимо обойти по замкнутым маршрутам; веса дуг графа G – длины соответствующих переходов. Пусть iN, j N, i j за исключением случая i = j =1, а V – любое подмножество из N, не содержащее городов 1, i и j. Через М''(V, i, j) обозначим совокупность всех пар (1,2) путей, обладающих следующими свойствами:

а) каждый из путей начинается в городе 1;

б) путь 1 заканчивается в городе i;

в) путь 2 заканчивается в городе j;

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

Кратчайшую суммарную длину, подсчитанную для пар путей из М''(V, i, j) обозначим В*(V, i, j). Ясно, что В*({2, 3,…,n},1,1) – искомая минимальная суммарная длина пары циклов, удовлетворяющих требованиям решаемой задачи о двух коммивояжерах.

Множество М''({k}, i, j) состоит из двух пар путей: {1 =(1, k, i), 2= (1, j)} и { =(1, i), 2=(1, k, j))}. Суммарная длина путей первой пары: s1k + ski + s1j = (s1k + s1j ) + ski = В*(, k, j ) + ski. Аналогичным образом получаем, что суммарная длина путей второй пары равна В*(, i, k )+ skj. Поэтому В общем случае, когда i N, j N, i j за исключением варианта i = j =1, а V любое подмножество N, не содержащее городов 1, i и j, имеем следующее. В путях пары (1,2) из М''(V, i, j) последними являются города i и j соответственно. Если некоторый принадлежащий подмножеству V город k является предпоследним в первом пути, то при данном дополнительном условии минимальная суммарная длина пары путей (1,2) равна В*(V\ {k},k,j) + ski; если же принадлежащий V город k является предпоследним во втором пути, то при данном дополнительном условии минимальная суммарная длина пары путей (1,2) равна В*( V\ {k}, i, k )+ skj. Отсюда получаем:

В* (V,i, j) = min{ min (В*(V \ {k},k,j) + ski), min (sik + В*( V \ {k}, i, k )+ skj)}. (1.28) Равенства (1.26)-(1.28) являются рекуррентными соотношениями динамического программирования для решения задачи двух коммивояжеров.

Классическая задача о ранце (КЗР). Имеются ранец и предметы П1, П2,…, Пn;

каждый предмет Пi характеризуется двумя целыми положительными показателями: сi – стоимость предмета; vi – вес предмета, i = 1, n. Предметы недробимы, т.е. каждый из них можно поместить в ранец только целиком. Требуется найти совокупность предметов, которые следует поместить в ранец с тем, чтобы суммарная стоимость предметов в ранце оказалась максимальной при условии, что суммарный вес предметов в ранце не может превысить заданной натуральной константы W (предполагается, что суммарный вес всех имеющихся предметов больше W).

программирования (БЛП):

при условиях Задачу (1.29)- (1.31) далее будем именовать задачей Z.

По начальным данным задачи Z формулируем совокупность частных задач о ранце Z(k, p), где k{1, 2,…, n}; р{1, 2,…, W}. Задача Z(k, p) записывается следующим образом:

при условиях (в частной задаче Z(k, p) имеющимися в наличии считаются только первые k предметов из совокупности {П1, П2,…, Пn}, суммарный вес предметов в ранце не может превышать константы р).

Оптимальное значение критерия в частной задаче Z(k, p) обозначим В*(k, p).

Как очевидно, задача Z(n,W) совпадает с исходной задачей Z; поэтому В*(n,W) – оптимальное значение критерия в задаче Z.

Пусть для некоторого k, принадлежащего множеству {1, 2,…, n-1} и всех р{1, 2,…, W} значения функции В*(k, p) уже вычислены. При р{0,1,2,…, vk+1- 1} cитуация, возникающая при нахождении В*(k+1, p), фактически не отличается от ситуации, имевшей место при подсчете В*(k, p), ибо дополнительно появляющийся при переходе от задачи Z(k, p) к задаче Z(k+1, p) предмет Пk+1 в ранец поместить невозможно. В случае, когда р{vk+1, vk+1+1,…,W}, при переходе от задачи Z(k, p) к задаче Z(k+1, p) мы получаем дополнительную возможность поместить в ранец предмет Пk+1. Этой возможностью можно: а) не воспользоваться; б) воспользоваться. Очевидно, что в случае а) мы получим уже вычисленную величину В*(k, p). В случае б) в ранец кладется предмет Пk+1 стоимостью сk+1 и так как вес этого предмета равен vk+1, то далее мы оказываемся в условиях задачи Z(k, p - vk+1). В итоге получаем:

здесь k= 2, 3,…, n-1.

Равенства (1.32) - (1.33) – рекуррентные соотношения динамического программирования для решения задачи о ранце. Пользуясь ими, мы находим сначала величины В*(1, p), р{1, 2,…, W}, затем величины В*(2, p), р{1, 2,…, W}, и т.д., вплоть до отыскания В*(n, W) – оптимального значения критерия в исходной задаче Z.

Процедуру вычисления значений функции В*(k, p) целесообразно реализовывать как процесс последовательного заполнения строк таблицы стоимостей.

В этой таблице строки соответствуют значениям параметра k (по возрастанию), а столбцы – значениям параметра р (также по возрастанию). В каждую клетку, расположенную в пересечении произвольной строки k и произвольного столбца р, вносится значение В*(k, p). Первая строка заполняется согласно формуле (1.32). Далее заполнение каждой (k+1)-ой строки, k= 1,2,…, n-1, осуществляется в соответствии с формулой (1.33). Одновременно целесообразно фиксировать множества предметов М(k, p), которые обеспечивают значения В*(k, p) критериев рассматриваемых частных задач.

Как очевидно, М(1, p) =, если р < v1; М(1, p) ={1} в противном случае. Далее можно считать В заполненной таблице стоимостей содержимое клетки (n, W) – оптимальное значение критерия в задаче Z. Для обеспечения этого значения в ранец следует поместить предметы совокупности М(n, W).

ПРИМЕР 1.6. Решить КЗР:

при условиях Таблица 1.4. Таблица стоимостей для примера 1.6.

Задача решается путем последовательного, сверху вниз, заполнения строк таблицы стоимостей (таблица 1.4). В каждой клетке (k,p) данной таблицы вслед за полученным значением В*(k, p) в скобках малыми цифрами перечисляются номера предметов, которые согласно оптимальному решению частной задачи Z(k, p) следует положить в ранец. Если задача Z(k, p) имеет несколько оптимальных решений, то указывается только одно из них. Заполнение первой строки таблицы выполняется в соответствии с формулой (1.32); здесь считается, что в нашем распоряжении имеется только предмет П1, его стоимость равна 5 и вес равен 2. Предмет П1 можно положить в ранец, если дозволенный вес предметов в ранце не меньше чем 2. Поэтому В*(1, 1)= и В*(1, p) = 5, если p 2. Заполнение второй и каждой из нижеследующих строк выполняется в соответствии с формулой (1.33). Рассмотрим в качестве иллюстрации, причем на содержательном уровне, как заполняется клетка (4, 8). Данная клетка соответствует задаче Z(4, 8). В сравнении с задачей Z(3, 8), которой соответствует клетка (3, 8), в Z(4, 8) появляется новая возможность – в ранец можно положить предмет П4. Согласно формуле (1.33), выбирается лучший из двух вариантов. Первый вариант предполагает, что возможностью положить в ранец предмет П4 мы не воспользовались. Тогда имеет место абсолютно та же ситуация, что в задаче Z(3, 8), и мы можем обеспечить суммарную стоимость предметов в ранце равную В*(3, 8), т.е.

числу 11, записанному в клетке, расположенной непосредственно над заполняемой.

Итак, первый вариант обеспечивает суммарную стоимость предметов в ранце, равную 11; реализация данного варианта означает, что в ранец кладутся предметы П1, П2 и П3.

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

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

непосредственно над полученной клеткой, а именно в клетке (3, 4) записано число 9, это максимально возможная суммарная стоимость предметов, взятых из совокупности {П1, П2, П3}, при условии, что их суммарный вес не превышает четырех (в этой ситуации как показывает заполнение клетки (3, 4), из указанной совокупности следует взять первый и третий предмет). Таким образом, второй вариант обеспечивает суммарную стоимость предметов в ранце 7 + 9=16; реализация данного варианта означает, что в ранец кладутся предметы П1, П3 и П4. Второй вариант дает лучший результат, заполнение клетки (4, 8) осуществляется по этому варианту.

Некоторые действия, выполненные нами при решении примера 1.6, являются излишними. Для решения КЗР все клетки таблицы стоимостей заполнять не обязательно. В последней строке нам достаточно заполнить только одну, крайне правую клетку (n, W). Согласно формуле (1.33), для этого достаточно знать содержимое только двух клеток предпоследней строки, а именно клетки (n-1, W) и клетки (n-1, Wvn). Для заполнения указанных клеток предпоследней строки достаточно знать заполнение максимум четырех клеток строки n-2, и т.д. Процессу счета по соотношениям динамического программирования (1.32)-(1.33) целесообразно предварить процесс разметки, когда двигаясь по строкам таблицы снизу вверх, мы отмечаем, заполнение каких клеток таблицы действительно необходимо для решения заданной КЗР.

К рассмотренной КЗР легко сводится и, следовательно, может решаться алгоритмом Акзр задача "Разбиение", формулируемая следующим образом. Имеется конечное множество натуральных чисел W ={v1,v2,…,vn}. Требуется определить, можно ли разбить совокупность W на два непересекающихся подмножества так, чтобы сумма элементов, входящих в одно подмножество, совпала с суммой элементов, входящих в другое подмножество.

Задачу "Разбиение" определяет набор натуральных чисел {v1,v2,…,vn}. Будем считать, что сумма всех входящих в множество W чисел четна (в противном случае рассматриваемая задача положительного решения заведомо не имеет). Пусть v1+v2 +…+ vn = 2V, где V – натуральное число. По имеющемуся набору {v1,v2,…,vn} строим следующую КЗР:

Оптимальное значение критерия в этой КЗР не может превысить V, ибо критерий задачи совпадает с левой частью ее линейного ограничения. Оптимальное значение критерия равно V тогда и только тогда, когда исходная задача "Разбиение" имеет положительное решение (т.е. совокупность W можно разбить на два непересекающихся подмножества так, чтобы сумма элементов, входящих в одно подмножество, совпала с суммой элементов, входящих в другое подмножество.). В отвечающем оптимальному решению КЗР разбиении элемент wi включается в первое подмножество, если переменная хi принимает значение 1, и во второе подмножество, если хi принимает значение 0, i=1, n.

Часто задачу "Разбиение" называют задачей о камнях. При этом предполагается следующая интерпретация. Имеется куча, состоящая из n камней.

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

задачи:

при условиях Задачу (1.34) - (1.36) будем называть многомерной задачей о ранце и обозначать символом Zm.

По начальным данным задачи Zm формулируем совокупность частных задач Z(k, р), где k {1, 2, …, n}; р = (p1, p2,…, pm), причем рj {0, 1, 2,…, Wj}, j=1, m. В частной задаче Z(k, р) считаются имеющимися в наличии только первые k предметов из совокупности {П1, П2, …, Пn}, величина суммарного веса предметов в ранце по j-ому показателю, j=1, m, не может превышать константы рj. Оптимальное значение критерия в частной задаче Z(k, р) обозначим В*(k, p). Задача Zm совпадает с задачей Z(n,W), где W = (W1, W2,…, Wm). Поэтому В*(n, W) – оптимальное значение критерия в задаче Zm.

Процедура решения задачи Zm методом динамического программирования представима как процесс заполнения таблицы стоимостей, строки которой соответствуют возможным значениям параметра k (по возрастанию), а столбцы – возможным значениям векторного параметра р = (p1, p2,…, pm). Для определенности считаем, что в заголовочной для столбцов строке этой таблицы векторы перечисляются в соответствии с их лексикографическим порядком по возрастанию. В клетку, расположенную в пересечении строки k и столбца р, вносится значение В*(k, p).

Заполнение клеток производится по строкам, в порядке возрастания их номеров.

Рекуррентные соотношения динамического программирования для решения задачи Zm очевидным образом обобщают равенства (1.32)-(1.33) на случай многомерной задачи.

Оценим вычислительную сложность алгоритма в применении к m-мерной задаче. Пусть максимальная из координат вектора W равна W. В таком случае число подлежащих заполнению столбцов таблицы стоимостей имеет верхнюю оценку (W+1)m. Число строк таблицы равно n. Верхняя оценка числа подлежащих заполнению клеток n (W+1)m.

Число элементарных операций, необходимых для определения заполнения каждой отдельной клетки, является функцией, линейно зависящей от m. Получаем, что Сmn(W+1)m – верхняя оценка числа элементарных операций, выполняемых изложенным алгоритмом при решении m-мерной задачи о ранце; здесь С – константа, не зависящая от конкретных характеристик задачи. В частном случае, для одномерной задачи о ранце (m=1) получаем оценку СnW; можно считать, что константа С не превосходит 10.

Задача отыскания кратчайших путей (ЗОКП). Считается заданным конечный взвешенный ориентированный граф G с множеством вершин N = {1, 2,…, n}, веса всех дуг неотрицательны. Веса дуг трактуем как их длины. Последовательность i1,i2,…, ik вершин графа G определяет путь из вершины i1 в вершину ik, если для каждого t =1, 2,…, k-1 в данном графе имеется дуга (it, it+1); указанные дуги образуют путь i1,i2,…, ik.

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

Вес дуги (i,j) графа G обозначаем с(i,j). Длину кратчайшего пути из 1 в х будем называть расстоянием от вершины 1 до вершины х. Расстояние от вершины 1 до вершины х будем обозначать s(x).

Ясно, что s(1) = 0. Пусть H – множество вершин, длины кратчайших путей из вершины 1 в которые уже известны. В начальной ситуации это множество одноэлементно: H = {1}. Через s(1, M) обозначим минимальную из длин кратчайших путей от вершины 1 до вершин множества М, М{2, 3,…, n}. Как очевидно, для множества вершин Н, содержащего вершину 1, имеет место Пусть минимум правой части (1.40) реализуется на паре (i0, j0). Тогда кратчайший путь из вершины 1 в вершину j0 получаем добавлением к кратчайшему пути из вершины 1 в вершину i0 дуги (i0,j0), длина s(j0) этого пути равна s(i0) + с(i0,j0).

программирования для решения ЗОКП. Пользуясь этой формулой, на первом шаге определяем ближайшую к вершине 1 вершину i1 из совокупности {2, 3,…, n}. На втором шаге определяем ближайшую к вершине 1 вершину i2 из совокупности {2, 3,…, n}\{i1}. На третьем шаге определяем ближайшую вершине 1 вершину i3 совокупности {2, 3,…, n}\{i1, i2}, и т.д. В процессе счета строится дерево D кратчайших путей из вершины 1 в остальные вершины. Корнем D является вершина 1; если на произвольном шаге алгоритма минимум правой части (1.40) реализуется на паре (i0,j0), к конструируемому дереву добавляется ребро (i0,j0).

Ход выполняемых вычислений можно оформить в виде процесса заполнения таблицы, строки которой соответствуют вершинам графа G (i-ая строка – вершине i, i = 1, n ). Таблица заполняется по столбцам, слева направо (каждый столбец для определенности заполняется сверху вниз). При этом первый (левый) столбец таблицы имеет имя "1". При заполнении столбца "1" в клетку, стоящую в пересечении с j-ой строкой, j {2, 3,…, n}, вносится с(1,j), если дуга (1, j) в графе G имеется, и +, если такой дуги в графе нет. После заполнения этого столбца, в нем символом * отмечается наименьший элемент (в случае, когда таких элементов несколько, отмечается любой из них). Если отмеченный символом * элемент равен u и находится в строке номер v, то длина кратчайшего пути от вершины 1 до вершины v найдена, s(v)= u. Первый шаг работы алгоритма реализован. Каждый следующий шаг алгоритма предусматривает заполнение очередных двух столбцов таблицы. Результатом каждого следующего шага является определение расстояния от вершины 1 до еще одной вершины. После того, как очередное расстояние s(х) определилось, соответствующая строка х таблицы считается отмеченной, дальнейшее заполнение клеток отмеченных строк не производится. В момент, когда строка становится отмеченной, во всех незаполненных ее клетках ставим специальный символ z. Изначально отмеченной считается первая строка таблицы, ибо значение s(1) известно с самого начала: s(1) = 0.

На втором шаге алгоритма второй столбец таблицы, а на последующих шагах – каждый следующий четный столбец, приобретает название последней вершины х графа G, для которой реализуемая вычислительная процедура в результате выполнения предшествующего шага определила расстояние от 1 до х. В заголовках первого, второго и далее каждого следующего четного столбца рядом с его именем "х" указывается значение s(х). При заполнении второго и каждого следующего четного столбца "х" в каждую клетку, находящуюся в пересечении с неотмеченной строкой j вносится сумма s(х) + с(х,j); если в графе G дуга (х,j) отсутствует, в клетку вносится символ +. Третий и далее каждый следующий нечетный столбец имеет наименование "min". В каждую клетку такого столбца, стоящую в пересечении с j-ой неотмеченной строкой, вносится минимальное из расстояний, записанных в двух соседних слева клетках данной строки.

После заполнения каждого очередного столбца "min", в нем отмечается символом * наименьший элемент (если таких элементов несколько, отмечается любой из них). Если отмеченный символом * элемент последнего заполненного столбца "min" равен u и находится в строке номер v, то, согласно (1.40), считаем найденной длину кратчайшего пути от вершины 1 до вершины v, s(v)= u. С этого момента v-ая строка таблицы переходит в число отмеченных строк, дальнейшее заполнение ее клеток производиться не будет. Следующий подлежащий заполнению столбец четный, ему назначается имя "v", в заголовке этого столбца указывается также найденное значение s(v). Далее заполняется очередной столбец "min". В результате заполнения каждой следующей пары столбцов определяется расстояние от вершины 1 до еще одной вершины графа, таким образом завершается реализация следующего шага алгоритма. Изначально известно, что s(1) = 0. Поэтому общее число заполняемых пар столбцов n-1.

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

ПРИМЕР 1.7. Взвешенный ориентированный граф G задан матрицей Числовой элемент mij этой матрицы равен весу дуги (i,j) графа G; если дуга в графе отсутствует, то mij =. Веса дуг трактуются как их длины. Требуется найти расстояния от вершины 1 до остальных вершин графа.

Ход выполняемых в процессе решения вычислений отображаем как последовательное заполнение столбцов таблицы 1.5.

Таблица 1.5. Таблица определения расстояний.

В итоге получаем, что в рассматриваемом графе G расстояния от вершины 1 до вершин 2, 3, 4, 5, 6 и 7 равны соответственно 5, 3, 4, 2, 1 и 3.

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

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

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

Задача вычисления произведения матриц. Заданы прямоугольные матрицы М1, М2,…, Мn таких размеров, что произведение этих матриц определено. Известно, что умножение (pq)-матрицы на (qr)-матрицу требует выполнения f(p,q,r) элементарных операций, где функция f – монотонно возрастающая по всем своим аргументам. Требуется найти порядок перемножения матриц М1, М2,…, Мn, при котором являющаяся результатом перемножения матрица М вычисляется выполнением минимального числа арифметических операций.

Рассмотрим пример, в котором считаем, что умножение (pq)-матрицы на (qr)-матрицу требует выполнения 2pqr элементарных операций; это практически соответствует действительности. Пусть матрицы М1, М2, М3 и М4 имеют размеры 10х20, 20х50, 50х1 и 1х100 соответственно. Если вычислять М в порядке, определяемом записью (М1х(М2х(М3хМ4))), то потребуется 250000 операций. Если же вычислять М в порядке, определяемом записью ((М1х(М2хМ3))хМ4), понадобится выполнить только 4400 операций.

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

Задачу определения оптимальной (т.е. минимизирующей число выполняемых элементарных операций) схемы перемножения матриц М1, М2,…Мn, каждая матрица Мi имеет размер riхri+1, i = 1, n, назовем задачей Z. Введем совокупность частных задач Z(i,j), каждая задача Z(i,j) заключается в синтезе схемы оптимального вычисления произведения МiхМi+1х…хМj, здесь i =1, n ; j =1, n ; i j. Минимальное число элементарных операций, необходимое для вычисления МiхМi+1х…хМj, обозначим mij;

как очевидно, mii = 0.

Значения mij будем вычислять последовательно, в порядке возрастания разности индексов j - i. Считаем, что умножение (pq)-матрицы на (qr)-матрицу требует выполнения f(p,q,r) элементарных операций. Тогда Рекуррентные соотношения (1.41)-(1.42) позволяют находить значения mij и определять соответствующие схемы умножения матриц последовательно, в порядке увеличения разности j - i от 1 до n-1. В результате окажется найденной величина m1n и соответствующая оптимальная схема перемножения матриц М1, М2,…Мn.

Процесс вычислений по приведенным соотношениям продемонстрируем на приведенном выше примере. Полагаем, что f(p,q,r) =2pqr. Тогда в соответствии с (1.41):

m12 = 2х10х20х50 = 20000; m23= 2х20х50х1= 2 000; m34= 2х50х1х100 = 10000.

Далее, пользуясь (1.42), получаем:

000+2x10x20x1, 20 000 +0 + 2x10x50x1} = min{2 400, 21 000} = 2 400.

10000+2х20х50х100, 2 000 + 0+2х20х1х100}= min{20 000, 4 000}= 4 000.

m14 = min{ 0 + 4 000 + 2x10x20x100, 20 000 + 10 000+2x10x50x100, 2 400 + 0 + 2x10x1x100}= min{44 000, 130 000, 4 400}= 4 400.

Таким образом, в приведенном примере минимальное число операций, необходимое для вычисления матрицы М =М1х М2х М3 х М4 равно 4 400. Схема перемножения ((М1х(М2хМ3))хМ4) оказывается оптимальной.

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

Задача отыскания максимального произведения. Пусть Мi – конечные множества натуральных чисел, Мi = {m i1, m i2,,...,m ik(i)}, i =1, n ; считаем, что входящие в состав каждого множества числа перечислены по возрастанию. В каждом из множеств Мi, i =1, n, надо выбрать по одному элементу так, чтобы сумма этих чисел не превысила заданного числа S, а произведение оказалось максимально возможным.

Обозначим через В(r, z), где r{1, 2,…,n}и z{0,1, 2,…, S}, максимально возможную величину произведения r чисел при условиях: а) эти числа берутся из множеств Мn-r+1, Мn-r+2,…, Мn (по одному числу из каждого множества); б) сумма взятых чисел не превышает z. Как очевидно, В(n,S) – искомое оптимальное значение критерия в решаемой задаче.

Если каждый элемент множества Мn больше z, полагаем В(1,z) = 0; в остальных случаях согласно сделанному определению В(1,z) равно максимальному, не превосходящему z, элементу множества Мn. Далее для значений r, последовательно равных 2, 3,…,n, имеем:

здесь U(r,z) = {j | (j{1, 2,…, k(n-r+1) &( m n-r+1j 1, имеем здесь Wi – произвольное i-элементное подмножество из совокупности {1,2,…,n}.

Записанные равенства (1.44)-(1.45) являются соотношениями динамического программирования для решения КЗН. Легко видеть, что оценкой числа элементарных операций, выполняемых основанным на соотношениях (1.44) - (1.45) алгоритмом, является функция, которая экспоненциально зависит от n. В отличие от всех остальных рассматриваемых в данном разделе задач, для КЗН имеются алгоритмы, обладающие существенно лучшими в сравнении с процедурой счета по соотношениям динамического программирования, характеристиками быстродействия.

Классическая задача о назначениях с кубично зависящей от n верхней оценкой числа выполняемых элементарных операций решается, в частности, алгоритмом Куна.

Изложение этого алгоритма приведено в ряде источников (см., например, [6, 10]).

Задача о назначениях с учетом предпочтений исполнителей данные задачи определяем как набор объектов где I = {1, 2,..., n} – совокупность исполнителей; R = {r1, r2,..., rn} – совокупность работ;

А = {aij } – (nxn)-матрица численных оценок, аij – оценка закрепления исполнителя i за работой rj; L = { 1, 2,..., n} – упорядочения, определяющие предпочтения исполнителей на множестве работ (выполнение отношения х i y означает, что для исполнителя i работа у в сравнении с работой х является не менее предпочтительной).

Если соотношения х i y и у i х имеют место одновременно, то работы х и у для исполнителя i считаются равноценными, эквивалентными (в таком случае используем обозначение х i у). Если х i y, но работы х и у для исполнителя i неэквивалентны, то работа у для исполнителя i является лучшей, более предпочтительной в сравнении с работой х, а работа х соответственно худшей в сравнении с работой у (в данной ситуации используем обозначение х а(q+1) (q).

Разделив обе части полученного неравенства на положительное произведение (q) (q+1), получаем Неравенство (2.5) – следствие сделанного предположения об оптимальности расписания 0. Из этого неравенства вытекает простейший алгоритм синтеза оптимального расписания в задаче мастера: для каждой заявки i нужно определить показатель µ(i) = а(i) / (i), i =1, n, и упорядочить заявки по убыванию значений µ(i).

Полученная перестановка является оптимальным расписанием обслуживания имеющегося множества заявок.

Изложенный способ отыскания правила оптимального упорядочения заявок называется перестановочным приемом. Найденный для задачи мастера способ синтеза оптимального расписания именуем µ - правилом. Содержательный смысл его очевиден:

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

Двухпроцессорная задача мастера. Отличие рассматриваемой задачи от предыдущей состоит в наличии двух идентичных процессоров, Р1 и Р2. Каждая заявка множества {1,2,…,n} должна быть обслужена либо первым, либо вторым процессором.

Оба процессора считаются готовыми к обслуживанию заявок начиная с момента времени t = 0. Обслуживание одной заявки двумя процессорами считается невозможным. Расписание определяем как пару =(1, 2), где 1= (i1,i2,i3,…,ip) перестановка, определяющая последовательность обслуживания заявок первым процессором, а 2= (j1,j2,j3,…,jq) - перестановка, определяющая последовательность обслуживания заявок вторым процессором. Каждая заявка входит либо в первую, либо во вторую перестановку, поэтому р + q =n. Требуется найти расписание, минимизирующее суммарный по всем заявкам штраф.

По аналогии с результатами, полученными для однопроцессорной задачи мастера, можно предположить, что оптимальным является расписание, синтезируемое в соответствии с интерпретируемым следующим образом µ - правилом: упорядочиваем совокупность всех заявок по убыванию показателя µ(i), в этом порядке выполняем их перенумерацию и в этом же порядке направляем на обслуживание освобождающимися процессорами. В синтезируемом расписании процессоры Р1 и Р2 сначала должны обслужить заявки 1 и 2 соответственно (все номера заявок – новые), заявка направляется следующей на процессор, который раньше освободится. Точно так же заявка 4 направляется следующей на процессор, который раньше обслужит поступившие ему заявки из совокупности {1, 2, 3}, и т.д.

Покажем, что в двухпроцессорной задаче мастера конструируемое применением µ - правила расписание не всегда оптимально. Рассмотрим пример, в котором множество подлежащих обслуживанию заявок трехэлементно, их характеристики заданы таблицей 2.1.

Таблица 2.1. Характеристики заявок.

Применением µ - правила в рассматриваемом примере строится расписание 0= (1, 2), где 1 = (1, 3) и 2 = (2). В случае реализации этого расписания суммарный штраф по трем заявкам равен 10111. В то же время при реализации расписания 1= ((1,2), (3)) будем иметь суммарный штраф, равный 10015. Таким образом, в двухпроцессорной задаче мастера расписание, синтезируемое в соответствии с µ - правилом, оптимальным вообще говоря, не является.

Для синтеза оптимального в двухпроцессорной задаче мастера расписания применим метод динамического программирования. Будем считать, что все заявки пронумерованы в порядке убывания значений показателя µ. Тогда если =(1, 2) – оптимальное расписание, то заявки в каждой из последовательностей 1= (i1,i2,i3,…,ip) и 2= (j1,j2,j3,…,jq) записаны в порядке возрастания номеров.

При синтезе оптимального расписания для каждой следующей (в порядке возрастания номеров, т.е. по убыванию показателя µ) заявки i + 1 мы должны определить, на какой из двух процессоров ее направить в качестве подлежащей обслуживанию в следующую очередь. При этом все заявки множества {1, 2,…,i} по процессорам уже распределены, известны величины промежутков времени, которое будет потрачено на обслуживание этих заявок первым и вторым процессорами; время работы процессора Р1 над предписанными ему заявками из совокупности {1, 2,…,i} обозначим. В таком случае время работы процессора Р2 над заявками из той же совокупности равно величину суммарного штрафа по заявкам множества {1, 2,…,i}, если на обслуживание направленных на процессор Р1 заявок из этого множества затрачивается время. Как очевидно, При значениях аргумента, отличных от нуля и (1), определяемая парой (1, ) ситуация возникнуть не может; удобно положить далее для любых нереализуемых ситуаций (i, ) из рекуррентных соотношений будем получать W*(i, ) =+.

Предположим, что все значения функции W*(i, ) для некоторого конкретного значения i уже найдены. Рассмотрим ситуацию в процессе обслуживания, определяемую парой (i+1, ). В случае (i+1) непосредственно предшествующими для этой ситуации являются две: (i, ) и (i, – (i+1)); в случае < (i+1) непосредственно предшествующей является только ситуация (i, ); значение W*(i, – (i+1)), где второй аргумент функции отрицательный, считается равным +. Переход от ситуации (i, ) к ситуации (i+1, ) предполагает, что обслуживание заявки i+ выполняется процессором Р2; обслуживание этой заявки начинается в момент времени ситуации (i+1, ) предполагает, что обслуживание заявки i+1 выполняется процессором Р1; обслуживание начинается в момент времени -(i+1)) и завершается в момент..

Отсюда получаем:

W*(i+1, ) =min{ W*(i, – (i+1))+ a(i + 1), W*(i, )+a(i+1){ ( ) –}} (2.8) Процедуру вычисления значений функции W*(i, ) удобно представлять как процесс заполнения таблицы, строки которой соответствуют значениям параметра i, а столбцы – значениям параметра ; в клетку, являющуюся пересечением строки i и столбца, вносится значение W*(i, ). Общее число строк таблицы значений функции W*(i, ) равно n. Величины W*(i, ) требуется определять для значений второго аргумента из множества {0, 1, …, ( ) +1. Строки таблицы заполняются сверху вниз, в порядке роста значений равно параметра i. Первая строка заполняется по формулам (2.6) – (2.7), остальные – по формуле (2.8). Отметим, что в силу идентичности процессоров в клетки (i+1, ) и (i, ( ) – ).вносятся одинаковые числа; если при вычислении значения W*(i+1, ) минимум правой части (2.8) реализуется на первой (второй) компоненте, то при отыскании величины W*(i, второй (соответственно первой) компоненте. Оптимальным значением критерия в решаемой задаче является минимальный элемент, внесенный в нижнюю строку таблицы значений функции W*(i, ). Если данный элемент находится в столбце ', то общее время работы одного процессора в реализации оптимального расписания равно ', время работы другого процессора равно Для обеспечения возможности синтеза оптимального расписания в каждую клетку (i+1, ) таблицы кроме значения W*(i+1, ), требуется записывать условный символ, указывающий, на какой компоненте правой части соотношения (2.8) при вычислении W*(i+1, ) реализуется минимум.

Равенства (2.6) – (2.8) – рекуррентные соотношения динамического программирования для решения двухпроцессорной задачи мастера.

ПРИМЕР 2.1. Требуется построить оптимальное расписание обслуживания заявок 1 –5 в системе, состоящей из двух идентичных процессоров. Характеристики заявок следующие: а(1) = 5, (1) =2; а(2) = 4, (2) =1; а(3) =7, (3) =3;а(4) =3, (4) =3;а(5) =2, (5) =2.

Решение начинается с переупорядочивания (введения новой нумерации) заявок с тем, чтобы заявкам с большими номерами соответствовали меньшие значения показателя µ. В рассматриваемом примере заявке 2 присваивается новый номер 1, заявке 1 – новый номер 2; остальные заявки номеров не меняют. Складывая заданные времена обслуживания заявок, получаем, что максимальное значение параметра равно 11. Результаты выполненной в соответствии с соотношениями (2.6) - (2.8) процедуры счета представлены в таблице 2.2. В клетки, где при вычислении внесенного значения функции минимум правой части (2.8) реализуется на первой компоненте, внесен дополнительный символ *.

Таблица 2.2. Значения функции W*(i, ).

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

Для определенности считаем, что в качестве минимального в нижней строке взят элемент, стоящий в пятом столбце, т.е. заключительной является ситуация (5,5), на обслуживание всех заявок первый процессор затрачивает 5 тактов дискретного времени. Так как взятый в нижней строке таблицы минимальный элемент отмечен звездочкой, заявка 5 должна обслуживаться процессором Р1, на это затрачиваются такта. Из отмеченного вытекает, что ситуацией, непосредственно предшествующей ситуации (5,5), является (4,3). Стоящий в пересечении четвертой строки и третьего столбца таблицы элемент звездочкой не отмечен, заявка 4 должна обслуживаться процессором Р2, непосредственно предшествующей ситуации (4,3) является ситуация (3,3). Элемент, стоящий в пересечении третьей строки и третьего столбца отмечен звездочкой; заявка 3 должна обслуживаться процессором Р1. Непосредственно предшествующей ситуации (3,3) является ситуация (2,0). Последнее означает, что заявки 1 и 2 должны обслуживаться процессором Р2. В итоге получаем, что оптимальным в рассматриваемом примере является (номера заявок - новые) расписание =(1, 2), где 1 = (3,5) и 2 = (1, 2, 4). Легко проверяется, что при реализации построенного расписания суммарный штраф по всем заявкам действительно равен 68.

В заключение переходим к исходным номерам и фиксируем, что оптимальным в рассмотренном примере является расписание ((3,5),(2, 1, 4)).

Если в нижней строке таблицы 2.2 в качестве минимального зафиксировать элемент, стоящий в :6-ом столбце, то в итоге будет построено также оптимальное расписание ((2, 1, 4), ((3,5)).



Pages:     || 2 | 3 |


Похожие работы:

«67.99 К 93 /пекдекцт/ в сщр^укту/іе Костанайская Социальная академия Курзова Н. А. Абдуллина А. А. Этиоправовые тенденции в структуре мусульманского права. Костанай 2002 I/ ББК 67.99 (2) Курзова Н. Д., Абдуллина Д. Д. Эхноправовь.е тенденции в структуре мусульманского права.— Костанай, 2002 г. - 284 стр. ISBN № 9965-13-730-7 ББК 67.99 (2) Одобрено научно-методическим советом Костанайской Социальной академии. Рецензент: доктор философских наук, профессор Мурзапин С. К. Авторы составители:...»

«1 ПСИХОЛОГИЯ. ЛОГИКА 1. Ананьев, Борис Герасимович. Избранные труды по психологии / Б. Г. АнаньЮ9 ев. - СПб. : Изд-во СПбГУ Г640 Т. 1 : Очерки психологии; История русской психологии. - 2007. - 412 с.; 21 см Экземпляры: всего:1 - ЧЗ (1) 2. Ананьев, Борис Герасимович. Избранные труды по психологии / Б. Г. АнаньЮ9 ев. - СПб. : Изд-во СПбГУ А640 Т. 2 : Развитие и воспитание личности. - 2007. - 549 с.; 21 см Экземпляры: всего:1 - ЧЗ (1) 3. Батаршев, Анатолий Васильевич. Ю9 Диагностика...»

«НОУ ВПО ИВЭСЭП НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ИНСТИТУТ ВНЕШНЕЭКОНОМИЧЕСКИХ СВЯЗЕЙ, ЭКОНОМИКИ И ПРАВА МЕЖДУНАРОДНОЕ ЧАСТНОЕ ПРАВО УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по специальности 030501.65 Юриспруденция САНКТ-ПЕТЕРБУРГ 2011 2 Международное частное право: Учебно-методический комплекс / Авторсоставитель: Крайнова С.А., СПб: СПб ИВЭСЭП, 2011. Материалы комплекса по международному частному праву предназначены для оказания...»

«Министерство образования Республики Беларусь УО ПОЛОЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра уголовного права и криминалистики УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ для самоподготовки и самоконтроля для студентов заочной формы обучения по дисциплине АДМИНИСТРАТИВНОЕ ПРАВО для специальности 24-01-02 Правоведение г. Новополоцк, 2013 Рассмотрены и рекомендованы к утверждению на заседании кафедры уголовного права и криминалистики, протокол №_ от _ _ 2012 г. Заведующий кафедрой И.В. Вегера Составитель:...»

«Пояснительная записка Рабочая программа Музыка для школ (классов) с углубленным изучением предметов художественно-эстетического цикла базируется на программах, выпущенных под грифом Министерства образования РФ. Программа Музыка 5-8кл. Авт. Г.Сергеева. Е.Критская. Изд. М. Просвещение, 2007г. Программы образовательных учреждений. Музыка. Под руководством Д.Б.Кабалевского. 1-8 кл. –М. Просвещение, 2006 Программы образовательных учреждений. Музыка. Авторы В.В.Алеев, Т.И.Науменко. М. Просвещение,...»

«Примерная программа среднего (полного) общего образования 10—11 КЛАССЫ (Базовый уровень) Пояснительная записка Статус документа Примерная программа по физике составлена на основе федерального компонента Государственного стандарта среднего (полного) общего образования. Примерная программа конкретизирует содержание предметных тем образовательного стандарта на базовом уровне; дает примерное распределение учебных часов по разделам курса и рекомендуемую последовательность изучения разделов физики с...»

«ФГОБУ ВПО ФинансОВый УниВерситет При ПраВительстВе рОссийскОй Федерации МАКРОЭКОНОМИКА ТеОРИя И РОссИйсКАя пРАКТИКА Под редакцией профессора А.Г. Грязновой и профессора Н.Н. Думной Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов, обучающихся по экономическим специальностям Шестое издание, стереотипное УДК 330(075.8) ББК 65.012.2я73 М15 Учебник удостоен первой премии в номинации Экономика на конкурсе Лучшая научная книга 2005 года,...»

«Государственное образовательное учреждение высшего профессионального образования Липецкий государственный технический университет Экономический факультет Утверждаю: Декан экономического факультета Московцев В.В.. _2011 г. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ Теоретические основы товароведения и экспертизы Направление подготовки: 080100 Экономика Профиль подготовки: Коммерция Квалификация (степень) выпускника: бакалавр Форма обучения: очная г. Липецк – 2011 г. Содержание Цели освоения учебной...»

«ГБУЗ КО Кемеровская областная научная медицинская библиотека Научная библиотека ГОУ ВПО КемГМА Росздрава ГУК Кемеровская областная научная библиотека им. В.Д. Федорова Медицинская литература (текущий указатель литературы) Вып. 2 Кемерово - 2014 Текущий указатель новых поступлений Медицинская литература издается Кемеровской областной научной медицинской библиотекой совместно с научной библиотекой КемГМА, Кемеровской областной научной библиотекой им. В.Д. Федорова. Библиографический указатель...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования ШУЙСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра теории и методики физической культуры и спорта УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по дисциплине ПЕДАГОГИЧЕСКОЕ ФИЗКУЛЬТУРНО-СПОРТИВНОЕ СОВЕРШЕНСТВОВАНИЕ для специальности 050720.65 Физическая культура со специализацией Составитель: Гогин А.Б., кандидат педагогических наук, доцент кафедры...»

«1 МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ГРАЖДАНСКОЙ АВИАЦИИ А.В. Агафонов ПСИХОЛОГИЯ И ПЕДАГОГИКА Пособие по изучению дисциплины и выполнению контрольных домашних заданий для студентов I курса специальности 030602 дневного обучения Москва – 2006 2 Рецензент: канд.педагог.наук, доцент Л.Г.Золотарева Агафонов А.В. Психология и педагогика. Пособие по изучению дисциплины и выполнению контрольных домашних заданий (для студентов I курса специальности 030602 дневного обучения) - М.: МГТУ...»

«Методические и иные документы для обеспечения образовательного процесса по направлению подготовки (специальности) 1. Учебно-методическое обеспечение для самостоятельной работы студентов № п/п Уровень, ступень образования, Автор, название, место издания, издательство, год издания учебной и учебно-методической вид образовательной программы литературы (основная, дополнительная), направление подготовки, специальность, профессия, наименование предмета, дисциплины (модуля) в соответствии с учебным...»

«Министерство образования Российской Федерации Государственное образовательное учреждение Высшего профессионального образования САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ Кафедра технологии приборостроения МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ КУРСОВОГО ПРОЕКТА ПО ОРГАНИЗАЦИИ СОВРЕМЕННОГО ПРОИЗВОДСТВА И РАЗРАБОТКЕ ТЕХНОЛОГИЧЕСКОЙ ПОДГОТОВКИ ПРОИЗВОДСТВА ( РЕИНЖЕНЕРИНГ БИЗНЕС-ПРОЦЕССА) Рекомендовано УМО по образованию в области приборостроения и...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОУ ВПО МОСКОВСКАЯ АКАДЕМИЯ ЭКОНОМИКИ И ПРАВА Воронежский филиал Кафедра экономических дисциплин УТВЕРЖДАЮ Директор Воронежского филиала д.т.н., профессор Заряев А.В. 2013 г. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по учебной дисциплине УЧЕТ НА ПРЕДПРИЯТИЯХ МАЛОГО БИЗНЕСА по специальности: 080109.65 – Бухгалтерский учет, анализ и аудит Воронеж Автор: Воронин В.П., д.э.н., профессор _ Учебно-методический комплекс рассмотрен и одобрен на заседании...»

«Муниципальное бюджетное общеобразовательное учреждение Сатинская средняя общеобразовательная школа Рассмотрена на заседании Утверждена приказом Педагогического совета № 444 от 31.08.13 Протокол № 12 от 30.08.13 Директор школы _Т.Н.Демина Рабочая программа по истории 5-9 класс 2013 – 2014 уч. год 2 Пояснительная записка Рабочая программа по истории составлена на основе федерального компонента государственного стандарта основного общего образования, примерной программы основного общего...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ ЗАОЧНЫЙ УНИВЕРСИТЕТ (ФГОУ ВПО РГАЗУ) ИКМИТ МЕТОДИЧЕСКИЕ УКАЗАНИЯ по выполнению дипломной работы студентам специальности 080301 - Коммерция (торговое дело) (специализаций: Коммерция в сфере таможенных услуг, Коммерция в сфере сервиса, Коммерция в сфере банковских услуг, Коммерция в сфере земельно-имущественных...»

«Министерство образования и науки Республики Бурятия Комитет по образованию г.Улан-Удэ Муниципальное бюджетное общеобразовательное учреждение Вечерняя (сменная) общеобразовательная школа № 3 Принято на заседании Утверждаю педагогического совета Директор_ от 3009. 2013 г. Г.П.Михайлова протокол № 1 3009. 2013 г. Перечень УМК, используемых учителями-предметниками МБОУ ВСОШ №3 в 2013-2014 учебном году. Должность по Занимаемая Учебно-методический комплекс Издательство, Учитель Класс Авторы диплому...»

«САМАРСКИЙ ЛИЦЕЙ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ОБРАЗОВАТЕЛЬНЫЕ ПРОГРАММЫ 2013-2014 УЧЕБНЫЙ ГОД Предмет, КолПрограмма (автор, название, выходные данные, гриф (если авторская - кем и когда класс, во утверждена, рецензирована)) уровень (базовый, профильный, углубленный) часов Паутова А.Г., Бененсон Е.П. Программа по информатике. 2-4 кл. / Бененсон Е.П. Информатика и ИКТ, 1 класс, углубленный 34 Информатика. Программа 2-4 кл. Бененсон Е.П. – М.: Академкнига/Учебник, 2007 Паутова А.Г., Бененсон Е.П....»

«ЧЕЛОВЕЧЕСКОЕ РАЗВИТИЕ: новое измерение социально экономического прогресса Программа развития ООН Экономический факультет МГУ им. М.В. Ломоносова ЧЕЛОВЕЧЕСКОЕ РАЗВИТИЕ: новое измерение социально экономического прогресса Учебное пособие Второе издание, дополненное и переработанное МОСКВА Издательство ПРАВА ЧЕЛОВЕКА 2008 ББК 67.91 4 39 Ч 39 Содержание данной книги не обязательно отражает точку зрения Программы развития Организации Объединенных Наций или какой либо иной организации, с которой...»

«ОГЛАВЛЕНИЕ 1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ – ВВЕДЕНИЕ В КЛИНИЧЕСКУЮ ПСИХОЛОГИЮ, ЕЕ МЕСТО В СТРУКТУРЕ ОСНОВНОЙ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЫ 2. КОМПЕТЕНЦИИ ОБУЧАЮЩЕГОСЯ, ФОРМИРУЕМЫЕ В РЕЗУЛЬТАТЕ ОСВОЕНИЯ ДИСЦИПЛИНЫ – ВВЕДЕНИЕ В КЛИНИЧЕСКУЮ ПСИХОЛОГИЮ. 3. ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ 4. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 4.1. Лекционный курс 4.2. Практические занятия 4.3. Самостоятельная внеаудиторная работа студентов (СВРС) 5. МАТРИЦА РАЗДЕЛОВ УЧЕБНОЙ ДИСЦИПЛИНЫ И ФОРМИРУЕМЫХ В НЕЙ ОБЩЕКУЛЬТУРНЫХ И...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.