Дата конвертації15.07.2017
Розмір78.67 Kb.
Типконтрольна робота

Скачати 78.67 Kb.

Методи вирішення транспортних завдань

1) Виберемо змінними задачі x 1 - виробів виду А1; x 2 - виробів виду А2.

Складемо систему обмежень у вигляді нерівностей

Складемо цільову функцію z (x) = 25 · x 1 + 17 · x 2 → max, тобто забезпечити максимальну виручку від реалізації готової продукції.

2) Знайдемо рішення сформульованої задачі, використовуючи її геометричну інтерпретацію. Спочатку визначимо багатокутник рішень. Для цього в нерівностях системи обмежень і умов невід'ємності змінних знаки нерівностей замінимо на знаки точних рівностей і знайдемо відповідні прямі

Ці прямі зображені на рис. 1. Перетин отриманих напівплощин і визначає багатокутник рішень даної задачі.


Мал. 1. Графічне представлення математичної моделі

Як видно з рис. 1, многоугольником рішень є п'ятикутник ОАВС D. Координати будь-якої точки, що належить даному п'ятикутник, задовольняють даній системі нерівностей і умові незаперечності змінних. Тому сформульована задача буде вирішена, якщо ми зможемо знайти точку, що належить п'ятикутник ОАВС D, в якій функція z приймає максимальне значення. Щоб знайти зазначену точку, побудуємо вектор , Перпендикулярний прямій 25 · x 1 + 17 · x 2 = h, де h - деяка постійна така, що дана пряма має загальні точки з багатокутником рішень.

Переміщаючи, дану пряму в напрямку вектора , Бачимо, що останньою спільною точкою її з багатокутником рішень задачі служить точка B. Координати цієї точки і визначають план виробництва продукції, при якому виручка від їх реалізації буде максимальною.

Знаходимо координати точки C як координати точки перетину прямих 8 · x 1 + 6 · x 2 = 848 і 5 · x 1 + 2 · x 2 = 432.

Вирішивши цю систему рівнянь, отримаємо , . Отже, виручка від реалізації буде найбільшою, якщо в плані по виробництву міститься випуск 64 виробів А1 і 56 виробів А2, і, становить 25 · 64 + 17 · 56 = 2552 ден. од.

3) Запишемо це завдання в формі основного завдання лінійного програмування. Для цього від обмежень-нерівностей перейдемо до обмежень-равенствам. Введемо три додаткові змінні, в результаті чого обмеження запишуться у вигляді системи рівнянь

Складаємо таблицю першої ітерації:

базисні

змінні

25 17 0 0 0

0

0

0

848

532

432

8

3

5

6

5

2

1

0

0

0

1

0

0

0

1

0 -25 -17 0 0 0

В 4-му рядку табл. в шпальтах змінних , , Є негативні числа. Наявність цих чисел говорить про те, що даний план не є оптимальним. Переходимо до нового плану завдання: дозволяє елемент виділено (тут і далі) підкресленням.


друга ітерація

базисні

змінні

25 17 0 0 0

0

0

25

784/5

1364/5

432/5

0

0

1

14/5

19/5

2/5

1

0

0

0

1

0

-8/5

-3/5

1/5

2160 0 -7 0 0 0

третя ітерація

базисні

змінні

25 17 0 0 0

17

0

25

56

60

64

0

0

1

1

0

0

5/14

-19/14

-1/7

0

1

0

-4/7

11/7

3/7

2552 0 0 5/2 0 1

З табл. видно, що знайдений новий опорний план вихідної завдання X * = (64; 56; 0; 60; 0) є оптимальним. При цьому max z = 2552.

Отже, виручка від реалізації буде найбільшою, якщо в плані по виробництву міститься випуск 64 виробів А1 і 56 виробів А2, і, становить 2552 ден. од.

4) Для даного завдання , тоді . Число змінних в двоїстої задачі дорівнює числу рівнянь у вихідній задачі, тобто 3. Коефіцієнти в цільової функції двоїстої задачі є вільними членами нерівностей-обмежень, тобто числами 848, 532, 432. Оскільки, в вихідної системі обмеження представлені нерівностями, то в двоїстої завданню перемінні є невід'ємними.

Отже, двоїста задача така: знайти мінімум функції z * (x) = 848 · y 1 + 532 · y 2 + 432 · y 3 за умов


З останньої симплекс-таблиці (ітерація 3) видно, що двоїста задача має рішення , , .

1) Розподільчий метод

Приймемо деякі позначення: i - індекс рядка j - індекс стовпця m - кількість постачальників n - кількість споживачів X i, j - перевезення між постачальником A i і споживачем B j.

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
0
8
0
17
0
5
0
3
0
370
A2
21
0
10
0
7
0
11
0
6
0
450
A3
3
0
5
0
8
0
4
0
9
0
480
потреба 300 280 330 290 100

Транспортна задача має закритий тип, так як сумарний запас вантажу дорівнює сумарним потребам.Знаходимо опорний план за правилом північно-західного кута: Введемо деякі позначення: A i * - надлишок нерозподіленого вантажу від постачальника A i B j * - недостача в постачанні вантажу споживачеві B j

Розміщуємо в клітку (1,1) менше з чисел A 1 * = 370 і B 1 * = 300 Так як попит споживача B 1 задоволений, то стовпець 1 надалі в розрахунок не береться поміщаємо в клітку (1,2) менше з чисел A 1 * = 70 і B 2 * = 280 Так як запаси постачальника A 1 вичерпані, то рядок 1 в подальшому в розрахунок не береться Розміщуємо в клітку (2,2) менше з чисел A 2 * = 450 і B 2 * = 210 так як попит споживача B 2 задоволений, то стовпець 2 надалі в розрахунок не береться Розміщуємо в клітку (2,3) менше з чисел A 2 * = 240 і B 3 * = 330 так як запаси постачальника A 2 вичерпані, то рядок 2 в подальшому в рас чет не береться Розміщуємо в клітку (3,3) менше з чисел A 3 * = 480 і B 3 * = 90 Так як попит споживача B 3 задоволений, то стовпець 3 надалі в розрахунок не береться Розміщуємо в клітку (3,4) менше з чисел A 3 * = 390 і B 4 * = 290 Так як попит споживача B 4 задоволений, то стовпець 4 надалі в розрахунок не береться Розміщуємо в клітку (3,5) менше з чисел A 3 * = 100 і B 5 * = 100

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
300
8
70
17
5
3
370
A2
21
10
210
7
240
11
6
450
A3
3
5
8
90
4
290
9
100
480
потреба 300 280 330 290 100

Цільова функція F = 11320

Вирішуємо задачу розподільчим методом:

Етап 1

Визначимо значення оцінок S i, j для всіх вільних клітин (неоптимальні виділені червоним кольором). Для цього будуємо цикл для кожної вільної клітини і, переміщаючись по клітинам циклу, складаємо тарифи клітин. При цьому тарифи в непарних клітинах беруться зі знаком "плюс", в парних - зі знаком "мінус". S 1,3 = c 1,3 -c 1,2 + c 2,2 -c 2,3 = 12 S 1,4 = c 1,4 -c 1,2 + c 2,2 -c 2,3 + c 3,3 -c 3,4 = 4 S 1,5 = c 1,5 -c 1,2 + c 2,2 -c 2,3 + c 3,3 -c 3,5 = -3 S 2,1 = c 2,1 -c 2,2 + c 1,2 -c 1,1 = 5 S 2,4 = c 2,4 -c 2,3 + c 3,3 -c 3,4 = 8 S 2,5 = c 2,5 -c 2,3 + c 3,3 -c 3,5 = -2 S 3,1 = c 3,1 -c 3,3 + c 2,3 -c 2 , 2 + c 1,2 -c 1,1 = -14 S 3,2 = c 3,2 -c 3,3 + c 2,3 -c 2,2 = -6


B1 B2 B3 B4 B5
A1 12 4 -3
A2 5 8 -2
A3 -14 -6

За наявності кількох клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш перспективною є клітина (3,1). Для неї оцінка дорівнює -14. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
- 14
300
+ 8
70
17
5
3
370
A2
21
- 10
210
+ 7
240
11
6
450
A3
+ 3
5
- 8
90
4
290
9
100
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 90 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус". В результаті переміщення по циклу отримаємо новий план:

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
210
8
160
17
5
3
370
A2
21
10
120
7
330
11
6
450
A3
3
90
5
8
4
290
9
100
480
потреба 300 280 330 290 100

Цільова функція F = 10060

Значення цільової функції змінилося на 1260 одиниць в порівнянні з попереднім етапом.

етап 2

Визначимо значення оцінок S i, j для всіх вільних клітин (неоптимальні виділені червоним кольором). Для цього будуємо цикл для кожної вільної клітини і, переміщаючись по клітинам циклу, складаємо тарифи клітин. При цьому тарифи в непарних клітинах беруться зі знаком "плюс", в парних - зі знаком "мінус". S 1,3 = c 1,3 -c 1,2 + c 2,2 -c 2,3 = 12 S 1,4 = c 1,4 -c 1,1 + c 3,1 -c 3,4 = -10 S 1,5 = c 1,5 -c 1,1 + c 3,1 -c 3,5 = -17 S 2,1 = c 2,1 -c 2,2 + c 1,2 - c 1,1 = 5 S 2,4 = c 2,4 -c 2,2 + c 1,2 -c 1,1 + c 3,1 -c 3,4 = -6 S 2,5 = c 2 , 5 -c 2,2 + c 1,2 -c 1,1 + c 3,1 -c 3,5 = -16 S 3,2 = c 3,2 -c 3,1 + c 1,1 - c 1,2 = 8 S 3,3 = c 3,3 -c 3,1 + c 1,1 -c 1,2 + c 2,2 -c 2,3 = 14

B1 B2 B3 B4 B5
A1 12 -10 -17
A2 5 -6 -16
A3 8 14

За наявності кількох клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш перспективною є клітина (1,5). Для неї оцінка дорівнює -17. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
- 14
210
8
160
17
5
+ 3
370
A2
21
10
120
7
330
11
6
450
A3
+ 3
90
5
8
4
290
- 9
100
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 100 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус".В результаті переміщення по циклу отримаємо новий план:

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
110
8
160
17
5
3
100
370
A2
21
10
120
7
330
11
6
450
A3
3
190
5
8
4
290
9
480
потреба 300 280 330 290 100

Цільова функція F = 8360

Значення цільової функції змінилося на 1700 одиниць в порівнянні з попереднім етапом.

етап 3

Визначимо значення оцінок S i, j для всіх вільних клітин (неоптимальні виділені червоним кольором). Для цього будуємо цикл для кожної вільної клітини і, переміщаючись по клітинам циклу, складаємо тарифи клітин. При цьому тарифи в непарних клітинах беруться зі знаком "плюс", в парних - зі знаком "мінус". S 1,3 = c 1,3 -c 1,2 + c 2,2 -c 2,3 = 12 S 1,4 = c 1,4 -c 1,1 + c 3,1 -c 3,4 = -10 S 2,1 = c 2,1 -c 2,2 + c 1,2 -c 1,1 = 5 S 2,4 = c 2,4 -c 2,2 + c 1,2 -c 1,1 + c 3,1 -c 3,4 = -6 S 2,5 = c 2,5 -c 2,2 + c 1,2 -c 1,5 = 1 S 3,2 = c 3, 2 -c 3,1 + c 1,1 -c 1,2 = 8 S 3,3 = c 3,3 -c 3,1 + c 1,1 -c 1,2 + c 2,2 -c 2 , 3 = 14 S 3,5 = c 3,5 -c 3,1 + c 1,1 -c 1,5 = 17

B1 B2 B3 B4 B5
A1 12 -10
A2 5 -6 1
A3 8 14 17

За наявності кількох клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш перспективною є клітина (1,4). Для неї оцінка дорівнює -10. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
- 14
110
8
160
17
+ 5
3
100
370
A2
21
10
120
7
330
11
6
450
A3
+ 3
190
5
8
- 4
290
9
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 110 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус". В результаті переміщення по циклу отримаємо новий план:

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
160
17
5
110
3
100
370
A2
21
10
120
7
330
11
6
450
A3
3
300
5
8
4
180
9
480
потреба 300 280 330 290 100

Цільова функція F = 7260

Значення цільової функції змінилося на 1100 одиниць в порівнянні з попереднім етапом.

етап 4

Визначимо значення оцінок S i, j для всіх вільних клітин (неоптимальні виділені червоним кольором). Для цього будуємо цикл для кожної вільної клітини і, переміщаючись по клітинам циклу, складаємо тарифи клітин. При цьому тарифи в непарних клітинах беруться зі знаком "плюс", в парних - зі знаком "мінус". S 1,1 = c 1,1 -c 1,4 + c 3,4 -c 3,1 = 10 S 1,3 = c 1,3 -c 1,2 + c 2,2 -c 2,3 = 12 S 2,1 = c 2,1 -c 2,2 + c 1,2 -c 1,4 + c 3,4 -c 3,1 = 15 S 2,4 = c 2,4 -c 2 , 2 + c 1,2 -c 1,4 = 4 S 2,5 = c 2,5 -c 2,2 + c 1,2 -c 1,5 = 1 S 3,2 = c 3,2 - c 3,4 + c 1,4 -c 1,2 = -2 S 3,3 = c 3,3 -c 3,4 + c 1,4 -c 1,2 + c 2,2 -c 2, 3 = 4 S 3,5 = c 3,5 -c 3,4 + c 1,4 -c 1,5 = 7

B1 B2 B3 B4 B5
A1 10 12
A2 15 4 1
A3 -2 4 7

За наявності кількох клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш перспективною є клітина (3,2). Для неї оцінка дорівнює -2. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".


Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
- 8
160
17
+ 5
110
3
100
370
A2
21
10
120
7
330
11
6
450
A3
3
300
+ 5
8
- 4
180
9
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 160 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус". В результаті переміщення по циклу отримаємо новий план:

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
17
5
270
3
100
370
A2
21
10
120
7
330
11
6
450
A3
3
300
5
160
8
4
20
9
480
потреба 300 280 330 290 100

Цільова функція F = 6940

Значення цільової функції змінилося на 320 одиниць в порівнянні з попереднім етапом.

етап 5

Визначимо значення оцінок S i, j для всіх вільних клітин (неоптимальні виділені червоним кольором). Для цього будуємо цикл для кожної вільної клітини і, переміщаючись по клітинам циклу, складаємо тарифи клітин. При цьому тарифи в непарних клітинах беруться зі знаком "плюс", в парних - зі знаком "мінус". S 1,1 = c 1,1 -c 1,4 + c 3,4 -c 3,1 = 10 S 1,2 = c 1,2 -c 1,4 + c 3,4 -c 3,2 = 2 S 1,3 = c 1,3 -c 1,4 + c 3,4 -c 3,2 + c 2,2 -c 2,3 = 14 S 2,1 = c 2,1 -c 2 , 2 + c 3,2 -c 3,1 = 13 S 2,4 = c 2,4 -c 2,2 + c 3,2 -c 3,4 = 2 S 2,5 = c 2,5 - c 2,2 + c 3,2 -c 3,4 + c 1,4 -c 1,5 = -1 S 3,3 = c 3,3 -c 3,2 + c 2,2 -c 2, 3 = 6 S 3,5 = c 3,5 -c 3,4 + c 1,4 -c 1,5 = 7

B1 B2 B3 B4 B5
A1 10 2 14
A2 13 2 -1
A3 6 7

За наявності кількох клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш перспективною є клітина (2,5). Для неї оцінка дорівнює -1. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
17
+ 5
270
- 3
100
370
A2
21
- 10
120
7
330
11
+ 6
450
A3
3
300
+ 5
160
8
- 4
20
9
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 20 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус". В результаті переміщення по циклу отримаємо новий план:


Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
17
5
290
3
80
370
A2
21
10
100
7
330
11
6
20
450
A3
3
300
5
180
8
4
9
480
потреба 300 280 330 290 100

Цільова функція F = 6920

Значення цільової функції змінилося на 20 одиниць в порівнянні з попереднім етапом.

етап 6

Визначимо значення оцінок S i, j для всіх вільних клітин (неоптимальні виділені червоним кольором). Для цього будуємо цикл для кожної вільної клітини і, переміщаючись по клітинам циклу, складаємо тарифи клітин. При цьому тарифи в непарних клітинах беруться зі знаком "плюс", в парних - зі знаком "мінус". S 1,1 = c 1,1 -c 1,5 + c 2,5 -c 2,2 + c 3,2 -c 3,1 = 9 S 1,2 = c 1,2 -c 1,5 + c 2,5 -c 2,2 = 1 S 1,3 = c 1,3 -c 1,5 + c 2,5 -c 2,3 = 13 S 2,1 = c 2,1 -c 2 , 2 + c 3,2 -c 3,1 = 13 S 2,4 = c 2,4 -c 2,5 + c 1,5 -c 1,4 = 3 S 3,3 = c 3,3 - c 3,2 + c 2,2 -c 2,3 = 6 S 3,4 = c 3,4 -c 3,2 + c 2,2 -c 2,5 + c 1,5 -c 1,4 = 1 S 3,5 = c 3,5 -c 3,2 + c 2,2 -c 2,5 = 8

B1 B2 B3 B4 B5
A1 9 1 13
A2 13 3
A3 6 1 8

Так як всі оцінки S i, j> = 0, то отриманий план є оптимальним. Транспортна задача вирішена.


Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
17
5
290
3
80
370
A2
21
10
100
7
330
11
6
20
450
A3
3
300
5
180
8
4
9
480
потреба 300 280 330 290 100

Цільова функція F = 6920

2) Метод потенціалів

Приймемо деякі позначення: i - індекс рядка j - індекс стовпця m - кількість постачальників n - кількість споживачів X i, j - перевезення між постачальником A i і споживачем B j.

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
0
8
0
17
0
5
0
3
0
370
A2
21
0
10
0
7
0
11
0
6
0
450
A3
3
0
5
0
8
0
4
0
9
0
480
потреба 300 280 330 290 100

Транспортна задача має закритий тип, так як сумарний запас вантажу дорівнює сумарним потребам. Знаходимо опорний план за правилом північно-західного кута: Введемо деякі позначення: A i * - надлишок нерозподіленого вантажу від постачальника A i B j * - недостача в постачанні вантажу споживачеві B j

Розміщуємо в клітку (1,1) менше з чисел A 1 * = 370 і B 1 * = 300 Так як попит споживача B 1 задоволений, то стовпець 1 надалі в розрахунок не береться поміщаємо в клітку (1,2) менше з чисел A 1 * = 70 і B 2 * = 280 Так як запаси постачальника A 1 вичерпані, то рядок 1 в подальшому в розрахунок не береться Розміщуємо в клітку (2,2) менше з чисел A 2 * = 450 і B 2 * = 210 так як попит споживача B 2 задоволений, то стовпець 2 надалі в розрахунок не береться Розміщуємо в клітку (2,3) менше з чисел A 2 * = 240 і B 3 * = 330 так як запаси постачальника A 2 вичерпані, то рядок 2 в подальшому в рас чет не береться Розміщуємо в клітку (3,3) менше з чисел A 3 * = 480 і B 3 * = 90 Так як попит споживача B 3 задоволений, то стовпець 3 надалі в розрахунок не береться Розміщуємо в клітку (3,4) менше з чисел A 3 * = 390 і B 4 * = 290 Так як попит споживача B 4 задоволений, то стовпець 4 надалі в розрахунок не береться Розміщуємо в клітку (3,5) менше з чисел A 3 * = 100 і B 5 * = 100

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
300
8
70
17
5
3
370
A2
21
10
210
7
240
11
6
450
A3
3
5
8
90
4
290
9
100
480
потреба 300 280 330 290 100

