Методы нахождения опорного решения в транспортной задаче

[re3burn]

Здравствуйте!
Посоветуйте, пожалуйста, литературу по методам нахождения опорного решения в транспортной задаче.
Я нашел алгоритмы методов северо-западного угла, минимального элемента, аппроксимации Фогеля, двойного предпочтения, Лебедева-Тихомирова.
Встречал в литературе название "метод приоритетов ближайших пунктов", но не нашёл алгоритма (описания) этого метода. Кто знает - помогите:)
И еще такой вопрос, а есть какая-то литература, где теоретически обосновываются эти методы или эти правила являются эмпирическими.
Заранее благодарю, Алексей

[Sonic86]

re3burn в сообщении #478372 писал(а):

И еще такой вопрос, а есть какая-то литература, где теоретически обосновываются эти методы или эти правила являются эмпирическими.

Нам рассказывали, что метод северо-западного угла отфонарный, метод минимального значения - жадный алгоритм, метод аппроксимации Фогеля действительно работает еще лучше и что обоснование этому есть. Однако источников не скажу.

[Евгений Машеров]

Похоже, что "метод приоритетов ближайших пунктов" есть глубокомысленное именование метода минимального элемента.
Что до обоснований - то для каждого из них можно придумать контрпример, для которого он приведёт к чрезвычайно плохому плану. Для с.-з. угла - просто поставив на пути очень дорогой переход, для минимального элемента - поставив такой переход так, чтобы, выбрав минимальный, на следующем шаге пришлось бы брать этот дорогой и т.д., но для методов Фогеля, двойной пометки и др. контрпример сложнее, и представляется маловероятным, чтобы он встретился в реале. То есть это "эвристические алгоритмы". Доказать можно только, что они дают допустимый план, то, что он будет в каком-то смысле близок к оптимальному недоказуемо, иногда и неверно.

[Sonic86]

Евгений Машеров в сообщении #478569 писал(а):

Доказать можно только, что они дают допустимый план, то, что он будет в каком-то смысле близок к оптимальному недоказуемо

Не, ну насчет недоказуемости Вы, конечно, загнули, хотя доказать, пожалуй, довольно трудно.

[Psw]

Для метода двойного предпочтения (двойных пометок) контрпример построить примерно также просто как для метода наименьшей стоимости.

Евгений Машеров в сообщении #478569 писал(а):

Похоже, что "метод приоритетов ближайших пунктов" есть глубокомысленное именование метода минимального элемента.

А это, видимо, не так.
Нашлось вот это

Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(cij), способу Фогеля и по способу Лебедева-Тихомирова.

Вот отсюда - http://math.semestr.ru/transp/transpraspred.php
Возможно, это метод минимумов по строкам?

[Евгений Машеров]

Пытался найти описания некоторых методов. Что-то они, похоже, "широко известны в узких кругах", так что надо искать какие-то местночтимые методички.
Вообще, это была важная и исследуемая тема, когда Т.З. считалась вручную, и улучшить начальный план было экономией нескольких часов работы. По мере развития вычтехники - как-то увяло.
И что до "недоказуемости". Если к утверждению можно придумать контрпример - оно недоказуемо. То есть утверждение "метод минимального элемента всегда лучше северо-западного угла" недоказуемо, а утверждение "в среднем метод М.Э. даёт лучший план, что С.-З.У." может быть, в принципе, доказано, если ввести какой-то закон распределения матриц коэффициентов, но доказательство будет трудоёмко, а при изменении постулированного закона - неприменимо. Хотя, наверно, "экспериментально-математическая работа", с генерацией случайных матриц и сравнением разных алгоритмов на них, будет вполне достойным опусом для студента, в качестве курсового или работы на студенческий конкурс. Но это не математика, хотя и имеет отношение к её приложениям. Это другой, не-математический способ рассуждений, ближе к инженерному.

[Sonic86]

Евгений Машеров в сообщении #478973 писал(а):

утверждение "в среднем метод М.Э. даёт лучший план, что С.-З.У."

Я его и имел ввиду

(Оффтоп)

Евгений Машеров в сообщении #478973 писал(а):

То есть утверждение "метод минимального элемента всегда лучше северо-западного угла" недоказуемо, а утверждение "в среднем метод М.Э. даёт лучший план, что С.-З.У." может быть, в принципе, доказано, если ввести какой-то закон распределения матриц коэффициентов, но доказательство будет трудоёмко, а при изменении постулированного закона - неприменимо. Хотя, наверно, "экспериментально-математическая работа", с генерацией случайных матриц и сравнением разных алгоритмов на них, будет вполне достойным опусом для студента, в качестве курсового или работы на студенческий конкурс. Но это не математика, хотя и имеет отношение к её приложениям. Это другой, не-математический способ рассуждений, ближе к инженерному.

Не математический?! Странно... Наверное я что-то не понимаю.
А что понимается под "изменении постулированного закона"? Можно было бы ввести одно распределение матриц из каких-то довольно общих соображений и попытаться вывести. И по-моему было бы вполне применимо. Применяется же анализ скорости сортировок на случайных данных. Просто технически выглядит очень страшно и без навыков фиг докажешь (я когда-то пытался доказать, что жадный алгоритм для решения задач БЛП лучше, чем какой-то другой алгоритм, но не смог).
Я не докапываюсь, мне просто интересно

[Евгений Машеров]

Не-математический в том смысле, что "на данном примере алгоритм А дал лучший результат, чем В" может быть полезно - но это не доказательство, это "показ на примере".
А с сортировками - там либо худший случай смотрят, либо рассматривают все возможные перестановки и берут среднее. То есть n! вариантов, в принципе рассматриваемо. Здесь же континуум вариантов по каждому коэффициенту, и перебрать все невозможно. Можно, однако, ввести закон распределения. И рассматривать случайные матрицы стоимостей, сгенерированные в соответствии с этим законом. Но результат для каждого закона может быть иным.

[re3burn]

Спасибо за ответы. Встречал еще метод "плавающих" зон, но тоже без описания. Может кто знает его описание?