Постановка и модель транспортной задачи в различных формах записи

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

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

Таким образом, пусть имеем m пунктов, в которых находится известное количество однородных грузов (поставщики). Порядковый номер поставщика обозначается i, то есть i=1,2,…, m. Наличие грузов у поставщика bi. Имеется n пунктов испытывающих потребность в этих грузах (потребителей). Порядковый номер потребителя j=1,2,…, n. Потребность в грузах каждого потребителя aj. Известна «цена» перевозки единицы груза от каждого поставщика к каждому потребителю (сij). Необходимо составить план перевозки грузов от поставщиков к потребителю, т. е. определить: какое количество груза необходимо перевезти от каждого поставщика к каждому потребителю (xij), причем значения xij должны отвечать следующим требованиям:

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

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

— условие разрешимости задачи.

Если условие разрешимости выполняется, то задача будет являться задачей, так называемого закрытого типа (сбалансированной). Иначе — задача открытого типа (несбалансированная). Для того чтобы решить задачу открытого типа, надо её «закрыть» (то есть привести к закрытому типу). Для этого вводится или фиктивный поставщик или фиктивный потребитель.

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

.

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

.

Введение

фиктивного потребителя или отправителя повлечет необходимость формального задания фиктивных тарифов (реально не существующих) для фиктивных перевозок. Поскольку нас интересует определение наиболее выгодных реальных перевозок, то необходимо предусмотреть, чтобы при решении задачи (при нахождении опорных планов) фиктивные перевозки не рассматривались до тех пор, пока не будут определены все реальные перевозки. Для этого надо фиктивные перевозки сделать невыгодными, чтобы при поиске решения задачи их рассматривали в самую последнюю очередь. Таким образом, если целевая функция стремится к min, то затраты берутся во всех фиктивных клетках таблицы произвольные, одинаковые и на порядок выше настоящих цен, т. е. величина фиктивных тарифов должна превышать максимальный из реальных тарифов, используемых в модели:. Если целевая функция стремится к max, то берётся равная нулю.

Развёрнутая форма записи модели транспортной задачи.

Для удобства, прежде чем писать модель, запишем в виде матрицы цен все значения cij. А также в виде матрицы грузоперевозок переменные xij.

Матрица цен:

С =.

Матрица С = (cij)m*n называется также матрицей тарифов (издержек или транспортных расходов).

Матрица грузоперевозок:

Х =.

Матрица Х = (хij)m*n еще называется планом транспортной задачи.

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

I. Целевая функция описывает затраты на перевозку грузов:

Z=c11×11+c12×12+…+c1nx1n+c21×21+c22×22+…+c2nx2n+… +cm1xm1+cm2xm2+…+cmnxmnmin.

II. Система ограничений описывает второе и третье требования для xij из постановки задачи.

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

x11+x12+…+x1n = b1,.

x21+x22+…+x2n = b2,.

…

xm1+xm2+…+xmn = bm;

2 группа: условие удовлетворения потребителя (сумма грузов привезённых потребителю должна быть равна его потребности):

x11+x21+…+xm1=a1,.

x12+x22+…+xm2=a2,.

…

xm1+xm2+…+xmn = аn.

III. Условие неотрицательности переменных величин x110, x120, …, xmn0.

Структурная форма записи модели транспортной задачи.

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

II.

III. xij0 (i = 1,2,…, m, j = 1,2,…, n).

Табличная форма записи модели транспортной задачи.

Общепринято в таблице информацию по поставщикам располагать по строкам, по потребителю — по столбцам.

Размер таблицы: cтрок m+2, cтолбцов n+2.

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

Если в таблицу записана только исходная информация и нет значений xij, то это рабочая таблица или макет задачи. Если значения xij проставлены, то получаем первый вариант решения задачи. В такой форме задачи решаются.

Кроме основных условий, в транспортных задачах может встретиться ряд дополнительных, ограничивающих количественные связи между отдельными потребителями и поставщиками. Характер этих ограничений и способы решения задачи при наличии дополнительных ограничений заключаются в следующем.

• 1. Полное отсутствие связи между поставщиком и потребителем, то есть xij = 0. Это означает, что в данной клетке матрицы искомый объем перевозок должен быть равен нулю. В этом случае оценка переменной завышается на большую величину, обычно обозначаемую буквой М, и «попадание» груза в эту клетку нежелательно, так как целевая функция стремиться к минимуму (и занижается, если Zmax).
• 2. Наличие частной заранее фиксированной связи между поставщиками и потребителями, то есть xij = q (искомый объем перевозок от i-го поставщика к j-му потребителю должен быть строго равен q). Тогда, до начала решения задачи от величины грузов соответствующего поставщика и потребителя вычитается величина q, затем в соответствующую клетку пересечения поставщика и потребителя записывается завышенная оценка М (при Zmin и заниженная при Zmax) и задача решается обычным методом.
• 3. xij? q, то есть искомый объем перевозок от i-го поставщика к j-му потребителю должен быть не меньше величины q. В этом случае до начала решения от величины грузов соответствующего поставщика и потребителя вычитается величина q, затем задача решается обычным путем.

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