Реферат Курсовая Конспект
Алгоритм метода потенциалов - раздел Экономика, Конспект лекций ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Наиболее Распространенным Методом Решения Транспортных Задач ...
|
Наиболее распространенным методом решения транспортных задач является метод потенциалов.
Решение задачи методом потенциалов включает следующие этапы:
1. разработку начального плана (опорного решения);
2. расчет потенциалов;
3. проверку плана на оптимальность;
4. поиск максимального звена неоптимальности (если условие
п. 3 не было достигнуто);
5. составление контура перераспределения ресурсов;
6. определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;
7. получение нового плана.
Описанная процедура повторяется несколько раз (итераций), пока не будет найдено оптимальное решение. Вычислительный алгоритм для каждой итерации не меняется.
Для транспортной задачи существует несколько методов отыскания начального плана (опорного решения):
- метод северо-западного угла;
- метод минимальной стоимости;
- метод двойного предпочтения и т. д.
Вычислительный алгоритм метода потенциалов рассмотрим на примере решения конкретной задачи прикрепления пунктов отправления i = к пунктам назначения j = . В соответствии с принятыми обозначениями исходные данные задачи приведены в табл. 7.2
Таблица 7.2 – Исходные данные задачи
Начальный план можно составить одним из перечисленных выше методов. Воспользуемся наиболее простым методом — методом северо-западного угла. В соответствии с этим методом загрузка клеток (распределение объемов пунктов отправления по пунктам назначения) начинается с верхней левой клетки («северо-западная» часть таблицы) и продолжается вниз и вправо (по диагонали).
По указанному правилу загружаем первую клетку (i-j) = (1-1) на основании следующего условия:
Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза Δa1 = 60 - 40 = 20, которые и распределяем на второй пункт назначения:
Продолжая преобразования аналогичным образом, получаем:
Результаты начального плана и расчета потенциалов представлены в табл. 8.3.
Таблица 7.3 – Начальный план перевозок
В процессе решения после каждой итерации (в том числе и после получения допустимого решения) по загруженным клеткам проверяется выполнение следующего условия:
N=m+n-1 (7)
В нашем примере m = 3, n=4, а число загруженных клеток равно 6, т. е. соответствует условию (7): N=3 + 4-1=6. Если условие (7) не выполняется, план называется вырожденным. В этом случае в любые свободные клетки надо поставить столько нулей, чтобы с их учетом выполнялось условие (7). Клетка, в которой стоит ноль, считается занятой. Значение целевой функции по результатам расчета допустимого плана
Расчет потенциалов выполняют по загруженным клеткам, для которых должно выполняться следующее равенство:
(8)
где αi, – потенциал i-и строки; βj — потенциал j-го столбца.
Вычисляя потенциалы по выражению (8), принимаем для первой строки
α1 = 0. Используя загруженные клетки (i-j) = (1-1), (1 - 2), получаем:
Далее по загруженным клеткам (2 — 2), (2 — 3) определяем другие потенциалы:
Проверяем план на оптимальность по незагруженным клеткам, используя следующее неравенство:
(9)
Если для незагруженных клеток условие (9) выполняется, то план — оптимальный. По табл. 3 осуществляем проверку начального плана на оптимальность:
Итак, по трем клеткам условие (9) не выполняется, следовательно, начальный план требует улучшения. Характеристики Δcij показывают размер экономии транспортных издержек на 1 ед. перевозимого груза. В нашем примере наибольшую экономию можно получить по клетке (i -j) = (3-1), где Δc31 = 2 > { Δc24; Δc32}. Следовательно, клетку (3-1) необходимо загрузить за счет перераспределения ресурсов из других загруженных клеток. В табл. 3 клетку (3-1) помечаем знаком «+», так как здесь в начальном плане находится вершина максимальной неоптимальности.
Контур перераспределения ресурсов составляют по следующим правилам:
- этот контур представляет замкнутый многоугольник с вершина
ми в загруженных клетках, за исключением клетки с вершиной
максимальной неоптимальности «+», и звеньями, лежащими
вдоль строк и столбцов матрицы;
- ломаная линия должна быть связанной в том смысле, что из любой ее вершины можно попасть в любую другую вершину по
звеньям ломаной цепи (по строке или по столбцу);
- в каждой вершине контура встречаются только два звена, одно
из них располагается по строке, другое — по столбцу;
- число вершин контура четное, все они в процессе перераспределения делятся на загружаемые и разгружаемые;
- в каждой строке (столбце) имеются две вершины: одна — загружаемая, другая — разгружаемая.
В этой клетке намечаем одну из вершин контура и далее по вышеизложенным правилам строим контур, вершины которого будут находиться в клетках (3—1) — (1—1) — (1—2) — (2—2) — (2—3) — (3—3). Вершины контура последовательно подразделяем на загружаемые (З) и разгружаемые (Р), начиная с вершины максимальной неоптимальности «+» (табл. 8.3).
Перераспределение ресурсов по контуру осуществляется с целью получения оптимального плана. В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных xij ни одно из этих значений не должно превратиться в отрицательное число. Поэтому анализируют только клетки, помеченные знаком Р, из которых выбирают клетку с минимальным объемом перевозок. В нашем примере Xmin = min{40; 40; 40} = 40. Следовательно, клетки (1 — 1), (2—2), (3—3) полностью разгружаются. В клетке (1—2) загрузка увеличится на 40 и достигнет 60, в клетке (2—3) загрузка составит 40 + 40 = 80, и клетка (3—1) загрузится на 40 (табл. 4).
Проверяем условие N = m + n - 1. В нашем примере m = 3, n =4, а число загруженных клеток равно 4, т. е. условие не выполняется и 6 ≠ 4. В процессе перераспределения ресурсов произошла полная разгрузка трех клеток, а мы должны освободить только одну клетку. В этом случае следует в две клетки проставить нули (нулевой ресурс) и считать условно их загруженными. Например, в клетки (1 — 1) и (3—3) проставим нулевой ресурс (табл. 14.4). Получение нового плана (итерации) осуществляется в том же порядке, который был рассмотрен выше, т. е.
- по загруженным клеткам (в соответствии с новой загрузкой) вычисляются потенциалы αi, и βj ;
- по незагруженным клеткам производится проверка плана на оптимальность;
- находится вершина максимальной неоптимальности и строится новый контур перераспределения, и т. д., до тех пор, пока не будет найдено оптимальное решение, удовлетворяющее неравенству (9).
Таблица 7.4 – Первый план перевозок
По результатам первой итерации имеем
Ниже приведены расчеты по второй итерации и оптимальный план.
Поиск потенциалов следующий:
Проведем проверку на оптимальность:
Клетку (2-4) необходимо загрузить.
В соответствии с перераспределением ресурсов по контуру получаем табл. 7.5, для которой вновь рассчитываем потенциалы αi, и βj, и последовательность вычислений повторяется.
Таблица 7.5 – Оптимальный план перевозок
Для распределения, полученного в табл. 7.5, условие выполняется, следовательно, план — оптимальный.
Транспортные издержки по оптимальному плану следующие:
Таким образом, построением начального плана с последующим расчетом двух итераций получено оптимальное решение по прикреплению пунктов отправления грузов к пунктам назначения.
– Конец работы –
Эта тема принадлежит разделу:
ГОУ ВПО КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ... УНИВЕРСИСТЕТ Кафедра вычислительной техники и АСУ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм метода потенциалов
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов