Методичні вказівки до виконання курсового проекту 3 страница

4. Наступним найменшим значенням у таблиці володіє клітка ( ) ;одержуємо нові значення = 70 – 70 = 0 і = 100 – 70 = 30. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-й рядок (табл. 29).

Таблиця28

ТТ з розподілом вантажу у клітинку А₂В₁

	B1	B2	B3	B4	Запаси ai	ai'
A1			–	–
A2	103	–	1101	–		10-10=0
A3			–	702
Заявки bj
bj'	80-10=70

Таблиця29

ТТ з розподілом вантажу у клітинку А₃В₂

	B1	B2	B3	B4	Запаси ai	ai'
A1			–	–
A2	103	–	1101	–
A3	–	704	–	702		70-70=0
Заявки bj
bj'		100-70=30

5. Наступним найменшим значенням у таблиці володіє клітинка ( ) ;одержуємо нові значення = 100 – 70 = 30 і = 70 – 70 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 1-й стовпець (див. табл. 30).

6. Останнім найменшим значенням у таблиці володіє клітинка ( ) ;одержуємо нові значення = 30 – 30 = 0 і = 30 – 30 = 0 (див. табл. 31).

Таблиця30

ТТ з розподілом вантажу у клітинку А₁В₁

	B1	B2	B3	B4	Запаси ai	ai'
A1	705		–	–		100-70=30
A2	103	–	1101	–
A3	–	704	–	702
Заявки bj
bj'	70-70=0

Таблиця31

ТТ з розподілом вантажу у клітинку А₁В₂

	B1	B2	B3	B4	Запаси ai	ai'
A1	705	306	–	–		30-30=30
A2	103	–	1101	–
A3	–	704	–	702
Заявки bj
bj'		30-30=0

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

у.г.о.

3.8. Метод мінімального вузла відправлення вантажу ТТ

Метод мінімального вузла відправлення вантажу побудови опорного плану перевезень, який поєднує кращі якості перерахованих вище методів також розглянемо на конкретному прикладі (див. табл. 1).

Спочатку знайдемо суми вартостей перевезення одиниці вантажу окремо по рядках (С_і , i = 1,m) ТТ і відсортуємо отримані величини у порядку їх зростання (табл. 32). Порядкові номери зростання сум проставлені у вигляді нижніх індексів відповідних величин.

Таблиця32

Вихідна ТТ

	B1	B2	B3	B4	Запаси ai	Ci
A1	x11	x12	x13	x14		181
A2	x21	x22	x23	x24		182
A3	x31	x32	x33	x34		203
Заявки bj

