Размещено на http://www.allbest.ru/

МИНОБРНАУКИ РОССИИ

ФГБОУ ВО «Тульский государственный университет»

Институт прикладной математики и компьютерных наук

Кафедра «Вычислительная техника»

Курсовая работа

по дисциплине «Клиент-серверное программирование»

Тема проекта: Клиент-серверное приложение для системного проектирования программного обеспечения

Студент группы 240851/01

Суворов Дмитрий Александрович

Введение

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

Вэб-сервисная архитектура программ позволяет использовать ей удалённые компоненты. Веб-службы могут взаимодействовать друг с другом и со сторонними приложениями посредством сообщений, основанных на определённых протоколах (SOAP, XML-RPC, REST и т. д.). Веб-служба является единицей модульности при использовании сервис-ориентированной архитектуры приложения. Для обеспечения взаимодействия используются стандарты XML, SOAP, WSDL, UDDI. Веб-службы обеспечивают взаимодействие программных систем независимо от платформы. Использование интернет-протокола обеспечивает HTTP-взаимодействие программных систем через межсетевой экран. Это значительное преимущество, по сравнению с такими технологиями, как CORBA, DCOM или Java RMI. С другой стороны, веб-службы не привязаны к HTTP и могут использоваться и другие протоколы.

Windows Communication Foundation (WCF) представляет платформу для построения сервисноориентированных приложений. С помощью WCF можно отправлять данные в виде асинхронных сообщений от одной конечной точки службы к другой. Конечная точка службы может входить в постоянно доступную службу, размещаемую в IIS, или представлять службу, размещаемую в приложении. WCF предоставляет единую инфраструктуру разработки, при умелом применении повышающую производительность и снижающую затраты на создание безопасных, надёжных и транзакционных Web-служб нового поколения.

Заложенные в неё принципы интероперабельности позволяют организовать работу с другими платформами. WCF позволяет отправлять сообщения по протоколу TCP. Механизм TCP предоставляет поток данных с предварительной установкой соединения, осуществляет повторный запрос данных в случае потери данных и устраняет дублирование при получении двух копий одного пакета.

Данные технологии будут использованы мною при выполнении курсовой работы.

1. Постановка задачи проектирования

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

· выполнять оптимизацию для заразе подготовленных контрольных примеров. Интерфейс пользователя также предусматривает случайный ввод параметров;

· выполнение исследовательской части работы - исследование вычислительной эффективности метода оптимизации в зависимости от размерности задачи оптимизации.

Вариант задания № 5:

· модель: многомерная задача загрузки рюкзака (МЗЗР);

· метод оптимизации: метод ветвей и границ(ВиГ);

· интерфейс клиентского приложения: WinForms;

· язык веб-сервера: C#;

· тип веб-сервиса: WCF;

· привязка: NetTcp;

· тип хоста: WinForm.

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

В режиме оптимизации проводится исследование вычислительной эффективности алгоритма оптимизации в зависимости от размерности задачи оптимизации. Для каждого значения размерности (например, n = 5, 10, 15, 20, 25, …) генерируются параметры задачи и выполняется серия оптимизационных экспериментов. По результатам каждой серии определяется среднее значение времени оптимизации, которое вместе с исходными данными запоминается в структуре данных в оперативной памяти. Затем результаты экспериментов выводятся на экран в виде таблиц или графиков.

Курсовая работа по клиент-серверному программированию выполняется для закрепления знаний по курсу "Клиент-серверное программирование" и приобретения навыков комплексной реализации прикладной задачи (задачи оптимизации рюкзачного типа) в виде клиент-серверного приложения с использованием низкоуровневых и высокоуровневых сокетов, функциональных возможностей платформы Microsoft Windows Communication Framework (WCF), многопоточной серверной обработки, а также различных инструментальных систем и библиотек, автоматизирующих проектирование и программирование создаваемого приложения.

Задачами курсовой работы являются:

приобретение навыков решения задач оптимизации булева типа;

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

овладение методами и средствами создания и использования клиент-серверных приложений;

приобретение практических навыков оформления и выпуска документации в соответствии с ГОСТ (ЕСПД, UML).

алгоритм конфигурация серверный клиентский

2. Алгоритм решения задачи оптимизации

2.1 Математическое определение задачи MЗЗР

2.1.1 Задача загрузки рюкзака

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

Пусть P={p1, p2, … , pn} - множество программ и n=|P| - мощность этого множества. Характеристиками Pi являются ai и ci - объем программ и коэффициент использования внешней памяти. С позиции задачи о рюкзаке -- это объем и цена i-го предмета.

Необходимо определить подмножество программ, которые будутрезидентными, то есть определить Pоп, Pоп P где |Pоп| = nоп - число резидентных программ.

Введем переменные xi, i = 1, … ,n следующим образом:

Решением задачи один из элементов множества всех подмножеств множества P. Вектор X={x1, x2, …, xn}однозначно определяет выбранные решения.

Пусть - стоимость всех предметов, которые для каждого решения будут разбиваться на стоимости предметов в рюкзаке и стоимости предметов в не рюкзака . Объем рюкзака b рассматривается как величина выделяемого ресурса. Тогда для каждого решения X сумма определяет необходимую величину ресурса.

