Модели оптимального объема производства

V₁ + u₃ = c₃₁ v₁ + u₃ = 2 v₁ = 2 - 8 = -6



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

Таблица 2.14

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30	Ui
S1 =25	6	10	4	7	U1=7
S2 = 45	9	12	6	4	U2=4
S3 = 30	2	3	5	8	U3=8
Vj	V1=-6	V2=8	V3=2	V4=-0

G₁₁ = c₁₁ - ( u₁ + v₁ ) = 6 - ( 7 + (-6) ) = 5

G₁₂ = c₁₂ - ( u₁ + v₂ ) = 10 - ( 7 + 8) = -5

G₁₃ = c₁₃ - ( u₁ + v₃ ) = 4 - ( 7 + 2 ) = -5

G₂₁ = c₂₁ - ( u₂ + v₁ ) = 9 - ( 4 + (-6) ) = 11

G₃₂ = c₃₂ - ( u₃ + v₂ ) = 3 - ( 8 + 8 ) = -13

G₃₃ = c₃₃ - ( u₃ + v₃ ) = 5 - ( 8 + 2 ) = -5

Оценка свободной ячейки S₁M₃ (незадействованного маршрута) отрицательная (G₁₃ = -5), следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки S₁M₃ :

Ячейки образующие цикл для свободной ячейки S₁M₃: S₁M₃, S₁M₄, S₂M₄, S₂M₃

Пусть ячейка S₁M₃ , для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла S₁M₄, S₂M₃ , номера которых четные, найдем ячейку, обладающую наименьшим значением.

Min = {25,30} = 25

В данном случае, это ячейка S₁M₄.

Другими словами, из маршрута доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика S₁ к потребителю M₄, по которому доставляется меньше всего (25) единиц продукции. Данный маршрут мы исключаем из схемы доставки продукции.

От ячеек цикла с четными номерами отнимаем 25. К ячейкам с нечетными номерами прибавляем 25.

Таблица 2.15

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30
S1 =25	6	10	4 +25	7 25-25
S2 = 45	9	12 10	6 30-25	4 5+25
S3 = 30	2 30	3	5	8

Таблица 2.16

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30
S1 =25	6	10	4 25	7
S2 = 45	9	12 10	6 5	4 30
S3 = 30	2 30	3	5	8

Z= 2*30+12*10+4*25+6*5+4*30=430 ден.ед.

ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.

Каждой строке Si ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому столбцу Mj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки SiMj)

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

Примем u₂ = 0

V₂ + u₂ = c₂₂ v₂ + u₂ = 12 v₁ = 12 - 0 = 12

V₃ + u₂ = c₂₃ v₃ + u₂ = 6 v₃ = 6 - 0 = 6

v₄ + u₂ = c₂₄ v₄ + u₂ = 4 v₄ = 4 - 0 = 4

v₄ + u₃ = c₃₄ v₄ + u₃ = 8 u₃ = 8 - 4 = 4

v₃ + u₁ = c₁₃ v₃ + u₁ = 4 u₁ = 4 - 6 = -2

v₁ + u₃ = c₃₁ v₁+ u₃ = 2 v₁ = 2 - 4 = -2

Таблица 2.17

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30	Ui
S1 =25	6	10	4	7	U1=-2
S2 = 45	9	12	6	4	U2=0
S3 = 30	2	3	5	8	U3=-4
Vj	V1=-2	V2=12	V3=6	V4=4

G₁₁ = c₁₁ - ( u₁ + v₁ ) = 6 - ( -2 + (-2) ) = 10

G₁₂ = c₁₂ - ( u₁ + v₂ ) = 10 - ( -2 + 12) = 0

G₁₄ = c₁₄ - ( u₁ + v₄ ) = 7 - ( -2 + 4 ) = 5

G₂₁ = c₂₁ - ( u₂ + v₁ ) = 9 - ( 0 + (-2)) = 11

G₃₂ = c₃₂ - ( u₃ + v₂ ) = 3 - ( 4 + 12 ) = -13

G₃₃ = c₃₃ - ( u₃ + v₃ ) = 3 - ( 4 + 6 ) = -5

