ответы мат методы (1). По предмету математические методы

• Название: По предмету математические методы
• Дата: 07.02.2023
• Размер: 426 Kb.
• Имя файла: ответы мат методы (1).doc
• Тип: Решение; #923726
• страница: 1 из 5

По предмету «МАТЕМАТИЧЕСКИЕ МЕТОДЫ»

1. 
   Основные понятия: решение, множество возможных решений, оптимальное решение, показатель эффективности.
   
2. 
   Математические модели, основные принципы построения моделей, аналитические и статические модели.
   
3. 
   Классификация задач, возникающих в практической деятельности и подходы к их решению: прямые и обратные задачи.
   
4. 
   Классификация задач, возникающих в практической деятельности и подходы к их решению: детерминированные задачи и задачи в условиях неопределенности.
   
5. 
   Классификация задач, возникающих в практической деятельности и подходы к их решению: однокритериальные и многокритериальные задачи.
   
6. 
   Методы решения многокритериальных задач (выделение множества Парето, линейная свертка, наложение ограничений на показатели эффективности, метод последовательных уступок).
   
7. 
   Общий вид задач линейного программирования (ЛП).
   
8. 
   Основная задача линейного программирования (ОЗЛП) и сведение произвольной задачи линейного программирования к основной задаче линейного программирования.
   
9. 
   Симплекс–метод при решении ОЗЛП.
   
10. 
    Транспортная задача.
    
11. 
    Методы нахождения начального решения транспортной задачи (дописать).
    
12. 
    Метод потенциалов в решении транспортной задачи.
    
13. 
    Общий вид задач нелинейного программирования. Графический метод решения задач нелинейного программирования.
    
14. 
    Метод множителей Лагранжа для решения задач нелинейного программирования.
    
15. 
    Основные понятия динамического программирования: шаговое управление, управление операцией в целом, оптимальное управление, выигрыш на данном шаге, выигрыш за всю операцию, аддитивный критерий, мультипликативный критерий.
    
16. 
    Идея метода динамического программирования. Простейшие задачи, решаемые методом динамического программирования.
    
17. 
    Определение графа и его основные характеристики. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный подграф.
    
18. 
    Определение графа. Матрицы смежностей и инциденций. Методы хранения графов в памяти ЭВМ.
    
19. 
    Путь в графе и связные компоненты графа. Цепи, простые цепи, циклы, простые циклы. Операции удаления вершины, удаления ребра. Дерево и его особенности.
    
20. 
    Определение паросочетаний в графе и их разновидностей. Двудольные графы и алгоритм выбора наибольшего паросочетания в двудольном графе.
    
21. 
    Планарные и плоские графы. Формулировки теоремы Эйлера о соотношении чисел граней, ребер и вершин плоского графа.
    
22. 
    Методы хранения графов в памяти ЭВМ. Взвешенный граф. Кратчайшие пути во взвешенном графе и алгоритм Форда построения кратчайших маршрутов.
    
23. 
    Сети и потоки в сетях. Задача о максимальном потоке и алгоритм Форда–Фалкерсона.
    
24. 
    Ориентированный граф и его графическая интерпретация. Локальные степени. Матрица смежностей. Ориентированные пути и связность в ориентированном графе.
    
25. 
    Задача о коммивояжере.
    
26. 
    Понятие системы массового обслуживания, классификация систем массового обслуживания. Простейшие системы массового обслуживания и их параметры.
    
27. 
    Основные понятия теории марковских процессов: случайный процесс, марковский процесс, граф состояний, поток событий, вероятность состояния, уравнения Колмогорова, финальные вероятности состояний.
    
28. 
    Предмет и задачи теории игр. Основные понятия теории игр: игра, игроки, партия, выигрыш, проигрыш, ход, личные и случайные ходы, стратегические игры, стратегия, оптимальная стратегия.
    
    29. 
        Антагонистические матричные игры: чистые и смешанные стратегии. Методы решения конечных игр: сведение игры mxn к задаче линейного программирования.
        
    30. 
        Назначение и области применения сетевого планирования и управления. Сетевая модель и её основные элементы. Порядок и правила построения сетевых графиков.
        

1. Основные понятия: решение, множество возможных решений, оптимальное решение, показатель эффективности.

