Транспортная задача и принципы ее решения
На сегодняшний день множество предприятий занимаются перевозкой продукции для ее дальнейшей реализации. Поэтому большое значение имеет процесс оптимизации грузоперевозок с целью минимизации затрат на доставку грузов. Этим вопросом занимается линейное программирование, точнее такое его направление, как решение транспортной задачи. Этот вопрос и будет рассмотрен далее в статье.
Понятие транспортной задачи. Открытые и закрытые типы задач
Начнем с определения транспортной задачи. Условно говоря, у вас есть товар, расположенный на нескольких складах. Необходимо доставить товар нескольким потребителям – это могут быть магазины, ларьки на рынке и т.д. – при этом у вас есть выбор из нескольких маршрутов. Каждый потребитель имеет свою потребность в товаре, кому-то нужно получить, к примеру, 10 тонн груза, а кому-то хватит и 5 тонн товара.
Ясно, что стоимость перевозки будет различаться в зависимости от количества перевозимого груза и дальности пути. Минимизировать нужно суммарные затраты на перевозку груза. Введем нужные обозначения, пусть $n$ – количество складов, а $m$ – количество точек назначения (потребителей). Через $С(i,j)=c_{ij}$ обозначим стоимость перевозки одной единицы груза из $i$-го склада к $j$-му потребителю.
При этом $a(i)=a_i$ означает запас груза у $i$-го склада, а $b(j)=b_j$ – потребность соответствующего потребителя. Ясно, что общая стоимость перевозки вычисляется как сумма всех затрат на перевозку товара от каждого склада к каждому потребителю. Пусть вас не пугает такая общая постановка задачи, если из какого-то склада нельзя перевезти товар, например из-за невыгодного расположения, то соответствующий $b$ можно установить равным нулю.
Теперь можно перейти к математической формулировке задачи. На языке формул задача примет следующий вид: $$\sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \to \min$$ при следующих ограничениях: $$ \left\{ \begin{array}{l} \sum_{j=1}^{n} x_{ij} = a_i,\\ \sum_{i=1}^{m} x_{ij} = b_j,\\ x_{ij} \geq 0, c_{ij} \geq 0, a_{i} \geq 0, b_{j} \geq 0,\\ i=1,2,...,m; j=1,2,...,n. \end{array} \right. $$ В такой постановке все ясно и дальнейших пояснений не требуется. Остается только решить транспортную задачу.
Существует две разновидности транспортной задачи – открытая и закрытая. Закрытая задача характеризуется тем, что суммарная потребность всех потребителей равна суммарным запасам всех складов. То есть, весь товар на всех складах будет реализован полностью. Математически это пишется как $$ \sum_{i=1}^{m} a_i =\sum_{j=1}^{n} b_j.$$
В открытой задаче суммарная потребность и суммарные запасы не совпадают. Например, какой-то склад не реализуется товар полностью, появляются остатки продукции. В этом случае процесс решения транспортной задачи немного усложняется, потребуется ввести фиктивного поставщика или потребителя с нулевыми стоимостями перевозки.
Решение транспортной задачи: пример постановки, основные методы
Рассмотрим пример постановки простой транспортной задачи.
В следующей таблице приведены стоимости перевозок единицы товара из определенного склада к определенному потребителю.
Например, число 7 в последней строке означает, что на перевозку единицы товара из склада №3 к заводу С тратится семь условных единиц денег. При этом 350+350+500=350+350+250+250=1200. Следовательно, потребности заводов равны запасам всех складов – это закрытая задача.
Для того чтобы решить транспортную задачу используется множество методов. В зависимости от особенностей задачи используются метод потенциалов, дифференциальных рент (для поиска оптимального плана), метод северо-западного угла, метод наименьшего элемента (для поиска опорного плана) и т.д. До сих пор одним из самых популярных остается симплексный метод в силу его универсальности. Этот метод хорошо реализован в надстройке «Поиск решения», доступной в стандартной программе Excel. Достаточно активировать «Поиск решения» и ввести условия, и вы получите подробное решение.
Подробные примеры: Транспортные задачи с решениями.
Дополнительно:
- Решение контрольных по линейному программированию
- Примеры по линейному программированию
- Учебники и ссылки по линейному программированию
