Задание к контрольной работе по теме 2.3

Задачи 401 – 500 [3] изображены в виде неориентированного связного графа. На ребрах записаны значения удельных стоимостей , на вершинах (в кружках) – значения запасов-потребностей . Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.

Вопросы для самопроверки

1. Приведите общую формулировку линейной сетевой задачи по критерию стоимости. Запишите математическую модель прямой задачи и двойственную к ней.

2. Покажите, что транспортная задача в матричной постановке является частным случаем транспортной задачи в сетевой постановке.

3. Дайте определение понятия «остов сети». Какая связь существует между остовом сети и базисом транспортной задачи в сетевой постановке?

4. Какой план перевозок называют невырожденным?

5. Каким способом можно получить допустимый план в транспортной сети? Назовите требования, предъявляемые к опорному плану.

6. Перечислите основные этапы метода потенциалов для транспортной задачи в сетевой постановке.

7. Как вычисляются потенциалы и оценки?

8. Что называется разрешающей стрелкой? Каково должно быть направление разрешающей стрелки?

9. Что называется циклом пересчета в сетевой задаче?

10. Как определяется величина корректировки плана?

11. Что надо делать, если величина корректировки достигается на нескольких перевозках? Можно ли менять направление нулевых перевозок, появившихся в этом случае?

12. Как в процессе улучшения плана изменяются перевозки в цикле пересчета и перевозки, не вошедшие в цикл пересчета?

13. Назовите способы вычисления целевой функции для начального опорного плана и для последующих планов.

14. В каком случае в сетевой задаче коммуникация, только что вышедшая из базиса, снова имеет наибольшую положительную оценку?

15. В чем состоит задача о кратчайшем пути?