Решение транспортной задачи. Составление опорного плана

1.

Решение транспортной задачи
Составление опорного плана
B1
Выполним табличную запись ТЗ
Из требования
m
n
i 1
j 1
ai b j
следует, что одно
уравнение оказывается зависимым, т.е. транспортная модель содержит только m+n-1 независимых уравнений.
Таким образом начальное базовое допустимое
решение должно иметь m+n-1 базисную переменную.
Для получения этого решения используют метод наименьшей стоимости, правило северо-западного угла и
другие.
B2
B3
A1
A2
14
15
15
13
16
14
A3
bj
12
17
18
25
30
35
ai
10
15
13
28
30
22
52
90
По методу наименьшей стоимости сначала берут 1-ый
пункт производства продукции (А1 ) ив первую очередь
удовлетворяют потребность в продукции те пункты назначения, у которых затраты (cij ) будут меньшими по
сравнению с остальными, затем переходят к А2 , А3 и т.д.
Вычислим значение целевой функции при таких допустимых значениях:
z 10 14 15 13 13 14 30 17 22 18 1423
Нажмите «ENTER»

2.

Проверка плана на оптимальность
Для проверки опорного плана на оптимальность
используют так называемый «метод потенциалов»,
по которому строке i и столбцу j транспортной
таблицы ставится в соответствие числа ui и vj .
Для каждой базисной переменной xij текущего
решения потенциалы ui и vj должны удовлетворять уравнению ui + vj = cij .Эти уравнения приводят к системе, состоящей из m + n -1 уравнений,
в которых фигурируют m + n неизвестных.
Значения потенциалов можно определить из этой
системы, придавая одному из них произвольное
значение (обычно полагают u1 =0).
Итак, для клеток, в которых содержался груз,
определили потенциалы, пользуясь условием:
B1
A1 10
A2 15
A3
bj
vj
B2
B3
14
15
13
16
12
25
30 17
30
14
14
15
13
22
35
14
18
ai ui
10 0
28 -1
52
90
3
15
1. ui + vj = cij
Теперь надо провести оценку для небазисных переменных xpg , т.е. для клеток, в которых нет груза.
Оценки для небазисных переменных xpg определяются в соответствии с соотношением:
2. ĉpg= cpg - ( ui + vj )
A1 B 2 :
A1 B 3 :
A2 B 2 :
A3 B 1 :
15 – ( 14 + 0 ) = 1
15 – ( 15 + 0 ) = 0
16 – ( 14 - 1 ) = 3
12 – ( 14 +3 ) = -5
Если в результате получатся отрицательные значения, то план считается
не оптимальным, и его надо перестроить путём перераспределения продукции.
Нажмите «ENTER»

3.

Улучшение опорного плана
Предварительно восстановим табличную запись задачи
B1
A1 10 14
A2 15 -. 13
A3
bj
+
.
25
12
B2
B3
15
16
30 17
30
15
ai
10
28
13 +.
22 . -18 52
35
90
14
B1
B2
B3
A1
A2
14
15
13
16
A3 15
bj 25
12
17
30
15
28
7
35
14
18
ai
10
28
52
90
Для улучшения опорного плана в базис включается небазисная переменная, имеющая самую большую по
модулю отрицательную оценку. В нашем случае это переменная x31 (клетка А3В1), для которой 2-ое условие не
выполняется. Необходимо выяснить, а какую же базисную переменную нужно вывести из базиса? Для этого
поступим следующим образом: точками обозначим пункты отправки и пункты назначения, пунктирной линией
соединим те вершины, в клетках которых есть груз, например, А1В1 , А2В1 , и т.д.
А1
А2
А3
Обозначим клетку А3В1 , в которой 2-ое условие не выполняется и, начиная с одного
◦
◦
◦
из концов этой линии по пунктирным линиям доберёмся к другому концу.
Напомним, что каждая линия соответствует определённой клетке. Отметим точками
те клетки в таблице, которые соответствуют сплошным линиям, построим многоугольник соединяя эти точки последовательно. Вершинам припишем чередующиеся знаки ( + , - ), начиная со знака (+) для вводимой в базис переменной.
◦
◦
◦
Затем в вершинах со знаком (-) отыщем наименьшую продукцию, которую и будем
В1
В2
В3
перемещать по вершинам многоугольника согласно знакам.
Получили новый опорный план Вычислим значение целевой функции
Нажмите «ENTER»
z 10 14 28 14 15 12 30 17 7 18 1348
Значение z уменьшилось. Цикл завершён. Снова надо проверить условия 1 и 2. Проследите цикл на практике.