1631124435-59a81a8a1084f5170bbbb6e23ee88408 (848542), страница 3

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

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

В результате выполнения s шагов алгоритма Форда для любой вершины v: 1) ≤ ;2) = , если ранг события v не превосходит s.Доказательство. Докажем утверждение 1 индукцией по рангу события. Для входа 1 = 0, так как этавершина не является концевой ни для одной дуги. Предположим неравенство справедливо для событий рангов 1, …, R. Рассмотрим событие v, ранг которого = R + 1. Пусть k(j) = v и j − последняя′работа, при рассмотрении которой изменилась величина (т. е. произошло присваивание = ()+′1). Тогда, по предположению индукции, = ()+ 1 ≤ () + 1 ≤ () + 1 ≤ . Докажемутверждение 2 индукцией по номеру шага алгоритма. На шаге 0 для единственной вершины ранга 0имеем 1 = 1 = 0.

Пусть в результате s − 1 шагов величины = для всех событий l, рангикоторых не превосходят s − 1, найдены. Рассмотрим событие v ранга s и работу j такую, что k(j) = v,() = s − 1. По индукционному предположению, и утверждению 1 величина () не меняется на шагеs и равна () . Следовательно, ≥ () + 1 = () + 1 = s.♦16.2. Для каких задач применим метод ветвей и границ?Задача коммивояжера.16.3. Выписать математическую постановку следующей задачи.

У студента осталось T часов доэкзамена и Q невыученных вопросов. Для подготовки вопроса i требуется часов. Ценностьвыученного вопроса i равна . Требуется определить, какие вопросы учить, чтобы максимизироватьсуммарную ценность выученных вопросов?1, если учим билетВведем переменные = {0, иначе.Целевая функция: max Ограничения: ∑=1 ≤T, ∊ {0,1}17.1. Правильная нумерация событий и правильное упорядочивание работ в сетевых моделях.Особенности вычисления характеристик сети в этом случае (с доказательством).17.2.

Дать определение матричной игры? Привести примеры.Стратегия игрока – это набор правил для определения варианта действий, используемых привыборе каждого личного хода. Результат ходов игроков оценивается платежными функциямиучастников игры, которые можно интерпретировать как их выигрыши. Если сумма выигрышей всехигроков равна нулю, то такую игру называют игрой с нулевой суммой. Стратегия игрока называетсяоптимальной, если при многократном повторении игры его средний выигрыш максимален. Вдальнейшем будем считать, что игроки ведут себя разумно (без риска и азарта). В рамках данногопособия рассмотрим матричные игры. Матричная игра – это парная игра, в которой заданы: {1, …, m}– множество стратегий первого игрока, {1, …, n} – множество стратегий второго игрока, и для любойпары стратегий i ∈ {1, …, m} и j ∈ {1, …, n} определен выигрыш первого игрока, равный aij.

Матрицу A= (aij, i = 1, …, m, j = 1, …, n) называют платежной.17.3. В каких случаях целесообразно переходить от прямой задачи о ранце к обратной?1) если в прямой (обратной) задаче параметры ( ) не целочисленные, а ( ) целочисленные;2) если в прямой (обратной) задаче число A (B) большое и ( ) достаточно большие параметры,чтобы быстро выполнилось неравенство A < Q(β + 1) (S(α − 1) < B). В первом случае переход кобратной (прямой) задаче необходим для конечности реализации алгоритма. Во втором − переход кобратной (прямой) задаче может уменьшить трудоемкость.18.1. Теорема об активных стратегиях (с доказательством).

Игра 2x2. Схема решения игры 2xn, mx2.Чистая стратегия i является активной, если она используется в некоторой оптимальной стратегии сположительной вероятностью. Другими словами, если существует оптимальная стратегия p (q)такая,что > 0 ( > 0), то чистая стратегия i (j) является активной для первого (второго) игрока.Теорема (Об активных стратегиях). Если один игрок придерживается оптимальной стратегии, тоего соперник достигает цены игры ν, применяя любую свою смешанную стратегию, в которойиспользуются только активные стратегии.Доказательство.

