- •1. Структурная схема микропроцессора (на примере i8086). Назначение регистров.
- •3. Организация основной памяти.
- •3. Структура и характеристики оперативной памяти
- •4. Модель osi
- •5. Стек протоколов tcp/ip
- •6. Классификация компьютерных сетей
- •7. Данные и модели данных
- •8. Модель данных «сущность-связь»
- •Ограничения целостности
- •9. Реляционная модель данных
- •10. Основные направления исследования в области ии
- •11. Метод резолюции в лппп.
- •12. Продукционная модель
- •13. Основные парадигмы языков программирования.
- •14. Основные понятия ооп: инкапсуляция, наследование, полиморфизм
- •1. Инкапсуляция
- •2. Полиморфизм
- •3. Наследование
- •15. Понятие алгоритма.
- •16. Понятие о временной и емкостной сложности алгоритма
- •17. Машина Тьюринга: детерминированная и недетерминированная
- •18. Понятие формального языка и формальной грамматики
- •19. Основные понятия теории графов.
- •20. Понятие количества информации и энтропии. Теорема Шеннона.
- •21. Деревья в теории графов.
- •22. Модели линейного программирования (постановка задачи, математическая модель, решение графическим методом).
- •23. Двойственность в задачах линейного программирования.
- •25. Элементы теории игр.
- •2. Подпрограммы. Процедуры и функции
- •3. Массивы
- •4. Записи
- •5. Работа с Динамическими данными
- •6. Динамические структуры данных. Линейные списки.
- •7. Динамические структуры данных: двоичные деревья
- •8. Работа с файлами
- •9.Операции целочисленной арифметики
- •10. Системы счисления. Перевод чисел из одной системы счисления в другую
- •11. Язык sql. Назначение и основные команды.
- •Манипулирование данными
- •Простые запросы
- •12. Алгоритмы внутренней сортировки.
- •13. Алгоритмы внешней сортировки
- •14. Нахождение кратчайших путей в графе
- •15. Поиск в ширину
- •16. Поиск остова и минимального остова.
- •17. Линейная модель работы информационно-поисковой системы.
- •18. Хеширование
- •Основные достоинства в-дерева
- •20. Логические вопросно-ответные системы:выполнение запросов различных типов.
- •21. Поиск в семантической сети.
- •22. Принципы динамического программирования. Иллюстрация на примере.
- •23. Адресация в Интернете
- •Доменные имена
- •Общий вид формата url-адреса
- •Как работает dns-сервер
- •24. Основные сервисы в сети Интернет.
- •Word Wide Web (www) - "Всемирная паутина"
- •Поиск информации в сети
- •VoIp сервис
- •Мессенджеры
- •25. Использование html. Структура Web(html) страницы.
23. Двойственность в задачах линейного программирования.
Любой задачи линейного программирования (исходной или прямой) можно поставить в соответствие другую задачу, которая называется двойственной или сопряженной. Обе эти задачи образуют пару двойственных задач линейного программирования. Каждая из задач является двойственной в другой задаче в рассматриваемой паре. Составим двойственную задачу к задаче использования сырья.
Имеется m видов сырья в количестве b1 , b2 , ……, bm , которые используются для изготовления n видов продукции.
aij – расход i-го вида сырья на 1 j вид продукции
cj – прибыль при реализации 1 j вида продукции
составить план выпуска продукции обеспечит максимальную прибыль.
Матем. модель
z=c1x1+c2x2+….+ cnxn → max (1)
н абор ограничений
a11x1+a12x2 +…..+a1nxn≤b1; (y1)
a21x1+a22x2+……. +a2nxn ≥b2; (y2)
. . . . . . ;
am1x1+am2x2+……. +amnxn ≥bm (ym)
xj>=0 j=1…n (3)
xj-V производства j вида продукции
предположим что второй производитель хочет перекупить сырье, составим двойственную задачу, решение которой позволит определить условие продажи сырья.
Введем вектор оценок (цен) видов сырья
Y=(y1,…..,ym)
Затраты на приобретение i вида сырья в количестве bi=biyi
Второму производителю выгодно min суммарные затраты на приобретение всех видов сырья.
Целевая функция имеет вид
F(y) = b1y1 +……+bmym →min
П ервому производителю не выгодно продавать сырье если суммарная стоимость всех видов сырья расходуемых на каждое изделие j продукции т.е. a1jy1+a2jy2+…..+ amjym меньше прибыли cj получаемой при реализации этого изделия. Система ограничений задачи имеет вид.
a11y1+a12y2 +…..+am1ym≤c1; (y1)
a21y1+a22y2+……. +am2ym ≥c2; (y2)
. . . . . . ;
a1ny1+a2ny2+……. +amnym ≥cn (ym)
Оцевидно что оценки видов сырья yi>=0 i=1…n
Связь исходной и двойственной задач состоит в том что коэффициенты cj целевой функции исходной задачи является свободными членами системы ограничений двойственной задачи, свободные члены bi ограничений исходной задачи служат коэффициенты целевой функции двойственной задачи. Матрица коэффициентов системы ограничений двойственной задачи является транспортной матрицей коэффициентов системы ограничений исходной задачи. Рассматриваемая пара задач относится к симметричным парам двойственных задач, в теории двойственности используются 4 пары двойственных задач.
исходная |
двойственная |
симметричные |
|
Z(X)=CX→max AX<=B X>=0 |
F(Y)=YB→min YA>=C Y>=0 |
Z(X)=CX→min AX>=B X>=0 |
F(Y)=YB→max YA<=C Y>=0 |
несимметричные |
|
Z(X)=CX→max AX=B X>=0 |
F(Y)=YB→min YA>=C |
Z(X)=CX→min AX=B X>=0 |
F(Y)=YB→max YA<=C
|
С=(с1,……….,сn) Y=(y1,……..,ym)
a11……….. a1n b1 x1
A= ………………….. B= X=
am1………… amn bm xn
При составлении двойственных задач используются следующие правила.
1. во всех ограничениях исходной задачи свободные члены должны находится в правой части, а члены с неизвестными в левой.
2. ограничение неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были напрвлены в одну сторону
3. если знаки неравенств в ограничениях исходной задачи <= то целевая функция Z(X) должна максимизироваться, если >= то минимизироваться.
4. каждому ограничению исходной задачи соответствует неизвестная в двойственной задачи. При этом неизвестная отвечающая ограничению неравенству, должно удовлетворять условию неотрицательности, а неизвестная отвечающая ограничению равенству может быть любого знака.
5. целевая функция двойственной задачи имеет вид
F(y) = c0 + b1y1 +……+bmym c0 свободный член целевой функции z=c1x1+c2x2+….+ cnxn
исходной задачи
b1 ………… bn свободные члены в ограничениях исходной задачи, bi свободный член именно того ограничения, которому соответствует неизвестная yi, y1,……..,ym неизвестные в двойственной задачи.
6. целевая функция F(Y) двойственной задачи должна оптимизироваться в противоположном по сравнению с z(x) образом. Если z(x) →max, то F(y) →min. И наоборот.
7. каждому неизвестному xj исходной задачи, j=1….m. Соответствует ограничению в двойственной задачи. Совокупность этих n-ограничений вместе с условиями неотрицательности образует систему ограничений двойственной задачи.Все ограничения двойственной задачи имеют вид неравенств.
Теоремы двойственности.
Позволят установить взаимосвязь между оптимальными решениями пары двойственных задач. Решив одну из пары двух задач можно решить или найти оптимальное решение другой задачи не решая её или установить её отсутствие.
Возможны следующие случаи:
Обе задачи из пары двойственных имеют оптимальное решение
Одна из задач не имеет решения в виду неограниченности целевой функции, а другая в виду несовместности системы ограничений.
Теорема 1
Если одна из пары двойственных задач имеет оптимальное решение то и двойственная к ней имеет оптимальное решение; при чем значения целевых функций задач на своих оптимальных решениях совпадает. Если же одна из пары двойственных задач не имеет решения в виду неограниченности целевой функции, а другая не имеет решения в виду несовместности системы ограничений.
Теорема 2
Для того чтобы допустимые решения X=(x1+x2+….+xn) Y=(y1,……..,ym) являлись оптимальными решениями пары двойственных задач необходимо и достаточно, чтобы выполнялись следующие неравенства
xj ( aij yi - cj)=0 j=1….n.
yi ( aij xj - bi)=0 i=1….m.
иначе если при подстановке оптимального решения в систему ограничений i ограничение исходной задачи выполняется как строгое неравенство, то i координата двойственной задачи = 0 и наоборот если i координата оптимального решения двойственной задачи отлична от 0 то i ограничение исходной задачи удовлетворяется оптимальным решением как равенство. Для решения двойственных задач применяются те же методы решения что и для исходной задачи линейного программирования.
24. Критерии оптимальности при принятии решений при неопределенности.
Альтернативе соответствует множество последовательностей
|
b1 |
... |
|
a1 |
U11 |
|
U1n |
ai |
Ui1 |
|
Uin |
am |
Um1 |
|
Umn |
Максиминный критерий
U |
b1 |
b2 |
a1 |
1 |
0 |
a2 |
0.9 |
0.4 |
a3 |
0.1 |
0.6 |
Получается оптимальная альтернатива
Этот критерий часто называют пессимистическим.
Оптимистический (максимаксный) критерий. решение будет
Критерий оптимизма-пессимизма Гурвица. - параметр(степень) оптимизма
Пример: ; т.о. решение по max = a2
Критерий минимаксного сожаления или критерий Севиджа.
|
b1 |
b2 |
a1 |
0 |
0.6 |
a2 |
0.1 |
0.2 |
a3 |
0.9 |
0 |
Решение a2 т.к. min достигаем в a2
Критерий Байеса.
Во всех предыдущих случаях критерии завесили от взглядов самого ЛПР-ов (Лицо Принимающее Решение-ЛПР) т.е. были субъективны. Подход Байеса принципиально иной и этот подход основан на использовании статистических методов. Мат. Статистика как раз и является продвинутой теорией принятия решений в условиях неопределенности. Данный подход основан на том, что пытается оценить вероятность p1….pn наступления того или иного состояния природы критерий: при этом выполняются условия нормировки , но методы расчета вероятностей называются статистическими методами. В простейшем случае он сводится к тому, что подсчитываем кол-во наступлений тех или иных состояний в прошлом, что позволяет оценить данные вероятности по закону больших чисел. В более сложных случаях наблюдаются другие параметры, на которые оказывает влияние состояние природы. Пример на простейший случай: Пусть мы выходили на прогулку 50 раз ранее, и пусть 20 раз была хорошая погода, 30 раз плохая погода тогда 20/50=0,4, 30/50=0,6. Тогда используется следующий критерий f(a1)=0.4*1+0.6*0=0.4; f(a2)=0.4*0.9+0.6*0.4=0.6; f(a3)=0.4*0.1+0.6*0.6=0.4; Вывод: решение a2.
Замечание: подход Байеса напоминает задачу теории принятия решений при риске, но в данном случае в качестве лотерей выступают состояния природы, а элементы платежной матрицы рассматриваются как полезности.
Критерий Лапласа.
Это частный случай критерия Байеса. Если по каким-то причинам оценка вероятности состояний природы невозможна, то Лаплас предлагает считать эти вероятности равновероятными. Получается такой критерий:
, тогда:
Решение =a2
Критерий Неймана-Пирсона.
Этот Критерий применяется в частном случае, когда: 1)всего 2 состояния природы. 2)вероятности этих состояний можно оценить только в порядковой шкале. Т.о. один критерий считается более значимым чем другой. Полезность по этому критерию не должна быть меньше некоторой пороговой величины и уже в этих условиях оптимизируем по второму состоянию. Пусть b2 предпочтительнее и выбираем порог - параметр критерия. Удовлетворяют альтернативы по второму критерию: a2 и a3. По b1 – 0.9, 0.1 – решение a2 по 1-ому состоянию.
Смешанное решение
Смешанные решения могут возникать в виде диверсификации или в виде рандомизации. Решение представлено в виде вектора ; ; пример1: ”диверсификация” пусть 2 состояния природы; b1 – теплая осень, b1 –холодная осень; 2 альтернативы: a1- купить партию кондиционеров, a2 – купить партию обогревателей
-
b1
b2
a1
5
1
a1
2
7
Идея диверсификации состоит в том, что применяется некоторая механическая смесь элементарных решений и выбирается уже оптимальное смешанное решение. Т.е. множество альтернатив выглядит следующим образом: в партии x*100% ,будет % купленных кондиционеров, (1-x)*100% процент купленных обогревателей. Решение применяем не элементарное, а множество смешанных решений. Элементарные решения: при x=0 – обогреватели(a2), x=1 – кондиционеры(a1). Такой подход не всегда возможен. пример2: ”рандомизированное” решение. В данном случае в качестве смешанных решений выступают лотерее, исходами которых являются простые альтернативы . Условия нормировки выполняются. В этом случае под смешанным решением подразумевается случайный механизм, с помощью которого ЛПР и принимает решение. Рандомизированные решения эффективно применять при многократном принятии решений. В этом случае по закону больших чисел достигается max-ая полезность в среднем. Оценка сложного решения: ; ; ; i=1…n; j=1…n – полезность смешанного решения x при состоянии природы bj. Замечание: в случае рандомизированных решений эта оценка совпадает с оценкой по теории Неймана-Монгенштерма. Также очевидно что к смешанным решениям применимы критерии оптимальности.