Оценка свободной ячейки S₃M₂ (незадействованного маршрута) отрицательная (G₃₂ = -13), следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки S₃M₂ :

Ячейки образующие цикл для свободной ячейки S₃M₂:

S₃M₂, S₃M₄, S₂M₄, S₂M₂

Пусть ячейка S₃M₂ , для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла S₃M₄, S₂M₂ , номера которых четные, найдем ячейку, обладающую наименьшим значением.

Min = {0,10} = 0

В данном случае, это ячейка S₃M₄.

Другими словами, из маршрута доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика S₃ к потребителю M₄, по которому доставляется меньше всего (0) единиц продукции. Данный маршрут мы исключаем из схемы доставки продукции.

От ячеек цикла с четными номерами отнимаем 0. К ячейкам с нечетными номерами прибавляем 0.

Таблица 2.15

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30
S1 =25	6	10	4 25	7
S2 = 45	9	12 10-0	6 5	4 30+0
S3 = 30	2 30	3 +0	5	8 0-0

Таблица 2.16

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30
S1 =25	6	10	4 25	7
S2 = 45	9	12 10	6 5	4 30
S3 = 30	2 30	3	5	8

Z= 2*30+12*10+4*25+6*5+4*30=430 ден.ед.

ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.

Каждой строке Si ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. Каждому столбцу Mj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки SiMj)

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

Примем u₂ = 0 V₂ + u₂ = c₂₂ v₂ + u₂ = 12 v₂ = 12 - 0 = 12

V₃ + u₂ = c₂₃ v₃ + u₂ = 6 v₃ = 6 - 0 = 6

v₄ + u₂ = c₂₄ v₄ + u₂ = 4 v₄ = 4 - 0 = 4

v₂ + u₃ = c₃₂ v₂ + u₃ = 3 u₃ = 3 - 12 = -9

v₃ + u₁ = c₁₃ v₃ + u₁ = 4 u₁ = 4 - 6 = -2

v₁ + u₃ = c₃₁ v₁+ u₃ = 2 v₁ = 2 - (-9)= 11

Таблица 2.17

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30	Ui
S1 =25	6	10	4	7	U1=-2
S2 = 45	9	12	6	4	U2=0
S3 = 30	2	3	5	8	U3=- -9
Vj	V1=11	V2=12	V3=6	V4=4



G₁₁ = c₁₁ - ( u₁ + v₁ ) = 6 - ( -2 + 11 ) = -3

G₁₂ = c₁₂ - ( u₁ + v₂ ) = 10 - ( -2 + 12) = 0

G₁₄ = c₁₄ - ( u₁ + v₄ ) = 7 - ( -2 + 4 ) = 5

G₂₁ = c₂₁ - ( u₂ + v₁ ) = 9 - ( 0 + 11) = -2

G₃₃ = c₃₃ - ( u₃ + v₃ ) = 5 - ( -9 + 6 ) = 8

G₃₄ = c₃₄ - ( u₃ + v₃ ) = 8 - ( -9 + 4 ) = 13

Оценка свободной ячейки S₁M₁ (незадействованного маршрута) отрицательная (G₁₁ = -3), следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки S₁M₁ :

Ячейки образующие цикл для свободной ячейки S₁M₁:

S₁M₁, S₁M₃, S₂M₃, S₂M₂, S₃M₂, S₃M₁

Пусть ячейка S₁M₁ , для которой мы строили цикл, имеет порядковый номер один. Среди ячеек цикла S₁M₃, S₂M₂ , S₃M₁, номера которых четные, найдем ячейку, обладающую наименьшим значением. Min = {25,10,30} = 10 В данном случае, это ячейка S₂M₂. Другими словами, из маршрута доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика S₂ к потребителю M₂, по которому доставляется меньше всего (10) единиц продукции. Данный маршрут мы исключаем из схемы доставки продукции. От ячеек цикла с четными номерами отнимаем 10. К ячейкам с нечетными номерами прибавляем 10.

