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

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

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

1. Транспортная задача открытого типа

В общем виде транспортная задача формулируется в следующем виде.

Заданы m пунктов отправления с запасами грузов , n пунктов потребления подали заявки на груз в количестве , известна стоимость перевозки единицы груза из i-го пункта отправления в j-й пункт назначения. Вводятся переменные, определяющие количество отправляемых грузов из i-го склада в j-й пункт потребления, - x_ij.

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

. (1)

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

. (2)

Условие выполнения заявок каждого пункта потребления запишется в виде

. (3)

При равенстве количества запасов и заявок пунктов потребления, т.е.

, (4)

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

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

(5)

и допущением, что стоимость перевозки единицы груза между любым пунктом i и фиктивным пунктом равна нулю, т.е. c_i(n+1) = 0, i=.

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

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

Обозначим: r_j - величина ущерба на одну единицу груза в результате невыполнения запроса j-го пункта. Тогда для приведения этой задачи к основной вводится фиктивный пункт отправления А_m+1 с запасами

(6)

и предполагается, что стоимость перевозки единицы груза между этим пунктом и любым пунктом назначения равна нулю, т.е. c_(m+1)j = 0 для всех j=.

Далее минимизируем затраты

, (7)

где y_j - количество груза, «недовезенного» в пункт j при тех же ограничениях и дополнительном условии

. (8)

2. Определение допустимого базисного решения транспортной задачи

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

.

Таким образом, каждой клетке такой матрицы соответствуют два числа x_ij, c_ij, как показано в таблице 1.

Таблица 1

Ai/Bj	B1 …	Bj	… Bn
A1	c11 x11	…	c1n x1n	a1
Ai	…	cij xij	…	ai
Am	cm1 xm1	…	cmn xmn	am
	b1	bj	bn

A₁, …,A_i, …,A_m - обозначения пунктов отправления, B₁,…,B_j,…,B_n - обозначения пунктов назначения.

В матрице перевозок приведены также запасы пунктов отправления и потребности (заявки) пунктов назначения.

В матрице перевозок существуют базисные (занятые) и свободные (незанятые) клетки. Базисные клетки соответствуют базисным переменным, и в них записываются значения базисных неизвестных из допустимого базисного решения (в том числе и нулевые). Свободные клетки, соответствующие свободным переменным, не заполняются, нули в них не записываются. Число базисных переменных в матрице перевозок: r=m+n-1.

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

Первым рассматривается диагональный метод (метод северо-западного угла) на конкретном примере с цифровыми данными, приведенными в таблице 2.

Таблица 2

	В1	В2	В3	В4
А1	2 х11=20	3	2	4	30
А2	3	2	5	1	40
А3	4	3	2	6	20
	20	30	30	10	=90

При этом методе, начиная с угловых объектов, попытаемся удовлетворить потребность пункта В₁ запасами пункта А₁. Это можно сделать, т.к. a₁>b₁. Удовлетворим его, осуществив перевозки х₁₁=20. Пункт В₁ оказывается удовлетворенным полностью, поэтому этот столбец можно временно исключить, в результате получаем таблицу 3.

Таблица 3

	В2	В3	В4	ai
A1	x12=10			a1 30-20=10
A2				40
A3				20
bj	b2=30	30	10	70

Запасы пункта А₁ при этом уменьшаются и становятся равными a₁=30-20=10. Далее попытаемся удовлетворить потребность пункта В₂ (играющего теперь роль первого) запасами пункта А₁. Т.к. b₂ > a₁, то потребности можно удовлетворить лишь частично x₁₂=10 единицами груза из А₁. При этом потребности b₂ сократятся и станут равными b₂=b₂ - a₁=30 -10= 20, при этом запасы пункта А₁ окажутся исчерпанными, и его строку можно исключить, что приводится в таблице 4.

Таблица 4

	В2	В3	В4	ai
A2	x22=10			40
A3				20
bj	b2'=20	30	10	60

Для этой таблицы выбирается х₂₂=20, при этом сокращаются запасы А₂. Они становятся равными a₂ = a₂ - b₂ = 20 единицам груза. Столбец В₂ исключается, получается новая таблица.

Таблица 5

	В3	В4	ai
