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

Рис.4

Получаем решение. (Рис.5)

Рис.5

Полученное решение можно отобразить на графе.

Рис. 6.

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

Запуская еще раз процедуру Поиск решения, можно получить еще одно решение.

Рис.7

Полученное решение на графе выглядит следующим образом.

Рис. 8

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

Рис.9

Полученное решение на графе выглядит следующим образом.

Рис.10

Откроем отчет по устойчивости (Рис. 11) для последнего решения и выделим в нем строки, соответствующие дугам с ненулевыми пропускными способностями. В этих строках в столбце Нормированная стоимость единицы соответствуют дугам, образующим один из разрезов минимальной пропускной способности. Увеличивая пропускные способности этих дуг, можно увеличить мощность всего потока. Если увеличивать пропускные способности других дуг, то мощность потока увеличиваться не будет. На рисунке 11 соответствующие клетки выделены рамкой.

Рис.11

Изменяемые ячейки
			Результ.	Нормир.	Целевой	Допустимое	Допустимое
	Ячейка	Имя	Знач.	стоимость	Коэфф.	Увеличение	Уменьшение
	$B$15	Узел 1 Узел2				1E+30
	$C$15	Узел 1 Узел 3
	$D$15	Узел 1 Узел 4
	$E$15	Узел 1 Узел 5					1E+30
	$F$15	Узел 1 Узел 6					1E+30
	$B$16	Узел 2 Узел2					1E+30
	$C$16	Узел 2 Узел 3					1E+30
	$D$16	Узел 2 Узел 4				1E+30
	$E$16	Узел 2 Узел 5					1E+30
	$F$16	Узел 2 Узел 6					1E+30
	$B$17	Узел 3 Узел2					1E+30
	$C$17	Узел 3 Узел 3					1E+30
	$D$17	Узел 3 Узел 4					1E+30
	$E$17	Узел 3 Узел 5
	$F$17	Узел 3 Узел 6					1E+30
	$B$18	Узел 4 Узел2					1E+30
	$C$18	Узел 4 Узел 3					1E+30
	$D$18	Узел 4 Узел 4					1E+30
	$E$18	Узел 4 Узел 5					1E+30
	$F$18	Узел 4 Узел 6				1E+30
	$B$19	Узел 5 Узел2
	$C$19	Узел 5 Узел 3					1E+30
	$D$19	Узел 5 Узел 4					1E+30
	$E$19	Узел 5 Узел 5					1E+30
	$F$19	Узел 5 Узел 6				1E+30

Итак, разрез образуют дуги (4;6) и (5;6). Найдем возможный экономический эффект от увеличения пропускной способности этих дуг. Увеличим пропускную способность дуги (4;6), значение которой находится в ячейке F9, на единицу и обратимся к процедуре Поиск решения. Увеличения общей мощности потока не произошло. Причина хорошо видна на соответствующем графе. (Рис.10) Очевидно, что необходимо также увеличить пропускную способность дуги (2;4). Увеличим ее значение на единицу и найдем решение. Получили поток, мощность которого равна 9 единицам, т.е. поток увеличился на одну единицу. Проверим, нельзя ли увеличить поток на 2 единицы. Увеличиваем пропускные способности дуг (2;4) и (4;6) еще на единицу и находим решение. Получаем поток мощностью в 10 единиц. Проверяем, что дальнейшее увеличение пропускных способностей этих дуг не приводит к увеличению мощности потока по сети.

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

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

8-4-4=0. Т.е. такое увеличение пропускных способностей не выгодно.

При увеличении пропускных способностей на две единицы получаем прибыль, равную 16-6-6=4. Т.е. такое увеличение пропускных способностей приносит прибыль 4 ед..

Перейдем к анализу увеличения пропускной способности дуги (5;6). Восстанавливаем первоначальные пропускные способности дуг (2;4) и (4;6) и увеличиваем пропускную способность дуги (5;6) последовательно на одну, две, три единицы. Получаем, что увеличение пропускной способности дуги (5;6) на одну и две единицы приводит к увеличению мощности потока соответственно на столько же единиц. Увеличение пропускной способности дуги (5;6) на три единицы уже не приводит к увеличению мощности потока.

Найдем возможный экономический эффект.

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

8-3=5.

При увеличении пропускной способности на две единицы получаем прибыль, равную. 16-4,5=11,5

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