2020, випуск 4, c. 5-14

Одержано 21.10.2020; Виправлено 05.12.2020; Прийнято 17.12.2020

Надруковано 31.12.2020; Вперше Online 22.01.2021

https://doi.org/10.34229/2707-451X.20.4.1

Попередня  |  Повний текст  |  Наступна

 

УДК 519.85

Про лінійну та квадратичну двоетапні транспортні задачі

П.І. Стецюк 1 * ORCID ID favicon Big,   О.П. Лиховид 1,   А.А. Супрун 1

1 Інститут кібернетики імені В.М. Глушкова НАН України, Київ

* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Вступ. При формулюванні класичної двоетапної транспортної задачі мається на увазі, що вантаж перевозиться від постачальників до споживачів через проміжні пункти. В якості проміжних пунктів можуть виступати посередницькі фірми та різного роду сховища (склади).

У статті розглядаються дві математичні моделі для двоетапної транспортної задачі (задача лінійного програмування та задача квадратичного програмування) та достатньо універсальний спосіб їх розв'язання за допомогою сучасного програмного забезпечення. Він використовує опис задачі на мові моделювання AMPL (A Mathematical Programming Language) та залежить від того, яка із відомих програм вибирається для розв’язання задачі лінійного, або квадратичного програмування.

Мета роботи. Запропонувати використання AMPL-коду для розв'язання двоетапної транспортної задачі лінійного програмування за допомогою сучасного програмного забезпечення для задач лінійного програмування. Сформулювати математичну модель двоетапної транспортної задачі квадратичного програмування та дослідити її властивості.

Результати. Описано властивості двох варіантів двоетапної транспортної задачі: задачі лінійного програмування та задачі квадратичного програмування. Наведено AMPL-код для розв'язання двоетапної транспортної задачі лінійного програмування за допомогою сучасного програмного забезпечення для задач лінійного програмування. Наведено та проаналізовано результати розрахунку за допомогою програми Gurobi для двоетапної транспортної задачі лінійного програмування, яка має багато розв'язків. Сформульовано двоетапну транспортну задачу квадратичного програмування та знайдено умови, при яких вона має єдиний розв’язок.

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

 

Ключові слова: транспортна задача, задача лінійного програмування, мова моделювання AMPL, програма Gurobi, задача квадратичного програмування.

 

Цитувати так: Стецюк П.І., Лиховид О.П., Супрун А.А. Про лінійну та квадратичну двоетапні транспортні задачі. Cybernetics and Computer Technologies. 2020. 4. С. 5–14. https://doi.org/10.34229/2707-451X.20.4.1

 

Список літератури

           1.     Карагодова О.О., Кігель В.Р., Рожок В.Д. Дослідження операцій: Навч. посіб. К.: Центр учбової літератури, 2007. 256 с.

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

           3.     Стецюк П.І., Ляшко В.І., Мазютинець Г.В. Двоетапна транспортна задача та її AMPL-реалізація. Наукові записки НаУКМА. Комп'ютерні науки. 2018. Т. 1. С. 14–20. https://doi.org/10.18523/2617-3808.2018.14-20

           4.     Fourer R., Gay D., Kernighan B. AMPL, A Modeling Language for Mathematical Programming. Belmont: Duxburry Press, 2003. 517 p.

           5.     NEOS Solver. https://neos-server.org/neos/solvers/

           6.     Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, 2014. https://www.gurobi.com

           7.     Григорак М.Ю. Інтелектуалізація ринку логістичних послуг: концепція, методологія, компетентність: монографія. Київ: Сік Груп Україна, 2017. 513 с.

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна

 

 

 

© Вебсайт та оформлення. 2019-2022,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.