A2	x23=20		а2'=20
A3	x33=10	x34=10	20
bj	30	10	40

В таблице 5 перевозится в текущем северо-западном углу x₂₃=20, т. к. запасы А₂ составляют только а₂'=20. Исключается строка А₂, а оставшиеся потребности b₃'=b₃ - a₂ '= 10 удовлетворяются перевозками x₃₃=10 и x₃₄=10. Следует заметить, что при каждом шаге удовлетворяется и вычеркивается только один пункт - либо отправления, либо назначения. И только на последнем шаге удовлетворяются одновременно два пункта.

Таким образом, получим для решения задач возможные допустимые значения базисных переменных х₁₁=20, х₁₂=10, х₂₂=20, х₃₃=10, х₂₃=20, х₃₄=10. Общая стоимость перевозок F=290. Это и есть допустимое базисное решение, приведенное в таблице 6.

Таблица 6

	В1	В2	В3	В4
А1	2 х11=20	3 х12=10	2	4	30
А2	3	2 х22=20	5 х23=20	1	40
А3	4	3	2 х33=10	6 х34=10	20
	20	30	30	10	=90

Число базисных переменных равно r=m+n-1=6, т.е. соответствует требуемому числу базисных переменных.

Второй метод нахождения исходных базисных решений транспортной задачи - это метод наименьшей стоимости.

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

Из таблицы следует, что минимальная стоимость перевозок будет между пунктами А₂ и В₄, поэтому полагаем х₂₄=10. Удовлетворяем пункт В₄ и мысленно исключаем этот столбец. Запасы а₂ уменьшились и стали a₂ = a₂ - b₄ = 30. Следующая по цене стоимость «2» перевозок в нескольких клетках. Выбираем пункты А₁ и В₁, полагаем х₁₁=20, тогда a₁ = a₁ - b₁ = 10. Удовлетворяем В₁ и исключаем его (мысленно) из рассмотрения. Затем выбираем клетку 2-2, полагаем х₂₂=30 и исключаем строку А₂, т.к. запасы исчерпаны (но В₂ не исключаем, т.к. два исключения одновременно запрещаются), поэтому удовлетворим В₂, но его «нулевая» потребность осталась.

Рис. 1

Следующей клеткой (по-прежнему с ценой «2») выбираем 1-3, т.к. b₃>a₁, то возьмем x₁₃ = a₁' = 10, исключаем строку А₁. Потребность пункта В₃ уменьшилась до b₃' = b₃ - a₁'=20. Теперь в матрице перевозок осталось два пункта В₂ с нулевой потребностью b₂ =0 и В₃ с потребностью b₃' = 20. Удовлетворяем потребности В₂ и В₃, полагая х₃₂=х₃₃=20. F =170. Таким образом, получили допустимое базисное решение методом наименьшей стоимости.

3. Распределительный метод решения транспортной задачи

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

Для преобразования таблицы используется понятие цикла.

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

- замкнутости;

- в каждой вершине должно встречаться два звена.

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

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

Например, для свободной клетки с координатами (3,3) левой матрицы строится цикл, приведенный на рисунке, и осуществляется сдвиг по циклу на величину 8. В результате получаются новые значения перевозок, приведенные на правой матрице. Клетки, не являющиеся вершинами цикла, при этом остаются без изменений.

Рис. 2

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

- коэффициент равен 0, если соответствующая базисная клетка не является вершиной цикла пересчета данной свободной клетки;

- коэффициент равен 1, если базисная клетка является положительной вершиной цикла пересчета данной свободной клетки;

- коэффициент равен -1, если базисная клетка является отрицательной вершиной пересчета данной свободной клетки.

Например, матрица перевозок имеет 4 пункта отправления и 4 пункта назначения. В ней записано некоторое базисное решение в заштрихованных клетках x₁₁ , x₁₂ , x₂₃ , x₂₄ , x₃₂ , x₄₁ и x₄₃ , число которых должно быть r=m+n-1=7. При этом в каждой строке и каждом столбце таблицы должна быть как минимум одна базисная клетка.

Рис. 3

