UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваТранспортна задача (ТЗ). Постановка, методи розв\'язування та аналізу (реферат)
АвторPetya
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось2844
Скачало504
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

План.

 

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

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