Нахождение первоначального базисного распределения поставок

Одним из возможных методов нахождения первоначального базисного распределения поставок является метод «северо-западного» угла.

Алгоритм метода северо-западного угла:

1. Пользуясь таблицей распределяют груз, начиная с левой верхней, условно называемой северо-западной, клетки (1,1). Необходимо удовлетворить потребности В₁ за счет поставщика А₁;

2. а). Если b₁>a₁, в клетку (1,1) записывают a₁ и строку 1 вычеркивают из рассмотрения;

b). Если a₁>b₁, в клетку (1,1) записывают b₁ и столбец 1 вычеркивают из рассмотрения;

3. а). Если b₁>a₁, ∆= b₁ - a₁ – неудовлетворенные потребности. Спускаются на клетку вниз и сравнивают ∆ с a₂;

b). Если a₁>b₁, ∆=a₁ - b₁ – не вывезенные запасы. Двигаются по строке вправо и сравнивают ∆ с b₂;

4. Необходимо вернуться к пункту 2;

5. Рассчитываются транспортные расходы.

Существенный недостаток метода «северо-западного» угла состоит в том, что он построен без учета значений коэффициентов затрат. С другой стороны, данный метод допускает модификацию, лишенную этого недостатка: на каждом шаге максимально возможную поставку следует давать не в «северо-западную» клетку, а в клетку с наименьшим коэффициентом затрат. При этом распределение поставок оказывается ближе к оптимуму, чем то, которое получено по методу «северо-западного» угла. Такой метод получения опорного плана называется методом минимального элемента.

Алгоритм метода минимального элемента.

1. Из распределительной таблицы выбирают наименьшую стоимость и в клетку, которая ей соответствует, помещают меньшее из чисел a_i или b_j (если таких клеток несколько, то выбирают любую);

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

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

4. Рассчитывают транспортные расходы: сумма произведений количества перевезенной продукции на стоимость для занятых клеток.

Метод потенциалов

Алгоритм решения транспортной задачи по методу потенциалов сводится к следующему:

1. проверяется тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой;

2. находится опорный план перевозок путем составления 1-й таблицы одним из способов - северо-западного угла или наименьшей стоимости;

3. проверяем план (таблицу) на удовлетворение системе уравнений и на невырожденность; в случае вырождения плана добавляем условно заполненные клетки с помощью « 0 »;

4. для опорного плана определяются потенциалы u_i и v_j, соответствующие базисным клеткам, по условию:

u_i + v_j = c_ij

Таких уравнений будет m + n - 1 , а переменных будет m + n. Для их определения одну из переменных полагают равной любому постоянному значению. Обычно принимают u₁ = 0.

После этого для небазисных (свободных) клеток опорного плана определяются оценки Δ_ij,

где

При этом если оценки всех свободных клеток отрицательны, то опорный план оптимален, если же среди Δ_ij окажется хотя бы один положительный элемент, то опорный план можно улучшить.

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

Циклом транспортной таблицы называется последовательное соединение замкнутой ломаной линией некоторых клеток, расположенных в одном ряду (строке, столбце), причем число клеток в одном ряду должно быть равно двум.

Каждый цикл имеет четное число вершин, одна из которых в клетке с небазисной переменной, другие вершины в клетках с базисными переменными. Клетки отмечаются знаком «+», если перевозки в данной клетке увеличиваются и знаком «–» в противном случае. Цикл начинается и заканчивается на выбранной небазисной переменной и отмечается знаком «+». Далее знаки чередуются.

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

Цена цикла – это стоимость перевозки единицы продукта по циклу с учетом знаков вершин.

Улучшение опорного плана осуществляется путем нахождения цикла с отрицательной ценой.

5. Если критерий оптимальности не выполняется, то переходим к следующему шагу. Для этого:

а) в качестве начальной небазисной переменной принимается та, у которой оценка имеет максимальное значение;

б) составляется цикл пересчета;

в) находится число перерасчета по циклу: число X=min{X_ij}, где X_ij - числа в заполненных клетках со знаком « - »;

г) составляется новая таблица, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла;

6. Возвращаются к пункту 3 и т.д.

7. Если среди оценок клеток последнего оптимального распределения есть хотя бы одна нулевая для свободной клетки, то оптимальное распределение поставок не является единственным.

Для полученного оптимального распределения вычисляют суммарные затраты на перевозки как сумму произведений затрат на соответствующие поставки.

Динамическое программирование