Как найти оптимальный путь с помощью линейного программирования?

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

Линейное программирование — метод оптимизации конкретного сценария, который позволяет найти наилучшие значения переменных с учётом определённых ограничений. 1

Чтобы решить задачу линейного программирования, нужно выполнить следующие шаги: 1

1. Отметить переменные решения в задаче. 1
2. Построить целевую функцию задачи и проверить, нужно ли её минимизировать или максимизировать. 1
3. Записать все ограничения линейных задач. 1
4. Обеспечить неотрицательные ограничения переменных решения. 1
5. Решить задачу линейного программирования одним из методов, например симплексным или графическим. 1

Графический метод основан на геометрическом представлении допустимых решений и целевой функции задачи. 2 Он применяется для задач линейного программирования с двумя переменными, когда ограничения выражены неравенствами, и задач со многими переменными, если в их канонической записи содержится не более двух свободных переменных. 2

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