20.2 Базисное распределение в транспортной задаче

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

Существует несколько способов его составления.

СПОСОБ СЕВЕРО-ЗАПОДНОГО УГЛА

Чтобы воспользоваться этим способом, необходимо заполнить таблицу, начиная от левого верхнего угла и кончая нижним правым углом.

Посмотрим, как это делается, на примере.

Условия задачи представлены в таблице.

Поставщики и их мощность		Потребители и их спрос
		D1	D2	D3	D4
		45	55	51	49
S1	20	10	1	2	8
S2	30	8	3	1	1
S3	40	6	5	6	4
S4	50	4	7	9	6
S5	60	3	4	2	8

Начинаем заполнять таблицу с клетки S₁ -D₁(20).

Поставщики и их мощность		Потребители и их спрос
		D1	D2	D3	D4
		45	55	51	49
S1	20	20
S2	30	25	5
S3	40		40
S4	50		10	40
S5	60			11	49

Затем последовательность заполнения выглядит следующим образом:

S₁ - D₁ (25); S₂ – D₂ (5); S₃ – D₂ (40); S₄ – D₂ (10); S₄ – D₂ (10); S₄ – D₃ (40);

S₅ –D₃(11);S₅ –D₄(49).

Проверьте себя.

Перепишите в тетрадь условия задачи и составьте первый опорный план табличным способом.

Вариант 1

	D1	D2	D3	D4	Мощность
S1	2	7	7	8	40
S2	1	9	2	3	50
S3	4	8	4	5	40
S4	2	6	3	2	50
Спрос	50	10	100	20	180

Вариант 2

	D1	D2	D3	D4	Мощность
S1	6	6	3	8	90
S2	3	9	4	3	60
S3	5	4	7	2	150
S4	2	7	5	4	20
Спрос	100	60	80	30	270

Вариант3

	D1	D2	D3	D4	Мощность
S1	7	10	2	7	20
S2	8	9	5	5	70
S3	5	3	7	2	30
S4	6	4	4	3	80
Спрос	50	60	50	40	200

Вариант 4

	D1	D2	D3	D4	Мощность
S1	3	2	4	7	40
S2	2	5	3	8	60
S3	5	7	9	5	40
S4	7	4	10	6	80
Спрос	70	60	70	20	220

СПОСОБ НАИМЕНЬШЕГО ЭЛЕМЕНТА В СТОЛБЦЕ (СТРОКЕ)

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

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

Обратите внимание:

Если в столбце (строке) два или несколько одинаковых по величине показателей c_{t j}, то для составления плана перевозки может быть взят любой из них.

В качестве примера заполним (построчно) методом наименьшего элемента таблицу с предыдущего примера. Заполнение начинаем с клетки S₅- D₁ (45).

Поставщики и их мощность		Потребители и их спрос
		D1	D2	D3	D4
		45	55	51	49
S1	20		20
S2	30		30
S3	40			40
S4	50			1	49
S5	60	45	5	10

Затем последовательность заполнения выглядит следующим образом:

S₁ – D₂ (20); S₂ – D₂ (30); S₅ – D₂ (5); S₅ – D₃ (10); S₃-D₃ (40); S₄ – D₃ (1); S₄ – D₄ (49).

Проверь себя.

Перепишите в тетрадь условия задачи и составьте опорный план способом наименьшего элемента в столбце (строке).