27. Алгоритм метода потенциалов.

1)Условие записываем в виде распределительной таблицы. 2) Проверяем выполнение необходимого и достаточного условия разрешимости задачи (Задача закрытого типа). 3) Строим начальное опорное решение. (Проверяем что количество занятых клеток равно m+n-1 и убеждаемся в линейной независимости векторов). 4) Строим систему потенциалов по занятым клеткам u_i+v_j=c_ij, x_ij>0. Система имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов (большее число раз встречаемое) задают произвольное значение (чаще 0) и находим оставшиеся потенциалы. 5) Вычисляем оценки свободных членов по формуле ∆_ij=C_ij-(u_i+v_j) если ∆_ij>=0, то план оптимальный и остаётся подсчитать транспортные расходы. 6) Перейдём к новому опорному решению на котором значение целевой функции будет меньше. Строим цикл включающую данную клетку и часть клеток занятых опорным решением. В клетках цикла расставляют знаки +- чередуя, начиная с + в клетке с наибольшей положительной оценкой. Осуществляем перераспределение груза по циклу на величину Q=min{x_ij}. Если минимум достигается в нескольких клетках, то одна из них остаётся пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m+n-1. Далее переходим к пункту 4.

28. Оценка (характеристика) свободной клетки транспортной таблицы Признак оптимальности опорного плана транспортной задачи. Не единственность оптимального опорного плана.

Вычисляем оценки свободных членов по формуле ∆ij=Cij-(ui+vj) если ∆ij>=0, то план оптимальный и остаётся подсчитать транспортные расходы. Теорема об оптимальности решения ТЗ. Решение ТЗ будет оптимальным, если найдутся числа ui* и vj* i=1,n; j=1,m; называемые потенциалами поставщиков и потребителей удовлетворяющие следующим условиям : ui*+vj*=cij, если xij>=0 и ui*+vj*<=cij; xij=0.

Если ∆ij>0 то оптимальный план единственный, если ∆ij=0 то задача имеет множество оптимальных планов, если ∆ij<0 то выбирают клетку с наибольшей по абсолютной отрицательной оценкой и переходят к следующему пункту алгоритма.

29. Потенциалы поставщиков и потребителей. Система уравнений для определения потенциалов.

Теорема об оптимальности решения ТЗ. Решение ТЗ будет оптимальным, если найдутся числа ui* и vj* i=1,n; j=1,m; называемые потенциалами поставщиков и потребителей удовлетворяющие следующим условиям : ui*+vj*=cij, если xij>=0 и ui*+vj*<=cij; xij=0.

Если ∆ij>0 то оптимальный план единственный, если ∆ij=0 то задача имеет множество оптимальных планов, если ∆ij<0 то выбирают клетку с наибольшей по абсолютной отрицательной оценкой и переходят к следующему пункту алгоритма.

30. Связь между оценками свободных клеток и потенциалами.

Если в оптимальном плане есть свободные клетки с отрицательными оценками , то из них выбирается клетка с максимальной по модулю оценкой(перспективная) и загружается максимально возможной поставкой. Чтобы загрузить перспективную клетку, нужно составить для нее цикл. Он существует, причем единственный. Вершины его отмечаются знаками + и – поочередно, начиная с перспективной клетки. Далее выбирается наименьшая загрузка клетки, отмеченной минусом. Это число(λ) добавляется к загрузке клеток, отмеченных +, и вычитается от тех, что отмечены -. Эта процедура называется сдвиг λ по циклу. В рез-те загружается 1 клетка, и должна освободиться 1 клетка. Если освобождается больше чем 1 клетка, то свободной нужно оставить только одну, ту, у которой тариф наибольший. В остальные освобождающиеся вписать нулевую загрузку.

Теорема об оптимальности решения ТЗ. Решение ТЗ будет оптимальным, если найдутся числа ui* и vj* i=1,n; j=1,m; называемые потенциалами поставщиков и потребителей удовлетворяющие следующим условиям : ui*+vj*=cij, если xij>=0 и ui*+vj*<=cij; xij=0.

Если ∆ij>0 то оптимальный план единственный, если ∆ij=0 то задача имеет множество оптимальных планов, если ∆ij<0 то выбирают клетку с наибольшей по абсолютной отрицательной оценкой и переходят к следующему пункту алгоритма.