при условии что,
Математическая модель двойственной задачи:
Экономический смысл переменных:
Z – целевая функция прямой задачи (суммарные затраты);
Z ' – целевая функция двойственной задачи (суммарная потенциальная прибыль от перевозки груза);
Сij – стоимость перевозки единицы продукции из i-го пункта в j-ый;
Xij – объем перевозок от i-го поставщика j-му потребителю;
Ui – условная плата перевозчику за вывоз единицы груза из i-го пункта отправления;
Vj – условная плата перевозчику за доставку единицы груза в j-ый пункт назначения.
Потребители Поставщики | В1 | В2 | В3 | В4 | В5 | Ui | |||
А1 | 350 4 | 8 | 50 -W | +W | U1 =-2 | ||||
6 | 9 | 0 | |||||||
А2 | 9 | 100 +W | 200 | -W 0 | U2= -6 | ||||
5 | 10 | 4 | |||||||
А3 | 7 | 150 | -W | 100 | +W 8 | 250 6 | 0 | U3 =0 | |
11 | |||||||||
Vj | V1 =6 | V2 =11 | V3 =8 | V4 =6 | V5 = 6 | W=50 |
Проверяем на вырожденность:
R=m+n-1=3+5-1=7
m= 3 – количество поставщиков;
n = 5 – количество потребителей.
Базисных клеток 7, план не вырожден.
Проверяем план на оптимальность, используя метод потенциалов. Для базисных клеток составляем систему уравнений Ui + Vj = Сij находим значение потенциалов так как переменных на 1 больше, чем уравнений,
|
|
то переменной U3 присваиваем значение 0 и решаем систему уравнений, получаем
Проверяем выполнение неравенства в свободных: клетках Ui + Vj ≤ Сij
более всего не выполняется условие Ui + Vj ≤ Сij, сюда ставим «+W», строим контур перераспределения W и находим его значение:
Перераспределяем W=50 по контуру.
Составляем следующий план:
Потребители Поставщики | В1 | В2 | В3 | В4 | В5 | Ui | |||
А1 | 350 | -W | 50 +W | U1 =-6 | |||||
4 | 8 | 6 | 9 | 0 | |||||
А2 | 9 | 150 +W | 150 | -W 0 | U2= -6 | ||||
5 | 10 | 4 | |||||||
А3 | +W | 100 | -W | 150 8 | 250 6 | 0 | U3 =0 | ||
7 | 11 | ||||||||
Vj | V1 =10 | V2 =11 | V3 =8 | V4 =6 | V5 = 6 | W=100 |
Так как переменных на i больше, чем уравнений, то переменной U3 присваиваем значение 0 и решаем систему уравнений, получаем
проверяем выполнение неравенства в свободных клетках Ui + Vj ≤ Сij,
– более всего не выполняется условие Ui + Vj ≤ Сij, сюда ставим «+W», строим контур перераспределения W и находим его значение: перераспределяем W=100 по контуру.
Составляем следующий план:
Потребители Поставщики | В1 | В2 | В3 | В4 | В5 | Ui | |
А1 | 250 4 | 8 | 6 | 9 | 150 0 | U1 =-3 | |
А2 | 9 | 250 5 | 10 | 4 | 50 0 | U2= -3 | |
А3 | 100 7 | 11 | 150 8 | 250 6 | 0 | U3 =0 | |
Vj | V1 =7 | V2 =8 | V3 =8 | V4 =6 | V5 = 3 |
Для базисных клеток Ui + Vj = Cij. Составляем для них систему уравнений. Принимаем U3=0, так как в строке потенциала U3 наибольшее количество (три) базисных клеток, решаем систему уравнений и находим количественное значение Ui и Vj:
|
|
Проверяем выполнение неравенства Ui + Vj ≤ Сij, в свободных клетках:
Неравенство Ui + Vj ≤ Сij,в свободных клетках выполняется, построенной план является оптимальным.