Лабораторная работа № 4

Закрытая транспортная задача

Цель работы: изучить математическую модель транспортной задачи, овладеть методами решения этой задачи.

Задания для подготовки к работе

1. Изучить содержательную и математическую постановки закрытой транспортной задачи, методы нахождения первого опорного решения ее системы ограничений. Изучить понятие цикла пересчета в матрице перевозок. Овладеть распределительным методом и методом потенциалов, а также их алгоритмами.

2. Составить и отладить программы решения транспортной задачи распределительным методом и методом потенциалов.

3. Для подготовки тестовых данных решить вручную одну из следующих ниже задач.

Варианты заданий

1.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

Контрольные вопросы

1. Как формулируется транспортная задача? Что такое матрица перевозок? Как выглядит математическая модель закрытой транспортной задачи?

2. Как записать транспортную задачу в форме таблицы данных?

3. Нахождение первого опорного решения системы ограничений транспортной задачи. В чем заключаются метод северо-западного угла и метод наименьшей стоимости?

4. Что называют циклом в матрице? Какими комбинаторными свойствами обладают циклы?

5. Означенный цикл. Что называют сдвигом по означенному циклу в матрице перевозок? Каким основным свойством обладает этот сдвиг?

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

7. Как находятся коэффициенты при свободных переменных в базисном виде системы ограничений транспортной задачи?

8. Как находится выражение целевой функции транспортной задачи через свободные переменные для произвольного базисного вида системы ограничений?

9. В чем заключается распределительный метод решения закрытой транспортной задачи?

10. Опишите порядок работы по методу потенциалов.