Построим цикл пересчета для свободной клетки x₁₄ так, чтобы все остальные вершины лежали в базисных клетках. Такой цикл существует только один и приведен в таблице, при этом свободной клетке x₁₄ присваивается знак «+», а знаки всех последующих вершин чередуются при их обходе по циклу в одном направлении.

Таким образом, можно по теореме утверждать, что клетка x₁₄ входит в выражение для неизвестных базисных со знаками:

.

Аналогично можно найти коэффициенты для других свободных неизвестных.

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

Найденное любым методом допустимое базисное решение вносится в матрицу перевозок и занимает r=m+n-1 клеток. Вносятся и нулевые базисные решения. Далее меняются местами базисные и свободные переменные для приближения к оптимальному решению.

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

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

=220 + 310 + 220 + 520 + 210 + 610 = 290.

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

Рис. 4

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

х_{13 13} = с₁₃ - с₂₃ + с₂₂ - с₁₂ = 2 - 5 + 2 - 3 = -4 ,

х_{14 14} = с₁₄ - с₂₄ +с₃₃ - с₂₃ + с₂₂ - с₁₂ = 4 - 6 + 2 - 5 + 2 - 3 = -6 ,

х_{21 21} = с₂₁ - с₁₁ + с₁₂ - с₂₂ = 3 - 2+ 3 - 2 = 2 ,

аналогично ₂₄ = - 8, ₃₁ = 6, ₃₂ = 4.

Выбираем те из свободных переменных, которые имеют отрицательное значение суммы стоимости по циклу пересчета. В рассматриваемом примере это х₁₃, х₁₄, х₂₄.

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

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

Производя преобразования по циклу, мы должны получить нуль в одной из базисных переменных. Кроме того, необходимо учитывать, что переменные не могут принимать отрицательных значений. Поэтому выбирается та базисная переменная, которая имеет наименьшее значение из всех базисных переменных, расположенных в отрицательных вершинах цикла пересчета. В нашем примере это будет х₁₂=10.

Для получения нового допустимого базисного решения осуществляем сдвиг по циклу пересчета выбранной свободной переменной х₁₃ на величину значений выбранной базисной переменной х₁₂=10, которая после сдвига переводится в свободные.

При этом получим новую таблицу матрицы перевозок.

Таблица 7

	В1	В2	В3	В4	ai
A1	2 20	3	2 10	4	30
A2	3	2 30	5 10	1	40
A3	4	3	2 10	6 10	20
bj	20	30	30	10

Сдвиг по циклу привел к новому допустимому базисному решению:

х₁₁=20, х₁₃=10, х₂₂=30, х₂₃=10, х₃₃=10, х₃₄=10, остальные x_ij=0.

Новое решение дает значение целевой функции F=250, меньшее предыдущего, т. е. ближе к оптимальному значению.

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

Для нового базисного решения также подсчитываются суммы стоимостей по циклам пересчета для каждой свободной неизвестной: ₁₂=4, ₁₄=2, ₁₂=4, ₂₁= - 2,₂₄= - 8, ₃₁= 2, ₂₃= 4.

Выбираются новые свободная и базисная переменные для сдвига по новым циклам, и все повторяется. Операция продолжается до тех пор, пока не получится, что все стоимости по циклам пересчета больше нуля (_ij > 0), что является признаком оптимальности решения, полученного распределительным методом.

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

х₁₁=20, х₁₃=10, х₂₂=30, х₂₄=10, х₃₃=10, х₁₂=0, остальные x_ij=0. Стоимость оптимальной перевозки F=170, и уменьшить ее дальше невозможно.

4. Метод потенциалов для решения транспортной задачи

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

- сбалансированная транспортировка.

Таблица 8

	В1 …	Вt	Bq …	Bn	ai
A1	c11				a1
As		cs1 xst	csq xsq		as
Ap		cpt	cpq xpq		ap
Am	cm1			cmn	am
bj	b1	bt	bq	bn

Сущность метода состоит в том, что каждому пункту сопоставляют некоторые векторы, называемые потенциалами пункта: A_ii , B_{j j}. Для определения потенциалов необходимо иметь одно из допустимых базисных решений. Существуют соотношения, показывающие, что алгебраическая сумма стоимости по циклу пересчета свободной клетки равна разности между стоимостью и суммой потенциалов:

