Транспортная задача по критерию времени

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

Как и для классической транспортной задачи, имеем m поставщиков с запасами однородного груза в количестве a1, a2, am и n потребителей, которым этот груз нужно доставить в объеме b1, b2, bn Допустим, щ що

m n

выполняется условие баланса: 2 at = 2bj Обозначим через Ху объем груза от z'-ro поставщика j-му потребителю Известен также время ty (i = 1, m; j = 1, n), за какой груз перевозится от z'-ro поставщика j-му потребителю, и допускается, что он не зависит от 06сягив Перевозок ХХу.

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

Составим математическую модель решения такой управленческой проблемы Система ограничений этой задачи не отличается от системы ограничений классической транспортной задачи Обозначим через T максимальную вели ичину из всех возможных значений ty, соответствующие ненулевым перевозкам (ху 0): T = max t \"

Критерием оптимальности плана перевозок является минимальная продолжительность всех перевозок Следовательно, математическая модель имеет вид:

T = max ty - \"min, 2 ху ai, i = 1, m;

m -

2 Ху ^ bj, j = 1, n;

1 = 1

Ху 0, i = 1, m; у = 1, n

Транспортная задача по критерию времени не относится к задачам линейного программирования, поскольку ее целевая функция не линейная от переменных Ху Решение этой задачи можно свести к последовательному розвьяза Ання нескольких задач линейного программированияя.

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

n

коэффициентов равна единице: 2аi = 1 в) нормирование или нормализация

и = и

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

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

F (X) = L (X), T (X) - min;

m n

L (X) = Т ^ ЦСуХу - min;

mn

T (X) = tjXij - min

где cj, tj - стоимость и время перевозки единицы груза от 7-го поставщика j-му потребителю

Через D здесь обозначено допустимую множество решений, описывается системой

2 Xj at, i = 1, m;

m - Z xij bj, j = 1, n;

Xj 0, i = 1, m; j = 1, n

Сразу достичь наилучшего результата по всем показателям, как правило, невозможно, поэтому эта задача сводится к скалярной транспортной задачи с помощью свертки критериев качества в одного критерия:

F (X) = а, LX) ~ Lmin а2 TX) ~ Tmin ^ min

Lmax Lmin Tmax Tmin

где АШП = тип ДХИтж = тах ДХX

Ттип = ИП Т (Х) 'Ттах = Т (Х)

Обобщенный критерий и (Х включает нормализацию критериев качества и учитывает важность критериев с помощью коэффициентов веса а1 и а2, которые может менять лицо, принимает управленческие решения для с увеличение (уменьшение) важности критериев После получения скалярной транспортной задачи она решается стандартными методами.