Реферат на тему:
Транспортна задача (ТЗ). Постановка, методи розв’язування та аналізу.
План
1. Визначення оптимального плану ТЗ, які мають деякі ускладнення в їх
постановці.
2. Приклади розв’язування задач.
3. Література
Визначення оптимального плану транспортних задач, які мають деякі
складності в їхній постановці.
При знаходження рішення ряду конкретних транспортних задач часто буває
необхідно враховувати додаткові обмеження, що не зустрічалися вище при
розгляді простих варіантів даних задач. Зупинимося докладніше на деяких
можливих ускладненнях у постановках транспортних задач.
1. При деяких реальних умовах перевезення вантажу з визначеного пункту
відправлення Аі, у пункт призначення Вj, не можуть бути здійснені. Для
визначення оптимальних планів таких задач припускають, що тариф
перевезення одиниці вантажу з пункту Аі, у пункт Вj, є як завгодно
великою величиною М, і при цьому умові відомими методами знаходять
рішення нової транспортної задачі. При такім припущенні виключається
можливість при оптимальному плані транспортної задачі перевозити вантаж
з пункту Аі, у пункт Вj. Такий підхід до перебування рішення
транспортної задачі називають забороною чи перевезень чи блокуванням
відповідної клітки таблиці дані задачі.
2. В окремих транспортних задачах додатковою умовою є забезпечення
перевезення по відповідним маршрутах визначеної кількості вантажу.
Нехай, наприклад, з пункту відправлення Аі у пункт призначення Вj
потрібно обов’язково перевести dij одиниць вантажу. Тоді в клітку
таблиці даних транспортної задачі, що знаходиться на перетинанні рядка
Аi і стовпця Вj записує зазначене число аij і надалі цю клітку вважають
вільної з як завгодно великим тарифом перевезень М. Для отриманої в
такий спосіб нової транспортної задачі знаходять оптимальний план, що
визначає оптимальний план вихідної задачі.
3. Іноді потрібно знайти рішення транспортної задачі, при якому з пункту
відправлення Аі у пункт призначення Вj повинне бути завезено не менш
заданої кількості вантажу аij. Для визначення оптимального плану такої
задачі вважають, що запаси пункту Аі і потреби пункту Вj менше фактичних
на аij одиниць. Після цього знаходять оптимальний план нової
транспортної задачі, на підставі якого і визначають рішення вихідної
задачі.
4. У деяких транспортних задачах потрібно знайти оптимальний план
перевезень за умови, що з пункту відправлення Аі у пункт призначення Вj
перевозиться не більш ніж аij одиниць вантажу, тобто
(1)
Сформульовану задачу можна вирішити так. У таблиці результатних даної
задачі для кожного j-го обмеження (1) передбачають додатковий стовпець,
тобто вводять додатковий пункт призначення. В даному стовпці записують
ті ж тарифи що й у стовпці Вj за винятком тарифу, що знаходиться і
рядку Вj додатковому стовпці в цьому рядку тариф рахують рівним деякому
як завгодно великому числу М. При цьому потреби пункту В, вважають
рівними аij а потреби знову введеного пункту призначення думають рівними
bi, — аij. Рішення отриманої транспортної задачі може бути знайдено
методом потенціалів, і тим самим буде визначений оптимальний чи план
установлений нерозв’язність вихідної задачі. Помітимо, що вихідна
транспортна задача розв’язна лише в тому випадку, коли для неї існує
хоча б один опорний план.
Приведену вище задачу можна вирішити і таким способом З урахуванням
обмеження (1) за правилом мінімального елемента будують опорний план При
цьому якщо величина записуваного на даному кроці у відповідну клітку
числа визначається тільки обмеженням (1), то в наступному з розгляду
виключають тільки заповнену клітку В інших випадках з розгляду
виключають або рядок, або стовпець (що-небудь одне).
Якщо в результаті складання плану постачань усі наявні запаси пунктів
відправлення розподілені і потреби в пунктах призначення задоволені, то
отриманий опорний план транспортної задачі.
Якщо в якомусь рядку (а отже, і в стовпці) залишився нерозподілений
залишок, рівний d, то вводять додатковий пункт призначення і додатковий
пункт відправлення з потребами і запасами, рівними d. У клітці, що
знаходиться на перетинанні стовпця додаткового пункту призначення і
рядки додаткового пункту відправлення, тариф вважають рівним нулю У всіх
інших клітках даного рядка і стовпця тарифи думають рівними деякому як
завгодно великому числу М. Отриману в результаті цього транспортну
задачу вирішують методом потенціалів Після кінцевого числа кроків або
встановлюють, що вихідна задача не має опорного плану, або знаходять її
оптимальний план. При цьому (xj*f) — оптимальний план вихідної задачі,
якщо
(2)
Література.
Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. –
К.:КНЕУ, 2003.- 452 с.
Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник /
А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків,
Р.І. Квіт, В.В. Кісілевич – Львів: Національний університет “Львівська
політехніка” (Інформаційно-видавничий центр “Інтелект+” Інститут
післядипломної освіти) “Інтелект – Захід”, 2004. – 448 с.
Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное
пособие для студентов экономических специальних вузов. – Вища школа,
1985-319с.,ст.270-274.
Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне
програмування: Навч. – метод. посібник для самост. вивч. дисц. – К.:
КНЕУ, 2001. – 248 с.
Математичне програмування (методичний посібник для студентів економічних
спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І.,
Дронь В.С., Кондур О.С., – Чернівці: „Рута”, 1998.-168 с.
Нашли опечатку? Выделите и нажмите CTRL+Enter
