Программный комплекс решения задачи многокритериального линейного программирования

• Введение
• 1. Решение задач линейного программирования со скалярным и векторным критериями
• 1.1 Оптимизационная задача линейного программирования. Виды задач линейного программирования
• 1.2 Существование решения основной ЗЛП и способы его нахождения
• 1.3 Решение задач линейного программирования симплекс-методом
• 1.4 Принятие решений на основе количественной информации об относительной важности критериев
• 1.4.1 Выбор решений
• 1.4.2 Векторный критерий и отношение предпочтения
• 1.4.3 Множество Парето
• 1.5 Многокритериальный симплекс метод
• 1.6 Постановка задачи
• 2. Программный комплекс линейной векторной оптимизации (ЛВО)
• 2.1 Проектирование архитектуры ПК ЛВО
• 2.2 Проектирование интерфейса ПК ЛВО
• 2.3 Проектирование функционирования ПК ЛВО
• 2.4 Выбор средств разработки
• 2.5 Программная реализация ПК ЛВО
• 2.5.1 Исходные данные
• 2.5.2 Этапы решения МЛП
• 2.5.3 Системные требования
• 2.5.4 Требования к настройке ОС
• 3. Решение численного примера
• 4. Экономическая часть
• 4.1 Введение в экономическую часть
• 4.2 Расчет трудоемкости проекта
• 4.3 Определение затрат на заработную плату
• 4.4 Определение материальных расходов.
• 4.5 Определение накладных расходов
• 4.6 Определение себестоимости проекта
• 5. Безопасность и экологичность проекта
• 5.1 Требования к помещениям для работы с ПЭВМ
• 5.2 Требования к организации рабочих мест пользователей ПЭВМ
• 5.3 Требования к микроклимату на рабочих местах
• 5.4 Требования к уровням шума и вибрации на рабочих местах
• 5.5 Требования к освещению на рабочих местах
• 5.6 Основные способы защиты от вредного воздействия
• 5.7 Защитные фильтры
• 5.8 Пожарная безопасность
• 5.9 Обеспечение электробезопасности
• Заключение
• Список литературы
• Приложение А
• Приложение Б
• Приложение В
• Введение

Известно, что многие объекты социально-экономического и технического характера при их формализации с целью моделирования функционирования допускают применение оптимизационных методов. При этом широкий класс таких методов укладывается в рамки линейно-программных задач. Такие задачи на формальном уровне состоят в минимизации линейной целевой функции от набора аргументов на множестве их допустимых значений, задаваемым линейными ограничениями. Весьма часто цель функционирования объекта неисчерпывается одним критерием, а представляет собой набор таких критериев или, выражаясь строго, целевая функция является уже не скалярной величиной, а вектором. Другими словами классическая задача линейного программирования (ЛП) преобразуется в задачу многокритериального линейного программирования (МЛП).

В рамках теории принятия решений разработан конструктивный аппарат решения задач такого рода. Настоящая дипломная работа посвящена разработки программного обеспечения процесса решения задач МЛП, основанного на некоторых известных методах.

1. Решение задач линейного программирования со скалярным и векторным критериями

1.1 Оптимизационная задача линейного программирования. Виды задач линейного программирования В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности.

Оптимизация — целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев — невозможно.

В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот — любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т. д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.

Наиболее часто используемым методом оптимизации является линейное программирование. Линейное программирование — один из первых и наиболее подробно изученных разделов математического программирования. К числу задач линейного программирования можно отнести задачи:

— рационального использования сырья и материалов;

— задачи оптимизации раскроя;

— оптимизации производственной программы предприятий;

— оптимального размещения и концентрации производства;

— составления оптимального плана перевозок, работы транспорта;

— управления производственными запасами;

— и многие другие, принадлежащие сфере оптимального планирования.

Задачами ЛП называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств[2].

Согласно определению, задача ЛП может быть записана в виде где величины являются элементами некоторого подполя F поля вещественных чисел R. Такая форма задачи ЛП называется общей.

Задача ЛП вида называется канонической, а задача ЛП вида называется стандартной (нормальной).

При этом также требуется (хотя это и некритично), чтобы правые части равенств были неотрицательны, т. е. должны соблюдаться условия

().

Пусть — матрица с элементами , — вектор-столбец, а — вектор-строка. Каноническую и стандартную формы задачи ЛП можно записать в матричном виде как соответственно

и Для реализации какого-либо метода решения задачи ЛП обычно бывает необходимо перейти от стандартной формы к канонической. Это достигается путем добавления в каждое неравенство вида переменной. Таким образом,

.

Для перехода от максимума целевой функции к минимуму используется

1.2 Существование решения основной ЗЛП и способы его нахождения

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям — равенствам

(1)

и обращающие в максимум линейную функцию этих переменных

(2)

Для простоты предположим, что все условия (1) линейно независимы (r=m), и будем вести рассуждения в этом предположении.

Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений x1, x2, …, xn, удовлетворяющую условиям (1).Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение.

Всегда ли эта задача имеет решение? Нет, не всегда.

ЗЛП неразрешима (не имеет оптимального решения):

Из-за несовместности системы ограничений. Т. е. система не имеет ни одного решения, как показано на рисунке 1.

Рисунок 1 — Несовместность системы ограничений Из-за неограниченности целевой функции на множестве решений. Другими словами при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min — к минус бесконечности, как показано на рисунке 2.

Рисунок 2 — Неограниченность целевой функции на множестве решений ЗЛП разрешима:

Множество решений состоит из одной точки. Она же и является оптимальной, как показано на рисунке 3.

Рисунок 3 — Множество решений состоит из одной точки Единственное оптимальное решение ЗЛП. Прямая, соответствующая целевой функции в предельном положений пересекается с множеством решений в одной точке, как показано на рисунке 4.

Рисунок 4 — Единственное оптимальное решение Оптимальное решение ЗЛП не единственно. Вектор N перпендикулярен к одной из сторон множества решений. В этом случае оптимальной является любая точка на отрезке АВ, как показано на рисунке 5[2].

Рисунок 5 — Оптимальное решение не единственно

1.3 Решение задач линейного программирования симплекс-методом

Симплекс-метод — алгоритм решения задачи ЛП, реализующий перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции С. Симплекс-метод является основным в линейном программировании.

Использование этого метода в дипломном проекте для решения задачи ЛП обусловлено следующими факторами:

— метод является универсальным, применимым к любой задаче линейного программирования в канонической форме;

— алгоритмический характер метода позволяет успешно программировать и реализовать его с помощью технических средств.

Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т. е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если «да», то задача решена. Если «нет», то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции .

Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

Система ограничений здесь — система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен, то возможно выбрать неизвестных, которые выражают через остальные неизвестные. Для определенности обычно полагают, что выбраны первые, идущие подряд, неизвестные. Эти неизвестные (переменные) называются базисными, остальные свободными. Количество базисных переменных всегда равно количеству ограничений.

Присваивая определенные значения свободным переменным, и вычисляя значения базисных (выраженных через свободные), получают различные решения системы ограничений. Особый интерес представляют решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Оно соответствует всем ограничениям.

Имея систему ограничений, находят любое базисное решение этой системы. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому допустимому базисному решению.

Симплексный метод гарантирует, что при этом новом решении линейная форма если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным.

Если первое найденное базисное решение окажется недопустимым, то с помощью симплексного метода осуществляется переход к другим базисным решениям, пока на каком-то шаге решения базисное решение окажется допустимым, либо можно сделать вывод о противоречивости системы ограничений[3].

Таким образом, применение симплексного метода распадается на два этапа:

— нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;

— нахождение оптимального решения в случае совместности системы ограничений.

Алгоритм перехода к следующему допустимому решению следующий:

— в строке коэффициентов целевой функции выбирается наименьшее отрицательное число при отыскании максимума. Порядковый номер коэффициента —. Если такового нет, то исходное базисное решение является оптимальным;

— среди элементов матрицы с номером столбца (этот столбец называется ведущим, или разрешающим) выбираются положительные элементы. Если таковых нет, то целевая функция неограничена на области допустимых значений переменных и задача решений не имеет;

— среди выбранных элементов ведущего столбца матрицы выбирается тот, для которого величина отношения соответствующего свободного члена к этому элементу минимальна. Этот элемент называется ведущим, а строка, в которой он находится — ведущей;

— базисная переменная, отвечающая строке ведущего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу ведущего элемента, вводится в число базисных. Строится новое решение, содержащее новые номера базисных переменных.

Условие оптимальности плана при решении задачи на максимум: среди коэффициентов целевой функции нет отрицательных элементов.

1.4 Принятие решений на основе количественной информации об относительной важности критериев

1.4.1 Выбор решений Человек в своей деятельности постоянно сталкивается с ситуациями, в которых ему приходится осуществлять выбор. Руководители различных уровней и рангов постоянно вынуждены заниматься формированием персонала, возглавляемых ими подразделений, выбирать ту или иную стратегическую линию поведения, принимать конкретные хозяйственные и экономические решения. Работники банков выбирают объекты для инвестирования, экономисты предприятий и фирм планируют оптимальную экономическую программу и т. д. и т. п.

Приведенный список практических задач выбора можно было бы продолжать и дальше. Ограничимся сказанным и выявим общие элементы, присущие всякой задаче выбора.

Прежде всего, должен быть задан набор решений, из которого следует осуществлять выбор. Обозначим его и будем называть множеством возможных решений. Природа самих решений при этом не играет никакой роли. Это могут быть проектные решения, варианты поведения, политические или экономические стратегии и т. д.

Собственно выбор (или принятие) решений состоит в указании среди всех возможных такого решения, которое объявляется выбранным (наилучшим, или оптимальным), хотя в некоторых случаях происходит выбор не одного, а целого набора решений, являющегося определенным подмножеством множества возможных решений .

Обозначим множество оптимальных (выбранных) решений. Оно и представляет собой решение задачи выбора. Решить задачу выбора — означает найти множество, являющееся определенным подмножеством множества возможных решений. В частности, может быть и одноэлементным множеством.

Процесс выбора невозможен без наличия того, кто осуществляет этот выбор, преследуя свои собственные цели. Человека (или целый коллектив, подчиненный достижению определенной цели), который производит выбор и несет полную ответственность по его последствия, называют лицом, принимающим решение (ЛПР)[5].

линейный программирование векторный оптимизация

1.4.2 Векторный критерий и отношение предпочтения

Нижеследующее рассмотрение посвящено ситуации, когда имеется несколько числовых функций, , определенных на множестве. В зависимости от содержания задачи выбора эти функции называют критериями оптимальности, критериями эффективности, целевыми функциями, показателями или критериями качества.

Проиллюстрируем введенные термины, рассмотрев задачу выбора наилучшего проектного решения. В этой задаче множество состоит из нескольких конкурсных проектов (например, строительства нового предприятия), а критериями оптимальности могут служить стоимость реализации проекта и величина прибыли, которую обеспечит данное проектное решение (т.е. построенное предприятие). Если ограничить рассмотрение данной задачи лишь одним критерием оптимальности, практическая значимость решения такой задачи окажется незначительной. В самом деле, при использовании только первого критерия будет выбран самый дешевый проект, но его реализация может привести к недопустимо малой прибыли. С другой стороны, на строительство самого прибыльного проекта, выбранного на основе второго критерия оптимальности, может просто не хватить имеющихся средств. Поэтому в данной задаче необходимо учитывать оба указанных критерия одновременно. Если же дополнительно стараться минимизировать нежелательные экологические последствия строительства и функционирования предприятия, то к двум указанным следует добавить еще один — третий критерий и т. д. Что касается ЛПР, осуществляющего выбор проекта, то в данной задаче таковым является глава администрации района, на территории которого будет построено предприятие, при условии, что это предприятие является государственным. Если же предприятие — частное, то в качестве ЛПР выступает глава соответствующей фирмы.

Указанные выше числовые функции образуют векторный критерий

(3)

который принимает значения в l-мерном арифметическом пространстве. Это пространство называют критериальным пространством или пространством оценок, а всякое значение векторного критерия при определенном именуют векторной оценкой возможного решения.

Задачу выбора, содержащую множество возможных решений и векторный критерий, обычно называют многокритериальной задачей.

Формальная постановка задачи МЛП имеет вид

(4)

(5)

Здесь, в отличие от обычной задачи ЛП, С — матрица размерности, а не вектор. А — матрица ограничений размерности. Таким образом, многокритериальная задача (4), (5) предполагает максимизацию на многограннике не одного линейного критерия, как в обычной задаче (ЛП), а l критериев одновременно.

1.4.3 Множество Парето

Вернемся к задаче многокритериального выбора. В ней кроме множества возможных решений и отношения предпочтения присутствует также векторный критерий. Компонента векторного критерия характеризует определенную цель ЛПР, а стремление достичь этой цели в математических терминах выражается в максимизации или минимизации этой компоненты на множестве. Для определенности всюду далее будем считать, что ЛПР заинтересовано в получении по возможности бульших значений каждой компоненты векторного критерия.

Выбрав произвольное возможное решение и вычислив значение векторного критерия на этом решении, получим набор чисел, образующий векторную оценку данного решения. Таким образом, каждое возможное решение имеет свою собственную векторную оценку.

Теперь рассмотрим два произвольных возможных решения и вместе с соответствующими им оценками и. Допустим, что эти оценки связаны соотношением

(6)

которое означает справедливость покомпонентных неравенств для всех номеров, причем, т. е. хотя бы для одного номера верно строгое неравенство .

Выполнение неравенства (6) означает, что по всем компонентам первая векторная оценка «не хуже» (точнее говоря, не меньше) второй векторной оценки, причем, по крайней мере, какая-та одна компонента первой оценки «лучше» (строго больше) соответствующей компоненты второй оценки. Поскольку, как принято выше, ЛПР заинтересовано в достижении максимального возможного значения по каждому критерию, то в имеющейся ситуации ЛПР из двух представленных ему на выбор решений и явно выберет первое.

Иначе говоря, стремление ЛПР максимизировать каждую компоненту векторного критерия можно выразить в терминах следующего требования: отношение предпочтения и векторный критерий подчиняются аксиоме Парето, т. е. всякий раз из выполнения неравенства (6) следует справедливость соотношения :

. (7)

Если для некоторой пары возможных решений выполняется неравенство (6), то благодаря аксиоме Парето первое решение будет предпочтительнее второго. Значит, второе решение ни при каких обстоятельствах не окажется оптимальным и его можно исключить из последующего процесса выбора. Исключение всех подобного рода решений приводит к множеству Парето.

Множество парето-оптимальных решений обозначается через. Решение называется паретовским (недоминируемым, неулучшаемым), если его нельзя улучшить по какому-то одному критерию, не ухудшив значение хотя бы одного из оставшихся.

Или, формально,

где — i-ая строка (i-ый критерий) матрицы .

Установим теперь взаимосвязь между недоминируемыми и парето-оптимальными решениями. Если решение не является парето-оптимальным, то для некоторого возможного решения выполнено неравенство (6). Согласно аксиоме Парето отсюда следует, что, а значит, — доминируемое решение. Таким образом, всякое решение, не являющееся парето-оптимальным, — доминируемое. Отсюда следует, любое недоминируемое решение должно быть парето-оптимальным.

В результате формализации конкретных практических задач выбора становятся известными множество возможных решений и векторный критерий. Знание векторного критерия и множества возможных решений позволяет найти множество Парето (решений и/или оценок). Построение множества Парето нередко считают первым необходимым шагом в решении любой многокритериальной задачи.

Из рассмотрения простых примеров следует, что множество парето-оптимальных решений в одном крайнем случае может состоять из одного-единственного элемента, а в другом — каждое возможное решение будет парето-оптимальным. Если парето-оптимальное решение единственно, то в такой задаче оптимальным может быть только это парето-оптимальное решение. Однако, практика показывает, что в реальных задачах множество Парето оказывается достаточно широким и его построение полностью не решает задачу принятия решений. Необходимы методы, которые позволили бы сузить область дальнейшего поиска оптимальных решений. Именно такого рода метод разработан в рамках теории относительной важности критериев.

1.5 Многокритериальный симплекс метод

Как правило, традиционного решения задача МЛП (4), (5) не существует, то есть отсутствует точка такая, что для всех. В случае, когда у ЛПР, отсутствует какая-либо априорная информация относительно сравнительной важности критериев, под решением задачи (4), (5) будем понимать множество Парето[7].

Проблеме построения множества Парето в задаче МЛП посвящена обширная литература. Вместе с тем, одной из лучших (если не лучшей) публикацией на эту тему является, по-видимому, статья американских математиков P. L. Yu и M. Zeleny. Именно здесь приведены хорошо теоретически обоснованные методы построения множества паретовских вершин и всего множества Парето.

Для построения множества представлен так называемый многокритериальный симплекс-метод. Он основан на двух основных теоремах, формулировки которых мы приведем здесь без доказательства.

Теорема 1 ([8]). Множество связно.

Теорема 2 ([8]). .

Здесь, а — решение задачи ЛП

(8)

(9)

Суть алгоритма построения множества состоит в следующем. Сначала ищется первая паретовская вершина. Для этого достаточно решить задачу ЛП с целевой функцией

(10)

После этого на паретовость путем решения задачи по формулам (8), (9) проверяются все соседние к точки. Те из них, которые окажутся паретовскими, включаются в, проверке подвергаются соседние к ним и т. д.

Наряду с многокритериальным симплекс-методом в показано, что для любой точки существует набор чисел, такой, что

(11)

Это означает, что множество можно построить, перебирая узлы l — мернойсети на множестве

(12)

и решая для каждого узла задачу ЛП по формуле (11).

Далее в показывается, как на основе можно построить множество. При этом будет представлять собой объединение паретовских выпуклых комбинаций (граней многогранника) точек из .

Заметим, что со всем множеством Парето работать трудно, поскольку оно содержит бесконечное число возможных «равноправных» решений, ЛПР же, как правило, для реализации требуется какое-то одно решение. В то же время вся объективная информация уже использована, как будто бы, при построении множеств и .

Казалось бы, выходом из этой ситуации может быть решение задачи ЛП по формуле (11) с равными весовыми коэффициентами

. (13)

Это, однако, не так по двум причинам. Во-первых, такой способ предполагает одинаковую важность для ЛПР всех критериев, что сужает постановку исходной задачи. И, во-вторых, такое решение непременно «выведет» на какую-нибудь точку из (то есть на вершину), игнорируя, по существу, множество / .

Способ, позволяющий ЛПР выделить для реализации лишь одну точку из и не требующих дополнительных соображений субъективного характера, может состоять в следующем.

Прежде всего, заметим, что каждое паретовское решение равноправно по отношению к другим паретовским решениям (не лучше, но и не хуже них). Следовательно, при выделении единственной точки из (то есть при точечной характеризации) для реализации должно быть учтено (пусть и неявно) все множество .

Отметим далее, что такая характеризация — обозначим ее через — должна отражать конфигурацию множества, в значительной мере задаваемую множеством .

Основанная на учете этих двух соображений идея поиска решения состоит в следующем. Необходимо, считая каждую точку из равноправной по отношению к другим, найти выпуклую комбинацию всех точек из с равными весами. Обозначим её через *

(14)

где p — число элементов (мощность) множества .

Ясно, что в общем случае точка не является паретовской. Поэтому естественно в множестве выделить точку (ранее обозначенную через), в максимальной степени «улучшающую» по всем критериям.

Таким образом, предложенный алгоритм, сводит решение многокритериальной задачи управления к последовательности решения скалярных задач оптимизации, для которых разработаны надежные численные методы решения.

1.6 Постановка задачи

В рамках дипломного проекта необходимо разработать программный комплекс решения задачи многокритериального линейного программирования. Данный программный комплекс предназначен для автоматизации процесса решения линейной задачи векторной оптимизации.

Основные возможности программного комплекса:

— построение множества Парето;

— определение компромиссного решения для ЛПР;

— определение образа окончательного решения задачи;

— формирование отчёта о результатах решения задачи многокритериального линейного программирования в Microsoft Word.

Программа должна допускать использование не более 5 неравенств в матрице ограничений. Так как для задачи с количеством уравнений более 5, расчетное время становится слишком большим, то было принято решение в текущем варианте продукта ограничить функциональность продукта расчетом только до 5 уравнений.

Кроме этого должна быть возможность выбора шага разбиения lмерной сетки.

2. Программный комплекс линейной векторной оптимизации (ЛВО)

Для разработки ПК ЛВО необходимо выполнение следующих этапов:

— проектирование архитектуры ПК ЛВО;

— проектирование функционирования ПК ЛВО;

— проектирование интерфейса ПК ЛВО;

— выбор средств разработки;

— программная разработка ПК ЛВО.

2.1 Проектирование архитектуры ПК ЛВО

В первую очередь необходимо определиться с архитектурой программного комплекса. Существует множество определений понятия «архитектура». Наиболее полно суть данного понятия отражает определение из стандарта IEEE 1471 «Рекомендуемые методы описания архитектуры преимущественно-программных систем IEEE».

Архитектура — это базовая организация системы, воплощенная в ее компонентах, их отношениях между собой и с окружением, а также принципы, определяющие проектирование и развитие системы.

При проектировании ПК ЛВО оптимальным является выбор одноуровневой архитектуры, основное преимущество которой заключается в простоте.

