Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями



Скачать 133.38 Kb.
Дата16.10.2012
Размер133.38 Kb.
ТипЗадача


Казанский Государственный Университет

Факультет Вычислительной Математики и Кибернетики

Кафедра Системного Анализа и Информационных Технологий

Методы решения задач аукциона с ценовыми функциями.

Работу выполнила

Зайнутдинова Залина

студентка группы № 948

Научный руководитель

профессор Коннов И.В.

Казань, 2009г.

Постановка задачи.

Аукцион при ценах, зависящих от объёмов поставок и покупок.

Постановка задачи.

Пусть

-ый продавец заявляет максимальное и минимальное объемы поставок, -ый покупатель заявляет максимальное и минимальное объемы покупок.

Избыточный спрос для пассивных участников положим равным .

Требуется определить объемы продаж , объемы покупок , а также цену единицы товара, установившуюся на аукционе.

Решение.

Определим допустимое множество:



Решением задачи будет являться вектор объемов и цена , которые удовлетворяют условию:

,

,

Решение вариационного неравенства

(1)

дает решение задачи аукциона [1].

Точка gif" name="object21" align=absmiddle width=73 height=19> есть решение задачи (1), следовательно, она является решением задачи оптимизации [1]:



Положим, что .

Запишем итерационную формулу:

(2)

Задача оптимизации:



дает решение .
Рассмотрим функции и , имеющие значения стоимости проданного -ым продавцом объема и стоимости купленного -ым покупателем объема товара соответственно:

,

Задача оптимизации для (2) имеет вид:

,

где .

Метод условного градиента.

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

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

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

Во-первых, отыскивается решение следующей вспомогательной задачи:

(1)

Легко увидеть, что при сделанных выше предположениях задача (1) имеет решение. Обозначим ее решение .

Далее, положим .

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

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

Например, такой шаговый множитель можно определить как:

.

Наконец, вычисляем следующее приближение .

Пример 1.

Функция цены продавца задается формулой

Функция цены покупателя задается формулой
Число продавцов m=5;

Число покупателей n=8;

Начальные объемы поставок и цены продавцов представлены в таблице:

Продавец

Начальный объем поставки

Начальные значения цен

1

0.7

0.5890

2

0.4

0.3637

3

0.8

0.1129

4

0.9

0.6811

5

0.6

0.5754



Начальные объемы покупок и начальные значения цен покупателей:



Покупатель

Начальный объем покупки

Начальные значения цен

1

0.4

0.3859

2

0.1

0.3783

3

0.5

0.6600

4

0.2

0.5447

5

0.7

0.1669

6

0.4

0.6858

7

0.3

0.5799

8

0.8

0.0808


Значение установившейся цены аукциона P=0.1129;

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

Продавец

Объем продажи

Значения цен продавцов

1

0.2563

0.2157

2

0.2372

0.2157

3

0.8

0.1129

4

0.2850

0.2157

5

0.2249

0.2157



Покупатель

Объем покупки

Значения цен покупателей

1

0.2598

0.4289

2

0.0649

0.3908

3

0.5

0.6600

4

0.1299

0.5785

5

0.1384

0.2492

6

0.4

0.6858

7

0.3

0.5799

8

0.0104

0.1440


Двойственный метод.

Рассмотрим теперь применение теории двойственности для решения задач аукциона.

Функция Лагранжа имеет вид:



Тогда прямая задача записывается в виде



Рассмотрим двойственную задачу:

,

где
Найдем производную функции :



и приравняем ее к нулю.

Таким образом, будет найдено значение цены и соответствующих значений объемов поставки и продаж.

Пример 3.(решение задачи 1методом Удзавы)

Функция цены продавца задается формулой

Функция цены покупателя задается формулой

Число продавцов m=5;

Число покупателей n=8;

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

Значение установившейся цены аукциона P=0.2579;

Объемы продаж и объемы покупок соответственно равны:

Продавец

Объем продажи

Значения цен продавцов

1

0.3065

0.2579

2

0.2836

0.2579

3

0.8

0.1129

4

0.3408

0.2579

5

0.2690

0.2579



Покупатель

Объем покупки

Значения цен покупателей

1

0.4000

0.3859

2

0.1000

0.3783

3

0.5000

0.6600

4

0.2000

0.5447

5

0.0998

0.2579

6

0.4000

0.6858

7

0.3000

0.5799

8

0

0.1455



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



Для решения, полученного методом условного градиента, значение функции составляет -0.7195, а для решения задачи аукциона двойственным методом –

-0.7054.

Т.о., при решении этого примера метод условного градиента дает более точный результат.

Метод проекции градиента.

Пусть -некоторое начальное приближение. Далее будем строить последовательность  по правилу

,

где

, ,

- положительная величина.

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


. (1)

Ф.П. Васильев «Численные методы решения экстремальных задач» (стр.193)

Теорема 4.4.1 Пусть  – выпуклое замкнутое множество из . Тогда всякая точка   имеет, и притом единственную, проекцию на это множество.
Пусть задан способ выбора . Тогда из теоремы следует, что так как Z-выпуклое замкнутое множество, то последовательность  будет однозначно определяться.

Остается проблема построения проекции точки на выпуклое множество.

Для гиперплоскости вектор проекции находится по формуле:


.

Для случая усеченной гиперплоскости  формула для компонентов вектора проекции имеет тот же вид, но для исключения случаев



регулируется значение шага ∝k.

В основной итерации выбора шага возможно априорное задание величин



Например, 

Сходимость метода исследована в [1].
Пример 4. (решение задачи 1 методом проекции градиента)

Функция цены продавца задается формулой

Функция цены покупателя задается формулой
Число продавцов m=5;

Число покупателей n=8;

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

Продавец

Объем продажи

Значения цен продавцов

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)
Для решения задачи оптимизации ,

изучим поведение функции

  1. Функция дифференцируема.

  2. Вторая производная



Таким образом, функция является выпуклой.

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

Для этого выберем произвольные 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



Похожие:

Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconGief ru Кафедра информационных технологий методы исследования и моделирование
Направления и методы анализа национальной и региональной экономики. Система статистических показателей
Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconСовременные проблемы системного анализа и управления
Целью данного курса является: выработка системного видения мира; ознакомление студентов с технологией решения сложных проблем системного...
Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconОпыт внедрения информационных технологий для решения задач научной каталогизации и учета в Государственном Эрмитаже
Опыт внедрения информационных технологий для решения задач научной каталогизации и учета
Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconРешение практических задач и заданий на семинаре
Кафедра математических методов, статистики и информационных технологий в экономике
Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconПрограмма «Теория и математические методы системного анализа и управления в технических системах»
Цель программы. Программа нацелена на подготовку специалистов в области системного анализа и принятия решений в ходе проектирования...
Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconПрограмма цикла обучения для стажеров-бакалавров Международного института информационных технологий (г. Пуна, Индия) по вычислительной аэрогидродинамике «Численные методы решения уравнений математической физики»
«Численные методы решения уравнений математической физики»
Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconКинетические методы анализа
Возможность применения достаточно простой и доступной аппаратуры, экспрессность выполнения анализа привлекает внимание к этим методам,...
Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconКафедра системного анализа пояснительная записка к учебно-исследовательско

Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconЧеловека на объекты исследования, включая вопросы анализа
Теоретические основы и методы системного анализа, оптимизации, управления, принятия решений и обработки информации
Кафедра Системного Анализа и Информационных Технологий Методы решения задач аукциона с ценовыми функциями iconИнформационные системы и процессы Формула cпециальности
Методы и модели описания, оценки, оптимизации информационных процессов и информационных ресурсов, а также средства анализа и выявления...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org