- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
52. Многомерные задачи динамического программирования
В рассмотренных выше задачах вектор состояния S имел размерность 1 или 0 (нулевая в задаче о кратчайшем пути). Если размерность вектора S (число параметров состояния) больше 1, то говорят, что задача многомерна в смысле динамического программирования. Многомерные задачи порождают определенные проблемы при реализации вычислительной схемы метода ДП. Покажем на примерах, как возникают такие задачи и с чем приходится сталкиваться при их решении.
Задача 1. Необходимо распределить два вида ресурсов в объеме X и Y соответственно между N производствами при известных функциях прибыли Rj(xj,yj), j=1,N. Здесь xj, yj - количество ресурса 1-го и 2-го вида, потребляемое j-м производством.
Запишем модель задачи:
(9.40)
(9.41)
(9.42)
(9.43)
Очевидно, что задача представима как N-шаговая (по числу производств). Для принятия решения по распределению ресурсов нужно знать их количество и число производств, участвующих в распределении. При выделении ресурсов одному из производств изменяется объем ресурсов, направляемых на остальные производства. Поэтому состояние характеризуется двумя параметрами: количеством ресурса 1-го вида V и 2-го вида U (V£X, U£Y). Введем последовательность функций:
(9.44)
и рассмотрим k оставшихся производств (шагов), между которыми нужно распределить ресурсы в количестве V и U. Приняв решение о выделении k-му производству произвольного допустимого количества ресурсов xk и yk, будем иметь прибыль от этого производства Rk(xk,yk), а на остальные k-1 шагов останется ресурсов V-xk 1-го вида и U-yk 2-го вида. Следуя принципу оптимальности, распределим оставшиеся ресурсы оптимальным образом, что обеспечит максимальную прибыль от k-1 производств, то есть fk-1(V-xk ,U-yk ). Прибыль же от всех k шагов составит
Rk(xk, yk)+ fk-1(V-xk, U-yk).
Так как она зависит от двух переменных, то варьируя их в допустимой области, можно получить максимальную прибыль, которая по определению (9.44) есть fk(V,U). Таким образом, приходим к функциональному уравнению динамического программирования:
(9.45)
Задача 2. Распределению подлежит один вид ресурса, но в системе имеются ограничения, связанные с его использованием. Это могут быть ограничения на общий объем, вес, габариты, стоимость и др. Рассмотрим случай двух ограничений, согласно которым фактические значения учитываемых показателей использования ресурса не могут превышать величин A и B. Тогда модель задачи можно представить в виде:
(9.46)
(9.47)
(9.48)
(9.49)
где xi - количество ресурса, выделяемое i-му потребителю;
Zi(xi) - показатель эффективности i-го потребителя;
ji(xi), yi(xi) - функции ограничиваемых показателей.
Для применения метода ДП необходимо, как всегда, определить параметры состояния. Нетрудно видеть, что информация, достаточная для принятия решения на текущем шаге, должна содержать значения ограничивающих показателей. Они же непосредственно влияют на оптимальное значение эффективности системы. Кроме того, изменение ресурса на i-м шаге влечет изменение этих показателей к следующему шагу. Следовательно, в процедуре ДП ограничивающие показатели a и b выступают в качестве параметров состояния (a£A, b£B).
Определим функции последовательности как
. (9.50)
Не повторяя известных рассуждений, опирающихся на принцип оптимальности ДП, приведем в окончательном виде рекуррентное соотношение для рассматриваемой задачи:
(9.51)
Проанализируем полученные выражения (9.45) и (9.51). При их выводе не возникло принципиальных затруднений. Хотя число распределяемых ресурсов разное, в обеих задачах функции последовательности зависят от двух параметров состояния. Нетрудно понять теперь, что размерность вектора состояния связана с числом ограничений, включающих переменные всех шагов. Трудоемкость решения сравниваемых уравнений разная, так как различно число переменных, по которым ищется экстремум. При нелинейных функциях jk и yk может усложниться перебор допустимых xk в (9.51). Однако эти различия не столь существенны, большее значение имеет одинаковая размерность вектора состояния.
Покажем на задаче 1, к чему приводит увеличение числа параметров состояния. Решение уравнения (9.45) проводится для всех возможных состояний. Число таких состояний зависит от шага дискретности и числа параметров состояния. Пусть mx и my - число возможных значений ресурсов X и Y соответственно, тогда число возможных состояний будет равно mxmy. Для каждого из них в результирующей таблице решения уравнения (9.45) на k-м шаге должны быть представлены V, U, , и fk(V,U). Для вещественного числа требуется хотя бы 6 байт памяти, поэтому одна строка результирующей таблицы будет занимать не менее 30 байт. При mx = my =100 число возможных состояний, а значит, и число строк составит 104. Следовательно, для запоминания одной таблицы потребуется около 300 Кбайт. Для эффективного расчета нужно иметь в оперативной памяти две таблицы - k-ю и (k-1)-ю. Вынос этих таблиц во внешнюю память сделает метод ДП практически малопригодным, так как затраты времени на решение задачи многократно увеличатся. Теперь нетрудно оценить, насколько будут возрастать требования к памяти с увеличением числа параметров состояния до 3, 4 и более.
Таким образом, решение многомерных задач наталкивается на проблему реализации вычислений по рекуррентным соотношениям. Сама идея метода ДП настолько привлекательна, что обнаружив трудно преодолимое препятствие применению метода в виде отмеченной проблемы, Беллман назвал ее "проклятием размерности".
Естественно, появилась необходимость найти пути решения возникшей проблемы. К предложенным средствам можно отнести использование множителей Лагранжа, аппроксимацию в области стратегий, принципиально иной способ решения рекуррентного уравнения, применение идей последовательного анализа вариантов и др. Однако ни одно из них не является универсальным, а в ряде случаев не работают все. Ниже рассматривается один из способов преодоления проблемы размерности, нашедший практическое применение.