Сіра О. В. Національний технічний університет «хпі» (м. Харків) icon

Сіра О. В. Національний технічний університет «хпі» (м. Харків)




Скачати 84.52 Kb.
НазваСіра О. В. Національний технічний університет «хпі» (м. Харків)
Дата11.10.2012
Розмір84.52 Kb.
ТипЗадача

інформаційні системи і моделювання


УДК 656.073:519.246


Транспортна задача зі стохастичним попитом

Сіра О.В.

Національний технічний університет «ХПІ» (м. Харків)

Бачкір Л.В.

Кременчуцький державний політехнічний університет


Вступ. Транспортна задача лінійного програмування в традиційній постановці формулюється наступним чином. Маємо постачальників однорідного продукту та споживачів цього продукту. Відомі вектор

,

компоненти якого фіксують можливості постачальників, вектор

,

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


(1)


і задовольняє обмеження


, , (2)

, , (3)

, , . (4)


Шляхом додавання фіктивних змінних ця задача зводиться до канонічної, в якій нерівності (2), (3) перетворяться в рівності. Методи вирішення цієї задачі добре відомі та реалізовані в математичних пакетах, які широко застовуються (Mathсad, Exсel тощо).

Слід зазначити, що в умовах ринкової економіки приведена постановка транспортної задачі не може бути визнана реалістичною, оскільки параметри задачі, як правило, не є детермінованими величинами.

На практиці випадковими є можливості постачальників, потреби споживачів (попит на продукт), а також вартість перевезень. Зрозуміло, що за цих умов розв’язання задачі теж є випадковим і його отримання традиційними методами неможливе.

Методи вирішення таких задач поєднані в специфічний підклас загальних методів математичного програмування, що отримав назву стохастичне програмування [1].

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

Припустимо, наприклад, розглядається транспортна задача, в якій параметри , , що визначають попит споживачів продукту, - випадкові величини з відомими щільностями розподілу

, .

При цьому у формулюванні задачі замість обмежень (3) виникають імовірнісні обмеження наступного виду:


, , (5)


де , - допустимі вірогідності виконання нерівностей (3) при реалізації плану .

Для отримання детермінованого аналогу імовірнісного обмеження (5) обчислимо значення з рівнянь


,

.


Тоді, вочевидь, обмеження (5) еквівалентні умовам


, . (6)


Таким чином, отримана транспортна задача (1), (2), (4), (6) у детермінованій постановці, яка вирішується звичайними методами.

Принциповий недолік описаної методики полягає в неврахуванні відмінностей в компонентах сумарних витрат, пов’язаних з реалізацією різних планів задачі, що визначаються набором значень , . Річ у тому, що цей набір впливає не тільки на величину й, відповідно, сумарну вартість перевезень, але й на рівень витрат на зберігання нереалізованого продукту, а також на величину «штрафу» при виникненні дефіциту. В зв’язку з цим виникає необхідність постановки специфічної транспортної задачі з урахуванням зазначених обставин.

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

^ Матеріал і результати дослідження. Припустимо, для конкретності в задачі йдеться про перевезення будь-якого товару від виробників до магазинів для його реалізації. Введемо

- щільність розподілу випадкової величини попиту на товар у - му магазині;

- платня за зберігання одиниці товару в - му магазині;

- вартість одиниці товару в - му магазині при продажу;

- закупівельна вартість одиниці товару;

- обсяг замовлення товару для - го магазину, .

Тоді

- середні витрати на зберігання непроданої частини товару в - ому магазині,

- середні втрати у зв’язку з дефіцитом товару в - ому магазині,


,

.


З урахуванням цього, вихідна задача перетвориться до вигляду: знайти план перевезень,


, (7)


який задовольняє обмеженням


, , (8)

, , (9)

, (10)

, , .(11)


В окремому випадку, коли продається швидкопсувний товар, що потребує дотримання спеціальних умов при зберіганні, щільність розподілу випадкової величини попиту має вигляд:


,

.


Тоді вираз (7), після елементарних перетворень, запишеться таким чином:

(12)

Для вирішення отриманої задачі пропонується застосовувати двохетапну ітераційну процедуру.

На першому етапі кожної ітерації розв’язується координуюча задача визначення набору .

На другому етапі ітерації розв’язується звичайна транспортна задача, в якій вектор значень параметрів споживання задається вирішенням координуючої задачі. Для побудови загальної процедури вирішення задачі може бути застосований метод Нелдера-Міда відшукання вектору з алгоритмічно заданою цільовою функцією . Обчислювальна процедура організовується таким чином.

Попередньо для кожного зі споживачів розраховуються оцінки мінімального та максимального значення попиту шляхом розв’язання рівнянь:


,

, (13)

,

, (14)


де - деяка достатньо мала вірогідність (наприклад, ).

У результаті розв’язання отримаємо


, ,

, .


Вважатимемо, що компоненти векторУ





повинні задовольняти обмеженням


, . (15)


Тепер, на першій ітерації задамо вихідну сукупність векторів , що формує симплекс із -ою вершинами в - мірному просторі з координатами вершин, які визначаються матрицею:

(16)

,

, (17)

, (18)

. (19)


У даному випадку -й стовпець матриці задає координати вектора . При цьому, як легко перевірити, співвідношення (17) забезпечують виконання обмежень (15) для компонентів вектора , а співвідношення (18), (19) – для компонентів всієї решти векторів -


.


Далі, послідовно задаючи компоненти векторів





