Задача транспорта

 

 

 

 

 

 

Таблица 16

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

                                             T = t _ijx_ij                                                          (23)

не  даст нужного результата: решение, для которого величина Т достигает минимального значения, как, правило, не будет оптимальным по времени. В табл. 17 представлен план перевозок, оптимальный по минимуму линейной формы Т. Все перевозки по этому плану будут выполнены за 8 ч. при Т = 370 ч.

 

 

 

 

 

 

 

 

 

 

Таблица 17

 

В табл. 18 показан другой план этой задачи, по которому значение линейной формы несколько больше - Т = 380 ч (план по критерию Т не оптимален, так как t_ij < u_i + v_j), но все перевозки выполняются за 5 ч.

 

Таблица 18

 

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

Обозначим через x_ij количество груза, планируемого к отправке из пункта A в пункт B. Тогда при выбранном критерии оптимальности задача формируется следующим образом: определить набор чисел x_ij (план перевозок), для которого время t (X) наиболее продолжительной перевозки

                                         t ( X) = max t_ij для x_ij > 0                                                    (24)

достигает минимума при условиях

                                           x_ij = b_j, j = 1, 2, …, n;                                                    (25)

                                           x_ij = a_i, i= 1, 2, …, m;                                                    (26)

                                         x_ij > 0, i= 1, 2, …, m; j = 1, 2, …, n.                                (27)

Выражение (24) означает наибольшее из времен запланированных  перевозок.

Так как t (X) - нелинейная функция своих переменных x_ij, то модель (24) - (27) не является задачей линейного программирования. Это задача на минимакс, и решить её методами линейного программирования нельзя. Вместе с тем решение задачи можно свести к последовательному решению одним из способов распределительного метода (методом потенциалов) серии обычных транспортных задач, где оптимальное решение предыдущей задачи служит исходным планом последующей задачи. Процедура вычислений складывается из следующих шагов.

 

1.Составить матрицу условий так, как это делают при решении обычной транспортной задачи.

2. Найти методом потенциалов план, у которого линейная форма

t_ij x_ij достигает минимального значения.

3. Определить  max t_ij (наибольшее из времён) запланированных перевозок (где x_ij >0).

4. Во  всех клетках матрицы, где t_ij = max t`_ij, заменить на число M = .

5. Отыскать  для изменённой матрицы решение, при котором линейная форма t_ij x_ij достигает минимума. Если в полученном решении

x_ij > 0 расположены только в клетках, где t_ij < М, то снова находим mах t``_ij и повторяем шаги 4 и 5. Если же в полученном решении имеется хотя бы один x_ij > 0, расположенный в клетке с t_ij = М, то оптимальным по критерию (24) будет предыдущее решение.

Очевидно, что после конечного числа  повторений шагов 3, 4 и 5 будет получено оптимальное решение, т.е. такой план перевозок, по которому грузы всем потребителям будут доставлены за возможно короткое время.

Поясним процесс вычислений на конкретном примере. В табл. 30 приведена матрица условий задачи. В правом верхнем углу клеток записано время движения автомобилей между соответствующими пунктами в часах.

 

 

 

 

 

 

 

 

Таблица 19