![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм построения решения.
1) Проверить выполнение условия закрытости задачи: 2) Построить исходное опорное решение задачи методом минимального тарифа (или методом северо-западного угла). а) Согласно методу минимального тарифа, грузы распределяются в первую очередь в те клетки, в которых находятся минимальный тариф
Клетка б) Количество занятых клеток должно быть равно рангу матрицы ограничений задачи
Если это условие не выполнено, требуется недостающее их число заполнить клетки с нулевыми поставками. Этот условно занятые клетки. в) Применить метод вычеркивания, чтобы проверить, что построенное решение – опорное. Метод вычеркивания: последовательно вычеркиваем строки (столбцы), содержащие только одну занятую клетку. Если в результате все строки и столбцы будут вычеркнуты, то соответствующее решение – опорное.
Исходное решение – опорное. Если же после вычеркиваний останется часть клеток, то решение не является опорным. Надо взять другое исходное решение. г) Рассчитать стоимость перевозки: 3) Построить систему потенциалов в занятых клетках.
Потенциалы
считая, например,
4) Проверить построенное решение на оптимальность. Построенное опорное решение является оптимальным, если для незанятых клеток
Результаты вычислений
Если хотя бы одна из оценок
5) Строим цикл. а) Начинаем цикл с клетки с наибольшим положительным значением
б) Строим цикл с вершинами в занятых клетках (за исключением клетки с максимальным – число вершин четное; – в каждой строке (столбце) имеются две вершины. Получается замкнутый многоугольник. Замечание. Метод вычеркивания требовался для проверки возможности образования циклов в таблице.
в) Чередуем знаки «-» и «+» у вершин цикла.
6) Перейти к новому опорному решению. а) У вершин построенного многоугольника со знаком «-» выбрать минимальный груз б) Перераспределить груз: – прибавить – отнять «-».
В результате перераспределения получаем новое опорное решение.
Повторяем алгоритм. Проверяем условие (5):
Рассчитаем стоимость перевозки: Построим систему потенциалов в занятых клетках.
Проверим построенное решение на оптимальность. Запишем в левом нижнем углу незанятых клеток результаты вычислений
Строим цикл.
Переходим к новому опорному решению.
Получаем новое опорное решение.
Повторяем алгоритм. Проверяем условие (5):
Рассчитаем стоимость перевозки: Построим систему потенциалов в занятых клетках и запишем в левом нижнем углу незанятых клеток результаты вычислений
Построенное опорное решение является оптимальным, так как для всех незанятых клеток
Ответ:
|