Calc - Задача коммивояжера (потратить минимум денег на посещение нескольких городов)

[Stasroot1]

Здравствуйте. Как в LibreOffice 4.3.3.2 решить задачу коммивояжера? Есть табличка со стоимостью перелетов из каждого города в каждый город. Городов 4. При этом стоимость перелета например из города 1 в город 2 составляет 100, а в обратном направлении например 140.
Вопрос: как найти самый дешевый по стоимости перелетов маршрут? При этом: Каждый город можно посетить только один раз.

Никогда задачи такого рода ни в каком офисном пакете не решал. а тут потребовалось. Подскажите как это сделать?

[SLEDopit]

Гуглить не пробовали?
Вот, например, или вот. Оно хоть и делалось для excel'я, если не заведётся, хотя бы логику можно подсмотреть.

[Stasroot1]

Да смотрел. только там, по первой ссылке рассматривается вариант с расчетеом расстояний по координатам. и в той задаче получается расстояние из города А в город Б равно в двух направлениях друг другу. У меня стоимость и она к моему удивлению совсем не одинаковая в разных направлениях. Т.е. из Москвы в Питер стоит 100 а из Питера в Москву стоит 132. Плюс по аналогии.. я задачами ни в экселеле ни в кальке не занимался.
Вторая ссылка на английском. Почитал. Там теоретические раскладки и вариации. Намного более полная инфа по сравнению с той что я находил на русском языке.

Будем разбираться...

[NickLion]

Ну, так сделайте несимметричную таблицу и разверните её в полный список дуг.

[Stasroot1]

несимметричную таблицу и разверните её в полный список дуг.

Это как?

[NickLion]

Stasroot1
Ну, как в примере №1, таблица расстояний, только заполнить таблицу нужными значенями. Т.к. путь из 1 в 2 ≠ 2 в 1, то таблица не будет симметричной. Далее, разворачиваете в таблицу дуг (в примере, 2-й скриншот), только там будут и 1 2, так и 2 1. Ну, и ограничения правильные задать.