Лекции.Орг


Поиск:




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




1. проверяется тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой;

2. находится опорный план перевозок путем составления 1-й таблицы одним из способов - северо-западного угла или наименьшей стоимости;

3. проверяем план (таблицу) на удовлетворение системе уравнений и на невыражденность; в случае вырождения плана добавляем условно заполненные клетки с помощью «0»;

4. для опорного плана определяются потенциалы ui и vj, соответствующие базисным клеткам, по условию:

ui + vj = cij

Таких уравнений будет m + n - 1, а переменных будет m + n. Для их определения одну из переменных полагают равной любому постоянному значению. Обычно принимают u1 = 0.

После этого для небазисных клеток опорного плана определяются оценки ,

где

При этом если £0, то опорный план оптимален, если же среди окажется хотя бы один положительный элемент, то опорный план можно улучшить.

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

Циклом транспортной таблицы называется последовательное соединение замкнутой ломаной линией некоторых клеток, расположенных в одном ряду (строке, столбце), причем число клеток в одном ряду должно быть равно двум.

Каждый цикл имеет четное число вершин, одна из которых в клетке с небазисной переменной, другие вершины в клетках с базисными переменными. Клетки отмечаются знаком «+», если перевозки в данной клетке увеличиваются и знаком «–» в противном случае. Цикл начинается и заканчивается на выбранной небазисной переменной и отмечается знаком «+». Далее знаки чередуются.

Количество единиц продукта, перемещаемого из клетки в клетку по циклу, постоянно, поэтому сумма перевозок в каждой строке и в каждом столбце остаются неизменными. Стоимость всего плана изменяется на цену цикла.

Цена цикла – это стоимость перевозки единицы продукта по циклу с учетом знаков вершин.

Улучшение опорного плана осуществляется путем нахождения цикла с отрицательной ценой.

5. Если критерий оптимальности не выполняется, то переходим к следующему шагу. Для этого:

а) в качестве начальной небазисной переменной принимается та, у которой оценка имеет максимальное значение;

б) составляется цикл пересчета;

в) находится число перерасчета по циклу: число X=min{Xij}, где Xij - числа в заполненных клетках со знаком «-»;

г) составляется новая таблица, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла;

6. Возвращаются к пункту 3 и т.д.

7. Через конечное число шагов (циклов) обязательно приходят к ответу, так как транспортная задача всегда имеет решение.





Поделиться с друзьями:


Дата добавления: 2016-12-04; Мы поможем в написании ваших работ!; просмотров: 481 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Либо вы управляете вашим днем, либо день управляет вами. © Джим Рон
==> читать все изречения...

634 - | 502 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.