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

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

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

Пусть имеется 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)

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

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

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

 

	B 1	B 2	B 3	B 4	B 5	Запасы
А1	c 11 x 11	c 12 x 12	c 13 x 13	c 14 x 14	c 15 x 15	a 1
А 2	c 21 x 21	c 22 x 22	c 23 x 23	c 24 x 24	c 25 x 25	a 2
А 3	c 31 x 31	c 32 x 32	c 33 x 33	c 34 x 34	c 35 x 35	a 3
Потребности	b 1	b 2	b 3	b 4	b 5

 

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

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. Любая закрытая транспортная задача имеет решение, которое достигается за конечное число шагов метода потенциалов.