Вход

Вариант 3

Рекомендуемая категория для самостоятельной подготовки:
Курсовая работа*
Код 173390
Дата создания 2012
Страниц 79
Источников 5
Мы сможем обработать ваш заказ (!) 1 апреля в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 580руб.
КУПИТЬ

Содержание

Оглавление
Задача 1 Решения задач транспортного типа
Задание № 2. Методы решения задач линейного и целочисленного программирования
Задание № 3. Методы нелинейного программирования
Задание № 4. Динамическое программирование. Матричные игры
Литература

Фрагмент работы для ознакомления

Возможно одно из двух: Если существует такой план ,чтото этот план оптимальны.Рис. 5Если такой план не найден, то выбирается одно из множеств (как правило, имеющее наибольшую оценкуВсе имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются как ,после чего процесс повторяется.Схема дробления множества Dпредставлена на рис. 5 в виде графа. Существуют и более сложные системы индексации подмножеств, при которых не требуется их переобозначение на каждом шаге.Конкретные реализации метода ветвей и границ связаны с правилами разбиения на подмножества (правилами ветвления) и построения оценок значений целевых функций на данных подмножествах (границ).Область допустимых решений представляет собой многоугольник. Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:8x1+13x2≤104x1≤9Решив систему уравнений, получим: x1 = 9, x2 = 2.4615Откуда найдем максимальное значение целевой функции:F(X) = 5*9 + 4*2.4615 = 54.8462 Оптимальное значение переменной x2=2.46 оказалось нецелочисленным.Разбиваем задачу 1 на две подзадачи 11 и 12.В первой из них к условиям задачи 11 добавляется условие х2 ≥ 3, а к задаче 12 — условие х2 ≤ 2.Эта процедура называется ветвлением по переменной х2. Решим графически задачу 11 как задачу ЛП. 8x1+13x2≤104(1)x1≤9(2)x2≥3(3)x1≥0(4)x2≥0(5)Область допустимых решений представляет собой треугольник. Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:8x1+13x2≤104x2≥3Решив систему уравнений, получим: x1 = 8.125, x2 = 3Откуда найдем максимальное значение целевой функции:F(X) = 5*8.125 + 4*3 = 52.625 Решим графически задачу 12 как задачу ЛП. 8x1+13x2≤104(1)x1≤9(2)x2≤2(3)x1≥0(4)x2≥0(5)Область допустимых решений представляет собой многоугольник. Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:x1≤9x2≤2Решив систему уравнений, получим: x1 = 9, x2 = 2Откуда найдем максимальное значение целевой функции:F(X) = 5*9 + 4*2 = 53 Решение задачи 12 получилось целочисленным.Новое значение текущего рекорда будет равно F(X) = 53.Так как найденная точка является первым целочисленным решением, то ее и соответствующее ей значение ЦФ следует запомнить. Сама точка называется текущим целочисленным рекордом или просто рекордом, а оптимальное значение целочисленной задачи — текущим значением рекорда. Это значение является нижней границей оптимального значения исходной задачи Z*. F(X) = 53x1 = 9x2 = 2 Дерево решения задачиЗадание № 3.Методы нелинейного программирования Для предложенного варианта необходимо:1) Построить конусы возможных направлений в угловых точках допустимого множества задачи ЛП.2) Построить конусы, сопряженные к конусам возможных направлений в угловых точках допустимого множества задачи ЛП.3) Проверить условия оптимальности Куна – Таккера в угловых точках допустимого множества задачи ЛП. Показать, что эти условия выполняются только в оптимальной точке.4) Найти точку безусловного экстремума (минимума) для заданной в табл. целевой функции и начальной точки: методом наискорейшего спуска; методом Ньютона. Для каждого из методов проделать пять итерационных шагов и оценить точность полученного решения. Для метода наискорейшего спуска сделать с помощью одного из методов одномерной оптимизации ( метод Фибоначчи, метод золотого сечения, метод квадратичной аппроксимации). Проделать не менее пяти шагов одномерной минимизации. Результаты вычислений оформить в виде таблицы, в которой необходимо отразить номер итерационного шага, значение целевой функции на данном шаге, решение на данном шаге.5) Найти решение задачи выпуклого программирования одним из методов:методом возможных направлений; методом Нелдора – Мида. Проделать не менее пяти итерационных шагов. Оценить точность полученного решения. В качестве допустимых точек взять множество допустимых точек задачи ЛП (задание №2), в качестве целевой функции и начальной точки взять соответствующие варианту значения из таблицы 3.1.1. Результаты решения оформить в виде таблицы. Номер вариантаЦелевая функция, Нач. точка Безусловный минимум 9(0,1)(6,7)1) Построить конусы возможных направлений в угловых точках допустимого множества задачи ЛП.Целевая функцияНачальная точка: Безусловный минимум: 3) Проверить условия оптимальности Куна – Таккера в угловых точках допустимого множества задачи ЛП. Показать, что эти условия выполняются только в оптимальной точке.Условие Куна-Такера(6;7)- выполняется4)а Метод наискорейшего спускаНазвание метода можно было бы понимать буквально, если бы речь шла о минимизации целевой функции. Тем не менее, по традиции такое название используется и при решении задачи на максимум.Пусть f(x) = f(xl,xl,...xn) — дифференцируемая функция, заданная на Rn, а — некоторая текущая точка. Оговоримся, что каких-либо общих рекомендаций, касающихся выбора исходной точки (или, как еще говорят, начального приближения) x(0), не существует, однако по возможности она должна находиться близко от искомого оптимального плана х*. Как уже говорилось выше, если x(q) — нестационарная точка (т. е. ), то при движении в направлении функция f(x) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значения f(x) от шагового множителя > 0 , полагая (1)или, в координатной форме,(2)Чтобы добиться наибольшего из возможных значений f при движении по направлению , нужно выбрать такое значение , которое максимизирует функцию . Для вычисления , используется необходимое условие экстремума . Заметим, что если для любого >0, то функция f(x) не ограничена сверху (т. е. не имеет максимума). В противном случае, на основе (2) получаем(3)что, в свою очередь, дает(4)Если считать, что следующая точка соответствует оптимальному значению , то в ней должно выполняться условие , и следует находить из условия или(5)Условие (5) означает равенство нулю скалярного произведения градиентов функции f точках х(q+1)и х(q) . После того как точка х(q+1)найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение координат точек, рассматриваемых на последовательных итерациях. Одновременно с этим координаты вектора должны быть близки к нулю.5) Метод возможных направлений.Для основной задачи нелинейного программирования, т.е. множество V – решение системы неравенств:Пусть х(0)–некоторое произвольное начальное приближение и уже рассчитаны приближения х(1)…х(К) Укажем способ построения следующего приближения:1)  Определяются активные в точке х(К) ограничения. Через I(x(K)) обозначается множество номеров активных ограничений.2)  Рассчитываются градиент целевой функции и градиенты активных ограничений.3)   cоставляется следующая вспомогательная задача линейного программирования: Пусть эта вспомогательная задача имеет решения S(K) и σК.Это решение может быть найдено, например, симплекс-методом.4)   Проверяем, выполняется ли неравенство σк≤0. Если это неравенство выполняется, то, согласно 1-ой теореме (необходимое условие условного минимума) точка х(к) удовлетворяет необходимому условию условного минимума. Выдаем эту точку в качестве решения. Процесс останавливается.Если же σК>0, идем к шагу 5).5)   Из неравенства (3) и 1-ой леммы о возможных направлениях следует, что вектор S(K)является возможным направлением для множества V в точке 6)   Вводим в рассмотрение функцию одной переменной qК(α)= f(x(K)+αS(K) ирассматриваем следующую задачу одномерного поиска:7)   Полагаем х(К+1)=х(К)+αК(K). Один шаг заканчиваетсяЗадание № 4.Динамическое программирование. Матричные игрыДля предложенного варианта необходимо:1) По заданной в таблице 4.1.1 (см. стр. 40) платежной матрице определить, существует ли седловая точка игры. Определить верхнюю и нижнюю цены игры.2) Свести игру в матричной постановке к задаче линейного программирования. Показать, что прямая задача линейного программирования и двойственная задача линейного программирования соответствуют смешанным стратегиям соответственно для первого и второго игроков.3) С помощью симплекс – метода найти решение матричной игры в смешанных стратегиях, т.е. найти: смешанную стратегию первого игрока как решение прямой задачи линейного программирования;смешанную стратегию второго игрока как решение двойственной задачи линейного программирования;цену игры как значение целевой функции указанных задач линейного программирования.4) Методом динамического программирования для данных, приведенных в таблице 4.1.2 (см. стр. 41) решить дискретную задачу о выборе оптимальной траектории.5) Математическая постановка задачи динамического программирования.32 4 56 2 44 6 8 37 6 49 7 8 58 6 76 9 7 47 8 98 6 5 47 8 91)Удобным способом задания игры двух участников с нулевой суммой является платежная матрица. Отсюда, кстати, происходит еще одно их название — матричные игры. Каждый элемент платежной матрицы аijсодержит числовое значение выигрыша игрока I (проигрыша игрока II), если первый применяет стратегию i, а второй — стратегию j. Термины выигрыш и проигрыш следует понимать в широком смысле, т. к. они могут принимать отрицательные значения и с житейской точки зрения означать противоположное. Нетривиальность задачи, прежде всего, заключается в том, что каждый из игроков делает свой выбор, не зная о выборе другого, что существенно осложняет процесс оптимизации выбираемой стратегии.Классическим примером антагонистической игры является игра с двумя участниками, загадывающими независимо друг от друга числа. Предполагается, что если их сумма оказывается четной, то выигрыш, равный 1, достается первому игроку, а если нечетной, то второму. Положив, что для обоих игроков загадывание нечетного числа является первой стратегией, а четного — второй, можем записать платежную матрицу данной игры:н/ччн/ч1-1ч-11(1)Строки матрицы (1) соответствуют стратегиям игрока I, столбцы — стратегиям игрока II, а ее элементы — результатам первого игрока. Также из определения игры следует, что элементы данной матрицы, взятые с обратным знаком, соответствуют выигрышам второго игрока.Более сложная и содержательная платежная матрица может быть получена, если несколько модифицировать предложенную игру. Допустим, что оба участника имеют право загадывать числа от 1 до 4, что составляет их соответствующие стратегии. В случае, если результат сложения задуманных чисел будет четным, то второй игрок выплачивает первому получившуюся сумму, а если нечетным, то первый — второму. Некоторая условность и искусственность в постановке проблемы не должны в данном случае нас смущать, так как к подобной форме может быть сведена модель, описывающая, например, соревнование двух фирм за вновь открывшийся рынок сбыта продукции и т. п.Как уже отмечалось, важнейшим в теории игр является вопрос об оптимальности решения (выбора стратегии) для каждого из игроков. Проанализируем с этой точки зрения некоторую матричную игру, для которой задана платежная матрица . При выборе игроком I стратегии iего гарантированный доход независимо от действий игрока II составит . Поскольку он может выбирать i самостоятельно, то целесообразно этот выбор сделать таким, чтобы он при любой стратегии противника максимизировал величину гарантированного дохода, т. е. обеспечивал получение , Такой принцип выбора стратегии получил название«принцип максимина». С другой стороны, аналогичные рассуждения могут быть проведены по поводу действий второго игрока. Его наибольший проигрыш при выборе стратегии j составит , и, следовательно, ему следует выбирать стратегию так, чтобы минимизировать величину проигрыша при любых действиях соперника, т. е. обеспечить . В этом суть принципа минимакса.Можно доказать справедливость следующего соотношения:(3)Однако очевидный интерес представляет ситуация, при которой значение выигрыша (платежа), получаемого игроком I при выборе им максиминной стратегии, равно платежу (проигрышу) II-го игрока при минимаксной стратегии=(4)В этом случае говорят, что игра имеет седловую точку. Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. Понятие «оптимальность» здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии и , образующие седловую точку, называются оптимальными, а значение . называют ценой игры. Тройка считается решением матричной игры с седловой точкой.ИгрокиB1B2B3a = min(Ai)A12452A26242A34684b = max(Bi)668Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 4, которая указывает на максимальную чистую стратегию A3.Верхняя цена игры b = min(bj) = 6.Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 4 <= y <= 6. 2) Дальнейшее развитие теории матричных игр основывается на исследовании игры как некоторого повторяющегося процесса. Действительно, вряд ли можно дать содержательные рекомендации по такому вопросу, как следует поступать участникам однократно проводимой игры, не имеющей седловой точки. В случае же ее многократных повторов естественной и плодотворной представляется идея рандомизации выбора стратегий игроками, т. е. внесение в процесс выбора элемента случайности. Действительно, систематическое отклонение, например, игрока I от максиминной стратегии с целью увеличения выигрыша может быть зафиксировано вторым игроком и наказано. В то же время абсолютно хаотичный выбор стратегий не принесет в среднем наилучшего результата.►Смешанной стратегией игрока I в игре с матрицей называется упорядоченный набор действительных чисел xi, i1:m , удовлетворяющих условиям(1)Числа интерпретируются как вероятности применения игроком I стратегий 1,2,..., т, которые, в отличие от смешанных, также называют чистыми стратегиями.Аналогично вводится понятие смешанных стратегий игрока II, которые определяются как набор чисел уj, jl:n, удовлетворяющих условиям(2) Тогда, если игрок I применяет смешанную стратегию х=(х1, х2, ..., хт), а игрок II смешанную стратегию у = (у1, у2,…,yn), то математическое ожидание выигрыша игрока I (проигрыша игрока II) определяется соотношением(3)В дальнейшем через Xбудем обозначать множество допустимых смешанных стратегий игрока I, определяемое условием 2, а через Y — определяемое условием 3 множество допустимых смешанных стратегий игрока П.К поиску решения игры в смешанных стратегиях, могут быть применены критерии максимина-минимакса. В соответствии с ними игрок I будет выбирать свою смешанную стратегию x=(xl, х2, ..., хт) таким образом, чтобы максимизировать наименьший средний выигрыш:(4)который, как можно доказать, равен(5)а игрок II — свою смешанную стратегию так, чтобы минимизировать наибольший средний проигрыш:(6)также равный(7)Для любых х е Xи г/ € У справедливо неравенство(8)►Стратегии и называют оптимальными смешанными стратегиями, если для любых хХ и yYсправедливо равенство= (9)называют ценой игры, и если х*и у*существуют, то говорят, что игра имеет решение в смешанных стратегиях (х* , у*, v) .3)Задача, решаемая первым игроком, была сформулирована как максимизация наименьшей из суммно если определить некоторое хт+1 , для которого выполняется(1)то она может быть сведена к задаче линейного программирования: (2) при ограничениях(3)Проведя аналогичные рассуждения, приходим к тому, что задача минимизации наибольшего ожидаемого проигрыша, решаемая игроком II , сводится к задаче линейного программирования(4)(5)Таким образом, мы получаем возможность применять все возможности аппарата линейного программирования для поиска оптимальных стратегий обоих игроков. б) смешанная стратегия второго игрока как решение двойственной задачи линейного программированияИногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного jaij > akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э Maij ≤ ail и хотя бы для одного iaij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.С позиции проигрышей игрока В стратегия B3 доминирует над стратегией B2 (все элементы столбца 3 больше элементов столбца 2), следовательно исключаем 3-ой столбец матрицы. Вероятность q3 = 0.246246В платежной матрице отсутствуют доминирующие строки.Мы свели игру 3 x 3 к игре 3 x 2.Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.3. Находим решение игры в смешанных стратегиях.Запишем систему уравнений.Для игрока I2p1+6p2+4p3 = y4p1+2p2+6p3 = yp1+p2+p3 = 1Для игрока II2q1+4q2 = y6q1+2q2 = y4q1+6q2 = yq1+q2 = 14)Дискретная задача о выборе оптимальной траектории.7 6 49 7 8 58 6 76 9 7 47 8 98 6 5 47 8 95) Математическая постановка задачи динамического программирования.Из множества возможных управлений U найти такое оптимальное управление u, которое переводит физическую систему S из начального состояния S0˜S0 в конечное состояние SwSw так, чтобы при этом выигрыш W обращался в максимум. Одной из задач, решаемых методом динамического программирования, является задача об оптимальном режиме набора высоты и скорости летательным аппаратом. Пусть самолет (или другой летательный аппарат), находящийся на высоте H0 и имеющий скорость V0, должен быть поднят с высоты В на высоту А. Известен расход горючего, потребный для подъема летательного аппарата и для увеличения скорости. Требуется найти оптимальный режим набора высоты и скорости, при котором общий расход горючего будет минимальным.Первоначально метод был предложен Дэвидоном (Davidon [1959] ), а затем развит Флетчером и Пауэллом (Fletcher, Powell [1963] ). Метод Дэвидона - Флетчера - Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Djf(y). Направление градиента является, таким образом, отклоненным в результате умножения на  -Dj , где Dj - положительно определенная симметрическая матрица порядка n х n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.ЛитератураЗайченко Ю.П. Исследования операций. – Киев: Вища школа, 1975.Кузнецов Ю.Н. и др. Математическое программирование. – М.: Высшая школа, 1980.Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. – М.: Наука, 1964.Карманов В.Г. Математическое программирование. – М.: Наука, 1980.Оуэн Г. Теория игр. – М.: Мир, 1971.

Список литературы [ всего 5]

Литература
1.Зайченко Ю.П. Исследования операций. – Киев: Вища школа, 1975.
2.Кузнецов Ю.Н. и др. Математическое программирование. – М.: Высшая школа, 1980.
3.Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. – М.: Наука, 1964.
4.Карманов В.Г. Математическое программирование. – М.: Наука, 1980.
5.Оуэн Г. Теория игр. – М.: Мир, 1971.
Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.00535
© Рефератбанк, 2002 - 2024