- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
53. Снижение размерности с помощью множителей Лагранжа
Покажем на примере задачи 1, каким образом введение множителей Лагранжа позволяет заменить исходную задачу рядом задач с меньшей размерностью вектора состояния.
В задаче 1 состояние описывалось двумя параметрами, что обусловливалось наличием двух ограничений. Для уменьшения размерности на 1 достаточно из модели (9.40)-(9.43) убрать одно из ограничений, что можно сделать, если удаляемое ограничение включить в критерий задачи с неопределенным множителем Лагранжа l. Тогда модель измененной задачи примет вид:
(9.52)
(9.53)
(9.54)
Как будет доказано ниже, задача (9.52)-(9.54) при определенных условиях эквивалентна исходной задаче (9.40)-(9.43). Так как ограничения (9.53), (9.54) не связывают между собой переменные yj, то есть они стали независимыми, то справедлива следующая цепочка равенств:
где
. (9.55)
Функции hj(xj) имеют смысл, если максимум в (9.55) достигается при конечных значениях yj, что всегда будет, когда
. (9.56)
Это условие ограничивает применение данного способа, но в рассматриваемой задаче оно, очевидно, выполняется, так как при неограниченном возрастании ресурса y рост прибыли будет замедляться.
Как видно из (9.55), вычисление функции hj(xj) при фиксированном значении заключается в нахождении максимума функции одной переменной для всех возможных значений xj, что не вызывает особых затруднений (для дифференцируемых Rj(xj,yj) максимум можно найти аналитически). При известных hj(xj), j=1,N задача (9.52)-(9.54) сводится к следующей:
(9.57)
(9.58)
(9.59)
Получили уже знакомую нам задачу распределения одного ресурса. Для решения ее методом ДП введем последовательность функций
,
где V - параметр состояния, значения которого не превосходят X. Для них справедливо рекуррентное соотношение:
fk(V) = max[hk (xk)+ fk-1(V-xk)], (9.60)
в котором f1(V)= h1(V), =V.
Вычисления по формуле (9.60) проводятся, как обычно, от f1 к fN, затем в обратном порядке - безусловная оптимизация, начиная с V=X, которая дает значения . По последним из функций hj(xj) находятся значения . Теперь следует вспомнить об условии (9.42), которое не вошло в измененную задачу. Если =Y, то найденное решение , является оптимальным решением задачи (9.40)-(9.43). В противном случае придется продолжить расчеты.
Нетрудно увидеть, что оптимальное решение измененной задачи зависит от принятого значения множителя . Поэтому при невыполнении условия (9.42) нужно изменить значение и повторить весь расчет, начиная с вычисления функций hj(xj). В данной задаче при изменении можно воспользоваться очевидным свойством: с увеличением будет монотонно убывать и наоборот. В более сложных ситуациях можно воспользоваться одним из методов одномерного поиска нелинейного программирования. Таким образом, равенство (9.42) может быть выполнено с любой заданной точностью.
Чтобы нагляднее представить весь расчет с использованием множителей Лагранжа, приведем его алгоритм в виде блок-схемы (рис.9.11). Как видно из алгоритма, функции fk(V) и hj(xj), участвующие в расчете, зависят от одного параметра состояния, и, следовательно, поставленная цель достигнута.
Рис.9.11
Теперь покажем эквивалентность задач (9.40)-(9.43) и (9.52)-(9.54), понимая под этим совпадение решений. Следуя Беллману, доказательство проведем от противного. Имея оптимальное решение измененной задачи , , предположим, что оптимальное решение исходной задачи иное, а именно, , . Тогда для критерия исходной задачи должно выполняться неравенство
. (9.61)
Так как å =Y по условию исходной задачи, а å =Y по алгоритму решения измененной задачи, то å =å . Вычитание одной и той же величины, умноженной на , из левой и правой частей выражения (9.61) не меняет знак неравенства:
. (9.62)
Но здесь и слева, и справа имеем выражение критерия измененной задачи, по которому оптимальным является решение , . Таким образом, неравенство (9.62), вытекающее из допущения существования разных решений, противоречит исходной посылке и потому такое допущение неверно, что доказывает совпадение решений исходной и измененной (эквивалентной) задач.
Для задачи 2 применение метода множителей Лагранжа реализуется проще. Модель измененной задачи можно записать по аналогии с вышеприведенным случаем в виде:
Для функций последовательности, определенных как
справедливо следующее рекуррентное соотношение
(9.63)
Как видно, здесь нет дополнительных функций hj и вычисления можно проводить сразу по рекуррентной формуле (9.63), задавшись предварительно значением . После нахождения решения проверяется условие (9.48) - å )£B и, если оно не выполняется, то необходимо изменить значение и повторить расчет. Таким способом достигается эквивалентность исходной и измененной задач и получение оптимального решения с помощью последовательности функций, зависящих только от одного параметра состояния.
В общем случае, когда вектор состояния исходной задачи имеет размерность m, можно использовать q множителей Лагранжа (q<m), что позволит снизить размерность вектора состояния измененной задачи до m-q. При этом выполнение исключенных из условий исходной задачи q ограничений может быть обеспечено управлением таким же числом множителей Лагранжа. Однако увеличение размерности вектора состояния и соответственно числа множителей Лагранжа ведет к значительно более быстрому росту трудоемкости решения измененной задачи. Поэтому проблема "проклятия размерности" остается, ограничивая применение метода ДП задачами с небольшим числом параметров состояния.
Несмотря на указанный недостаток метод динамического программирования находит широкое применение для решения многих задач исследования операций, в том числе задач распределения, замены, кратчайшего пути, упорядочения и др.