Транспортная задача линейного программирования

Транспортная задача линейного программирования

Постановка задачи

Пусть имеется m поставщиков некоторого однородного груза, сосредоточенного на станциях А₁ , А₂ , …, А_m и имеется n потребителей этого продукта, расположенные на станциях В₁ , В₂ , …, В_n. Известны также запасы этого груза (а₁ , а₂ ,…, а_m), которые должны быть вывезены в фиксированный период времени. Потребности получателей груза за этот же период времени составляют (b₁ , b₂ , …b_n).

Пусть запасы равны потребностям, т.е. . (6.1)

При выполнении условия (6.1) транспортная задача называется закрытой.

Кроме того, известны затраты С_ij на перевозку единицы груза с любой станции А_i на каждую станцию В_j.

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

Математическая модель

Обозначим величину перевозки со станции А_i на станцию B_j как x_ij. Тогда условия полного вывоза груза со всех станций А_i можно записать в виде системы уравнений:

(6.2)

С другой стороны, станции В_j должны получить необходимое количество груза, что тоже записывается в виде системы уравнений:

(6.3)

При этом выполняется условие неотрицательности для переменных x_ij:

Функция цели задачи по критерию минимума суммарных затрат –

(6.4)

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

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

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

	B1	B2	B3	B4	B5	Запасы
А1	c11 x11	c12 x12	c13 x13	c14 x14	c15 x15	a1
А2	c21 x21	c22 x22	c23 x23	c24 x24	c25 x25	a2
А3	c31 x31	c32 x32	c33 x33	c34 x34	c35 x35	a3
Потребности	b1	b2	b3	b4	b5

Рассмотрим различные методы нахождения первого опорного решения.

6.2. Методы определения начального опорного плана

Метод северо-западного угла

В соответствии с этим методом, в верхнюю левую (северо-западную) клетку таблицы заносится максимально допустимая перевозка. При этом либо вывозится весь груз со станции А₁, тогда все остальные клетки первой строки вычеркиваются, либо потребности первого потребителя В₁ полностью удовлетворены, тогда все клетки первого столбца вычеркиваются. После этого самой северо-западной клеткой становится клетка А₁-В₂ или А₂-В₁. Указанный алгоритм применяется до заполнения всей таблицы.

Рассмотрим этот метода на примере.

Ставим первую перевозку в клетку А₁-В₁. Она будет равна . Закрыт первый столбец. Идем по строке. В клетку А₁-В₂ ставим перевозку, равную . Закрыли первую строку (в закрытой строке или столбце будем ставить прочерки для того, чтобы не поставить туда перевозку). Спускаемся по второму столбцу. В клетку А₂-В₂ ставим перевозку и закрываем второй столбец. Идем по второй строке и ставим перевозку в клетку А₂-В₃. Она равна . Закрыли третий столбец. Продолжаем идти по третьей строке. В клетку А₂-В₄ ставим перевозку . Теперь закрыли вторую строку и спускаемся по четвертому столбцу. В клетку А₃-В₄ ставим перевозку . Закрыв этот столбец, идем по третьей строке. Перевозка в клетке А₃-В₅ равна . Таблица исчерпана. Все грузы вывезены, все потребности удовлетворены.

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

	В1	В2	В3	В4	В5
А1	20 4	20 3	- 4	- 11	- 9
А2	- 3	1 4	7 7	22 15	- 8
А3	- 7	- 4	- 2	2 8	8 15

Вычислим стоимость всех перевозок. Она равна:

Теперь на этом же примере рассмотрим другой метод.

Метод наименьшей стоимости

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

Опишем последовательность действий для данного метода на примере.