Таблица 2.15

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30
S1 =25	6 +10	10	4 25-10	7
S2 = 45	9	12 10-10	6 5+10	4 30
S3 = 30	2 30-10	3 0+10	5	8



Таблица 2.16

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30
S1 =25	6 10	10	4 15	7
S2 = 45	9	12	6 15	4 30
S3 = 30	2 20	3 10	5	8

Z= 6*10+2*20+3*10+4*15+6*15+4*30=400 ден.ед.

ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.

Каждой строке Si ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому столбцу Mj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки SiMj)

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

Примем v₃ = 0

V₃ + u₁ = c₁₃ v₃ + u₁ = 4 u₁ = 4 - 0 = 4

V₃ + u₂ = c₂₃ v₃ + u₂ = 6 u₂ = 6 - 0 = 6

v₄ + u₂ = c₂₄ v₄ + u₂ = 4 v₄ = 4 - 6 = -2

v₁ + u₁ = c₁₁ v₁ + u₁ = 6 v₁ = 6 - 4 = 2

v₁ + u₃ = c₃₁ v₁ + u₃ = 2 u₃= 2 - 2 = 0

v₂ + u₃ = c₃₂ v₂+ u₃ = 3 v₂ = 3 - 0= 3



Таблица 2.17

Склады	Магазины
	М1= 30	М2= 10	М3 = 30	М4 = 30	Ui
S1 =25	6	10	4	7	U1=4
S2 = 45	9	12	6	4	U2=6
S3 = 30	2	3	5	8	U3=- 0
Vj	V1=2	V2=3	V3=0	V4= -2

G₁₂ = c₁₁ - ( u₁ + v₂) = 10- ( 4 + 3 ) = 3

G₁₄ = c₁₄ - ( u₁ + v₄ ) = 7 - ( 4 + (-2)) = 5

G₂₁ = c₂₁ - ( u₂ + v₁ ) = 9 - ( 6 + 2 ) = 1

G₂₂ = c₂₂ - ( u₂ + v₂ ) = 12 - ( 6 + 3) = 3

G₃₃ = c₃₃ - ( u₃ + v₃ ) = 5 - ( 0 + 0 ) = 5

G₃₄ = c₃₄ - ( u₃ + v₃ ) = 8 - ( 0 + (-2) ) = 10

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

Таблица 2.18

Склады	Магазины
	М1= 30	М2= 10	М3 = 40	М4 = 30
S1 =25	6 10	10	4 15	7
S2 = 45	9	12	6 15	4 30
S3 = 40	2 20	3 10	5	8

Z = 6*10+2*20+3*10+6*15+4*15+4*30=400 ден.ед.

РЕШЕНИЕ ЗАДАЧИ В EXCEL

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

Исходные данные
Спрос на товары в магазинах
Наличие товаров на складах	М1	М2	М3	М4
	30	10	30	30
Стоимость перевозки ед.груза
S1	25	6	10	4	7
S2	45	9	12	6	4
S3	30	2	3	5	8
Решение
Наличие товаров на складах	М1	М2	М3	М4
	0	0	0	0
S1	0	0	0	0	0
S2	0	0	0	0	0
S3	0	0	0	0	0
стоимость перевозки		М1	М2	М3	М4
Общая	0	0	0	0	0

Рис.1

Рис.2

Работа в диалоговом окне «Поиск решения»

Выберите команду: Сервис - Поиск решения. На экране появится диалоговое окно Поиск решения. Выполните следующие действия:

В поле Установить целевую ячейку введите адрес $Ј$17.

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

В поле Изменяя ячейки введите адрес блока ячеек $С$13: $f$15.

Введите ограничения: нажмите кнопку Добавить. На экране появится диалоговое окно Добавление ограничения. Введите в левое поле левую часть ограничения $5$ 13 .$5$ 15, выберите из раскрывающегося списка знак ограничения =, введите в правое поле правую часть ограничения $5$6:$5$8; щелкните по клавише Добавить - на экране опять появится диалоговое окно Добавление ограничения. Введите второе ограничение $C$12:$.F$12 = $С$4:$7л$4 и граничные условия C$13:.F$15 > 0 аналогичным образом; нажмите кнопку ОК. На экране появится диалоговое окно Поиск решения с введенными ограничениями (рис. 3)

