16. Идея метода динам-го програм-я. Простейшие задачи, решаемые методом дин-го прогр-я.

ДП – метод оптимизации, приспособленный к операциям, в ктр процесс принятия решения может быть разбит на шаги. Такие операции наз-ся многошаговыми. Начало развития ДП относ-ся к 50-м годам ХХв. Модели ДП прим-ся при решении задач меньшего масштаба (чем ЛП), #при распред-и дефицитных капитальных вложений между возможными нов.направлениями их использ-я; при составлении календар.планов тек.и капитал.ремонта слож.оборудования и его замены. Эти модели позволяют на основе станд.подхода с использ-ем при min вмешательстве человека принимать такие решения. И если кажд.взятое в отдельности такое реш-е малосущ-но, то в совок-ти эти решения могут оказать большое влияние на прибыль. Планируя многошаг.операцию, надо выбирать упр-е на кажд.шаге с учетом всех его буд.последствий на еще предстоящих шагах. Общ.постановка задач ДП: Рассматр-ся упр-мый процесс, (эк.процесс) распре­д-я ср-в между предпр-ями, использ-я ресурсов в течение ряда лет, замены оборудов-я, пополнения запасов… В рез-те упр-я сис-ма (объект упр-я) S пере­вод-ся из начал.состояния s0 в сост-е s . Предположим, что упр-е можно разбить на n шагов, т.е. реш-е приним-ся послед-но на кажд.шаге, а упр-е, переводящее систему S из нач.сост-я в конечное, предст-ет собой совок-ть n пошаговых упр-й. Обозначим через Хк упр-е на k-м шаге (к=1, 2, ..., n). Пер-ные Хк удовлетворяют некоторым огранич-ям и в этом смысле наз-ся допустимыми (Хк может быть числом, точкой в n-мерном простр-ве, кач-ным признаком). Пусть Х(Х1, X2, ..., Хn) – упр-е, переводящее сис-му S из s0 в s . Sk – сост-е сис-мы после к-го шага упр-я. Показ-ль эф-ти рассматриваемой упр-мой опе­рации – цел.f-я - зависит от нач.состояния и упр-я: Z=F(S0;X). Сделаем неск-ко предполож-й: 1)Сост-е Sk сис-мы в конце к-го шага зависит только от предшест.сост-я Sk-1 и упр-я на к-м шаге. Это требов-е наз-ся "отсутствием последействия".

- ур-е сост-й. 2)Цел.f-я явл-ся аддитивной от показ-ля эф-ти кажд.шага. Показ-ль эф-ти кажд.шага: . Задача пошаг.оптимизации (задача ДП) формулир-ся так: опр-ть такое допустимое упр-е X, переводящее сис­-му S из s0 в s , при ктр цел.f-я принимает наиб.(наим.)

знач-е. Особен-ти модели ДП: 1)Задача оптимизации интерпретир-ся как n-шаг.процесс упр-я. 2)Цел.f-я = сумме цел.f-й кажд.шага. 3)Выбор упр-я на k-м шаге зависит только от сост-я сис-мы к этому шагу и не влияет на предшеств.шаги. 4)Сост-е Sk после k-го шага упр-я зависит только от предшеств.сост-я Sk-1 и упр-я Хк (отсутствие последействия). 5)На кажд.шаге упр-е Хк зависит от конеч.числа упр-щих пер-ных, а сост-е Sk - от конеч.числа пар-ров.

17. Опред-е графа и его осн-е характер-ки. Вершины и ребра. Графич-я интерпр-я графа. Смежность и инцидентность. Локальная степень. Подграф. Полный подграф.

Пусть А – любое мн-во. Обозначим через V(A) – мн-во всех неупорядоченных пар его различ.эл-тов. #A= {1,2,3}. Тогда V(A)={(1,2);(1,3);(2,3)}. Если мн-во А={1,2}, тогда V(A)={(1,2)}. Если A={1}, тоV(A)=. Когда в записи V(A) указ-ся пара (1,2), то это обозначает одно и то же, что и пара (2,1), т.к. она не упорядоченная. Графом наз-ся пара мн-в Г=[A,B], где А – любое непустое мн-во, ВV(A). Эл-ты из мн-ва А наз-ся вершинами графа, а эл-ты из В – его ребрами. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Геом. интерпретация графа: пусть Г=[A,B] – некоторый граф. А={a₁,a₂,…,a_p}, В={в₁,в₂,…,в_q}. Фиксируем на плоск-ти проивол.образом р-точек и назовем их А1, А2, …, Ар. Затем д/кажд.пары (а_i, а_j)В проведем отрезок, соед-щий дан.вершины. Если в некотором графе пара вершин а_i, и а_j  одному ребру, то они наз-ся смежными. В этой ситуации каждый из них наз-ся инцидентной ребру (а_i, а_j), а ребро (а_i, а_j) - инцидентно кажд.вершине а_i, и а_j. Кол-во ребер, инцидентных дан.вершине А, наз-ся ее степенью или локал.степенью графа в вершине А; обознач-е d(a) – степень вершины А. В любом графе кол-во вершин нечетной степени обяз-но четно. Пусть даны Г1=[A1,B1] и Г2=[A2,B2] – два графа таких, что А1А2, а В1В2. Тогда говорят, что граф Г1 явл-ся подграфом Г2. Если в некотором графе Г=[A,B] мн-во ребер В таково, что В=V(A), то дан.граф наз-ся полным. Если в полном графе число вершин р, то ребер будет: (р(р-1)/2). Пусть Г=[A,B] – граф и А={a₁,a₂,…,a_p} – его вершины. Построим квадрат.матрицу, состоящую из эл-тов М=(m_ij), где i,j=1,2,…,р.

Эта матрица наз-ся матрицей смеж-тей графа. Она симметрична. Сопоставим графу Г=[A,B] еще одну матрицу. А={a₁,a₂,…,a_p} – вершины, В={в₁,в₂,…,в_q} – ребра. Определим матрицу N=(n_ij) след.образом:

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