Вычислим новые значения для узлов контура. В четных вершинах значения уменьшаются на 30, в клетке (2,1) значение станет равным 30-q=0
в клетке (4,3) - равным 80-q=80-30=50
В нечетных вершинах значение увеличивается на q=30, так в клетке (4,1) значение равно 0+q=0+30=30
а в клетке (2,3) значение равно 110+q=110+30=140
Получим новое опорное решение (таблица 6)
Таблица 6
Вычислим суммарную стоимость перевозок для полученного опорного плана:
 |
Уменьшение стоимости перевозок по сравнению с начальным планом составило:
 |
|||
 |
|||
Теоретически это уменьшение равно
q - множитель на соответствующее превышение т.е. те же 120 (произведение 30 на 4)
Рассчитаем новую систему потенциалов.
Для определения U1, U2,
U3, U4, V1, V2, V3, V4
имеем следующую систему уравнений:
Имеем 8 уравнений и 9 неизвестных.
Положим что U1=0, тогда остальные величины будут равны:
V1=2
V2=4
V3=7
V4=5
U2=4
U3=3
U4=1
U5=5
Припишем значения потенциалов соответствующим строкам и столбцам (таблица 7).
Таблица 7
Вычислим значения невязок для всех клеток
без перевозок по формуле:
В ряде клеток (5,3) и (1,3) наблюдаются нарушения (невязка больше нуля)
Выберем клетку (5,3) в которой превышение равно 2.
Построим замкнутый цикл с началом в этой точке.
В качестве остальных вершин выберем клетки (4,3), (4,4), (5,4)
Нечетные вершины (5,3), (4,4) образуют положительную полуцепь.
Четные вершины (4,3), (5,4) образуют отрицательную полуцепь.
Величина q=min{40;50}=40
Вычислим новые значения для узлов контура. В четных вершинах значения уменьшаются на 40, в клетке (5,4) значение станет равным 40-q=0
в клетке (4,3) - равным 50-q=50-40=10
В нечетных вершинах значение увеличивается на q=40, так в клетке (5,3) значение равно 0+q=0+40=40
а в клетке (4,4) значение равно 120+q=120+40=160
Получим новое опорное решение (таблица 8)
Таблица 8
Вычислим суммарную стоимость перевозок для полученного опорного плана:
 |
Уменьшение стоимости перевозок по сравнению
с начальным планом составило:
Теоретически это уменьшение равно
q - множитель на соответствующее превышение т.е. те же 80 (произведение 40 на 2)
Рассчитаем новую систему потенциалов.
Для определения U1, U2, U3, U4, V1, V2, V3, V4 имеем следующую систему уравнений:
Имеем 8 уравнений и
9 неизвестных.
Положим что U1=0, тогда остальные величины будут равны:
V1=2
V2=4
V3=7
V4=5
U2=4
U3=3
U4=1
U5=7
Припишем значения потенциалов соответствующим строкам и столбцам (таблица 9).
Таблица 9
Вычислим значения невязок для всех клеток без перевозок по формуле:
|
В клетке (3,1) наблюдаются нарушения (невязка больше нуля)
Выберем клетку (3,1) в которой превышение равно 6.
Построим замкнутый цикл с началом в этой точке.
В качестве остальных вершин выберем клетки (4,3), (4,1), (1,1)
Нечетные вершины (1,3), (4,1) образуют положительную полуцепь.
Четные вершины (4,3), (1,1) образуют отрицательную полуцепь.
Величина q=min{120;10}=10
Вычислим новые значения для узлов контура. В четных вершинах значения уменьшаются на 10, в клетке (4,3) значение станет равным 10-q=0
в клетке (1,1) - равным 120-q=120-10=110
В нечетных вершинах значение увеличивается на q=10, так в клетке (3,1) значение равно 0+q=0+10=10
а в клетке (1,4) значение равно 30+q=30+10=40
Получим новое опорное решение (таблица 10)
Таблица 10
Вычислим суммарную стоимость перевозок для полученного опорного плана:
 |
Для определения U1, U2, U3, U4, V1, V2, V3, V4 имеем следующую систему уравнений:
Имеем 8 уравнений и
9 неизвестных.
Положим что U1=0, тогда остальные величины будут равны:
V1=2
V2=3
V3=6
V4=5
U2=3
U3=2
U4=1
U5=6
Припишем значения потенциалов соответствующим строкам и столбцам (таблица 11).
Таблица 11
Все невязки не положительны, следовательно, оптимальное решение найдено
2. Решение транспортной задачи в Excel
Таблица 12
Оптимальные объемы перевозок содержатся в интервале В15:Е19.
Полученные результаты полностью совпадают с результатами, полученными ранее методом интервалов.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.