Решение транспортной задачи распределительным методом

Для решения задачи воспользуемся исходным базисным решением, полученным методом северо-западного угла (см. табл. 2.7).

1. Строим цикл пересчета и подсчитываем АСС для каждой свободной клетки.

(1,3) АСС=9-7+13-22=-7.

(1,4) АСС=16-4+13-22=3.

(1.5) АСС=13-8+12-4+13-22=4.

(2,1) АСС=5-20+22-13=-6.

(2,5) АСС=10-8+12-4=10.

(3,1) АСС=13-8+12-4+13-22=4.

(3,2) АСС=18-13+4-12=-3.

(3,3) АСС=15-74-12=0.

Есть три клетки с отрицательными АСС. Решение не оптимальное.

2. Выбираем свободную неизвестную, то есть клетку с максимальной отрицательной алгебраической суммой стоимостей: (1,3).

3. В вершинах ее цикла пересчета базисные неизвестные имеют следующие значения

Минимальное значение в отрицательной вершине равно 30. В клетки со знаком + прибавляем 30, со знаком минус – отнимаем 30. Получим:

Количество базисных неизвестных не может измениться. Поэтому клетка (2.3) остается базисной со значением неизвестной равной нолю.

Новая матрица перевозок примет вид (табл.2.9).

Таблица 2.9

Базы	Потребители	Запасы
B1	B2	B3	B4	B5
A1
A2
A3
Потребности

Подсчитаем АСС свободных клеток.

(1,2): 22-9+7-13=7;

(1,4): 16-4+7-9=10;

(1.5): 13-8+12-4+7-9=11;

(2.1): 5-20+9-7=-13;

(2.5): 10-8+12-4=10;

(3.1): 30-20+9-7+4-12=4;

(3.2): 18-13+4-12=-3;

(3.3): 15-7+4-12=0.

Решение не оптимальное. Надо преобразовать неизвестную (2.1). В ее цикле пересчета надо сдвигать на значение неизвестной в клетке (2.3), т.е. на ноль. Получаем новую матрицу перевозок (табл.2.10).

Таблица 2.10

Базы	Потребители	Запасы
B1	B2	B3	B4	B5
A1
A2
A3
Потребности

Подсчитаем АСС свободных клеток:

(1.2): 22-13+5-20 = -6;

(1.4): 16-4+5-20 = -3;

(1.5): 13-8+12-4+5-20 = -2;

(2.3): 7-5+20-9 = 13;

(2.5): 10-8+12-4 = 10;

(3.1): 30-5+4-12 = 17;

(3.2): 18-13+4-12 = -3;

(3.3): 15-9+20-5+4-12 =13.

Решение не оптимальное.

Составим цикл пересчета для клетки (1.2). Получим новое решение (табл.2.11).

Таблица 2.11

Базы	Потребители	Запасы
B1	B2	B3	B4	B5
A1
A2
A3
Потребности

Подсчитаем АСС таблицы 2.11:

(1.1): 20-22+13-5=6;

(1.4): 16-4+13-22=3;

(1.5): 13-8+12-4+13-22=4;

(2.3): 7-13+22-9=7;

(2.5): 10-8+12-4=10;

(3.1): 30-5+4-12=17;

(3.2): 18-13+4-12=-3;

(3.3): 15-9+22-13+4-12=7.

Существует одно значение АСС<0 для клетки (3.2). Составим для нее цикл пересчета. Новое решение имеет вид:

Таблица 2.12

Базы	Потребители	Запасы
B1	B2	B3	B4	B5
A1
A2
A3
Потребности

Подсчитаем АСС для таблицы 2.12:

(1.1): 20-22+13-5=6;

(1.4): 16-4+13-22=3;

(1.5): 13-8+18-22=1;

(2.3): 7-13+22-9=7;

(2.5): 10-8+12-4=10;

(3.1): 30-5+13-18=20;

(3.2): 15-18+22-9=10;

(3.3): 12-18+13-4=3.

АСС всех свободных клеток неотрицательны. Следовательно, получено оптимальное решение. Подсчитаем стоимость перевозок:

руб.

По сравнению с исходным планом (табл.2.7), получена экономия за счет оптимизации на рублей.

Ответ: Оптимальный план дан таблицей 2.12. Стоимость перевозок рублей. Получена экономия 390 рублей.