2. Транспортная задача и методы ее решения

Рассмотрим следующий пример транспортной задачи.

Три хлебобулочных комбината поставляют продукцию в 4 населенных пункта. Производственные мощности каждого из комбинатов составляют 6 тонн, 8 тонн и 10 тонн хлебобулочных изделий в сутки. Суточный спрос для каждого населенного пункта составляет 4 тонны, 6 тонн, 8 тонн и 6 тонн. Стоимость затрат на перевозку 1 тонны хлебобулочных изделий от хлебобулочных комбинатов до населенных пунктов указаны в таблице 6 (тыс. руб.):

Таблица 6 Стоимость затрат на перевозку 1 тонны хлебобулочных изделий

Хлебокомбинаты	Населенные пункты
	1	2	3	4
1	4	5	3	7
2	8	7	5	4
3	9	3	4	5

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

Требуется:

1. составить математическую модель задачи;

2. найти начальное опорное решение методом «северо–западного угла»;

3. найти оптимальное решение методом потенциалов.

Решение

Составим математическую модель транспортной задачи.

Обозначим через x_ij объем хлебобулочных изделий, перевозимых из i – го хлебокомбината в j – й населенный пункт. Величины x_ij называются перевозками. Совокупность чисел x_ij называется планом перевозок.

При составлении системы ограничений будем исходить из следующих предположений:

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

2. суточный спрос для каждого потребителя должен быть полностью удовлетворён.

Математическая модель транспортной задачи, в которой справедливы эти предположения, называется закрытой. В контрольных заданиях рассматриваются закрытые модели транспортной задачи.

Математическая модель транспортной задачи имеет следующий вид:

Целевая функция и ограничения являются линейными функциями, поэтому транспортная задача является задачей линейного программирования.

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

Исходные данные транспортной задачи удобно записывать в виде транспортной таблицы. В первой строке укажем номера населенных пунктов, в первом столбце номера хлебозаводов. В углах клеток транспортной таблицы записаны стоимости перевозок 1 тонны хлебобулочных изделий (иначе эти числа называются тарифами). Клетки транспортной таблицы можно обозначить как (i, j), где i – номер строки транспортной таблицы; j – номер столбца транспортной таблицы.

Таблица 7 Транспортная таблица

Хлебокомбинаты	Населенные пункты								Предложение
	1		2		3		4
1	4		5		3		7		6
2	8		7		5		4		8
3	9		3		4		5		10
Спрос	4		6		8		6

Транспортная задача называется допустимой, если она имеет хотя бы один план перевозок. Условие допустимости формулируется в следующем виде: суммарный объем предложения должен быть равен суммарному объему спроса. Если транспортная задача допустима, то для нее существует оптимальное решение (оптимальный план перевозок).

Проверим условие допустимости для транспортной задачи: 6+8+10=24; 4+6+8+6=24.

Данная транспортная задача допустима, поэтому имеет оптимальное решение.

Отметим некоторые свойства транспортной задачи.

1. Ранг матрицы транспортной задачи на единицу меньше числа уравнений, т.е. равен m+n-1. Это означает, что в любом опорном решении транспортной задачи число положительных чисел меньше или равно m+n-1.

2. Если все числа a_i, b_j – целые, то в любом опорном решении транспортной задачи объемы перевозок являются целыми числами.

Определим начальное опорное решение методом «северо-западного» угла. Транспортную таблицу начинаем заполнять с левого верхнего (северо-западного) угла.

Завезём максимальный объем продукции из 1 хлебокомбината в 1 населенный пункт. Так как объем предложения 1 хлебокомбината равен 6, а спрос в продукции для первого населенного пункта равен 4, то максимальный объем перевозки равен 4 тонн: min (6, 4)=4.

В результате спрос на продукцию для первого населенного пункта удовлетворен. Первый столбец полностью заполнен.

В оставшейся части таблицы находим верхнюю левую или «северо-западную» клетку и помещаем в нее максимально возможный объем перевозки.

«Северо-западной» клеткой будет клетка (1, 2). Максимально возможный объем перевозки будет равен min(6-4, 6)=2. С первого хлебокомбината во второй населенный пункт надо привезти 2 тонны продукции. Вся продукция первого хлебокомбината полностью реализована. Первая строка заполнена полностью.

В оставшейся части таблицы северо-западной клеткой будет клетка (2,2). Максимально возможный объем перевозки равен min(8, 6-2)=4. Спрос на продукцию для второго населенного пункта удовлетворен. Второй столбец полностью заполнен.

Заполняем клетку (2,3). Максимально возможный объем перевозки равен min(8-4, 8)=4. Вся продукция второго хлебокомбината полностью реализована. Вторая строка заполнена полностью

В клетки (3, 4) и (3, 4) записываем нераспределенные объемы продукции: 4 и 6 тонн. План перевозок показан в таблице 8.

Таблица 8 – План перевозок, найденный методом «северо-западного угла»

	1		2		3		4		Предложение
1	4	4	5	2	3	0	7	0	6
2	8	0	7	4	5	4	4	0	8
3	9	0	3	0	4	4	5	6	10
Спрос	4		6		8		6

Транспортные затраты для данного плана перевозок равны 120 тыс. руб.

Справедлива следующая теорема.

Теорема. План перевозок, построенный по методу «северо-западного угла», является опорным решением.

Из этого утверждения следует, что число положительных чисел плана перевозок, найденного по методу «северо-западного угла» не превышает ранга матрицы транспортной задачи. Для нашего примера число положительных чисел равно 6, а ранг матрицы транспортной задачи также равен 6.

Итак, идея метода «северо-западного угла» состоит в последовательном заполнении матрицы, соответствующей искомому опорному решению, элементами, начиная с левого верхнего (северо-западного) элемента незаполненной к текущему шагу матрицы. При этом на каждом шаге заполняется либо строка матрицы, либо ее столбец, причем все элементы заполняемой строки (соответственно, столбца), начиная со следующего за вычисленным на текущем шаге метода элементом, – нулевые.

Определим, является ли найденное опорное решение, невырожденным.

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

Если любое опорное решение транспортной задачи невырожденное, то транспортная задача называется невырожденной.

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

Если транспортная задача имеет хотя бы одно вырожденное опорное решение, то она называется вырожденной.

Полученное опорное решение является невырожденным, так число занятых клеток равно 6, а ранг матрицы транспортной задачи также равен 6 (3+4-1=6).

Если транспортная задача является вырожденной, то в число базисных переменных вводим необходимое количество свободных переменных, которым соответствуют нулевые поставки. Соответствующие клетки считаются занятыми.

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

Метод потенциалов основывается на следующей теореме.

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

1. 

2. если , то

n – число пунктов производства;

m – число пунктов потребления.

Опираясь на эту теорему любому опорному решению транспортной задачи ставятся в соответствие так называемые потенциалы пунктов производства и потребления. Эти потенциалы выбираются так, чтобы их сумма значений для любой пары пунктов, один из которых является пунктом производства, а другой – пунктом потребления, и между которыми в соответствии с опорным решением перевозится ненулевое количество продукта, была равна стоимости транспортных расходов на перевозку между этими пунктами единицы продукта. Если суммы потенциалов между всеми парами пунктов не превосходят транспортных затрат на перевозку между ними единицы продукта, то опорное решение является оптимальным решением исходной задачи. В противном случае по специальным правилам осуществляется переход к другому опорному решению, реализуемому с меньшими транспортными расходами. Через конечное число шагов находится оптимальное решение транспортной задачи.

Исследуем опорное решение транспортной задачи на оптимальность, используя метод потенциалов.

Введем семь переменных, которые называются потенциалами пунктов производства и пунктов потребления: - потенциалы пунктов производства (хлебозаводов); - потенциалы пунктов потребления (населенных пунктов).

Найдем значения потенциалов, исходя из условия: суммы потенциалов для заполненных клеток равны тарифам.

Получим следующую систему уравнений:

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

Пусть Тогда остальные значения потенциалов будут равны:

Оценкой клетки транспортной таблицы называется значение следующего выражения:

Если опорное решение является оптимальным, то согласно теореме все оценки должны быть неположительными:

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

Проверим условие оптимальности. Вычислим оценки для свободных клеток.

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

Справедлива следующая теорема.

Теорема. В опорном решении для каждой свободной клетки транспортной таблицы существует цикл, и притом единственный, удовлетворяющий перечисленным условиям.

В таблице 9 показан цикл для клетки (3, 2).

Таблица 9 – Нахождение оптимального решения методом потенциалов

	1		2		3		4		Предложение
