2015-04-30
684
Метод состоит в том, что для каждой свободной клетки составляется и оценивается цикл. Цикл – это прямоугольная фигура, в которой все клетки, кроме первой, заняты. Наиболее типичные примеры циклов приведены на рисунке 3.2.
Рисунок 3.2 – Примеры циклов транспортных перестановок
В таблице 3.2.3 приведены циклы для исходной задачи, представленной в таблице 3.2.1. В пустой клетке ставим минус, а далее по порядку плюс, минус, плюс, минус и т.д.
Таблица 3.2.3 – Составление и оценка циклов для оптимизации плана перевозок
|
Оценки циклов:
- + 72 – 22 + 16 – 40 = +26;
- +25 – 22 + 16 – 52 = -33;
- +40 – 22 + 16 – 52 + 12 – 11 = -17;
+15 – 70 + 22 – 8 = -41;
+10 – 8 + 16 – 40 = -22;
+4 – 8 + 16 – 52 = -40;
+15 – 11 + 12 – 52 + 16 – 8 = -28;
+27 – 70 + 22 – 16 = -37;
+52 – 52 + 12 – 11 = +1;
+55 – 70 + 22 – 16 + 52 – 12 = +31;
+8 – 16 + 52 – 12 = +32;
+52 – 40 + 52 – 12 = +52.
Перестановки осуществляются по циклу с наибольшей по модулю отрицательной оценкой. В данном случае это цикл, составленный для клетки А2-В4, имеющий оценку -40. По циклу переставляется минимальное число, стоящее в отрицательной вершине. Здесь в отрицательных вершинах стоят 154 и 127 единиц товаров. Переставляем 127 путем вычитания его из отрицательных вершин и прибавления в положительные.
|
|
|
В результате получается новый план, приведенный в таблице 3.2.4.
Таблица 3.2.4 – План перевозок после первой перестановки
| Запасы поставщиков | Потребности потребителей | ||||
| B1=100 | B2=200 | B3=50 | B4=252 | B5=77 | |
| A1=152 | |||||
| A2=127 | |||||
| A3=225 | |||||
| A4=175 | |||||
Для этого плана снова составляются и оцениваются все циклы, Процедура повторяется до тех пор, пока есть отрицательные циклы.
После каждой итерации вычисляется целевая функция – суммарные затраты на перевозку. В данном случае
F = 70 × 100 + 22 × 52 + 4 × 127 + 16 × 148 + 40 × 50 + 52 × 27 + 12 × 98 + 11 × 77 = = 16 447 уд.е.
При использовании данного метода для наглядности каждый цикл рекомендуется обозначать своим цветом.
