Jumpow писал(а):
Замечвние: Алгоритм Романовского, приведенный в книге, является одной из первых реализаций метода потенциалов и оо-очень неэффективен.
Сужествуют реализации в сотни раз более быстрые
Я указал на книгу Романовского "
Алгоритмы решения экстремальных задач". Значить, я и должен ответить.
Междувременно, книга уже находится на полках этой билиотеки
http://lib.mexmat.ru/books/14564
Каждый, у кого доступ, может сам ее перелистать и составит свое собственное непредубежденное мнение.
Когда прочел просьбу о помощи во Форуме библиотеки нашего факультета, я допустил, что проситель учиться и поэтому должен составлять программу. Не собирается разрабатывать "производственный" живой проект. Иначе, задача врядь ли ставилась бы в матричной постановке, а скорее всего --- в сетевой. Позднее это потвердилось --- человек писал, что "горить" его курсовая работа.
У меня под рукой был выбор из short-list'а книг: Гольштейн и Юдин "Задачи линейного программирования транспортного типа" (1969), или "Линейное программирование и его расширения" Дж. Дантцига (1966), или Л.М.Абрамов и В.Ф.Капустин "Математическое программирование" (1976), или "Курс математического программирования" И.Ф.Полунина.
Из этих, только в книге Романовского одновременно и кратко описывается один алгоритм, и предложена одна его реализация на АЛГОЛ-е.
По моему книга Романовского --- и доброе учебное пособие, и хороший сжатый справочник, собравших в одном месте очень много из оптимизационных задач, вместье с выбранными автором алгоритмами их решения. Взгляд с 1977-ого года.
(Между прочим, в разделе Библиографические указания (стр. 336-337) можно увидеть указание на то, что первая известная постановка транспортной задачи принадлежить советскому экономисту А.Толстому (1939). Только недавно мог подробно прочитать весьма любопитные и поучительные детали около этого. В Google выходить следующая ссылка на этот счет:
www.cwi.nl/~lex/files/histtrpclean.pdf
Когда теперь решили современными програмами задачу Толстого, оказалась, что опубликованное им еще раньше, в 1930-ом (!), решение совпадает с оптимальним).
В разделе Библиографические указания вопросной книги Романовский сам указывает, что дальнейшее совершенствование метода потенциалов проводилось, например, в работах К.В.Кима и В.И.Шмирева.
Другими словами, автор нигде и не утверждал, что вопросный алгоритм наилучший в каком-то смисле. Наоборот, он даже ссылает на более совершенные.
Думаю, при обучении, всегда можно из-за методических соображений начать не с самых развитых методов.
Вопрос о наиболее эффективном алгоритме решения транспортной задачи и/или более общей задачи линейного программирования достаточно сложен. Естествено, он не решается на уровне форумов. Многое сказано в монографиях, в статьях. Важен преследуемый критерий или критерии. Быть может, из-за, и я скажу, оо-очень больших залогов в соответствующих применениях в экономике, в военном деле и т.д., многое не сказано вообще публично. А как видно из выше упомянотой публикации by Alexander Schrijver, то бывали случаи, в которых что-то могло бы быть полярно перевернуто.
Для алгоритмов решения задач линейного программирования один краткий взгляд на эффективности можно получить например из ответа на второй вопрос в:
Linear Programming - Frequently Asked Questions List
по линку:
ftp://rtfm.mit.edu/pub/usenet/sci.answe ... amming-faq
02.09.2006, 10:33 
