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