Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

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

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

Приводятся результаты вычислительного эксперимента.

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

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:52:52)