Знаходження значень потенціалів

Базисні змінні	Рівняння щодо потенціалів	Рішення
x11	U1 + V1 = 10	U1=0 V1=10
x12	U1 + V2 = 20	U1=0 V2=20
x22	U2 + V2 = 170	V2=20 U2 =150
x23	U2 + V3 = 190	U2=150 V3=40
x24	U2 + V4 = 200	U2=150 V4=50
x34	U3 + V4 = 180	V4=50 U3=130

У підсумку маємо: U₁=0, U₂=150, U₃=130, V₁=10, V₂=20, V₃=40, V₄=50.

2.3. Використовуючи обчислені значення потенціалів, для кожної небазисної змінної (порожньої клітки транспортної таблиці) обчислюємо величини U_i + V_j - C_ij (табл. 5.5).

Таблиця 5.5

Обчислення значень U_i + V_j - C_ij

Небазисні змінні	Значення Ui + Vj - Cij
x13	U1 + V3 – C13 = 0 + 40 – 120 = -80
x14	U1 + V4 – C14 = 0 + 50 – 110 = -60
x21	U2 + V1 – C21 = 150 + 10 – 180 = -20
x31	U3 + V1 – C31 = 130 + 10 –130 = 10
x32	U3 + V2 – C32 = 130 + 20 – 160 = -10
x33	U3 + V3 – C33 = 130 + 40 – 190 = -20

 

2.4. Через те, що для небазисної змінної x₃₁ значення U_i + V_j - C_ij не є від’ємним, знайдене рішення не можна вважати оптимальним. Так як в транспортній задачі ведеться пошук мінімуму вартості перевезень, то в базис вводиться змінна з найбільшим позитивним значенням U_i + V_j - C_ij (x₃₁).

2.5. Визначивши змінну, що вводиться в базис, далі треба визначити змінну, що виключається з базису, так як в даному прикладі кількість базисних змінних повинна дорівнювати 3 + 4 – 1 = 6.

Змінна, що виключається з базису, визначається наступним чином. Вибираючи в якості змінної, що вводиться в базис, змінну x₃₁, ми хочемо, щоб перевезення за маршрутом, що відповідають цій змінній, зменшили загальну вартість перевезень. Позначимо через θ кількість вантажу, що перевозиться за маршрутом Одеса-Запоріжжя (тобто, x₃₁ = θ). Максимально можливе значення θ визначаємо за наступними умовами:

1. Повинні виконуватися обмеження на попит і пропозицію.

2. Ні за яким маршрутом не повинні виконуватись перевезення з від’ємним об’ємом вантажу.

Для знаходження θ побудуємо замкнений цикл, який об’єднує клітини, що відповідають поточним базисним змінним, і клітину, яка відповідає змінній, що вводиться в базис (табл. 5.6). Для будь-якої змінної, що вводиться, можна побудувати тільки один замкнений цикл.

2.6. За даними табл. 5.6 знайдемо значення θ. Для задоволення обмежень за попитом і пропозицією треба почергово віднімати і прибавляти θ до значень базисних змінних, що розташовані в кутових клітинах циклу (направлення обходу циклу не має значення: за або проти часової стрілки). Нові значення базисних змінних залишаться невід’ємними, якщо будуть виконуватись наступні нерівності:

x₁₁ = 50 – θ ≥ 0,

x₂₂ = 50 – θ ≥ 0,

x₃₄ = 100 – θ ≥ 0.

Таблиця 5.6

Перший цикл перерахунку

Підприємства-постачаль-ники	Підприємства-споживачі	Про-пози-ція, т
Запоріжжя	Дніпропет-ровськ	Київ	Сімферо-поль
Кривий Ріг										U1=0
50-θ		100+θ			-80
Харків										U2=150
	-20	50-θ				50+θ
Одеса										U3=130
θ			-10		-20	100-θ
Попит, т
	V1=10	V2=20	V3=40	V4=50

 

Звідси випливає, що найбільше значення, яке може прийняти θ, дорівнює 50, при цьому змінні x₁₁ і x₂₂ обертаються на 0. Так як тільки одна змінна виключається з базису, в якості змінної, що виключається, можна обрати як x₁₁, так і x₂₂. Зупинимо свій вибір на x₁₁.

2.7. Визначивши значення для змінної, що вводиться (x₃₁ = 50), і обравши змінну, що виключається (x₁₁), далі необхідно скоректувати значення базисних змінних, що відповідають кутовим клітинам замкненого циклу (табл. 5.7).

Таблиця 5.7