Специальные задачи линейного программирования: транспортная задача.

2.1. Постановка задачи и математическая модель транспортной задачи. Предположим, что существуют N потребителей и M поставщиков некоторого однородного груза, у каждого из поставщиков определенный запас этого груза (A_i единиц, i=1, 2, …, M), а каждому из потребителей требуется B_j единиц груза (j=1, 2, …, N). Известны также затраты c_ij на перевозку единицы груза от поставщика A_i к потребителю B_j. Требуется составить такой план перевозок от поставщиков к потребителям, чтобы суммарные затраты на перевозки оказались минимальными (при этом должны быть по возможности вывезены все запасы поставщиков и удовлетворены все запросы потребителей).

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

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

При составлении математической модели через x_ij обозначается количество единиц груза, который будет перевезен от поставщика A_i к потребителю B_j (объем перевозок от A_i к B_j). Эти значения будут вноситься в центр соответствующей ячейки.

С учетом сказанного целевая функция принимает вид

(просуммированы все произведения затрат на соответствующий объем перевозок). Ограничения связаны с вывозом запасов и удовлетворением запросов, поэтому математическая модель имеет вид:

Пример 2.1. Транспортная задача задана с помощью таблицы 2.1, из которой видно, что на складах трех поставщиков A1, A2, A3 сосредоточены соответственно 30, 190 и 250 единиц груза, потребители B1, B2, B3, B4 нуждаются соответственно в 70, 120, 150, 130 единицах груза, а стоимости перевозок указаны непосредственно в таблице.

В А Таблица 2.1.

Заметим, что суммарные запасы (30+190+250=470) равны суммарным запросам (70+120+150+130=470). Разместим в основной (незаштрихованной) части таблицы искомые объемы перевозок x_ij и перейдем к составлению математической модели. Заметим, что нумерация соответствует привычной нумерации элементов в матрицах (i – номер строки, j – номер столбца). Итак, целевая функция принимает вид

(2.1)

(просуммировали произведения стоимостей на объемы перевозок по всем строкам). При построении системы ограничений сначала суммируем объемы перевозок по каждому столбцу (удовлетворяем все запросы), а потом суммируем объемы перевозок по каждой строке (вывозим все запасы). Учтем также неотрицательность значений x_ij и получаем следующие условия:

(2.2)

Итак, мы построили математическую модель предложенной задачи с целевой функцией (2.1) и системой ограничений (2.2).

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

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

Метод северо-западного угла. Основная идея заключается в том, вычисление значений x_ij начинается с верхней левой клетки (северо-западный угол таблицы). Из значений запасов и запросов, ей соответствующих (A₁ и B₁) выбираем минимальное – это и будет объем перевозок x₁₁. При этом либо удовлетворены все запросы (и тогда из рассмотрения исключается потребитель, при этом в таблице в оставшихся ячейках соответствующего столбца ставятся прочерки, а объем запасов в соответствующей строке уменьшается на это значение), либо вывезены все запасы (из рассмотрения исключается поставщик, прочерки ставятся в строке и уменьшается объем запросов). В случае, когда A₁=B₁, вычеркивается либо строка, либо столбец (но не строка и столбец одновременно! ) Далее действия повторяются со следующей ячейкой, которая оказалась верхней левой – и так до момента, пока не окажется, что все запасы вывезены, а все запросы удовлетворены. При этом клетки, в которые попали значения x_ij, , называются занятыми.

Внимание! Во избежание ошибок необходимо убедиться в том, что число занятых клеток равно M+N-1; в противном случае построенное начальное решение не будет опорным. При этом необходимо помнить, что, в силу сформулированного правила выбора объема перевозок, в занятых клетках могут оказаться значения, равные нулю!

Пример 2.2. Ниже в таблицах 2.2-2.7 приводится пошаговое построение методом северо-западного угла начального опорного решения для закрытой задачи из примера 2.1; объемы перевозок внесены в таблицы жирным курсивным шрифтом.

 

 

В А - - -                 Таблица 2.2.	В А - - -       -       Таблица 2.3.
В А - - -     - -     Таблица 2.4.	В А - - - - - -     Таблица 2.5

 

В А - - - - - -   Таблица 2.6.

