Контенус
Ступенька
Задача, решаемая алгоритмом 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 |
Алгоритм можно реализовать с помощью двух таблиц (одна для затрат, другая для потоков). Также можно отобразить оба значения в одном поле, поскольку будет меняться только поток.
Ступенька – Шаг 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 предложения я на запрос я.
По методу минимумов
2. Если минимальная стоимость не уникальна, вы можете выбрать любую ячейку.
3. Выберите максимально возможное значение xij соответствующие, в зависимости от ограничений мощности и требований.
4. Повторяйте шаги 1-3, пока не будут соблюдены все ограничения.
Методом Фогеля (или Баласа-Хаммера)
Этот метод использует транспортную разницу между двумя лучшими вариантами спроса и предложения. Базовое решение часто очень близко к оптимальному решению.
1. Определите штрафную стоимость для каждой строки (столбца) путем вычитания наименьшей стоимости элементарной ячейки в строке (столбце) из наименьшей стоимости элементарной ячейки в той же строке (столбце).
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: расчет потенциалов
Когда у вас есть базовое решение, идея состоит в том, чтобы изменить решение, чтобы сделать его лучше. То есть волны должны быть модифицированы. Для этого мы выберем поток, который максимально снижает общие транспортные расходы. Первым шагом в определении этого потока является расчет потенциалов. Потенциалы рассчитываются ТОЛЬКО на площадях с ненулевым потоком!
Затем мы можем вычислить другие потенциалы. Потенциалы рассчитываются поэтапно. В нашем случае мы вычислили потенциал строки 1 из c12, поэтому можно рассчитать потенциал столбца 1 или столбца 2.
Давайте снова возьмем пример: для столбца 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: расчет изменения удельной стоимости
Получаем следующую таблицу:
вij | Д1 | Д2 | Д3 | Д4 | Д5 | пО |
О1 | – | – | -20 | -18 | -19 | 0 |
О2 | 17 | – | – | -8 | -5 | 9 |
О3 | 12 | 15 | – | – | -10 | 11 |
О4 | 23 | 8 | 8 | – | – | 12 |
пД | 7 | 12 | 21 | 23 | 28 |
Шаг 4: расчет максимального объема потока
Например, для поля 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 | – | – | – | 4 | 4 | 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.
В нашем примере мы получим следующую таблицу:
ф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.
в стороне
Мы говорим о потоке, потому что проблема решается как задача о потоке с минимальными затратами (максимальный поток при минимальных затратах) в полном двудольном графе — наборе источников, соединенных с набором стоков (отсюда и правило «+-», поскольку мы идем один раз). в направлении потока, а затем в противоположном направлении в выбранном контуре).
RU 
FR 
EN 
ES