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

3.1. Общие положения теории транспортной задачи

3.1.1. Классическая постановка транспортной задачи

Пусть имеется m поставщиков однородного груза в количествах соответственноединиц иn потребителей этого груза, потребность которых составляет соответственноединиц.

Известны стоимости перевозок единицы груза от i-го поставщика к j-тому потребителю - .

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

Замечание. Перевозимый груз должен быть однородным, например песок, уголь, лес, кирпичи, металл и т.п. Единицы измерения количества груза могут быть различными (т, м³, шт., л и т.п.). Стоимость перевозки измеряется, как правило, в рублях. Предполагается, что стоимость перевозимого груза пропорциональна его количеству. В качестве поставщиков могут выступать предприятия, базы, склады, а в качестве потребителей – предприятия, магазины, строительные объекты и т.п.

Таблица 3.1

					…			…
					…			…
					…			…
…	…		…		…	…		…	…
					…			…
…	…		…		…	…		…	…
					…			…

Прежде, чем приступить к построению модели задачи, необходимо обозначить неизвестные. Исходя из условия задачи, неизвестной величиной является количество единиц груза, перевозимого от каждого поставщика к каждому потребителю. Обозначим через – количество единиц груза, перевозимого отi-го поставщика к j-му потребителю.

Чтобы лучше представить условие задачи, сведем исходные данные в табл. 3.1. Строка таблицы соответствует поставщику, а столбец – потребителю.

3.1.2. Модели транспортной задачи.

При постановке конкретных задач перевозки грузов может возникнуть одна из трех ситуаций:

1) количество груза у всех поставщиков () равно потребности в данном грузе всех потребителей ():

(3.1)

или

(3.2)

2) количество груза у всех поставщиков () больше потребности в данном грузе всех потребителей ():

(3.3)

или

(3.4)

3) количество груза у всех поставщиков () меньше потребности в данном грузе у всех потребителей ():

(3.5)

или

(3.6)

Каждой ситуации соответствует определенная модель транспортной задачи.

Рассмотрим ситуацию (1), которой отвечает соотношение (3.2). Объектом исследования в транспортной задаче является планирование перевозок грузов. Цель исследования задачи - составление плана перевозки грузов, обеспечивающего минимальные транспортные расходы. Критерий задачи – минимальные транспортные расходы. Отразим критерий задачи в целевой функции. Стоимость перевозки единицы груза от i-го поставщика к j-му потребителю составляет , а груза перевозитсяединиц. Следовательно, стоимость перевозки всего груза отi-го поставщика j-му потребителю будет равна величине . Учитывая, что суммарная стоимость перевозки грузов от всех поставщиков ко всем потребителям должна быть минимальной, целевая функция транспортной задачи должна иметь вид:

(3.7)

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

Первая группа ограничений, количество которых равно m (количество поставщиков), отражает тот факт, что весь груз, имеющийся у поставщиков, должен быть вывезен:

(3.8)

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

(3.9)

Количество перевозимого груза от i-го поставщика к j-му потребителю должно быть величиной неотрицательной. Следовательно, в модель необходимо добавить ограничения неотрицательности переменных:

(3.10)

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

(3.11)

Для того, чтобы транспортная задача (3.11) была разрешима, т.е. имела оптимальный план, необходимо и достаточно выполнение условия (3.2).

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

(3.12)

В ситуации (3), которой отвечает соотношение (3.6), всем потребителям нужно больше груза, чем имеется у поставщиков. Поэтому каждый поставщик весь свой груз вывезет, а часть потребителей получат груза меньше необходимого количества и уже ограничения второй группы примут вид «»:

(3.13)

Модель (3.11) является закрытой моделью транспортной задачи, а соответственная ей задача - сбалансированной. Модели, отвечающие соотношениям (3.4) и (3.6), называются открытыми. Задачи будут несбалансированные. Количество переменных в модели равно (), а количество ограничений - ().

Чтобы решить транспортную задачу, описываемую открытой моделью, её необходимо сбалансировать или, по-другому, открытую привести к закрытой. Достигается это следующим образом:

В ситуации (2), когда , вводится фиктивный потребительc потребностью . К левой части каждого ограничения первой группы прибавляется соответственно неотрицательная переменная, во вторую группу ограничений добавляется ограничение, соответствующее фиктивному потребителю:

(3.14)

В таблицу исходных данных задачи (табл. 3.1) добавляется столбец.

В ситуации (3), когда , вводится фиктивный поставщикс наличием груза в количестве.

К левой части каждого ограничения второй группы прибавляется соответственно неотрицательная переменная , в первую группу ограничений добавляется ограничение, соответствующее фиктивному поставщику:

(3.15)

В таблицу исходных данных задачи (табл. 3.1) добавляется строка.

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

Переход от открытой модели к закрытой фактически означает приведение модели транспортной задачи к канонической форме без учета требования максимизации целевой функции.

Замечание. Предположение, что для фиктивного поставщика , приводит к неудовлетворению некоторых потребителей. Среди них могут оказаться те, потребности которых необходимо обязательно удовлетворить. Поэтому стоимости перевозок от фиктивного поставщика к потребителям, потребности которых следует обязательно удовлетворить, устанавливаются значительно большими по сравнению с заданными стоимостями перевозок. В результате принятых мер перевозки от фиктивного поставщика к указанным потребителям планироваться не будут и их потребности удовлетворят только реальные поставщики. Рассмотренный метод получил названиеметода запрещения перевозок. Он может применяться и для другого варианта открытой модели транспортной задачи, когда выдвигаются требование - у определенных поставщиков весь груз вывести, а также в случае, если груз от конкретного поставщика к конкретному потребителю по каким-либо причинам (например, отсутствие транспортных путей) не может быть доставлен. Обычно при запрещении определенной перевозки её стоимость принимается равной большому числу (М), значительно превышающему по своему значению другие стоимости перевозок.