Решение транспортной задачи методом приоритетных связей

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Решение транспортной задачи методом приоритетных связей

1. Вступление

Главной особенностью метода приоритетных связей при решении транспортной задачи является “многослойность” решения, количество слоев при этом зависит от исходных данных задачи. Формируется решение по каждому из слоев. Окончательным же решением является их сумма.

2. Постановка задачи

2.1 Транспортная задача классическая

Однородный груз сосредоточен у m поставщиков в объемах a₁, a₂, …, a_m. Данный груз необходимо доставить n потребителям в объемах b₁, b₂, …, b_n. Известны c_ij, i = 1, 2, …, m, j = 1, 2, …, n - стоимости перевозки единицы груза от каждого i - го поставщика каждому j - му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, а запросы всех потребителей будут полностью удовлетворены при минимальных затратах на перевозку всех грузов.

Исходные данные транспортной задачи обычно записываются в табличном виде (табл.1).

Таблица 1

i = 1, 2, …, m, (2.1.1.)

j = 1, 2, …, n, (2.1.2.)

x_ij 0_, i = 1, 2, …, m, j = 1, 2, …, n, (2.1.3)

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

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

Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется т поставщиков с запасами однородного груза в количестве a₁, a₂, …, a_m. Данный груз необходимо доставить n потребителям в объемах b₁, b₂, …, b_n.

Известны t_ij, i = 1, 2, …, m, j = 1, 2, …, n - время, за которое груз доставляется от каждого i - го поставщика каждому j - му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и наибольшее время доставки всех грузов является минимальным (табл.2)

Таблица 2

Математическая модель задачи выглядит:

T(X) = max{t_ij} min, при x_ij > 0

где:

x_ij - объем перевозимого груза от i - гo поставщика j - мy потребителю,

T(X) - время, за которое план перевозок будет выполнен полностью.

Транспортная задача классическая

Алгоритм решения

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

На их основе сверху вниз, без разрывов, формируются все возможные приоритетные первичные (их в задаче 30), вторичные (их в задаче 58) и т.д. схемы. Такие схемы, например, будут 1,1 - 2,3 - 3,4 или 1,4 - 3,2, где Х, Х - местоположение данного элемента в исходной матрице.

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

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

В результате анализа всех выявленных приоритетных схем обязательно найдется одно или несколько оптимальных решений.

Первичные (первый слой) схемы дают лишь первичную составляющую решения. После присвоений и вычеркиваний на основе изменившейся исходной матрицы и в зависимости от ее нового вида формируется (или не формируется) вторичная (второй слой) схема и вторичная составляющая решения. Все составляющие решения суммируются в матрицу окончательного плана решения, который умножается на исходную матрицу для получения целевой функции. Всего приоритетных схем решений в этой задаче 63. Из них 9 решений дают оптимальный результат.

В представлении алгоритма решения нет необходимости анализировать все 30 первичных схем. Рассмотрена лишь одна схема, дающая оптимальное решение, и одна - неоптимальное. Вообще же, естественно, при решении задачи обязательно надо анализировать ВСЕ схемы, чтобы выбрать оптимальное решение.

В качестве примера решим транспортную задачу (Матрица 2.1.).

Матрица 2.1.

Сначала определим приоритетные связи (Матрица 2.2.)

Матрица 2.2.

1. Выберем первичную схему 1,1 - 2,4 - 3,2.

Проведем присвоения и вычеркивания (Матрица 2.3.).

Получим результат решения 1 слоя задачи: 1*20 + 2*110 + 3*100 = 540.

Среди оставшихся элементов исходной матрицы (жирные цифры) выявим приоритетные связи и обозначим их (Матрица 2.4.). Здесь только одна вторичная приоритетная схема 1,2 - 2,3.

Получим результат решения 2 слоя: 2*10 + 5*10 = 70.

Результатом решения последнего, третьего слоя является 5*30 = 150. (Матрица 2.5).

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

R = 540 + 70 + 150 = 760.

2. Выберем теперь первичную схему 1,1 - 3,3.

Проведем присвоения (Матрица 2.6.) и вычеркивания (Матрица 2.7.).

Получим результат решения 1 слоя задачи: 1*20 + 7*40= 300.

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

Итак, 1 вариант 2 слоя.

Получим результат решения 1 варианта 2 слоя (Матрица 2.8.):

2*40 + 2*110 +3*60 = 480.

