Транспортная задача относится к типу специальных задач линейного программирования, обладающих некоторыми особенностями, с учётом которых могут быть разработаны упрощённые методы решения, значительно более экономные по сравнению с принятыми. В классической постановке транспортная задача заключается в поиске такого плана перевозок продукции одного типа (однородной, взаимозаменяемой) из пунктов производства в пункты потребления, при котором затраты на перевозку минимальны (см., например, [1, 3, 6]).

Первая строгая постановка данной задачи принадлежит Хичкоку, а её детальное рассмотрение и разбор – Купмансу. Данциг сформулировал транспортную задачу как задачу линейного программирования и разработал первые методы её решения. Многие литературные источники, посвящённые линейному программированию, так или иначе упоминают, затрагивают транспортную задачу (см., например, [1, 6]). Целиком посвящена классу транспортных задач и методам их решения монография Е.Г. Гольштейна, Д.Б. Юдина [3].

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

Постановка транспортной задачи

Существуют замкнутая и открытая транспортная модель. Формулировка транспортной задачи в виде замкнутой транспортной модели заключается в следующем: имеется m пунктов производства ) и n пунктов потребления ) однородной, взаимозаменяемой продукции. Для каждого пункта производства заданы объёмы производства a_i, а для каждого пункта потребления – величины спроса b_j в одних и тех же единицах измерения:

Расходы, связанные с перевозкой единицы продукта из i-ого пункта в j-ый, заданы величиной c_ij и известны для каждой пары (i, j). Можно представить эти расходы в виде матрицы размерностью m×n:

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

Искомое количество единиц продукта, поставленное из i-ого пункта в j-ый, определяется величиной x_ij. Количество перевезённой продукции неотрицательно:

Можно представить перевезённую продукцию в виде матрицы размерностью m×n:

Исходные данные удобнее всего представляются в виде таблицы (таблица).

Исходные данные задачи

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

Минимизируются суммарные расходы на перевозку всей продукции (из всех пунктов производства во все пункты потребления):

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

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

т.е. объём продукции, имеющейся в пунктах производства, должен совпадать с объёмом продукции, требуемым в пунктах потребления.

Для представления условий задачи в матричном виде требуется ввести в рассмотрение векторы Pij и Р.

Pij – вектор коммуникации, соответствующий коммуникации, которая связывает i-ый пункт производства с j-ым пунктом потребления, и состоящий из (n + m) компонент, из которых i-я и (m + j)-я равны единице, а все остальные – нулю:

Р – вектор производства – потребления, состоящий из объёмов производства a_i и величин спроса b_j:

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

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

тогда справедливо следующее условие:

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

В таком случае справедливо условие

Открытую транспортную модель можно привести к замкнутой. Если объём продукции в пунктах производства больше требуемого объёма продукции на пунктах потребления, то вводится фиктивный пункт потребления B_{n +1} с объёмом потребления

Величина b_{n +1} определяет суммарный объём нереализованного продукта.

Стоимость перевозок от каждого поставщика в такой фиктивный пункт потребления – нулевая:

Если объём продукции в пунктах производства меньше требуемого объёма продукции на пунктах потребления, то вводится фиктивный пункт производства A_{m +1} с объёмом поставок

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

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

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

В работе [9] в качестве целевой функции рассматривается минимизация максимального среди всех потребителей числа поставщиков. Несмотря на название («Многокритериальная транспортная задача с разрывной целевой функцией») решается задача при помощи стандартных методов линейного программирования.

В работе [4] в качестве условий рассмотрены: минимизация времени нахождения в пути из пункта производства в пункт потребления продукции, минимизация общей себестоимости перевозки единицы груза, максимизация общего количества перевезённых грузов. Предлагается решать задачу с использованием методов Парето, устанавливая приоритеты критериев, или с использованием интеллектуальных методов нейросетевого прогнозирования. В данном случае определение приоритетов и выделение главного критерия является одним из самых простых методов многокритериального линейного программирования.

В работе [5] минимизировать предлагается расстояние между пунктами назначения перевозки, время транспортировки груза, тарифы перевозки и стоимость перевозки. В качестве решения такой задачи рассматриваются два метода: первый, как и в работе [4], заключается в установлении приоритетов критериев и выделении главного критерия, а второй – в свёртывании критериев и введении одного агрегированного критерия.

Рассмотрим более сложную для решения модификацию транспортной задачи с двумя целевыми функциями. Для этого введём матрицу H размерностью m×n. Элемент h_ij матрицы H определяет степень важности перевозки продукта из i-ого пункта производства в j-ый пункт потребления. Степень важности перевозки для каждой пары (i, j) может задаваться, например, экспертами:

Соответственно, добавляемая целевая функция заключается в максимизации степени важности перевозок:

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

при условиях

или в матричном виде:

Для открытой модели многокритериальной транспортной задачи справедливо одно из условий (в зависимости от типа открытой модели):

либо

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

При приведении открытой транспортной модели к замкнутой важность перевозки из фиктивного пункта производства A_{m +1} или в фиктивный пункт потребления B_{n +1} будет нулевой:

Решение поставленной задачи может быть найдено при помощи многокритериального симплекс-метода, основанного на построении множества Парето в задаче многокритериального линейного программирования [7, 8, 10].

Заключение

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