Рис. 3

Решение задачи

Для решения задачи выполните следующие действия:

Щелкните по кнопке Параметры. Появится диалоговое окно Параметры поиска решения.

Оставьте без изменения Максимальное время решения задачи (100 с) и Предельное число итераций (100).

Установите флажок Линейная модель.

Нажмите кнопку ОК. Появится диалоговое окно Поиск решения.

Щелкните по кнопке Выполнить. Появится диалоговое окно Результаты поиска решения. Решение найдено.

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

7.Нажмите кнопку ОК. На экране появится исходная таблица
(рис.4), где в блоке ячеек C13:F15 находятся значения искомых пе-
ременных: XI - Х5, а в ячейке В14 значение целевой функции.

Рис.4

Анализ оптимального решения в Excel

Для анализа оптимального решения задачи воспользуемся отчетами: Результаты, Устойчивость, Пределы.

Отчет по результатам

Щелкните мышью по ярлычку Отчет по результатам. На экране появится лист данного отчета (рис. 5)

Microsoft Excel 12.0 Отчет по результатам
Рабочий лист: [Транспортная задача.xlsx]Лист1
Отчет создан: 31.05.2012 22:58:09
Целевая ячейка (Минимум)
	Ячейка	Имя	Исходное значение	Результат
	$B$17	Общая	0	400
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$C$13	S1 М1	0	10
	$D$13	S1 М2	0	0
	$E$13	S1 М3	0	15
	$F$13	S1 М4	0	0
	$C$14	S2 М1	0	0
	$D$14	S2 М2	0	0
	$E$14	S2 М3	0	15
	$F$14	S2 М4	0	30
	$C$15	S3 М1	0	20
	$D$15	S3 М2	0	10
	$E$15	S3 М3	0	0
	$F$15	S3 М4	0	0

Рис.5

Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$B$13	S1	25	$B$13=$B$6	не связан.	0
	$B$14	S2	45	$B$14=$B$7	не связан.	0
	$B$15	S3	30	$B$15=$B$8	не связан.	0
	$C$4	М1	30	$C$4=$C$12	не связан.	0
	$D$4	М2	10	$D$4=$D$12	не связан.	0
	$E$4	М3	30	$E$4=$E$12	не связан.	0
	$F$4	М4	30	$F$4=$F$12	не связан.	0
	$C$13	S1 М1	10	$C$13>=0	не связан.	10
	$D$13	S1 М2	0	$D$13>=0	связанное	0
	$E$13	S1 М3	15	$E$13>=0	не связан.	15
	$F$13	S1 М4	0	$F$13>=0	связанное	0
	$C$14	S2 М1	0	$C$14>=0	связанное	0
	$D$14	S2 М2	0	$D$14>=0	связанное	0
	$E$14	S2 М3	15	$E$14>=0	не связан.	15
	$F$14	S2 М4	30	$F$14>=0	не связан.	30
	$C$15	S3 М1	20	$C$15>=0	не связан.	20
	$D$15	S3 М2	10	$D$15>=0	не связан.	10
	$E$15	S3 М3	0	$E$15>=0	связанное	0
	$F$15	S3 М4	0	$F$15>=0	связанное	0

Рис.6

В верхней таблице отчета указан номер целевой ячейки - $B$17, в которой находится значение целевой функции, ее исходное значение, равное 0, и результирующее - минимальное значение целевой функции, равное 5240, которое получили в результате решения задачи.

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

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

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

Отчет по пределам

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