1	4	4	5	 2	3	0	7	0	6
2	8	0	7	4	5 +	4	4	0	8
3	9	0	3 + *	0	4 	4	5	6	10
Спрос	4		6		8		6

Определим, какое положительное число необходимо ввести в перспективную клетку. Обозначим это значение через y. Пересчитаем объемы перевозок в вершинах цикла. Для того чтобы сумма по второму столбцу не изменилась, необходимо из 4 вычесть y. Для того чтобы сумма по второй строке не изменилась, необходимо к 4 прибавить y. Аналогично из объема перевозки клетки (3, 3) необходимо вычесть y: 4- y. Объемы перевозок должны быть неотрицательными. В итоге получаем следующую систему неравенств:

Решение этой системы линейных неравенств следующее: . В опорном решении число положительных чисел должно быть не более 6. Поэтому значение переменной y должно быть равно 4.

В дальнейшем эти рассуждения можно опускать и расчет в вершинах цикла можно делать быстрее по следующим правилам.

Перспективную клетку обозначим знаком «+». Следующие вершины цикла обозначим по очереди знаками «» и «+». Обходить цикл можно по часовой стрелке или против часовой стрелки. Иначе говоря, вершины цикла с четными номерами мы обозначаем символом «», а нечетные символом «+». Второе и третье неравенства системы соответствуют вершинам цикла, имеющими символ «», поэтому определим наименьшее число, которое находится в вершинах с символом «»: 4. Это значение помещаем в перспективную клетку. Рассчитываем остальные значения в вершинах цикла. Где знак «» у вершины, вычитаем 4, где знак «+» прибавляем 4: 4-4=0, 4+4=8, 4-4=0.

Получаем новое опорное решение, которое записано в таблице 10. Транспортные затраты для нового опорного решения равны 108 тыс. руб.

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

Таблица 10 – Нахождение оптимального решения методом потенциалов

	1		2		3		4		Предложение
1	4	4	5		3	0	7	0	6
			2
2	8	0	7		5	8	4	0	8
			0
3	9	0	3		4	0	5	6	10
			4
Спрос	4		6		8		6

Клетку необходимо выбрать так, чтобы система потенциалов была разрешена. Клетка (2, 3) находится на пересечении второй строки и третьего столбца. Кроме клетки (2, 3), в этих строках и столбцах нет ни одной заполненной клетки. Поэтому введем в число занятых клеток одну из свободных клеток, находящуюся во второй строке или в третьем столбце. Выбираем свободную клетку (1, 3) и вводим ее в число занятых клеток.

В результате опорное решение является невырожденным и можно применить метод потенциалов.

Составляем систему уравнений:

Находим одно из решений системы:

Проверяем условие оптимальности. Находим оценки для свободных клеток:

Есть положительная оценка, поэтому опорное решение не является оптимальным. Клетка (2, 4) – перспективная. Строим для этой клетки цикл перевозок по указанным выше правилам. Расставляем знаки «+» и «» в вершинах цикла. Определяем наименьшее число в вершинах цикла: 2. Построенный цикл показан в таблице 10.

Пересчитываем значения в вершинах цикла. Получаем новое опорное решение, которое записано в таблице 11.

Таблица 11 – Метод потенциалов решения транспортной задачи

	1		2		3		4		Предложение
1	4	4	5	0	3	2	7	0	6
2	8	0	7	0	5	6	4	2	8
								2
3	9	0	3	6	4	0	5	4	10
								4
Спрос	4		6		8		6

Транспортные затраты для данного плана перевозок равны 98 тыс. руб. Опорное решение не является оптимальным. Опорное решение является невырожденным. Применяем метод потенциалов. Вычисляем оценки для свободных клеток. Условие оптимальности не выполняется. Переходим к новому невырожденному опорному решению, которое записано в таблице 12. Условие оптимальности для данного опорного решения справедливо.

Таблица 12 – Оптимальное решение транспортной задачи

	1		2		3		4		Предложение
1	4	4	5	0	3	2	7	0	6
2	8	0	7	0	5	2	4	6	8
3	9	0	3	6	4	4	5	0	10
Спрос	4		6		8		6

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

Подведем итог.

Оптимальное решение будет следующим:

Минимальные транспортные затраты равны 90 тыс. руб.