ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 28.03.2024
Просмотров: 9
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
0 – точка min. 2)если В2-АС>0, то в точке х0 экстремума нет. 3)если В2-АС=0, то вопрос о сущ-и экстремума остается откр. Глобал.экстр. F-я
имеет в точке Х0 заданной обл-ти D глобал.max – наибольшее знач-е в обл-ти D (min – наим.знач.), если нерав-во
(
) соотв-но выполн-ся д/любой точки X D. Т.(Вейерштрасса): Если обл-ть D замкнута и ограничена, то диф.f-я
достигает в этой обл-ти своих
наибольшего и наим.знач-й или в стац.точке, или в граничной точке обл-ти. Чтобы найти глобал.экстремум: 1)найти все стац.точки обл-ти D, найти в них знач-я f-и. 2)найти знач-я –и в граничных точках обл-ти D. 3)сравнить эти знач-я и сделать вывод. Услов.экстр. Пусть необх-мо найти экстре-
мум f-и
при усл-и, что переменные х1…хn удовлетв-ют ур-ям 
= 0 (*). Предполаг-ся, что f-и
и f(х) имеют непрерыв.част.производные по всем пер-ным, тогда = 0 наз-ют ур-ем связи. Точка 
, удовлетворяющей ур-ю *, явл-ся точкой усл.max (min) f-и
, если ( ) имеют место д/всех точек X, корд-ты ктр удовлетворяют ур-ям связи.
14. Метод множителей Лагранжа для решения задач нелинейного программирования.
Пусть решается задача опр-я усл.экстремума f-и
при огранич-ях =0. Составим f-ю
, ктр наз-ся f-ей Лагранжа. 
- постоян.множ-ли (множ-ли Лагранжа). Отметим, что множ-лям Лагранжа можно придать эк.смысл. Если 
- доход, соотв-щий этому плану, то - цена (оценка) i-го ресурса, хар-щая изменение экстремального знач-я целевой f-и в завис-ти от изменения размера i-го ресурса (маргинальная оценка). L(X) – f-я n+m переменных (
. Опр-е стац.точек этой f-и приводит к решению сис-мы ур-й: 
. Легко заметить, что 
, т.е. в это ур-ие входит ур-ие связи. Т.о., задача нахождения усл.экстремума f-и сводится к нахождению локал.экстремума f-и L(X). Если стац.точка найдена, то вопрос о сущ-и экстремума в прост.случаях решается на основании дост.условий экстремума – исследования знака II диф-ла 
в стац.точке при условии, что переменные приращения 
связаны соотнош-ями: 
, i=1,2,m, полученными путем диф-ния ур-ий связи. Для решения примеров, необх-мо найти усл.глобал.экстремум. Ур-ие связи приравнивается к 0. Составл-ся f-ю Лагранжа, нах-ся част.производные этой f-и по 
. Приравниваем их к 0 и получаем сис-му. Решая ее, получаем стац.точки, в ктр нах-ся знач-я f-и Z. Выбираем из всех знач-й z наиб.и наим.
15. Ос-е понятия динам-го программ-я: шаговое управление, управл-е операцией в целом, оптимальное управление, выигрыш на данном шаге, выигрыш за всю опер-ю, аддитивный критерий.
ДП – метод оптимизации, приспособленный к операциям, в ктр процесс принятия решения может быть разбит на шаги. Такие операции наз-ся многошаговыми. Начало развития ДП относ-ся к 50-м годам ХХв. Представим себе некоторую операцию, распадающуюся на ряд послед-ных «шагов» или «этапов» - # деят-ть отрасли пром-ти в течение ряда хоз.лет. Пусть эф-ть операции хар-ся каким-то показ-лем W, ктр для краткости наз-ся «выигрышем». Предположим, что выигрыш за всю операцию складыв-ся из выигрышей на отд.шагах:
, где wi – выигрыш на t-м шаге. Если W обладает таким св-вом, то его наз-ют «аддитивным критерием». Операция, о ктр идет речь, предст-ет собой упр-мый процесс, т.е. мы можем выбирать какие-то пар-ры, влияющие на его ход и исход, причем на кажд.шаге выбир-ся какое-то реш-е, от ктр зависит выигрыш на дан.шаге и выигрыш за операцию в целом. Будем наз-ть это реш-е «шаговым упр-ем». Совок-ть всех шаг.упр-й предст-ет собой упр-е операцией в целом. Обозначим его буквой х, а шаг.упр-я – буквами 
: х=( ), где - не числа, а может быть, векторы, f-и. Требуется найти такое упр-е х, при ктр выигрыш обращ-ся в max: 
. То упр-е х*, при ктр этот max достиг-ся, наз-ся оптим.упр-ем. Оно состоит из совок-ти оптим.шаг.упр-й: х*=(
). Тот max выигрыш, ктр достиг-ся при этом упр-и, обознач-ся W*: W*=max{W(x)} (величина W* есть max из всех W(x) при разных упр-ях х (max берется по всем упр-ям х, возможным в дан.усл-ях).
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] – некоторый граф. А={a1,a2,…,ap}, В={в1,в2,…,в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] – граф и А={a1,a2,…,ap} – его вершины. Построим квадрат.матрицу, состоящую из эл-тов М=(mij), где i,j=1,2,…,р.
Эта матрица наз-ся матрицей смеж-тей графа. Она симметрична. Сопоставим графу Г=[A,B] еще одну матрицу. А={a1,a2,…,ap} – вершины, В={в1,в2,…,вq} – ребра. Определим матрицу N=(nij) след.образом:
Такая матрица наз-ся матрицей инциденций графа. Дан.матрица зависит от того, как занумерованы ребра. Если в графе все вершины имеют степень 0, то матрицы инциденций не сущ-ет.
18. Опред-е графа. Матрицы смежностей и инциденций. Методы хранения графов в памяти ЭВМ.
Графом назыв-ся пара множ-в Г=[А,В], где А – любое непустое множ-во, а В – множ-во, кот-е явл-ся подмножеством множ-ва V(A). Матрицей смежности M порядка n назыв-ся матрица, сост-я из чисел mij, равных сумме чисел ориентиров-х ребер, идущих из аi в
имеет в точке Х0 заданной обл-ти D глобал.max – наибольшее знач-е в обл-ти D (min – наим.знач.), если нерав-во ( ) соотв-но выполн-ся д/любой точки X D. Т.(Вейерштрасса): Если обл-ть D замкнута и ограничена, то диф.f-я достигает в этой обл-ти своих наибольшего и наим.знач-й или в стац.точке, или в граничной точке обл-ти. Чтобы найти глобал.экстремум: 1)найти все стац.точки обл-ти D, найти в них знач-я f-и. 2)найти знач-я –и в граничных точках обл-ти D. 3)сравнить эти знач-я и сделать вывод. Услов.экстр. Пусть необх-мо найти экстре-
мум f-и
при усл-и, что переменные х1…хn удовлетв-ют ур-ям = 0 (*). Предполаг-ся, что f-и и f(х) имеют непрерыв.част.производные по всем пер-ным, тогда = 0 наз-ют ур-ем связи. Точка , удовлетворяющей ур-ю *, явл-ся точкой усл.max (min) f-и , если ( ) имеют место д/всех точек X, корд-ты ктр удовлетворяют ур-ям связи.14. Метод множителей Лагранжа для решения задач нелинейного программирования.
Пусть решается задача опр-я усл.экстремума f-и
при огранич-ях =0. Составим f-ю , ктр наз-ся f-ей Лагранжа. - постоян.множ-ли (множ-ли Лагранжа). Отметим, что множ-лям Лагранжа можно придать эк.смысл. Если - доход, соотв-щий этому плану, то - цена (оценка) i-го ресурса, хар-щая изменение экстремального знач-я целевой f-и в завис-ти от изменения размера i-го ресурса (маргинальная оценка). L(X) – f-я n+m переменных ( . Опр-е стац.точек этой f-и приводит к решению сис-мы ур-й: . Легко заметить, что , т.е. в это ур-ие входит ур-ие связи. Т.о., задача нахождения усл.экстремума f-и сводится к нахождению локал.экстремума f-и L(X). Если стац.точка найдена, то вопрос о сущ-и экстремума в прост.случаях решается на основании дост.условий экстремума – исследования знака II диф-ла в стац.точке при условии, что переменные приращения связаны соотнош-ями: , i=1,2,m, полученными путем диф-ния ур-ий связи. Для решения примеров, необх-мо найти усл.глобал.экстремум. Ур-ие связи приравнивается к 0. Составл-ся f-ю Лагранжа, нах-ся част.производные этой f-и по . Приравниваем их к 0 и получаем сис-му. Решая ее, получаем стац.точки, в ктр нах-ся знач-я f-и Z. Выбираем из всех знач-й z наиб.и наим.15. Ос-е понятия динам-го программ-я: шаговое управление, управл-е операцией в целом, оптимальное управление, выигрыш на данном шаге, выигрыш за всю опер-ю, аддитивный критерий.
ДП – метод оптимизации, приспособленный к операциям, в ктр процесс принятия решения может быть разбит на шаги. Такие операции наз-ся многошаговыми. Начало развития ДП относ-ся к 50-м годам ХХв. Представим себе некоторую операцию, распадающуюся на ряд послед-ных «шагов» или «этапов» - # деят-ть отрасли пром-ти в течение ряда хоз.лет. Пусть эф-ть операции хар-ся каким-то показ-лем W, ктр для краткости наз-ся «выигрышем». Предположим, что выигрыш за всю операцию складыв-ся из выигрышей на отд.шагах:
, где wi – выигрыш на t-м шаге. Если W обладает таким св-вом, то его наз-ют «аддитивным критерием». Операция, о ктр идет речь, предст-ет собой упр-мый процесс, т.е. мы можем выбирать какие-то пар-ры, влияющие на его ход и исход, причем на кажд.шаге выбир-ся какое-то реш-е, от ктр зависит выигрыш на дан.шаге и выигрыш за операцию в целом. Будем наз-ть это реш-е «шаговым упр-ем». Совок-ть всех шаг.упр-й предст-ет собой упр-е операцией в целом. Обозначим его буквой х, а шаг.упр-я – буквами : х=( ), где - не числа, а может быть, векторы, f-и. Требуется найти такое упр-е х, при ктр выигрыш обращ-ся в max: . То упр-е х*, при ктр этот max достиг-ся, наз-ся оптим.упр-ем. Оно состоит из совок-ти оптим.шаг.упр-й: х*=( ). Тот max выигрыш, ктр достиг-ся при этом упр-и, обознач-ся W*: W*=max{W(x)} (величина W* есть max из всех W(x) при разных упр-ях х (max берется по всем упр-ям х, возможным в дан.усл-ях).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] – некоторый граф. А={a1,a2,…,ap}, В={в1,в2,…,в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] – граф и А={a1,a2,…,ap} – его вершины. Построим квадрат.матрицу, состоящую из эл-тов М=(mij), где i,j=1,2,…,р.
Эта матрица наз-ся матрицей смеж-тей графа. Она симметрична. Сопоставим графу Г=[A,B] еще одну матрицу. А={a1,a2,…,ap} – вершины, В={в1,в2,…,вq} – ребра. Определим матрицу N=(nij) след.образом: Такая матрица наз-ся матрицей инциденций графа. Дан.матрица зависит от того, как занумерованы ребра. Если в графе все вершины имеют степень 0, то матрицы инциденций не сущ-ет.18. Опред-е графа. Матрицы смежностей и инциденций. Методы хранения графов в памяти ЭВМ.
Графом назыв-ся пара множ-в Г=[А,В], где А – любое непустое множ-во, а В – множ-во, кот-е явл-ся подмножеством множ-ва V(A). Матрицей смежности M порядка n назыв-ся матрица, сост-я из чисел mij, равных сумме чисел ориентиров-х ребер, идущих из аi в
