Методические указания для выполнения контрольной работы

Волгоградский филиал государственного образовательного учреждения

высшего профессионального образования

Российский государственный университет туризма и сервиса

Кафедра «Информационные системы»

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ДЛЯ ВЫПОЛНЕНИЯ

КОНТРОЛЬНОЙ работЫ

по дисциплине «Методика научных исследований»

для студентов всех специальностей

Проф. каф. ИС

Волгоград-2009

1.  ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

·   

Решение многокритериальных задач на ЭВМ с использованием интерактивного графического метода

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

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

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

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

Множество допустимых решений можно представить в виде ориентированного графа, в котором варианты решения — вершины, а связи между вариантами — дуги. В таком многокритериальном графе в каждой вершине содержится информация о критериях в виде вектора X, называемого индикатором. Затем ищется наиболее эффективный путь F*i(x) среди множества допустимых решений Fi(x) с учётом всех fi(x) критериев: F*i(x)=>max Fi(x), (i=1,2,3,...,k ), k — количество критериев. Каждый индикатор, описывающий вариант решения, можно представить в виде вектора

(4.6)

где j=1,2,…,m; m — количество индикаторов вершин

Процесс выбора отражается не только посредством графа с индикаторами вершин, но и возможными вариантами перемещения по этому графу при продвижении к цели. Им будет соответствовать многомерный индикатор вида Q(i) = Возможные пути от начала Q(1) до конца Q(n). Оптимальный путь среди множества возможных должен быть оптимальным одновременно по всем критериям, содержащимся в индикаторах вершин.

2. пРАКТИЧЕСКАЯ ЧАСТЬ

Построение графа вариантов решений

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

В каждой вершине данного графа определены векторы Q состояний, характеризующие процесс выбора. Компонентами векторов служат переменные x (стоимость и продолжительность). II-й, III-й и IV-й этапы проекта соответствуют трем различным типам конструкций фундамента, стен и кровли, соответственно.

Рис. 1. Математическая модель в виде графа для решения двухкритериальной задачи. Критерии записаны в виде дроби: числитель – время реализации проекта (Т), знаменатель – стоимость (С)

Компоненты Q оцениваются в девятибальной шкале и указаны в табл. 1.

Таблица.1

Двухкритериальная оценка вершин задачи

Вершина	1	2	3	4	5	6	7	8	9	10	11
Время	—	2	3	5	7	8	4	6	2	3	—
Стоимость	—	6	2	4	3	3	7	4	9	5	—
		фундамент	стены	кровля

Компьютерная реализация задачи для данного примера сводится к построению на экране координат альтернатив решений в виде соответствующих точек. Возможные альтернативные решения вычисляются программой и сравниваются с кривой вида Q1×Q2=const, график которой также изображается на экране (рис. 2.).

Оптимальным вариантом для этого иллюстративного примера является путь через вершины 1—3—5—10. Приведённый алгоритм позволяет решать двухкритериальные задачи любой природы. Напомним ещё раз, что при этом проблема разбивается на элементарные этапы принятия решений, т. е. вначале производится декомпозиция задачи, а затем строится математическая модель в виде графа с двумерными индикаторами в вершинах.

Рис. 2. Выбор оптимального варианта решения с помощью интерактивного режима на ЭВМ. Минимизация целевой функции, содержащей два критерия, определяет наилучшую точку. На языке компромиссов Парето — это неулучшаемая альтернатива. Она соответствует минимальному пути на графе с вершинами 1—3—5—10—11.

ЗАДАНИЕ

1.  Получить у преподавателя массив чисел для решения двухкритериальной проблемы.

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

3.  Разбить задачу на пять этапов и вычислить последовательно для каждого этапа индексы вершин в виде двух чисел Т/С.

4.  На пятом этапе выбрать оптимальный вариант по двум критериям.

5.  Оформить отчет по лабораторной работе.

6.  Используя критерии стоимости и времени, рассмотрите задачу предоставления услуг некоторой фирмой, занимающейся перевозками.

7.  Как формулируется аналогичная проблема для гостиничного и ресторанного сервиса?

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

ВАРИАНТЫ ЗАДАНИЙ

№ вар.	Критерии/ Вершины	1	2	3	4	5	6	7	8	9
1	Т	9	6	1	5	4	4	5	5	7
С	8	5	8	5	7	9	3	5	1
2	Т	9	2	3	5	8	8	2	8	2
С	7	9	6	7	3	4	6	8	9
3	Т	5	1	8	4	5	2	4	5	7
С	2	6	9	6	2	3	1	6	5
4	Т	5	2	3	6	9	4	6	7	6
С	6	3	6	7	6	8	2	1	5
5	Т	8	2	5	9	7	6	4	4	6
С	7	5	3	8	1	4	6	5	3
6	Т	4	1	8	4	8	9	5	8	7
С	6	2	2	7	2	7	2	8	7
7	Т	8	4	8	4	6	5	4	4	7
С	5	1	7	2	2	3	9	8	5
8	Т	1	5	8	2	9	6	9	9	3
С	4	3	6	4	5	4	2	8	4
9	Т	7	8	3	2	1	5	6	6	2
С	6	8	6	9	5	8	3	7	4
10	Т	2	8	2	2	7	6	2	9	8
С	2	1	9	7	6	8	7	5	2
11	Т	7	5	2	4	5	4	9	5	3
С	8	5	6	3	5	4	8	4	2
12	Т	2	4	4	2	2	1	1	5	7
С	4	7	3	4	1	6	5	6	8
13	Т	1	5	7	7	7	6	6	7	4
С	2	8	2	5	5	6	6	8	6
14	Т	5	2	7	8	6	6	7	7	3
С	8	7	4	7	5	2	1	5	3
15	Т	5	2	7	3	5	7	6	3	5
С	8	2	5	2	5	7	5	4	5
16	Т	7	3	4	2	8	5	3	6	2
С	7	2	1	1	7	8	3	4	8
17	Т	4	5	6	7	7	3	6	2	8
С	1	6	8	4	8	5	7	2	5
18	Т	5	2	6	8	5	4	8	6	7
С	4	1	7	6	5	8	6	7	9
19	Т	3	2	7	8	9	4	8	1	3
С	7	5	9	7	4	1	9	6	6
20	Т	7	8	6	3	5	8	6	1	5
С	3	5	3	6	1	4	2	4	2
21	Т	8	8	6	3	2	7	6	7	3
С	1	4	1	5	3	4	6	8	8
22	Т	9	1	7	3	8	2	6	9	8
С	2	9	3	5	9	2	9	7	5
23	Т	8	5	2	2	6	7	8	7	5
С	4	1	7	6	7	6	7	6	8
24	Т	2	8	4	7	3	6	6	8	9
С	4	3	1	8	3	9	4	3	8
25	Т	3	7	7	6	2	9	2	2	7
С	4	9	7	5	3	5	5	3	3
26	Т	4	2	8	2	5	5	8	3	8
С	9	3	6	1	7	9	7	3	1
27	Т	2	6	8	9	6	1	8	6	7
С	9	8	8	8	2	3	7	6	5
28	Т	7	9	7	4	5	2	5	8	9
С	9	1	5	5	6	8	2	2	8
29	Т	5	3	8	2	8	7	1	3	5
С	9	5	7	8	9	9	5	3	8
30	Т	6	4	6	2	2	6	4	3	2
С	2	6	3	4	4	7	7	2	5
31	Т	6	4	3	5	8	4	7	7	6
С	4	3	9	5	2	4	5	3	5
32	Т	2	3	1	4	5	6	1	8	3
С	7	3	4	3	3	9	3	7	3