МОСКОВСЬКИЙ ГУМАНІТАРНО-ЕКОНОМІЧНИЙ ІНСТИТУТ
Калузький філія
Юридичний факультет
Кафедра цивільно-правових дисциплін
Контрольна робота
за навчальним курсом
"Математичні методи аналізу і прийняття рішень"
Виконав: Титов Е.А.
студент 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) = - log2 0,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) = - log2 0,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
Список використаної літератури
Аветисян Р.Д., Аветисян Д.В. Теоретичні основи інформатики. - М.: РДГУ, 1997.
Грицьків І.І. Поняття інформації. Логіко-методологічний аспект. - М.: Наука, 1973.
Дмитрієв В.І. Прикладна теорія інформації. - М., 1989.
Сєдов Е.А. Еволюція та інформація. - М.: Наука, 1976.
Смородинський С.С., Батин Н.В. - Оптимізація рішень на основі методів.
Кононов В.А. - Дослідження операцій. Для просунутих математиків.
Чернавський Д.С. Синергетика та інформація. - М.: Знание, 1990.