Для расчетов симплекс метода будет использоваться стороннее приложение, которое в рамках данной архитектуры будет называться consoleprogram. Программа является консольным приложением, входные данные для программы передаются из текстового файла input.txt. Выходные данные передаются через текстовый файл output.txt. Выходные данные стороннего приложения будут использоваться в дальнейших расчетах при решении задачи МЛП.

На рисунке 6 показана общая физическая структура программного комплекса на уровне файловой системы, которая является своего рода обобщением разработанной архитектуры.

Рисунок 6 — Общая физическая структура программного

комплекса на уровне файлов Расшифровка обозначений рисунка:

1) PK_LVO.exe — главный запускающий файл программного комплекса;

2) Consoleprogram. exeфайл программы для реализации простого симплекс-метода;

3) Primer. txt — текстовый файл с исходными данными;

4) Input. txt — файл с исходными данными, который используется для программы Consoleprogram. exe;

5) Output. txt — файл с выходными данными программы Consoleprogram.exe.

В состав программного комплекса будут входить четыре блока-модуля программного обеспечения.

Рассмотрим каждый блок — модуль в отдельности:

А) Блок «Исходные данные» состоит из двух модулей:

— чтение матрицы из файла пользователя — модуль необходим для считывания матрицы ограничений A — размерности [mЧn], целевой матрицы С — размерности [lЧn] и вектора В из текстового файла с расширением .txt. Данный модуль позволяет загружать данные из файла пользователя, что облегчает работу пользователя с программой и освобождает его от необходимости повторно вводить одни и те же исходные данные;

— чтение и запись в файл — данный модуль необходим для правильного формирования данных в файл input. txt, используемый приложением consoleprogramm.exe. и считывания данных из выходного файла программы — output. txt .Данное консольное приложение решает задачу линейного программирования простым симплекс-методом при одном заданном ограничении.

Б) Блок «Поиск Паретовских вершин» — предназначен для построения множества Парето с помощью многокритериального симплекс-метода. Он состоит из двух модулей:

— модуль перебора l-мерной решетки — предназначен для перебора узлов l-мерной решетки в зависимости от шага разбиения решетки, который задается пользователем;

— модуль запуска внешней программы — модуль, который позволяет запускать на выполнение программу consoleprogramm. exe c переданными ей значениями целевой матрицы.

В) Блок «Поиск компромиссного решения» — предназначен для определения оптимального решения ЗЛП с несколькими критериями.

Г) Блок «Результаты» — состоит из двух модулей:

— расчет и выдача результата — определение окончательного образа компромиссного решения и выдача результата на экран пользователю;

— модуль создания отчета в Word — данный модуль позволяет создать отчет в текстовом редакторе Microsoft Word. Отчет будет содержать исходные данные и полученный результат.

На рисунке 7 представлена общая структурная схема программного комплекса линейной векторной оптимизации.

Рисунок 7- Структурная схема ПК ЛВО На рисунке 8 показана функциональная диаграмма нотации IDEF0, описывающая основные процессы, протекающие в ПК ЛВО. В приложении, А приведены диаграммы и их взаимосвязи, показана структура модели ПК ЛВО. Каждый компонент модели декомпозирован на другой диаграмме. Каждая диаграмма иллюстрирует «внутреннее строение» блока на родительской диаграмме.

Рисунок 8 — Функциональная диаграмма ПК ЛВО На рисунке 9 показано дерево диаграмм ПК ЛВО.

Рисунок 9 — Дерево диаграмм ПК ЛВО

2.2 Проектирование интерфейса ПК ЛВО

Целью всего процесса разработки пользовательского интерфейса является эффективный выбор и размещение визуальных элементов управления, целостность интерфейса (в пределах одного диалогового окна должны быть только те элементы управления, которые относятся именно к его главному предназначению, и не должно быть лишних элементов) и его интуитивная понятность. Понятие архитектуры пользовательского интерфейса относится к общей структуре интерфейса, а не к мелким его деталям.

Проектирование архитектуры интерфейса ПК ЛВО было реализовано с использованием графических редактора Microsoft Office Visio. В первую очередь было уделено внимание только ключевым интерфейсам ПК.

ПК ЛВО должен обладать простым, удобным, легко осваиваемым интерфейсом, который должен предоставить конечному пользователю все необходимые для его работы функции, но в то же время не дать ему возможности выполнять какие-либо лишние действия.

Для удобства пользователя в ПК ЛВО должна быть возможность загрузить данные из файла. Исходные данные должны отображаться на главной форме слева направо в соответствующем порядке: матрица ограничений А, вектор В и целевая матрица С.

Для выбора условия решения задачи пользователю должна предоставлена возможность выбрать максимум или минимум, а также указать знак неравенства между матрицей ограничения, А и вектором В. Кроме этого, необходимо создать поле для ввода шага разбиения сетки.

Для вывода и просмотра результата будет создано специальное поле, которое можно будет очистить при необходимости. Функции очистки значений матриц, формирование отчета удобнее всего занести в меню ПК ЛВО. Кроме этого, в меню ПК ЛВО будет возможность задать размеры матриц через настройки, и ввести исходные значения на главной форме. Ввод данных будет осуществляться с помощью двойного нажатия левой кнопки мыши по соответствующей ячейки.

В зависимости от исходных данных процесс решения задачи может занять некоторое время. Для удобства необходимо создать компонент для отображения хода процесса.

ЛПР после ввода исходных данных запускает задачу на поиск паретовских вершин. После создания множества Парето должна быть реализована возможность поиска компромиссного решения для ЛПР, и при необходимости возможность пропустить этот шаг.

Таким образом, на рисунке 10 представлен макет интерфейса ПК ЛВО.

Рисунок 10 — Макет интерфейса ПК ЛВО

2.3 Проектирование функционирования ПК ЛВО

Алгоритм функционирования программы должен обеспечивать ввод исходных данных и преобразование их к стандартной форме записи ЗЛП. Поиск паретовских вершин и создание множества Парето будет реализовано после ввода всех исходных данных. После поиска паретовских вершин в программе должен быть реализован выбор для ЛПР, который определят искать компромиссное решение или закончить вычисления. Если ЛПР не требуется определить компромиссное решение, программа выводит на экран найденное множество Парето. Если ЛПР требуется найти компромиссное решение, то программа производит вычисления и выводит на экран полученный результат.

Поиск паретовских вершин в программе реализуется по следующим шагам:

— построение множества паретовских вершин, перебором узлов l-мерной сети на множестве (12);

— запуск внешней программы consoleprogram. exe и решение ЗЛП для каждого узла решетки;

— удаление одинаковых точек во множестве паретовских вершин.

На рисунке 11 представлен алгоритм перебора l — мерной сети.

Алгоритм поиска компромиссного решения состоит из следующих шагов:

— нахождение выпуклой комбинации всех точек из с равными весами по формуле (14);

— вызов программы consoleprogram. exe и решение задачи ЛП с данными, найденной выпуклой комбинации точек;

— вычисление образа окончательного решения задачи .

Так как в программе мы приняли количество строк в целевой матрице не превышать 5, алгоритм перебора lмерной сети должен обеспечивать перебор сетки по 5- мерному пространству. Алгоритм перебора lмерной сети представлен на рисунке 11. Фрагмент реализации перебора lмерной сети представлении в приложении В.

Алгоритм функционирования программного комплекса представлен на рисунке 12.

Рисунок 11- Алгоритм перебора lмерной сети Рисунок 12 — Алгоритм функционирования программного комплекса

2.4 Выбор средств разработки

Программный комплекс рассчитан для работы с большими объемами информации и применения в однопользовательском режиме.

Для организации удобного для пользователя способа общения с программой предназначена интерфейсная часть, включающая блоки ввода информации и интерпретации результатов. Она должна иметь удобный и понятный интерфейс, поэтому для его реализации с учетом приведенных характеристик разрабатываемого программного комплекса остановимся на среде визуального моделирования Delphi. Это позволит создать стандартный Windows-интерфейс для программы, максимально удобный и понятный для пользователя, обеспечит ввод и вывод информации в удобном для чтения виде. Использование именно этого инструмента позволит существенно сократить объем программы и упростить процесс передачи параметров, при сохранении хорошего качества и надежности программного продукта. Delphi — надежный инструмент разработки, качество которого доказано множеством реализованных и внедренных программных продуктов промышленного масштаба.

2.5 Программная реализация ПК ЛВО

2.5.1 Исходные данные Для того чтобы начать работать с программным комплексом пользователю необходимо ввести исходные данные. Это можно сделать двумя способами:

— выбрать файл с исходными данными;

— ввести значения данных с помощью настроек программы.

Рассмотрим первый вариант. Файл с исходными данными представляет собой обычный текстовый файл с расширением *.txt, содержащий матрицы значений исследуемой задачи, количество строк и столбцов матриц. Значения могут быть как положительными, так и отрицательными, как целыми, так и вещественными. Требования, предъявляемые к файлу:

— файл не должен содержать никаких данных, кроме значений числового формата;

— в первых двух строчках вводятся количество строк и количество столбцов матрицы ограничений, далее вводится значения матрицы. Аналогично происходит ввод целевой матрицы и вектора b, в соответствующем порядке;

— для вещественных чисел целая часть отделяется от дробной точкой.

Во многих приложениях элементы пользовательского интерфейса обладают разным функциональным значением. Элементы в ПК ЛВО расположены так, чтобы более важные были заметны пользователю в первую очередь, а менее важные — потом. Таким образом, в левом верхнем углу программы, куда взгляд пользователя упирается в первую очередь, с помощью компонента MainMenu среды разработки Delphi, реализовано главное меню программы.

Чтобы выбрать файл с исходными данными, необходимо в главном меню нажать кнопку «Файл» и из появившегося списка выбрать пункт «Открыть» как показано на рисунке 13.

Рисунок 13 — Главное меню программы Для реализации диалога «Открыть файл» при разработки использовался компонент для работы с файлами — OpenDialog[10].

Считывание из файла данных реализовано следующим образом:

— считываем из файла количество строк и столбцов матрицы ограничений А;

— в цикле считываем значения для матрицы ограничений А;

— считываем количество строк и столбцов в целевой матрице С;

— в цикле считываем значения целевой матрицы, затем считываем количество строк и столбцов вектора В;

— в цикле считываем значения для вектора В.

После нажатия на пункт меню «Открыть» откроется диалоговое окно рисунок 14, в котором используется фильтр «Тип файлов». Пользователь может выбирать только файлы *.txt.

Рисунок 14 — Диалоговое окно После выбора пользователем файла с исходными данными, значения файла будут отображаться на главной форме программного комплекса, как показано на рисунке 15.