. (9)

Свяжем все пункты, соответствующие базисным переменным, уравнениями: _i +_j = c_ij , где c_ij -стоимость перевозки единицы груза из i-го пункта в j-й. Объединение всех уравнений для базисных неизвестных образует систему с числом уравнений r = m + n - 1 и числом неизвестных потенциалов (m+n).

Система уравнений для рассматриваемого общего случая при базисных клетках x_sl , x_sq , x_pq будет

(10)

Решить систему уравнений нетрудно, т.к. ее ранг равен рангу системы ограничений задачи, т.е. r = m + n - 1, и за свободную переменную можно взять любую из неизвестных _i, _j .

В качестве свободной переменной, например, можно принять _S и придать ей произвольное значение (удобно нуль).

Далее рассматривают все базисные неизвестные x_st, которые располагаются в s-й строке матрицы перевозок. Каждой такой неизвестной соответствует в системе определенное уравнение _s + _t = c_st.

Т.к. _s задаются, то из уравнения можно найти _t (например, _s=0, _t= c_st). Так же находятся все остальные _t из s-й строки, например _q=с_sq. После этого останавливаются на одном из найденных , например _q, и рассматривают все те базисные неизвестные x_pq, которые располагаются в q-м столбце матрицы. Каждой такой неизвестной отвечает уравнение: _p + _q = c_pq. Но, т.к. _q найдено ранее (_q= с_sq), то из такого уравнения можно найти _p = c_pq - _q = c_pq - с_sq. Так находятся все _p, соответствующие всем базисным неизвестным x_pq из q-го столбца.

Этот процесс продолжается, пока не будут найдены все _i, _j, т.е. пока не будут определены потенциалы всех пунктов.

5. Алгоритм решения транспортной задачи методом потенциалов

1. Записываются уравнения задачи.

2. Определяется каким-либо способом допустимое базисное решение.

3. С помощью уравнений для базисных клеток находятся потенциалы _i и _j всех пунктов отправления и назначения.

4. Определяется сумма стоимости по циклам пересчета _ij = c_ij - (_i + _j) для всех свободных переменных. Выбирается свободная переменная x_i0j0 , для которой _i0j0 отрицательна и является наибольшей по абсолютной величине. Если таких нет, то это означает, что данное базисное решение оптимально.

5. Для выбранной переменной x_i0j0 строится цикл пересчета и осуществляется сдвиг на величину наименьшего значения базисной переменной в отрицательных вершинах.

6. Далее операции 2 - 5 повторяются, пока не будет получено оптимальное решение, т. е. пока все _ij не станут положительными.

7. Вычисляется общая стоимость перевозок, соответствующая оптимальному решению.

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

транспортный потенциал программирование перевозка

Таблица 9

	В1	В2	B3	B4	ai	i
A1	2 20	3 10	2	4	30	0
A2	3	2 20	5 20	1	40	-1
A3	4	3	2 10	6 10	20	-4
bj	20	30	30	10
j	2	3	6	10

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

Число уравнений равно числу базисных переменных.

Примем в качестве свободной неизвестной ₁, положим ₁ =0.

В первой строке таблицы имеется две базисные неизвестные x₁₁ , x₁₂ , им соответствуют уравнения ₁ +₁ =2 и ₁ +₂ =3. Из этих уравнений находим ₁=2, ₂ =3.

В первом столбце таблицы содержится одна базисная неизвестная x₁₁ , соответствующее ей уравнение уже было использовано.

Во втором столбце кроме x₁₂ содержится базисная переменная x₂₂. Ей соответствует уравнение ₂ +₂ =2. Т. к. ₂ =3, значит ₂ =2 - ₂ = -1.

Во второй строке кроме рассмотренной x₂₂ имеется базисная неизвестная x₂₃. Из соответствующего ей уравнения ₂ +₃ =5 при условии ₂ = -1 следует, что ₃ =5 - ₂ =6.

В третьем столбце кроме базисной x₂₃ есть x₃₃. Из уравнения ₃ +₃ =2 по известному значению ₃ находим ₂ = -4.

И, наконец, из уравнения для базисной неизвестной x_{34 3} +₄ =6 определяем ₄ =6 - ₃ =10.

