Ответына контрольные вопросы
«Характеристиказадач оптимизации выбора»
Ответ 1:
Процесс отысканиянаилучшего решения задачи называется процессом
оптимизации. Но припрактическом решении задач далеко не все во-
зможнопредусмотреть Удается найти рациональное (целесообразное)
решение — возможно не самоелучшее, но приемлемое в данной ситу-
ации.Далее, при поиске оптимума, необходимо выбрать наилучшее
решение езмножества всех рациональных (целесообразных).
Ответ 2:
Почему сложно найтицелесообразное решение в ПО? Как было сказа-
нновыше, отыскание оптимального решения возможно при наличии
множества рациональныхрешений. Но ПО является структурированной
сложной иерархическойсистемой, поэтому количество возможных ва-
риантов(outcomes) является колоссальным. Это обусловленно боль-
шимколичеством переменных. Для решения этихчасто используется
ЭВМ и разработанныметоды: линейный, динамический, программный.
Ответ 3:
При решении задачоптимизации в основном используются переменные
(константы используютсяреже). Дело в том, что переменные прини-
мают значения в зависимостиот разных условий.
Ответ 4:
Основными проблемами математической теорииоптимизации являются:
_аСуществованиедопустимого решения;
бНаличиенеобходимого условия оптимизации;
вНаличиедостаточного условия оптимизации;
гАлгоритмизациявыбора.
Ответ 5:
1. Сущность проблемысуществования допустимого решения:
Вся проблема состоит ввыявлении хотя бы одного допустимого реше-
ния,и если оно есть, то надо найти экстремум среди этих решений
И здесь задача минимизации и максимизации превращается взадачи
на супремуми инфимум — установление max (min) точки допустимых
решений.
2. Необходимое и достаточноеусловия оптимизации:
Необходимые условия обеспечивают выделение в классе допустимых
управлений некоторогоподкласса к которому может принадлежать оп-
тимальноезначение управления. Поэтому возможно установить свой-
стваоптимального решения, выявить его функциональную форму. При
совпадении необходимого и достаточного условий возможноуказать
путь к решению.
Ответ 6:
В настоящее время созданно множество программ АНАЛИЗАТОРОВ кото-
рыеобеспечивают процесс оптимизации и значительно «облегчают»
работу менеджеров.
1. Для оценки алгоритмовнеобходимо знать:
а) Сходимость алгоритма — возможность выявления оптимального
решения после конечногоколичества вычислений;
б) Скорость сходимости — то конечное количество вычислений;
в) Чуствительностьалгоритма к ошибкам вычисления.
2. Для реализации алгоритмовзадач оптимизации на ЭВМ нужно знать
количество операций, объемОЗУ, требования к обмену данными.
Ответына контрольные вопросы по теме № 11.
Выбор решений в условиях неопределённости
1. Для чего создаётсяматематическая модель в задачах выбора?
Математическая модель в задачах выбора создаётсядля того, чтобы преодолеть
слабую структуризацию большинства исходныхпостановок задач выбора.
2. В чем состоит трудность выборав этих задачах?
На мой взгяд, трудностьпри выборе в такого рода задачах состоит в неопреде-
лённости понятия «лучшего альтернативного варианта».При этом возникает
вопрос — в каком смысле лучше?
3. Какие виды и зависимостивыделяют в проблеме выбора?
Обычно выделяют три вида принятия решений. Приэтом учитывают следующие
пункты:
— кемпринимаются решения: коллективом или индивидуумом?
— насколько однозначна связь между принимаемыми решениями
и ихрезультатами;
— какхарактеризуются результаты (исходы) выбираемых решений.
4. Какие типы неопределённостисуществуют в проблеме выбора? их сущность?
В проблеме выбора выделяют три типанеопределённости:
1.Неопределённость выбора — когда цель склонна к одному из многих желаний
трудносопоставить различные требования: либо цель не реальна, либо её
вообщетрудно сформулировать;
2.Неопределённость природы — у нас есть цель, которая требует выполнения, но
результат выполнения зависит от каких-либо параметров, а выборспособа
действий от значений этихпараметров;
3.Неопределённость реального «противника» — у «противника» тоже есть цели,
которые мы можем и не знать, и поэтому результат наших действий зависит
отдействий «противника».
5. Что называется математическойструктурой выбора с неопределённостью?
Математической структурой выбора снеопределённостью называется структура, которая характеризуется:
1.Неопределённостью, вводимой при построении общей структуры выбора;
2.Неопределённостью исходной математической структуры;
3. Илиобоими указанными видами.
6. Какие вводятся виды мат.структуры выбора с неопределённостью?
Структура 1-го вида создаётся надетерминированной исходной структуре и
связана с введением следующих разновидностейнеопределённости:
— нечеткое задание отношения предпочтения и дополнительных, ограничиваю-
щихотношений на основа нечетких множеств;
— неизвестность выбора «природы», учитываемого в структуре выбора;
— искусственноевведение рандомизации (random — случайный)
Рандомизация — статистическая процедура, в которой решение принимается
случайным образом (Технический пример: случайноеудаление страниц
физической памяти при работе с использованиемвиртуальных адресов).
Структуры выбора 2-го вида создаются как стахостические и нечеткие. Статис-
тическиеструктуры вводятся для получения различной информации и умень-
шениянеопределённости в самом процессе решения задачи выбора.
Copyright©1994 by Vsevolod Ukrainsky
Тема 12: «Выбор с мультипредпочтением»
1. В чем трудность выбора с мультипредпочтением?
Переходк выбору с мультипредпочтением обычно приводит к неопределённости. При этом неопределённость преодолеваетсяпереходом от начального множества отношений предпочтений
крезультирующему отношению предпочтений. Основная трудность принятия решений здесь связанна сотсутствием скалярных показателей для оценки качества альтернативных вариантоврешений. Причина — отсутсвие их в сложных задачах.
2. Почему возникает МКЗПР?
Многокритериальнаязадача принятия решений (МКЗПР), проблема сравнения и оценки раз-личныхвариантов решений с учётом определённых критериев возникает из-за сложности приня-тия решений выбора с мультипредпочтением.А также для выявления влияния выбираемых ре-
шенийна возможные последствия.
3. Для чего предназначенамногокритериальная модель?
Организацияпроцесса принятия решений — специальная деятельность, требующая специальныхзнаний. Для этого предназначена модель МКЗПР, которая должна представить задачув упро-щенном виде. Для объективного анализа исравнения альтернитивных вариантов., учитывая их
последствияи отнощение ответственного руководителя кпоследствиям.
4. Что даёт итеративный подход кпостроению модели?
Превлечениеметодов принятия решений обусловленнослабоструктурируемостью решения задачи. Для предотвращения этого используется итеративный подход.
5. Какие правила применяются припостроении МКЗПР?
1.Модель создаётся последовательно для структурирования и уточнений предложений ответст-венного руководителя, который участвует в еёразработке.
2.Модель должна быть логически непротиворечивой.
3.Она должна содержать описание всех возможных элементов ЗПР и их свойств.
4.Модель должна обеспечивать применение реальной информации по задаче, получаемой от экспертов и ответственного руководителя.
5.Модель должна быть простой и удобной для анализа и использования отв.руководителем.
6. Что подразумевается под груповым, игровым, векторным выбором и
математической структурой выбора с мультипредпочтением?
Групповымназывается выбор, при котором каждая альтернатива подвергается ординальнойили кардинальной оценке поиндивидуальным отношениям предпочтений и по определённому правилувырабатывается результирующая оценка.
Игровымназывается выбор сложной альтернативы, (кортежа на множестве альтернатив)который осуществляется некоторым количест-вом игроков(коалиций) в соответствии с индивидуальными отношениями предпочтений инекоторой степенью информированности о дейстствияхдругих игро-ков, включая и достижения каких-либосоглашений.
Векторнымназывается выбор, при котором отношения предпочтения задаются элементами крите-риальных функций, дающих оценку альтернатив с разныхпозиций.
Матеметическойструктурой выбора с мультипредпочтениемназывается структура, определённая заданием на исходной структуре некоторого количества отношений предпочтения и описание правила длясопоставления этим отношением результирующего отношения предчпочтения.
Copyright© 1994 by VsevolodUkrainsky
Тема 13: «Анализвыбора решений»
1. Каковы основные элементымодели МКЗПР?
Основнымимоделями МКЗПР являются:
цпостановка или тип задачи;
чмножество решений;
шмножество критериев;
щмножества шкал критериев;
ъотображениемножества допустимых решений во множестве
векторных решений;
ынабор предпочтений ответственного руководителя, принимаю-
щего решения;
ьрешающее правило;
2. Что требуется отсодержательной постановки задачи?
В зависимости от содержательной постановкизадачи, необходимо:
1.Отыскать наиболее предпочтительное решение;
2.Полностью упорядочить множество допустимых решений;
3.Выделить множество недоминируемых решений;
3. Какие названия имеет элементмножество решений?
Элементы множества решений могут носить следующиеназвания:
лдопустимые решения;
мварианты решений;
нстратегии;
одействия;
пальтернативы;
ральтернативныеварианты.
4. Какие показатели называютсякритериями модели МКЗПР?
Критериями модели МКЗПР называются показатели:
1.признанные ответственным руководителем, как характеристики
степени достижения подцелей или поставленной цели;
2.являющиеся общими и измеримыми для всех допустимых решений;
3.характеризующие общую ценность решений, для того, чтобы руко-
водитель мог получить по ним наиболее предпочтительные оценки.
5. Что представляет собой шкалакритериев, какми они бывают?
Для каждого критерия заданна шкала,представленная множеством
упорядоченных оценок. Шкалы могут быть числовами и нечисловыми.
6. Что такое набор (система)предпочтений?
Сравнивая всевозможные варианты решений,руководитель обычно имеет
неструктуированныепредставления о достоинствах и недостатках срав-
ниваемыхрешений. Совокупность всех этих представлений и называется
системой предпочтений.
7. Как определить решающееправило и его назначение?
Решающее правило (или метод принятия решения) — есть принцип срав-
нения векторных оценок и вынесения предпочтения.Основное назначение
решающего правила - выносить суждения о предпочтительности одних
векторных оценок перед другими, а также упорядочить множество всех
допустимых решений.
8. Какие допущения приняты вмодели МКЗПР?
В модели МКЗПР приняты следующие допущения:
1. ополноте множества решений и набора критериев;
2. ободнозначности соответствия множества шкал множеству критериев;
3. одостаточной точности оценки решений по шкалам критериев;
4. онаборе предпочтений, возможностях его выявления.
9. Какие этапы можно выделить впроцессе создания модели?
В чем ихсущность?
I. Постановка задачи: установления видатребуемого упорядочения вариантов
решений, цели предстоящего исследования, cодержательного значения поня-
тия«вариант решения»;
II. Формирование множества допустимых вариантоврешений:
а)проверяется возможность их применения для достижения цели;
б) установливается смысл понятия «допустимость»;
в)разрабатывается способ проверки допустимости вариантов решений и
выявляется их множества;
III. Формирование набора критериев:
а)проводится анализ последствий выделенных вариантов решений;
б)определяется перечень показателей, характеризующих последствия;
в)формируется набор критериев для характеристики этих последствий.
IV. Разработка оценочных шкал критериев: длякаждого критерия учитывают-
сяразличия в интенсивности соответствующего свойства у допустимых вари-
антов ивлияния различных интенсивностей этого свойства на общее предс-
тавлениеокачестве решений.
V. Оценка допустимых вариантов решений по шкаламкритериев:
Наданном этапе может быть:
а)неоднозначность смысла некоторых критериев;
б) ихкомплексный характер;
в)излишняя деятельность или неконкретность оценок;
г)неоднозначность смысла качественных оценок некоторых шкал.
VI. Получение и уточнение информации опредпочтениях: полученная инфор-
мация характеризует влияние изменений оценок по шкалам критериев на
общее качество решения.
VII. Построение решающего правила: проверяемаяинформация о предпочте-
нияхиспользуется ответственнымруководителем для построения соответст-
вующегорешающего правила.
VIII. Упорядочение дополнительных вариантоврешений: на основе построен-
ногорешающего правила происходит сравнение и упорядочение вариантов
решений.
IX. Анализ результатов упорядочения.
X. Проверка условия: удовлетворительно липроведенное упорядочение...
если «да», тогда следует проверка — соответствуетли полученное упорядо-
чениепоставленной задаче (в пункт XI);
если «нет», то анализ причиннеудовлетворительности и установление вида
необходимых корректив.
XI. Проверка соответствия поставленной задачиполученному упорядочению:
«соответствует» — конец решения; «нет» — возвращение в (VI) или в (I).
10. В чем сущностьморфологического анализа для формирования МДВР?
Сущность морфологического анализа заключается втом, что решаемая про-
блемаразделяется на ряд уровней, для каждого из которых определены воз-
можныеспособы решения.
11. Каким требованиям долженудовлетворять набор критериев в МКЗПР?
а)Полнота: множество критериев из N полное, если, зная значение
n-мерного вектора оценок по ним, принимающий решение имеет
представление о степени достижения главной цели;
б) Операциональность: каждый критерий должен иметь понятную
формулировку, однозначный смысл, и характеризовать определен-
ные последствия;
в) Декомпозируемость: нужна для упрощения задачи оценки предпоч-
тений на множестве исходов, через разделение на подзадачи;
г) Неизбыточность: различные критерии из множества критериевне
должны учитывать одинаковых последствий;
д) Измеримость: каждый критерий должен допускатьвозможность
оценки интенсивности характеризуемого им свойства;
е)Минимальность: набор критериев должен содержать как можно
меньше критериев.
12. Какие методы применяются дляоценки вариантов решений по
шкалам критериев?
Методы:
-физические измерения: измерения физических и технических па-
раметровиопределение значений материальных технико-экономических
и других показателей;
-экспертные методы: разными специалистами даются различные ха-
рактеристикииоценки одному и тому же варианту решения и по одина-
ковойшкале (в том случае, когда варианты решений нельзя измерить
физически).
13. В чем проявляются затрудненияпри выявлении набора предпочтений?
а) Напрактике очень трудно получить, например информацию о пред-
почтениях. При получении усложненных утвержденийо решении, уверен-
ностьвобъективности этих утверждений уменьшается;
б) Напрактике могут возникать противоречия в высказываниях менед-
жера, нообнаружить их в информации о предпрочтениях сложно;
в)Некоторые предпочтения могут изменяться и приводить к противо-
речивости суждений при окончательном принятиирешения.
14. Как различаются решающиеправила МКЗПР?
В чем сущность их построения?
Решающие правила различаются по:
1.Принципам построения:
†аксиоматический:
основан на принятии аксиом о множестве решений, о структуре
предпочтений принимающего решения, овозможности получе-
ния каких-либо видов информации относительнопредпочтений;
†эвристический:
конкретная схема построения решающего правила определенного
вида
2.Процедурам построения:
†одношаговые: основанные на однократном использовании реша-
ющего правила;
†многошаговые: основанные на многократном использовании реша-
ющего правила и позволяют сочетатьисследование математичес-
ких моделей с опытом и интуицией того, ктопринимает решения.
3.Назначению:
решающие правила приводят к полному или частичному упорядоче-
ниюМДВП.
«Введение в алгоритмизацию»
1. Что называется алфавитом,словом, языком?
Алфавитомназывается конечное множество, состоящее из четко различимых символов. Словом
в алфавите называется любаяконечная последовательность из его символов. Количество симво-ловв этой последовательности называется длинной слова. Языкомназывается множество слов
в некотором алфавите.
2. Что означает: алгоритм — предписание на каком-то языке?
Алгоритм — точное предписание на каком-то языке, однозначно приводящее от изменяющихсяисходных данных к искомому результату.Это определение не является строго научным и то,
что алгоритм — предписание накаком-то языке, означает: алгоритм — слово из языка.
3. Какие требования предъявляютсяк алгоритму?
Алгоритм при выполнении недолжен зависеть от любого произвольного решения пользователя, от его выбора, от случайности, и не должен содержать неопределённости. Алгоритм должен
быть применим к любымвариантам исходных данных. Исходнымиданными для алгоритма и
результатом его выполнениямогут быть числа и другие объекты, обязательно задаваемые словами. Типрезультата, который выдает алгоритм, должен быть заранее описан.
4. Что называется конечнойалгоритмически (не)разрешимой задачей?
Конечнойназывается задача, если все объекты, которые в ней могут быть икоторые нужно
найти, задаются словами в исходных алгоритмах. Алгоритмически разрешимой называется
конечная задача, еслисуществует алгоритм, когторый по данному ґ отвечает «да», если верно Q(ґ), и отвечает «нет» если верно ¬Q(ґ) — «неQ». Или существует алгоритм готорый по ґ
строит ґ',и для него верно Q(ґ, ґ').Если таких алгоритмов нет (не существуют или невозмож-ны),то конечная задача называется алгоритмически неразрешённой.
Примечание:Алгоритмическая (не)разрешенность относятся только кконкретным задачам.
5. Как обозначается (не)применимостьалгоритма к исходным данным?
Применимостьалгоритма к исходным данным ф называется! А(ф), а результат работы над ф
— А(ф).Если алгоритм А неприменим к исходнымданным ф (ихнедостаточно для выполне-
ния какого-либо шага алгоритма А или они приводятк противоречивым действиям, или А
работает неограниченнодолго (например зациклившись), или по каким-то другим причинам,
то его обозначают ¬! А(ф).
6. Как выполняется и обозначается А с любым вариантом исх. данных?
АлгоритмА выполняется с любым вариантом исходных данных (например ф) отдельными
итерациями(то есть дозами или порциями), каждая из которых состоит из несколькихшагов. L(А, ф) — общее количество шагов на всехитерациях при использовании алгоритма А для исходных даннахф, если! А(ф). Если же ¬А(ф), то L(А, ф) неопределена.
7. Что такое сложность алгоритма, переборный алгоритм, алгоритм
показательно-степенной сложности, память алгоритма?
Сложностьюалгоритма А называется величина при фиксированном А и при произвольном ф
(она является частично определённой функцией). Переборным называеся алгоритм, если
L(А, ф)=22|ф|, где |ф| — длинна слова ф (исходныхданных). Алгоритмом показательной
сложностиназывается алгоритм,если L(А, ф)=C|ф|, где С является любой константой.
Памятьюалгоритма называетсяего способность учитывать его работу на предыдущих
этапах. Бывают алгоритмы не имеющие памяти (комбинационные схемы), с конечной
памятьюфиксированного объема (автоматы) и обладающие ни чем не ограниченной
памятью, которыерешают любую алгоритмическую задачу (машина Тьюринга).
Тема№ 15
«Введение в теориюмножеств»
1. Что означает понятие«множество»?
Понятие «множество» — одно из многихматематических понятий (множество решений проблем,
множество геометрических точек, множество людей).По определению математика Георга Кан-
тора, создателя теории множеств, — множество- есть многое, мыслимое неми как единое. Мно-
жествосамое широкое понятие математики и логоки. Другоеопределение, данное Г. Кантором
выглядит так: «множество — это объединение вединое целое элементов, хорошо различимых
нашей интуицией или мыслями»
2. Какие знаки применяются длязаписи множества?
Элементы множества и обозначаются заглавнымибуквами латинского алфавита A..Z и могут
сами быть множествами.
x є Z - x принадлежитмножеству Z
3. Как можно задавать множество?
Множество может быть заданно по-разному, например{X} обозначает множество Х, или мно-
жествоможно задать указывая какое-либо свойство Q(х),которым обладают все элементы дан-
ногомножества и только они.
X = {x|Q(x)|} Множество тех х,что Q(x)
Множество всех натуральных чисел меньше 10 можнообозначить следующим образом:
X1 = {2, 4, 6, 8}; Q1(x) = (x є R, x div 2 = 0, x
4. Как можно задавать множество?
Множество Y называется подмножеством X, если оносодержит только элементы входящие в
множество X. Строгим подмножеством X называетсяY, если Y является подмножеством X, но
не равно ему. Конечным называется множество,состоящее из конечного количества элементов.
Бесконечное множество состоит из элементов,количество которых бесконечно.
5. Как записать равные множества?
Равные множества X и Y, можно записать следующимобразом X = Y.
6. Как множество называетсяструктурой?
Структурой называется множество, элементыкоторого являются объектами разных типов. Нап-
римерзапись (Record) в языке Паскаль является структурой,так как она под одним логичес-
кимименем объединяет объекты разного типа. Структуру можно обозначить так:
X ={1..9, A..N, µ2 -ћn}
7. Что называется группой множеств?
Группой называется множество X, на которомопределена операция, сопостовляющая любым x и y (элементам этогомножества), элемент zиз того же множества. Предположим, что x и yявляются элементами, принадлежащими множеству X. Сопоставим эти элементы с элементом z,принадлежащиму тому же множеству, тогда (если они сопоставимы, томножество Х является группой. При этом злемент z может быть обозначен как (x+y)или (x*y). Длягруппы должны быть выполнимы обычные свойства сложения и умножения.
8. Когда выполняется выбормножества и структкры в сложной системе?
Выбором множества и структуры сложной системы, называется выбор,который отражает все реально существующие отношения между элементамиданной системы. Этот выбор производитсяесли задача поставлена математически. От того как сделан выбора частозависит результат исследования.
9. Какие операции выполняются надмножествами?
Над множествами выполняются следующие операции:
а) объединение множеств- результатом является множество, состоящее из всех злемен-тов,принадлежащих хотя бы одному из исходных (объединенных) множеств.
б) пересечение — полученное множество состоит из всех элементов исходных множеств.
в) взятие разности — разностью множеств X и Y является множество, составленное из
элементов, которые входя в X, но не входят в Х.
Copyright©1994 by Vsevolod Ukrainsky.