Материал: TransportnaZadacha
МІНІСТЕРСТВО ТРАНСПОРТУ ТА ЗВ’ЯЗКУ УКРАЇНИ
Дніпропетровський національний університет залізничного транспорту імені академіка В. Лазаряна
Львівська філія
Кафедра транспортних технологій
МЕТОДИЧНІ ВКАЗІВКИ ТА ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ “РОЗВ’ЯЗУВАННЯ ТРАНСПОРТНИХ ЗАДАЧ” З ДИСЦИПЛІНИ “КОМП’ЮТЕРНІ ТЕХНОЛОГІЇ НА ЗАЛІЗНИЧНОМУ ТРАНСПОРТІ”
Укладач: Ю. М. Гнатів
Львів 2008
Укладач: Ю. М. Гнатів
УДК 681.3
Методичні вказівки та завдання до лабораторної роботи “Розв’язування транспортних задач” з дисципліни “Комп’ютерні технології на залізничному транспорті” / Львівська філія Дніпропетровського національного університету залізничного транспорту ім. акад. В. Лазаряна; укладач: Ю. М. Гнатів. – Львів, 2008. – 20 с.
Наводяться постановка транспортної задачі та методика її розв’язування у середовищах Excel і Mathcad. Пропонуються завдання для лабораторної роботи.
Для студентів денної та безвідривної від виробництва форм навчання спеціальності “Організація перевезень і управління на залізничному транспорті”.
Друкується за рішенням методичної комісії Львівської філії.
Рецензенти:
канд. фіз.-мат. наук, доцент Б. Р. Монцібович – керівник Львівського відділення Центру прикладної інформатики НАН України; канд. фіз.-мат. наук, доцент М. Д. Грилицький – доцент кафедри
фундаментальних дисциплін Львівської філії Дніпропетровського національного університету залізничного транспорту ім. академіка В. Лазаряна
©Гнатів Ю. М., укладання, 2008
©Видавничо-поліграфічний відділ Львівського центру науково - технічної і економічної інформації, 2008
2
ЛАБОРАТОРНА РОБОТА “РОЗВ’ЯЗУВАННЯ ТРАНСПОРТНИХ ЗАДАЧ”
Мета роботи. Отримати розв’язок транспортної задачі за допомогою табличного процесора Excel і пакета Mathcad.
1.ПОРЯДОК ВИКОНАННЯ РОБОТИ
1.Отримайте у викладача завдання для лабораторної роботи.
2.Ознайомтеся з методичними вказівками до виконання завдань.
3.Виконайте завдання у середовищах Excel і Mathcad.
4.Надрукуйте результати роботи.
5.Оформіть звіт про лабораторну роботу та здайте викладачу на перевірку.
2.ПОСТАНОВКА ТРАНСПОРТНОЇ ЗАДАЧІ
Транспортна задача – це задача про найбільш економний план перевезень однорідних продуктів з пунктів постачання в пункти споживання.
Нехай у m постачальників Ai зосереджені деякі однорідні продукти в
кількостях ai (i = |
1, m |
) |
одиниць відповідно. Ці продукти необхідно перевезти |
||||||||||||
до n споживачів Bj |
у кількостях bj ( j = |
|
) одиниць. |
Відомі вартості |
cij |
||||||||||
1, n |
|||||||||||||||
перевезень одиниці вантажу від постачальників Ai |
до споживачів B j . |
|
|||||||||||||
Необхідно скласти такий план перевезень, який дозволяє вивезти всі |
|||||||||||||||
вантажі, повністю задовольнити потреби та має мінімальну вартість. |
|
||||||||||||||
Нехай xij |
– кількість одиниць вантажу, які перевозитимуться від i -го |
||||||||||||||
постачальника |
до j -го |
споживача. |
Тоді умову |
задачі |
можна |
записати |
у |
||||||||
вигляді таблиці (табл. 1). |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Ai \ Bj |
|
|
B1 |
|
B2 |
|
|
… |
|
|
Bn |
Запаси |
|
||
A1 |
|
|
|
|
c |
c |
|
|
… |
|
|
c1n |
a1 |
|
|
|
|
|
|
11 |
12 |
|
|
|
x1n |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
x |
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
A2 |
|
|
|
|
c |
c |
|
|
|
|
|
|
c2n |
a2 |
|
|
|
|
|
21 |
22 |
|
|
… |
|
x2n |
|
|
|||
x |
|
|
|
|
x |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
21 |
|
|
|
|
22 |
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
… |
|
|
… |
|
|
… |
|
|
||
Am |
|
|
|
|
cm1 |
cm2 |
|
|
… |
|
|
cmn |
am |
|
|
xm1 |
|
xm2 |
|
|
|
xmn |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
||||||
Потреби |
|
|
b1 |
|
b2 |
|
|
… |
|
|
bn |
Σai = Σbj |
|
||
|
|
|
|
|
|
Табл |
. 1 |
|
|
|
|
|
|||
Вартість всього плану перевезень виражається подвійною сумою |
|
||||||||||||||
|
|
|
|
|
|
m |
|
n |
|
|
|
|
|
||
|
|
|
|
|
|
L = ∑∑cij xij . |
|
|
|
|
|
||||
i=1 j=1
Математична модель транспортної задачі має наступний вигляд.
3
Знайти найменше значення лінійної (цільової) функції
m |
n |
||||
L = ∑∑cij xij |
|||||
i=1 j=1 |
|||||
за обмежень |
|
|
|
|
|
n |
|
|
|
|
|
(i =1, m), |
|||||
∑xij = ai |
|||||
j=1 |
|
|
|
|
|
m |
|
|
|
|
|
∑xij =bj |
( j = |
|
), |
||
1, n |
|||||
|
|
|
|
|
|
i=1 |
|
|
|
|
|
xij ≥ 0 (i =1, m; j =1, n).
У цій моделі припускається, що сумарні запаси дорівнюють сумарним потребам, тобто
m
∑ai
i=1
Така модель називається закритою.
n
= ∑bj .
j=1
3. РОЗВ’ЯЗУВАННЯ ЗАДАЧІ У СЕРЕДОВИЩІ EXCEL
Нехай умова транспортної задачі задана таблицею 2.
Ai \ Bj |
B1 |
|
B2 |
|
B3 |
|
B4 |
|
Запаси |
A1 |
x |
5 |
x |
7 |
x13 |
4 |
x |
8 |
140 |
|
|
|
|
||||||
|
11 |
|
12 |
|
|
|
14 |
|
|
A2 |
x |
4 |
x |
9 |
x23 |
3 |
x |
6 |
90 |
|
|
|
|
||||||
|
21 |
|
22 |
|
|
|
24 |
|
|
A3 |
x31 |
2 |
x32 |
5 |
x33 |
8 |
x34 |
3 |
170 |
|
|
|
|
||||||
|
|
|
|
|
|
||||
Потреби |
100 |
|
150 |
|
80 |
|
70 |
|
400 |
|
|
|
|
Табл |
. 2 |
|
|
|
|
Для розв’язування цієї задачі на персональному комп’ютері з використанням табличного процесора Excel достатньо:
1)увести вихідні дані в комірки робочого листа;
2)розмітити діапазони комірок, необхідні для моделювання обсягів перевезень і формування елементів математичної моделі та цільової функції;
3)сформувати на робочому листі елементи математичної моделі та цільову функцію;
4)налаштувати програму Пошук розв’язку та виконати її.
Уведення вихідних даних. Вихідними даними для розв’язування транспортної задачі є матриця вартостей перевезень, запаси постачальників і потреби споживачів. Фрагмент робочого листа з уведеними даними поданий на мал. 1.
4
Мал. 1
Розмітка діапазонів комірок. На робочому листі для розв’язування транспортної задачі необхідно передбачити:
1)діапазон комірок „Матриця обсягів перевезень”, в якому будуть моделюватися об’єми перевезень;
2)діапазон комірок „Фактично реалізовано”, в якому моделюватиметься фактична реалізація продукту;
3)діапазон комірок „Фактично отримано”, в якому буде моделюватися фактичне задоволення потреб;
4)діапазон комірок „Вартості перевезень за споживачами”, в якому будуть обчислюватися транспортні витрати за кожним споживачем;
5)комірку „Вартість усіх перевезень”, в якій будуть моделюватися транспортні витрати за всіма споживачами.
Для розмітки перелічених діапазонів достатньо обвести їх рамками.
Фрагмент робочого листа з розміченими діапазонами комірок показаний на мал. 2.
Мал. 2
Формування елементів математичної моделі та цільової функції.
Елементами математичної моделі транспортної задачі є наступні суми:
5