Исследов-е операций – прим-е мат., кол-венных методов д/обоснования решений во всех обл-тях целенаправленной человеч.деят-ти. Операция – любое управляемое мероприятие, направленное на достиж-е цели. Рез-т операции зависит от способа ее проведения, орг-ции (от выбора некоторых пар-ров). Всякий опр.выбор пар-ров наз-ся решением. Те пар-ры, совок-ть ктр образует решение, наз-ся эл-тами решения. Оптимальными считаются те решения, ктр по тем или иным соображ-ям предпочтительнее др. Поэтому осн.задачей исследов-я операций явл-ся предварительное кол-венное обоснование опт.решений. #Д/реализации опр.партий сезон.товаров создается сеть временных торговых точек. Т.е. требуется выбрать пар-ры сети: число точек, их размещ-е, кол-во персонала так, чтобы обеспечить мах экономич.эф-ть распродажи. Чтобы сравнивать между собой по эф-ти разные решения, нужно иметь какой-то кол-венный критерий – показ-ль эф-ти (целевая f-я). Этот показ-ль выбир-ся так, чтобы он отражал целевую направлен-ть операции. «Лучшим» будет считаться то решение, ктр в мах степени способствует достижению поставлен.цели. Иногда выполнение операции сопровожд-ся действием случ.факторов («капризы» погоды, колебания спроса и предлож-я). В таких случаях обычно в кач-ве показ-ля эф-ти берется не сама величина, ктр хотелось бы мах-ровать (min-ровать), а ее среднее знач-е (мат.ожидание). В некотор.случаях бывает, что операция, сопровождаемая случ.факторами, преследует какую-то опр.цель, ктр может быть только достигнута полностью или совсем не достигнута, и никакие промежуточ.рез-ты нас не интересуют. Тогда в кач-ве показ-ля эф-ти выбир-ся вер-ть достиж-я этой цели.
2. Математ-е модели, осн-е принципы постр-я моделей, аналит-е и статич-е модели.

Д/прим-я кол-венных методов исследования в любой обл-ти всегда требуется какая-то мат.модель. При построении модели реал.явление неизбежно упрощ-ся и описыв-ся с помощью того или другого мат.аппарата. Чем удачнее будет подобрана мат.модель, чем лучше она будет отражать хар-ные черты явления, тем успешнее будет исследов-е и полезнее вытекающие из него рекомендации. Общих способов построения мат.моделей не сущ-ет. В кажд.конкрет.случае модель выбир-ся, исходя из вида операции, ее целевой направлен-ти. Необх-мо также в кажд.конкрет.случае соразмерять точность и подроб-ть модели: а)с той точностью, с ктр нам нужно знать решение; б)с той i-цией, ктр мы располагаем или можем приобрести. В исследовании операций прим-ся как аналитические, так и статистические модели, каждая из ктр имеет свои недостатки и преимущ-ва. Аналитич.модели более грубы, учитывают меньшее число факторов, всегда требуют каких-то допущений и упрощений. Зато рез-ты расчета по ним легче обозримы, отчетливее отражают присущие явлению закономер-ти. Аналит.модели больше приспособлены д/поиска опт.решений. Статистич.модели более точны и подробны, не требуют столь грубых допущений, позволяют учесть большое число факторов. Недостатки: громоздкоть, плохая обозримость, большой расход машин.времени, крайняя трудность поиска опт.решений, ктр приходится искать путем догадок и проб.
3. Классиф-я задач, возник-х в практ-й деятел-ти и подходы к их решению: прямые и обрат-е з-и.

Задачи исследования операций делятся на 2категории: прямые и обратные. Прямые задачи отвечают на вопрос: что будет, если в заданных условиях мы примем какое-то решение хХ? В частности, чему будет =, при данном решении х, выбранных показ-ль эф-ти W? Д/решения такой задачи строится мат.модель, позволяющая выразить 1 или неск-ко показ-лей эф-ти через заданные условия и эл-ты решения. Обратные задачи отвечают на вопрос: как выбрать решение х д/того, чтобы показ-ль эф-ти W обратился в мах? Если число возможных вариантов реш-я, образ-х множ-во Х, невелико, то можно попросту вычислить величину W д/каждого из них, сравнить между собой полученные знач-я и непоср-венно указать 1 или неск-ко опт.вариантов, д/ктр W достигает мах. Такой способ нахожд-я опт.решения наз-ся «простым перебором». Однако, когда число возможных вариантов решения, образующих множ-во Х, велико, поиск среди них оптимального «вслепую», прост.перебором, затруднителен, а зачастую практически невозможен. В этих случаях прим-ся методы «направленного перебора», обладающие той общей особен-тью, что опт.решение нах-ся рядом последовательных «попыток» или «приближений», из ктр каждое последующее приближает нас к искомому оптимальному.

5. Классиф-я задач, возникающих в практической деят-ти и подходы к их решению: однокритер-е и многокритер-е задачи.

