WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Транспортна задача (ТЗ). Постановка, методи розв'язування та аналізу - Реферат

Транспортна задача (ТЗ). Постановка, методи розв'язування та аналізу - Реферат


Реферат на тему:
Транспортна задача (ТЗ). Постановка, методи розв'язування та аналізу.
План.
1. Методи мінімального елемента знаходження опорного плану ТЗ.
2. Приклад знаходження опорного плану методом мінімального елемента.
3. Метод апроксимації Фогеля знаходження опорного плану ТЗ.
4. Приклад знаходження опорного плану методом апроксимації Фогеля.
5. Література
Метод мінімального елемента.
Метод апроксимації Фогеля для визначення опорного плану ТЗ.
Метод мінімального елемента. В методі північно-західного кута на кожному кроці потреби першого з пунктів призначення, які залишилися задовольнялись за рахунок запасів першого з пунктів відправлення, які залишилися. Очевидно, вибір пунктів призначення і відправлення доцільно робити, орієнтуючись на тарифи перевезень, а саме: на кожному кроці потрібно вибирати яку-небудь клітинку, яка відповідає мінімальному тарифу (якщо таких клітинок декілька, то потрібно вибрати будь-яку з них), і розглянути пункти призначення і відправлення, які відповідають вибраній клітинці. Суть методу мінімального елемента і полягає в виборі клітинки з мінімальним тарифом. Потрібно відмітити, що цей метод, як правило, дозволяє найти опорний план транспортної задачі, при якому загальна вартість перевезень вантажу менша, ніж загальна вартість перевезень при плані, знайденому для даної задачі з допомогою північно-західного кута. Тому найбільш доцільно опорний план транспортної задачі знаходити методом мінімального елемента.
Приклад 1. Знайти опорний план транспортної задачі методом мінімального елемента .
Розв'язок. Вихідні дані задачі запишемо в вигляді таблиці 1.
Таблиця 1.
Пункти
Відправлення Пункти призначення Запаси
7
8 1
160 2
160
4
120 5 9 8
20
140
9
2
50 3
30 6
90
170
Потреби 120 50 190 110 470
Мінімальний тариф, що дорівнює 1, знаходиться в клітинці для змінної . Припустимо , запишемо це значення в відповідну клітинку таблиці 1 і виключимо тимчасово з розгляду рядок . Потреби пункту призначення рахуємо рівними 30 од.
В частині таблиці, яка залишилася, з двома рядками і , і чотирма стовбцями , , і клітинка з найменшим значенням тарифу знаходиться на перетині рядка і стовбця , де . Припустимо і внесемо це значення в відповідну клітинку таблиці 1.
Тимчасово виключимо з розгляду стовбець і будемо рахувати, що запаси пункту дорівнюють 120 од. Після цього розглянемо частину таблиці, яка залишилася, з двома рядками і , і трьома стовбцями , і . В ній мінімальний тариф знаходиться в клітинці на перетині рядка і стовбця і дорівнює . Заповнимо описаним вище методом цю клітинку і аналогічно заповнимо (в певній послідовності) клітинки, які знаходяться на перетині рядка і стовбця , рядка і стовбця , рядка і стовбця . В результаті отримаємо опорний план
При даному плані перевезень загальна вартість перевезень складає
.
Метод апроксимації Фогеля. При визначенні оптимального плану транспортної задачі методом апроксимації Фогеля на кожній ітерації по всіх стовбцях і по всіх рядках знаходять відмінність між двома записаними в них мінімальними тарифами. Ці відмінності записують в спеціально відведених для цього рядку і стовбці в таблиці умов задачі. Серед вказаних відмінностей вибирають мінімальну. В рядку (або стовбці), якій відповідає дана відмінність, визначають мінімальний тариф. Клітинку, в якій він записаний, заповнюють на даній ітерації.
Якщо мінімальний тариф однаковий для декількох клітинок даного рядка (стовбця), то для заповнення вибирають ту клітинку, яка знаходиться в стовбці (рядку), який відповідає найбільшій відмінності між двома мінімальними тарифами, які знаходяться в даному стовбці (рядку).
Приклад 2. Використовуючи метод апроксимації Фогеля, знайти опорний план транспортної задачі, вихідні дані якої наведені в таблиці 2 (опорний план цієї задачі раніше був знайдений методом мінімального елемента).
Розв'язок. Для кожного рядка і стовбця таблиці умов знайдемо відмінності між двома мінімальними тарифами, записаними в даному рядку чи стовбці, і помістимо їх в відповідному доповнюючому стовбці або доповнюючому рядку таблиці 3. Так, в рядку мінімальний тариф дорівнює 4, а наступний за ним дорівнює 5, відмінність між ними .
Таблиця 2.
Пункти
відправлення Пункти призначення Запаси
7
4
9 8
5
2 1
9
3 2
8
6 160
140
170
Потреби 120 50 190 110 470
Так само відмінність між мінімальними елементами в стовбці дорівнює . Вирахувавши всі ці відмінності, бачимо, що найбільша з них відповідає стовбцю . В цьому стовбці мінімальний тариф записаний в клітинці, яка знаходиться на перетині рядка і стовбця .Таким чином, цю клітинку потрібно заповнити. Заповнивши її, ми тим самим задовільним потреби пункту . Тому виключимо з розгляду стовбець і будемо рахувати, що запаси пункту дорівнюють од. Після цього визначимо наступну клітинку для заповнення. Знову знайдемо відмінності між двома мінімальними тарифами, які залишилися, в кожному з рядків і стовпців і запишемо їх в другому доповнюючому стовбці і в другому доповнюючому рядку таблиці 3.
Таблиця 3.
Пункти
відправлення Пункти призначення Запаси Відмінності по
Рядкам
7
8 1
50 2
110 160 1 6 - - - -
4
120 5
20 9 8 140 1 1 1 1 1 0
9
2
30 3
140 6 170 1 1 1 7 - -
Потреби 120 50 190 110 470
Відмінності по стовбцям 3 3 2 4
3 3 2 -
5 3 6 -
5 3 - -
- 0 - -
- 0 - -
Як видно з таблиці 3, найбільша вказана відмінність відповідає рядку . Мінімальний тариф в цьому рядку записаний в клітинці, яка знаходиться на перетині її з стовбцем . Послідовно, заповнюємо цю клітинку. Помістивши в неї число 50, цим самим припускаємо, що запаси в пункті повністю вичерпані, а потреби в пункті дорівнюють од. Виключимо з розгляду рядок і визначимо нову клітинку для заповнення. Продовжуючи ітераційний процес, послідовно заповнюємо клітинки, які знаходяться на перетині рядка і стовбця , рядка і стовбця , рядка і стовбця , рядка і стовбця . В результаті отримаємо опорний план
При цьому плані загальна вартість перевезень така:
.
Як правило, застосування метода апроксимації Фогеля дозволяє отримати або опорний план, близький до оптимального, або самий оптимальний план. Знайдений вище опорний план транспортної задачі являється також і оптимальним.
Використана література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:
КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка"(Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти)
"Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с
Loading...

 
 

Цікаве