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

Введение.

Глава 1. Программно реализованные методы решения линейных задач распределения ресурсов: аналитический обзор.

1.1. Задачи линейного программирования (ЛП).

1.1.1. Редукция к стандартной задаче ЛП.

1.1.2. Симплекс-метод.

1.1.3. Замечания о применимости симплекс-метода.

1.1.4. Метод барьеров (внутренних точек).

1.2. Задачи целочисленного и смешанно-целочисленного программирования.

1.3. Задачи сетевого линейного программирования.

Глава 2. Многоресурсное распределение

2.1. Постановка общей задачи.

2.2. Целевое перемещение решения.

2.2.1. Симплекс-метод решения задачи ЛП.

2.2.2. Поиск чебышевской точки.

2.3. Примение метода целевого перемещения решения.

2.3.1. Расчет действия мобильных групп патрулирования экологически опасных объектов.

2.3.2. Распределение медикаментов по регионам, пострадавшим от землетрясений.

Глава 3. Одноресурсное распределение.

3.1. Бесприоритетное распределение.

3.2. Приоритетное распределение.

3.3. Применение методов одноресурсного распределения.

3.3.1. Эскизный расчет бюджета.

3.3.2. Распределение медикаментов.

Глава 4. РЕСУРС-комплекс: архитектура, характеристика реализации, оценка функциональной эффективности.

4.1. Архитектура.

4.1.1. Переносимость вычислительного ядра.

4.2. Характеристика реализации.

4.2.1. Управление задачами.

4.2.2. Графический интерфейс.

4.2.3. Генератор отчетов.

4.3. Оценка функциональной эффективности.

4.3.1. Типы современного программного обеспечения для решения задач линейного программирования (ПО ЛП).

4.3.2. Формат МР8 — язык моделирования для ЛП-пакетов.

4.3.3. Характеристика известных средств ПО ЛП.

4.3.4. Сравнительный анализ.

4.3.4.1. Схема смешанного алгоритма внутрених точек.

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

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

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

ЧТО величина ожидаемого годового дохода, например, применительно к государственному бюджету — это прогнозируемая величина. Поэтому в диссертации предложено расширение существующего задачного арсенала одноресурсного распределения. Задача одноресурсного распределения поставлена и решена как задача интервального анализа, где исходные и искомые величины представлены вещественными отрезками. Предлагаемые алгоритмы многоресурсного и одноресурсного распределения предназначены для ситуационного управления процессами статусной конкуренции [13, 7, 8]. Глобальные и локальные экономические механизмы представляют собой наиболее наглядные примеры статусных конкурирующих систем. Статус (приоритет) понимается как положение элемента системы, определяющее его возможности по потреблению и управлению ресурсами. Ситуационное управление процессами статусной конкуренции неразрывно связано с решением задач преобразования ресурсов [6,9]. Постановки таких задач так или иначе сводятся к отысканию ресурсно-обоснованного плана перевода системы из исходного состояния (заданного описанием отправной ситуации) в требуемое, которое представлено описанием целевой ситуации. Линейные задачи многоресурсного распределения традиционно решаются методами линейного программирования (ЛП). Линейное программирование пригодно для моделирования различных задач планирования, маршрутизации, составления расписаний, назначений, смесей и многих других. ЛП и его расширения используются при планировании в транспортной индустрии, энергетике, телекоммуникационной и других отраслях. Применение методов

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

В диссертации предложена дополнительная к стандартной постановка задачи многоресурсного распределения, разработан алгоритмически реализованный метод решения и программные средства, расширяющие существующий набор средств, ориентированных на диалоговую работу в режиме вычислительного эксперимента. Основная идея - дать эксперту-планировщику возможность перемещения в линейном пространстве с задаваемым дискретом, исходя из требований к значениям ресурсных функций (целевое перемещение решения). Предложенные в диссертации алгоритмы реализованы на языке С++ и вошли в состав вычислительного ядра диалоговой системы РЕСУРС-комплекс, разработанной в рамках исследований методов и вычислительных средств преобразования ресурсов, проводимых в Институте проблем информатики

