Розробка програми розв'язку транспортної задачі

                    1

                         15

                    2

                      25

                    3

                        10

 

Рисунок 12. – Розв’язок методом ПЗ кута

 Визначення  змінної, яку будемо вводити  в базис, засновано на обчисленнях  коефіцієнтів Z-рядку, які відповідають небазисним змінним з використанням методу потенціалів.

В методі потенціалів  кожному і-му рядку і кожному j-му стовпцю транспортної таблиці ставляться у відповідність числа (потенціали) u_i та v_j. Для кожної базисної змінної X_ij потенціали u_i та v_j задовольняють рівняння:

U_i+V_j=C_ij.

В нашій задачі маємо 7 невідомих змінних (потенціалів) і 6 рівнянь, які відповідають шістьом базисним змінним. Щоб знайти значення потенціалів із системи рівнянь, необхідно присвоїти одному з них довільне значення (u₁=0) і потім послідовно обчислити значення інших потенціалів.

Базисні змінні	Рівняння відносно потенціалів	Розв’язок
X11	u1+v1=10	u1=0→ v1=10
X12	u1+v2=2	u1=0→ v1=2
X22	u2+v2=7	v2=2→ u2=5
X23	u2+v3=9	u2=5→ v3=4
X24	u2+v4=20	u2=5→ v4=15
X34	u3+v4=18	v4=15→ u3=3

Рисунок 13. – Базисні змінні

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

Небазисні зміні	Значення Ui+Vj-Cij
X13	U1+V3-C13=0+4-20=-16
X14	U1+V4-C14=0+15-11=4
X21	U2+V1-C21=5+10-12=3
X31	U3+V1-C31=3+10-4=9
X32	U3+V2-C32=3+2-14=-9
X33	U3+V3-C33=3+4-16=-9

Рисунок 14. – Небазисні змінні

Обчислені значення та нульові значення для базисних змінних (оскільки U_i+V_j-C_ij=0 для будь-якої базисної змінної X_ij) є коефіцієнтами Z-рядка симплекс-таблиці.

Базис	X11	X12	X13	X14	X21	X22	X23	X24	X31	X32	X33	X34
z	0	0	-16	4	3	0	0	0	9	-9	-9	0

Рисунок 15. – Відповідні базиси

Оскільки в  транспортній задачі шукаємо мінімум  вартості перевезень, то в базис  вводимо зміну, яка має найбільший додатій коефіцієнт в Z-рядку. В нашому випадку це змінна X₃₁.

Дані обчислень  виконуються безпосередньо в  транспортній таблиці, величини U_i+V_j-C_ij для небазисних змінних позначено позначено а правих нижніх кутах відповідних комірок:

	V1=10	V2=2	V3=4	V4=15	Пропозиція
U1=0	10 5	2 10	20 -16	11 4	15
U2=5	12 3	7 5	9 15	20 5	25
U3=3	4 9	14 -9	16 -9	18 10	10
Попит	5	15	15	15

Рисунок 16. – Визначення U_i+V_j-C_ij

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

Далі необхідно знайти зміну, яка виключається з базису. Для цього позначимо через θ кількість вантажу, який необхідно перевезти по маршруту (3, 1), тобто X₁₃= θ. Для максимального значення θ ставляться такі умови(рис 17):

• Повинні виконуватися обмеження на попит і пропозицію.
• Ні за яким маршрутом не повинні виконуватися перевезення з від'ємним обсягом вантажу.

	V1=10	V2=2	V3=4	V4=15	Пропозиція
U1=0	10 5- θ	2 10+ θ	20 -16	11 4	15
U2=5	12 3	7 5- θ	9 15	20 5+ θ	25
U3=3	4 θ              9	14 -9	16 -9	18 10- θ	10
Попит	5	15	15	15

Рисунок 17. – Умови для базисів

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

X₁₁=5-Θ≥0

X₂₂=5-Θ≥0

X₃₄=10-Θ≥0

З цих нерівностей  випливає, що найбільше значення, яке  може прийняти Θ, дорівнює 5, при цьому  змінні X₁₁, та X₂₂ обертаються в нуль. Оскільки лише одна змінна виключається з базису, то виключити можна або X₂₂ або X₁₁, обираємо X₁₁.

Значення змінної, що вводиться X₃₁=5. Далі необхідно змінити значення кутових комірок циклу. Оскільки перевезення одиниці вантажу по маршруту (3,1) зменшує загальну вартість перевезень на 9 одиниць (U₃+V₁-C₃₁), тут сумарна вартість перевезень буде на 9*5=45 одиниць менше, ніж у попередньому розв'язку. Таким чином, нова вартість перевезень дорівнює 520-45=475 одиниць.

Після отримання нового базисного розв'язку, необхідно повторити обчислення потенціалів(Рис 18):

Базисні змінні	Рівняння відносно потенціалів	Розв’язок
X12	u1+v2=2	u1=0→ v1=2
X22	u2+v2=7	v2=2→ u2=5
X23	u2+v3=9	u2=5→ v3=4
X24	u2+v4=20	u2=5→ v4=15
X31	u3+v1=4	u3=3→ v1=1
X34	u3+v4=18	v4=15→ u3=3

Рисунок 18. – Обчислення потенціалів

Далі, використовуючи значення потенціалів, для кожної небазисної змінної обчислюється величина U_i+V_j-C_ij безпосередньо в таблиці. Оскільки знайдений розв’язок не оптимальний (U_i+V_j-C_ij=4), то будуємо знову цикл для знаходження змінної, що виводиться з базису.

Змінна, яку  треба включити в базис X₁₄. Замкнутий цикл дозволяє знайти значення цієї змінної X₁₄=10, і змінну, яку треба виключити X₂₄.

	V1=1	V2=2	V3=4	V4=15	Пропозиція
U1=0	10 -9	2 15- Θ	20 -16	11 Θ              4	15
U2=5	12 -6	7 0 + θ	9 15	20 10- θ	25
U3=3	4 5	14 -9	16 -9	18 5	10
Попит	5	15	15	15

Рисунок 19. – Виведення старої, введення нової базисної змінної

Отримаємо новий  розв'язок:

	V1=-3	V2=2	V3=4	V4=11	Пропозиція
U1=0	10 -13	2 5	20 -16	11 10	15
U2=5	12 -10	7 10	9 15	20 -4	25
U3=7	4 5	14 -5	16 -5	18 5	10
Попит	5	15	15	15

Рисунок 20. – Новий розв'язок ТЗ

Новий розв'язок на 4*10=40 зменшує значення цільової функції. Тому сумарна вартість перевезень 475-40=435 одиниць. Зараз нові значення величин U_i+V_j-C_ij для всіх небазисних змінних X_ij від’ємні, тому розв’язок оптимальний.

Отриманий розв’язок  стосовно задачі про перевезення  зерна має такий зміст(Рис 21):

Мінімальна  вартість перевезень дорівнює 435 одиниць.

Від елеватора	До млина	Кількість машин
1	2	5
1	4	10
2	2	10
2	3	15
3	1	5
3	4	5

Рисунок 21. – План розподілення товару

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