Цель решения задачи это минимизация . Поскольку то решение минимизирующее будет решением, максимизирующим .

В результате задачу рюкзака можно сформулировать следующим образом:

2.1.2 Многомерная задача загрузки рюкзака

Многомерная задача загрузки рюкзака формулируется следующим образом:

.

- потребление j-го ресурса i-ым предметом;

- величина j-го ресурсного ограничения;

m - количество ограничений.

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

2.2 Метод решения задачи

2.2.1 Алгоритм решения непрерывной задачи загрузки рюкзака

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

Решение задачи загрузки рюкзака методом ветвей и границ предполагает наличие вспомогательной модели, позволяющей прогнозировать получение определенных значений целевой функции в процессе ветвления. Вспомогательная (непрерывная) задача загрузки рюкзака (НЗЗР) использует допущение о непрерывности значений управляемых переменных. Модель НЗЗР (в отличие от ЗЗР) имеет простое решение. Алгоритм решения НЗЗР требует, чтобы индексы в последовательности были отсортированы по убыванию стоимости единицы объема предметов, помещаемых в рюкзак

Решение вспомогательной задачи о рюкзаке очевидно: необходимо брать груз, начиная с первого, до тех пор, пока не заполним весь рюкзак объема b. Если первые k грузов полностью поместим в рюкзак, а (k+1)-й груз частично, то оптимальное решение ?n вспомогательной задачи о рюкзаке будет следующим:



где