Однокритериальный подход- когда ясен критерий, по которому производится оценка эффективности, и требуется обратить в максимум(минимум) один-единственный показатель W #собираешься на отдых не знаешь какая погода будет точно(нужно решить какую одежду взять- один критерий). Рассм-м пример такой задачи. Орган-ся обо­рона важного объекта от возд-х налетов. В нашем распоряж-и - какие-то средства противовозд-й обороны, кот-е надо разумным образом разместить вокруг объекта, организовать их взаимодействие, распределить между ними цели, назначить боезапас н т. д. главная задача операции - не до­пустить к объекту ни одного самолета, а естеств-й показатель эффект-ти - вероятность Wтого, что ни один самолет не прорвется к объекту. М - среднее число пораженных целей, кот-й нам тоже хотелось бы максимизировать; П - еще один крит-й, кот-й хотелось бы минимиз-ть. Несмотря на ряд существенных трудностей, свя­занных с неопределен-ю, мы до сих пор рассмат­р-ли только самые простые случаи, когда ясен кри­т-й, по кот-му произв-ся оценка эффективно­сти, и требуется обратить в максимум (минимум) один-единственный показ-ль W. К сожалению, на практике такие задачи, где критерий оценки одно­значно диктуется целевой направленностью операции, встречаются не так уж часто - преимущественно при рассм-и небольших по масштабу и скромных по значению меропр-и. А когда идет речь о круп­номасштабных, сложных операциях, затрагивающих разнообразные интересы их организаторов и общества в целом, то их эффект-ть, как правило, не может быть полностью охарактеризована с помощью одного единственного показ-ля эффект-ти W. На по­мощь ему приходится привлекать другие, дополни­т-е. Такие задачи исследования операций наз-тся многокритериальными. Итак, типичной для крупномасшт-й задачи ис­следования опер-й является многокритер-е - наличие ряда количеств-х показат-й, один из кот-х желательно обратить в максимум, другие – в минимум.

7. Общий вид задач лин-го программир-я (ЛП).

Они явл-ся наиболее простыми среди задач исследования операций, где выбор показ-лей эф-ти (целевой f-ции) W достаточно явно диктуется целевой направлен-тью задачи, а ее усл-я – известны заранее (детерминирован.случай). W=W (,x), где  - факторы, налагаемые на эл-ты решения х некоторые огранич-я. Wmax (min). Трудности, возникающие при решении задач мат.программир-я, зависят: ф)от вида f-ной завис-ти, связывающей W с эл-тами решения; б)от «размер-ти» задачи, т.е.от кол-ва эл-тов решения х₁, х₂, …, х_n; в)от вида и кол-ва огранич-й, наложенных на эл-ты решения. Д/задач ЛП хар-но: 1)показ-ль эф-ти (цел.f-я) W линейно зависит от эл-тов решения х₁, х₂, …, х_n; 2)огранич-я, налагаемые на эл-ты решения, имеют вид лин.нерав-в или ур-й относ-но х₁, х₂, …, х_n. К задачам ЛП относ-ся задачи распред-я ресурсов, планирования произв-ва, орг-ции работы транспорта.

4. Классиф-я задач, возник-х в практ-й деятельности и подходы к их решению: детерминир-е задачи и задачи в условиях неопредел-ти.