в якості правих частин обмежень (9), отримаємо транспортних задач з цільовою функцією





та обмеженнями (8)-(11).

Сукупність розв’язань цих задач визначають набір значень цільової функції на цих векторах:


.


Подальша обчислювальна процедура організовується відповідно до стандартної технології методу Нелдера-Міда. Вершини симплексу впорядковуються в порядку зростання значень цільової функції та перенумеровуються. Потім здійснюється віддзеркалення «якнайгіршої» точки відносно центру тяжіння багатогранника, який отримаємо в результаті віддалення «якнайгіршої» вершини.

Координати нової точки, що виходить, розраховують за формулою:


, (20)

. (21)


Обчислюється значення цільової функції в цій точці шляхом вирішення транспортної задачі (7) – (11), в якій потреби магазинів визначаються вектором .

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

За результатами порівняння виконується одна з наступних операцій.

Якщо , то виконується операція розтягування. При цьому обчислюється нова точка


. (22)


Якщо , то реалізується операція віддзеркалення.

Якщо , то виконується операція стиснення та обчислюється нова точка


. (23)


У всіх випадках нові точки або замінюють «якнайгіршу» крапку .

Нарешті, якщо , то реалізується редукція симплексу. При цьому всі точки підтягуються до якнайкращої вершини:


.(24)


В отриманих нових точках обчислюються значення цільової функції шляхом вирішення відповідних транспортних задач, після чого процедура Нелдера-Міда може бути продовжена.

Покажемо тепер, що якщо точки початкового симплексу задовольняють співвідношенню (10), то і нові точки, що розраховуються по формулах (20) – (24) також будуть задовольняти йому.

Отже, припустимо


. (25)


Тоді для точки , яку отримали в результаті віддзеркалення за формулою (20), маємо





Звідси, з урахуванням (25), отримаємо


.


Абсолютно аналогічно доводиться, що точки і також належать гіперплощині, що проходить через .

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

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


ЛІтература

  1. Ермольев Ю.М. Методы стохастического программирования. - М.: Наука, 1976. – 239с.

  2. Юдин Д.Б. Задачи и методы стохастического программирования. - М.: Сов. Радио, 1979. – 385с.

  3. Ермольев Ю.М., Ляшко И.И., Михалевич В.С., Тюптя В.И. Математические методы исследования операций. – К.: Вища школа, 1979. – 312 с.



Стаття подана 7.11.2006 г.

Вісник КДПУ. Випуск 6/2006 (41). Частина 1



Схожі:

Сіра О. В. Національний технічний університет «хпі» (м. Харків) icon«харківський політехнічний інститут»
Національний технічний університет «хпі» проводить ХІ міжнародну школу-семінар «Сучасні педагогічні технології в освіті»
Сіра О. В. Національний технічний університет «хпі» (м. Харків) iconЯ. Н. Питак Я. Н., С. В. Горбатко, О. Я. Питак // Зб наук праць ват «Укрндівогнетривів імені А. С. Бережного». Харків: Каравела. 2008. №108. С. 174-179
Горбатко С. В. Разработка и совершенствование метода керамической наплавки / А. Н. Манкевич, С. В. Горбатко // Вісник Національного...
Сіра О. В. Національний технічний університет «хпі» (м. Харків) iconМІнІстерство освіти І науки украЇни запорізький національний технічний університет державний вищий навчальний заклад «ДонецЬкий національний технІчний унІверситет»
move to 0-22565859
Сіра О. В. Національний технічний університет «хпі» (м. Харків) iconИ запорізький національний технічний університет державний вищий навчальний заклад «ДонецЬкий національний технІчний унІверситет»

Сіра О. В. Національний технічний університет «хпі» (м. Харків) iconИ запорізький національний технічний університет державний вищий навчальний заклад «ДонецЬкий національний технІчний унІверситет»

Сіра О. В. Національний технічний університет «хпі» (м. Харків) iconДоговір про підготовку фахівців № 20 р. Державний вищий навчальний заклад «Донецький національний технічний університет»
Державний вищий навчальний заклад «Донецький національний технічний університет», в особі ректора Мінаєва О. А., який діє на підставі...
Сіра О. В. Національний технічний університет «хпі» (м. Харків) iconЛьвівський національний університет імені Івана Франка Тернопільський національний технічний університет імені Івана Пулюя Вінницький національний аграрний університет Жешувський університет Інформаційний лист Вельмишановні колеги,
На конференції планується обговорення проблем та розробка рекомендацій за такими напрямами
Сіра О. В. Національний технічний університет «хпі» (м. Харків) icon«донецький національний технічний університет» 83000, м. Донецьк, вул. Артема, 58 телефон (062) 301 03 64
Міністерства освіти І науки, молоді та спорту України №1324 від 18. 11. 11 р. Донецький національний технічний університет призначений...
Сіра О. В. Національний технічний університет «хпі» (м. Харків) iconУгода про підготовку аспіранта (докторанта) за рахунок державного замовлення № 20 р. Державний вищий навчальний заклад «Донецький національний технічний університет»
Державний вищий навчальний заклад «Донецький національний технічний університет» Міністерства освіти І науки, молоді та спорту України...
Сіра О. В. Національний технічний університет «хпі» (м. Харків) iconПолтавський національний технічний університет імені Юрія Кондратюка електромеханічний факультет вас вітає провідний вищий навчальний заклад центрального регіону України Полтавський національний технічний університет імені Юрія Кондратюка
move to 928-10859
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи