Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями
|
Скачать 133.38 Kb.
|
Казанский Государственный Университет Факультет Вычислительной Математики и Кибернетики Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями. Работу выполнила Зайнутдинова Залина студентка группы № 948 Научный руководитель профессор Коннов И.В. Казань,  2009г. Постановка задачи. Аукцион при ценах, зависящих от объёмов поставок и покупок. Постановка задачи. Пусть  -ый продавец заявляет максимальное  и минимальное  объемы поставок,  -ый покупатель заявляет максимальное  и минимальное  объемы покупок.Избыточный спрос для пассивных участников положим равным  .Требуется определить объемы продаж  , объемы покупок  , а также цену единицы товара , установившуюся на аукционе.Решение. Определим допустимое множество:  Решением задачи будет являться вектор объемов   и цена  , которые удовлетворяют условию: ,   ,  Решение вариационного неравенства  (1)дает решение задачи аукциона [1]. Точка есть решение задачи (1), следовательно, она является решением задачи оптимизации [1]: Положим, что  .Запишем итерационную формулу:  (2)Задача оптимизации:  дает решение  .Рассмотрим функции  и  , имеющие значения стоимости проданного -ым продавцом объема и стоимости купленного -ым покупателем объема товара соответственно: ,  Задача оптимизации для (2) имеет вид:  ,где  .Метод условного градиента. Воспользуемся методом условного градиента для решения задачи условной минимизации функции  на выпуклом замкнутом и ограниченном множестве  .В методе условного градиента для построения последовательности приближений используются условно релаксационные направления для минимизируемой функции  в точке, что позволяет подбирать шаговый множитель, невыводящий очередное приближение за пределы допустимой области. Предположим, что, начиная с произвольной точки  , уже найдены приближения  . Опишем действия, которые необходимо выполнить для отыскания следующего приближения  . Во-первых, отыскивается решение следующей вспомогательной задачи:  (1)Легко увидеть, что при сделанных выше предположениях задача (1) имеет решение. Обозначим ее решение  . Далее, положим  . Если  , то отсюда и из определения вектора следует, что  . Таким образом, в точке  выполняется необходимое условие условного минимума функции на множестве .Предположим, что  Это означает, что процесс построения последовательности приближений бесконечен, ни одна точка  не является точкой условного минимума. В этом случае вектор  является условно релаксационным направлением для функции в точке и, следовательно, можно сделать шаг в этом направлении, не нарушив ограничений и уменьшив значение функции. Например, такой шаговый множитель можно определить как:  .Наконец, вычисляем следующее приближение  . Пример 1. Функция цены продавца задается формулой  Функция цены покупателя задается формулой  Число продавцов m=5; Число покупателей n=8; Начальные объемы поставок и цены продавцов представлены в таблице:
Начальные объемы покупок и начальные значения цен покупателей:
Значение установившейся цены аукциона P=0.1129; Объемы продаж и объемы покупок, а также соответствующие им цены составляют:
Двойственный метод. Рассмотрим теперь применение теории двойственности для решения задач аукциона. Функция Лагранжа имеет вид:  Тогда прямая задача записывается в виде  Рассмотрим двойственную задачу:  ,где  Найдем производную функции  :  и приравняем ее к нулю. Таким образом, будет найдено значение цены и соответствующих значений объемов поставки и продаж. Пример 3.(решение задачи 1методом Удзавы) Функция цены продавца задается формулой Функция цены покупателя задается формулой Число продавцов m=5; Число покупателей n=8; Положим значения минимальных поставок и продаж нулевыми, а значения максимальных положим стартовыми для продавцов и покупателей. Значение установившейся цены аукциона P=0.2579; Объемы продаж и объемы покупок соответственно равны:
Сравним с ответом, полученным методом условного градиента. Для этого вычислим значение минимизируемой функции в задаче оптимизации: Для решения, полученного методом условного градиента, значение функции составляет -0.7195, а для решения задачи аукциона двойственным методом – -0.7054. Т.о., при решении этого примера метод условного градиента дает более точный результат. Метод проекции градиента. Пусть  -некоторое начальное приближение. Далее будем строить последовательность  по правилу ,где  ,  , - положительная величина. По определению проекцией точки |
на множество 
называется вектор 
, удовлетворяющий условию
. (1)
– выпуклое замкнутое множество из 
. Тогда всякая точка 
имеет, и притом единственную, проекцию на это множество. 
вектор проекции находится по формуле:
формула для компонентов вектора проекции имеет тот же вид, но для исключения случаев
| Продавец | Объем продажи | Значения цен продавцов |
| 1 | 0.4655 | 0.3917 |
| 2 | 0.2433 | 0.2212 |
| 3 | 0.7295 | 0.1030 |
| 4 | 0.6336 | 0.4795 |
| 5 | 0.3703 | 0.3551 |
-
Покупатель
Объем покупки
Значения цен покупателей
1
0.2975
0.4164
2
0.0001
0.4161
3
0.3022
0.7603
4
0.0422
0.6272
5
0.6736
0.1695
6
0.1931
0.8047
7
0.1300
0.6672
8
0.8034
0.0807
Значение целевой функции -0.0547. Что дает результат, менее точный, чем методы условного градиента и метод Удзавы.
Метод штрафов.
Перепишем задачу в виде
В результате последовательной минимизации функции при k=1,2,.. мы получим минимизирующую последовательность для исходной задачи.
Воспользуемся модификацией метода сопряженных градиентов на параллелограмме для решения построенной задачи.
Обозначим
Градиент этой функции
Пусть
- некоторое начальное приближение. Будем строить последовательность 
по правилам
, где
, 
,величина
определяется условиями
, 
,а
вычисляется по одной из формул (1), (2) или (3)
(1)
(2)
(3)Для решения задачи оптимизации
,изучим поведение функции
Функция дифференцируема.
Вторая производная
Таким образом, функция является выпуклой.
Для решения этой оптимизационной задачи можно воспользоваться метод касательных.
Для этого выберем произвольные a1 и b1 такие, что fk(∝) выпукла на [a1 b1].
Вычисляем f k(∝n). Если f k(∝n)=.0, то задача решена, итерации на этом заканчиваются. Иначе полагаем
Пример 4. (решение задачи 1 методом штрафов)
Функция цены продавца задается формулой
Функция цены покупателя задается формулой
Число продавцов m=5;
Число покупателей n=8;
Объемы продаж и объемы покупок, а также соответствующие им цены составляют:
-
Продавец
Объем продажи
Значения цен продавцов
1
0.6864
0.5776
2
0.3916
0.3561
3
0.7974
0.1125
4
0.8843
0.6693
5
0.5867
0.5626
-
Покупатель
Объем покупки
Значения цен покупателей
1
0.4089
0.3835
2
0.1087
0.3753
3
0.5152
0.6534
4
0.2125
0.5391
5
0.7038
0.1665
6
0.4158
0.6782
7
0.3134
0.5740
8
0.8019
0.0807
Похожие:
 | Gief ru Кафедра информационных технологий методы исследования и моделирование Направления и методы анализа национальной и региональной экономики. Система статистических показателей | | Современные проблемы системного анализа и управления Целью данного курса является: выработка системного видения мира; ознакомление студентов с технологией решения сложных проблем системного... |
| Опыт внедрения информационных технологий для решения задач научной каталогизации и учета в Государственном Эрмитаже Опыт внедрения информационных технологий для решения задач научной каталогизации и учета | | Решение практических задач и заданий на семинаре Кафедра математических методов, статистики и информационных технологий в экономике |
| Программа «Теория и математические методы системного анализа и управления в технических системах» Цель программы. Программа нацелена на подготовку специалистов в области системного анализа и принятия решений в ходе проектирования... | | Программа цикла обучения для стажеров-бакалавров Международного института информационных технологий (г. Пуна, Индия) по вычислительной аэрогидродинамике «Численные методы решения уравнений математической физики» «Численные методы решения уравнений математической физики» |
 | Кинетические методы анализа Возможность применения достаточно простой и доступной аппаратуры, экспрессность выполнения анализа привлекает внимание к этим методам,... |  | Кафедра системного анализа пояснительная записка к учебно-исследовательско |
| Человека на объекты исследования, включая вопросы анализа Теоретические основы и методы системного анализа, оптимизации, управления, принятия решений и обработки информации | | Информационные системы и процессы Формула cпециальности Методы и модели описания, оценки, оптимизации информационных процессов и информационных ресурсов, а также средства анализа и выявления... |