Реферат на тему:

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

План.

1. Методи мінімального елемента знаходження опорного плану ТЗ.

2. Приклад знаходження опорного плану методом мінімального елемента.

3. Метод апроксимації Фогеля знаходження опорного плану ТЗ.

4. Приклад знаходження опорного плану методом апроксимації Фогеля.

5. Література

Метод мінімального елемента.

Метод апроксимації Фогеля для визначення опорного плану ТЗ.

Метод мінімального елемента. В методі північно-західного кута на кожному
кроці потреби першого з пунктів призначення, які залишилися
задовольнялись за рахунок запасів першого з пунктів відправлення, які
залишилися. Очевидно, вибір пунктів призначення і відправлення доцільно
робити, орієнтуючись на тарифи перевезень, а саме: на кожному кроці
потрібно вибирати яку-небудь клітинку, яка відповідає мінімальному
тарифу (якщо таких клітинок декілька, то потрібно вибрати будь-яку з
них), і розглянути пункти призначення і відправлення, які відповідають
вибраній клітинці. Суть методу мінімального елемента і полягає в виборі
клітинки з мінімальним тарифом. Потрібно відмітити, що цей метод, як
правило, дозволяє найти опорний план транспортної задачі, при якому
загальна вартість перевезень вантажу менша, ніж загальна вартість
перевезень при плані, знайденому для даної задачі з допомогою
північно-західного кута. Тому найбільш доцільно опорний план
транспортної задачі знаходити методом мінімального елемента.

Приклад 1. Знайти опорний план транспортної задачі методом мінімального
елемента .

Розв’язок. Вихідні дані задачі запишемо в вигляді таблиці 1.

Таблиця 1.

Пункти

7

8 1

160 2

4

120 5 9 8

20

9

2

50 3

30 6

90

170

Потреби 120 50 190 110 470

рахуємо рівними 30 од.

і внесемо це значення в відповідну клітинку таблиці 1.

. В результаті отримаємо опорний план

При даному плані перевезень загальна вартість перевезень складає

.

Метод апроксимації Фогеля. При визначенні оптимального плану
транспортної задачі методом апроксимації Фогеля на кожній ітерації по
всіх стовбцях і по всіх рядках знаходять відмінність між двома
записаними в них мінімальними тарифами. Ці відмінності записують в
спеціально відведених для цього рядку і стовбці в таблиці умов задачі.
Серед вказаних відмінностей вибирають мінімальну. В рядку (або стовбці),
якій відповідає дана відмінність, визначають мінімальний тариф.
Клітинку, в якій він записаний, заповнюють на даній ітерації.

Якщо мінімальний тариф однаковий для декількох клітинок даного рядка
(стовбця), то для заповнення вибирають ту клітинку, яка знаходиться в
стовбці (рядку), який відповідає найбільшій відмінності між двома
мінімальними тарифами, які знаходяться в даному стовбці (рядку).

Приклад 2. Використовуючи метод апроксимації Фогеля, знайти опорний план
транспортної задачі, вихідні дані якої наведені в таблиці 2 (опорний
план цієї задачі раніше був знайдений методом мінімального елемента).

.

Таблиця 2.

Пункти

7

4

9 8

5

2 1

9

3 2

8

6 160

140

од. Після цього визначимо наступну клітинку для заповнення. Знову
знайдемо відмінності між двома мінімальними тарифами, які залишилися, в
кожному з рядків і стовпців і запишемо їх в другому доповнюючому стовбці
і в другому доповнюючому рядку таблиці 3.

Таблиця 3.

Пункти

відправлення Пункти призначення Запаси Відмінності по

7

8 1

50 2

4

120 5

9

2

30 3

. В результаті отримаємо опорний план

При цьому плані загальна вартість перевезень така:

.

Як правило, застосування метода апроксимації Фогеля дозволяє отримати
або опорний план, близький до оптимального, або самий оптимальний план.
Знайдений вище опорний план транспортної задачі являється також і
оптимальним.

Використана література.

1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб.
– К.:

КНЕУ, 2003.- 452 с.

2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник
/ А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків,
Р.І. Квіт, В.В. Кісілевич – Львів: Національний університет “Львівська
політехніка” (Інформаційно-видавничий центр “Інтелект+” Інститут
післядипломної освіти)

“Інтелект — Захід”, 2004. – 448 с.

3. Акулич М.Л.Математичиское програмирование в примерах и задачах:
Учебное пособие для студентов экономических специальних вузов. – Вища
школа, 1985-319с.,ст.36-47.

4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне
програмування: Навч. – метод. посібник для самост. вивч. дисц. – К.:
КНЕУ, 2001. – 248 с.

5. Математичне програмування (методичний посібник для студентів
економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І.,
Готинчан Т.І., Дронь В.С., Кондур О.С., — Чернівці: „Рута”, 1998.-168 с

1

Похожие записи