Стоимость решения вспомогательной задачи может служить граничной (верхней) оценкой значений F(?n') модели ЗЗР, поскольку

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

2.2.2 Алгоритм решения многомерной задачи загрузки рюкзака

Решение многомерной задачи загрузки рюкзака должно удовлетворять m ограничениям. Схема ветвей и границ применяется для вычисления «обещаний» C(x) на каждом фрагменте решения ?k.

Если как и в одномерной задаче загрузки рюкзака отказаться от дискретности xi, то есть считать, что грузы сыпучи (0? xi ?1), то перейдем к формулировке вспомогательной задачи как задачи линейного программирования. Для упрощения задачи отбросим m-1 ограничений и сведем задачу к одномерной задачи загрузки рюкзака. В каждой вершине дерева перебора будет решаться m вспомогательных задач, получаю m обещаний C(x). Берется наименьшее из этих обещаний.

2.3 Контрольные примеры

2.3.1 Контрольный пример 1

Рассмотрим пример решения многомерной задачи загрузки рюкзака. Параметры первого примера приведены в табл. 1. Задача сформулирована следующим образом:



при условиях ?a1i xi?b1, ?a2i xi?b2,

Таблица 1. Параметры первого примера

i	1	2	3	4	5
ci	15	12	12	15	10
a1i	3	3	4	5	5	b1=13
ci/a1i	5	4	3	3	2
a2i	5	4	3	3	2	b2=11
ci/a2i	3	3	4	5	5

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

максимизировать С1(x)= ?ci xi

при условиях .

С помощью табл. 1. найдем это решение:

x1=x2=x3=1, x4=3/5, x5=0, C1(x)=48.

Сформулируем вторую вспомогательную задачу, выбрав второе ограничение:

максимизировать С2(x)= ?ci xi

при условиях .

В результате решения получим:

x1=x2=x3=1, x4=3/5, x5=0, C2(x)=46.

Поскольку прогноз должен удовлетворять каждому ограничению выберем наименьший прогноз С2. Ход решения представлен на рис. 1.

Размещено на http://www.allbest.ru/

Рис. 1. Решение первого примера

Как видно оптимальное решение получилось X=(1,0,1,1,0). Целевая функция имеет значение 42.

2.3.2 Контрольный пример 2.

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

Таблица 2. Параметры второго примера

i	1	2	3	4	5
ci	24	30	36	20	15
a1i	3	2	2	4	3	b1=9
ci/a1i	8	15	18	5	5
a2i	6	2	3	4	5	b2=14
ci/a2i	4	15	12	5	3
a2i	3	5	2	4	3	b2=13
ci/a2i	8	6	18	5	5

Начнем построение дерева перебора с начальной вершины, отождествляемой с множеством всех возможных вариантов (Рис. 2).

Решим сначала задачу для первого ограничения:

максимизировать С1(x)= ?ci xi

при условиях .

С помощью табл. 2. найдем это решение:

x3=x2=x1=1, x4=2/4, x5=0, C(x)=100.

Сформулируем вторую вспомогательную задачу, выбрав второе ограничение:

максимизировать С2(x)= ?ci xi

при условиях .

В результате решения получим:

x2=x3=x4=1, x1=5/6, x5=0, C(x)=106.

Сформулируем третью вспомогательную задачу, выбрав третье ограничение:

максимизировать С3(x)= ?ci xi

при условиях .

В результате решения получим:

x3=x1=x2=1, x4=3/4, x5=0, C(x)=105.

Размещено на http://www.allbest.ru/

Рис. 4. Решение второго примера

Как видно из рис. 4. Оптимальное решение X=(1,1,1,0,0), а значение целевой функции 90.

3. Структура приложения

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

На рис. 3 показано высокоуровневое представление типичного приложения WCF.

Рис. 3. Высокоуровневое представление приложения WCF

Приложение службы содержит файлы:

BranchAndBound.cs - файл содержащий класс решения задачи;

Multiknapsack.svc - файл реализации службы;

IMultiknapsack.cs - файл с интерфейсом службы;

Mark.cs - файл с классом целевой функции;

Web.config - файл с конфигурациями службы.

Проект хоста состоит из следующих файлов:

Program.cs - файл с главным классом приложения;

Form1.cs - файл с классом формы;

App.config - файл с конфигурацией хоста.

Клиентское приложение содержит файлы:

Program.cs - файл с главным классом приложения клиента;

Knapsack.cs - файл который содержит класс многомерной задачи загрузки рюкзака;

Form1.cs - файл содержащий класс главного окна приложения;

Optimization.cs - файл с классом, организующим связь с сервисом для решения задачи;

EffectiAnalysis.cs - файл с классом, организующим режим анализа;

app.config - файл конфигурации клиента;

Reference.cs - файл прокси-класса для вызова удаленных методов.

4. Программная реализация алгоритма оптимизации

4.1 Входные и выходные данные

Входными данными приложения являются следующие параметры:

· количество предметов;

· стоимости предметов;

· количество ресурсных ограничений;

· коэффициенты ресурсов, требующиеся для предметов.

Выходными данными является решение задачи оптимизации.

Для исследовательской части приложения входными данными является:

· количество ресурсных ограничений;

· максимальная размерность задачи;

· число опытов при одинакового количества ограничений.

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

4.2 Контракт WCF-службы

Контракт WCF-службы определяется следующим образом:

[ServiceContract]

public interface IMultiknapsack

{[OperationContract]

Double[] Сalculate (Double[] vesa, List<Double[]> zad, Double[] B, out int time);}

Интерфейс IMultiknapsack содержит метод Сalculate(), который позволяет запустить процесс оптимизации модели МЗЗР методом ветвей и границ. При этом ему передается список стоимостей предметов vesa, список коэффициентов ресурсов zad, список ограничений B и выходной параметр Time, содержащий продолжительность вычислений в миллисекундах. Полная реализация серверной части приведена в приложении.

4.3 Основные классы WCF-службы

4.3.1 Диаграмма классов

Диаграмма классов WCF-службы представлена на рис.4.

Рис. 4. Диаграмма классов WCF-службы

4.3.2 Класс Multiknapsack

Класс Multiknapsack реализующий интерфейс IMultiknapsack и представляет реализацию контракта службы. Его диаграмма представлена на рис. 5.

Рис. 5. Диаграмма класса Multiknapsack

Класс Multiknapsack содержит следующий метод:

double[] Сalculate() - главная конечная точка вызываемая у клиента.

4.3.3 Класс Knapsack

Класс Knapsack служит для хранения условий задачи, таких как веса предметов для рюкзака и их критериев. Его диаграмма представлена на рис. 6

Рис. 6. Диаграмма класса Knapsack

Класс Knapsack содержит следующие поля:

double[] Weight - массив весов для добавления в рюкзак;

int N - количество условий;

int Length - размер рюкзака;

double[] B - ограничения по каждому условию;

List<double[]> Settings - критерии для каждого ограничения.

Также класс Knapsack содержит конструктор:

Knapsack() - конструктор класса, инициализирующий основные переменные.

4.3.4 Класс BranchAndBound

Класс BranchAndBound служит для решения многомерной задачи рюкзака методом ветвей и границ. Его диаграмма представлена на рис. 7.



Рис. 7. Диаграмма класса BranchAndBound

Класс BranchAndBound имеют следующие поля:

Knapsack knapsack - условия рюкзака для конкретной задачи;

double[] resaltKnapsack - массив выбранных предметов(если предмет выбран значение элемента массива 1, в противном случае 0).

В классе BranchAndBound также имеется следующий метод:

double[] Ran() - основной метод рассчитывающий оптимальный рюкзак методом ветвей и границ.

4.3.5 Класс Mark

Класс Mark предназначен для нахождения целевой функции по одному из критериев. Его диаграмма представлена на рис. 8.

Рис. 8. Диаграмма класса Mark

Класс Mark содержит следующие поля:

Knapsack knapsack - условия рюкзака для данной задачи;

int N - количество предметов, помещаемых в рюкзак.

Класс Mark имеет следующие методы:

double getMark() - метод нахождения значения целевой функции для текущее задачи;

int[] getVeaSort() - метод сортирующий индексы предмета по величине отношения веса к критерию.

4.3.6 Класс MultyMark

Класс MultyMark производный от класса Mark. Дополняет его нахождением целевой функции по каждому ограничению. Его диаграмма представлена на рис. 9.

Рис. 9. Диаграмма класса MultyMark

Класс MultyMark содержит следующие поля:

double[] Rez1 - значения целевых функций в правой ветки задачи;

double[] Rez2 - значения целевых функций в левой ветки задачи.

Класс MultyMark содержит следующие методы:

double[] GetRez1() - решение целевой функции для правой ветки задачи;

double[] GetRez2() - решение целевой функции для левой ветки задачи;

double MaxC() - нахождение максимального решения и выбор ветки с этим решением.

5. Программная реализация клиент-серверного приложения

5.1 Программные средства разработки

Приложение на базе WCF разрабатывается в интегрированной среде разработки Microsoft Visual Studio Community 2015.

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

И клиентское, и серверное приложение для реализации графического интерфейса используют технологию Win Forms.

Серверная часть приложения основана на WCF сервисах.

Windows Communication Foundation - это унифицированная модель программирования распределенных приложений на платформе Microsoft. Она инкапсулирует и развивает предшествующие технологии - ASMX (технологию web-сервисов с расширением *.asmx), .NET Remoting, DCOM, MSMQ - и предоставляет расширяемый API, отвечающий разнообразным требованиям, которые возникают при создании распределенных систем. До WCF приходилось овладевать всеми этими технологиями, чтобы выбрать ту, которая лучше всего подходит в конкретной ситуации. WCF упрощает задачу, предлагая единообразный подход. WCF-служба - это множество оконечных точек (endpoints), которые предоставляет клиентам некие полезные возможности. Оконечная точка - это просто сетевой ресурс, которому можно посылать сообщения.

Класс службы WCF не может существовать самостоятельно. Каждая служба WCF должна находиться под управлением некоторого процесса Windows, называемого хостовым процессом. В нашем приложении хостом является Windows Forms приложение.

Для работы с табличными данными используется тип DataTable. Тип DataSet представляет собой контейнер для любого количества объектов DataTable, каждый из которых содержит коллекцию объектов DataRow и DataColumn.

Для вывода диаграммы используется компонент Chart. Этот класс предоставляет все свойства, методы и события диаграммы элемента управления Windows.

Два наиболее важных свойства класса Chart -- Series и ChartAreas, являющиеся свойствами коллекций. Свойство-коллекция Series хранит объекты Series, которые используются для хранения данных, которые должны отображаться, наряду с атрибутами этих данных. Свойство-коллекция ChartAreas хранит объекты ChartArea, которые в основном используются для рисования одной или нескольких диаграмм с помощью одного набора осей.

5.2 Разработка конфигурации службы

Конфигурации службы описаны в конфигурационном файле App.config. Его листинг приведен ниже.

<system.serviceModel>

<services>

<service name="MZZRServ.Multiknapsack" behaviorConfiguration="mexBehavior">

<endpoint address="Multiknapsack" binding="netTcpBinding" contract="MZZRServ.IMultiknapsack"></endpoint>

<host>

<baseAddresses>

<add baseAddress="net.tcp://localhost:45617/"/>

</baseAddresses>

</host>

</service>

</services>

</system.serviceModel>

В этом файле был определен новый элемент service с именем MZZRServ.Multiknapsack. В службе была определена конечная тока со своими адресом, привязкой и контрактом. Адресом конечной точки является «Multiknapsack». Этот адрес пишется относительно базового адреса, определенного в теге baseAddresses. Базовым адресом является «net.tcp://localhost:45617/». Он имеет net.tcp схему. Соответственно привязкой конечной точки была выбрана netTcpBinding. В атрибуте contract был указан контракт «MZZRServ.IMultiknapsack».

5.3 Классы приложения-хоста

5.3.1 Диаграмма классов

Серверная часть приложения реализует WCF сервис и хост. Она содержит несколько классов. Общая схема классов хоста службы показана на рис. 10.

Рис. 10. общая диаграмма классов хоста

5.3.2 Класс Form1

Класс Form1 запускает службу. Диаграмма этого класса показана на рис. 11.

Рис. 11. Диаграмма класса Form1

Класс Form1 имеет следующие методы:

void StartButton_Click() - обработчик кнопки для запуска службы;

void StopButton_Click() - обработчик кнопки для остановки службы.

5.3.3 Класс Program

Класс Program представляет механизм управления приложением. Диаграмма этого класса представлена на рис. 12.

Рис. 12. Диаграмма класса Program

Класс Program имеет один метод:

private void Main() - метод, определяющий точку входа для приложения.

5.4 Классы клиентского приложения

5.4.1 Диаграмма классов

Клиентская часть приложения реализована в виде WinForm проекта. Она вызывается на клиентском компьютере и содержит несколько классов, представленных ниже.

Диаграмма классов клиентского приложения представлена на рис. 13.

Рис. 13. Диаграмма классов приложения клиента

5.4.2 Класс Knapsack

Класс Knapsack аналогичен такому же классу на сервере. Он содержит те же поля и методы (пункт 4.3.3).

5.4.3 Класс Form1

Класс Form1 представляет графический пользовательский интерфейс для обращения к службе. Его диаграмма представлена на рис. 14.



Рис. 14. Диаграмма класса Form1

Класс Form1 содержит следующее поля:

Dictionary<string, Knapsack> test - список содержащий контрольные примеры;

ListBox listBox1 - элемент графического интерфейса для выбора контрольного примера;

TextBox textBoxRezult - элемент графического интерфейса для вывода результата;

DataGridView dataGridView1 - элемент графического интерфейса для вывода результата анализа эффективности алгоритма;

Chart chart1 - график показывавший зависимость времени работы алгоритма от размера рюкзака.

Класс Form1 содержит следующие методы:

void Form1_Load() - загрузка формы в которой происходит инициализация контрольных примеров и списков для ListBox;

void button1_Click() - обработчик кнопки реализующий связь с сервером и отправкой ему задачи. А также вывод результата полученного от сервера;

void outputResult() - вывод результата оптимизации;

void button2_Click() - обработчик нажатия кнопки начинающий анализ алгоритма оптимизации по введённым пользователем параметрам и выводящий результат в виде графика и таблицы.

5.4.4 Класс Optimization

Класс Optimization решает задачу оптимизации рюкзака и связывается с сервисом через прокси-класс. Класс представлен на рис. 15.

Рис. 15. - Диаграмма класса Optimization

Класс Optimization содержит следующие методы:

void IntroduceData() - метод решение задачи на сервере по данным введённым пользователем;

void testExempl() - метод для решения контрольного примера выборного пользователем.

5.4.5 Класс EffectiAnalysis

Класс EffectiAnalysis выполняет анализ алгоритма по введённым пользователем параметрам. Класс представлен на рис. 16.

Рис. 16. Диаграмма класса EffectiAnalysis

Класс EffectiAnalysis содержит следующие методы:

DataTable Ran() - главный метод, выполнявший анализ времени работы алгоритма;

Knapsack GenerateRandomKnapsack() - метод реализующий генерацию случайной задачи для расчета эффективности метода оптимизации;

int[] Experian() - метод рассчитает времени всех экспериментов.

5.5 Подключение веб-сервиса к клиентскому приложению

Клиентское приложение использует сервисы для обращения к фикциям и методам на сервере. Для использование WCF в клиентском приложении необходимо добавить ссылку на System.ServiceModel. После создания сервиса в проект клиентского приложения необходимо добавить ссылку на сервис. Для этого в окне Solution Explorer в пункте Reference надо выбрать опцию Add Service Reference. В появившемся окне необходимо указать адрес сервиса, нажать «Go» и выбрать появившийся сервис. После этого будет сгенерирован файл References.cs, содержащий все разрешенные методы сервиса, и они станут доступны из клиентского приложения через прокси класс. На клиентской стороне будет сгенерирован файл конфигурации App.config, содержащий информацию о службе. После чего можно создать экземпляр прокси класса и работать с ним как с обычным классом.

5.6 Результаты работы приложения

На рис. 17 представлено окно хоста службы WCF.

Рис. 17. Окно хоста

На рис. 18 представлены результаты работы приложения для решения МЗЗР методом «Ветвей и границ» с данными введёнными пользователем.

Рис. 18. Результаты работы с введёнными пользователем данными

На рис. 19 представлены результаты работы программы при решении первого контрольного примера.

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

Как видно из рисунка результаты совпадают с рассчитанными ранее.

Выполнение режима оптимизации для 500 элементов 2-ч ограничений и 20-ти опытов приведена на рис. 20.

Рис. 20. Результаты исследования эффективности

Сообщения об ошибках при некорректном вводе данных представлены на рис. 21.

Рис. 21. Сообщения об ошибках

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

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

Требования к компьютеру клиента и сервера:

· операционная система MS Windows;

· установленные .net framework 4 и более;

· оперативная память 1 Гб и более;

· наличие 50 Мб свободного дискового пространства.

6. Исследование вычислительной эффективности алгоритма оптимизации

Исследование вычислительной эффективности проводится путем определения зависимости затраченного времени на решении задачи от количества элементов в условии.

Исследование вычислительной эффективности алгоритма ветвей и границ проводилось на компьютере со следующей конфигурацией:

· операционная система - Windows 10 64-bit;

· процессор - Core i5 2000 МГц;

· оперативная память - 4 Гб.

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

Для начала проверим эффективность задачи при размере рюкзака равного 2. Результат показан на рис. 22

Рис. 22. Анализ эффективности метода с 2-мя ограничениями

Как видно из графика время работы алгоритма имеет экспоненциальную зависимость от количества элементов в задаче.

Проведем также эксперименты для 3-х и 4-х ограничений. Результаты, которых показаны на рис.23 и рис. 24.

Рис. 23. Анализ эффективности метода с 3-мя ограничениями

Рис. 24. Анализ эффективности метода с 4-мя ограничениями.

Как видно из графиков время решения задачи на прямую зависит от количества ограничений. При использовании 500 предметов и 4-x ограничений алгоритм работает 1400 миллисекунд. Исходя из этого можно сделать вывод что метод «ветвей и границ» может использоваться для решения задачи рюкзака.

Заключение

В ходе выполнения данной курсовой работы было разработано клиент-серверное приложение, решающее МЗЗР методом «ветвей и границ». Был проведен анализ вычислительной эффективности этого алгоритма. В ходе исследования увеличивалось количество предметов, размещаемых в рюкзаке, при неизменном количестве ресурсных ограничений.

Также во время выполнения курсовой работы были закреплены знания по предмету «Клиент-серверное программирование», и приобретены навыки разработки клиент-серверных приложений.

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

1. ГОСТ 19.106-78 ЕСПД. Требования к программным документам, выполненным печатным способом.

2. ГОСТ 19.503-79 Руководство системного программиста. Требования к содержанию и оформлению.

3. ГОСТ 19.504-79 Руководство программиста. Требования к содержанию и оформлению.

4. ГОСТ 19.505-79 Руководство оператора. Требования к содержанию и оформлению.

5. ГОСТ 19.401-78 ЕСПД. Текст программы. Требования к содержанию и оформлению.

6. Резник С., Крейн Р., Боуэн К. Основы Windows Communication Foundation для .NET Framework 3.5. - М.: ДМК Пресс, 2008. - 480 с.

7. А.А. Кожемякин HTML и CSS в примерах. Создание Web-страниц Питер 2012

8. Троелсен Э. Язык программирования C# 5.0 и платформа .NET 4.5. 6-изд. : Пер. с англ. - М. : ООО «И.Д. Вильямс», 2013. - 1312 с.

9. Сибраро П. и др. WCF 4: Windows Communication Foundation и .NET 4 для профессионалов. - М.: ООО И.Д. Вильямс, 2011. -- 465 с.

10. Берсенев Г. Б. Системное проектирование программного обеспечения. Модели и методы принятия решений. Тула 2010 - 116 с.

Приложение

Файл IMultiknapsack.cs

namespace MZZRServ

{

[ServiceContract]

public interface IMultiknapsack

{

[OperationContract]

double[] Сalculate(double[] vesa, List<double[]> zad, double[] B, ref int time);

}

}

Файл Multiknapsack.svc

using System.Diagnostics;

namespace MZZRServ

{

public class Multiknapsack : IMultiknapsack

{

public double[] Сalculate(double[] vesa, List<double[]> zad, double[] B, ref int time)

{

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();

BranchAndBound Br = new BranchAndBound();

double sum;

var rez = Br.Ran(vesa, zad, B, out sum);

stopWatch.Stop();

var s = stopWatch.ElapsedMilliseconds;

time = (int)s;

return rez;

}

}

Файл BranchAndBound.cs

public class Knapsack

{

public double[] Weight { get; set; }

public int N { get; set; }// количество условий;

public int Length { get; set; }//

public double[] B { get; set; }// ограничения по каждому условию.

public List<double[]> Settings { get; set; }// различные веса

public List<double[]> Otnoh { get; set; }

public Knapsack(double[] vesa, List<double[]> zad, double[] B)

{

this.Weight = vesa;

this.N = B.Length;

this.Length = vesa.Length;

this.B = B;

this.Settings = zad;

this.Otnoh = new List<double[]>();

}

}

/////////////

public class BranchAndBound

{

public Knapsack knapsack;//рюкзак

public double[] resaltKnapsack;

public int[] getVeaSort(int[] index1, int pos, int nu)

{

//int[] rez = (int[])vesa.Clone();

int n = index1.Length - pos;

double[] ot = new double[n];// (double[])otnoh[nu].Clone();

int[] index = new int[n];// (int[])index1.Clone();

for (int i = 0; i < n; i++)

{

ot[i] = knapsack.Otnoh[nu][i + pos];

index[i] = index1[i + pos];

}

for (int i = 0; i < n; i++)

{

for (int j = i + 1; j < n; j++)

{

if (ot[i] < ot[j])

{

double temp = ot[i];

int tmp1 = index[i];

ot[i] = ot[j];

index[i] = index[j];

ot[j] = temp;

index[j] = tmp1;

}

}

}

return index;

}

public double getMark(double[] X2, int pos, int nump)

{

double[] X = (double[])X2.Clone();

double sumA = 0;

double sumC = 0;

//массив индексов

int[] index = new int[knapsack.Length];

for (int i = 0; i < index.Length; i++) index[i] = i;

for (int i = 0; i < pos; i++)

{

if (X[i] == 1)

{

sumA += knapsack.Settings[nump][i];

sumC += knapsack.Weight[i] * X[i];

if (sumA > knapsack.B[nump]) return -1;

}

}

//получение сортированного массива индексов по отношению весов к частным критериям

int[] Nindex = getVeaSort(index, pos, nump);

if (pos < knapsack.Length)

{

foreach (int i in Nindex)

{

if (i >= pos)

{

if ((sumA + knapsack.Settings[nump][i]) < knapsack.B[nump])

{

X[i] = 1;

sumA += knapsack.Settings[nump][i];

sumC += knapsack.Weight[i] * X[i];

}

else if ((sumA + knapsack.Settings[nump][i]) == knapsack.B[nump])

{

X[i] = 1;

sumA += knapsack.Settings[nump][i];

sumC += knapsack.Weight[i] * X[i];

return sumC;

}

else if ((sumA + knapsack.Settings[nump][i]) > knapsack.B[nump])

{

X[i] = (knapsack.B[nump] - sumA) / knapsack.Settings[nump][i];

sumC += knapsack.Weight[i] * X[i];

return sumC;

}

}

}

}

else return sumC;

return 0;

}

public double[] Ran(double[] weight, List<double[]> settings, double[] B, out double sum)

{

knapsack = new Knapsack(weight, settings, B);

for (int i = 0; i < knapsack.B.Length; i++)

{

var tmp = new double[knapsack.Weight.Length];

for (int j = 0; j < knapsack.Weight.Length; j++)

{

tmp[j] = knapsack.Weight[j] / knapsack.Settings[i][j];

}

knapsack.Otnoh.Add(tmp);

}

var templ = new double[weight.Length];// { 0, 0, 0, 0, 0 };

int pos = 0;

double rez = 0;

pos = 1;

////////////////АЛГОРИТМ

for (int i = 0; i < knapsack.Length; i++)

{

double[] rez1 = new double[knapsack.N];

templ[pos-1] = 1;

for (int j = 0; j < knapsack.N; j++)

{

rez1[j] = getMark(templ, pos, j);

}

double[] rez2 = new double[knapsack.N];

templ[pos-1] = 0;

for (int j = 0; j < knapsack.N; j++)

{

rez2[j] = getMark(templ, pos, j);

}

if (rez1.Min() > rez2.Min() && rez1.Min()!=-1)

{

templ[pos-1] = 1;

pos++;

rez = rez1.Min();

}

else if(rez2.Min()!=-1)

{

templ[pos-1] = 0;

pos++;

rez = rez2.Min();

}

}

sum = rez;

resaltKnapsack = templ;

return templ;

}

}

Файл Form1.cs

namespace CSWcfHost

{

public partial class Form1 : Form

{

ServiceHost host;

public Form1()

{

InitializeComponent();

}

private void StartButton_Click(object sender, EventArgs e)

{

if (host==null||!(host.State == CommunicationState.Opening))

{

host = new ServiceHost(typeof(Multiknapsack));

host.AddDefaultEndpoints();

host.Open();

msg.Text = "Сервис запущен";

}

}

private void StopButton_Click(object sender, EventArgs e)

{

if (host.State == CommunicationState.Opening || host.State == CommunicationState.Opened)

{

host.Close();

msg.Text = "Сервис остановлен";

}

}

}

}

Файл App.config

<?xml version="1.0" encoding="utf-8" ?>

<configuration>

<startup>

<supportedRuntime version="v4.0" sku=".NETFramework,Version=v4.5.2" />

</startup>

<system.serviceModel>

<services>

<service name="MZZRServ.Multiknapsack" behaviorConfiguration="mexBehavior">

<endpoint address="Multiknapsack" binding="netTcpBinding" contract="MZZRServ.IMultiknapsack"></endpoint>

<endpoint address="mex" binding="mexHttpBinding" contract="IMetadataExchange"></endpoint>

<host>

<baseAddresses>

<!--<add baseAddress="http://localhost:8101/"/>-->

<add baseAddress="net.tcp://localhost:45617/"/>

</baseAddresses>

</host>

</service>

</services>

<behaviors>

<serviceBehaviors>

<behavior name="mexBehavior">

<serviceMetadata httpGetEnabled="true"/>

</behavior>

</serviceBehaviors>

</behaviors>

</system.serviceModel>

</configuration>

Файл Form1.cs

namespace MZZRClient

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

Dictionary<string, Knapsack> test;

private void Form1_Load(object sender, EventArgs e)

{

test = new Dictionary<string, Knapsack>();

var zad1 = new List<double[]>();

zad1.Add(new double[] { 3, 3, 4, 5, 5 });

zad1.Add(new double[] { 5, 4, 3, 3, 2 });

var zad2 = new List<double[]>();

zad2.Add(new double[] { 3, 2, 2, 4, 3 });

zad2.Add(new double[] { 6, 2, 3, 4, 5 });

zad2.Add(new double[] { 3, 5, 2, 4, 3 });

test.Add("Пример1", new Knapsack

{

Weights = new double[] { 15, 12, 12, 15, 10 },

N = 2,

B = new double[] { 13, 11 },

zad = zad1

});

test.Add("Пример2", new Knapsack

{

Weights = new double[] { 24, 30, 36, 20, 15 },

N = 3,

B = new double[] { 9, 14, 13 },

zad = zad2

});

listBox1.Items.AddRange(test.Keys.ToArray());

listBox1.SelectedIndex = 0;

}

private void button1_Click(object sender, EventArgs e)

{

ChannelFactory<ServiceReference1.IMultiknapsack> factory = new ChannelFactory<ServiceReference1.IMultiknapsack>(new NetTcpBinding());

ServiceReference1.IMultiknapsack client1 = factory.CreateChannel(new EndpointAddress("net.tcp://localhost:45617/"));

if (checkBox1.Checked)

{

testExempl(client1);

}

else

{

IntroduceData(client1);

}

}

private void IntroduceData(IMultiknapsack client1)

{

double[] B;

double[] Weights;

List<double[]> zad;

int NumLimitations;

if (!int.TryParse(textBox1.Text, out NumLimitations))

{

MessageBox.Show("Количество ограичений имеет не верный фармат");

};

try

{

B = textBox3.Text.Split(new char[] { ',' }).Select(i => double.Parse(i)).ToArray();

Weights = textBox2.Text.Split(new char[] { ',' }).Select(i => double.Parse(i)).ToArray();

zad = new List<double[]>();

var str = richTextBox1.Text.Split(new char[] { '\n' });

foreach (var s in str)

{

s.Trim();

zad.Add(s.Split(new char[] { ',' }).Select(i => double.Parse(i)).ToArray());

}

try

{

int ti = 0;

var s = client1.Сalculate(Weights, zad.ToArray(), B, ref ti);

outputResult(s);

}

catch (Exception exep) { MessageBox.Show("Нет ответа от сервера"); };

}

catch (Exception exep) {

MessageBox.Show("Введеные данные задачи имеют не верный фармат");

};

}

private void outputResult(double[] s)

{

StringBuilder formatResalt = new StringBuilder();

foreach (var items in s)

{

formatResalt.AppendFormat("{0} - ", items);

}

formatResalt.Remove(formatResalt.Length - 2, 2);

textBoxRezult.Text = formatResalt.ToString();

}

private void testExempl(ServiceReference1.IMultiknapsack client1)

{

try

{

var kn = test[(string)listBox1.SelectedItem];

var client = new ServiceReference1.MultiknapsackClient("NetTcpBinding_IMultiknapsack1");

int ti = 0;

var s = client1.Сalculate(kn.Weights, kn.zad.ToArray(), kn.B, ref ti);

outputResult(s);

}

catch (Exception exep) { };

}

private Knapsack GenerateRandomKnapsack(int length, int N)

{

Random rand = new Random();

var resalt = new Knapsack();

double[] Weights = new double[length];

for(int i=0; i<length; i++)

{

Weights[i] = rand.Next(50);

}

double[] B = new double[N];

List<double[]> list = new List<double[]>();

for (int i=0; i< N; i++)

{

double[] zad = new double[length];

for (int j=0; j<length; j++)

{

zad[j] = (double)rand.Next(50);

}

double sum = zad.Sum();

B[i] = rand.Next((int)sum, (int)sum);

list.Add(zad);

}

resalt.Weights = Weights;

resalt.zad = list;

resalt.N = N;

resalt.B = B;

return resalt;

}

private void button2_Click(object sender, EventArgs e)

{

ChannelFactory<ServiceReference1.IMultiknapsack> factory = new ChannelFactory<ServiceReference1.IMultiknapsack>(new NetTcpBinding());

ServiceReference1.IMultiknapsack client1 = factory.CreateChannel(new EndpointAddress("net.tcp://localhost:45617/"));

int size = (int)numericUpKnaSize.Value;

int limit = (int)numericUpNumdeLimit.Value;

int experience = (int)numericUpExperiNumde.Value;

DataTable td = new DataTable();

td.Columns.Add(new DataColumn("x", Type.GetType("System.Int32")));

td.Columns.Add(new DataColumn("y", Type.GetType("System.Int32")));

this.chart1.Series.Clear();

Series series = this.chart1.Series.Add("");

series.ChartType = SeriesChartType.Spline;

for (int i = 50; i < size; i+=10)

{

int startSiz = i;

Knapsack kn = GenerateRandomKnapsack(startSiz, limit);

int[] tisred = new int[experience];

for (int j=0; j< experience; j++)

{

int t = 0;

var s = client1.Сalculate(kn.Weights, kn.zad.ToArray(), kn.B, ref t);

}

int ti = (tisred.Max() + tisred.Min()) / 2;

//series.Points.AddXY(startSiz, ti);

td.Rows.Add(startSiz, ti);

}

chart1.DataSource = td;

dataGridView1.DataSource = td;

series.XValueMember = "x";

series.YValueMembers = "y";

chart1.DataBind();

dataGridView1.Show();

int idd = 5;

}

}

}

Файл app.config

<?xml version="1.0" encoding="utf-8" ?>

<configuration>

<startup>

<supportedRuntime version="v4.0" sku=".NETFramework,Version=v4.5.2" />

</startup>

<system.serviceModel>

<services>

<service name="MZZRServ.Multiknapsack" behaviorConfiguration="mexBehavior">

<!--<endpoint address="Multiknapsack" binding="basicHttpBinding" contract="MZZRServ.IMultiknapsack"></endpoint>-->

<endpoint address="Multiknapsack" binding="netTcpBinding" contract="MZZRServ.IMultiknapsack"></endpoint>

<host>

<baseAddresses>

<!--<add baseAddress="http://localhost:8101/"/>-->

<add baseAddress="net.tcp://localhost:45617/"/>

</baseAddresses>

</host>

</service>

</services>

<behaviors>

<serviceBehaviors>

<behavior name="mexBehavior">

<serviceMetadata httpGetEnabled="false"/>

</behavior>

</serviceBehaviors>

</behaviors>

</system.serviceModel>

</configuration>

Размещено на Allbest.ur