ЛЕКЦИЯ №1. ТЕОРИЯ ИНФОРМАЦИИ.

Контрольные вопросы к лекции 12

Контрольные вопросы к лекции 11

1. Что включает в себя простейшая схема принятия решений?

2. Что такое цель?

3. Что такое критерий оптимальности?

4. Что такое однокритериальная ЗПР?

5. Что такое многокритериальная ЗПР?

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

7. Напишите общий вид математической модели формирования оптимальных решений.

8. Сформулируйте задачу принятия решений.

9. Запишите критерий минимального расхода материала для задачи о баке.

10. Запишите критерий минимальной трудоемкости для задачи о баке.

11. Запишите общий вид функции Лагранжа.

12. Перечислите недостатки аналитического метода условной оптимизации.

Во многих задачах принятия решений имеется несколько целей, которые хочет достичь ЛПР. Такие задачи сводятся к многокритериальным задачам вида:

где Х (х₁, х₂,…х_n) – вектор решений.

Наибольшее распространение на практике решения таких задач получил подход, связанный с работами итальянского математика-экономиста Викторио Парето. Он обеспечивает ЛПР возможность гибкого принятия решений. При оптимизации по Парето строится множество «неулучшаемых» решений, изменение каждого из которых ухудшает значение целевых функций f₁(X), f₂(X),…, f_k(X).

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

(4.12)

(4.13)

Условия (4.13) определяют множество допустимых решений и образуют на плоскости х₁Ох₂ некоторую область, каждой точке С которой соответствует точка С* в пространстве значений критериев W₁OW₂ (Рис. 4.4). Ее координаты вычисляются по формулам (4.12) при х₁ = х₁^С; х₂ = х₂^С:

Рассмотрим в множестве значений критериев четыре точки A*, B*, D* и С*
(см. рис. 4.4). Точка А* является оптимальной для критерия W₂ = f(x₁,x₂), так как в этой точке критерий W₂ имеет максимальное значение. Аналогично точка В* является оптимальной для критерия W₁ = f(x₁, x₂). Точка С* является «заведомо плохой» точкой, она не является оптимальной ни для одного критерия, так как в области значений критериев можно найти «более лучшую» точку D* такую, что Для точек A*, B*, D* более «лучших» точек в пространстве значений критериев не существует. Такие точки составляют множество решений, оптимальных по Парето в пространстве значений критериев. В нашем случае это точки кривой A*D*B*. Для выделения «лучших» (неулучшаемых) точек используется понятие конуса K_i с вершиной в точке ()
(Рис. 4.5). Уравнения этого конуса имеют вид:

Правило выделения «лучших» точек:

Если в конусе K_i лежит хотя бы одна точка (), то она является более предпочтительной, чем точка () (см. рис. 4.5).

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

Для нашего примера конусы, построенные во всех точках кривой A*D*B*
(см. рис. 4.4), являются пустыми. Строя обратное отображение этих точек в пространство решений Х, можно получить множество искомых решений (кривая АВ на рис 4.4), оптимальных по Парето. Такое множество называется множеством компромиссов, множеством эффективных точек или множеством Парето. Построив множество компромиссов, ЛПР выбирает в нем из неформальных соображений некоторую точку, которая является наилучшим компромиссом, по мнению ЛПР.

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

Вернемся к рассмотренной в п. 4.5 задаче о баке, описанную формулами (4.5) – (4.8), и попробуем найти паретооптимальное ее решение. Для этого введем параметры
a₁ > 0 и a₂ > 0, удовлетворяющие условию a₁ + a₂ = 1, и построим линейную свертку критериев (4.5) и (4.8):

. (4.14)

Положим a₁ = 1, тогда a₂ обращается в ноль, свертка (4.14) принимает вид
F(X) = S(X) и задача превращается в однокритериальную. Решив эту задачу, найдем оптимальную точку X_S для обеспечения минимального расхода материала. Теперь положим
a₁ = 0, тогда a₂ = 1, свертка (4.14) примет вид F(X) = T(X). Решив эту однокритериальную задачу, найдем оптимальную точку X_T, обеспечивающую минимальную трудоемкость изготовления бака. Если провести аналогию с рис. 7.4, то X_S соответствует точке А, X_T соответствует точке В. Чтобы определить промежуточные точки (остальные компромиссные решения), введем обозначение a = a₁. Тогда a₂ = 1 – a. Формула (4.14) примет вид . Или:

.

Функция Лагранжа запишется в виде

.

Распишем функцию Лагранжа подробнее:

.

Чтобы найти минимум функции Лагранжа, нужно взять от нее производные по искомым переменным r, h, l и приравнять их к нулю.

(4.15)