После вычеркиваний получим 1 вариант 3 слоя, т.е. последнего

(Матрица 2.9): 6*10 = 60.

Первый вариант полного решения 300 + 480 +60 = 840.

2 вариант 2 слоя

Получим результат решения 2 варианта 2 слоя (Матрица 2.10.):

2*40 + 4*60 = 320..

После вычеркиваний получим 2 вариант 3 слоя, последнего (Матрица 2.11.):

6*70 + 2*50 = 520.

Второй вариант полного решения 300 + 320 +520 = 1140.

3 вариант 2 слоя

Получим результат решения 3 варианта 2 слоя (Матрица 2.12.):

3*40 + 3*60 = 300.

После вычеркиваний получим 3 вариант 3 слоя, последнего (Матрица 2.13.):

6*50 + 2*70 = 440.

Третий вариант полного решения

300 + 300 +440 = 1040.

Из всех полученных решений (в результате анализа двух выбранных схем), а именно

R = 760, R = 840, R = 1140 , R = 1040 .

Наилучший результат тот, где R = 760

(Матрицы 2.4., 2.5. и 2.6.).

Таким образом, были проанализированы лишь две первичные приоритетные схемы. После анализа всех остальных 28 первичных приоритетных схем и сравнения с остальными 59 полученными результатами решения окажется, что целевая функция R=760 и соответствующий ей план решения (Матрица 2.15.) представляют собой оптимальное решение.

R = 1 · 20 + 2 · 10 + 5 · 30 + 5 · 10 + 2 · 110 + 3 · 100 = 760.

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

Алгоритм решения:

Транспортная задача по критерию времени методом приоритетных связей решается так же, как и классическая. Из полученного оптимального решения извлекаются его временные составляющие, формируется целевая функция T(X) и оптимальный план решения задачи по критерию времени.

Рассмотрим пример решения транспортной задачи по критерию времени (Матрица 2.16.).

Решим эту задачу как транспортную классическую.

Получим следующий оптимальный результат (Матрица 2.17.):

Целевая функция

Z(X) = 5*20 + 4*30 + 2*20 + 4*10 + 5*20 + 5*20 + 4*30 = 580 ед.

Назовем неизвестные единицы (как и тонно-километры) товаро-часами, обозначающими, сколько товаров и за какое время перевезено.

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

T(X) = max(5, 4, 2, 4, 5, 5, 4) = 5,

т.е. все товары будут доставлены потребителям не позднее, чем за 5 временных единиц по следующему плану (Матрица 2.18.)

Решение является оптимальным по следующим соображениям:

Допустим, что имеется решение, в котором максимальная составляющая T(X) меньше, чем 5. Но тогда надо признать, что решение классической транспортной задачи является неоптимальным. А это невозможно, так как оно оптимально.

Значит и T(X) = 5 тоже оптимально, как и план решения.

Разработана программа:

mps_trans.exe - программа решения задачи, в Интернете искать по адресу smetod1.narod.ru/mps_trans.zip;

mps_trans_instruk.doc - инструкция по применению программы решения задачи, в Интернете искать по адресу

smetod1.narod.ru/mps_trans_instruk.doc;

primery_trans_mps.zip - примеры решения задач с ответами. в Интернете искать по адресу smetod1.narod.ru/primery_trans_mps.zip;

3. Глоссарий

Элементарная матрица - матрица размерностью 2х2 (матрица 3.1);

Элементарная связь - воображаемая линия между диагонально расположенными элементами элементарной матрицы (матрицы 3.2 и 3.3);

Приоритетная связь - элементарная связь элементарной матрицы, отражающая решение, направленное на достижение поставленной в задаче цели матрица 3.4 с приоритетной связью, отражающей решение задачи на минимум и матрица 3.5 с приоритетной связью, отражающей решение задачи на максимум.

Схема решения - совокупность соединенных между собой элементарных связей, отражающая одно из решений;

Приоритетная схема решения - совокупность соединенных между собой приоритетных связей;

Оптимальная схема - одна (или несколько) из приоритетных схем, отражающая оптимальное решение;

транспортная задача приоритетная связь

План - одно из допустимых решений, удовлетворяющее системе ограничений и условиям неотрицательности;

Переменные задачи - величины x₁, x₂, …, x_n, которые полностью характеризуют экономический процесс;

Система ограничений - система уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических или физических условий (положительности переменных и др.);

Целевая функция - функция переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти;

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

Размещено на Allbest.ru