Курсовая работа: Решение транспортной задачи методом потенциалов
4
7
u2
3
1
8
u3
v1
v2
v3
v4
v5
v 5 = 0 ® u 3 = 8, так как u 3 + u 5 = p 35 = 8, ® v 4 = -7, так как u 3 + v 4 = p 34 = 1, ® v 3 = -5, так как u 3 + v 3 = 3, ® u 2 = 12 ® v 2 = -8, ® v 1 = -6 ® u 1 = 11.
Симплекс – множители нужны для того, чтобы найти свободную ячейку ( i , j ) , которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс – методе).
Для определения симплекс – множителей мы вносим на свободные места в таблице значения
p ¢ ij = pij – ui – vj
(коэффициенты целевой функции, пересчитанные для свободных переменных). Если все p ¢ ij 
0, то базисное решение оптимально. В противном случае мы выбираем произвольное p ¢ a b < 0, чаще всего наименьшее. Индексом a b помечено свободное переменное х a b , которое должно войти в базис. Соответствующую ячейку транспортной таблицы мы отметим знаком +.
Кроме ячейки (a, b) транспортной таблицы, мы пометим значками – и + другие занятые числами ячейки таким образом, чтобы в каждой строке и в каждом столбце транспортной таблицы число знаков + было равно числу знаков -. Это всегда можно сделать единственным образом, причем в каждой строке и в каждом столбце будет содержаться максимум по одному знаку = и по одному знаку -.
Затем мы определяем минимум М из всех элементов, помеченных знаком -, и выбираем ячейку (g, d), где этот минимум достигается.
В нашем примере с М = 5 можно выбрать (g, d) = (2, 3); при этом (g, d) определяет базисное переменное, которое должно стать свободным, т.е. базисное переменное, соответствующее индексу разрешающей строки симплекс – метода.
|
20 |
5 |
10 |
10 |
5 | |
|
15 |
15 | ||||
|
15 |
5 |
К-во Просмотров: 313
Бесплатно скачать Курсовая работа: Решение транспортной задачи методом потенциалов
|