Г. Способы построения опорного плана
Способ «северо-западного угла». Первой загружается клетка (1;1). Если закрывается строка, то следующей загружается клетка (2;1); если же закрывается столбец, то следующей загружается клетка (1;2). Итак, каждый раз загружается клетка, соседняя либо по строке, либо по столбцу (в зависимости от конкретных данных задачи). Последней будет загружена клетка (m;n). В результате загруженные клетки расположатся вдоль диагонали (1;1) – (m;n), поэтому способ «северо-западного угла» называют еще диагональным способом.
(Учащиеся читают способ «северо-западного угла» и пытаются самостоятельно построить опорный план)
|
(75) |
(80) |
(60) |
(85) |
(100) |
6
|
7
|
3
|
5
|
(150) |
1
|
2
|
5
|
6
|
(50) |
3
|
10
|
20
|
1
|
(Как вы думаете, чему будет равна целевая функция?)
д.е.
Способ «минимального элемента». Первой в распределительной таблице загружается клетка с наименьшим тарифом. Далее загружается клетка той же строки (столбца) со следующим по величине тарифом и т.д.
Поскольку при заполнении таблицы учитываются величины тарифов, то, как правило, построенный план оказывается ближе к оптимальному, нежели построенный способом «северо-западного угла».
(Учащиеся читают способ «минимального элемента» и пытаются самостоятельно построить опорный план)
|
(75) |
(80) |
(60) |
(85) |
(100) |
6
|
7
|
3
|
5
|
(150) |
1
|
2
|
5
|
6
|
(50) |
3
|
10
|
20
|
1
|
(Как вы думаете, чему будет равна целевая функция?)
д.е.
(Разбор ошибок?)
(Почему построенные нами планы являются опорными?) (Проверка двух условий)
Д. Оценка опорного плана
Оценка опорного плана связана со следующим свойством циклов: если в транспортной таблице содержится опорный план, то для каждой свободной клетки можно образовать один, и притом только один, цикл, содержащий эту свободную клетку и некоторую часть загруженных клеток. Эти циклы изображаются в транспортной таблице контурами, одна вершина которых находится в свободной клетке, а остальные – только в загруженных.
Пусть клетка (k;s) свободная, построим для нее цикл и обозначим алгебраическую сумму тарифов следующим образом.
(6)
Величина
называется оценкой свободной клетки
(k;s).
Если оценка свободной клетки отрицательная, то её следует загружать, такие клетки называются перспективными. Если же оценки всех свободных клеток неотрицательные, то содержащийся в распределительной таблице опорный план является оптимальным.
Пример 2: Исследовать построенный опорный план транспортной задачи на оптимальность. (Учащиеся по очереди выходят к проектору и находят оценку каждой свободной клетки )
|
(75) |
(80) |
(60) |
(85) |
(100) |
6 75 |
7 25 |
3
|
5
|
(150) |
1
|
2 55 |
5 60 |
6 35 |
(50) |
3
|
10
|
20
|
1 50 |
3-5+2-7=-7
|
(75) |
(80) |
(60) |
(85) |
(100) |
6 75 |
7 25 |
3
|
5
|
(150) |
1
|
2 55 |
5 60 |
6 35 |
(50) |
3
|
10
|
20
|
1 50 |
5-6+2-7=-6
|
(75) |
(80) |
(60) |
(85) |
(100) |
6 75 |
7 25 |
3
|
5
|
(150) |
1
|
2 55 |
5 60 |
6 35 |
(50) |
3
|
10
|
20
|
1 50 |
1-6+7-2=0
|
(75) |
(80) |
(60) |
(85) |
(100) |
6 75 |
7 25 |
3
|
5
|
(150) |
1
|
2 55 |
5 60 |
6 35 |
(50) |
3
|
10
|
20
|
1 50 |
3-6+7-2+6-1=7
|
(75) |
(80) |
(60) |
(85) |
(100) |
6 75 |
7 25 |
3
|
5
|
(150) |
1
|
2 55 |
5 60 |
6 35 |
(50) |
3
|
10
|
20
|
1 50 |
10-2+6-1=13
|
(75) |
(80) |
(60) |
(85) |
(100) |
6 75 |
7 25 |
3
|
5
|
(150) |
1
|
2 55 |
5 60 |
6 35 |
(50) |
3
|
10
|
20
|
1 50 |
20-5+6-1=20
(Какие действия мы должны произвести, чтобы определить является ли опорный план, содержащийся в транспортной таблице, оптимальным?)