Microsoft Excel 12.0 Отчет по пределам
Рабочий лист: [Транспортная задача.xlsx]Отчет по пределам 1
Отчет создан: 31.05.2012 22:58:10
		Целевое
	Ячейка	Имя	Значение
	$B$17	Общая	400
		Изменяемое			Нижний	Целевой		Верхний	Целевой
	Ячейка	Имя	Значение		предел	результат		предел	результат
	$C$13	S1 М1	10		10	400		10	400
	$D$13	S1 М2	0		0	400		0	400
	$E$13	S1 М3	15		15	400		15	400
	$F$13	S1 М4	0		0	400		0	400
	$C$14	S2 М1	0		0	400		0	400
	$D$14	S2 М2	0		0	400		0	400
	$E$14	S2 М3	15		15	400		15	400
	$F$14	S2 М4	30		30	400		30	400
	$C$15	S3 М1	20		20	400		20	400
	$D$15	S3 М2	10		10	400		10	400
	$E$15	S3 М3	0		0	400		0	400
	$F$15	S3 М4	0		0	400		0	400

Рис.6

Отчет по устойчивости Щелкните мышью по ярлычку Отчет по устойчивости. На экране появится лист данного отчета (рис. 7).

Microsoft Excel 12.0 Отчет по устойчивости
Рабочий лист: [Транспортная задача.xlsx]Лист1
Отчет создан: 31.05.2012 22:58:09
Изменяемые ячейки
			Результ.	Нормир.	Целевой	Допустимое	Допустимое
	Ячейка	Имя	значение	стоимость	Коэффициент	Увеличение	Уменьшение
	$C$13	S1 М1	10	0	6	1	5
	$D$13	S1 М2	0	3	10	1E+30	3
	$E$13	S1 М3	15	0	4	5	1
	$F$13	S1 М4	0	5	7	1E+30	5
	$C$14	S2 М1	0	1	9	1E+30	1
	$D$14	S2 М2	0	3	12	1E+30	3
	$E$14	S2 М3	15	0	6	1	5
	$F$14	S2 М4	30	0	4	5	1E+30
	$C$15	S3 М1	20	0	2	5	3
	$D$15	S3 М2	10	0	3	3	1E+30
	$E$15	S3 М3	0	5	5	1E+30	5
	$F$15	S3 М4	0	10	8	1E+30	10
			Результ.	Теневая	Ограничение	Допустимое	Допустимое
	Ячейка	Имя	значение	Цена	Правая часть	Увеличение	Уменьшение
	$B$13	S1	25	2	25	0	15
	$B$14	S2	45	4	45	0	30
	$B$15	S3	30	-2	30	0	15
	$C$4	М1	30	-4	0	0	15
	$D$4	М2	10	-5	0	0	15
	$E$4	М3	30	-2	0	0	30
	$F$4	М4	30	0	0	1E+30	0

Рис.7



В нем приводится информация о чувствительности целевой ячейки к изменению ограничений. Отчет состоит из двух таблиц: Изменяемые ячейки и Ограничения. В таблице Изменяемые ячейки на отдельной строке выводятся номера ячеек и результирующие значения изменяемых переменных, находящихся в них. Данные столбца Нормированная стоимость характеризуют изменение значения целевой функции при увеличении на единицу значения соответствующей изменяемой переменной, т. е двойственные оценки. В столбце Целевой коэффициент приводятся значения коэффициентов при основных и вспомогательных переменных в выражении целевой функции. Если в окне Параметры поиска решения установлен флажок Линейная модель, в отчет включаются данные об изменении целевой функции при увеличении на единицу значения изменяемой переменной.

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

Столбцы Допустимое увеличение и Допустимое уменьшение

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

Задача 3

Задание.

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

Задача о кратчайшем пути формулируется следующим образом:

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

Метод заключается в присвоении вершинам графа временных меток L(x_j), а затем по определенному правилу заменить их постоянными метками L*(x_j). Постоянные метки - кратчайшие расстояния от заданной вершины (х₁) до всех остальных (х_j).

Алгоритм нахождения кратчайших путей графа методом Дейкстры.

· Определить множество вершин графа, смежных с вершиной х₁: S(x₁)={xj}

· Для каждой вершины, принадлежащей множеству S(x₁) вычислить новые временные метки L(x_j), равные min {L_ст(x_j), L*(x_j) + R_ij}, где L_ст(x_j) - старая временная метка вершины x_j, L(x_j) - постоянная метка вершины xj, R_ij - вес ребра (x_i, x_j)

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

