11. Распределительный метод решения транспортной задачи. Вычисление максимально допустимой циркуляции.

Построим цикл , который образует клетка (i_*,j_*) с базисными клетками таблицы, и разметим его знаками «+» и «-». Изменим объем поставки от i_* -го поставщика к j_*-му потребителю на величину циркуляции Θ>0 и рассмотрим изменения, произошедшие в клетках цикла , обозначив через измененные объемы поставок:

Формулы (1) отражают простой факт: циркуляция добавляется в клетках, помеченных знаком «+», и вычитается в клетках, помеченных знаком «-».

Уменьшение транспортных затрат прямо пропорционально циркуляции Θ и составляет величину , т.е. чем больше циркуляция, тем меньше затраты. Однако циркуляция не может быть скол угодно большой, поскольку объемы поставок не могут быть отрицательными. Действительно, в клетках цикла, помеченных знаком «-», объемы поставок уменьшаются на величину циркуляции. При больших Θ все они могут стать отрицательными. Чтобы этого не произошло, рассчитаем максимально допустимую циркуляцию.

Так как отрицательные объемы могут появиться только в клетках, помеченных знаком «-», то в силу (3) максимально допустимая циркуляция не может быть больше минимального объема поставки в этих клетках. Обозначим максимально допустимую циркуляцию через Θ⁰. Тогда .

Таким образом, для вычисления максимально допустимой циркуляции необходимо найти минимальное из чисел x_ij, находящихся в клетках цикла, помеченных знаком «-».

12. Метод потенциалов решения транспортной задачи.

С каждой i-ой строкой транспортной таблицы свяжем величину U_i, которую будем называть потенциалом строки. Аналогично с каждым столбцом свяжем величину V_j. Для нахождения потенциалов составим систему линейных алгебраических уравнений:

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

Поэтому суть метода потенциалов можно выразить двумя пунктами: для проверки условий оптимальности базисного плана перевозок

1) решаем систему;

2) находим оценки по формуле

Общая схема решения транспортной задачи не изменяется, остается такой же, как и распределительном методе

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

13. Задача целочисленного линейного программирования: постановка, подходы к разработке методов.

Подходы:

1) Метод ветвей и границ

2) Метод отсечения основан на том, что вначале требование целочисленности отбрасывается, а затем вводятся дополнительные ограничения