Пусть первый игрок использует оптимальную стратегию p*, а второй −смешаннуюстратегиюq,вкоторой∈ J′, где J′ − подмножество активных стратегий второго игрока. Необходимо показать, что ценаигры ν = E(p*, q).18.2. НЕТ!!!!! Является ли необходимым (достаточным) условие целочисленности пропускныхспособностей ребер для реализации алгоритма Форда-Фалкерсона для нахождения потокамаксимальной мощности?18.3 . НЕТ!!!!!!!! Записать математическую постановку следующей задачи.

Имеется множествоскладов(I), для каждого из которых задано количество хранящегося продукта( ). Известномножество потребителей(J) продукции, для каждого из которых задана потребность( ). Известнызатраты на транспортировку единицы продукции из любого склада к любому потребителю( −из склада потребителю). Требуется определить объемы поставки из каждого склада потребителямт.о., что суммарные транспортные затраты минимальны.19.1. Решения матричной игры в чистых стратегиях (с доказательством соотв.

теоремы). Примеры.Смешанная стратегия – это вероятностное распределение на множестве чистых стратегий.Смешанные стратегии игроков определяются векторами:19.2. Можно ли с помощью алгоритма Форда найти самый длинный простой путь между парой вершинв неориентированном взвешенном графе?Нет, т.к. если в графе есть цикл положительного веса, то алгоритм никогда не остановится и можетсделать путь между вершинами сколь угодно длинным.19.3.

. Записать математическую постановку следующей задачи. Имеется множество складов(I), длякаждого из которых задано количество хранящегося продукта( ). Известно множествопотребителей(J) продукции, для каждого из которых задана потребность( ). Известны затраты натранспортировку единицы продукции из любого склада к любому потребителю( −из склада потребителю). Требуется определить объемы поставки из каждого склада потребителямт.о., что максимальные транспортные затраты, связанные с поставкой продукции из некоторогосклада некоторому потребителю, минимальны.1, если из склада повезли потребителю Введем переменные = {0, иначе.Целевая функция: ∑ → Ограничения: ≥ 0, ≥ 0, ∑ ≤ , ∑ = .20.1.

Потоки минимальной стоимости. Алгоритмы. Доказательство корректности алгоритма Клейна.Пусть дополнительно каждой дуге приписан неотрицательный «вес» cij, равный стоимоститранспортировки единицы потока по дуге (i, j) ∈ A. Задача поиска s−t потока заданной мощности vминимальной стоимости имеет видАлгоритм Клейна Шаг 1. Найти произвольный допустимый s−t поток величины v. (Это можносделать подбором, или алгоритмом Форда−Фалкерсона, в котором следует увеличивать поток, покаон не станет равным v.)Шаг 2. Определить модифицированные дуговые стоимости:Шаг 3. Найти в сети цикл отрицательной стоимости (назовем его отрицательным), где стоимостьцикла равна сумме модифицированных стоимостей входящих в него дуг.

Если отрицательного цикланет, то найденный поток оптимален. В противном случае увеличить поток по отрицательному циклуна величину δ = min{bij – xij, xji}, где минимум берется по всем прямым (i, j) и обратным (j, i) дугамцикла, и перейти на шаг 2.(Если в сети существует несколько отрицательных циклов, то увеличить поток по каждому из них.)Теорема 8.4. Поток величины v оптимален (имеет минимальную стоимость) тогда и только тогда,когда в сети с модифицированными дуговыми стоимостями c *ij не существует отрицательных циклов.Доказательство. Необходимость следует из того, что в случае существования отрицательного цикламожно добавить циркуляцию по этому циклу, сохранив величину потока и уменьшив его стоимость,что противоречит оптимальности потока.Докажем достаточность. Рассмотрим некоторый поток, для которого в сети не существуетотрицательных циклов.

Предположим, что оптимальный поток имеет меньшую стоимость.Разложим оптимальный поток на v путей, обозначим их oi, i = 1, …, v, по каждому из которыхпропущен единичный поток. Аналогично разложим рассматриваемый поток на v путей pi, i = 1, …, v,по каждому из которых пропущен единичный поток.Ввиду того, что оптимальный поток имеет меньшую стоимость, существуют пути oi и pi такие, чтостоимость потока по oi меньше стоимости потока по pi. Тогда эти пути:a) либо не имеют общих дуг,b) либо частично совпадают.Если имеет место случай a, то рассмотрим цикл из s в t по пути oi, затем из t в s по пути pi.

