Найдем новое базисное решение.
Клетку (2,2), которая соответствует отрицательная невязка, равная -1,5, отметим знаком (+) (табл. 16). Одновременно установим равновесие по всему многоугольнику: если в клетку (2,2) поставили (+), то в клетку (2,1) поставим (-), если в клетку (3,1) - (+), в клетку (3,3) - (-), если в клетку (1,3) - (+), в клетку (1,2) - (-).
Табл. 16
|
Магазины |
|
|||
Склады |
К1=50 |
К2 =30 |
К3 = 45 |
К4 = 40 |
|
S1= 50 |
|
14 (-) 30 |
11 (+) 20 |
12,5 |
|
S2 = 55 |
13 (-) 15 |
13,5 (+)
|
15 |
12 40 |
|
S3 = 60 |
10 (+) 35 |
12,5
|
9 (-) 25
|
14 |
|
16
Наименьшим из чисел, находящихся в клетках со знаком (-), является содержимое клетки (2,1), где Х21 = 15, поэтому во всех клетках, помеченных знаком (+), надо увеличить перевозки на 15, а во всех клеток, помеченных знаком (-) уменьшить перевозки на 15 (табл. 17). Переменная Х21 становится равной нулю, т.е. выводится из базиса.
Табл. 17
|
Магазины |
|
|||
Склады |
К1=50 |
К2 =30 |
К3 = 45 |
К4 = 40 |
|
S1= 50 |
16
|
14 15 |
11 35 |
12,5 |
|
S2 = 55 |
13
|
13,5 15 |
15 |
12 40 |
|
S3 = 60 |
10 50 |
12,5
|
9 10
|
14 |
|
Получим план перевозок (см. табл. 17), при котором значение целевой функции равно:
Z= 50*10 + 15*14 + 15*13.5 + 35*11 + 10*9 + 40*12 = 1867,5.
Повторим действия, описанные в пунктах 1- 4.
Для всех xij > 0 (см. табл. 17) составим потенциальные уравнения: (21)
-
10-U3-V1=0
14-U1-V2=0
13,5-U2-V2=0
11-U1-V3=0
9-U3-V3=0
12-U2-V4=0
Определим неизвестные потенциалы (21), присвоив значение, равное нулю, например, наиболее часто встречающемуся неизвестному индексу: U2 = 0, тогда
U1 = 0,5 V1 = 11,5
U2 = 0 V2 = 13,5
U3 = -1,5 V3 = 10,5
V4 = 12
Занесем вычисленные потенциалы в табл. 18.
Табл. 18
|
Магазины |
||||
Склады |
К1=50 |
К2 =30 |
К3 = 45 |
К4 = 40 |
Ui |
S1= 50 |
16
|
14 15 |
11 35 |
12,5 |
U1 =0,5 |
S2 = 55 |
13
|
13,5 15 |
15 |
12 40 |
U2 =0 |
S3 = 60 |
10 50 |
12,5
|
9 10
|
14 |
U3 =-1,5 |
Vj |
V1 =11,5 |
V2 =13,5 |
V3 =10,5 |
V4 =12 |
|
Для всех небазисных клеток определим невязки:
G11=16-0,5-11,5=4 |
G21=13-0-11,5=1,5 |
G32=12,5+1,5+-13,5=0,5 |
G23=15-0-10,5=4,5 |
G14=12,5-0,5-12=0 |
G34=14+1,5-12=3,5 |
Отрицательных невязок нет, значит, найденный план (табл. 18) - оптимален.
Таким образом, минимальная стоимость перевозок (с учетом принятой единицы измерения, равной 100 у.е.) Z=186 750 и достигается она при значениях перевозок:
,
,
,
,
,
