ВВЕДЕНИЕ 4
1 ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 6
1.1 Основные понятия 6
1.2 Методы линейного программирования 7
1.2.1 Графический способ 8
1.2.2 Симплекс-метод 9
2 ТЕОРИЯ ДИСКРИМИНАНТНОГО АНАЛИЗА 11
2.1 Основные понятия 11
2.2 Методы дискриминантного анализа 11
2.2.1 Методы линейной коррекции 13
2.2.2 Методы фейеровских отображений 14
3 АЛГОРИТМ РЕШЕНИЯ ЗЛП С НЕФОРМАЛИЗОВАННЫМ ОГРАНИЧЕНИЕМ .. 16
4 РЕАЛИЗАЦИЯ АЛГОРИТМА РЕШЕНИЯ ЗЛП С
НЕФОРМАЛИЗОВАННЫМ ОГРАНИЧЕНИЕМ НА БАЗЕ КЛИЕНТСЕРВЕРНОГО ПРИЛОЖЕНИЯ 19
4.1 Формирование начального набора образцов 19
4.2 Выбор критерия завершения работы алгоритма 19
4.3 Выбор метода формирования разделяющей функции 20
4.4 Выбор метода решения аппроксимационной ЗЛП 20
4.5 Выбор среды разработки 20
4.6 Реализация алгоритма на базе приложения 20
5 ИССЛЕДОВАНИЕ РАБОТЫ АЛГОРИТМА 24
5.1 Анализ выбора £ в зависимости от размерности задачи 25
5.2 Влияние радиуса рандомизации на эффективность алгоритма 26
5.3 Влияние мощности рандомизации на эффективность алгоритма 37
ЗАКЛЮЧЕНИЕ 48
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 49
ПРИЛОЖЕНИЕ А 52
ПРИЛОЖЕНИЕ Б 55
ПРИЛОЖЕНИЕ В 57
ПРИЛОЖЕНИЕ Г 61
ПРИЛОЖЕНИЕ Д
В практике экономико-математического моделирования часто возникают задачи линейного программирования с ограничениями, не поддающимися полной формализации.
Как правило задачи такого типа появляются в технологическом процессе, параметры которого невозможно измерить напрямую в силу каких-либо обстоятельств.
Единственным критерием, определяющим качество значений параметров в данном случае, может быть решение некоторого эксперта, основанное на каких- либо эмпирических данных, в качестве которого может выступать человек, нейронная сеть или экспертная система.
Для решения задач подобного рода может использоваться универсальный алгоритм, представляющий собой некоторый сплав методов из различных областей математического программирования. Одним из таких алгоритмов является алгоритм решения задачи линейного программирования в условиях неполных данных.
Поэтому, целью данной работы является обзор и реализация алгоритма решения задачи линейного программирования в условиях неполных данных. Для достижения данной цели необходимо решить следующие задачи:
1) изучить методы решения задач линейного программирования;
2) изучить методы решения задач с неформализованными ограничениями;
3) изучить общие принципы и методы теории распознавания образов;
4) изучить методы решения задач дискриминантного анализа.
Задачи линейного программирования с неформализованными ограничениями имеют непосредственное отношение к задачам различных сфер жизни общества. Это могут быть, например, задачи из сферы черной металлургии, задачи о портфеле ценных бумаг и т.п.
В рамках выполнения выпускной квалификационной работы был исследован алгоритм решения задачи линейного программирования в условиях неполных данных.
В основе работы лежит анализ теоретических достижений науки в области решения задач линейного программирования и дискриминантного анализа, на базе которых и построен алгоритм.
После обзора предметной области были описаны непосредственно этапы алгоритма, а также представлена его программная реализация на базе клиентсерверного приложения на стеке технологий Vue.js (реализация клиентской части) и Node.js (реализация серверной части). Кроме того, был проведен ряд вычислительных экспериментов на предмет установления влияния параметров алгоритма на его быстродействие.
Направление дальнейших исследований может быть связано с оптимизацией кодовой базы и расширением функциональности как клиентской части приложения (добавление графической интерпретации решения), так и серверной (добавление новых эмуляторов модели эксперта).
