Автор: Пользователь скрыл имя, 01 Декабря 2011 в 15:15, реферат
1. Формализация проблемы в виде транспортной таблицы по аналогии с решением транспортной задачи.
2. В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки.
3. Повторить ту же самую процедуру для столбцов.
Минимальную дальность перевозок для каждого из трех решений можно вычислить из исходной таблицы:
Решение 1: 68 + 60 + 35 + 45 - 208 миль;
Решение 2: 68 + 63 + 35 + 42 = 208 миль;
Решение 3: 72 + 56 +
35 + 45 = 208 миль.
Общая дальность перевозок для всех трех
решений одинакова.
Примечание: в задачах большей размерности, чем задача из примера 13.7. убедиться в том, что проведенное в соответствии г пунктом 1 этапа 3 число прямых является минимальным, гораздо труднее. В этой связи может оказаться полезным так называемое "правило правой руки":
1. Выбирается любая строка или столбец, содержащие только один нулевой элемент.
2. Если выбрана строка, прямая проводится через столбец, в котором находился данный нулевой элемент.
3. Если выбран
столбец, прямая проводится
4. Пункты 1-3 повторяются до тех пор, пока не будут учтены все входящие в таблицу нули.
http://sider.home.nov.ru/book/
http://habrahabr.ru/blogs/