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

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

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

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

Таблиця14

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–	1001	–		100-100=0
A2
A3
Заявки bj
bj'			110-100=10

2. Найменшим значенням у другої строчці ТТ володіє клітка ( ); одержуємо нові значення = 120 – 10 = 110 і = 10 – 10 =0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-й стовпець (див. табл. 15).

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

4. Починаємо процес спочатку – з першої строки. Але запаси вантажу у першого постачальника А1 вичерпали, тому перейдемо до другої строки ТТ. Наступним найменшим значенням у другої строчці таблиці володіє клітка ( ) ;одержуємо нові значення = 110 – 80 = 30 і = 80 – 80 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 1-й рядок (табл. 17).

Таблиця15

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–	1001	–
A2			102			120-10=110
A3			–
Заявки bj
bj'			10-10=0

Таблиця16

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–	1001	–
A2			102	–
A3			–	703		140-70=70
Заявки bj
bj'				70-70=0

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

6. Починаємо процес спочатку – з першої строки. Але запаси вантажу у першого постачальника А1 вичерпали, тому перейдемо до другої строки ТТ. Останнім незаповненим значенням у таблиці володіє клітка ( ); одержуємо нові значення = 30 – 30 = 0 і = 30 – 30 = 0 (див. табл. 19).

Таблиця17

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–	1001	–
A2	804		102	–		110-80=30
A3	–		–	703
Заявки bj
bj'	80-80=0

Таблиця18

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–	1001	–
A2	804		102	–
A3	–	705	–	703		170-70=0
Заявки bj
bj'		100-70=30

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

у.г.о.

Таблиця19

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–	1001	–
A2	804	306	102	–		30-30=0
A3	–	705	–	703
Заявки bj
bj'		30-30=0

3.6. Метод найменшого елемента стовпця ТТ

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

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

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

Таблиця20

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–
A2	801					120-80=40
A3	–
Заявки bj
bj'	80-80=0

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

Таблиця21

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–
A2	801	–
A3	–	1002				140-100=40
Заявки bj
bj'		100-100=0

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

Таблиця22

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–
A2	801	–	403	–		40-40=0
A3	–	1002
Заявки bj
bj'			110-40=70

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

Таблиця23

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–
A2	801	–	403	–
A3	–	1002	–	404		40-40=0
Заявки bj
bj'				70-40=30

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

Таблиця24

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–	705			100-70=30
A2	801	–	403	–
A3	–	1002	–	404
Заявки bj
bj'			70-70=0

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

Таблиця25

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

	B1	B2	B3	B4	Запаси ai	ai'
A1	–	–	705	306		30-30=0
A2	801	–	403	–
A3	–	1002	–	404
Заявки bj
bj'				30-30=0

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

у.г.о.

3.7. Метод найменшого елемента ТТ

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

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

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

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

Таблиця26

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

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

Таблиця27

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

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

3. Наступним найменшим значенням у таблиці володіє клітка ( ) і клітка ( ) – беремо першу з них, тобто ; одержуємо нові значення = 10 – 10 = 0 і = 80 – 10 = 70 (див. табл. 28).