Выбираем в таблице клетку с наименьшей стоимостью (А₃-В₃) и ставим в нее перевозку , закрыли третий столбец. В пункте А₃ осталось 10-7=3 единиц груза. В оставшихся клетках выбираем наименьшую стоимость. Таких клеток две: А₂-В₁ и А₁-В₂. Случайным образом выбираем сначала клетку А₁-В₂: ставим сюда перевозку, равную . Мы закрыли второй столбец, а в пункте А₁ осталось 40-21=19 единиц груза. Далее ставим перевозку в клетку А₂-В₁. Она равна . Закрыли первый столбец, а в пункте А₂ осталось 30-20=10 единиц груза. Минимальная стоимость в оставшихся клетках равна 8 и находится она в клетке А₃-В₄. Ставим туда перевозку . Закрыта третья строка.

Пункту В₄ необходимо еще 24-3=21 единиц груза. Такая же стоимость и в клетке А₂-В₅. Ставим туда перевозку . Закрыли пятый столбец, а в пункте А₂осталось 10-8=2 ед. груза. Во второй строке осталась свободной только клетка А₂-В₄. Ставим туда перевозку . Вторая строка закрыта.

Пункту В₄ необходимо 21-2=19 единиц груза. Заполняем оставшуюся клетку А₁-В₄. Ставим сюда перевозку 19 единиц груза. Заполнена вся таблица.

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

	В1	В2	В3	В4	В5
А1	- 4	21 3	- 4	19 11	- 9
А2	20 3	- 4	- 7	2 15	8 8
А3	- 7	- 4	7 2	3 8	- 15

Вычислим общую стоимость перевозок:

.

Метод двойного предпочтения

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

Опишем алгоритм этого метода на том же примере.

Выберем в каждом столбце минимальную стоимость и отметим его значком. Тоже сделаем со строками. Выбрали клетки с двумя значками: в клетку А₁-В₂ ставим перевозку (закрыт 2 столбец, в пункте А₁ осталось 40-21=19 ед.); клетка А₂-В₁ – перевозка равна , закрыт 1 столбец, в пункте А₂ осталось 30-20=10 ед.); клетка А₃-В₃ – перевозка , закрыт 3 столбец, в пункте А₂ осталось 10-7=3 ед.) Теперь ставим перевозки в клетки с одним значком: А₂-В₅ – перевозка (закрыт 5 столбец, в пункте А₂ осталось 10-8=2 ед.); А₃-В₄ – перевозка (закрыта 3 строка, а пункту В₄ нужно 24-3=21 ед.). Остальные клетки можно заполнить так же, как в предыдущем методе.

	В1	В2	В3	В4	В5
А1	- 4	☺☺21 3	- 4	19 11	- 9
А2	☺☺20 3	- 4	- 7	2 15	☺8 8
А3	- 7	- 4	☺☺7 2	☺ 3 8	- 15

Общая стоимость перевозок равна:

.

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

Метод потенциалов

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

Теоремы метода.

Теорема 1: Если опорный план X = (x_ij) является оптимальным, то существует система из (m+n) чисел, называемых потенциалами, U_i , V_j , такая, что:

а) U_i +V_j = C_ij, для x_ij > 0 (базисные переменные);

б) U_i +V_j = C_ij, для x_ij = 0 (свободные переменные).

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

- для каждой занятой клетки сумма потенциалов равна стоимости перевозки единицы груза, стоящей в этой клетке:

U_i +V_j = C_ij (6.5)

- для каждой свободной клетки сумма потенциалов меньше или равна стоимости перевозки единицы груза, стоящей в этой клетке:

U_i +V_j ≤ C_ij (6.6)

Примечание: Система (6.5) содержит (m+n) неизвестных и (m+n-1) линейно независимых уравнений. Такая система имеет бесчисленное множество решений, которые можно получить, придавая одной из неизвестных конкретное значение. Это значение выбирается произвольно, например, можно придать U₁ значение равное 0, тогда другие потенциалы вычисляются из системы (6.5).

Теорема 2. Любая закрытая транспортная задача имеет решение, которое достигается за конечное число шагов метода потенциалов.