РОСІЙСЬКИЙ ДЕРЖАВНИЙ ВІДКРИТИЙ ТЕХНІЧНИЙ
УНІВЕРСИТЕТ шляхів сполучення
Факультет В«ЕкономічнийВ»
Кафедра В«Економіка, фінанси та управління на транспорті В»
Контрольна робота
по дисципліни: В«ЕКОНОМІКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ В»
Воронеж 2008
Завдання № 1
Метод потенціалів для вирішення транспортної задачі в матричній формі з обмеженнями пропускної здібності.
Завдання:
1. Побудувати оптимальний план перевезень кам'яного вугілля з п'яти станцій А i (i = 1,2,3,4,5), до дев'яти великих споживачів, що мають під'їзні шляхи У j (J = 1,2, ..., 9). p> 2. Визначити обсяг тонно-кілометрової роботи початкової та оптимального планів перевезення вантажів.
Вихідні дані ( варіант 67 ):
Дані про наявність ресурсів на п'яти станціях відправлення А i наведені в таблиці 1, дані про розміри прибуття вантажу У j на дев'ять станцій призначення - в таблиці 2.
Таблиця 1 - Ресурси станцій відправлення А i (Рядки матриці)
Номер станції відправлення
Значення
А 1
150
А 2
160
А 3
400
А 4
150
А +5
140
Разом:
1000
Таблиця 2 - Обсяг потреби У j одержувача (Стовпці матриці)
Номер станції призначення
Значення
У 1
135
У 2
105
У 3
95
У 4
115
У 5
85
У 6
105
У 7
90
У 8
135
У 9
135
Разом:
1000
Рішення:
Відстань перевезення від кожній i-й станції відправлення до кожної j-й станції призначення зазначено у правому верхньому куті кожної клітини матриці. У лівому верхньому куті ряду клітин матриці вказані обмеження пропускної здатності.
Умовою завдання встановлено, що розмір всіх ресурсів у відправників дорівнює загальної потреби Одержувач:
В
З урахуванням отриманих умов необхідно знайти такі невід'ємні значення величин обсягів перевезень х ij , при яких сума добутків значень критерію З ij на розмір перевезень буде мінімальної, тобто
В
Спочатку будується початковий план базисного варіанту способом найменшого значення критерію.
Будь допустимий план є оптимальним тоді і тільки тоді, коли кожному рядку і кожному колонки матриці можуть бути присвоєні деякі числа U i і V j , звані потенціалами і що відповідають умовам:
V j - U i ≤ C ij для х ij = 0; (1) p>
V j - U i = C ij для d ij > х ij > 0, (2)
V j - U i ≥ C ij для х ij = d ij sub>, (3)
де V j - потенціал j-го стовпчика;
U i - потенціал i-го рядка;
C ij - відстань перевезення від i-го постачальника до j-го споживача;
х ij - кореспонденція (розміри перевезень) від i-го постачальника до j-го споживача;
d ij - величина пропускної здатності ij клітини.
Присвоєння потенціалів починають з рядка, в якій серед базисних клітин є максимальне відстань. Цьому рядку можна присвоїти будь-який позитивний потенціал, наприклад, 100. Потім...