Обратные задачи отвечают на вопрос: как выбрать решение х д/того, чтобы показ-ль эф-ти W обратился в мах? Если число возможных вариантов решения, образующих множ-во Х, невелико, то можно попросту вычислить величину W д/каждого из них, сравнить между собой получ-е знач-я и непоср-венно указать 1 или неск-ко опт.вариантов, д/ктр W достигает мах. Такой способ нахожд-я опт.решения наз-ся «простым перебором». Сейчас мы ограничимся постановкой задачи опти­мизации решения (обратной задачи исследования опе­раций) в самой общей форме. Пусть имеется некот-я операция Q, , па успех ко­т-й мы можем в какой-то мере влиять, выбирая тем или другим способом реш-е х (напомним, что х — не число, а целая группа параметров). Пусть эффек­тив-ть операции характер-ся одним показат-м W max. Возьмем самый простой, так назыв-й «детерми­нированный» случай, когда все условия операции пол­ностью известны заранее, т. е. не содержат неопреде­л-ти. Тогда все факторы, от которых зависит ус­пех опер-и, делятся на две группы: 1) заданные, заранее известные факторы (условия выпол-я опер-и), кот-е мы д/краткости обозначим одной буквой а; 2) зависящие от нас элем-ты реш-я, образую­щие в своей совок-ти реш-е х. Заметим, что первая группа факт-в содержит, в частности, и огранич-я, налаг-е на реш-е, т. е. определяет область возм-х решений X. Показ-ль эффект-ти Wзависит от обеих групп факторов W=W(,x), как х, так и а в общем случае — не числа, а сово­купности чисел (векторы), функции в т. д. В числе за­данных условий ее обычно присутствуют огран-я, налагаемые на эл-ты реш-я, имеющие вид ра­венств или неравенств. При заданном комплексе условий а. найти такое ре­шение х = х*, которое обращает показатель эффект-сти W в максимум. Эта задача принадлежит к классу так называемых «вариационных задач», хорошо разработ-х в мате­матике. Самые простые аз таких задач («задачи на максимум и минимум») знакомы каждому инженеру. Чтобы найти максимум или минимум (короче, «экстре­мум») ф-я многих аргументов, надо продифферен­цировать ее по всем аргументам (в данной случае — элементам решения), приравнять производные нулю и решить полученную сис-му уравн-й. Метод поиска экстремума и связанного с ним опти­м-го решения х* должен всегда выбираться исхо­дя из особен-й функции Wи вида ограни-й, накладыв-х на реш-е. #, если фун-я Wлинейно зависит от элем-в реш-я X₁, Х₂, ..., а огран-я, налагаемые на X₁, Х_2,.. имеют вид линейных равенств или неравенств, возникает ставшая классич-й задача лин-го программи­р-я, кот-я решается сравн-но простыми, а главное, станд-ми методами. Д/оптимизации управл-я многоэтапными опер-ми примен-ся метод динамического програм-я . Наконец, сущ-ет целый набор чис­л-х методов отыскания экстремумов, специально приспособленных для реализации на ЭВМ; некот-е из них включают элемент «случайного поиска», кото­рый д/многомерных задач нередко оказывается эф­фективнее упорядоченного перебора. Т. О., задача нахождения оптимал-го реш-я в простейшем, детерминированном случае есть чисто математ-я задача, принадл-я к классу вариационных (при отсутствии или наличия ограничений), кот-я может представить вычислит-е, но не принцип-е трудности. В предыдущем мы рассмотрели обратную задачу исследования опер-й в детерминированном случае, когда показатель эффективности Wзависит только от двух групп факторов: заданных, заранее из­вестных а и элементов решения х. Реальные задачи исслед-я опер-й чаще всего содержат помимо этих двух групп еще одну — неизвес-е факторы, кот-е в совок-ти мы обозначим одной буквой . Итак, показатель эффект-ти Wзависит от всех трех групп факторов: W=W(, х, ). Так как величина Wзависит от неизв-х фак­торов, то даже при заданных а и х она уже не мо­жет быть выч-на, остается неопред-й. Задача поиска оптимал-го реш-я тоже теряет определ-ть. # 1: планируется ассортимент товаров на распродажи на ярмарке. Желат-но было бы максимиз-ть прибыль. Однако заранее неизвестно ни кол-во покуп-й, кот-е придут на ярмарку, ни потр-ти каждого покуп-ля. # 2: Проект-ся сис-ма сооруж-й, оберегающих район от паводков. Ни моменты их наступления, ни размеры заранее не известны. # 3: разрабатывается план вооружения страны на несколько лет вперед, но неизвестны ни конкретный противник, ни вооружения, кот-м он будет располагаться. Д/того, чтобы такие решения принимать современная наука располагает рядом приемов. Каким из них воспольз-ся — зависит от того, какова приро­да неизвестных факторов , откуда они возникают и кем контрол-ся. Классифицировать неопредел-ти по «родам» и «сортам». «Доброкачественный» вид неопредел-ти - это случай, когда неизв-е факторы  предст-т собой обычные объекты изу­чения теории вероятн-й — случайные велич-ны (или случайные фун-и), статистические харак­тер-ки кот-х нам известны или в принципе могут быть получены к нужному сроку. Такие задачи иссле­д-я операций мы будем называть стохастиче­скими задачами, а присущую им неопредел-ть — стохастической неопределен-ю. Возьмем самый гру­бый пример: пусть мы ведем обстрел какой-то цели, стремясь во что бы то ни стало попасть в нее. Произ­в-ся несколько выстрелов. Давайте заменим все случайные координаты точек попадания их математи­ческим ожиданием — центром цели. Получится, что любой выстрел с гарантией попадет в цель, что заве­домо неверно. Гораздо хуже обстоит дело, когда неизвестные факторы  не могут быть изучены и описаны статистич-ми методами. Это бывает в 2 случаях: либо распред-е вероятн-й д/параме-в  в принципе сущ-ет, но к моменту принятия решения не может быть получена. Либо распределение вероятн-й вообще не сущ-т. Пример ситуации типа а): проектируется информ-но вычислит-я система (ИВС), предназначен­ная д/обслужив-я каких-то случайных потоков требов-й (запросов). Вероятн-е характеристики этих потоков требов-й в принципе могли бы быть получены из статистики, если бы данная ИВС (или аналогичная ей) уже существ-ла и функционир-ла достаточно долгое время. Но к моменту создания проекта такой инф-и нет.