Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм метода потенциалов

 

Наиболее распространенным методом решения транспортных задач является метод потенциалов.

Решение задачи методом потенциалов включает следующие этапы:

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, условие выполняется, следовательно, план — оптимальный.

Транспортные издержки по оптимальному плану следующие:

Таким образом, построением начального плана с последующим расчетом двух итераций получено оптимальное решение по при­креплению пунктов отправления грузов к пунктам назначения.


<== предыдущая лекция | следующая лекция ==>
Постановка задачи. Транспортные задачи линейного программирования | Основные понятия. Моделирование систем поддержки принятия решений
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 4422; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.018 сек.