Транспортная задача. Линейное программирование. Часть 1

[@aminafarajieva]

Всё понятно, без воды. Благодарю за канал

[@ruchkoanna]

благодарю за обратную связь

[@mikeoxlong5100]

Спасибо за видео! А поясните пожалуйста, зачем нужно несколько методов решения если какой-то метод лучше выдал ответ? А симплекс метод, если он сюда применим, это ещё точнее?

[@ruchkoanna]

несколько методов построения начальных опорных планов? какие- просты в построении (метод северо-западных углов), какие-то более приближены к оптимальному (минимальная стоимость, либо Фогеля). В любом случае применяя метод потенциалов получим оптимальный план, просто разница в количестве шагов. Симплекс метод для ТЗ это очень муторно. Оптимальное решение получится то же (именно минимальная стоимость перевозок)

[@justmusic3038]

Скажите а что делать если нужно одновременно строку и столбец вычеркивать в методе минимального элемента?

[@ruchkoanna]

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

[@assanjuanyshbekov]

Эти методы получаются лишь приближения к оптимальному решению? Забил задачу в Excel, там получилось минимальная стоимость 956. x12=5; x13=9; x25=25; x31=40; x33=11; x35=5; x42=35; x44=10

[@mrApelsin4ikGaming]

Что очевидно - да. Есть симплекс, который в теории даст оптимальное решение для любой задачи линейного программирования (если решите задачу симплексом (или потенциалами, что по сути одно и то же), напишите, пожалуйста, получился ли ваш ответ). И есть полный перебор. Вроде как это - единственные методы, которые дадут верный оптимальный ответ. Но штука в том, что при масштабировании задачи, эти методы будут потреблять слишком большой вычислительный ресурс. В минимальном элементе и Фогеле есть погрешность и при критических значениях цена ошибки максимальна, но при нормальном распределении значений (что в реальном мире - эквивалентно словам "почти всегда"), погрешностью можно пренебречь. В северном углу погрешность равна или больше, но сложность алгоритма минимальна: O(n+m). В минимальном элементе порядок сложности такой же, но само O растет быстрее т.к. больше операций на итерацию. Так что в реальном кейсе лучше использовать либо симплекс (или полный перебор, если симплекс не работает), если есть возможность подождать, пока комп все посчитает, либо минимальный элемент, если ответ нужен здесь и сейчас или переменных слишком много.

[@ruchkoanna]

Эти методы используют для построения начального опорного плана. После этого для приведения задачи к оптимальному решению используется метод потенциалов. На канале есть видео (2 часть)

[@assanjuanyshbekov]

Спасибо за ваши ответы. Да, когда в универе спрашивают решение вручную - очень помогает. Часто метод Фогеля даёт сразу оптимальное решение, а когда не даёт - можно использовать метод потенциалов. Спасибо за видео!