29/11/2022

ступеньками

Проблема планирования
Домашняя страница
Вики

Ступенька

Задача, решаемая алгоритмом Stepping stone, состоит в следующем:

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

Давайте возьмем пример, чтобы показать, как работает алгоритм. Рассмотрим четыре происхождения и пять заявителей со стоимостью и количеством согласно таблице:

противij
Д1
Д2
Д3
Д4
Д5
предложение
О1
7
12
1
5
6
12
О2
15
3
12
6
14
11
О3
8
16
10
12
7
14
О4
18
8
17
11
16
8
запрос
10
11
15
5
4
 L’idée du stepping stone est de partir d’une основное решение réalisable (non optimale) afin de l’améliorer itérativement jusqu’à obtenir une solution non optimisable. Il n’existe pas de meilleure solution, donc elle est optimale. Il est important de vérifier que l’offre et la demande soit égales, si ce n’est pas le cas il faut rajouter une demande fictive de coût important pour chaque offre.

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

Ступенька – Шаг 1: получение базового решения

По северо-западному углу

Принцип прост:

1. Выберите ячейку северо-западного угла и назначьте как можно больше единиц (минимальные потребности), доступных для спроса и предложения.
2. Отрегулируйте значения спроса и предложения в соответствующих строках и столбцах.
3. Если запас первой строки исчерпан, спуститься к первой ячейке следующей строки
4. Если запрос на первую ячейку удовлетворен, перейти по горизонтали к следующей ячейке
5. Если для ячейки предложение равно спросу, следующее распределение может быть сделано в ячейке либо в следующей строке, либо в следующем столбце.
6. Продолжайте процедуру до тех пор, пока общее доступное количество не будет полностью распределено по ячейкам, как это необходимо.
фij
Д1
Д2
Д3
Д4
Д5
предложение
О1
10
2
–
–
–
12
О2
–
9
2
–
–
11
О3
–
–13
1
–
14
О4
–
–
–
4
4
8
запрос
10
11
15
5
4

Общая стоимость базового решения: 10*7+2*12+9*3+2*12+13*10+12+4*11+4*16 = 395.

Во многих случаях невозможно удовлетворить запрос, этот метод, хотя и быстрый, дает нереалистичное возможное решение. Здесь мы представляем не затраты, а потоки fij предложения я на запрос я.

По методу минимумов

1. Определите коробку с минимальной стоимостью транспортировки единицы c.ij.
2. Если минимальная стоимость не уникальна, вы можете выбрать любую ячейку.
3. Выберите максимально возможное значение xij соответствующие, в зависимости от ограничений мощности и требований.
4. Повторяйте шаги 1-3, пока не будут соблюдены все ограничения.
алгоритм ступенчатого камня проблема планирования баласа-молота Фогель

Методом Фогеля (или Баласа-Хаммера)

Этот метод использует транспортную разницу между двумя лучшими вариантами спроса и предложения. Базовое решение часто очень близко к оптимальному решению.

1. Определите штрафную стоимость для каждой строки (столбца) путем вычитания наименьшей стоимости элементарной ячейки в строке (столбце) из наименьшей стоимости элементарной ячейки в той же строке (столбце).

2. Определите строку или столбец с наибольшей стоимостью штрафа. Произвольно прерывайте ссылки (если они есть). Выделите как можно больше переменной с наименьшей стоимостью единицы в выбранной строке или столбце. Скорректируйте спрос и предложение и вычеркните уже удовлетворенную строку или столбец. Если строка и столбец удовлетворяются одновременно, вычеркните только один из двух и присвойте оставшемуся нулевое предложение или спрос.
 

3.

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

Во всех остальных случаях перейдите к шагу 1.

Первая итерация метода дает: DО1 = 4, ДО2 = 3, ДО3 = 1, ДО4 = 3, ДД1 = 1, ДД2 = 5, ДД3 = 9, ДД4 = 1, ДД5 = 2. Колонка D3 имеет наибольшую разницу в стоимости, наименьшая стоимость равна 1, поэтому мы насыщаем пересечение O1 с участием3 с потоком min(12, 15). Предложение О1 поэтому является насыщенным.

фij
Д1
Д2
Д3
Д4
Д5
предложение
О1
Икс
Икс
12
Икс
Икс
12
О2
–
–
–
–
–
11
О3
–
––
–
–
14
О4
–
–
–
–
–
8
запрос
10
11
15
5
4

Для нового расчета разницы затрат мы больше не будем учитывать значения строки О1. Получим после 5 итераций следующую конфигурацию:

фij
Д1
Д2
Д3
Д4
Д5
предложение
О1
–
–
12
–
–
12
О2
–
11
–
–
–
11
О3
10––
–
4
14
О4
–
–
3
5
–
8
запрос
10
11
15
5
4

Ступенька – Шаг 2: расчет потенциалов

Когда у вас есть базовое решение, идея состоит в том, чтобы изменить решение, чтобы сделать его лучше. То есть волны должны быть модифицированы. Для этого мы выберем поток, который максимально снижает общие транспортные расходы. Первым шагом в определении этого потока является расчет потенциалов. Потенциалы рассчитываются ТОЛЬКО на площадях с ненулевым потоком!

Присвоим потенциалу 0 линию с ящиком, имеющим поток с наибольшей стоимостью. Здесь мы возьмем базовое решение, обеспечиваемое методом северо-западного угла: pО1 = 0.

Затем мы можем вычислить другие потенциалы. Потенциалы рассчитываются поэтапно. В нашем случае мы вычислили потенциал строки 1 из c12, поэтому можно рассчитать потенциал столбца 1 или столбца 2.

 Для расчета потенциалов применим следующее правило: pД +рО = сij что дает N уравнений с N неизвестными.

Давайте снова возьмем пример: для столбца 1 pД1 = с11 + ПО1 = 7. Для строки 2, pД2 = с12 + ПО1 = 12. Аналогично для остальных строк и столбцов: pО2  =рД2 - против22 = 12 -3 = 9; пД3 = 21; п03 = 11; пД4 =23:ПО4 = 12; пД5 = 28.

Шаг 3: расчет изменения удельной стоимости

Для каждого ящика с нулевым потоком вычисляем vij путем добавления потенциала связанного источника к стоимости единицы пространства и вычитания потенциала соответствующего пункта назначения: vij = сij -пой -пдиджей.

Получаем следующую таблицу:

вij
Д1
Д2
Д3
Д4
Д5
пО
О1
–
–
-20
-18
-19
0
О2
17
–
–
-8
-5
9
О3
1215–
–
-10
11
О4
23
8
8
–
–
12
пД
7
12
21
23
28

Шаг 4: расчет максимального объема потока

Теперь мы знаем изменение стоимости единицы товара в зависимости от пункта отправления и назначения по сравнению с первоначальным решением. Теперь мы должны определить контуры потока, позволяющие снизить общую стоимость. Этот расчет делается только для vij отрицательный.
 Чтобы заполнить пустой ящик, вы должны опустошить полный ящик. При поиске контура («петли») мы должны следить за тем, чтобы квадрат с потоком всегда следовал за последним выбранным квадратом контура. Таким образом, схема состоит из пустого квадрата и полных квадратов. Максимальный поток, который можно переместить, чтобы заполнить пустой ящик, равен минимуму потоков ненулевых ящиков.

Например, для поля 01-Д3, возьмем следующую схему f13 -> ф12 -> ф22 -> ф23 -> ф13 с минимальным потоком 2. Получаем следующую таблицу:

фij
Д1
Д2
Д3
Д4
Д5
пО
О1
–
–
2
1
1
0
О2
––
–
1
1
9
О3
–––
–
1
11
О4
–
–
–
–
–
12
пД
7
12
21
23
28

Умножая fij*вij, мы знаем изменение полной стоимости от модификации потоком fij. Выбираем коробку с наибольшим fij*вij, здесь поле О1-Д3

Шаг 5: Обновленная таблица

Расчет обновления потока производится по правилу «+-» без учета возврата в исходную коробку. Так в схеме: f13 += 2, ф12 -=2, ф22 += 2 и f23 -= 2. Таблица выглядит следующим образом:

фij
Д1
Д2
Д3
Д4
Д5
предложение
О1
10
2-2 = –
0+2 = 2
–
–
12
О2
–9+2 = 11
2-2 = –
–
–
11
О3
––13
1
–
14
О4
–
–
–
44
8
запрос
10
11
15
5
4

Общая стоимость базового решения: 10*7+2*12+9*3+2*12+13*10+12+4*11+4*16 = 395. Стоимость этого решения: 10 * 7+11*3+2*1+13*10+12+4*11+4*16 = 355. Пусть базовое решение минус f13*в13 = 2*20 = 40.

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

В нашем примере мы получим следующую таблицу:

фij
Д1
Д2
Д3
Д4
Д5
предложение
О1
–
–
12
–
–
12
О2
–11
–
–
–
11
О3
10––
–
4
14
О4
–
–
3
5–
8
запрос
10
11
15
5
4

При общей стоимости: 10*8+11*3+12*1+3*17+5*11+4*7 = 259.

в стороне

Nous parlons de flot car le problème est résolu comme un problème de min cost flow (максимальный расход au coût minimum) dans un график biparti complet – un ensemble de sources reliés à un ensemble de puits  (d’où la règle du « + – » puisque l’on va une fois dans le sens du flot puis à contresens dans le circuit choisi).

алгоритм ступенчатого камня проблема планирования баласа-молота Фогель

Делиться
ru_RURU
ru_RURU fr_FRFR en_GBEN es_ESES
%d такие блоггеры, как: