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

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

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

План.

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

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

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

Для транспортної задачі, вихідні дані якої приведені в табл. 2.14, знайти оптимальний план методом диференціальних рент.

Таблиця  2.14

Розв’язання. Перейдемо від табл. 2.14 до табл. 2.15, додавши один доповнюючий стовпець для вказівки надлишку і недоліку по рядках і один рядок для запису відповідних різниць.

Таблиця  2.15

У кожнім зі стовпців табл. 2.15 знаходимо мінімальні тарифи й обводимо їх кружками. Заповнюємо клітки, у яких коштують зазначені числа. Для цього в кожну з кліток записуємо максимально припустиме число. Наприклад, у клітку, що знаходиться на перетинанні рядка Аі і стовпця Вз, записуємо число 120. У цю клітку не можна помістити більше число, оскільки в такому випадку були б перевищені потреби пункту призначення В3.

У результаті заповнення відзначених вище кліток отриманий так називаний умовно оптимальний план, відповідно до якого цілком задовольняються потреби пунктів призначення B1, B2 B3 B4  і частково — пункту призначення В5. При цьому цілком розподілені запаси пункту відправлення А2. частково-пункту відправлення А1 і залишилися зовсім нерозприділені запаси пункту відправлення А3.

Після одержання умовно оптимального плану визначаємо збиткові і недостатні рядки. Тут недостатньої є рядок А2, тому що запаси пункту відправлення А2 цілком використані, а потреби пункту призначення В5 задоволені частково Величина недоліку дорівнює 80 од.

Рядка А1 і А3 є надлишковими, оскільки запаси пунктів відправлення А1 і А3 розподілені не цілком. При цьому величина надлишку рядка А1 дорівнює 60 од., а рядка А3 — 20 од. Загальна величина надлишку 60 + 20 = 80 збігається з загальною величиною недоліку, рівної 80.

Після визначення надлишкових і недостатніх рядків по кожному зі стовпців знаходимо різниці між мінімальними тарифами, записаними в надлишкових рядках, і тарифами, стоячими в заповнених клітках У даному випадку ці різниці Відповідно рівні 5, 4, 2, 1 (табл. 2 15) Для стовпця В3 різницю не визначена, тому що число, записане в кружку в даному стовпці, знаходиться в позитивному рядку. В стовпці В1 число, що коштує в кружку, дорівнює 1, а в надлишкових рядках у клітках даного стовпця найменшим є число 6 Отже, різниця для даного стовпця дорівнює 6—1=5 Аналогічно знаходимо різниці для інших стовпців для В2 12 — 8 = 4, для В4 7 — 5 = 2; для В5 4 — 3=1

Вибираємо найменшу зі знайдених різниць, що є проміжною рентою. В даному випадку проміжна рента дорівнює 1 і знаходиться в стовпці В5 Знайшовши проміжну ренту, переходимо до табл. 2 16.

Таблиця  2. 16.

У цій таблиці в рядках А1 і А3 (які являються надлишковими) переписуємо відповідні тарифи з рядків А1 і А3 табл. 2.15. Елементи рядка А2 (яка була недостатньою) виходять у результаті додатка до відповідного тарифам, що знаходяться в рядку А2 табл. 2 15, проміжної ренти, т е 1.

У табл. 2 16 число заповнюваних кліток зросло на одну. Це зазначено тим, що число мінімальних тарифів, стоячих у кожнім зі стовпців даної таблиці, зросло на одиницю, а саме в стовпці В5 тепер маються два мінімальних елементи 4. Ці числа укладаємо в кружки, клітки, у яких вони коштують, варто заповнити. Необхідно заповнити і клітки, у яких стоять найменші для інших стовпців тарифи. Це клітки табл. 2 16 у який відповідні тарифи укладені в кружки. Після того як зазначені клітки визначені, установлюємо послідовність їхнього заповнення. Для цього знаходимо стовпці (рядка), у яких мається лише одна клітка для заповнення. Визначивши і заповнивши деяку клітку, виключаємо з розгляду відповідний стовпець (рядок) і переходимо до заповнення наступної клітки. В даному випадку заповнення кліток проводимо в такій послідовності. Спочатку заповнюємо клітки А1  В3, А2  В1, А2  В2, А2  В4,  тому що вони є єдиними клітками для заповнення в стовпцях В1  В2, В3  і В4. Послу заповнення зазначених кліток заповнюємо клітку А3  В5, оскільки вона є єдиної для заповнення в рядку А3. Заповнивши цю клітку (табл. 2. 16.), виключаємо з розгляду рядок А3. Тоді в стовпці В5 залишається лише одна клітка для заповнення. Це клітка А2  В5, що заповнюємо Після заповнення кліток, установлюємо надлишкові і недостатні рядки (табл. 2. 16.). Як видно з табл. 2 16, ще мається нерозподілений залишок. Отже, отриманий умовно оптимальний план задачі і потрібно перейти до нової таблиці. Для цього по кожному зі стовпців знаходимо різниці між числом, записаним у кружку даного стовпця, і найменшим по відношенні до нього числом, що знаходиться в надлишкових рядках (табл. 2 16) Серед цих різниць найменша дорівнює 1. Це і є проміжна рента. Переходимо до нової таблиці (табл. 2 17).

Таблиця   217

Література.

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

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

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

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

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