Таблиця № 4
ПН |
B1 |
B2 |
B3 |
B4 |
B5 |
Запаси |
A1 |
10 |
8 |
5 |
6 |
9 |
48 |
A2 |
6 |
7 |
8 |
6 |
5 |
30 |
A3 |
8 |
7 |
10 |
8 |
7 |
27 |
A4 |
7 |
5 |
4 |
6 |
8 |
20 |
Заявки |
18 |
27 |
42 |
12 |
26 |
125 |
На цьому способі зменшення вартості в подальшому і буде заснований алгоритм оптимізації плану перевезень. Циклом в транспортній задачі ми будемо називати кілька зайнятих клітин, з'єднаних замкнутої, ламаної лінією, яка в кожній клітині робить поворот на 90 °.
Існує кілька варіантів циклу:1. 2. 3.
Неважко переконатися, що кожен цикл має парне число вершин і значить, парне число ланок (стрілок). Домовимося відзначати знаком «+» ті вершини циклу, в яких перевезення необхідно збільшити, а знаком «-» , ті вершини, в яких перевезення необхідно зменшити. Цикл із зазначеними вершинами будемо називати зазначеним. Перенести якусь кількість одиниць вантажу по зазначеному циклу, це означає збільшити перевезення, що стоять в позитивних вершинах циклу, на цю кількість одиниць, а перевезення, що стоять в негативних вершинах зменшити на ту ж