Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Способ 2. 3 страница




при

Задача о назначении (проблема выбора, о женихах и невестах).

Имеется n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнением i-м исполнителем j-той работы (i,j= ). Нужно так назначить исполнителей на работы, чтобы добиться максимальной полезности при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплён только один исполнитель.

Для составления математической модели задачи обозначим через – факт назначения или не назначения i-того исполнителя на j-ю работу. Так как количество исполнителей равно количеству работ и каждый из них может быть назначен только на одну работу, то должны принимать только два значения 1 или 0. Такие переменные называются булевыми.

Так как нужно найти план назначения , который максимизирует суммарную полезность назначения

при

а) каждый исполнитель назначается только на одну работу:

б) на каждую работу назначается только один исполнитель:

, - ограничение неотрицательности и целочисленности.

Мы рассмотрели только два примера, можно еще рассмотреть задачу коммивояжера, транспортную задачу с фиксированными доплатами.

 

3.9. Сущность методов дискретной оптимизации

 

В первом приближении методы целочисленной оптимизации можно разделить на две группы: точные и приближённые. К точным относятся методы отсечения и комбинаторные (метод ветвей и границ). Однако точные методы имеют слабую сходимость. Многие экспериментальные и прикладные задачи не удалось решить за десятки и тысячи итераций. Общая идея решения задачи дискретного программирования методами отсечения состоит в следующем: исходная задача решается сначала без учёта ограничения целочисленности. Если полученный оптимальный план удовлетворяет условиям целочисленности, то задача решена, в противном случае к ограничениям исходной задачи добавляются новые, обладающие следующими свойствами:

· Полученный нецелочисленный план нарушает это ограничение.

· Любой целочисленный допустимый план исходной задачи заведомо удовлетворяет и новому ограничению.

Затем задача решается с учётом нового ограничения. В случае необходимости добавляется ещё одно ограничение и т.д. Геометрически добавления каждого нового ограничения отвечает проведение поверхности, которая отсекает от области допустимых решений некоторую его часть с оптимальной точкой и нецелыми координатами, но не затрагивает ни одной из целочисленных точек этого многогранника.

Для решения задачи дискретного программирования получили широкое распространение комбинаторные методы направленного частичного перебора допустимых планов. Из них наиболее универсален метод ветвей и границ. Для выявления сущности этого момента воспользуемся известной задачей об отыскании фальшивой монеты. Пусть в мешке с монетами одинакового достоинства имеется одна фальшивая, отличающаяся бόльшим весом, которую будем искать по средствам взвешивания на рычажных весах без гирь. Поступим так: Разделим содержимое мешка на 2 равные по количеству монет части. В случае, если число n монет – нечётное – разделим n-1 монет на 2 равные части. Положим на чашки весов равные по количеству монет части. Если чашки весов уравновесятся, то отложенная монета – фальшивая, в противном случае она находится в более тяжёлой части, с которой поступим аналогичным образом. Так до тех пор, пока не найдём фальшивую монету. Здесь деление мешка есть деление множества на подмножества, т.е. разбиение области допустимых решений на непересекающиеся подмножества. Взвешивание каждой части соответствует оценке целевой функции на подмножестве (оценке верхней или нижней границы). Если при этом удастся найти некоторый план, для которого верхняя (нижняя) оценка на множестве плана одного из подмножеств равна значению функции в этой точке и не меньше (не превосходит) оценок сверху (снизу) на всех подмножествах, то этот план оптимальный. Если такой план не обнаружен, то продолжается процесс разбиения, начиная его с подмножества, имеющего самую высокую (низкую) оценку и т.д. Поскольку множество всех планов задачи конечно, то в конце концов план будет оптимальный.

 

3.10. Задача выпуклого программирования

 

Определение 1: Функция f(x), определенная на выпуклом множестве Х, называется выпуклой, если для любых точек и из этого множества и любого справедливо неравенство:

.

Если в этом соотношении при и любых и Х () имеет место строгое неравенство, то f(x) называется строго выпуклой.

Определение 2: Функция f(x), определенная на выпуклом множестве Х, называется вогнутой, если для любых точек и из этого множества и любого справедливо неравенство:

.