Теперь можно найти алгебраическую сумму стоимостей по циклу пересчета свободных переменных. Так, для свободной переменной x₁₃ имеем ₁₃ = с₁₃ - - (₁ +₃) =2 - (0+6) = - 4. Аналогично находим

₁₄ = -6 , ₂₁ =2, ₂₄ = - 8, ₃₁ =6, ₃₂ =4.

Далее выбирается свободная неизвестная, для которой _ij отрицательна и имеет наибольшую абсолютную величину (в нашем случае это ₂₄ = - 8, и для нее будет x₂₄). Для выбранной переменной определяется цикл пересчета и осуществляется сдвиг по циклу на наименьшее значение базисной неизвестной в отрицательной вершине.

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

5. Решение транспортной задачи по критерию времени

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

a_i - запасы груза пункта отправления;

b_j - потребности груза в пунктах назначения;

t_ij - время доставки груза из i-го в j-й пункт.

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

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

Для решения этой задачи используется метод разгрузочных цепей.

Алгоритм решения состоит из следующих шагов

Вносятся исходные данные a_i, b_j, t_ij в матрицу перевозок.

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

Определяется максимальное время реализации, записанного в матрице решения задачи, т.е. .

Исследуется клетка с максимальным временем i₁j₁ на возможность разгрузки, т.е. проверяется в матрице решение на оптимальность. Признаком оптимальности решения транспортной задачи по критерию времени является невозможность построения разгрузочной цепи для клетки с максимальным t_ij.

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

Разгрузочная цепь является замкнутым циклом, который охватывает как базисные, так и свободные клетки. При этом в разгрузочную цепь не должны входить свободные клетке с t_ij больше максимального . Разгружаемая цепь изображается всегда так, что разгружаемой клетки приписывается знак «-» и в отрицательных вершинах обязательно находятся базисные переменные.

Пример. Исходное допустимое базисное решение, найденное, например, диагональным методом, приведено в таблице:

Таблица 10

	В1	В2	В3	В4	ai
А1	20 20	5 5	10	20 X	25
А2	10	15 15	10	5	15
А3	10	10 5	5 15	5	20
А4	5	8	8 5	10 30	35
bj	20	25	20	30

Далее вычеркиваем все свободные клетки с t_ij t₁₁, чтобы не использовать их для цикла переноса (это клетка t₁₄).

Пытаемся разгрузить клетку 1,1. Она имеет сейчас несколько разгрузочных цепей: а) 1,12,12,21,2; б) 1,13,13,21,2; в) 1,13,13,31,3; г) 1,14,14,31,3.

Однако ни одна из них не позволяет разгрузить клетку за один прием: вначале разгрузим ее на величину 15 по циклу (а), а затем по циклу (б) на величину 5.

В результате получим новое решение в таблице:

Таблица 11

	В1	В2	В3	В4	ai
А1	20 Х	5 25	10 Х	20 X	25
А2	10 15	15 Х	10 Х	5	15
А3	10 - 5	10 Х	5 + 15	5	20
А4	5 +	8	8 - 5	10 30	35
bj	20	25	20	30

Для этого решения max(t_ij)=t₂₁=t₃₁=t₄₄=10. Вычерчиваем все свободные клетки с t_ij10, это 1,3; 2,3; 3,2 и, конечно, 1,1 и 2,2.

Попытаемся разгрузить клетки 2,1; 3,1; 4,4. Клетку 3,1 можно разгрузить по циклу 3,14,14,33,3. Выполним операцию сдвига на х₃₁=5 и получим решение в следующей таблице 11.

Теперь разгрузим клетку 2,1 по циклу 2,14,14,42,4, а затем клетку 4,4 по циклу 4,44,33,33,4. В результате получим решение, данное в таблице 12.

Для реализации этого решения требуется max(t_ij)=t₄₃=8.

Таблица 11

Таблица 12

	В1	В2	В3	В4	ai
А1	20 Х	5 25	10 Х	20 X	25
А2	10 Х	15 Х	10 Х	5 15	15
А3	10 Х	10 Х	5 5	5 15	20
А4	5 20	8 Х	8 15	10 Х	35
bj	20	25	20	30

