Транспортная задача

 ТРАНСПОРТНАЯ  ЗАДАЧА

 

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

Пример 1. Сформулировать эту задачу можно на следующем примере. Имеются три поставщика и четыре потребителя. Предложения  поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары "поставщик — потребитель" сведены в таблицу поставок (табл. 1).

     Табл.1

 

Постав -щики	Предло-жения поставщиков	Потребители и их спрос
			1	2	3	4
			20	110	40	110
1	60	1	2	5	3
2	120	1	6	5	2
3	100	6	3	7	4

 

 

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

Задача ставится следующим образом. Найти объемы перевозок для каждой пары "поставщик — потребитель " так, чтобы:

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

 Решение. Построим математическую модель данной задачи. Искомый объем перевозки от i - поставщика к j - потребителю обозначим через и назовем поставкой клетки . Например, - искомый объем перевозки от 1-го производителя ко 2-му потребителю или поставка клетки (1,2). Заданные предложения поставщиков и спросы потребителей накладывают ограничения на значения неизвестных (уравнения балансов по строкам).

Уравнения балансов для каждой строки таблицы поставок, т. е.

        (1)

 

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

          (2)

 

Очевидно

.

 

Суммарные затраты F на перевозку выражаются через коэффициенты затрат и поставки следующим образом:

 

   (3)

 

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

 На множестве неотрицательных решений системы ограничений (1) и (2) найти такое решение , при котором целевая функция (3) принимает минимальное значение.

Особенности математической модели транспортной задачи:

• система ограничений есть система  уравнений (т.е. транспортная задача задана в канонической форме);
• коэффициенты при переменных системы ограничений равны единице или нулю;
• каждая переменная входит в систему ограничений два раза: один раз - в систему (1) и один раз - в систему (2).

Обозначим: - коэффициенты затрат;

 - предложения поставщиков,

- спросы потребителей,

где т - число поставщиков, - число потребителей.

 

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

,         (4)

 

        (5)

 

Целевая функция

.       (6)

 

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

 

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

 

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

.          (7)

 

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

 

Рассмотрим закрытую транспортную задачу.

Модификация симплекс - метода применительно к транспортной задаче называется распределительным методом.

 

Число базисных переменных ТЗ равно рангу системы линейных уравнений (максимальному числу линейно независимых уравнений в системе ограничений).

 

Теорема 1. Ранг системы уравнений (4), (5) при условии (7) равен .

Основное следствие теоремы 1 - число базисных  (основных) переменных закрытой транспортной задачи равно , где т - число поставщиков, п — число потребителей.

Заполнение таблицы поставок  назовем базисным.

 

Распределение поставок называется базисным, если переменные, соответствующие заполненным клеткам, можно принять за базисные переменные.

Клетки, отвечающие базисным переменным - базисные, «заполненные» клетки;

 клетки, соответствующие свободным переменным, — свободные или пустые.

 

Опорный план.

 

Нахождение начального базисного распределения поставок.

метод "северо-западного" угла.

 

 

Пример 2. Найти начальное допустимое базисное распределение поставок для транспортной задачи 1.

 

Решение.

• Дадим максимально возможную поставку в клетку (1,1) - "северо-западный" угол таблицы поставок (Дадим переменной максимально возможное значение):

 

.

 

Заполненные клетки перечеркиваем сплошной линией (табл. 2)). Клетки, выпавшие из последующего рассмотрения, перечеркнуты пунктирной линией.

 

• новый "северо-западный" угол - клетка (1,2) и дадим в нее максимально возможную поставку.

1-й поставщик  60-20=40 единиц груза,

х12 = min {40, 110} = 40.

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

новый "северо-западный угол" и т. д. В результате получаем следующее исходное распределение поставок (табл.2). Число заполненных клеток в полученном  распределении   оказалось равным =3+4-1=6, т.е. числу основных (базисных) переменных.

Табл. 2

 

 

Недостаток метода "северо-западного" угла: опорный план строится без учета коэффициентов затрат ТЗ.

 

Метод наименьших затрат.

 

 Пример 3. Найти методом наименьших затрат начальное распределение поставок в задаче 1.

Решение. Клеток две - (1,1) и (2,1) с коэффициентами затрат, равными 1.

Для клетки (1,1)     ,

Для клетки (2,1) .

 

Даем поставку, равную 20 единицам, в клетку (2,1).

 

Табл. 1

Постав -щики	Мощность поставщиков	Потребители и их спрос
			1	2	3	4
			20	110	40	110
1	60	1	2	5	3
2	120	1	6	5	2
3	100	6	3	7	4

 

    

Табл.3                          

	20	110	40	110
60	1	2	5	3
120	1                    20	6	5	2
100	6	3	7	4

 

В оставшейся таблице наименьшим коэффициентом затрат обладают две клетки: с12 = с24= 2.

 

Для клетки (1,2) x12= min {60, 110} = 60;

 

Для клетки (2,4) x24 = min {120-20, 110} = 100.

 

Даем поставку в клетку (2,4), для которой x24 = 100 (табл. 4).

       Табл.4

	20	110	40	110
60	1	2	5	3
120	1                    20	6	5	2                100
100	6	3	7	4

 

Получаем x12 = min{60, 110} = 60, x32 = min{100, 110-60} = 50, x34 = min {100-50, 110-100} = 10, x33 = min {100-60, 40} = 40 (табл. 5).

 

Сравним найденное распределение поставок с распределением, полученным для той же задачи по методу "северо-западного" угла ( табл. 2). Вычислим для каждого из этих распределений суммарные затраты в денежных единицах: табл.2:

    F0 = 1*20 + 2*40 + 6*70 + 5*40 + 2*10 + 4*100=

         = 1140;

табл.5:

F0= 1*20 + 2*60 + 3*50 + 2*100 + 7*40 + 4*10 =

    = 810.

 Табл.5

	20	110	40	110
60	1	2              60	5	3
120	1                    20	6	5	2                100
100	6	3               50	7              40	4                  10

 

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

 

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

Пример 4. Найти начальное допустимое базисное распределение поставок для следующей транспортной задачи (табл. 6).

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

  .

 

 Табл. 6

	20	10	40
30	1             20	3             10	5
30	3	3               0	2            30
10	4	1	2            10

 

 

 

 

 

 

 

 

 

Используем следующий искусственный прием.

 

Разобьем второй шаг на два шага. Допустим, что после поставки в клетку (1,2) из рассмотрения выпадает, например, только первая строка. Для того чтобы вывести из рассмотрения второй столбец, делаем еще один шаг: даем нулевую (фиктивную) поставку в «с-з», но не вычеркнутую клетку (2,2) второго столбца.

 

При последующем заполнении таблицы поставок используем метод "северо-западного" угла обычным способом. В результате получаем распределение поставок

 

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

Оценка при свободной переменной называется оценкой свободной клетки .

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