МОСКОВСКИЙ ГУМАНИТАРНО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ
Калужский филиал
Юридический факультет
Кафедра гражданско-правовых дисциплин
Контрольная работа
по учебному курсу
«Математические методы анализа и принятия решений»
Выполнил: Титов Е.А.
студент 4-го курса
группа ЮЗВС-08
Руководитель:
Махмудов Н.Р.
Калуга — 2010 г.
План
Статистический подход к измерению правовой информации
Графический метод решения задач линейного программирования
Методика решения задач ЛП графическим методом
Список используемой литературы
Статистический подход к измерению правовойинформации
Статистический подход изучаетсяв разделе кибернетики, называемом теорией информации. Его основоположникомсчитается К. Шеннон, опубликовавший в 1948 году свою математическую теориюсвязи. Большой вклад в теорию информации до него внесли ученые Найквист иХартли.
В 1924 и 1928 гг. ониопубликовали работы по теории телеграфии и передаче информации. Признаны вовсем мире исследования по теории информации российских ученых А.Н. Колмогорова,А.Я. Хинчина, В.А. Котельникова, А.А. Харкевича и др.
К. Шенноном было введено понятиеколичество информации как меры неопределенности состояния системы, снимаемойпри получении информации.
Количественно выраженнаянеопределенность состояния получила название энтропии по аналогии с подобнымпонятием в статистической механике.
При получении информацииуменьшается неопределенность, т.е. энтропия, системы. Очевидно, что чем большеинформации получает наблюдатель, тем больше снимается неопределенность, иэнтропия системы уменьшается.
При энтропии, равной нулю, осистеме имеется полной информация, и наблюдателю она представляется целикомупорядоченной. Таким образом, получение информации связано с изменением степенинеосведомленности получателя о состоянии этой системы.
До получения информации ееполучатель мог иметь некоторые предварительные (априорные) сведения о системе Х.
Оставшаяся неосведомленность иявляется для него мерой неопределенности состояния (энтропией) системы. Обозначимаприорную энтропию системы Х.
После получения некоторогосообщения наблюдатель приобрел дополнительную информацию уменьшившую егоначальную неосведомленность.
Другими словами, количествоинформации измеряется уменьшением (изменением) неопределенности состояниясистемы.
Вероятность p — количественнаяаприорная (т.е. известная до проведения опыта) характеристика одного из исходов(событий) некоторого опыта. Измеряется в пределах от 0 до 1.
Если заранее известны все исходыопыта, сумма их вероятностей равна 1, а сами исходы составляют полную группусобытий.
Если все исходы могут свершитьсяс одинаковой долей вероятности, они называются равновероятными.
Например, пусть опыт состоит всдаче студентом экзамена по информатике.
Очевидно, у этого опыта всего 4исхода (по количеству возможных оценок, которые студент может получить наэкзамене).
Тогда эти исходы составляютполную группу событий, т.е. сумма их вероятностей равна 1. Если студент училсяхорошо в течение семестра, значения вероятностей всех исходов могут быть такими:
p (5) = 0.5; p (4) = 0.3; p (3) =0.1; p (2) = 0.1, где запись p (j) означает вероятность исхода, когда полученаоценка j (j = {2, 3, 4, 5}).
Если студент учился плохо, можнозаранее оценить возможные исходы сдачи экзамена, т.е. задать вероятностиисходов, например, следующим образом: p (5) = 0.1; p (4) = 0.2; p (3) = 0.4; p(2) = 0.3.
В обоих случаях выполняетсяусловие:
/>
где n — число исходов опыта,
i — номер одного из исходов.
Пусть можно получить n сообщенийпо результатам некоторого опыта (т.е. у опыта есть n исходов), причем известнывероятности получения каждого сообщения (исхода) — pi.
Тогда в соответствии с идеейШеннона, количество информации I в сообщении i определяется по формуле:
I = — log2 pi,
где pi — вероятность i-госообщения (исхода).
Пример 1. Определить количествоинформации, содержащейся в сообщении о результате сдачи экзамена длястудента-хорошиста.
Пусть I (j) — количествоинформации в сообщении о получении оценки j. В соответствии с формулой Шеннонаимеем:
I (5) = — log20,5 = 1,I (4) = — log2 0,3 = 1,74,I (3) = — log2 0,1 = 3,32
I (2) = — log2 0,1 = 3,32.
Пример 2. Определить количествоинформации, содержащейся в сообщении о результате сдачи экзамена для нерадивогостудента:
I (5) = — log20,1 = 3,32,I (4) = — log2 0,2 = 2,32,I (3) = — log2 0,4 = 1,32,I (2) = — log2 0,3 = 1,74.
Таким образом, количествополучаемой с сообщением информации тем больше, чем неожиданнее данное сообщение.Этот тезис использован при эффективном кодировании кодами переменной длины(т.е. имеющими разную геометрическую меру): исходные символы, имеющие большуючастоту (или вероятность), имеют код меньшей длины, т.е. несут меньшеинформации в геометрической мере, и наоборот.
Формула Шеннона позволяетопределять также размер двоичного эффективного кода, требуемого дляпредставления того или иного сообщения, имеющего определенную вероятностьпоявления.
Помимо информационной оценкиодного сообщения, Шеннон предложил количественную информационную оценку всехсообщений, которые можно получить по результатам проведения некоторого опыта. Так,среднее количество информации Iср, получаемой со всеми n сообщениями,определяется по формуле:
/>
где pi — вероятность i-госообщения.
Пример 3. Определить среднееколичество информации, получаемое студентом-хорошистом, по всем результатамсдачи экзамена.
В соответствии с приведеннойформулой имеем:
Iср = — (0,5*log20,5 + 0,3*log20,3 + 0,1*log20,1 + 0,1*log20,1) = 1,67.
Пример 4. Определить среднееколичество информации, получаемое нерадивым студентом, по всем результатамсдачи экзамена.
В соответствии с приведеннойформулой имеем:
Iср = — (0,1*log20,1 + 0,2*log20,2 + 0,4*log20,4 + 0,3*log20,3) = 1,73.
Большее количество информации,получаемое во втором случае, объясняется большей непредсказуемостью результатов:в самом деле, у хорошиста два исхода равновероятны.
Пусть у опыта два равновероятныхисхода, составляющих полную группу событий, т.е. p1 = p2 = 0,5. Тогда имеем всоответствии с формулой для расчета I ср:
I ср = — (0,5*log20,5 +0,5*log20,5) = 1.
Эта формула есть аналитическоеопределение бита по Шеннону: это среднее количество информации, котороесодержится в двух равновероятных исходах некоторого опыта, составляющих полнуюгруппу событий.
Единица измерения информации пристатистическом подходе — бит.
На практике часто вместовероятностей используются частоты исходов. Это возможно, если опыты проводилисьранее и существует определенная статистика их исходов. Так, строго говоря, впостроении эффективных кодов участвуют не частоты символов, а их вероятности
Введенная количественнаястатистическая мера информации широко используется в теории информации дляоценки собственной, взаимной, условной и других видов информации.Графический метод решения задач линейногопрограммирования
Теоретическое введение.
Графический метод довольно прости нагляден для решения задач линейного программирования с двумя переменными. Оноснован на геометрическом представлении допустимых решений и ЦФ задачи.
Каждое из неравенств задачилинейного программирования определяет на координатной плоскости /> некоторую полуплоскость(рис.1), а система неравенств в целом — пересечение соответствующих плоскостей.Множество точек пересечения данных полуплоскостей называется областьюдопустимых решений (ОДР.). ОДР всегда представляет собой выпуклуюфигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежатэтой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может бытьпредставлена выпуклым многоугольником, неограниченной выпуклой многоугольнойобластью, отрезком, лучом, одной точкой. В случае несовместности системыограничений задачи (1) ОДР является пустым множеством.
Все вышесказанное относится и кслучаю, когда система ограничений (1) включает равенства, поскольку любоеравенство
/>
можно представить в виде системыдвух неравенств (см. рис.1)
/>
ЦФ /> прификсированном значении /> определяет наплоскости прямую линию />. Изменяязначения L, мы получим семейство параллельных прямых,называемых линиями уровня.
Это связано с тем, что изменениезначения L повлечет изменение лишь длины отрезка,отсекаемого линией уровня на оси /> (начальнаяордината), а угловой коэффициент прямой /> останетсяпостоянным (см. рис.1). Поэтому для решения будет достаточно построить одну излиний уровня, произвольно выбрав значение L.
Вектор /> с координатами изкоэффициентов ЦФ при /> и /> перпендикулярен к каждойиз линий уровня (см. рис.1). Направление вектора /> совпадаетс направлениемвозрастания ЦФ, что является важным моментом для решениязадач. Направлениеубывания ЦФ противоположно направлению вектора/>.
Суть графического методазаключается в следующем. По направлению (против направления) вектора /> в ОДР производится поископтимальной точки />. Оптимальнойсчитается точка, через которую проходит линия уровня />, соответствующаянаибольшему (наименьшему) значению функции />.Оптимальное решение всегда находится на границе ОДР, например, в последнейвершине многоугольника ОДР, через которую пройдет целевая прямая, или на всейего стороне.
При поиске оптимального решениязадач линейного программирования возможны следующие ситуации: существуетединственное решение задачи; существует бесконечное множество решений (альтернативныйоптиум); ЦФ не ограничена; область допустимых решений — единственная точка; задачане имеет решений.
/>
Рисунок 1. Геометрическаяинтерпретация ограничений и ЦФ задачи.
Методика решения задач ЛП графическим методом
В ограничениях задачи заменитьзнаки неравенств знаками точных равенств и построить соответствующие прямые.
Найти и заштриховатьполуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этогонужно подставить в конкретное неравенство координаты какой-либо точки [например,(0; 0)], и проверить истинность полученного неравенства.
Если неравенствоистинное,
то надо заштриховатьполуплоскость, содержащую данную точку;
иначе (неравенство ложное)надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку /> и /> должны бытьнеотрицательными, то их допустимые значения всегда будут находиться выше оси /> и правее оси />, т.е. в I-мквадранте.
Ограничения-равенства разрешаюттолько те точки, которые лежат на соответствующей прямой. Поэтому необходимовыделить на графике такие прямые.
Определить ОДР как частьплоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее.При отсутствии ОДР задача не имеет решений.
Если ОДР — не пустое множество,то нужно построить целевую прямую, т.е. любую из линий уровня /> (где L — произвольноечисло, например, кратное /> и />, т.е. удобное для проведениярасчетов). Способ построения аналогичен построению прямых ограничений.
Построить вектор />, который начинается вточке (0; 0) и заканчивается в точке />. Еслицелевая прямая и вектор /> построеныверно, то они будут перпендикулярны.
При поиске максимума ЦФнеобходимо передвигать целевую прямую в направлении вектора />, при поиске минимума ЦФ — противнаправления вектора />. Последняяпо ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такойточки (точек) не существует, то можно сделать вывод о неограниченности ЦФ намножестве планов сверху (при поиске максимума) или снизу (при поискеминимум).
Определить координаты точки max (min) ЦФ /> и вычислить значение ЦФ />. Для вычисления координатоптимальной точки /> необходиморешить систему уравнений прямых, на пересечении которых находится />.
Задача. Правоохранительныеорганы разработали 10 программ по борьбе с преступлениями в сфере экономики,причем среди этих программ есть одинаковые: 5 одинаковы по одним свойствам, 3программы по другим свойствам и 2 программы одинаковы по третьим свойствам. Сколькимиспособами эти программы могут быть переставлены?
Ответ.5*3*2 =30
Список используемой литературы
1. Аветисян Р.Д., Аветисян Д.В. Теоретические основы информатики. — М.: РГГУ,1997.
2. Гришкин И.И. Понятие информации. Логико-методологический аспект. — М.: Наука,1973.
3. Дмитриев В.И. Прикладная теория информации. — М., 1989.
4. Седов Е.А. Эволюция и информация. — М.: Наука, 1976.
5. Смородинский С.С., Батин Н.В. — Оптимизация решений на основе методов.
6. Кононов В.А. — Исследование операций. Для продвинутых математиков.
7. Чернавский Д.С. Синергетика и информация. — М.: Знание, 1990.