РАН.

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

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

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

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

• постановка и решение задач иерархического одноресурсного распределения как задач интервального анализа;

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

Исследование результативности диалоговой программной системы РЕСУРС-комплекс, разработанной диссертантом, подтвердило эффективность построенных алгоритмов при работе в условиях изменяющейся информированности эксперта-планировщика. РЕСУРС-комплекс применялся в Институте проблем информатики РАН для экспериментального проектирования бюджетов в иерархических системах и для решения задач многоресурсного распределения в условиях изменяющейся информированности.

Результаты диссертации, опубликованные в 7 печатных трудах, обсуждались на семинарах ВМиК МГУ (1995-96г.г.) и ИПИ РАН (1995-2001г.г.), на научной сессии ИПИ РАН «Проблемы и методы информатики» (17-18 апреля 2001г.), на международной научной конференции «Пользовательский интерфейс в современных компьютерных системах» (Орёл, Россия, 2-4 ноября 1999г.) Исследование прикладной эффективности разработанных алгоритмов производилось в Институте проблем информатики РАН, Институте медико-биологических проблем РАН и ООО «Марис». Первая глава диссертации содержит аналитический обзор традиционных методов решения линейных задач распределения ресурсов. Вторая глава посвящена решению задач многоресурсного распределения. В третьей главе изложены алгоритмы одноресурсного распределения.

Введение 11

В четвертой главе описана программная реализация разработанных методов, а также приведен обзор современных программных средств решения линейных задач распределения ресурсов и их сравнительный анализ. На простых примерах проведено сравнение РЕСУРС-комплекса и американской программной системы LINGO, показана эффективность разработанных методов и алгоритмов.

Заключение 96

6. архитектура программной диалоговой системы РЕСУРС-комплекс, рассчитанной на экспертов-планировщиков, решающих задачи распределения ресурсов в условиях изменяющейся информированности;

7. программная реализация (на языке С++) и исследование сравнительной прикладной эффективности экспериментальной версии программной диалоговой системы РЕСУРС-комплекс для решения двух классов задач распределения ресурсов в режиме вычислительного эксперимента.

1. Данциг Дж. Линейное программирование, его применение и обобщения. -М.: Прогресс, 1966.

2. Зуховицкий СИ, Авдеева Л.И. Линейное и выпуклое программирование. -М.: Наука, 1967.-460 с.

3. Ильин A.B. Математическое обеспечение процессов преобразования ресурсов. // Системы и средства информатики. Вып. 9. М.: Наука, 1999. - С. 159-177.

4. Ильин В.Д., Гавриленко Ю.В., Ильин A.B., Макаров Е.М. Математические средства ситуационной информатизации. М.: Наука, 1996. - 88 с.

5. Ильин A.B. Две математические модели ресурсных преобразований в статусных конкурирующих системах. Рукопись депонирована в ВИНИТИ 16.11.2000, №2910-В00.-21 с.

6. Ильин A.B. Вычислительные средства преобразования ресурсов. Рукопись депонирована в ВИНИТИ 30.11.1998, №3510-В98. - 23 с.

7. Ильин A.B. РЕСУРС-комплекс: программные средства и математическое обеспечение ресурсного обоснования решений (экспериментальная версия РЕСУРС-Э1.96). Препринт ИПИ РАН, 1996. - 28 с.

8. Ильин A.B., Ильин В.Д. Архитектура вычислительного ядра комплекса программных средств ресурсного обоснования решений. Препринт ИПИ РАН, 1995.-24 с.

9. Ильин A.B. Взаимодействие с пользователем в процессе ресурсного обоснования решений // Сборник материалов МНК «Пользовательский интерфейс в современных компьютерных системах». Орёл, Россия, 2-4 ноября 1999. С. 42-51.

10. Ильин В.Д Основания ситуационной информатизации. М.: Наука, 1996. - 180 с.

