РЕШЕНИЕ ЗАДАЧИ ДОСТАВКИ МАКСИМАЛЬНОГО ВОЗМОЖНОГО КОЛИЧЕСТВА ГРУЗА ЗА ОПРЕДЕЛЕННОЕ ВРЕМЯ
© И.И.Бочкарев
© Государственный музей истории космонавтики им. К.Э. Циолковского, г. Калуга
Секция "К.Э. Циолковский и экономика космической деятельности"
2018 г.
Доклад посвящен решению задачи доставки максимально возможного количества груза на предприятиях ракетно-космической отрасли, реализующих государственные оборонные заказы и другие сложные, высокотехнологичные проекты и программы. Рассмотрены существующие и предложены новые методики.
Теория графов часто используется в самых различных областях. Благодаря данной теории можно описать экономические и плановые задачи для обеспечения производства или, например, сетевое планирование на предприятии. Теория графов так же позволяет автоматизировать управление производством, более оптимально размещать заказы на транспорт, рационализировать схемы перевозок и грузопотоков.
Исследования в области теории графов развивались вместе с теорией линейного программирования (и в общем случае с теорией оптимизации). Однако, как с практической, так и с теоретической точек зрения, потоковые задачи ведут к значительно более эффективным решениям, чем использование линейных программ. И данный подход получил самое большое внимание с того момента как Форд и Фалкерсон решили написать фундаментальный труд о потоках в сетях.
Раньше данные исследования были необходимы для военных нужд – исходя из связи между максимальными возможными потоками и минимальными разрезами. В докладе рассмотрено «мирное» применение теории потоков. Поставлена и решена задача доставки максимального количества груза за определенное время. Рассмотрен алгоритм решения задачи о максимальном потоке в сети. Разобраны основные понятия максимального потока в сети. Рассмотрен алгоритм поиска максимального потока в графе Форда — Фалкерсона.
Литература
1. Палангин Ю.И. Логистика – планирование и управление материальными потоками: учеб. пособие. – СПб.: Политехника, 2009. – 286с.
2. Верников Б.М – Лекция 16: Потоки. [Электронный ресурс] / Б. М. Верников, А. М. Шур // Уральский федеральный университет, Институт математики и компьютерных наук, кафедра алгебры и дискретной математики, - Электрон. дан. - Режим доступа к файлу: http://kadm.imkn.urfu.ru/files/tgr08+pdf.