Цільова функція F = 11320

Вирішуємо задачу методом потенціалів:

Етап 1

Вважаючи потенціал U 1 = 0, визначаємо інші потенціали зі співвідношення U i + V j = C i, j (i = 1..m, j = 1..n), переглядаючи всі зайняті клітини. Потенціали U i, V j: U 1 = 0 V 1 = C 1,1 -U 1 = 14 V 2 = C 1,2 -U 1 = 8 U 2 = C 2,2 -V 2 = 2 V 3 = C 2,3 -U 2 = 5 U 3 = C 3,3 -V 3 = 3 V 4 = C 3,4 -U 3 = 1 V 5 = C 3,5 -U 3 = 6 Визначаємо значення оцінок S i , j = C i, j - (U i + V j) для всіх вільних клітин (неоптимальні виділені червоним кольором) S 1,3 = c 1,3 - (u 1 + v 3) = 12. S 1,4 = c 1,4 - (u 1 + v 4) = 4. S 1,5 = c 1,5 - (u 1 + v 5) = -3. S 2,1 = c 2,1 - (u 2 + v 1) = 5. S 2,4 = c 2,4 - (u 2 + v 4) = 8. S 2,5 = c 2,5 - (u 2 + v 5) = -2. S 3,1 = c 3,1 - (u 3 + v 1) = -14. S 3,2 = c 3,2 - (u 3 + v 2) = -6. За наявності кількох клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш потенційної є клітина (3,1). Для неї оцінка дорівнює -14. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
- 14
300
+ 8
70
17
5
3
370
A2
21
- 10
210
+ 7
240
11
6
450
A3
+ 3
5
- 8
90
4
290
9
100
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 90 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус". В результаті переміщення по циклу отримаємо новий план:

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
210
8
160
17
5
3
370
A2
21
10
120
7
330
11
6
450
A3
3
90
5
8
4
290
9
100
480
потреба 300 280 330 290 100

Цільова функція F = 10060

Значення цільової функції змінилося на 1260 одиниць в порівнянні з попереднім етапом.

етап 2

Вважаючи потенціал U 1 = 0, визначаємо інші потенціали зі співвідношення U i + V j = C i, j (i = 1..m, j = 1..n), переглядаючи всі зайняті клітини. Потенціали U i, V j: U 1 = 0 V 1 = C 1,1 -U 1 = 14 V 2 = C 1,2 -U 1 = 8 U 3 = C 1,3 -V 1 = -11 U 2 = C 2,2 -V 2 = 2 V 3 = C 2,3 -U 2 = 5 V 4 = C 3,4 -U 3 = 15 V 5 = C 3,5 -U 3 = 20 Визначаємо значення оцінок S i, j = C i, j - (U i + V j) для всіх вільних клітин (неоптимальні виділені червоним кольором) S 1,3 = c 1,3 - (u 1 + v 3) = 12. S 1,4 = c 1,4 - (u 1 + v 4) = -10. S 1,5 = c 1,5 - (u 1 + v 5) = -17. S 2,1 = c 2,1 - (u 2 + v 1) = 5. S 2,4 = c 2,4 - (u 2 + v 4) = -6. S 2,5 = c 2,5 - (u 2 + v 5) = -16. S 3,2 = c 3,2 - (u 3 + v 2) = 8. S 3,3 = c 3,3 - (u 3 + v 3) = 14. За наявності кількох клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш потенційної є клітина (1,5). Для неї оцінка дорівнює -17. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
- 14
210
8
160
17
5
+ 3
370
A2
21
10
120
7
330
11
6
450
A3
+ 3
90
5
8
4
290
- 9
100
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 100 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус". В результаті переміщення по циклу отримаємо новий план:


Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
110
8
160
17
5
3
100
370
A2
21
10
120
7
330
11
6
450
A3
3
190
5
8
4
290
9
480
потреба 300 280 330 290 100