Заносити обсяги перевезень починаємо з вузла, який має найменшу суму вартостей одиниці перевезень вантажу по окремому рядку – вузлу відправлення вантажу (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися у відповідності з порядковими номерами зростання сум вартостей перевезень одиниці вантажу вузлів відправлення, що залишилися і т.д., до одержання (m + n - 1) перевезень. Принцип заповнення клітинок ТТ у самому рядку буде наступним: максимально задовольнити весь обсяг замовлення вантажу в першу чергу за рахунок найменших вартостей перевезень одиниці вантажу.

У нашому прикладі процес побудови опорного плану методом мінімального вузла відправлення вантажу відображений у табл. 33, причому нижній індекс у обсягах перевезень вказує на черговість розподілу вантажу.

Таблиця33

Опорний план за методом мінімального вузла

відправлення вантажу ТТ

	B1	B2	B3	B4	Запаси ai	Ci
A1	–	–	1001	–		181
A2	804	306	102	–		182
A3	–	705	– –	703		203
Заявки bj

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

у.г.о.

3.9. Метод мінімального вузла призначення вантажу ТТ

Метод мінімального вузла призначення вантажу побудови опорного плану перевезень також розглянемо на конкретному прикладі (див. табл. 1).

Спочатку знайдемо суми вартостей перевезення одиниці вантажу окремо по стовпцях (С_j , j = 1,n) ТТ і відсортуємо отримані величини у порядку їх зростання (табл. 34). Порядкові номери зростання сум проставлені у вигляді нижніх індексів відповідних величин.

Заносити обсяги перевезень починаємо з вузла призначення, який має найменшу суму вартостей одиниці перевезень вантажу по окремому стовпцю (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися у відповідності з порядковими номерами зростання сум вартостей перевезень одиниці вантажу вузлів призначення, що залишилися і т.д., до одержання (m + n - 1) перевезень. Принцип заповнення клітинок ТТ у самому стовпці буде наступним:

Таблиця34

Вихідна ТТ

	B1	B2	B3	B4	Запаси ai
A1	x11	x12	x13	x14
A2	x21	x22	x23	x24
A3	x31	x32	x33	x34
Заявки bj
Cj	163	164	91	152

максимально задовольнити весь обсяг замовлення вантажу в першу чергу за рахунок найменших вартостей перевезень одиниці вантажу.

У нашому прикладі процес побудови опорного плану методом мінімального вузла призначення вантажу відображений у табл. 35, причому нижній індекс у обсягах перевезень вказує на черговість розподілу вантажу.

Таблиця35

Опорний план за методом мінімального вузла

призначення вантажу ТТ

	B1	B2	B3	B4	Запаси ai
A1	705	306	–	–
A2	103	–	1101	–
A3	–	704	–	702
Заявки bj
Cj	163	164	91	152

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

у.г.о.

3.10. Метод мінімального вузла відправлення-призначення вантажу ТТ

Метод мінімального вузла відправлення-призначення вантажу побудови опорного плану перевезень, який поєднує кращі якості перерахованих вище методів також розглянемо на конкретному прикладі (див. табл. 1).

Спочатку знайдемо суми вартостей перевезення одиниці вантажу окремо по рядках (С_і , i = 1,m) і стовпцям ТТ (С_j , j = 1,n) і відсортуємо отримані величини у порядку їх зростання (табл. 36). Порядкові номери зростання сум проставлені у вигляді нижніх індексів відповідних величин.

Таблиця36

Вихідна ТТ

	B1	B2	B3	B4	Запаси ai	Ci
A1	x11	x12	x13	x14		185
A2	x21	x22	x23	x24		186
A3	x31	x32	x33	x34		207
Заявки bj
Cj	163	164	91	152

Заносити обсяги перевезень починаємо з вузла, який має найменшу суму вартостей одиниці перевезень вантажу або по окремому рядку, або по окремому стовпцю (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися у відповідності з порядковими номерами зростання сум вартостей перевезень одиниці вантажу вузлів, що залишилися до одержання (m + n - 1) перевезень.

Принцип заповнення клітинок у самому рядку (стовпці) буде наступним: задовольнити весь обсяг постачання (замовлення) вантажу за рахунок найменших вартостей перевезень одиниці вантажу.

У нашому прикладі процес побудови опорного плану методом мінімального вузла відправлення-призначення вантажу відображений у табл. 37, причому нижній індекс у обсягах перевезень вказує на черговість розподілу вантажу.

Таблиця37

Опорний план за методом мінімального вузла

відправлення-призначення вантажу ТТ

	B1	B2	B3	B4	Запаси ai	Ci
A1	705	306	–	–		185
A2	103	–	1101	–		186
A3	–	704	–	702		207
Заявки bj
Cj	163	164	91	152

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

у.г.о.

3.11. Метод випадкового заповнення (рандомизації)

Побудова опорного плану перевезень методом випадкового заповнення (рандомизації) також розглянемо на конкретному прикладі (див. табл. 1).

Заносити обсяги перевезень починаємо з клітинки, у якої номер строки і стовпця генерується випадковим способом (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися аналогічно до одержання (m + n - 1) перевезень, причому вже заповнені клітинки ТТ будуть пропускатися, а номера строк і стовпців будуть генеруватися у діапазоні ,відповідно, від 1 до m і від 1 до n. У нашому прикладі опорний план побудований методом випадкового заповнення за допомогою відповідної програми відображений на рис. 1.

Рис. 1. Варіант опорного плану перевезень вантажу

Сам процес побудови опорного плану представлений у таблиці 38 (причому нижній індекс у обсягах перевезень вказує на черговість розподілу вантажу) і представляє наступне:

1-а генерація номерів строки і стовпця: i = 3; j = 3; х₃₃ = 110;

2-а генерація номерів строки і стовпця: i = 3; j = 4; х₃₄ = 30;

3-а генерація номерів строки і стовпця: i = 1; j = 3;

(вантаж у клітинку А₁В₃ не розподіляється, оскільки заявка b₃ вже задоволена)

4-а генерація номерів строки і стовпця: i = 1; j = 1; х₁₁ = 80;

5-а генерація номерів строки і стовпця: i = 2; j = 2; х₂₂ = 80;

6-а генерація номерів строки і стовпця: i = 3; j = 4;

(вантаж у клітинку А₃В₄ не розподіляється, оскільки вона вже заповнена)

7-а генерація номерів строки і стовпця: i = 1; j = 2; х₁₂ = 20;

8-а генерація номерів строки і стовпця: i = 2; j = 1;

(вантаж у клітинку А₂В₁ не розподіляється, оскільки заявка b₁ вже задоволена)

9-а генерація номерів строки і стовпця: i = 2; j = 4; х₂₄ = 20;

План перевезень побудований, оскільки вичерпані запаси у всіх постачальників вантажу і заявки всіх споживачів вантажу задоволені.

Таблиця38

Опорний план за методом випадкового

заповнення клітинок ТТ

	B1	B2	B3	B4	Запаси ai	ai'	ai'’
A1	803	205	–	–		100-80=20	20-20=0
A2	–	804	–	406		120-80=40	40-40=0
A3	–	–	1101	302		140-110=30	30-30=0
Заявки bj
bj'	80-80=0	100-80=20	110-110=0	70-30=40
bj'’		20-20=0		40-40=0

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

у.г.о.

3.12. Метод апроксимації Фогеля

Побудова опорного плану перевезень методом апроксимації Фогеля також розглянемо на тому же самому прикладі (див. табл. 1).

У кожному рядку і кожному стовпці матриці вартостей (табл. 39) шукаємо мінімальний і наступний за ним елементи (підкреслюємо відповідні значення). Різниця між ними записуємо праворуч і внизу таблиці і вибираємо з них максимальну величину. У нашому прикладі це значення 3, що зустрічається двічі – у другому і четвертому стовпцях (також підкреслюємо ці значення).

У такому випадку, перевіряють, чи є мінімальний елемент у стовпці також мінімальним і в рядку. Якщо такий елемент єдиний, то в нього й поміщають відповідну кореспонденцію. Якщо ж мінімальних елементів і в стовпці і у рядку декілька, то необхідно знайти в рядках другу різницю і вибрати той елемент, у якого друга різниця більше. У нашім випадку мінімальне значення 2 у четвертому стовпці одночасно є і мінімальним значенням у третьому рядку, а тому що воно єдине, те саме в цю клітинку А₃В₄ і поміщаємо максимально можливу кореспонденцію 70, при цьому виключаємо з подальшого розгляду четвертий стовпець, поставивши в його вільних клітинках знак “ –“, а нижче різниці - букву К (кінець). Різниці в інших стовпцях не змінилися, удруге їх не переписуємо. Різниці ж у рядках можуть змінитися, тому обчислюємо їх знову і записуємо у табл. 40.

Таблиця39

Перша ітерація ТТ

	B1	B2	B3	B4	Запаси ai		ai'
A1	4		2	5 –		4-2=2
A2	3	6	1	–		3-1=2
A3		3		2		3-2=1	140-70=70
Заявки bj
	4-3=1	6-3=3	2-1=1	5-2=3 К
bj'				70-70=0

Знову максимальне значення різниці 3 зустрічається у нашому прикладі двічі - у другому стовпці і у третьому рядку (також підкреслюємо ці значення). Але тому що мінімальні значення елементів, що залишилися, і в цьому стовпці, і в цьому рядку збігаються і являють собою значення 3 клітинки А₃В₂, те саме в цю клітинку А₃В₂ і поміщаємо максимально можливу кореспонденцію 70, при цьому виключаємо з подальшого розгляду третій рядок, поставивши в його вільних клітинках знак “–“, а нижче різниці - букву К (кінець), тому що повністю вичерпаний весь запас вантажу у третього постачальника.

Таблиця40

Друга ітерація ТТ

	B1	B2	B3	B4	Запаси ai		ai'
A1	4		2	–		4-2=2
A2	3	6	1	–		3-1=2
A3	–	3	6 –			6-3=3 К	70-70=0
Заявки bj
	4-3=1	6-3=3	2-1=1	К
bj'		100-70=30

В таблиці 41 максимальне значення різниці 2 знаходиться у першої і другій строчці, але тільки у другій строчці значення її мінімального елементу 1 у клітинці А₂В₃ є мінімальним і у третьому стовпці. Тому поміщаємо у цю клітинку (А₂В₃) максимально можливий обсяг вантажу – 110, при цьому виключаємо з подальшого розгляду третій стовпець, поставивши в його вільних клітинках знак “–“, а нижче різниці - букву К (кінець), тому що повністю задоволена заявка у третього споживача.

Таблиця41

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

	B1	B2	B3	B4	Запаси ai		ai'
A1	4	7	2 –	–		4-2=2
A2	3	6	1	–		3-1=2	120-110=10
A3	–		–			К
Заявки bj
	4-3=1	7-6=1	2-1=1 К	К
bj'			110-110=0

В таблиці 42 максимальне значення різниці 3 також знаходиться у першої і другій строчці, але тільки у другій строчці значення її мінімального елементу 3 у клітинці А₂В₁ є мінімальним і у першому стовпці. Тому поміщаємо у цю клітинку (А₂В₁) максимально можливий обсяг вантажу – 10, при цьому виключаємо з подальшого розгляду другу строку, поставивши в його вільних клітках знак “–“, а нижче різниці - букву К (кінець), тому що повністю вичерпаний весь запас вантажу у другого постачальника.