Получили систему трех алгебраических уравнений, решив которую найдем зависимость r, h, l от a. Задавая a от 0 до 1, получим множество решений, оптимальных по Парето. Поскольку аналитически решить систему (4.15) довольно сложно, можно воспользоваться любым численным методом, задавая предварительно значения a с любым приемлемым шагом.

Рис. 4.6

ЛПР выбрал из этого множества точку при a = 0,4, при котором S = 2601; T = 802;
r = 10,44; h = 29,2. Эта точка устроила его потому, что при дальнейшем увеличении a
S уменьшается уже незначительно и Т имеет наименьшее значение из всех последующих.

1. Какие решения называются паретооптимальными?

2. Сформулируйте правило выделения лучших точек.

3. Что такое множество компромиссных решений?

4. Как получить множество компромиссных решений?

5. Запишите функцию Лагранжа для двухкритериальной задачи о баке.

6. Как найти минимум функции Лагранжа?

Рубежный контроль 2

1.1 Понятие видов информации.

В интересах технических проблем удобно информацию классифицировать по структурно-метрическим свойствам.

Событие- это первичный и неделимый двоичный элемент информации. Как правило, это выбор из двух возможных состояний. Учитывая двоичный характер события, условно его можно представить в геометрической символике точкой или пробелом, в арифметике- 0 или 1, в сигнальной- импульсом или паузой. Еще говорят, что событие- это категория нулевой меры. Все другие категории информации могут быть представлены как совокупность отдельных событий.

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

1.2 Основные понятия комбинаторики.

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

1.Перестановка.

Q_n = n! ( без повторений элементов)

Правило организации перестановок: комбинации отличаются порядком следования элементов и не зависит от состава.

Q_nn=

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

Q_c=(без повторений элементов)

Q_c=

3. Размещения

Q_p =(без повторений элементов)

Q_p =

Главное свойство размещений в том, что комбинации отличаются как составом элементов, так и порядком их следования.

1.3 Случайные модели в теории информации.

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

Пусть А – некоторое событие, P(A)- вероятность этого события.

Если , а событие U=1,тогда U-достоверное, а события A_i образуют полную группу событий.

Если ,,V-невозможное, то А и B являются несовместными.

-обратные, если они несовместные и образуют полную группу.

Пусть N-серия опытов, , N-большое.

Во многих случаях случайное событие А является следствием происхождения некоторой совокупности

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

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

Пусть – дискретная случайная величина.

p_i

x

x₁ x₂ ……x_i....x_n

Функция распределения:

Свойства :

1..

2., если x₂ ≥ x₁.

3.

Математическое ожидание:(ДСВ)

Дисперсия: (ДСВ)

Чаще используют плотность распределения информации, которая является дифференциальной функцией распределения вероятности:

Свойства плотность распределения:

1. ≥ 0.

2. .

3. .

(HCB)

(HCB)

1.4 Основные понятия теории информации

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

В России эта программа была принята в 1989 году. Её завершение планировалось в 2050-е годы. Если страна с любым уровнем индустриального развития опоздает с информатизацией всех сфер жизни, то она переходит в разряд стран третьего мира.

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

Теория информации (ТИ) – это наука о получении, накоплении, преобразовании, отображении и передачи информации.

В теории информации можно выделить три направления:

1. Структурная теория - рассматривает структуру построения информационных сообщений, массивов и их измерения подсчетом информационных элементов или комбинаторным методом. Основной структурной единицей информации считается квант.

2. Статистическая теория - оценивает информацию с точки зрения мер неопределенности. В этой теории оперируют понятием энтропии, которая учитывает вероятностные свойства и характеристики информационных элементов.

3. Семантическая теория - занимается изучением смысловых характеристик информации (ценность, содержательность информации).

Строго говоря, наука теории информации состоит из:

1. ТИ, где рассматривают характеристики информационных сообщений, меры измерения информации, а также модели и методы описания сообщений и их свойства.

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

3. Прикладная ТИ – рассматривает модели и способы организации базовых информационных процессов.

Возникновение ТИ, как науки, связано с появлением работы К.Шеннона « Математическая теория связи» в 1948 году. В 1933 году Котельников предложил теорию представления непрерывной функции виде её дискретных отсчетов.

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

Этапы обращения информации:

Информационная система (ИС) - есть совокупность средств (аппаратных и программных), реализующих базовые информационные процессы для достижения определенных целей. К базовым процессам относятся процессы, реализующиеся на этапах обращения информации. Если ИС включает в свой состав человека, то её называют автоматизированной. Если в ней не присутствует человек, то - автоматической. Если ИС связана с управлением, то её называют системой управления. В системах управления выделяют автоматизированные системы управления (АСУ) и систему автоматического управления (САУ).