· Определить множество вершин графа, смежных с вершиной x_i, которой на предыдущем шаге была присвоена постоянная метка S(x₁)={x_j}

· Перейти к пункту 2. Процесс повторяется до тех пор, пока все вершины не будут иметь постоянные метки.



Неориентированных граф задан матрицей весов (таблица 1)

Таблица 1 Исходные данные

	Х1	Х2	Х3	Х4	Х5
Х1	?	4	?	?	2
Х2	4	?	3	?	4
Х3	?	3	?	1	6
Х4	?	?	1	?	?
Х5	2	4	6	?	?

Предварительно вершине х₁ (исходной) требуется присвоить постоянную метку L*(X₁)=0, а всем остальным вершинам - временные метки, равные ?: L(X₂)=L(X₃)=L(X₄)=L(X₅)= ? (Таблица 2.1)

Таблица 2.1

	0	1	2	3	4
Х1	0*
Х2	?
Х3	?
Х4	?
Х5	?

Шаг 1.

А) определим множество вершин графа, смежных с вершиной х₁, не имеющих еще постоянных меток:

S(x₁)={x₂,x₅} L*(x₁)=0

Б) min {Lст(x_j),L*(x₁)+R_1j}

Таблица 3

Lст(xj)	L*(x1)+Rij		min{Lст(xj),(L*(x1)+Rij)
L(x2)= ?	L*(x1)+R12=	0+4=4	Min{?;4}=4
L(x5)= ?	L*(x1)+R15=	0+2=2	Min{?;2}=2



Таблица 2.2

	0	1	2	3	4
Х1	0*
Х2	?	4
Х3	?	?
Х4	?	?
Х5	?	2*

Шаг 2.

А)определим множество вершин графа, смежных с вершиной х₅, не имеющие еще постоянных меток:

S(x₅) = {x₂,x₃} L*(x₅)=2

Б)min {Lст(x_j), L*(x₅)+R_ij}

Таблица 4

Lст (xj)	L*(x5)+R5j		min{Lст(xj),L*(x5)+R5j}
L(x2)= ?	L*(x5)+R52=	2+4=6	min{?;6}=6
L(x3)= ?	L*(x5)+R53=	2+6=8	min{?;8}=8

Таблица 2.3

	0	1	2	3	4
Х1	0*
Х2	?	4	6*
Х3	?	?	8
Х4	?	?	?
Х5	?	2*

Шаг 3.

А)определим множество вершин графа, смежных с вершиной х₂, не имеющих еще постоянных меток:

S(x₂)={x₃}

L*(x₂)=6



Таблица 5

Lст (xj)	L*(x2)+R2j		min{Lст(xj),L*(x2)+R2j}
L(x3)= 8	L*(x2)+R23=	6+3=9	min{8;9}=8

Таблица 2.4

	0	1	2	3	4
Х1	0*
Х2	?	4	6*
Х3	?	?	8	8*
Х4	?	?	?	?
Х5	?	2*

Шаг 4.

А)определим множество вершин графа, смежных с вершиной х₃, не имеющих еще постоянных меток:

S(x₃)={x₄}

L*(x₃)=8

Таблица 6

Lст (xj)	L*(x3)+R3j		min{Lст(xj),L*(x2)+R2j}
L(x3)=?	L*(x3)+R34=	8+1=9	min{?;9}=9

Таблица 2.5

	0	1	2	3	4
Х1	0*
Х2	?	4	6*
Х3	?	?	8	8*
Х4	?	?	?	?	9*
Х5	?	2*

Нахождение кратчайших путей от вершины х₁ до всех остальных.

1)Определим кратчайший путь от вершины х₁ до вершины х₄

А)L*(x₄)=9



Таблица 7

L*(x3)=8	R34=1	L*(x3)=L*(x3)+R34=8+1=9

Б)Определим, какая вершина предшествует вершине х₃ в кратчайшем пути.

L*(x₃)=8

Таблица 8

L*(x2)=6	R23=3	L*(x3)?L*(x2)+R23=6+3=9
L*(x5)=2	R53=6	L*(x3)=L*(x5)+R53=2+6=8

