Лекции по "Развитию операционных систем"

Лекция 19.

 

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

 

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

по критерию стоимости в матричной форме.

 

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

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

 

Поставщики	Потребители				Запас груза, ai
	B1	B2	…	Bn
A1	c11 x11	c12 x12	…	c1n x1n	a1
A2	c12 x12	c22 x22	…	c2n x2n	a2
…	…	…	…	…	…
Am	cm1 xm1	cm2 xm2	…	cmn xmn	am
Потребность в грузе, bj	b1	b2	…	bn

 

В m пунктах отправления A1, …, Am сосредоточен однородный груз в количествах соответственно a1, …, am единиц. Имеющийся груз необходимо доставить потребителям B1, …, Bn, спрос которых выражается величинами b1, …, bn единиц. Известна стоимость cij перевозки единицы груза из i-го пункта отправления в j-й пункт назначения. Удельные транспортные издержки (расходы) записывают в форме матрицы , которую называют матрицей тарифов. Требуется спланировать перевозки, т.е. указать, сколько единиц груза должно быть отправлено от i-го поставщика j-му потребителю, так, чтобы максимально удовлетворить спрос потребителей и чтобы суммарные транспортные затраты на перевозки были при этом минимальными. Рассмотрим простейший случай, когда суммарные запасы поставщиков равны суммарным потребностям

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

.

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

.           (17.1.1.)

Переменные должны удовлетворять следующим условиям:

1)  ограничения по  запасам:

                      (17.1.2.)

2)  ограничения по  потребностям:

                     (17.1.3.)

3)  условия неотрицательности:

xij ³0  .                                            (17.1.4.)

где cij – стоимость перевозки единицы груза из i-го пункта отправления в j-й пункт назначения;

     - количество груза, сосредоточенного в пункте ;

     - количество груза, необходимое для доставки потребителю .

Если план перевозок удовлетворяет ограничениям (17.1.2) – (17.1.4.), то такой план называется допустимым. Допустимый план перевозок, доставляющий минимум целевой функции называется оптимальным. В следующей теореме, которую примем без доказательства, введем критерий существования допустимого плана.

Теорема 17.1.  (о существовании допустимого плана).

Для того чтобы ТЗ имела допустимые планы, необходимо и достаточно выпол-нение равенства

                                                    (17.1.5.)

 

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

.

Если для ТЗ выполняется одно из условий:

 или  ,

то модель задачи называется открытой.

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

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

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

 

 

17.2.  Построение исходного опорного плана.

 

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

Для построения начального опорного плана в распределительной таблице исполь-зуют такие правила и методы, как правило «северно-западного угла», правило «мини-мального элемента», метод Фогеля.

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

После построения начального опорного плана ТЗ возникает вопрос: как опреде-лить, будет ли построенный план оптимальным? Чтобы ответить на этот вопрос, необхо-димо знать признак оптимальности. Для этого разработан метод потенциалов, который опирается на теорему о потенциалах.

Каждому поставщику (ограничению по запасам) поставим в соответствие число , а каждому потребителю (ограничения по спросу) – число . Числа и называются потенциалами соответственно i-го поставщика и j-го потребителя.

Следующую теорему о потенциалах примем без доказательства.

 

Теорема 17.2.  (теорема о потенциалах).

Если план транспортной задачи является оптимальным, то ему соот-ветствует система из чисел , удовлетворяющих условиям для и для .

 

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

1)  каждой занятой клетке в распределительной таблице соответствует сумма потенциалов, равная тарифу этой клетки, т.е. ;

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

 

 

17.3.  Метод потенциалов.

 

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

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

.

Если для всех свободных клеток оценки , то опорный план перевозок явля-ется оптимальным. Если для опорного плана перевозок указанное условие оптимальности не выполняется, то за счет загрузки свободной клетки с отрицательной оценкой план перевозки улучшается. Для наиболее перспективной свободной клетки строится замк-нутый цикл с вершинами в загруженных клетках. Вершинам этого цикла условно припи-сываются знаки: свободной клетке – знак «+», следующей по часовой или против часовой стрелки занятой клетке – знак «-», следующей – снова «+» и т.д. Из поставок в клетках цикла с «отрицательными» вершинами выбирается наименьшее количество l груза, ко-торое и перемещается по клеткам этого цикла: прибавляется к поставкам в положи-тельных вершинах и вычитается из поставок в отрицательных вершинах, в результате чего баланс цикла не нарушается.

В общем случае цикл представляет собой замкнутую ломаную линию, состоящую из звеньев, пересекающихся под прямым углом. Каждое звено соединяет две клетки строки (столбца). Цикл включает одну свободную клетку, остальные клетки цикла заняты. В цикле всегда четное число клеток. Для свободной клетки всегда можно построить единственный цикл. Если из занятых клеток образуется цикл, то план перевозок не является опорным. Цикл строится лишь для свободных клеток.

 

Сформулируем алгоритм решения ТЗ методом потенциалов:

1)  построить опорный  план;

2)  вычислить потенциалы поставщиков и потребителей и , решив систему уравнений вида ;

3)  вычислить оценки  для всех свободных клеток по формуле . Если , то полученный план является оптимальным. При этом если все , то по-лученный оптимальный план единственный. В случае, если хотя бы одна оценка , имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

Пример 17.1.  В пунктах производится однородная продукция в коли-чествах единиц. Готовая продукция поставляется в пункты , потребности которых составляют единиц. Стоимость cij перевозки единицы продукции из пункта Ai в пункт Bj заданы матрицей :

.

Требуется:

1) методом потенциалов  найти план перевозок продукции, при котором минимизируются суммарные  затраты по ее изготовлению  и доставке потребителям;

2)  вычислить суммарные  затраты fmin.

 

Решение.

1)  Найдем суммарные  запасы продукции и суммарные  потребности  150+380=890; b1+b2+b3+b4=270+190+340+200=1000. Поскольку ,то есть отсутствует баланс между производимой продукцией и потребнос-тями, то мы имеем задачу открытого типа. Вводим фиктивного поставщика A4, который имеет запас продукции в объеме (един.). Все тарифы на доставку продукции фиктивного поставщика равны нулю, т.е. c41=c42=c43=c44=0

Данные задачи заносим в таблицу 1.

Табл. 1.

Поставщики	Потребители				Запас груза, ai
	B1	B2	B3	B4
A1	7	3 160	6	1 200	360
A2	5	2 30	4 120	8	150
A3	3 160	5	7 220	9	380
A4	0 110	0	0	0	110
Потребность в грузе, bj	270	190	340	200	1000