- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
Дан сетевой график, в котором каждой дуге поставлена в соответствие ее длина Lij (рис. 9.10). Порядок нумерации вершин не имеет значения, но в приведенной нумерации задача состоит в определении кратчайшего пути из вершины 1 в вершину 7. Подобные задачи возникают непосредственно при сетевом планировании и управлении, при определении стратегии аренды оборудования, прокладке маршрутов и в других случаях.
Рис.9.10
Модель задачи включает критерий - длину искомого пути
, (9.22)
где - путь от вершины 1 к вершине 7, и граф сети (или описывающую его матрицу). Применение метода ДП правомерно, так как задача представима как многошаговая: искомый путь есть допустимая графом последовательность дуг, а выбор дуги рассматриваем как один шаг задачи. В отличие от предыдущих задач здесь нет параметра состояния, состояние полностью определяется номером вершины, а число шагов от конкретной вершины до 7-й неоднозначно. Учитывая эти особенности, вводим последовательность функций {fi}, i=1,7 так, что каждая функция есть минимальная длина пути от i-й вершины в 7-ю:
, (9.23)
где - множество всех допустимых путей из i-й вершины в 7-ю.
Для составления функционального уравнения возьмем произвольную вершину i (i¹7) и будем определять путь из нее в вершину 7. Из этого пути выделим один шаг - выбор вершины, следующей за i-й. Множество дуг, выходящих из вершины i, обозначим . Взяв произвольную дугу из множества , окажемся в смежной вершине j, длина пути до которой равна Lij. В соответствии с принципом оптимальности последующее поведение должно быть оптимальным, то есть путь от j-й вершины к 7-й должен иметь минимальную длину, которая согласно (9.23) есть fj. В результате, длина пути от i-й вершины до 7-й будет равна Lij + fj. Так как она зависит только от j, то выбором j можно ее минимизировать. Но минимальная длина пути от i-й вершины к вершине 7 есть по определению функция fi. Таким образом, приходим к рекуррентному соотношению задачи:
. (9.24)
Принципиальное отличие полученного соотношения состоит в том, что в нем нет однозначной последовательности шагов, которая выражалась в предыдущих задачах равенством j=i-1 (или j=i+1), и, следовательно, число шагов из фиксируемой вершины заранее определить нельзя (действительно, путь между двумя несмежными вершинами может состоять из разного числа дуг).
Рассуждения, которые привели к соотношению (9.24), подсказывают, что начинать условную оптимизацию следует с определения f7. Так как f7 - минимальная длина пути из вершины 7 в саму себя, то f7=0. Как показывает формула (9.24), вычислять можно те функции fi, для которых уже известны все fj, ijÎ . Поэтому следующей можно находить только функцию f6:
f6 = min (L67 + f7)=1+0=1.
Далее производим вычисления в порядке, диктуемом графом сети:
В приведенных формулах подчеркнуты индексы, на которых достигается минимум. Из расчета видно, что длина кратчайшего пути из вершины 1 в вершину 7 равна 11. Сам оптимальный путь найдем, как обычно, просматривая результаты условной оптимизации в обратном порядке: из f1 следует, что первая часть пути лежит на дуге 1-2, значит, новое состояние - это вершина 2; из f2 находим следующую часть пути - дугу 2-5 и очередное состояние - вершину 5; поэтому далее обращаемся к f5 и достраиваем оптимальный путь дугой 5-6 и, наконец, заканчиваем дугой 6-7. Таким образом, построен весь путь: 1®2®5®6®7. При этом на этапе безусловной оптимизации просматривались не все функции fi, что отличает данную задачу от ранее рассмотренных.
Очевидно, имея результаты условной оптимизации, можно легко найти кратчайшие пути из любой вершины сети в вершину 7, что характерно для метода ДП.
Для самостоятельного изучения предлагается такой вопрос: возможно ли применение метода ДП в случае, когда сеть содержит цикл, например, при добавлении дуги 6-2? Если нельзя, то почему, а если можно, то как построить расчет.