Каталог решений - Решение транспортной задачи запросом

Вступление (лирическое)

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

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

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

Дисклеймер

Собственно, написать эту статью мне было гораздо тяжелее, чем снова придумать то самое решение. От успешно решенной интересной проблемы я получил удовлетворение, а от статьи… Именно поэтому написание текста было отложено на месяц, чтобы собраться с мыслями, а потом еще в течение нескольких месяцев усилием воли приходилось заставлять себя заниматься ее проработкой. Так прошло более полугода.

То, что вышло — это труд, который, тем не менее, ни на что не претендует. А данная публикация является реализацией моего желания сделать “вклад в общее дело”. Какой он вышел, таким и останется.

И второе. Предложенное решение не решает транспортную задачу в ее классической постановке (мы не найдем таким образом оптимальное решение), так как рассматриваем лишь частный случай. Но, все же, полученный результат будет близок или повторять опорный план, найденный методом “северо-западного угла”.