Контрольная работа: Постановка и основные свойства транспортной задачи

Рис. 4. а)

5 6 11 7 8

1 1

9 1 1

2 1

10 1 1 1

3 1

4 1

Рис. 4. б)

Нахождение начальных опорных планов

Существует несколько методов построения начальных опорных планов Т-задачи. Из них самый распространенный метод северо-западного угла и метод минимального элемента.

Метод северо-западного угла. Основную идею метода рассмотрим на конкретном примере.

Пусть дана Т-задача с четырьмя пунктами производства А₁ , А₂ , А₃ , А₄ с объемами производства и пунктами потребления с объемами потребления соответственно .

Построим матрицу Х размером 4х4, причем для удобства вычислений снизу от нее оставим строку b_j , справа столбец a_i . Кроме того, снизу от b_j образуем строки , где будем записывать неудовлетворенные потребности, а справа от a_i – столбцы , где будем записывать остатки невывезенного продукта (табл. 2).

Заполнение таблицы начинают с левого верхнего элемента таблицы X – x₁₁ , что и обусловило название метода. Сравнив с и выбрав меньшее из них, получим x₁₁ =1. Записываем это значение в матрицу Х₀ . Так как первый выбор произведен по строке, то остальная часть первой строки должна быть заполнена нулями. Во вспомогательном столбце записываем остатки невывезенного продукта, , а в строке – неудовлетворенные потребности после одного шага заполнения.

Переходим к второй строке и начинаем заполнение с элемента (новый северо-западный угол незаполненной части таблицы 2). Сравнивая выбираем меньшее из них, и потому . Остальную часть второй строки заполняем нулями. Далее заполняем таблицу аналогично. После окончания процесса заполнения будем иметь начальный план Х₀ . Полученный план является базисным (опорным), так как из его ненулевых элементов нельзя составить цикл. Кроме того, он удовлетворяет условиям задачи, так как

.

Таблица 2

Х
	1	0	0	0	1	0	0	0	0	0	0
	2	0	0	0	2	2	0	0	0	0	0
	2	1	0	0	3	3	3	1	0	0	0
	0	0	2	2	4	4	4	4	4	2	0
	5	1	2	2
	4	1	2	2
	0	1	2	2
	0	0	2	2
	0	0	0	2
	0	0	0	0

Формальное описание алгоритма. I. Определяют верхний левый элемент матрицы Х :

.

Возможные три случая: а) если то и всю первую строку, начиная со второго элемента, заполняют нулями; б) если , то , а все оставшиеся элементы первого столбца заполняют нулями; в) если

то

и все оставшиеся элементы первых столбцов и строки заполняют нулями.

Находим

на этом один шаг метода заканчивается.

2. Пусть уже проделано k шагов. (k+1) – й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это будет элемент

причем

, (1.27)

где