Цільова функція F = 8360

Значення цільової функції змінилося на 1700 одиниць в порівнянні з попереднім етапом.

етап 3

Вважаючи потенціал U 1 = 0, визначаємо інші потенціали зі співвідношення U i + V j = C i, j (i = 1..m, j = 1..n), переглядаючи всі зайняті клітини. Потенціали U i, V j: U 1 = 0 V 1 = C 1,1 -U 1 = 14 V 2 = C 1,2 -U 1 = 8 V 5 = C 1,5 -U 1 = 3 U 3 = C 1,3 -V 1 = -11 U 2 = C 2,2 -V 2 = 2 V 3 = C 2,3 -U 2 = 5 V 4 = C 3,4 -U 3 = 15 Визначаємо значення оцінок S i, j = C i, j - (U i + V j) для всіх вільних клітин (неоптимальні виділені червоним кольором) S 1,3 = c 1,3 - (u 1 + v 3) = 12. S 1,4 = c 1,4 - (u 1 + v 4) = -10. S 2,1 = c 2,1 - (u 2 + v 1) = 5.S 2,4 = c 2,4 - (u 2 + v 4) = -6. S 2,5 = c 2,5 - (u 2 + v 5) = 1. S 3,2 = c 3,2 - (u 3 + v 2) = 8. S 3,3 = c 3,3 - (u 3 + v 3) = 14. S 3,5 = c 3,5 - (u 3 + v 5) = 17. за наявності кількох клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш потенційної є клітина (1,4). Для неї оцінка дорівнює -10. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
- 14
110
8
160
17
+ 5
3
100
370
A2
21
10
120
7
330
11
6
450
A3
+ 3
190
5
8
- 4
290
9
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 110 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус". В результаті переміщення по циклу отримаємо новий план:

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
160
17
5
110
3
100
370
A2
21
10
120
7
330
11
6
450
A3
3
300
5
8
4
180
9
480
потреба 300 280 330 290 100

Цільова функція F = 7260

Значення цільової функції змінилося на 1100 одиниць в порівнянні з попереднім етапом.

етап 4

Вважаючи потенціал U 1 = 0, визначаємо інші потенціали зі співвідношення U i + V j = C i, j (i = 1..m, j = 1..n), переглядаючи всі зайняті клітини. Потенціали U i, V j: U 1 = 0 V 2 = C 1,2 -U 1 = 8 V 4 = C 1,4 -U 1 = 5 V 5 = C 1,5 -U 1 = 3 U 2 = C 2,2 -V 2 = 2 U 3 = C 4,3 -V 4 = -1 V 3 = C 2,3 -U 2 = 5 V 1 = C 3,1 -U 3 = 4 Визначаємо значення оцінок S i, j = C i, j - (U i + V j) для всіх вільних клітин (неоптимальні виділені червоним кольором) S 1,1 = c 1,1 - (u 1 + v 1) = 10. S 1,3 = c 1,3 - (u 1 + v 3) = 12. S 2,1 = c 2,1 - (u 2 + v 1) = 15. S 2,4 = c 2,4 - (u 2 + v 4) = 4. S 2,5 = c 2,5 - (u 2 + v 5) = 1. S 3,2 = c 3,2 - (u 3 + v 2) = -2. S 3,3 = c 3,3 - (u 3 + v 3) = 4. S 3,5 = c 3,5 - (u 3 + v 5) = 7. Якщо є кілька клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш потенційної є клітина (3,2). Для неї оцінка дорівнює -2. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
- 8
160
17
+ 5
110
3
100
370
A2
21
10
120
7
330
11
6
450
A3
3
300
+ 5
8
- 4
180
9
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 160 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус". В результаті переміщення по циклу отримаємо новий план:

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
17
5
270
3
100
370
A2
21
10
120
7
330
11
6
450
A3
3
300
5
160
8
4
20
9
480
потреба 300 280 330 290 100

