ПРОВЕРКА СОВМЕСТНОСТИ ДВУХ ПОДКЛАССОВ СИСТЕМ ЛИНЕЙНЫХ ДВУСТОРОННИХ НЕРАВЕНСТВ ТРАНСПОРТНОГО ТИПА |
4 | |
2011 |
научная статья | 519.852 | ||
200-205 | системы линейных двусторонних неравенств, проверка совместности |
Рассматриваются два подкласса систем линейных двусторонних неравенств транспортного типа,
допускающих сведение к задачам распределения ресурсов или к задачам поиска допустимой циркуля-
ции в транспортных сетях. Подобное сведение позволяет решать системы неравенств из выделенных
подклассов с вычислительной сложностью |
1 . Черников С.Н. Линейные неравенства. М.: Наука, 1968. 488 с. 2 . Encyclopedia of Optimization (Editors: Christodoulos A. Floudas and Panos M. Pardalos), Volume II, New York: Springer, 2008. 4626 p. 3 . Ye Y. An O(n3L)-potential reduction algorithm for linear programming // Mathematical Programming. 1991. P. 239-258. 4 . Зоркальцев В.И., Филатов А.Ю. Новые алгоритмы оптимизации в конусе центрального пути // Дискретный анализ и исследование операций. Cерия 2. 1999. Т. 6. №1. C. 33-42. 5 . Голиков А.И., Евтушенко Ю.Г. Новый метод решения систем линейных равенств и неравенств // Докл. РАН. 2001. Т. 381. № 4. С. 444-447. 6 . Dantzig G.B., Thapa M.N. Linear Programming. V. 2. Theory and Extensions. New York: Springer, 2003. 456 p. 7 . Прилуцкий М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры // Труды Международной конференции «Идентификация систем и задачи управления SICPRO'2000». М.: Институт проблем управления им. В. А. Трапезникова РАН, 2000. C. 2038-2049. 8 . Van Leeuwen J. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity. Amsterdam: Elsevier / Cambridge: The MIT Press, 1990. 996 p. 9 . Афраймович Л.Г., Прилуцкий М.Х. Многоин- дексные задачи распределения ресурсов в иерархи- ческих системах // Автоматика и телемеханика. 2006. № 6. С. 194-205. 10 . Карзанов А.В. Нахождение максимального потока в сети методом предпотоков // ДАН СССР. 1974. Т. 215. №1. C. 49-52. |