Во втором случае пользователю предоставляется возможность ввести значения матриц с помощью настроек программы. Для этого необходимо в главном меню программы нажать кнопку «Настройки» и из появившегося списка выбрать пункт «Задать размер матриц» как показано на рисунке 16.

Рисунок 15 — Главное окно программы после загрузки данных Рисунок 16 — Пункт меню «Настройки»

Откроется окно программы — «Размерность матриц». В данном окне пользователю необходимо ввести размерность матрицы ограничений и целевой матрицы, как показано на рисунке 17.

Рисунок 17 — Окно программы «Размерность матриц»

При вводе данных необходимо учитывать следующие правила:

1) В поля формы можно вводить только целые, положительные значения числового формата.

2) Количество строк в матрице ограничений не может быть больше 5. При неправильном вводе данных программа выдаст сообщение об ошибке как показано на рисунке 18.

Рисунок 18 — Сообщение о неправильном вводе исходных данных После правильного заполнения полей размерности матриц, пользователю необходимо нажать кнопку «Применить», после чего откроется главное окно, в котором будут показаны матрицы необходимого размера. Пользователю остается ввести значения матриц исследуемого примера (рисунок 19).

Для удобства ввода исходных значений, которые представляют из себя массивы, при разработке использовался компонент StringGrid. Компонент представляет собой таблицу, ячейки которой содержат в себе строки символов.

Рисунок 19 — Главное окно программы перед вводом исходных данных пользователем Для того, чтобы очистить ячейки матрицы от значений, необходимо в пункте меню «Настройки» из выпадающего списка выбрать пункт «Очистить матрицы».

2.5.2 Этапы решения МЛП

После ввода исходных данных пользователю необходимо выбрать экстремум целевой функции: max или min.

Для этого в главном окне программы из выпадающего списка нужно выбрать соответствующее условие, как показано на рисунке 20.

Рисунок 20 — Выбор условия решения задачи

— Указать знак неравенства между матрицей ограничений и вектором B;

На рисунке 21 показан выбор знака неравенства.

Рисунок 21- Указание знака неравенства

— Ввести шаг разбиения lмерной решетки;

— Нажать кнопку «Поиск паретовских вершин» для запуска решения задачи.

После выполнения всех вышеперечисленных шагов программа начнет поиск паретовских вершин. Для этого потребуется некоторое время. Время решения задачи напрямую зависит от шага разбиения lмерной решетки. Чем меньше шаг, тем больше времени потребуется для решения задачи. Кроме этого скорость выполнения зависит от процессора ЭВМ.

Во время поиска паретовских вершин пользователь может наблюдать процент выполнения задачи. Для отображения хода процесса поиска в программе использован компонент Gaudge, как показано на рисунке 22.

Рисунок 22- Элемент для отображения хода процесса поиска вершин Когда поиск завершиться, программа выдаст сообщение: «Искать компромиссное решение?», как показано на рисунке 23.

Рисунок 23- Сообщение программы Если пользователю требуется найти компромиссное решение, следует нажать кнопку «ОК». После этого программа выдаст следующие данные:

— время выполнения;

— множество вершин Парето;

— компромиссное решение;

— образ компромиссного решения.

Если пользователю нет необходимости искать оптимальное решение, пользователь должен нажать кнопку «NO» и программа выведет следующие данные:

— время выполнения;

— множество вершин Парето.

На рисунке 24 показано главное окно программного комплекса после решения задачи.

Рисунок 24 — Главное окно программы после решения задачи МЛП Для формирования отчета служит пункт меню: «Файл" — «Сформировать отчет». Этот пункт становится активным только после решения задачи.

Отчет формируется в текстовом редакторе Microsoft Word и содержит в себе исходные данные и результаты решения.

2.5.3 Системные требования

Системные требования программы приведены в таблице 1.

Таблица 1 — Системные требования

2.5.4 Требования к настройке ОС

Перед установкой программы необходимо:

— отключить все антивирусные программы;

— в меню Пуск — Панель управления — Язык и региональные стандарты, во вкладке «Региональные параметры», в строке «Разделитель целой и дробной части» указать точку.

3. Решение численного примера

Рассмотрим классический пример многокритериальной задачи линейного программирования, который был описан в статье американских математиков P. L. Yu и M. Zeleny[7].

Исходные данные:

Матрица ограничений А:

Вектор B:

Целевая матрица С:

При решении этой задачи с помощью программного комплекса линейной векторной оптимизации множество составили 4 точки:

Образом множества в критериальном пространстве являются точки:

По формуле (14) выпуклая комбинацию точек из с равными весами:

.

Далее посредством решения задачи (8) на множестве точечная характеризация множества Парето :

.

Наконец, образом окончательного решения задачи будет точка :

Результаты показаны на рисунке 25.

Рисунок 25 — Результаты Формируемый отчёт приведён в приложении Б.

4. Экономическая часть

4.1 Введение в экономическую часть

Целью написания данного раздела является расчёт затрат на разработку и внедрение программного комплекса решения задачи многокритериального линейного программирования «ПК ЛВО». Программный комплекс осуществляет решение задачи МЗЛП и поиск компромиссного решения для ЛПР.

Себестоимость представляет собой стоимостную оценку использованных в процессе производства продукции (работ, услуг), средств и предметов труда, услуг других организации и оплату труда работников. В данном проекте установлено, что к затратам, включаемым себестоимость продукции относятся:

— затраты на выплату заработной платы исполнителям;

— отчисления с заработной платы;

