Нелинейное программирование

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

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

В области задач управления разного уровня довольно типичной есть задачи размещения (location problem), скажем, сервисных центров (клиник, полицейских служб, учебных заведений), складов или производительных мощностей. Целью таких задач есть определения такого размещения, для которого минимизируется, например, расстояние между центром предоставления услуг та их потребителем. Задачи такого типа появляются в практике коммуникационного обеспечения (пути, железная дорога, кабельная связь), где нужно исполнить определенные работы с минимальной стоимостью.

Начальными данными для этой задачи есть координаты и весовые коэффициенты (количество населения, число школьников, пенсионеров или больных) клиентов, дополнительно учитываются определенные ограничения. «Клиентами» в данном примере есть 25 районов города, а предоставляемая услуга – диагностико-процедурный центр для больных сахарным диабетом. Строительство центра и оборудование достаточно дорогостоящи, планируется строительство одного центра на город. Нужно найти координаты оптимального центра, чтобы минимизировать суму расстояний от центра ко всем районам города.

Экономико-математическая модель.

• Найти координаты центра, чтобы сума расстояний была минимальной при ограничениях:

• Расстояния от центра <= Максимально допустимой границы; все неизвестные больше нуля.

 

Реализация в Excel.

 

Оптимальное размещение
	X	Y	M	XM	YM	Растояние от центра	Разница
Балашовка	9,0	6,0	467	4203	2802	2,41	1,06
Ст. Балашовка	8,0	12,0	976	7808	11712	3,87	3,87
Ковалевка	7,5	14,5	527	3952,5	7641,5	6,38	6,38
Бустымки	11,5	6,0	158	1817	948	4,21	4,21
Жадова	7,0	12,5	785	5495	9812,5	4,46	4,46
Поповка	7,5	2,5	1021	7657,5	2552,5	5,64	5,64
Братковский р-н	11,5	8,0	946	10879	7568	3,63	3,63
Пироговка	8,0	9,5	826	6608	7847	1,38	1,38
Балка	8,5	15,5	465	3952,5	7207,5	7,40	7,40
бол. Балка	12,0	3,0	721	8652	2163	6,58	6,58
Кировский р-н	10,5	2,0	719	7549,5	1438	6,67	6,67
Волкова	5,0	9,0	683	3415	6147	3,00	3,00
Беляева	4,0	7,5	384	1536	2880	3,92	3,92
Озерка	10,0	11,5	996	9960	11454	3,99	3,99
Камышевский р-н	12,0	4,0	454	5448	1816	5,84	5,84
Октябрьский	1,0	11,5	846	846	9729	7,65	7,65
Буховский	13,0	11,5	908	11804	10442	6,14	6,14
Лесной	10,0	3,5	1039	10390	3636,5	5,09	5,09
Солгутовский	8,5	0,5	182	1547	91	7,65	7,65
Бобриково	11,5	13,0	472	5428	6136	6,07	6,07
Приречный	4,5	10,0	731	3289,5	7310	3,86	3,86
Нижний	10,0	3,5	346	3460	1211	5,09	5,09
Промышленный	10,0	9,0	985	9850	8865	2,30	2,30
Бережинка	14,0	8,5	127	1778	1079,5	6,14	6,14
Маслениковка	7,5	3,5	200	1500	700	4,64	4,64
Центр	7,9	8,1	15964	138826	133189	124,0
	Радиус=		1,345		7,655	Граница

 

Создаем таблицу с начальным данными (координаты х и у, весомый коэффициент). В столбец Расстояние от центра вводим формулу: =КОРЕНЬ((Х города-Х центр)^2+(У города-У центр)^2). В целевую ячейку вводим формулу сумы по столбцу Расстояние от центра. Запускаем программу Поиска решений и решаем это задачу только с ограничением координат больших нуля. Полученные оптимальные координаты центра (9,2; 7,9), и сума расстояний от которого ко всем районам города составляет 120,6 . Полученный результат полностью экономический, если идет речь о прокладке коммуникаций, где минимизируются затраты. Но с позиции предоставления услуг он оказывается «несправедливым» для тех клиентов на периферии, которым далеко ехать к центру. Введем критерий «справедливости», при котором устанавливается верхняя граница на величину расстояния от центра. Для того чтобы найти оптимальную границу нужно найти максимально допустимый радиус в диапазоне столбца Расстояния от центра функцией минимума. Столбец Разница заполняем формулами: =КОРЕНЬ((Х города-Х центр)^2+(У города-У центр)^2) – Макс. Радиус. В ячейку Граница вводим формулу: 9 - Макс. Радиус.

 

Запускаем программу Поиск решений командой Данные/Анализ/Поиск решения (В Excel 2007) Сервис/Поиск решения (В Excel 2003 и ниже). В полях Установить целевую ячейку, Изменяя ячейки, Ограничения вводим соответствующие адреса ячеек. Не забываем фиксировать в окне Параметры поиска решений переключатель на позицию Неотрицательные значения. Нажимаем кнопку Выполнить и в появившемся окне Результаты поиска решения выводим отчет по устойчивости.

 

 

 

 

 

 

 

 

 

Анализ результата.

Оптимальные координаты центра (7,9; 8,1) обеспечивают минимальное общее расстояние 124. Ближайший район  к центру Пироговка, наидлиннейший – Октябрьский и Лесной. Таким образом, рассмотренная модель нелинейной оптимизации для поиска координат диагностического центра позволяет учитывать специфику реальной ситуации введением соответствующих ограничений.

 

Заключение

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

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

 

Список литературы

1. Волошин Г.Я., Методы оптимизации в экономике: Учебное пособие. – М.: «Издательство «Дело и Сервис», 2005. – 320 с.
2. Данилов Н.Н. Курс математической экономики. – М.: Высшая школа, 2006.
3. Высшая математика. Математическое программирование: А. В. Кузнецов, В. А. Сакович, Н. И. Холод — Санкт-Петербург, Лань, 2010 г.- 352 с
4. Методы оптимизации в прикладных задачах: В. И. Струченков — Москва, Солон-Пресс, 2009 г.- 320 с.
5. Определитель Еремина в линейной и нелинейной алгебре. Линейное и нелинейное программирование. Новый метод: М. А. Еремин — Москва, КомКнига, 2006 г.- 120 с.
6. Программирование в алгоритмах: С. Окулов — Санкт-Петербург, Бином. Лаборатория знаний, 2007 г.- 384 с.
7. Программирование. Математические основы, средства, теория: С. Лавров — Санкт-Петербург, БХВ-Петербург, 2007 г.- 320 с.
8. Коршунов Н.И., Плясунов В.С., Математика в экономике. – М.: Изд-во «Вита-Пресс», 2006. – 345 с.
9. Кундышева Е.С. Математическое моделирование в экономике: Учебное пособие/ Под науч. ред. Проф. Б.А. Суслакова. – М.: Издательско-торговая корпорация «Дашков и Кο», 2005. – 352 с.
10. Достоверные вычисления. Базовые численнные методы: У. Кулиш, Д. Рац, Р. Хаммер, М. Хокс — Санкт-Петербург, НИЦ "Регулярная и хаотическая динамика", 2005 г.- 496 с.