Решение транспортной задачи. Составление опорного плана
ui vj 0 -1 3 14 14 15 Проверка плана на оптимальность 10 15 13 30 22 Для проверки опорного плана на оптимальность используют так называемый «метод потенциалов», по которому строке i и столбцу j транспортной таблицы ставится в соответствие числа ui и vj . Для каждой базисной переменной xij текущего решения потенциалы ui и vj должны удовлетво- рять уравнению ui + vj = cij .Эти уравнения при- водят к системе, состоящей из m + n -1 уравнений, в которых фигурируют m + n неизвестных. Значения потенциалов можно определить из этой системы, придавая одному из них произвольное значение (обычно полагают u1 =0). Итак, для клеток, в которых содержался груз, определили потенциалы, пользуясь условием: 1. ui + vj = cij Теперь надо провести оценку для небазисных переменных xpg , т.е. для клеток, в которых нет груза. Оценки для небазисных переменных xpg определяются в соответствии с соотношением: 2. ĉpg= cpg - ( ui + vj ) A1B2 : 15 – ( 14 + 0 ) = 1 A1B3 : 15 – ( 15 + 0 ) = 0 A2B2 : 16 – ( 14 - 1 ) = 3 A3B1 : 12 – ( 14 +3 ) = -5 Если в результате получатся отрицательные значения, то план считается не оптимальным, и его надо перестроить путём перераспределения продукции. Нажмите «ENTER» Улучшение опорного плана 10 15 13 30 22 Предварительно восстановим табличную запись задачи Для улучшения опорного плана в базис включается небазисная переменная, имеющая самую большую по модулю отрицательную оценку. В нашем случае это переменная x31 (клетка А3В1), для которой 2-ое условие не выполняется. Необходимо выяснить, а какую же базисную переменную нужно вывести из базиса? Для этого поступим следующим образом: точками обозначим пункты отправки и пункты назначения, пунктирной линией соединим те вершины, в клетках которых есть груз, например, А1В1 , А2В1 , и т.д. Обозначим клетку А3В1 , в которой 2-ое условие не выполняется и, начиная с одного из концов этой линии по пунктирным линиям доберёмся к другому концу. Напомним, что каждая линия соответствует определённой клетке. Отметим точками те клетки в таблице, которые соответствуют сплошным линиям, . . . . построим много- угольник соединяя эти точки последовательно. Вершинам припишем чередующие- ся знаки ( + , - ), начиная со знака (+) для вводимой в базис переменной. + + - - Затем в вершинах со знаком (-) отыщем наименьшую продукцию, которую и будем перемещать по вершинам многоугольника согласно знакам. 15 28 7 Получили новый опорный план Вычислим значение целевой функции Значение z уменьшилось. Цикл завершён. Снова надо проверить условия 1 и 2. Проследите цикл на практике. Нажмите «ENTER»