Одна задача розміщення вантажів як квадратична задача на поліпереставленях та підходи до її розв'язання з використанням maple
| Вид материала | Задача |
- Механічний рух та його види. Основна задача механіки та способи її розв’язання в кінематиці, 83.06kb.
- Навчально-виховний комплекс №6 «Перспектива» виховання творчої особистості в умовах, 116.55kb.
- Оптимальний розподіл однорідних ресурсів із використанням Mathcad І Excel. Мета, 61.72kb.
- Элективный курс по математике «Задача одна решения разные», 103.73kb.
- Перебирання варіантів в програмуванні задача про розміщення ферзів, 262.16kb.
- Обласна програма підтримки розвитку житлового кредитування населення м. Запоріжжя, 485.09kb.
- Загальна характеристика Програми Визначення проблем, на розв’язання яких спрямована, 164.05kb.
- Про графічний спосіб розв’язання математичних задач, 262.98kb.
- Программа курса лекций «Математические методы и модели исследования операций», 27.98kb.
- Т. М. Боровська кандидат технічних наук, доцент І. С. Колесник, 118.17kb.
УДК 519.85
ОДНА ЗАДАЧА РОЗМІЩЕННЯ ВАНТАЖІВ ЯК КВАДРАТИЧНА ЗАДАЧА НА ПОЛІПЕРЕСТАВЛЕНЯХ ТА ПІДХОДИ ДО ЇЇ РОЗВ'ЯЗАННЯ З ВИКОРИСТАННЯМ MAPLE
Пічугіна О.С., Гайтан Т.М.
Полтавський національний технічний університет, pichugina_os@mail.ru
Постановка задачі. Нехай є
вантажів із заданими вагами. Ці вантажі необхідно розмістити у відповідну кількість відсіків із заданими координатами таким чином, щоб відхилення центру тяжіння системи відносно заданої точки було мінімальним, якщо є певні обмеження по розміщенню вантажів на судні, а саме - всі вантажі та відсіки поділені на декілька груп, і вантажі кожної групи можна розміщувати тільки у відсіки цієї групи.Дана задача може бути сформульована як квадратична задача мінімізації на множині поліпереставлень
:
. (1)Цільова функція (1), взагалі кажучи, неопукла. Але використання геометричних властивостей множини
дозволяє звести (1) до:
, (2)де
- опукла, 
( - опукле продовження (ОП) 
на 
). При формуванні можна використати створену в Maple програму, яка дозволяє для довільних многочленів 
і множин ітераційно формувати 
.Особливостями та перевагами даної програми є:
- вдале поєднання вбудованих в Maple можливостей символьних перетворень та мови програмування;
- можливість покроково, отже наочно, побачити всі етапи формування ОП;
- в алгоритмі вперше було використано прийом, коли комбінаторні властивості множини , в даному випадку поліпереставлень, використовуються не тільки на останньому етапі формування ОП, але і на проміжних;
- окремими випадками її є можливість формування ОП: а) для переставлень (при
); для многочленів 2-го і 3-го степенів (
), що, в свою чергу, відкриває перспективи розв’язання чисельних практичних задач на переставленнях і поліпереставленнях, цільові функції яких квадратичні і кубічні, зокрема, для представленої задачі.
УДК 519.85
програмний комплекс підтримки прийняття рішень
У задачах вибору предметів споживання
Пічугіна О.С., Мушинський Ф.В.
Полтавський національний технічний університет, pichugina_os@mail.ru
Постановка задачі - спроектувати і програмно реалізувати систему підтримки прийняття рішень (ПР) при виборі довільного товару з використанням методу аналізу ієрархій (МАІ) і потужного сховища даних, сформованого з Інтернет із наступними можливостями:
1) автоматизація збору інформації про товари, наявної в Інтернет-ресурсах,
2) створення єдиної бази даних (БД) і ПР про вибір найкращого товару із наявних у БД залежно від вимог і пріоритетів користувача.
Актуальність поставленої задачі зумовлена постійною потребою в розв’язанні реальних задач вибору споживчих товарів на основі даних з Інтернет-ресурсів, які вельми різнорідні й значні за обсягом.
Було запропоновано власну методологію побудови людино-машинної системи підтримки ПР, що задовольняє поставлені вимоги, при цьому при впорядкуванні рішень використовується МАІ, у МАІ, в свою чергу, - агреговану експертну інформацію, що поступово уточнюється і наближається до об'єктивної. Зокрема, запропоновано поступове уточнення і вдосконалення базової ієрархії певного вибору (наприклад, вибору ноутбука), а також експертних порівняльних оцінок у ході розв'язання індивідуальних проблем аналогічного вибору. Також запропоновано при виборі конкретного предмету споживання інформацію про альтернативи (елементи вибору) та їх конкретні характеристики автоматизовано здобувати з Інтернет.
Дану методологію було покладено в основу розробленого мовою С# програмного комплексу з використанням СУБД SQL Server. Зокрема, було здійснено організацію завантаження й екстрагування даних із декількох Інтернет-ресурсів, їх стандартизацію та узгодження, формування єдиної БД, модифікацію структури ієрархії вибору, автоматичну генерацію базових порівняльних оцінок, внесення експертної інформації, надання рекомендацій у виборі товару.
Систему було протестовано на кількох задачах вибору з використанням реальних експертних оцінок, які можуть бути використані при розв’язанні аналогічних задач. Створена система може бути використана як у практичних цілях, наприклад, у задачах вибору обладнання й устаткування, в установах і організаціях, при виборі споживчих товарів фізичними особами, так і в методологічних, адже програма є потужним інструментом освоєння методів ПР, зокрема, МАІ.
УДК 519.85
ПРОГРАМА РОЗВ’ЯЗАННЯ СТОХАСТИЧНОЇ ЗАДАЧІ ФОРМУВАННЯ ПОРТФЕЛЮ ЦІННИХ ПАПЕРІВ ЯК ЗАДАЧІ ЦІЛОЧИСЕЛЬНОЇ ОПТИМІЗАЦІЇ
Пічугіна О.С., Шпилева Ю.В.
Полтавський національний технічний університет, pichugina_os@mail.ru
Постановка задачі - сформувати портфель цінних паперів (портфель ЦП, ПЦП) якщо відомо, що ЦП можуть продаватися заданими пакетами, вартість ПЦП не може перевищувати задану величину (тобто залучення ззовні не передбачається) з метою максимізації очікуваного прибутку портфеля (або мінімізації середнього ризику за умови дотримання певного рівня прибутковості ПЦП).
Математична модель задачі являє собою стохастичну модель ПЦП в абсолютній формі з умовою цілочисельності складових портфеля, отже, розвязується методами стохастичного програмування (СП).
Сфера застосування методів СП дуже широка, адже модель будь-якої задачі оптимізації, наприклад, звичайної задачі планування виробництва з визначеними наперед нормами споживання матеріалів на виробництво, обсягів ресурсів тощо, - лише абстракція, далека від реальності. Насправді всі параметри – випадкові величини, а оптимальне значення цільової функції можна інтерпретувати лише як максимум середнього, очікуваного значення критерію – прибутку, валового випуску, вартості продукції тощо.
Теж саме стосується і відомої моделі формування портфеля цінних паперів (портфеля ЦП) – створити пакет, якщо задана сума капіталу, що забезпечує максимальний очікуваний прибуток та мінімальний середній ризик від використання. Дана задача – нелінійна і двокритеріальна і не може бути зведена до однокритеріальної в силу конфліктності обох цілей, тож зазвичай розбивається на дві підзадачі.
Нами розглянуто деяке узагальнення класичної моделі формування ПЦП в абсолютній формі, метою якої є формування ПЦП у вигляді набору пакетів заданого обсягу, тобто розглядається дискретний аналог класичної задачі. Було створено програму, що дозволяє формувати вказані ПЦП, а також було порівняно ефективність застосування саме такого підходу до формування ПЦП порівняно з відомими постановками ПЦП у відносній формі, які не дозволяють урахувати умову цілочисельності кількості пакетів у портфелі.
Програма цікава як із практичної точки зору – може застосуватися у формування ПЦП невеликих обсягів (наприклад, фізичними особами), так і з методологічної, адже може використовуватися як засіб навчання формуванню портфелів у різних постановках і порівняння результатів.
УДК 519.85
ПРОГРАМНА РЕАЛІЗАЦІЯ ЗАДАЧІ ОПТИМІЗАЦІЇ І ПРОГНОЗУВАННЯ РОЗВИТКУ МІСТА
Пічугіна О.С., Кльокта І.В.
Полтавський національний технічний університет, pichugina_os@mail.ru
Дана робота присвячена актуальній проблеми складання плану розвитку міста, що забезпечує потреби в ресурсах, виконання планових завдань і при цьому мінімізує сумарні витрати на забезпечення діяльності міста.
Після огляду підходів до моделювання таких задач, в якості моделей було обрано оптимізаційні, серед задач оптимізації – лінійну модель розвитку міста, що зв'язує виробництво і споживання, виробничі і невиробничі потреби міста, ввезення і вивезення продукції тощо, яка продемонструвала свою ефективність ще за часів планової економіки. Нині, в період ринкової економіки дослідження перспектив і «вузьких місць» в управлінні великими містами може бути дуже цікавим як для місцевої адміністрації, так і для бізнесменів, які шукають шляхи підвищення ефективності своєї роботи.
Було створено програмну реалізацію для побудови оптимального плану системи «місто» з використанням вказаної математичної моделі в середовищі розробки C# із наступними можливостями:
- завантаження даних у спеціально визначеному форматі;
- формування матриці обмежень, цільової функції задачі лінійного програмування;
- перехід від загальної форми задачі до канонічної;
- пошук розв'язку лінійної задачі, реалізований з автоматичним підключенням вбудованих можливостей Ms Excel;
- формування оптимального розв’язку вихідної задачі по вектору плану ЗЛП;
- аналіз результату, зокрема, можливість визначення дефіцитних ресурсів та ресурсів, по яких є резерви.
Запронована програма має на меті, в першу чергу, практичне застосування у вирішенні існуючих проблем ефективного управління містом, областю чи країною. Але і в учбовому процесі вона може вдало використовуватися, адже демонструє непрості шляхи вирішення проблеми алгоритмізації складних задач математичного моделювання, а також відповідає на досить складно зрозумілі студентами питання інтерпретації отриманих планів розвитку міста, зокрема визначення шляхів покращення розв'язку за рахунок корегування параметрів обмежень, наприклад, збільшення обсягу дефіцитних ресурсів, а також обчислення сумарної ефективності подібних заходів управління.