2.2 Транспортная задача с оптимизацией плана перевозок по критерию стоимости
2.2.1 Решение задачи методом потенциалов
Задача. Найти оптимальное решение транспортной задачи с матрицей стоимостей перевозок
,
запасами в пунктах отправления a1=100, a2=150, a3=50 и заказами в пунктах назначения b1=75, b2=80, b3=60, b4=85.
Решение.
Задать нумерацию элементов массивов с единицы:
Задать матрицу стоимостей перевозок:
0 итерация. Составить опорный план:
Вычислить значение целевой функции:
Задать начальные нулевые значения элементов массива платежей:
I итерация. Рассчитать значения платежей из условия равенства стоимостей и псевдостоимостей в базисных ячейках таблицы, для чего записать уравнения:
Используя функцию Find, найти решение системы:
Найденный вектор Y является блочным: первым блоком является вектор , вторым – вектор . Чтобы получить их значения, необходимо выполнить присваивание:
Рассчитать значения псевдостоимостей во всех ячейках таблицы (матрица S) и разности между стоимостями и псевдостоимостями (матрица D):
Анализ элементов матрицы D позволяет заключить, что из двух ячеек с отрицательной разностью стоимости и псевдостоимости более перспективна ячейка (3, 2).
I I итерация. Организовать цикл по переброске 5 единиц груза:
Полученная матрица перевозок будет иметь вид:
,
значение
целевой функции
.
Рассчитать новые значений платежей:
Рассчитать новые значения псевдостоимостей и элементов матрицы D.
Поскольку полученная матрица D не содержит отрицательных элементов, найденное решение X1 является оптимальным.
Случай вырожденного опорного плана
Пусть при нахождении опорного плана методом северо-западного угла он получился следующим:
.
Здесь число базисных ячеек равно четырем, в то время как в невырожденном плане их должно быть n+m-1=5. Запишем в ячейку (1,2) некую малую величину (например, =0,1) и для сведения баланса отнимем ее от содержимого ячейки (2,2):
.
В ходе дальнейшего решения задачи методом потенциалов оказывается выгодным перебросить 20 единиц из ячейки (1,2) в ячейку (2,2), а затем – в ячейку (3,2). Соответствующие преобразования выглядят следующим образом:
.
После получения оптимального решения величину нужно округлить до нуля.
2.2.2 Решение транспортной задачи как задачи оптимизации
Задать нумерацию элементов массивов с единицы, ввести матрицу стоимостей C, вектор значений запасов A и вектор значений заявок B:
Определить число рядов и столбцов матрицы С:
Ввести единичные векторы IC (m x 1) IR(n x 1):
Используя оператор цикла, задать начальные значения перевозок равными 0:
Ввести выражение для вычисления значения целевой функции:
Записать ограничения на значения перевозок:
Решить задачу оптимизации:
Полученные результаты:
2.3 Варианты заданий
3 Потоки в орграфах
3.1 Алгоритм нахождения максимального потока
Задача. Задан орграф с пропускными способностями с, значения которых указаны рядом с каждой дугой. Найти максимальный поток из источника s в сток t.
Рисунок 3.1 - Исходный орграф
Решение. Пропустим по орграфу произвольный поток, для чего зададим для каждой дуги e потоковую функцию f, удовлетворяющую условиям:
1)
;
2) для каждой вершины, отличной от s и t, сумма потоковых функций входящих дуг равна сумме потоковых функций исходящих дуг.
Получим граф, изображенный на рис. 3.2,
где первое число рядом с дугой обозначает
ее пропускную способность, второе –
потоковую функцию. Суммарный поток,
исходящий из источника,
Равный ему поток входит в сток:
Рисунок 3.2 - Орграф с суммарным потоком 9
Присвоим тип I каждой дуге, для которой потоковая функция меньше ее пропускной способности, и тип D- каждой дуге, для которой потоковая функция отлична от нуля.
Рисунок 3.3 - Орграф с указанными типами дуг
На рис 3.3 изображен граф с указанными типами дуг. Отметим, что дуга (s,a) является одновременно как дугой типа I, так и дугой типа D.
Попытаемся найти в графе увеличивающую цепь, т.е. простую цепь из источника в сток, в которой каждая дуга, направленная из s в t, (прямая дуга) имеет тип I, а каждая дуга, направленная из t в s, (обратная дуга) - тип D. Для этого будем помечать вершины и дуги графа, начиная с источника s и используя следующее правило:
- если вершина x помечена, дуга (x,y) не помечена и имеет тип I, вершина y не помечена, то помечается дуга (x,y) и ее конец y;
- если вершина x помечена, дуга (y,x) не помечена и имеет тип D, вершина y не помечена, то помечается дуга (y,x) и ее начало y;
- других случаев пометки вершин и дуг не существует.
Если в результате окажется возможным пометить сток t, то в графе существует увеличивающая цепь, по которой можно пропустить дополнительный поток, иначе такой цепи не существует, и текущий поток является максимально возможным.
Пометим прежде всего вершину s. Из двух дуг, исходящих из этой вершины, можно пометить только дугу (s,a), имеющую тип I, и ее конец a. Далее можно пометить дугу (a,c) и ее конец c. Нельзя пометить прямую дугу (a,b), имеющую тип D, и обратную дугу (d,a), т.к. она имеет тип I. Непомеченными остаются также их вершины b и d. Далее, исходя из вершины c, помечается обратная дуга (b,c) типа D и ее начало b. Дуга (c,d) и ее вершина d не помечаются, т.к. эта прямая дуга имеет тип D. Наконец, помечаются прямая дуга (b,t) типа I и ее конец-источник t.
Таким образом, найдена увеличивающая цепь (s,a), (a,c), (b,c), (b,t).
Найдем для увеличивающей цепи резерв
увеличения потока по каждой прямой дуге
:
d(s,a)=4,
Рисунок 3.4 - Орграф с увеличенным потоком
d(b,t)=3;
далее найдем резерв уменьшения потока
по каждой обратной дуге
:
d(b,c)=1.
Минимальная из этих величин
есть дополнительный поток, который
можно пропустить по увеличивающей цепи.
Новые значения потоковой функции в
прямых дугах цепи
,
а в обратных дугах
.
Граф с увеличенным потоком изображен
на рис. 3.4.
Можно видеть, что суммарный поток в этом графе равен 10. Вновь определим типы дуг (рис. 3.5).
Анализ этого графа показывает, что в нем можно пометить только дуги (s,a), (a,c) и их вершины a,c. Дальнейшие пометки невозможны, и сток t остается непомеченным. Следовательно, новых увеличивающих цепей построить нельзя, и найденный поток, равный 10, является максимальным.
Рисунок 3.5 - Орграф с новыми типами дуг