Этоотрицательный цикл (для модифицированных стоимостей). Получили противоречие. В случае bобозначим через f первую вершину, после которой пути oi и pi начинают различаться, а через l –первую вершину, после которой они полностью совпадают. Стоимость потока по участкупути oi от f в l меньше стоимости по участку пути pi от f в l.

Значит, найден отрицательный цикл: из fв l по пути oi, а из l в f по пути pi.Это противоречие доказывает теорему.♦20.2. В каких случаях целесообразно переходить от прямой задачи о ранце к обратной?1) если в прямой (обратной) задаче параметры ( ) не целочисленные, а ( ) целочисленные;2) если в прямой (обратной) задаче число A (B) большое и ( ) достаточно большие параметры,чтобы быстро выполнилось неравенство A < Q(β + 1) (S(α − 1) < B). В первом случае переход кобратной (прямой) задаче необходим для конечности реализации алгоритма. Во втором − переход кобратной (прямой) задаче может уменьшить трудоемкость.20.3.

НЕТ!!!!!!! Пусть задачи P, QNP, Q полиномиально разрешима, и P полиномиальносводится к Q. Что можно сказать о P?P полиномиально разрешима21.1. Общая задача о ранце и схема динамического программирования для ее решения.Рассмотрим задачу о ранце с целевой функцией, представляющей собой сумму сепарабельныхmax ∑=1 ( );функций: S* = S(A) = {∊+∑=1 ≤ .Где функция зависит только от переменной (свойство сепара − бельности).Рассмотрим семейство задач с количеством предметов k = 1, …, n и емкостью ранца α = 0, …, A.Обозначим через (α) оптимальное значение функционала соответствующей задачи. Справедливыследующие рекуррентные соотношения:S1 ( ) S k ( ) maxx1  0 ,..., / a1 maxf1 ( x1 ), 0    A;Sk 1 (  ak xk )  f k ( xk ),xk  0,..., / ak k  2,..., n, 0    A.При целочисленных параметрах достаточно перебрать конечное множество значений параметраα = 0, …, A, что приводит к алгоритму псевдополиномиальной трудоемкости.21.2. Если частный случай проблемы является NP-полной задачей, то является ли NP-полнойисходная проблема?Да.

По определению. (Класс NP-полных проблем (обозначим его NPC) – это подмножество задачPNP, обладающих свойством, что любая задача из класса NP полиномиально сводится к P)21.3. НЕТ!!!!!!!!!!!!!!!! Имеется граф, отражающий связи университета со всеми общежитиями.Известна длина каждого ребра этого графа. Можно ли с полиномиальной трудоемкостью найтипути минимальной длины от всех общежитий в университет?22.1. Динамическое программирование. Принцип оптимальности. Схема решения задачипроизводства и хранения продукции.В основе метода ДП лежит идея рассмотрения, наряду с заданной индивидуальнойоптимизационной задачей, целого семейства индивидуальных подзадач. Прииспользовании метода ДП происходит поэтапное (пошаговое) принятие решений.Традиционная реализация метода состоит из прямого и обратного ходов.

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

Список файлов вопросов/заданий