Алгоритмы методов нахождения
Автор: Cvicky • Март 30, 2019 • Контрольная работа • 385 Слов (2 Страниц) • 322 Просмотры
АЛГОРИТМЫ МЕТОДОВ НАХОЖДЕНИЯ
НАЧАЛЬНОГО ОПОРНОГО ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ
- Метод Северо-Западного угла
1. i = 0, j = 0;
2. В i-й строке таблицы (матрица С) выбирается элемент x[i][j], в который записывается значение min(A[i], B[j]).
3. Остальные значения определяются в виде: A[i] = A[i] – min(A[i], B[j]),
В[j] = B[j] – min(A[i], B[j]).
4. Если В[j] = 0, то остальным элементам матрицы x[i][j] данной строки
присваивается значение 0.
В противном случае остальным элементам матрицы x[i][j] данной строки
присваивается значение min(A[i], B[j]) (j = 0, 1, 2, ..., n).
5. i = i + 1, j = 0. Перейти к п.2.
- Метод Минимальной стоимости
Отличается от метода северо-западного угла тем, что в нем на каждом шаге учитывается стоимость перевозки.
В этом случае в первую очередь заполняются клетки с минимальной стоимостью.
- Метод Двойного предпочтения
1. В каждом столбце таблицы (матрица С) отмечается галочкой клетка
с наименьшей стоимостью.
2. В каждой строке таблицы (матрица С) отмечается галочкой клетка с наименьшей
стоимостью.
3. Минимально возможные объемы перевозок помещаются в клетки таблицы
(матрица С), отмеченные двойной галочкой.
4. Минимально возможные объемы перевозок помещаются в клетки таблицы
(матрица С), отмеченным одной галочкой, начиная с наименьшего значения
стоимости.
5. В оставшихся клетках таблицы (матрица С) объемы перевозок распределяют
по методу минимальной стоимости.
- Метод Аппроксимации Фогеля
1. Для каждой строки таблицы тарифов определить величину "штрафа" строки как
модуля разности значений второго и первого минимального по стоимости
элемента.
2. Для каждого столбца таблицы тарифов необходимо определить величину
штрафа столбца как модуля разности значений второго и первого минимального
по стоимости элемента.
...