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

Потребители

Потребности

Для решения задачи воспользуемся исходным базисным решением, полученным методом северо-западного угла (см. табл. 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

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

(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

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

(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

Подсчитаем АСС таблицы 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

Подсчитаем АСС для таблицы 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 рублей.