— приобретение необходимых технических и программных средств;

— электроэнергия.

Расходы на выплату исполнителям заработной платы включают в себя: основную заработную плату, дополнительную заработную плату, отчисление с заработной платы в виде единого социального налога.

Основная заработная плата определяется исходя из количества разработчиков, времени выполнения разработки, а также заработной платы в расчете на один час. Исполнителем проекта является один инженер — программист.

4.2 Расчет трудоемкости проекта

Разработка программного обеспечения включает в себя следующие этапы:

— анализ предметной области;

— проектирование структуры программного комплекса;

— программная реализация;

— тестирование.

Расчет трудоемкости проекта представлен в таблице 2.

Таблица 2 — Перечень работ и их трудоемкость

4.3 Определение затрат на заработную плату

Затраты на выплату исполнителям заработной (, руб) платы определяется следующим соотношением:

(15)

где — основная заработанная плата, руб;

— дополнительная заработная плата, руб;

— отчисление с заработанной платы, руб.

Расчет основной заработанной платы при дневной оплате труда (, руб) исполнителей следует проводить на основе данных по окладам и графику занятости исполнителей:

(16)

где — число дней, отработанных исполнителем проекта;

— дневной оклад исполнителя, руб.

При восьмичасовом рабочем дне дневной оклад исполнителя рассчитывается по соотношению (, руб):

(17)

где — месячный оклад, руб;

— фонд времени в текущем месяце, который рассчитывается из учета общего числа дней в году, числа выходных и праздничных дней.

(18)

где tp — продолжительность рабочего дня;

— общее число дней в году;

— число выходных дней в году;

— число праздничных дней в году.

Фонд времени в текущем месяце равен 166 часов.

В данном дипломном проекте установлен месячный оклад работника, соответствующий должности, занимаемой в ИрГУПСе. Данные приведены в таблице 3.

Таблица 3 — Расчет затрат на заработную плату

Данные таблицы позволяют вычислить общие расходы проекта на выплату заработной платы исполнителям 29 397,73 руб.

Расходы на дополнительную заработанную плату учитывают районный коэффициент, северный коэффициент и премию. Величина этих выплат составляет 20% - районный, 30% -северный коэффициенты и 10% -премия от размера основной заработной платы:

(19)

где — основная заработная плата, руб.

Формула (14) позволяет вычислить расходы на дополнительную заработную плату:

руб.

Отчисления с заработной платы состоят в настоящее время в уплате единого социального налога. Согласно налоговому кодексу РФ применяются ставки налога для отчисления в пенсионный фонд РФ, фонд социального страхования, фонды обязательного медицинского страхования (федеральный и территориальный фонды).

(20)

где — отчисления с заработанной платы в виде единого социального налога ().

Формула 15 позволяет вычислить расходы на отчисление заработной платы:

руб.

Согласно формуле 15, затраты на выплату исполнителям заработной платы составят:

руб.

4.4 Определение материальных расходов

Расходы на персональный компьютер (ПК) определяются материальными расходами на ПК в течение срока разработки программного продукта и стоимостью компьютера.

В материальные расходы входят:

— расходы на электроэнергию;

— стоимость расходных материалов;

— расходы на ремонт;

— заработная плата ремонтника;

— дополнительные расходы — уборка помещения, охрана, аренда, коммунальные услуги ().

А) Расходы на электроэнергию ().

(21)

где — мощность компьютера (0,3 Квт/ч);

— стоимость 1 Квт/ч (0,62 руб.);

— время разработки (513 часов).

Формула 4.7 позволяет вычислить расходы на электроэнергию:

руб.

Б) Стоимость расходных материалов ().

Затраты на расходные материалы в течение всего срока эксплуатации примерно 10% от стоимости компьютера. Срок эксплуатации персонального компьютера — 3 года. Следовательно, можно определить подобные расходы за период создания программного обеспечения.

(22)

где — количество дней в году (249 дней);

— стоимость компьютера (21 000);

— срок разработки (61 день).

Формула 4.8 позволяет вычислить стоимость расходных материалов:

руб.

Итого суммарные материальные расходы ():

руб.

В) Амортизационные отчисления на персональный компьютер ().

Амортизационный период ПК в настоящее время равен сроку морального старения вычислительной техники и составляет 3 года. Следовательно, за 3 года равны стоимости компьютера.

(23)

где — срок службы (3 года).

Формула 4.9 позволяет вычислить амортизационные отчисления на персональный компьютер:

руб.

Г) Амортизационные отчисления на программное обеспечение ().

зависят от цикла замены ПО. Если принять срок морального старения такой же, как у ПК, то за 3 года равны стоимости ПО.

(24)

где — стоимость ПО (15 000).

Формула 4.10 позволяет вычислить амортизационные отчисления на программное обеспечение:

руб.

Итого суммарные амортизационные расходы равны ():

руб.

4.5 Определение накладных расходов

Накладные расходы следует вычислить, ориентируясь на расходы по основной заработанной плате. Обычно они составляют от 60% до 100% расходов на основную заработанную плату. Для Иркутского государственного университета путей сообщений его можно принять как 60% от ОЗП.

(25)

где — основная заработная плата, руб.

Формула 4.12 позволяет вычислить накладные расходы:

руб.

4.6 Определение себестоимости проекта

Определив затраты на материалы, оплату труда, социальное страхование, накладные расходы, можно определить себестоимость проекта — таблица 4.

Таблица 4 — Себестоимость проекта