 |
Транспортная задача с ограниченными возможностями транспортных средств
|
|
|
|
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
В общей постановке транспортной задачи предполагается, что из любого пункта производства любой пункт потребления может быть перевезено любое количество груза.
В целом ряде случаев оптимизации планирования перевозок приходится учитывать ограниченные возможности транспортных путей и средств. Поэтому математическую модель транспортной задачи:
(1.7)
i=1,2,…,m, (1.8)
j=1,2,…,n, (1.9)
(1.10)
должны быть введены дополнительные ограничительные условия, учитывающие возможность транспортных путей и средств.
Если обозначиться транспортные возможности между пунктами I и j через dij, то количество груза 
, которое может быть перевезено по этому направлению за планируемый период времени, не должно превышать транспортных возможностей, т.е.
(1.11)
Тогда ограничения 1.10, 1.11 объединяются, и модель задачи усложняется двусторонними ограничениями на переменные
(1.12)
При этом общая транспортная возможность дорог, соединяющих I -й пункт производства со всеми n пунктами потребления, должна быть ровна или больше количества продукции, предназначенной к постановке из этого i-го пункта всем n потребителя, т.е.
i=1,2,…,m, (1.13)
Общая же транспортная возможность дорог, соединяющих j-й пункт потребления со всеми m пунктами производства, должна быть равна или больше количества продукции, которые надо поставить в этот j-й пункт от всех m поставщиков, т.е.
|
|
|
i=1,2,…,n, (1.14)
Существуют различные подходы к решению этой задачи. Рассмотрим наиболее простой из них.
Путей некоторых преобразований условий ее можно свести к типу обычной транспортной задачи. Для этого пункт производства или потребления, для которых условия ограничены транспортные возможности, разбивается на два условных пункта. При этом следует подчеркнуть непременно один пункт.
Мощность условного поставщика А’i - принимается равный установленной возможности средств, соединяющих пункт и с потребителями j
A’i=dij (1.15)
а мощность условного поставщика А’j - равной разности между заданными в условии задачи мощностью поставщика в пункте I и возможностью средств между I-м и j-м пунктами, т.е.
a’’i=ai-dij. (1.16)
При этом затраты на поставку грузов из пунктов I’ в пункт j-cij принимаются равными действительным расходам cij приведенным в условии задачи. В оптимальном решение переменные хij могут иметь любое неотрицательное значение от нуля до a’i, т.е.
(1.17)
В отличие от них переменные хij в оптимальном решении непременно должны быть равны нулю, поскольку мощность А’j характеризует количество в пункте и сверх установленной средств, соединяющих пункты i и j, следовательно это часть груза должна быть направлена не j-му а любому другому потребителю. Для того, чтобы в оптимальном решении обеспечить значение переменных хij равно нулю, затраты на поставку груза из пункта i’’ в пункт j принимаются равными М, т. е cij=М.
При минимизации целевой функции (1.7) и коэффициентах cij=М, в оптимальном решении получим
Отсюда следует, что
Xij = Xi’j+ Xi’j = Xij (1.18)
Тогда, исходя из условий (1.15), (1.17), получим
|
|
|
Таким образом, объем поставки груза из пункта i в пункт j не превысит установленной способности транспортных средств, обеспечивающих эти пункты.
Если для какой то пары пунктов производства i потребления s транспортные возможности не ограничены, объем поставки груза от поставщика Аi к потребителю Bs определится как сумма значений пары соответствующих переменных:
Дальнейший расчет будет выполнен с помощью венгерского метода решении транспортного алгоритма.
|
|
|