В А - - - - - - Таблица 2.7.

Итак, заняты 6 ячеек: (1; 1), (2; 1), (2; 2), (2; 3), (3; 3) и (3; 4) (здесь, как и всюду далее, в «адресе» ячейки первым указан номер строки, вторым – номер столбца, заголовки в нумерации не учитываются). Количество занятых ячеек совпадает с числом M+N-1=3+4-1=6. Мы построили начальное опорное решение X₁, остается найти значение целевой функции для этого опорного решения (в свободных клетках, т.е. клетках с прочерками, значение объема перевозок считается равным нулю и потому на результат вычисления не влияет): .

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

Пример 2.3. В таблицах 2.8-2.13 приводится пошаговое построение начального опорного решения методом минимальной стоимости для закрытой задачи из примера 2.1. Обратите внимание, что первый выбор сделать легко, а в таблице 2.8 видно, что в ячейках (2; 3) и (1; 3) одинаковая стоимость затрат (равная 2). Поскольку в ячейку (2; 3) можно записать объем перевозок, равный 70, а в ячейку (1; 3) – равный 30, выбираем ячейку с большим объемом, т.е. (2; 3) – см. таблицу 2.9.

 

В А -             -     Таблица 2.8.

В А -     - -   -     Таблица 2.9.

 

В А - - - - -   -   Таблица 2.10.

В А - - - - - -   -   Таблица 2.11

 

В А - - - - - -   Таблица 2.12.

В А - - - - - - Таблица 2.13

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

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

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

В А       Таблица 2.14

Решение. Прежде всего, очевидно, что суммарные запасы равны 100, а суммарные запросы – 90. Поэтому необходимо ввести фиктивного потребителя, запросы которого равны 10 (это дополнительный столбец, значения стоимостей в котором будут равны 0) – см. таблицу 2.15, с которой начнем построение начального решения методом северо-западного угла. На первом шаге для ячейки (1; 1) значения запасов и запросов одинаковы и равны 30, поэтому объема перевозок равен 30, вычеркиваем, например, строку (при этом запросы в соответствующем столбце становятся равными 0). На следующем шаге (см. таблицу 2.16) в ячейку (2; 1) ставится значение объема перевозок 0 – как минимальное из чисел 0 и 20, при этом вычеркивается первый столбец.

В А - -           Таблица 2.15.	В А - - -     Таблица 2.16.
В А - - - -     Таблица 2.17.	В А - - - -   Таблица 2.18.
В А - -   - Таблица 2.19.	При получении таблиц 2.17-2.19 действовали по стандартной схеме. Занятыми оказались, как и положено, 5 клеток (3+3-1=5), остается найти значение целевой функции для найденного опорного решения:

Проведем теперь построение начального опорного решения методом минимальной стоимости (таблицы 2.20-2.24).

В А - -           Таблица 2.20.	В А - - - - Таблица 2.21.
В А - - - - Таблица 2.22.	В А - - - - Таблица 2.23.
В А - - - - Таблица 2.24.	Опять заняты 5 клеток, находим значение целевой функции для найденного опорного решения: Замечание. При записи ответа (начального опорного решения) последние столбцы в таблицах 2.19 и 2.24 не учитываются.

 

2.3. Проверка оптимальности решения. Метод потенциалов. Для проверки оптимальности решения введем потенциалы строк (u_i, i=1, 2, …, M) и столбцов (v_j, j=1, 2, …, N) – числа, которые определяются системой уравнений , составленных по занятым клеткам. Заметим, что занятых клеток M+N-1, поэтому мы имеем систему из M+N-1 уравнений с M+N неизвестными потенциалами. Это неопределенная система, нас интересует любое частное решение, поэтому любому из потенциалов можно на первом шаге дать значение, равное нулю. Далее последовательно находятся все потенциалы, которые записываются в дополнительный правый столбец и в дополнительную нижнюю строку таблицы транспортной задачи (общую схему см. в таблице 2.25).

B A	B1	B2	…	BM	Потенциалы строк
A1	с11	с12	…	с1N	u1
A2	с21	с22	…	с2N	u2
…	…	…	…	…	…
AM	сM1	сM2		cMN	uM
Потенциалы столбцов	v1	v2	…	vN

