Контрольная работа № 1. Отчет по задаче оптимального распределения ресурсов и транспортной задаче, страница 5

Нечетные вершины образуют положительную полуцепь. Четные вершины отрицательную. Величина . Получим новое опорное решение на рис. 26.

Вычислим суммарную стоимость перевозок для полученного опорного плана:

Уменьшение стоимости перевозок по сравнению с начальным планом составило  Теоретически это уменьшение равно , т.е. те же 280 ( 70*4).

Рассчитаем новую систему потенциалов.

Припишем значения потенциалов соответствующим строкам и столбцам (рис.27).

Вычислим значения невязок для всех клеток без перевозок.

Запишем их в правый верхний угол каждой клетки. В ряде клеток наблюдаются нарушения (невязки больше нуля). Выберем клетку с наибольшим превышением, равную 3. Построим замкнутый цикл с началом в этой клетке. Пронумеруем клетки.

Нечетные вершины образуют положительную полуцепь. Четные вершины отрицательную. Величина . Получим новое опорное решение на рис. 27.

Вычислим суммарную стоимость перевозок для полученного опорного плана:

Уменьшение стоимости перевозок по сравнению с начальным планом составило  Теоретически это уменьшение равно , т.е. те же 120 ( 40*3).

 

Рис.27

Рассчитаем очередную систему потенциалов.

Припишем значения потенциалов соответствующим строкам и столбцам (рис.28).

Вычислим значения невязок для всех клеток без перевозок.

Запишем их в правый верхний угол каждой клетки. В ряде клеток наблюдаются нарушения (невязки больше нуля). Выберем клетку с наибольшим превышением, равную 2. Построим замкнутый цикл с началом в этой клетке. Пронумеруем клетки.

Нечетные вершины образуют положительную полуцепь. Четные вершины отрицательную. Величина . Получим новое опорное решение на рис. 28.

Вычислим суммарную стоимость перевозок для полученного опорного плана:

Уменьшение стоимости перевозок по сравнению с начальным планом составило  Теоретически это уменьшение равно , т.е. те же 160 ( 80*2).

 Рис.28

Рассчитаем очередную систему потенциалов.

Припишем значения потенциалов соответствующим строкам и столбцам (рис.29).

Вычислим значения невязок для всех клеток без перевозок.

Запишем их в правый верхний угол каждой клетки. В ряде клеток наблюдаются нарушения (невязки больше нуля). Выберем клетку с наибольшим превышением, равную 2. Построим замкнутый цикл с началом в этой клетке. Пронумеруем клетки.

Нечетные вершины образуют положительную полуцепь. Четные вершины отрицательную. Величина . Получим новое опорное решение на рис. 29.

Вычислим суммарную стоимость перевозок для полученного опорного плана:

Уменьшение стоимости перевозок по сравнению с начальным планом составило  Теоретически это уменьшение равно , т.е. те же 80 ( 40*2).

 Рис.29

Рассчитаем новую систему потенциалов.

Припишем значения потенциалов соответствующим строкам и столбцам (рис.30).

Вычислим значения невязок для всех клеток без перевозок.

Запишем их в правый верхний угол каждой клетки. В ряде клеток наблюдаются нарушения (невязки больше нуля). Выберем клетку с наибольшим превышением, равную 1. Построим замкнутый цикл с началом в этой клетке. Пронумеруем клетки.

Нечетные вершины образуют положительную полуцепь. Четные вершины отрицательную. Величина . Получим новое опорное решение на рис. 30.

Вычислим суммарную стоимость перевозок для полученного опорного плана:

Уменьшение стоимости перевозок по сравнению с начальным планом составило  Теоретически это уменьшение равно , т.е. те же 80 ( 80*1).

 Рис.30

Рассчитаем систему потенциалов для полученного опорного решения.

Припишем значения потенциалов соответствующим строкам и столбцам (рис.31).

Вычислим значения невязок для всех клеток без перевозок. Все невязки неположительные, следовательно, опорное решение найдено.

 Рис.31

Заметим, что результат суммарной минимальной стоимости перевозок совпадает с результатом, полученным при помощи надстройки «Поиск решения».