Закрытая транспортная задача

Date: 2015-10-07; view: 567.

Рассмотрим задачу закрытого типа. Обозначим количество груза, перевозимого от i-го поставщика к j-му потребителю, через .

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

(1)

(2)

(3)

(4)

Первые m уравнений системы (1) соответствуют ограничениям по запасам поставщиков, последние n — ограничениям потребителей; условие неотрицательности (2) следует из экономического смысла неизвестных ; уравнение (2) означает, что транспортная задача является закрытой. Целевая функция (4) выражает суммарную стоимость перевозок.

Математически транспортная задача (1)—(4) ставится следующим образом: среди множества планов системы линейных уравнений (1), (3) и неравенств (2) найти такой план , который минимизирует целевую функцию (4).

Таким образом, транспортная задача является задачей линейного программирования и может быть решена симплекс-методом, алгоритм которого состоит из трех шагов:

1. Построение начального плана.

2. Проверка плана на оптимальность. Если план оптимален, то задача решена; в противном случае — переход к п.3.

3. Построение нового плана с меньшей (или равной) стоимостью перевозок.

Специфические особенности системы ограничений транспортной задачи привели к разработке упрощенного метода решения на каждом шаге алгоритма.

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

Требуется построить такой план перевозок, при котором суммарная стоимость будет наименьшей.

1. Построение начального плана.

Прежде всего проверим, является ли задача закрытой.

9+8+12+11=40;

12+9+11=40.

Поскольку , мы имеем дело с закрытой задачей.

Решение будем строить непосредственно в транспортной таблице 7, которая имеет вид:

Таблица 7.

Поставщики	Потребители
	b2

где a_i — мощность поставщиков, b_j — емкость потребителей, с_ij —стоимость единичной перевозки, а х_ij — количество перевозимого груза от А_i поставщика к B_j потребителю, i=1…m, j=1…n.

Начальный план составим методом наименьшей стоимости.

Из всей таблицы выбираем наименьшую стоимость единичной перевозки с_ij и в соответствующую ей клетку помещаем наименьшее из чисел и . Тогда или будет полностью исчерпан запас груза поставщика и в остальных клетках i -ой строки можно поставить прочерк, или потребности потребителя будут полностью удовлетворены и можно поставить прочерк в оставшихся клетках j-го столбца.

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

В нашем примере наименьшую стоимость перевозки с₄₂=1 имеет клетка (4;2). Потребность в грузе потребителя B₂ составляет 9, а запас груза поставщика А₄ 11 единиц. Наибольшая из возможных поставок =9 (наименьшее из чисел 11 и 9). Записываем =9 в таблицу и в оставшихся клетках второго столбца ставим прочерк, т.к. потребности B₂ будут полностью удовлетворены. У поставщика А₄ остается в запасе 2 единицы груза.

Далее заполняем клетку (4;1) с с₄₁=2. Поставку х₄₂ определим как наименьшее из чисел 12 и 2 (остаток груза А₄), х₄₂=2. Потребителю В₁ необходимо завезти еще 10 единиц груза, а возможности поставщика А₄ будут исчерпаны полностью, в клетке (4;3) ставим прочерк.

Из оставшихся клеток наименьшую стоимость имеет клетка (3;1) с с₃₁=5. Запас груза А₃ равен 12, потребность В₁ 10 единиц, следовательно х₃₁=10. Потребности В₁ удовлетворены полностью, в остальных клетках первого столбца ставим прочерки. Оставшиеся у А₃ 2 единицы поместим в (3;3), т. е. х₃₃=2. Далее вносим в таблицу х₂₃=8, х₁₂=9.

Таблица 8 представляет начальный план задачи Х₁. (Полезно проверить, что сумма поставок по столбцам равна соответствующим мощностям потребителей, сумма поставок по строкам — емкостям поставщиков.)

Таблица 8. План Х₁.

		—	—
		—	—
			—
				—

Заполненные клетки таблицы соответствуют базисным переменным, а пустые — свободным переменным из системы ограничений (1) (свободные переменные равны нулю). Поскольку система (1) содержит m+n–1 линейно независимых уравнений, то и число базисных переменных будет таким же, (m — число поставщиков, n — число потребителей). План с m+n–1 заполненными (базисными) клетками называется невырожденным,при меньшем числе заполненных клеток — вырожденным. Для того чтобы снять вырождение, необходимо в пустые клетки записать нулевые перевозки, дополнив число базисных переменных до количества m+n–1. Ноль можно поставить только в ту пустую клетку, которая не будет образовывать цикла вместе с уже заполненными клетками.

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

Проверим вырожденность плана нашей задачи: мы имеем 4-х поставщиков и 3-х потребителей, для невырожденного плана число заполненных клеток должно составлять 4+3–1=6. У нас 6 заполненных клеток, следовательно, план невырожденный.

Подсчитаем суммарную стоимость перевозок плана Х₁:

и делаем следующий шаг.

2. Проверка плана на оптимальность.

При проверке плана на оптимальность воспользуемся методом потенциалов.

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

, (i=1, 2, n; j=1, 2, m). (5)

Количество неизвестных потенциалов составит m+n, а уравнений (1) всего m+n–1. Поэтому один из потенциалов задается произвольно, после чего остальные потенциалы из системы уравнений (5) определяются однозначно. Обычно полагают .

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

, (i=1, 2, n; j=1, 2, m). (6)

Если ввести понятие оценки клетки:

, (7)

то условие (6) оптимальности плана можно сформулировать как условие неотрицательности оценок всех пустых клеток:

.(8)

Проверим оптимальность построенного нами начального плана.

По заполненным клеткам определим потенциалы поставщиков U_i и потребителей V_j, которые будем вписывать справа и внизу транспортной таблицы соответственно.

Положим U₁ =0. Для заполненных клеток запишем условие (5) и найдем неизвестные потенциалы:

(1;3): , откуда V₃=10;

(2;3): U₂ +10 = 12, U₂ = 2;

(3;3): U₃ +10 = 8, U₃ = –2;

(3;1): –2 + V₁= 5, V₁ = 7;

(4;1): U₄ + 7= 2, U₄ = –5;

(4;2): –5+ V₂ = 1, V₂ =6.

Вычислим оценки пустых клеток по формуле (7):

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

3. Улучшение плана.

Если среди оценок свободных клеток построенного плана есть хотя бы одна отрицательная, план может быть улучшен. Среди пустых клеток с отрицательными оценками выбираем клетку с наименьшей величиной и для нее строим цикл пересчета. Одна вершина цикла находится в пустой клетке (i;j), а остальные — в заполненных. В вершинах цикла, начиная с пустой клетки, последовательно расставляем знаки «+» и «–». Cреди клеток, помеченных знаком «–» определяется наименьшее значение перевозки . Внутри цикла происходит перераспределение перевозок: в клетки со знаком «+» добавляется, а из клеток со знаком «–» вычитается величина . Таким образом пустая клетка (i;j) с наименьшей величиной получает поставку ; поставки клеток, не входящих в цикл, остаются прежними.

В результате получаем новый план перевозок. Он может оказаться вырожденным, поэтому нужно следить за тем, чтобы каждый новый план содержал ровно m+n–1 заполненных клеток.

Для нашей задачи среди отрицательных оценок наименьшую оценку имеет клетка (1;2), для нее строим цикл пересчета.

Из клетки (1;2) звено ломаной можно провести только вправо (слева нет заполненной клетки), затем вниз до клетки (3;3) (вершина ломаной не может быть в клетке (2;3), поскольку в этой строке больше нет заполненных клеток). Затем влево до клетки (3;1), далее (4;1), (4;2) и возвращаемся в (4;1). Расставляем чередующиеся знаки «+» и «–» в вершинах ломаной, начиная с вершины в пустой клетке (1;2) (табл. 9).

Таблица 9.

	—	— +	-9
	—	—
	10 -	—	+ 2	-2
	2 +	9 -	—	-5

Вычислим = min{9;10;9}=9 — количество груза, перераспределяемое внутри цикла. Величина прибавляется к перевозкам в клетках, помеченных знаком «+», и вычитается из перевозок в клетках, помеченных знаком «–». Изменение величины перевозок происходит только в вершинах цикла, остальные значения х_ij остаются прежними.

Новый план Х₂ должен содержать 6 заполненных клеток, в построенном нами плане их всего 5, т.е. план вырожденный. Так получилось потому, клетки (1;3) и (4;2) одновременно стали пустыми. Чтобы снять вырождение плана, надо в одну из этих клеток дать перевозку, равную нулю, тогда клетка станет базисной. Поставим 0, например, в клетку (1;3), эта нулевая поставка переводит свободную клетку в разряд базисных. План Х₂ транспортной задачи представлен в табл.10. (В этой же таблице записаны потенциалы и изображен цикл пересчета, получаемые в дальнейшем).

Таблица 10. План Х₂.

	—	9
	— +	—	- 8
	1 _	—	+ 11	-2
		—	—	-5

Изменение значения целевой функции можно вычислить как = , где — оценка клетки, для которой построен цикл, — количество перемещаемого по циклу груза.

= + =265+9(-3)=238.

Исследуем план Х₂ на оптимальность.

Вычислим потенциалы U_i и V_j. Положим U₁ =0 и для заполненных клеток (напомним, что клетка (1;3) является заполненной) запишем условие (8.5):

(1;3): , откуда V₃=10;

(1;2): 0+V₂= 3, V₂ = 3;

(2;3): U₂+10 = 12, U₂= 2;

(3;3): U₃ +10= 8, U₃= –2;

(3;1): –2+ V₁= 5, V₁ = 7;

(4;1): U₄+7 = 2, V₁ = –5;

Сделаем оценки пустых клеток:

Для плана X₂ условие оптимальности (8) не выполнено, т.к. клетка (2;1) получила отрицательную оценку, для нее строим цикл пересчета. Расставляем чередующиеся знаки «+» и «–» в вершинах цикла, начиная с вершины (2;1).

Вычислим = min{8;1}=1. Прибавим это значение к величине перевозок в клетках со знакам «+», вычтем из перевозок в клетках со знакам «–». Получим новый невырожденный план X₃, представленный в таблице 11.

Таблица 11. План X₃.

	—	1
	—	8	—
	1	—		-2
		—	—	-3

= + =238+1(-2)=236.

Проверим план на оптимальность. Найдем потенциалы, полагая U₁ =0:

(1;3): , откуда V₃=10;

(1;2): 0+V₂= 3, V₂ = 3;

(2;3): U₂+10 = 12, U₂= 2;

(2;1): 2+ V₁= 7, V₁ = 5;

(3;3): U₃ +10= 8, U₃= –2;

(4;1): U₄+5 = 2, U₄= –3.

Вычислим оценки пустых клеток:

Поскольку все оценки неотрицательны, план X₃ является оптимальным.

X₃= , =236.