- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
48. Распределение одного вида ресурса
Пусть необходимо распределить ресурс в количестве X между N предприятиями, если известно, что при выделении i-му предприятию ресурса xi оно дает прибыль ri(xi). При этом к функциям ri не предъявляется каких-либо требований (например, дифференцируемости).
Запишем модель задачи:
. (9.7)
Очевидно, что условия применимости ДП выполняются: и критерий, и ограничение задачи (9.7) являются составными (в данном случае - аддитивными). Представим задачу как многошаговую. В качестве шага будем рассматривать выделение ресурса одному предприятию. Расположим предприятия в виде последовательности, в которой каждому предприятию приписано определенное место, и пронумеруем их справа налево. Порядок предприятий в последовательности шагов принципиального значения не имеет, но могут оказаться полезными следующие советы:
Если условие-ограничение имеет вид равенства, то на 1-е место целесообразно ставить предприятие с наиболее сложной функцией прибыли, а при неравенстве - наоборот, с самой простой, так как в этом случае несколько снизится трудоемкость расчетов.
Если нет уверенности, что некоторое предприятие останется в рассматриваемой системе распределения, его следует поставить последним (на самое левое место); тогда в случае его удаления не придется решать задачу заново.
Теперь необходимо определиться с состоянием. Для этого зададимся вопросом: что нужно знать, чтобы принять решение по распределению ресурса между заданным числом предприятий? Ответ очевиден - количество распределяемого ресурса. Тот же ответ последует и на вопрос: от чего зависит максимальная прибыль системы предприятий в нашей задаче? Следовательно, состояние определяется одним параметром - количеством распределяемого ресурса, которое обозначим через V. Оно может относиться к разному числу предприятий, поэтому V£X. В соответствии с процедурой ДП введем последовательность функций {fk(Vk)} так, что
(9.8)
есть максимальная прибыль k предприятий при распределении между ними ресурса в количестве Vk.
Если бы пришлось искать функции (9.8) непосредственно, то потребовалось бы решать семейство задач вида
(9.9)
для 0£V£X, что многократно увеличивает трудоемкость решения. В динамическом программировании число задач будет таким же, однако их размерность не зависит от номера задачи и будет в N раз меньше размерности исходной задачи.
Перейдем к составлению рекуррентного соотношения. Допустим, что осталось распределить ресурс Vk между k предприятиями. Выделим из них две части: k-е предприятие и все остальные k-1 (рис.9.8).
Примем решение по k-му предприятию: из всего имеющегося ресурса Vk выделим ему Xk. Тогда оно даст прибыль rk(xk), а система перейдет в состояние Vk-1, относительно которого следует искать решения на k-1 оставшихся шагах. Согласно принципу оптимальности эти решения должны составлять оптимальное поведение независимо от того, как система попала в состояние Vk-1. Такое поведение обеспечит максимальную прибыль от k-1 предприятий, то есть fk-1(Vk-1). В результате, прибыль k предприятий составит
rk(xk) + fk-1(Vk-1). (9.10)
Как следует из модели задачи (9.9), уравнение состояния имеет простой вид
Vk-1= Vk-xk , (9.11)
что означает уменьшение распределяемого ресурса после выделения xk ресурса k-му предприятию. Подставив (9.11) в (9.10), получим зависимость только от одной переменной xk:
rk(xk) + fk(Vk - xk),
максимизация которой по xk в допустимой области обеспечивает максимальную прибыль от всех k предприятий при распределении ресурса в количестве Vk. Но по определению (9.8) это есть fk(Vk). Таким образом, приходим к искомому рекуррентному соотношению
. (9.12)
Здесь видно, как допустимая область Dk, задаваемая диапазоном xk, явно зависит от состояния Vk. Формула (9.12) применима для k³2. Для первой функции последовательности в соответствии с ограничением модели (9.7) и определением (9.8) имеем
f1(V1)= r1(V1), x1*=V1,
так как весь имеющийся ресурс распределяется полностью. Поэтому 1-й шаг условной оптимизации состоит в прямом вычислении значений заданной функции r1, а в ряде случаев и этого не требуется.
Остановимся на вычислительной стороне формулы (9.12). В отдельных случаях при простых функциях rk(Vk) максимум в (9.12) может быть найден аналитически, однако в общем случае максимум находится одним из численных методов, в том числе полным перебором допустимых значений xk. Тогда, если xk и Vk - непрерывные величины, для вычислений по рекуррентному соотношению их необходимо дискретизировать. Шаг дискретности D выбирается по точности, с которой следует провести распределение ресурса. При этом, исходя из уравнения состояния, в данной задаче шаг дискретности должен быть одинаковым для xk и Vk. С учетом этого рекуррентная формула (9.12) примет вид
(9.13)
где = 1,2,…,m; mD = X, D = Vk, mD = xk. Один из способов вычислений по формуле (9.13) состоит в том, что сначала фиксируется , а затем ищется максимум правой части, и так для всех значений . Результаты заносятся в таблицу вида
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
где xk*( D) - значение xk, доставляющее максимум в (9.13) при Vk= D. Все N таблиц, получаемых при последовательном расчете функций fk, имеют одинаковую структуру. Решение исходной задачи (9.7) находится на этапе безусловной оптимизации следующим образом. По значению VN=X входим в таблицу N, из которой берем fN(X) - максимальную прибыль от N предприятий при распределении между ними ресурса в количестве X и xN*=xN*(X) - количество ресурса, выделяемое N-му предприятию при оптимальном распределении ресурса X. По уравнению состояния (9.11) находим VN-1=X-xN*, входим по этому значению состояния в таблицу N-1 и из нее извлекаем fN-1(X-xN*) и xN-1* - максимальную прибыль от N-1 предприятий и количество ресурса, выделяемое (N-1)-му предприятию при оптимальном распределении, соответственно. Снова пересчитываем состояние
VN-2=VN-1-xN-1*=X-xN*-xN-1* и по нему входим в таблицу N-2, в которой найдем xN-2*, и так вплоть до таблицы 1, из которой получим x1*. В результате имеем оптимальное решение задачи распределения ресурса в количестве X.
На примере этой задачи отметим ряд достоинств метода ДП.
1. Задача содержит N переменных, которые после дискретизации могут принимать m значений. Поэтому порядок числа вариантов распределения определяется величиной mN (точное значение можно получить, если убрать варианты, не удовлетворяющие условию в (9.7)). При расчете по рекуррентной формуле максимум ищется для m значений состояния, а поиск максимума путем просмотра всего диапазона переменной требует перебора от двух до m+1 вариантов, то есть в среднем ~m/2. Значит, один шаг включает расчет m2/2 вариантов, а вся задача в ДП - Nm2/2. Очевидно, что Nm2/2<<mN. Кроме того, вариант в полном переборе требует выполнения большего числа операций (вычисления N функций r(V) и N-1 сложений). Так, например, при m=N=10 полный перебор требует расчета ~1010 вариантов, что даже при затратах машинного времени порядка 10-5 секунды на вариант потребует непрерывной работы ЭВМ в течение 277 часов. Для решения этой же задачи методом ДП достаточно рассчитать не более 500 вариантов (!).
2. В случае изменения количества распределяемого ресурса метод полного перебора и другие регулярные численные методы требуют решать задачу заново. В динамическом программировании, если новое значение не больше X, достаточно провести безусловную оптимизацию, взяв за исходное состояние новое значение ресурса. А, как показано выше, безусловная оптимизация требует минимума элементарных действий. Это же возможно и при увеличении ресурса, если с самого начала решения задачи методом ДП увеличить значение X до максимально ожидаемого уровня либо дополнить часть последних таблиц недостающими строками.
3. При использовании любого метода оптимизации, кроме ДП, исключение одного из предприятий из системы распределения приведет к необходимости решать изменившуюся задачу как новую. В динамическом программировании, если этому предприятию был присвоен номер N, то есть оно было последним по ходу условной оптимизации, решение измененной задачи находится сразу: по заданному количеству распределяемого ресурса входим не в N-ю, а в (N-1)-ю таблицу и далее действуем в соответствии со схемой безусловной оптимизации, которая была рассмотрена выше.
Свойства, приведенные в п.п.2,3, обусловлены тем, что несмотря на резкое сокращение числа рассчитываемых вариантов, метод ДП находит не один оптимум для заданных X и N, а оптимумы для всех возможных состояний в данной задаче для принятого порядка нумерации предприятий и соответствующие им оптимальные решения. Иначе говоря, метод ДП дает весь ансамбль оптимальных решений, свойственных задаче. Отсюда также следует, что получаемые результаты позволяют определить чувствительность критерия к изменениям X.
4. Метод ДП не накладывает каких-либо специальных требований на вид и форму представления функций, составляющих критерий. Так, в рассмотренной задаче функции r(V) могут быть недифференцируемыми, могут быть заданы даже в виде таблицы или графика, или задаваться алгоритмически.
5. Отыскание глобального экстремума многомерной функции является очень сложной проблемой. Динамическое программирование снижает размерность решаемых задач в N раз (по числу переменных), что значительно облегчает нахождение глобального экстремума. Так в рассмотренной задаче на каждом шаге находится максимум функции одной переменной. Из свойства рекуррентного соотношения следует, что отыскание глобального оптимума на каждом шаге гарантирует достижение глобального оптимума исходной задачи.
6. Наложение специфических условий на переменные не «утяжеляет» решение задачи методом ДП (в отличие от многих других). Например, ограничения сверху и снизу или/и дискретность (в частности, целочисленность) переменных не затрудняют, а, наоборот, облегчают решение на каждом шаге.
7. Трудоемкость вычислений и объем памяти для хранения результатов на одном шаге не зависят от числа шагов. Поэтому увеличение числа шагов приводит только к пропорциональному возрастанию времени решения задачи, тогда как для других методов с увеличением размерности задачи трудоемкость ее решения растет гораздо быстрее.
Для лучшего усвоения материала решение следующих двух задач поясняется на численных примерах.