Двухфазный поиск с чередующимися окрестностями для задачи размещения предприятий и фабричного ценообразования

Назначение - поиск приближенных решений задачи размещения предприятий и фабричного ценообразования (Facility location and pricing problem)

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

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

Используемый алгоритм - двухфазный поиск с чередующимися окрестностями, использующий локальный поиск для определения размещения предприятий и локальный поиск по разным окрестностям для нахождения цен при выбранном размещении. Алгоритм опубликован в статье [1].

Для работы программы необходимо сформировать input.txt файл. 
1) Указать число примеров решаемой задачи (integer).

Для каждого из примеров:
2.а) Указать размерность задачи (число возможных мест открытия предприятий, число клиентов, число открываемых предприятий) и параметры метода решения (максимальное число итераций, максимальное время счета в секундах, максимальное число итераций внутреннего VNS-алгоритма, максимальный размер k окрестности k-flip, глубина просмотра окрестностей k-flip); (все integer)
2.б) Указать матрицу транспортных затрат (строки - возможные места открытия предприятий, столбцы - клиенты); (все double)
2.в) Указать бюджеты клиентов. (все double)
В прилагаемом файле Program1.png. приведен тестовый пример. Результаты работы программы выводятся в файл output.txt. В нем выводятся результаты работы (места, где открыты предприятия, цены, значение целевой функции и время работы) по каждой итерации и лучшее найденное решение в конце. Как видно из результатов расчета (файл Program2.png), на втором примере задачи (файл Program1.png), в найденном решении открыты предприятия в местах 0 и 2, и назначена цена 3 на обоих предприятиях. Итоговый доход равен 12. Время работы менее секунды (округление до целых). 

[1] Кочетов Ю., Панин А., Плясунов А. Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и ценообразования. Дискретн. анализ и исслед. опер., 2015, том 22, номер 3 с. 36-54. https://doi.org/10.17377/daio.2015.22.480

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

Инструментальные средства создания - Microsoft visual studio 2012, c/c++.