Цільова функція F = 6940

Значення цільової функції змінилося на 320 одиниць в порівнянні з попереднім етапом.

етап 5

Вважаючи потенціал U 1 = 0, визначаємо інші потенціали зі співвідношення U i + V j = C i, j (i = 1..m, j = 1..n), переглядаючи всі зайняті клітини. Потенціали U i, V j: U 1 = 0 V 4 = C 1,4 -U 1 = 5 V 5 = C 1,5 -U 1 = 3 U 3 = C 4,3 -V 4 = -1 V 1 = C 3,1 -U 3 = 4 V 2 = C 3,2 -U 3 = 6 U 2 = C 2,2 -V 2 = 4 V 3 = C 2,3 -U 2 = 3 Визначаємо значення оцінок S i, j = C i, j - (U i + V j) для всіх вільних клітин (неоптимальні виділені червоним кольором) S 1,1 = c 1,1 - (u 1 + v 1) = 10. S 1,2 = c 1,2 - (u 1 + v 2) = 2. S 1,3 = c 1,3 - (u 1 + v 3) = 14. S 2,1 = c 2,1 - (u 2 + v 1) = 13. S 2,4 = c 2,4 - (u 2 + v 4) = 2. S 2,5 = c 2,5 - (u 2 + v 5) = -1. S 3,3 = c 3,3 - (u 3 + v 3) = 6. S 3,5 = c 3,5 - (u 3 + v 5) = 7. Якщо є кілька клітин з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш потенційної є клітина (2,5). Для неї оцінка дорівнює -1. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
17
+ 5
270
- 3
100
370
A2
21
- 10
120
7
330
11
+ 6
450
A3
3
300
+ 5
160
8
- 4
20
9
480
потреба 300 280 330 290 100

Переміщаємо по циклу вантаж завбільшки 20 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус".В результаті переміщення по циклу отримаємо новий план:


Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
17
5
290
3
80
370
A2
21
10
100
7
330
11
6
20
450
A3
3
300
5
180
8
4
9
480
потреба 300 280 330 290 100

Цільова функція F = 6920

Значення цільової функції змінилося на 20 одиниць в порівнянні з попереднім етапом.

етап 6

Вважаючи потенціал U 1 = 0, визначаємо інші потенціали зі співвідношення U i + V j = C i, j (i = 1..m, j = 1..n), переглядаючи всі зайняті клітини.

Потенціали U i, V j: U 1 = 0 V 4 = C 1,4 -U 1 = 5 V 5 = C 1,5 -U 1 = 3 U 2 = C 5,2 -V 5 = 3 V 2 = C 2,2 -U 2 = 7 V 3 = C 2,3 -U 2 = 4 U 3 = C 2,3 -V 2 = -2 V 1 = C 3,1 -U 3 = 5 Визначаємо значення оцінок S i, j = C i, j - (U i + V j) для всіх вільних клітин (неоптимальні виділені червоним кольором) S 1,1 = c 1,1 - (u 1 + v 1) = 9. S 1,2 = c 1,2 - (u 1 + v 2) = 1. S 1,3 = c 1,3 - (u 1 + v 3) = 13. S 2,1 = c 2,1 - (u 2 + v 1) = 13. S 2,4 = c 2,4 - (u 2 + v 4) = 3. S 3,3 = c 3,3 - (u 3 + v 3) = 6. S 3,4 = c 3,4 - (u 3 + v 4) = 1. S 3,5 = c 3,5 - (u 3 + v 5) = 8. Так як всі оцінки S i, j> = 0, то отриманий план є оптимальним. Транспортна задача вирішена.

Постачальник споживач запаси вантажу
B1 B2 B3 B4 B5
A1
14
8
17
5
290
3
80
370
A2
21
10
100
7
330
11
6
20
450
A3
3
300
5
180
8
4
9
480