Если в этом соотношении при и любых и Х () имеет место строгое неравенство, то f(x) называется строго вогнутой.

Определение 3: Задача математического программирования

при ограничениях

(),

().

в которой либо целевая функция, либо ограничения, либо то и другое нелинейны, называется нелинейной.

Класс задач нелинейного математического программирования очень велик. Общих универсальных методов нет. Однако, есть задачи нелинейного программирования, для которых есть методы решения. Один из таких типов задач являются задачи выпуклого программирования.

В теории выпуклого программирования в качестве основной обычно рассматривается задача минимизации выпуклой функции n переменных при ограничениях (), (), где функции предполагаются выпуклыми.

Если и являются вогнутыми, то имеем задачу максимизации при ограничениях (), ().

 

3.11. Метод множителей Лагранжа

 

Метод множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого).

Рассмотрим классическую задачу оптимизации

при ограничениях

().

От основной задачи выпуклого программирования в данной постановке задача отличается тем, что в системе ограничений нет неравенств и нет ограничения неотрицательности для переменных.

Классический подход к решению данной задачи дает систему уравнений (необходимые условия), которым должна удовлетворять точка , доставляющая функции локальный экстремум на множестве точек, удовлетворяющих системе ограничений (для задачи выпуклого программирования найденная точка будет и глобальным экстремум).

Предположим, что в точке функция имеет локальный условный экстремум и ранг матрицы

равен m. Тогда необходимые условия запишутся в виде:

(),

(),

где

есть функция Лагранжа, – множители Лагранжа.

Алгоритм решения задачи методом множителей Лагранжа:

1. Составить функцию Лагранжа.

2. Найти частные производные функции Лагранжа по всем переменным и приравнять их к нулю. Получим систему из n+m уравнений с n+m неизвестными. Решив полученную систему, вычислим стационарные токи функции Лагранжа.

3. Из стационарных точек, взятых без , выбрать точки, в которых функция имеет условный локальный экстремумы при наличии ограничений.

Пример: Решить задачу математического программирования, используя метод множителей Лагранжа.

при

,

Решение:

Будем решать задачу без учета неотрицательности переменных.

1. Составим функцию Лагранжа.

2. Найдем ее частные производные по .

Приравняв производные к нулю, получим систему:

Решим ее:

Получена стационарная точка (91, 89). С помощью вторых производных легко доказать, что в полученной точке функция достигает условный локальный экстремум. Данная точка является точкой минимума функции.

Ответ: Z=17278.

 

3.12. Градиентные методы

 

Градиентным методом можно решать любую нелинейную задачу. При этом находится локальный экстремум. Целесообразнее же этот метод используют при решении задач выпуклого программирования.

Будем рассматривать задачу максимизации нелинейной дифференцируемой функции . Суть градиентного поиска точки максимума:

Возьмем произвольную точку из области допустимых значений. C помощью градиента функции в точке ( Определим направление, в котором возрастает с наибольшей скоростью. Затем сделав небольшой шаг в найденном направлении, перейдем в новую точку . Далее снова определяем наилучшее направление для перехода в очередную точку и т.д.

Поисковая траектория представляет собой ломаную . Таким образом, надо построить последовательность так, чтобы она сходилась к точке максимума. Для точек последовательности выполняются условия

Градиентные методы, как правило, позволяют найти точные решения за бесконечное число шагов и лишь в некоторых случаях за конечное. В связи с этим градиентные методы относят к приближенным методам решения.

 

Блок 4

4.1. Методы штрафных и барьерных функций

 

Определение: Методы решения задач нелинейного (в частности выпуклого) программирования, при использовании которых данную задачу минимизации можно свести к задаче минимизации некоторой специальной функции, представляющую собой сумму данной минимизируемой функции и некоторой другой функции (называемой штрафной), сформированной из ограничений данной задачи, называют методами штрафных функций.

Общая идея методов штрафных и барьерных функций заключается в следующем: исследуется на экстремум не сама функция, а новая функция, построенная из исходной функции и штрафной. Значения полученной и исходной функции в области допустимых значений совпадают, а при приближении к границе, а тем более при выходе за ее пределы резко возрастают за счет добавленной функции. В зависимости от способа формирования штрафных функций различают метод штрафных и метод барьерных функций..

Рассмотрим метод штрафных функций.

Пусть требуется минимизировать функцию при ограничениях (). Предполагаем, что условия неотрицательности включены в систему ограничений задачи. Тогда обобщенная функция будет иметь вид:

,

где Н – штрафная функция, удовлетворяющая следующим условиям: для всех точек области допустимых значений Н=0 и Н>0 для всех остальных точек. Штрафную функцию можно построить различными способами. Для выпуклого программирования наиболее часто она имеет вид:

,

где

– некоторые постоянные числа, представляющие собой весовые коэффициенты.

Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое решение. При этом координаты последующей точки находят по формуле:

Из последнего соотношения следует, что если предыдущая точка находится в области допустимых решений исходной задачи, то второе слагаемое в квадратных скобках равно 0 и переход к последующей точке определяется только градиентом целевой функции. Если же указанная точка не принадлежит области допустимых решений, то за счет данного слагаемого на последующих итерациях достигается возвращение в область допустимых решений. При этом чем меньше , тем быстрее находится приемлемое решение, однако точность определения его снижается. Поэтому итерационный процесс обычно начинают при сравнительно малых значениях и, продолжая его, эти значения постепенно увеличивают.

Рассмотрим теперь метод барьерных функций. Если ограничения исходной задачи имеют вид строгих неравенств, то для формирования обобщенной функции используются так называемые барьерные функции, значения которых неограниченно возрастают при приближении к границе допустимой области. Обобщенная функция имеет такой же вид как для метода штрафных функций и за границы области допустимых значений она не выходит. В качестве барьерной чаще всего берут логарифмическую функцию.

 

4.2. Динамическое программирование. Основные понятия. Сущность методов решения

 

Динамическое программирование – это метод нахождение оптимальных решений в задачах с многошаговой структурой. Многие экономические процессы разделяются на шаги естественным образом: это все процессы планирования и управления, развивающиеся во времени. Естественным шагом в них могут быть год, неделя, декада и т.д. Однако метод динамического программирования может использоваться при решении задач, где время вообще не фигурирует. Разделение на шаги в таких задачах вводится искусственно.

Особенности задач динамического программирования:

1.Рассматривается система, состояние которой на каждом шаге определяется вектором .Дальнейшие изменения ее состояния зависят только от данного состояния и не зависят от того, каким путем система пришла в него. Такие процессы называют процессами без последствий.

2.На каждом шаге выбирается одно решение , под действием которого система переходит из предыдущего состояния в новое . Это новое состояние является функцией состояния на начало интервала и принятого вначале интервала решения ,т.е.

.

3.Действие на каждом шаге связано с определенным выигрышем (доходом прибыли) или потерей (издержками), которые зависят от состояния на начало шага и принятого решения.

4.На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений.

5.Требуется найти такое допустимое управление для каждого шага t, чтобы получить экстремальное значение функции цели за все T шагов.

Определение: Любую допустимую последовательность действий для каждого шага, приводящую систему из начального состояния в конечное, называют стратегией управления.

Определение: Допустимая стратегия управления, доставляющая функции цели экстремальное значение, называется оптимальной.

Определение: Управление – это воздействие, переводящее систему из начального состояния в конечное.

Любую многошаговую задачу можно решать по-разному. Во-первых, можно считать неизвестными величинами и находить экстремум целевой функции одним из существующих методов оптимизации, т.е. искать сразу все элементы решения на всех шагах сразу. Этот путь не всегда приводит к результату, особенно если целевая функция задана таблично или число переменных велико. Второй путь основан на проведении поэтапной оптимизации. Поэтапность отнюдь не означает изолированность этап, наоборот, управление на каждом последующем этапе осуществляется с учетом результатов предыдущего. Чаще всего этот метод проще, чем решение всей задачи сразу. Идея постепенной пошаговой оптимизации составляет суть метода динамического программирования. Из качественного анализа идеи поэтапной оптимизации можно сформулировать следующие принципы, лежащие в основе динамического программирования: принцип оптимальности и принцип погружения.

Принцип оптимальности. Оптимальное управление на каждом шаге определяется состоянием системы на начало этого шага и целью управления. Или, в развернутом виде: оптимальная стратегия обладает таким свойством, что, каковы бы ни были начальное состояние и начальные решения, последующие решения должны приниматься исходя из оптимальной стратегии с учетом состояния, вытекающего из первого решения.

Принцип погружения. Природа задач, допускающей использование метода динамического программирования, не меняется при изменении количества шагов N. В этом смысле каждый конкретный процесс с заданным числом шагов оказывается как бы погруженным в семейство подобных ему процессов и может рассматриваться с позиции более широкого круга задач.

Реализация названных принципов дает гарантию того, что решение, принимаемое на очередном шаге, окажется наилучшим относительно всего процесса в целом, а не в узких интересах данного этапа.

 

4.3. Стохастическое программирование. Основные понятия

 

Определение: Оптимизационные задачи и их модели, в которых вся исходная информация задана строго однозначно, называются детерминированными.

В действительности детерминированные модели часто оказываются неадекватными реальным процессам экономики. Это объясняется неполнотой, неточностью данных, на основе которых формируется модель. В одних случаях некоторые параметры носят вероятностный характер. Тогда говорят о ситуациях, связанных с риском. В других случаях имеющаяся информация не позволяет составить представление о характере изменения параметров, описываемых случайный процесс. Такие ситуации называются неопределенными.

Определение: Оптимизационные задачи, при постановке которых нет исчерпывающих данных об их условиях, называются стохастическими.

Поскольку стохастические задачи приходится решать при недостаточной информации, это ведет к снижению экономической эффективности получаемых решений. Для исследования описываемых ситуаций разрабатываются специальные методы, объединенные в разделе математического программирования, называемом стохастическим программированием.

Стохастическое программирование изучает теорию и методы решения условных экстремальных задач при неполной информации об их условиях.

Различают пассивное и активное стохастическое программирование.

Определение: Пассивное стохастическое программирование – совокупность приемов, позволяющих находить наилучшее решение и экстремальное значение целевых функций в оптимизационных задачах со случайными исходными данными. При этом используются идеи параметрического программирования.

Определение: Активное стохастическое программирование – это совокупность приемов, позволяющих развивать методы выбора решений в условиях риска и неопределенности.

В стохастическом программировании исследуются одно-, двух-, многоэтапные задачи.

Определение: Одноэтапными называют задачи, в которых последовательность поступления исходной информации не имеет значения при выборе решения задачи. Оно принимается один раз и в дальнейшем не изменяется. Такие задачи могут порождаться детерминированными оптимизационными задачами, когда используемые данные теряют определенность и принимают случайный характер.

В одноэтапных задачах по-разному выбирается целевая функция и характер ограничений. В качестве целевых функций могут рассматриваться вероятность попадания решения в некоторую, случайную область или математическое ожидание некоторой функции от решения.

На практике чаще всего встречаются двухэтапные стохастические задачи. Подобные задачи возникают при планировании выпуска продукции в случае, когда отсутствуют данные о спросе, о ней. В такой ситуации сначала принимается предварительное решение об объеме выпуска на основе имеющейся информации (1 этап), затем после установления спроса принимается корректирующее решение (2 этап). При этом предварительное решение не должно исключать коррекции на втором этапе. Кроме того, предварительный и корректирующие планы согласовываются так, чтобы обеспечивались минимальные средние затраты за оба этапа.

Для ряда конкретных постановок двухэтапных стохастических задач Разработаны достаточно надежные методы решения.

В многоэтапных (динамических) задачах по мере получения информации о развивающемся процессе имеется возможность неоднократно корректировать решение, учитывая исходные ограничения и априорные статистические характеристики случайных параметров, описывающие процесс на каждом этапе. Многоэтапные задачи могут быть как с жесткими, так и с вероятностными ограничениями.

 

4.4. Матричные игры с нулевой суммой

 

Теория игр занимается разработкой различного рода рекомендаций по принятию решений в условиях конфликтной ситуации. Формализуя конфликтные ситуации, их можно представить как игру двух, трех и более игроков, каждый из которых преследует цель максимизации прибыли за счет других игроков.




Поделиться с друзьями:


Дата добавления: 2014-11-18; Просмотров: 760; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.