r/>
1. Занесемо дані завдання у таблицю:
У 1
У 2
У 3
У 4
У 5
В
А 1
5
8
7
10
3
100
А 2
4
2
2
5
6
200
А 3
7
3
5
9
2
200
А 4
5
7
4
2
5
100
В
190
100
130
80
100
600
2. Складаємо математичну модель задачі: для цього вводимо невідомі х ij , якими є кількість одиниць товару, що перевозиться від кожного постачальника до кожного споживача.
обмеження з постачань
обмеження по споживачам
(, (обмеження по здоровому глузду.
Мета завдання (вартість усієї перевезення) в математичній формі:
В
Задача розв'язана, тому що br/>
.
3. Знаходимо оптимальний план за методом найменшого елемента
У 1
У 2
У 3
У 4
У 5
В
А 1
5100
87
76
108
33
100
А 2
4-2 +
270 -
2130
53
65
200
А 3
- 770
+330
52
95
2100
200
А 4
520
76
43
280
55
100
В
190
100
130
80
100
600
- план невироджений
В
Дамо оцінку отриманим планом методом потенціалів. Кожному постачальнику А i ставимо у відповідність число (, зване потенціалом постачальника; кожному споживачеві B j - число (, зване потенціалом споживача. Причому і вибираємо так, щоб у будь завантаженої клітці сума їх дорівнювала тарифом цієї клітини, тобто p> Всього зайнятих клітин m + n - 1 = 8 (план не вироджений). Надаємо одному з невідомих значення 0.
Для визначення потенціалів складаємо систему:
В
Звідки
В
Обчислюємо оцінки для вільних клітин за формулою
В
і запишемо їх в лівому куті вільних клітин. У клітці (2; 1) отримали негативну оцінку. Будуємо для неї цикл
В
вздовж якого переміщаємо br/>
.
Отримуємо наступний план перевезень:
У 1
У 2
У 3
У 4
У 5
В
А 1
5100
85
74
108
31
100
А 2
470
20
2130
54
65
200
А 3
72
3100
52
97
2100
200
А 4
520
74
41
280
53
100
В
190
100
130
80
100
600
- план невироджений
В
Дамо оцінку отриманим планом. Всього зайнятих к...