11. Ильин В.Д. Система порождения программ. -М.: Наука, 1989. 264 с.

12. Канторович Л.В. Математические методы организации и планирования производства. Л.: Изд-во ЛГУ, 1939. - 67 с.

13. Канторович Л.В., Горстко А.Б. Математическое оптимальное программирование в экономике. М.: Знание, 1968. - 96 с.

14. Карманов ВТ. Математическое программирование. М.: Наука, 1986.

15. Ланге О. Оптимальные решения. -М. : Прогресс, 1967.

16. МинуМ. Математическое программирование. Теория и алгоритмы. -М. : Наука, 1990.

17. Михалевич B.C., КуксаЛ.И. Методы последовательной оптимизации. -М. : Наука, 1983.-208 с.

18. Моисеев КН., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. -М.: Наука, 1978.-352 с.

19. Новикова Н.М. Основы оптимизации. Курс лекций в МГУ. Вычислительный Центр РАН, 1999. - httn://www.cs.ru/depart/malashen/53kmsu.htm

20. ПервозванскийА.А. Математические модели в управлении производством. -М. : Наука, 1975.-616 с.

21. Тихонов A.M., Карманов В.Г., Руднева Т.Л. Об устойчивости задач линейного профаммирования. // Сборник «Вычислительная математика и программирование», XII. Изд-во МГУ, 1969.

22. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1979.-288с.

23. Фомин Т.П. Методы и модели линейного программирования в коммерческой деятельности. М.: Финансы и статистика, 2000. 128 с.

24. Dantzig G. Programming of interdependent activities. Mathematical model. // Econometrica, 17 (1949). P. 200-211.

25. FiaccoA., McCormickG. Sequential miconstrained minimization techniques. Wiley, 1968.

26. Fourer R Linear Programming Frequently Asked Questions. Optimization Technology Center at Argonne National Labaratory and Northwestern University, 2001.http://www-iiiiix.mcs.anl.gov/otc/Gnide/faa/linear-nrogrammmg-faq.html

27. GreenbergH. Mathematical Programming Glossary. University of Colorado at

28. Denver, 2000. — httB://carboii.cudenver.edu/~hgreenbe/glossarv/glossarv.html

29. Karmarkar N. A new polynomial-time algorithm for linear programming. // Combinatorica, 4 (1984). P. 373-395.

30. Mittelmann H., Spellucci P. Decision Tree for Optimization Software. Department of Mathematics, Arizona State University, 2001. - httii://piato.ia.asu.edu/guide.htmi1. Литература99

31. Miyano S., Shiraichi S., Shoudai T. A List of P-Complete Problems. Kyushu University,1996. — http://www.i. kyushu-u.ac.jp/~seki/P-CQmplete/alI/all.html

32. Nemhauser G., WolseyL. Integer and Combinatorial Optimization. Wiley, 1988. - 770p.

33. WilsonM., BorningA. Hierarchical Constraint Logic Programming. The Journal of Logic Programming, special issue on Constraint Logic Programming, Vol. 16 Nos. 3 & 4, July-August 1993. - P. 227-318.

34. Interior-Point Methods. Optimization Technology Center at Argonne National Labaratory and Northwestern University, 1996.http://www-fp.incs.aul.goy/otc/6iiide/OptWeb/continuous/constrained/liiiearDrog/sectioM2 1 l.html

35. Network Programming. Optimization Technology Center at Argonne National Labaratory and Northwestern University, 1996.http://www-fp.mcs.anl.goy/otc/Guide/OptWeb/continuous/constrained/network/index.html

36. Stochastic Programming. Optimization Technology Center at Argonne National Labaratory and Northwestern University, 1996.http://www-fp.incs.anLgov/otc/Guide/OptWeb/continuous/constrained/stochastic/index.htnil

37. SAS/OR User's Guide: Mathematical Programming. SAS Institute Inc., 1999.http://www.phtd.tpu.ru:8100/sashtml/ormp/index.htm