Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
В. 43 Алгоритм метода потенциалов
|
|
Метод потенциалов предназначен для решения транспортной задачи в матричной постановке. Потенциалы - это двойственные переменные. Сам метод - прямой, на каждом шаге выбирается одно из двойственных ограничений, которое не выполняется и исправляется таким образом, чтобы не нарушить ограничения прямой задачи. Постепенно в двойственной задаче ограничения будут выполнены, что будет означать оптимальность в прямой задаче.
Таблица для метода потенциалов имеет следующий вид:
| b1… | bj | ...bn | u | |
| a1 … | u1 … | |||
| ai | cij | ui | ||
| xij | ||||
| … am | … um | |||
| v | v1 | vj | …vn | z |
Каждая ячейка (i, j) таблицы хранит информацию о цене (сij) и о количестве перевозимого товара (xij). В процессе решения задачи часть клеток будем называть базисными (их всегда будет m+n-1), а остальные - небазисными (или свободными).
Алгоритм
Шаг 0. Замкнуть задачу, если она не замкнута. Перейти на шаг 1.
Шаг 1. Нарисовать начальную таблицу. Перейти на шаг 2.
Шаг 2. Рассчитать начальный план перевозок (например, методом северо-западного угла) и выделить базисные клетки. Вычислить значение целевой функции. Перейти на шаг 3.
Шаг 3. Рассчитать значения потенциалов. Положить u1=0 (или любому другому числу). Остальные потенциалы рассчитать с помощью базисных клеток, исходя из уравнения ui+vj=cij. Перейти на шаг 4.
Шаг 4. Для свободных клеток рассчитать оценки sij=cij-vi-vj. Если все sij≥0, то найдено оптимальное решение. Перейти на шаг 6. Иначе выполнить шаг 5.
Шаг 5. Из небазисных клеток выбрать ту, у которой оценка sij минимальна и для нее выполнить следующую процедуру:
• Построить цикл для этой клетки. Цикл - это замкнутая ломаная линия, которая чередует вертикальное и горизонтальное направления и проходит только по базисным клеткам. В исходной клетке поставить «+» и далее по циклу расставить, чередуя, «+» и «-».
• Вычислить λ=min{xij: «-»}. Клетку, на которой достигается этот минимум, убрать из базиса (только одну), а клетку (i,j) (у которой минимальная оценка sij) сделать базисной.
• Нарисовать новую таблицу, с пересчитанным планом перевозок: для клеток с «+» прибавить λ к хij а для клеток с «-» - вычесть. Остальные клетки остаются как были. Пересчитать целевую функцию: z’=z+min sij *λ.
Перейти на шаг 3.
Шаг 6 Конец алгоритма.
На шаге 3 у нас m+n-1 уравнений и n+m неизвестных. Поэтому возникает неоднозначность, разрешить которую можно, определив одну из переменных заранее (например, u1=0).
Date: 2015-12-12; view: 545; Нарушение авторских прав