Лабораторная работа №1 Основы работы в системе Mathcad арифметические вычисления 2 Символьные вычисления 4
Лабораторная работа 2. Задачи линейного программирование
жүктеу/скачать 5,09 Mb.
|
- Бұл бет үшін навигация:
- Лабораторная работа 3. Задачи динамического программирования
Лабораторная работа 2. Задачи линейного программированиеЦель работы: решение задач линейного программирования об оптимальном распределении ресурсаЗадание Определить оптимальную производственную программу для n=5+с видов изделий из m=3+b видов ресурсов с матрицей затрат , вектором ресурсов и вектором прибыли . В качестве примера рассмотрим задачу об оптимальном распределении ресурса. Пусть имеется n инвестиционных проектов и сумма средств для инвестиций . Прибыль от каждого проекта задана функцией - вложения в каждый проект. Должна быть максимизирована суммарная прибыль от всех проектов ( 7) при условии . ( 8) Разобьем решение задачи на n шагов. На первом шаге выделим деньги первому предприятию, на втором второму и так далее. Обозначим через остаток ресурса после k-го распределения, так что . (9) Теперь геометрическая интерпретация задачи состоит в нахождении ломаной наибольшей длины, соединяющей точку на начальной прямой и точку на конечной прямой. Введем функцию , (10 ) которая представляет собой прибыль от n-k последних проектов. Оптимальное значение этой функции , соответствующее максимальной прибыли, называется функцией Беллмана, так что х0 оптимальные вложения. Для последнего шага имеем: . (11) Величина - остаток ресурса после предпоследнего распределения нам неизвестна, поэтому прибыль зависит от этой величины. Для двух последних проектов, на шаге k-1 имеем (12) Для произвольного шага k аналогичным образом получим следующее уравнение Беллмана: , ( 13) которое вместе с начальным условием (11) позволяет рекуррентно определить все функции Беллмана. Для функции величина известна, что позволяет определить максимальную прибыль и наилучшие вложения в первый проект . Далее, двигаясь в обратном направлении, определим оптимальные вложения во все проекты. Преимущество применения метода динамического программирования для аддитивных функций (1) определяется тем, что вместо задачи минимизации функции многих переменных, что требует числа вычислений пропорционально кубу размерности задачи, решается n задач минимизации более простой функции одной переменной. Число вычислений в такой задаче растет линейно с ростом n. Недостаток состоит в том, что для решения задачи необходимо помнить все n функций Беллмана. Рассмотрим простой численный пример задачи распределения. Имеется сумма средств для инвестиций в три проекта порциями по 40 ед. Потенциальная прибыль от вложений в каждый проект дана в следующем виде (табл.2.1.): Табл. 2.1. Прибыль от вложений в каждый проект
Расчеты сведем в основную табл. 2.2, представленную ниже, и вспомогательную табл.2.3. Табл 2.2. Основная таблица для расчетов по методу ДП
Последние два столбца получены из (11 ) максимизацией функции . Расчеты функции Беллмана для следующих шагов сведены во вспомогательную табл.2.3. Табл. 2.3. Вспомогательная таблица для расчетов по методу ДП
В табл 2.3 максимальные значения прибыли от двух или трех проектов выделены жирным курсивом. В графе , k =1,2 найдем максимизирующие прибыль значения аргументов, и эти данные занесем в основную таблицу для соответствующего шага. Теперь можно определить оптимальные вложения. Наибольшая прибыль от вложения 100 единиц от трех проектов составляет 26 единиц при вложениях (в основной табл. 2.2. оптимальные вложения выделены жирным курсивом). Остаток средств после первого шага , наилучшая прибыль от двух последних проектов составляет, как это следует из основной таблицы, 21 единицу при вложениях . Остаток средств для последнего проекта . Из данного примера видно, что метод динамического программирования позволяет находить глобальный минимум и решает задачу оптимизации для всех рассматриваемых начальных значений состояния объекта в рассматриваемом интервале, то есть в терминах задач управления решается задача синтеза. В следующем документе MATHCAD (док. Д.5) приведена программа, в которой реализован пример решения задачи распределения ресурса. Контрольные вопросы: Что такое задача линейного программирования? Как определяется множество допустимых решений в задаче ЛП? Где достигается минимум в задаче ЛП? Какая из сформулированных задач не является задачей ЛП? Лабораторная работа 3. Задачи динамического программированияМетод ветвей и границЦель работы: решение задач динамического программирования. Задание Определить оптимальные вложения ресурса в 100 ед. частями xj по 10 ед. в п=с+3 проектов с функциями прибыли Пусть M0 – множество всех вариантов решения задачи перебора. Разобьем это множество на подмножества Мi так, чтобы эти подмножества охватывали все варианты, и чтобы каждый вариант входил только в одно подмножество, то есть чтобы выполнялись условия . Если продолжить такое разбиение для каждого из подмножеств, то в итоге построим дерево, корень которого содержит все варианты, а конечные ветви содержат единственный вариант. Если можно оценить снизу или сверху решения, содержащиеся в каждом подмножестве (определить функцию оценки или соответственно), то для сокращения перебора можно применить метод ветвей и границ. Метод содержит три этапа – ветвление, оценку и отбрасывание вариантов. Если удалось ввести функцию оценки, то после ветвления множества М0 оцениваем решения во множествах Мi, и дальнейшее ветвление производится для наиболее перспективного множества с максимальной или минимальной оценкой в надежде, что именно там содержится оптимальное решение. Так продолжаем до тех пор, пока в множестве не окажется единственное решение (рис.4). Рис. 4. Дерево вариантов комбинаторной задачи Процедура отбрасывания вариантов в задаче минимизации основана на следующих принципах. 1. По уже достигнутому значению функции, полученному на некотором расчетов . Пусть имеем вариант решения со значением функции . Тогда все множества, для которых оценка не могут содержать лучших значений функции и должны быть отброшены. 2. По предельному значению функции. В этом случае, если уже достигнута граница возможных значений функции, например, нулевая ошибка, то лучшего решения не может быть. Часто отбрасывают остальные решения, если полученное решение уже удовлетворяет ЛПР. 3. По сравнению оценок. Пусть для двух множеств получены оценки и . Если выполняется неравенство , то во множестве М1 нет лучших решений, чем во множестве М2. Рассмотрим применение метода ветвей и границ для задачи коммивояжера на конкретном примере. жүктеу/скачать 5,09 Mb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||