Итерационный апекс-метод для решения задач линейной оптимизации

АННОТАЦИЯ 2
ВВЕДЕНИЕ 8
1 АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 11
1.1 Линейное программирование 11
1.2 Некоторые методы решения задач линейного программирования 13
1.2.1 Графический метод 13
1.2.2 Симплекс-метод 14
1.2.3 Транспортная задача 15
1.2.4 Метод внутренней точки 15
1.2.5 Метод опорных векторов 16
1.3 Большие и сверхбольшие задачи линейного программирования 17
1.3.1 Развитие методов решения больших и сверхбольших задач линейного
программирования 17
1.3.2 Метод фейеровских отображений 19
1.3.3 Метод Чиммино 23
1.4 Применение метода Чиммино и метода фейеровских отображений для
решения двумерной задачи линейного программирования 25
1.4.1 Описание двумерной задачи 25
1.4.2 Решение задачи методом Чиммино 26
1.4.3 Решение задачи методом фейеровских отображений 27
1.4.4 Сравнительный анализ метода Чиммино и метода фейеровских
отображений 28
Выводы по разделу один 31
2 АПЕКС-МЕТОД ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ 32
2.1 Формулировка задачи 32
2.2 Фаза Quest 33
2.3 Фаза Target 34
Выводы по разделу два 38
3 ПРИМЕНЕНИЕ АПЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ 40
3.1 Описание экспериментальной задачи 40
3.2 Решение экспериментальной задачи размерности N = 2 41
3.3 Влияние параметров апекс-метода на время решения экспериментальной
задачи размерности N = 50, N = 75, N = 100 43
3.4 Верификация апекс-метода 53
Выводы по разделу три 54
ЗАКЛЮЧЕНИЕ 56
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 57
ПРИЛОЖЕНИЕ А 63
ЛИСТИНГ ФАЙЛА «APEX-METHOD.IPYNB» 63
Купить

Актуальность темы исследования итерационного апекс-метода для решения задач линейной оптимизации заключается в том, что для реализации любой задачи распределения ресурсов необходимо принять такое решение, которое обеспечит достижение желаемой цели, но с ограничениями по затрачиваемым ресурсам. Данным задачам характерно большое количество решений. Частное решение таких задач зависит от целевых установок, а решение, удовлятворяющее заданным условиям и соответствующее целевым установкам, называется оптимальным планом. Сами задачи называются оптимизационными.
Ярким примером таких задач является проблема распределения предпринимателем денежных средств между закупаемыми ресурсами. Предпринимателю необходимо так распределить денежные средства, чтобы с минимальными затратами получить максимальную прибыль. Условием этого примера является ограниченность у предпринимателя имеющихся денежных ресурсов, а целевым решением - максимальная прибыль.
Еще одним примером является статья «Стоимость пропитания», которую написал Стиглер в 1945 году. В статье рассматривается дешевая система пропитания, которого долно хватить для удовлетворения заданных минимальных норм [1]. Стиглер рассмотрел 27 вариантов пищи и нашел самую дешевую их комбинацию.
Нельзя не отметить вклад в теорию оптимизационных задач советским математиком Л.В. Канторовичем. Еще в 1930-е годы он помог экономистам с задачей раскроя материалов. За его вклад в исследование оптимизационных задач он стал лауреатом Нобелевской премии по экономике.
Внимание к задачам наилучшего выбора всегда высоко, но в последние годы оно особенно возросло в связи с интенсивным развитием науки и техники. Стало неизбежным нахождение научного подхода, базирующегося на математическом моделировании.
Джагадишем и Хартунгом в работах [2, 3] обсуждались проблемы, связанные с генерированием и обработкой больших данных. Интенсивное развитие математических моделей привело к появляению такого раздела науки как большие и сверхбольшие задачи линейного программирования. Чангом в работе [4] обсуждается применение сверхбольших задач линейного программирования в бизнесс-аналитике, а также проблемы таких задач, методы их решения и их дальнейшее развитие. Сверхбольшие задачи линейного программирования имеют место быть и в такой науке как квантовая физика. В работе [5] авторами Годзио, Груца и Джулианом Холлом обсуждаются модели задач линейного программирования для квантовой корреляции, сравниваются результаты применения симплекс-метода, а также предлагается безматричный метод внутренних точек. Перечислены преимущества предлагаемого метода и его возможные улучшения. Содхи в работе [6] рассматривал существующие статические модели сверхбольших задач линейного программирования для применения в управлении активами и пассивами. Также задачи линейного программирования применяются в ценообразовании, исследованию которого посвящена работа [7] авторов Брогаарда, Хендершотта и Риордана. Типи в своей работе [8] описывает возможные случаи возникновения сверхбольших задач линейного программирования, их сложность и проблемы решения.
Целью поставленной выпускной квалификационной работы является исследование итерационного апекс-метода для решения задач линейной оптимизации.
Для достижения поставленной цели, необходимо решить следующие поставленные задачи:
1. Проанализировать итерационный апекс-метод.
2. Спроектировать экспериментальную задачу для ее решения итерационным апекс-методом.
3. Реализовать итерационный апекс-метод на языке программирования Python.
4. Применить итерационный апекс-метод для решения экспериментальной задачи.
5. Исследовать результаты применения итерационного апекс-метода при различных значениях параметров алгоритма.
6. На основании полученных результатов сделать вывод о влиянии параметров алгоритма на время решения экспериментальной задачи.
7. Применить реализованный итерационный апекс-метод на реальной задаче, сравнить с ее точным решением и сделать соответствующий вывод
Купить