В)Определим, какая вершина предшествует вершине х₅ в кратчайшем пути. L*(x₅)=2

Таблица 9

L*(x1)=0	R15=2	L*(x5)=L*(x1)+R15=0+2=2
L*(x2)=6	R25=4	L*(x5)?L*(x2)+R25=6+4=10

2)Найдем кратчайший путь от вершины х₁ до вершины х₂.

А) Вершина х₂ имеет смежные вершины с:

S(x₁,x₃,x₅)

Б)Определим, какая вершина предшествует вершине х₂ в кратчайшем пути.

L*(x₂)=6

Таблица 10

L*(x1)=0	R12=4	L*(x2)?L*(x1)+R12=0+4=4
L*(x3)=8	R32=3	L*(x2)?L*(x3)+R32=8+3=11
L*(x5)=2	R52=4	L*(x2)=L*(x5)+R52=2+4=6



Задача 4

Двухполюсные транспортные сети

Двухполюсной транспортной сетью S называется взвешенный ориентированный граф (орграф) без петель с множеством вершин X и множеством дуг U, для которых выполняются следующие условия:

· Существует только одна вершина, в которую не заходит ни одна дуга. Она называется входом (истоком) сети;

· Существует только одна вершина, из которой не исходит ни одна дуга. Она называется выходом (истоком) сети;

· Каждой дуге сети поставлено в соответствие неотрицательное число c(u), называемое пропускной способностью сети;

Потоком в сети S=(X,U) от входа S до выхода tназывается неотрицательная вещественная функция ц=(I,j), определенная на множестве дуг сети, для которой выполняются следующие условия:

· Величина потока по каждой дуге не должна превосходить её пропускной способности;

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

0?ц(u)?c(u) Для любой вершины, где

- множество дуг, заходящих в вершину х,

- множество дуг, выходящих из вершины х.

· величина потока по каждой дуге не должна превосходить её пропускной способности;

· величина потока V, входящего в каждую вершину, за исключением входа и выхода, равна величине потока, выходящего из этой вершины;

Множество вершин сети S=(X,U) можно разбить на два непересекающихся подмножества Xp и Xp,

Причем вход S принадлежит подмножеству вершин Хр, а выход t принадлежит подмножеству вершин Хр.

Подмножества Хр и Хр соединяются между собой дугами, образующими множество Up.

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

Разрез представляет собой такое множество дуг Up, исключение которых отделяет вход S от выхода t сети, и, следовательно, отделяет множество вершин Хр сети от множества Хр сети таким образом, что существование потока в таком случае невозможно, т.е. V=0

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

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

Теорема Форда - Фалкерсона.

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

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

Дуга U, соединяющая вершины x_i и x_j сети S является допустимой, если для нее выполняется одно из следующих условий:

· направление дуги совпадает с направлением потока и значение потока по этой дуге меньше её пропускной способности: ц(u)?c(u).

Такие дуги называют увеличивающими или согласованными.

· Направление дуги противоположно направлению потока и по ней проходит ненулевой поток: ц(u)>0

Такие дуги называют уменьшающими или несогласованными.

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

Алгоритм построения максимального потока

1. Задать начальное значение потока равным нулю, если оно не задано.

2. Найти увеличивающую цепь от входа S к выходу t.Если такой цепи нет, максимальный поток построен:

Далее перейти в конец алгоритма.

В противном случае перейти к пункту 3.

3. Вдоль найденной увеличивающей цепи изменить значение потока на величину д: по каждой увеличивающей дуге поток увеличить на ?(u)=c(u)-ц(u), по каждой уменьшающей дуге уменьшить на величину ?(u).

Возврат в пункт 2.

Вариант 1.

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

Найти максимальное значение потока.



Таблица 1 Исходные данные

	Х1	Х2	Х3	Х4	Х5
S	14	0	13	0	0
Х1	0	6	0	0	0
Х2	0	0	0	9	20
Х3	18	5	0	3	0
Х4	0	0	0	0	16

Рис 1.

· Рассмотрим цепь (s,x₃,x₂,x₄ ,t).Б)Вдоль дуги поток можно увеличить на величину ?(u)=c(u)-ц(u)

Вдоль дуги (s,x₃) ?(u)=13-0=13

Вдоль дуги (x₃,x₂) ?(u)=5-0=5

Вдоль дуги (x₂,x₄) ?(u)=9-0=9

Вдоль дуги (x₄,t) ?(u)=16-0=16

В)д=min{13,5,9,16}=5 >

По каждой увеличивающей дуге поток следует увеличить на 5

· Рассмотрим цепь (s,x₁,x_2,x₄,t).

А)Вдоль дуги поток можно увеличить на величину ?(u)=c(u)-ц(u)

(s,x₁) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 0<14 (x₁,x₂) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 0<6

(x₂,x₄) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 5<9

(x₄,t) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 5<16

Б)Вдоль дуги поток можно увеличить на величину ?(u)=c(u)-ц(u)

Вдоль дуги (S,x₁) ?(u)=14-0=14

Вдоль дуги (x₁,x₂) ?(u)=6-0=6

Вдоль дуги (x₂,x₄) ?(u)=9-5=4

Вдоль дуги (x₄,t) ?(u)=16-5=11

В)д=min{14,6,4,11}=4 >

По каждой увеличивающей дуге потом следует увеличить на 4.

· Рассмотрим цепь (s,x₁,x₂,t).

А) (s,x₁) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 4<14

(x₁,x₂) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 4<6

(x₂,t) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 0<20

Б)Вдоль дуги поток можно увеличить на величину ?(u)=c(u)-ц(u)

Вдоль дуги (s,x₁) ?(u)=14-4=10

Вдоль дуги (x₁,x₂) ?(u)=6-4=2

Вдоль дуги (x₂,t) ?(u)=20-0=20

Б)д=min{10,2,20}=2 >

По каждой увеличивающей дуге потом следует увеличить на 2.

· Рассмотрим цепь (s,x₃,x₄,t).

А) (s,x₃) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 5<13

(x₃,x₄) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 0<3

(x₄,t) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и потом по ней меньше пропускной способности: 9<16

Б)Вдоль дуги поток можно увеличить на величину ?(u)=c(u)-ц(u)

Вдоль дуги (s,x₃) ?(u)=13-5=8

Вдоль дуги (x₃,x₄) ?(u)=3-0=3

Вдоль дуги (x₄,t) ?(u)=16-9=7

Б)д=min{8,3,7}=3 >

По каждой увеличивающей дуге потом следует увеличить на 3.

Минимальный разрез: (х₁,х₂),(х₃,х₂),(х₃,x₄)

Пропускная способность: 6+5+3=14

Решение задачи в Excel

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

Рис. 1

Рис. 2

Работа в диалоговом окне “Поиск решения”

Для подготовки к решению задачи оптимизации надо выполнить команду: Сервис - Поиск решения. На экране появится диалоговое окно Поиск решения ( рис. 3 ). Следует выполнить следующие действия:



Рис. 3

1. В поле Установить целевую ячейку ввести адрес $H$13.

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

3. В поле Изменяя ячейки ввести адрес блока ячеек $C$13:$G$17

4. Ввести ограничения: $C$13:$G$17?$C$5:$G$9, $C$14:$G$17?0, $C$18=$H$14, $D$18=$H$15, $E$18=$H$16, $F$18=$H$17 нажимая до ввода каждого ограничения кнопку Добавить. После ввода всех ограничений нажать кнопку ОК. На экране появится диалоговое окно Поиск решения с введенными ограничениями.

5. Нажать кнопку Параметры. Появится диалоговое окно Параметры поиска решения.

6. Установить флажок Линейная модель .

7. Оставить без изменений остальные установки.

8. Нажать ОК. Появится диалоговое окно Поиск решения.

9. Щелкнуть по кнопке Выполнить. Появится диалоговое окно Результаты поиска решений.

10. Нажать ОК. На экране появится исходная таблица ( рис. 4), где в блоке ячеек C13:G17 находятся значения искомых переменных х_ij , а в ячейке H13- значение целевой функции.



Рис. 4

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