Транспортна задача
1. Огляд теми
1. Математична постановка транспортної задачі.
2. Методи побудови опорного плану ТЗ.
3. Знаходження оптимального плану ТЗ методом потенціалів
2. Типові завдання.
В пунктах відправлення А1, А2, А3, …. знаходиться однорідний вантаж в кількості a1, а2, а3, …. відповідно, який необхідно перевезти в пункти призначення В1, В2, В3, …. , потреба кожного з яких становить b1, b2, b3, …. . Відома відстань між пунктами перевезень (оцінки).
Маємо три постачальника з такими запасами вантажу:
А1
і чотири споживача з потребою на цей вантаж:
В1 = 14 т, В2 = 19 т, В3 = 20 т, В4 = 5 т.
Відома відстань між пунктами перевезень.
Відстань між пунктами перевезень, км (Сij).
|
Постачальники |
Споживачі |
|||
|
B1 |
B2 |
B3 |
B4 |
|
|
A1 |
6 |
4 |
15 |
19 |
|
A2 |
13 |
17 |
28 |
3 |
|
A3 |
5 |
20 |
6 |
10 |
Необхідно знайти кількість вантажу, який повинен отримати кожен споживач від того або іншого постачальника, щоб загальна кількість тонно-кілометрів була мінімальною.
Рішення.
Рішення транспортної задачі лінійного програмування здійснюється в таблицях. Перша таблиця (опорний план) може бути заповнена декількома методами:
метод північно-західного кута; метод найменшої вартості; метод подвійної переваги.
Задача, в якій загальні запаси дорівнюють загальним потребам називається закритою транспортною задачею:
– загальні запаси = 26+33+45 = 104 т;
– загальні потреби = 14+19+20+5 = 58 т.
Отже задача відкрита, тому необхідно ввести фіктивного споживача, якому слід перевезти Вфікт = 104–58 = 46 т.
Клітини з фіктивним споживачем (постачальником) заповнюються в останню чергу, порушення умови оптимальності в цих клітинах розглядається лише після того, як в основних клітинах порушення умови оптимальності не спостерігається.
Першу транспортну таблицю заповнимо методом північно-західного кута: першою заповнюється верхня ліва клітина Х11, в яку заноситься або всі запаси А1, або вся потреба В1 в залежності від того, що менше. На кожному наступному кроці розглядається перший з тих, що залишилися, пункт призначення або пункт відправлення:
– якщо це пункт призначення, то потреба його визначається за правилом: Хij = ai – вивезений вантаж з Ai;
– якщо це пункт відправлення, то запаси його визначається за правилом: Хij = bj – завезений вантаж в Bj.
Так заповнюються всі клітини таблиці з Х11 по ХMh (це заповнення має вигляд східців по діагоналі таблиці).
В клітину Х11 записуємо 14 і відповідно покривається вся потреба першого споживача за рахунок першого постачальника, в якого залишається вантаж в кількості: 26–14=12тон, який можна відвезти в другий пункт призначення. Тимчасово не розглядається стовпець В1. Потреба другого пункту споживання В2 становить 19тон, а за рахунок першого постачальника А1 можна завезти лише 12тон, 7тон завозиться з другого пункту відправлення. Тимчасово не розглядається рядок А1. В постачальника А2 було 33тони, з яких 7тон перевозиться в пункт споживання В2, 20тон в пункт споживання В3 та 1тонна в фіктивний пункт споживання ВФікт. Потреба фіктивного пункту споживання покривається за рахунок другого та третього постачальника.
При такому плані перевезень загальна кількість тонно-кілометрів буде становити:
Fmin=14*6+12*4+7*17+20*28+5*3+1*0+45*0=826 т-км.
За допомогою методу потенціалів можна визначити оптимальний план транспортної задачі. Задача має оптимальне значення, коли сума потенціалів в усіх клітинах таблиці не перевищує оцінок, тобто при рішенні задачі на мінімум план вважається оптимальним в тому випадку, якщо для всіх вільних клітинок дотримується вимога: Ui +Vj £Cij, а для зайнятих Ui +Vj =Cij.
Для перевірки плану на оптимальність використовують систему оцінок (потенціалів) рядків і стовпчиків, що розраховуються за правилом: для будь-якої заповненої клітинки сума потенціалів відповідного рядка і стовпчика повинна дорівнюватися оцінці (вартість перевезення одиниці вантажу або відстань) цієї клітини.
Ui +Vj =Cij
Де: Cij – оцінка клітинки;
I – рядки (I = 1, 2, … , M),
J – стовпчики ( J=1, 2, … , H)
Ui – оцінка I–го рядка (I = 1, 2, … M)
Vj – оцінка J–го стовпця (J = 1, 2, … H)
Тобто, якщо відомий потенціал Ui, То Vj=Cij–Ui, а якщо відомий Vj, то Ui=Cij – Vj . При цьому один з рядків або один з стовпчиків отримує довільну оцінку, а оцінки останніх рядків і стовпчиків треба розрахувати за вказаними формулами.
Нехай U1 =0, тоді потенціали першого та другого стовпчиків будуть становити:
V1=C11 –U1 = 6-0 = 6 для В1
V2=C12 –U1 = 4-0 = 4 для В2
Тепер можна визначити потенціал другого рядка:
U2 = C22 – V2 = 17 – 4 = 13
Визначимо потенціали для В3 , В4 І Вфікт:
V3=C23 –U2 = 28 – 13 = 15 для В3
V2=C24 –U2 = 3 – 13 = -10 для В4
V2=C25 –U2 = 0 – 13 = -13 для Вфікт
Тепер можна визначити потенціал А3:
U3 = C35 – V5 = 0 – (-13) = 13
В усіх зайнятих клітинах умова оптимальності виконується, а для вільних клітин виконуються розрахунки по перевірці плану на оптимальність:
Для Х13 сума потенціалів U1 + V3 = 0 + 15 = 15, що £ 15
Для Х14 сума потенціалів U1 + V4 = 0 + (-10) = -10, що £ 19
Для Х15 сума потенціалів U1 + V5 = 0 + (-13) = -13, що£ 0
Для Х21 сума потенціалів U2 + V1 = 13 + 6 = 19, що > 13
Для Х31 сума потенціалів U3 + V1 = 13 + 6 = 19, що > 5
Для Х32 сума потенціалів U3 + V2 = 13 + 4 = 17, що £ 20
Для Х33 сума потенціалів U3 + V3 = 13 + 15 = 28, що > 6
Для Х34 сума потенціалів U3 + V4 = 13 + (-10) = 3, що £ 10
Отже, даний план перевезень не є оптимальним, тому що в клітинках Х21, Х31, Х33 не виконується вимога Ui + Vj £ Cij. Необхідно перейти до наступного плану.
Для цього вибирається клітина, в якій сума потенціалів найбільш перевищує оцінку, це клітина Х33 і вона називається клітиною перерахунку.
Починаючи з клітини перерахунку будується по зайнятим клітинам фігура перерахунку (замкнутий контур, вершини якого знаходяться в зайнятих клітинах), яка може мати вигляд (деякі варіанти фігури):
Клітини, які ввійшли до фігури перерахунку позначаються по черзі знаками “+”, “-”,”+”, “-”, … , починаючи з клітини перерахунку.
Заповнюється нова транспортна таблиця:
– кількість вантажу в клітинах, які не ввійшли до фігури перерахунку переноситься в нову таблицю без змін;
– для клітин фігури перерахунку: кількість вантажу в клітинках зі знаком “+” збільшується, а в клітинках зі знаком “-“ зменшується на одну і ту ж величину, а саме, на найменшу кількість вантажу у клітинках, позначених знаком “-“.
Виправлений таким чином план перевезень записується у відповідну таблицю і досліджується на оптимальність, як і попередній.
При такому плані перевезень загальна кількість тонно-кілометрів буде становити:
FMin=14*6+12*4+7*17+5*3+21*0+20*6+25*0=386 т-км.
Обчислимо потенціали за правилом, описаним вище, і перевіримо складений план на оптимальність.
Для вільних клітин зробимо розрахунки:
Для Х13 сума потенціалів U1 + V3 = 0 + (-7) = -7, що £ 15
Для Х14 сума потенціалів U1 + V4 = 0 + (-10) = -10, що £ 19
Для Х15 сума потенціалів U1 + V5 = 0 + (-13) = -13, що £ 0
Для Х21 сума потенціалів U2 + V1 = 13 + 6 = 19, що > 13
Для Х23 сума потенціалів U2 + V3 = 13 +(-7) = 6, що£ 28
Для Х31 сума потенціалів U3 + V1 = 13 + 6 = 19, що > 5
Для Х32 сума потенціалів U3 + V2 = 13 + 4 = 17, що £ 20
для Х34 сума потенціалів U3 + V4 = 13 + (-10) = 3, що £ 10
Даний план перевезень не є оптимальним, тому що в клітинках Х21, Х31, не виконується умова оптимальності Ui + Vj £ Cij.
Вибирається клітина Х31, починаючи з неї будується фігура перерахунку.
Наступна транспортна таблиця має вигляд:
При такому плані перевезень загальна кількість тонно-кілометрів буде становити:
FMin=7*6+19*4+5*3+28*0+7*5+20*6+18*0=288 т-км.
Обчислимо потенціали і для вільних клітин зробимо розрахунки по перевірці плану на оптимальність :
Для Х13 сума потенціалів U1 + V3 = 0 + 7 = 7, що £ 15
Для Х14 сума потенціалів U1 + V4 = 0 + 4 =4, що £ 19
Для Х15 сума потенціалів U1 + V5 = 0 + 1 = -1, що > 0
Для Х21 сума потенціалів U2 + V1 = -1 + 6 = 5, що £ 13
Для Х22 сума потенціалів U2 + V2 = -1 + 4 = 3, що £ 17
Для Х23 сума потенціалів U2 + V3 = -1 + 7 = 6, що £ 28
Для Х32 сума потенціалів U3 + V2 = -1 + 4 = 3, що £ 20
для Х34 сума потенціалів U3 + V4 = -1 + 4 = 3, що £ 10
Даний план перевезень не є оптимальним, тому що в клітинці Х15 не дотримується вимога оптимальності Ui + Vj £ Cij. Побудуємо фігуру перерахунку та розрахуємо нову таблицю.
Малюємо фігуру перерахунку та розрахуємо нову таблицю.
|
Поста-чальники |
Споживачі |
Запаси |
Потенціали, Ui |
|||||||||
|
В1 |
В2 |
В3 |
В4 |
Вфіктивний |
||||||||
|
A1 |
6 |
4 |
15 |
19 |
0 |
26 |
0 |
|||||
|
19 |
7 |
|||||||||||
|
A2 |
13 |
17 |
28 |
3 |
0 |
33 |
0 |
|||||
|
5 |
28 |
|||||||||||
|
A3 |
5 |
20 |
6 |
10 |
0 |
45 |
0 |
|||||
|
14 |
20 |
11 |
||||||||||
|
Потреба |
14 |
19 |
20 |
5 |
46 |
104 |
||||||
|
Потенціали, VJ |
5 |
4 |
6 |
3 |
0 |
При такому плані перевезень загальна кількість тонно-кілометрів буде становити:
FMin=7*6+19*4+5*3+28*0+7*5+20*6+18*0=281 т.-км.
Обчислимо потенціали та для вільних клітин зробимо розрахунки по перевірці плану на оптимальність :
Для Х11 сума потенціалів U1 + V1 = 0 + 5 = 5, що £ 6
Для Х13 сума потенціалів U1 + V3 = 0 + 6 = 6, що £ 15
Для Х14 сума потенціалів U1 + V4 = 0 + 3 = 3, що £ 19
Для Х21 сума потенціалів U2 + V1 = 0 + 5 = 5, що £ 13
Для Х22 сума потенціалів U2 + V2 = 0 + 4 = 4, що £ 17
Для Х23 сума потенціалів U2 + V3 = 0 + 6 = 6, що £ 28
Для Х32 сума потенціалів U3 + V2 = 0 + 4 = 4, що £ 20
для Х34 сума потенціалів U3 + V4 = 0 + 3 = 3, що £ 10
Даний план перевезень є оптимальним, тому що в усіх клітинах таблиці виконується умова оптимальності.
При оптимальному плані перевезень загальна кількість тонно-кілометрів буде становити 281 т.-км.
Так, перевезення вантажу слід організувати таким чином:
– з пункту А1 необхідно перевезти 19тон в пункт В2 та 7тон в пункт Вфікт;
– з пункту А2 необхідно перевезти 5тон в пункт В4 та 28тон в пункт Вфікт;
– з пункту А3 необхідно перевезти 14тон в пункт В1, 20тон в пункт В3 та 11тон в пункт Вфікт.
3. Рекомендована література
Курносов А. П., Сысоев И. А. Вычислительная техника т экономико-математические методы в сельском хозяйстве. – М., 1989. Кузнецов Ю. Н., Кузобов В. И., Ермольев Ю. М. Математическое программирование. – М.: Высш. шк., 1976. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. Исследование операций в экономике: Учебн. пособие для вузов/ Н. Ш.Кремер, Б. А.Путко, И. М.Тришин. М. Н.Фридман; Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. Акулич И. Л. Математическое программирование в примерах и задачах. – М.: Высш. Шк.», 1986, – 319 с . Ляшенко И. Н. Линейное и нелинейное программирование. – і К.: Вищашк., 1975,-371 с.
7. Математическое моделирование экономических процессов в сельском хозяйстве/ Гатаулин А. М. и др.; Под ред. А. М.Гатаулина. – М.: Агропромиздат, 1990. – 432с.:ил.
8. Эддоус М., Стэнфилд Р. Методы принятия решений/ Пер. с англ. под ред. член-корр. РАН И. И.Елисеевой. – М.: Аудит, ЮНИТИ, 1997. – 590с.
Крушевский А. В., Шевцов К. И. Математическое программирование и моделирование в экономике.: Учеб. пособие для вузов. – Киев: Высшая школа. Головное изд-во, 1979. – 456с. Курицкий Б. Я. Поиск оптимальных решений средствами Excel 7.0. – СПб.: ВНV – Санкт-Петербург, 1997. – 384с., ил. Ляшенко И. Н. Лінійне та нелінійне програмування. – К.: Вища шк., 1975. Степанюк В. В. Методи математичного програмування. – К.: Вища шк., 1984. Кузнецов Ю. Н., Кудрявцев В. И. Математическое программирование. – М., 1980. Франс Дж. и др. Математические модели в сельском хозяйстве. М.: Агропромиздат, 1987 Кравченко Р. Г. Математическое моделирование в сельском хозяйстве. М.:Колос, 1978. Кузнецов Ю. Н. Математические модели в с/х. М.: Высшая школа, 1981 Карпенко А. ф. Практикум по математическому моделированию экономических агропромышленных процессов в сельском хозяйстве. М.: Финансы и статистика, 1985.
Ви прочитали: "Транспортна задача"Читати далі