|
Для оптимизации полученной модели сведем исходные данные в таблицу 6 и введем следующие обозначения:
В1, В2, В3 - данные поставщика с запасами груза b1, b2, b3;
D1, D2, D3 - данные потребителя с объемами заявок d1, d2, d3.
Таблица 6 |
Поставщик |
Потребитель | |
Обозначение |
Запас |
D1 |
D2 |
D3 | |
В1 |
b1 = 50 |
4 |
10 |
8 | |
В2 |
b2 = 101 |
5 |
4 |
4 | |
В3 |
b3 = 13 |
5 |
10 |
7 | |
Потребность в грузе |
d1 = 42 |
d2 = 71 |
d3 = 52 |
В верхнем правом углу клеток занесены стоимости перевозок i-го поставщика к j-му потребителю.
Сравнивая запасы груза
с суммарным объемом заявок потребителей
убеждаемся, что это открытая транспортная задача (запасы груза у поставщика не равны потребностям в грузе потребителя). С избытком объема заявок
В этом случае заявки выполняются не полностью, поэтому равенство (3.7) заменяется неравенством
Открытая транспортная задача сводится к закрытой введением (m+1)-го фиксированного поставщика с запасом груза равным:
Тогда имеем: b4= 165-164=1 единица.
Себестоимость перевозок от фиктивного поставщика к любому потребителю принимаем равной нулю, после этого получаем таблицу 7, в которой методом наименьшего элемента находим опорное решение задачи.
Таблица 7 |
Поставщик |
Потребитель | |
Обозначение |
Запас |
D1 |
D2 |
D3 | |
В1 |
b1 = 50 |
4 42 |
10 |
8 8 | |
В2 |
b2 = 101 |
5 |
4 71 |
4 30 | |
В3 |
b3 = 13 |
5 |
10 |
7 13 | |
B4 |
b4 =1 |
0 |
0 |
0 1 | |
Потребность в грузе |
d1 = 42 |
d2 = 71 |
d3 = 52 |
Опорное решение проверяется на выраженность по формуле:
N=m+n-1
Где: N- количество клеток таблицы, занятых объемами грузов;
m- количество поставщиков;
n- количество потребителей.
N=4+3-1=6. Так как количество клеток в таблице 7 именно 6, то найденное опорное решение можно принять к рассмотрению.
Значение целевой функции будет иметь вид:
W = 42*(4+11) + 8*(8+11) +71*(4+11) +30(4+11) +13*(7+3)+1(0+0) = 2427
Оптимальное решение задачи находится методом потенциалов: каждому поставщику Bi ставятся в соответствие некоторая переменная Ui, называемая потенциалом данного поставщика. Каждому потребителю Dj ставятся в соответствие переменная Vj - потенциал этого потребителя.
Для отыскания значений этих переменных, т.е. потенциалов поставщиков и потребителей, составляется и решается система уравнений, каждой занятой объемами перевозок клетке соответствует уравнение вида:
|