Таблица 2.25

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

Пример 2.5. Проверить оптимальность решения, построенного в примере 2.4 (см. таблицу 2.24).

Решение. Сначала по таблице 2.24 определяем потенциалы.

Занятыми являются клетки (1; 1), (2; 1), (2; 2), (2; 3), (3; 2). С учетом стоимостей, записанных в этих клетках, составляем систему уравнений

В А ui - - - - -2 vj -1   Таблица 2.26.

Пусть . Далее последовательно: из первого уравнения , из второго уравнения , из третьего , из четвертого , из пятого . Результаты собраны в таблице 2.26.

Расчет оценок проводится по формуле непосредственно в таблице 2.27, с учетом найденных выше потенциалов

В А				ui
		0+4-3=1> 0 -	0+(-1)-0=-1< 0 -
	-2+1-4=-5< 0 -		-2+(-1)-0=-3< 0 -	-2
vj			-1

Таблица 2.27.

Итак, видно, что в ячейке (1; 2) оценка положительна, т.е. предложенное решение не является оптимальным.

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

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

Замечание. Если минимальное значение q достигается в нескольких клетках, то только одна из них становится пустой, а в остальных объем перевозок выставляется равным 0; это позволяет сохранить необходимое количество занятых клеток.

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

Пример 2.6. Найти оптимальное решение для транспортной задачи из примера 2.4.

Решение. Условия были приведены в таблице 2.14. Задача была открытой, поэтому сначала был введен фиктивный потребитель. Начальное опорное решение, построенное методом минимальной стоимости – в таблице 2.24. Таблица 2.27 (с потенциалами и оценками) свидетельствует, что построенное решение не оптимальное, а ячейка (1; 2) – единственная ячейка с положительной оценкой. С нее и начнем строить цикл. По таблице 2.27 видно, что его образуют ячейки (1; 2), (2; 2), (2; 1), (1; 1). В силу сказанного выше ячейки

В А - - - - Таблица 2.28.

(1; 2) и (2; 1) будут иметь знак «+», ячейки (2; 2) и (1; 1) – знак «-». Объем перевозок в ячейке (2; 2) равен 10, в ячейке (1; 1) 30, минимальное значение q=10. Таким образом, в ячейках (1; 2) и (2; 1) объем перевозок будет увеличен на 10, а в ячейках (2; 2) и (1; 1) уменьшен на 10, при этом ячейка (2; 2) освободится. Новое опорное решение приведено в таблице 2.28.

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

 

В А				ui
			0+(-1)-0< 0 -
		1+3-5< 0 -
	-1+1-4< 0 -		-1+(-1)-0< 0 -	-1
vj			-1

Таблица 2.29.

Все оценки отрицательны, значит, найденное опорное решение является оптимальным. Для завершения решения отбрасываем столбец с фиктивным

В А - - Таблица 2.30.

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

2.5. Алгоритм полного решения транспортной задачи. Подводя итог сказанному выше, определим порядок действий при решении транспортной задачи с M поставщиками и N потребителями.

1) Определить, является ли задача закрытой или открытой; в последнем случае ввести фиктивного потребителя или поставщика и построить новую таблицу.

2) Построить начальное опорное решение X₁ (рекомендуется метод минимальной стоимости) и убедиться, что занято необходимое число клеток (M+N-1) – см. п.2.2.

3) Найти потенциалы с помощью занятых клеток из неопределенной системы ((i; j) – адреса занятых клеток), а затем – оценки для свободных клеток (здесь (i; j) – адреса свободных клеток) – см. п.2.3.

4) В случае, когда все оценки , опорный план является оптимальным, и остается найти значение целевой функции f(X₁). Если же среди оценок оказались положительные, то выбираем ячейку с наибольшей положительной оценкой, строим для нее цикл и переходим к новому опорному решению X₂ – см. п. 2.4. При этом должно выполняться неравенство f(X₂)£ f(X₁). Затем возвращаемся к п. 3) алгоритма.

 

2.6. Задания для самостоятельной работы.

Решить транспортные задачи (определить оптимальное значение целевой функции).

1) В А

2) В А

3) В А	4) В А
5) В А	6) В А
7) В А	8) В А
9) В А

10)

В А