Вычеркнем из таблицы свободные клетки с t8, (т.е. клетку 4,2). Попытаемся разгрузить клетку 4,3. Сделать этого нельзя, т.к. в 4-й строке и в 3-м столбце нет незачеркнутых свободных клеток. Следовательно, решение, записанное в таблице, является оптимальным по критерию времени и найти план, который можно реализовать за время меньше t_ij=8, невозможно.

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

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

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

Рис. 5

Граф может быть неориентированным, если связь по всем ветвям двухсторонняя, или ориентированным, если имеют место односторонние (т.е. в одном направлении) связи между отдельными узлами, например 12 на рис. 5

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

Каждая ветвь характеризуется двумя параметрами. Один параметр - это емкость или пропускная способность _ij, которая ограничивает возможности передачи определенного объема информации между пунктами i и j. На рис. 5, например, пропускная способность односторонней ветви ₁₂ = 15, а двухсторонних, совпадающая в обоих направлениях, - ₁₅ = ₅₁ = 15, ₃₄ = ₄₃ = 10, ₂₃ = ₂₃ = 20 и т.д.

Второй параметр каждой ветви зависит от выбранного критерия оптимизации. Это может быть и длина ветви l_ij, и стоимость передачи единицы информации c_ij по данной ветви, и другие параметры. Как отмечено выше, для двухсторонних ветвей эти параметры могут не совпадать, например на рис. 5. Стоимость, указанная в скобках, для ветви с₄₃=8, а с₃₄=7.

Для полной характеристики сети используются матрица пропускных способностей (емкостей) В и, например, матрица стоимостей С, соответствующие приведенной на рис. 5 сети связи

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

это будет означать, что требуется передать потоки с объемами информации _2-5 = 16 и _1-3 = 15.

Возможные пути передачи потоков информации удобно представить в виде деревьев путей. В конкретном случае, если ограничиться только тремя ярусами (более длинные пути явно нецелесообразны), деревья путей можно представить в виде, приведенном на рис. 6.

В качестве переменных х_i целесообразно выбрать величины потоков информации, передаваемой по i-му пути. Число переменных будет определяться количеством путей входящих в построенные деревья путей.

Для составления математической модели задачи удобно использовать таблицу путей где каждому потоку Ф соответствует набор путей с количеством передаваемой информации х_i.

Рис. 6

Таблица 13

Ф	Пути	xi	Пропускные способности ветвей и стоимости	Стоимость пути С
			12 15	15=51 15	23=32 20	24=42 10	34 10	43 10	35=53 15	45=54 15
2-5	2-3-5	x1			5				9		14
	2-4-5	x2				6				2	8
	2-4-3-5	x3				6		8	9		23
	2-3-4-5	x4			5		7			2	14
1-3	1-2-3	x5	3		5						8
	1-5-3	x6		4					9		13
	1-2-4-3	x7	3			6		8			17
	1-5-4-3	x8		4				8		2	14

Стоимость пути складывается из стоимости передачи единицы информации по каждому из составляющих ветвей. Так стоимость первого пути с₁ = с₂₃ + + с₃₅ = 14.

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

Математическая модель задачи имеет целевую функцию, соответствующую оптимизации-минимизации стоимости передачи информации:

(11)

В частности, из таблицы путей следует F = 14x₁ + 8x₂ + 23x₃ + 14x₄ + 8x₅ + + 13x₆ + 8x₅ + 13x₆ + 17x₇ + 14x₈ min.

В качестве ограничений выступают следующие требования:

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

х₁ + х₂ + х₃ + х₄ = ₂₅ = 16,

х₅ + х₆ + х₇ + х₈ = ₁₃ = 15. (12)

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

х₅ + х₇ 15,

х₆ + х₈ 15,

х₁ + х₄ + х₅ 20,

х₂ + х₃ + х₇ 10,

х₄ 10, (7.13)

х₃ + х₇ + х₈ 10,

х₁ + х₃ + х₆ 15,

х₂ + х₄ + х₈ 15.

3. Потоки информации не могут принимать отрицательных значений, т.е. х_i 0.

Целевая функция (11) и система ограничений (12) и (13) позволяют решать и исследовать задачу оптимизации сети связи методом линейного программирования.

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

...