26806

Линейное программирование. Рассмотрим основные понятия, характеризующие строение и функционирование систем

Шпаргалка

Информатика, кибернетика и программирование

Для организационных систем и ИС удобно в определении системы учитывать цели и планы внешние и внутренние ресурсы исполнителей непосредственно процесс помехи контроль управление и эффект. Интегративное свойство системы обеспечивает ее целостность качественно новое образование по сравнению с составляющими ее частями. Под элементом принято понимать простейшую неделимую часть системы. Это часть системы обладающая внутренней структурой.

Русский

2015-01-19

101 KB

0 чел.

Бил 15

Линейное программирование.

Нужно найти  экстремальное значение линейной функции F от нескольких аргументов. Область поисков ограничена группой линейных неравенств. Получается вроде  как «выпуклый многогранник» в  n-мерном пространстве, внутри которого можно перемещаться  в поисках лучшего значения функции F. Решение лежит на границе.  Есть стандартные программы решения.

Задачи линейного программирования

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

Формально общая задача линейного программирования понимается как задача поиска экстремума скалярной линейной функции цели F вектора управляемых переменных = (X1, ... ,Xn):

  F(X) = C1*X1 + ... + Cj*Xj + ... + Cn*Xn -> extr;

при линейных функциональных ограничениях:

   Ai1*X1 + ... + Aij*Xj + ... + Ain*Xn (Ri) Bi,  i = 1,..,m

и прямых ограничениях по управляемым параметрам:

   Xj > или = 0,     j = 1,...,n,

где Ri - любые из отношений < ; > ; = или их комбинации.

2. Основные  понятия теории систем.

В настоящее время нет единства в определении понятия «система». Можно сказать, что система – это элементы и связи (отношения) между ними.

Для организационных систем и ИС удобно в определении системы учитывать цели и планы, внешние и внутренние ресурсы, исполнителей, непосредственно процесс, помехи, контроль, управление и эффект.

Под системой всегда понимается объект, свойства которого не сводятся без остатка к свойствам составляющих его дискретных элементов (неаддитивность свойств). Интегративное свойство системы обеспечивает ее целостность, качественно новое образование по сравнению с составляющими ее частями.

Рассмотрим основные понятия, характеризующие строение и функционирование систем.

Элемент. Под элементом принято понимать простейшую неделимую часть системы.

Подсистема. Это часть системы, обладающая внутренней структурой.

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

Связь. Понятие «связь» входит в любое определение системы наряду с понятием «элемент» и обеспечивает возникновение и сохранение структуры и целостных свойств системы. Это понятие характеризует одновременно и строение (статику), и функционирование (динамику) системы.

Состояние. Понятием «состояние» обычно характеризуют мгновенную фотографию, «срез» системы, остановку в ее развитии. Состояние определяют либо через входные воздействия и выходные сигналы (результаты), либо через макропараметры, макросвойства системы (например, давление, скорость, ускорение – для физических систем; производительность, себестоимость продукции, прибыль – для экономических систем).

Таким образом, состояние – это множество существенных свойств, которыми система обладает в данный момент времени.

Поведение. Если система способна переходить из одного состояния в другое, то говорят, что она обладает поведением. Этим понятием пользуются, когда неизвестны закономерности переходов из одного состояния в другое. Тогда говорят, что система обладает каким-то поведением, и выясняют его закономерности.

Внешняя среда. Под внешней средой понимается множество элементов, которые не входят в систему, но изменение их состояния вызывает изменение поведения системы.

Модель. Под моделью системы понимается описание системы, отображающее определенную группу ее свойств. Углубление описания – детализация модели. Создание модели системы позволяет предсказывать ее поведение в определенном диапазоне условий.

Модель функционирования (поведения) системы – это модель, предсказывающая изменение состояния системы во времени.

Входы и выходы. Это материальные или информационные потоки, входящие и выходящие из системы.

Равновесие. Под равновесием понимают способность системы в отсутствие внешних возмущающих воздействий (или при постоянных воздействиях) сохранить свое состояние сколь угодно долго.

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

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

Цель. В Большой Советской Энциклопедии цель определяется как «заранее мыслимый результат сознательной деятельности человека».

Понятие цели лежит в основе развития системы. Если перейти на язык математики, то можно сказать, что состояние системы описывается рядом переменных x1 , . . . , xn . Для достижения поставленной цели одна из переменных или группа переменных {xi}, должна поддерживаться в определенном значении xi = F(X, t) (или диапазоне значений), называемой целевой функцией.

Информация – это совокупность сведений, воспринимаемых из окружающей среды, выдаваемых в окружающую среду или сохраняемых внутри информационной системы.

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

3. Общие требования к методологии и технологии  11

Методологии, технологии и инструментальные средства проектирования (CASE-средства) составляют основу проекта любой ИС. Методология  проектирования ПО представляет собой организованную совокупность процессов создания ряда моделей. Методология реализуется через конкретные технологии и поддерживающие их стандарты, методики и инструментальные средства, которые обеспечивают выполнение процессов ЖЦ.

Технология проектирования определяется как совокупность трех составляющих:

пошаговой процедуры, определяющей последовательность технологических операций проектирования (рис. 1);

критериев и правил, используемых для оценки результатов выполнения технологических операций;

нотаций (графических и текстовых средств), используемых для описания проектируемой системы.

 

Технология проектирования, разработки и сопровождения ИС должна удовлетворять следующим общим требованиям:

поддерживать полный ЖЦ ПО;

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

возможность декомпозиции проекта на составные части, разрабатываемые группами исполнителей ограниченной численности (3-7 человек), с последующей интеграцией составных частей;

обеспечивать минимальное время получения работоспособной ИС. Речь идет о сроках реализации отдельных подсистем.

предусматривать возможность управления конфигурацией проекта, ведения версий проекта и его составляющих, возможность автоматического выпуска проектной документации и синхронизацию ее версий с версиями проекта;

обеспечивать независимость выполняемых проектных решений от средств реализации ИС;

быть поддержана комплексом согласованных CASE-средств, обеспечивающих автоматизацию процессов, выполняемых на всех стадиях ЖЦ.

Реальное применение любой технологии проектирования, разработки и сопровождения ИС в конкретной организации и конкретном проекте невозможно без выработки ряда стандартов (правил, соглашений), которые должны соблюдаться всеми участниками проекта. К таким стандартам относятся следующие:

стандарт проектирования;

стандарт оформления проектной документации;

стандарт пользовательского интерфейса.

4.Диагностика маршрута (traceroute) с использованием протокола UDP и ICMP.  2

UDP - протокол передачи данных,  ICMP - протокол управляющих сообщений.

Вы их получаете постоянно, а иногда и отправляете, например:

  •  Если адрес не доступен, вы получаете сообщение ICMP.
  •  Если порт не доступен, вы получаете сообщение ICMP.
  •  и т.д.

Принцип работы traceroute 

traceroute отправляет на несуществующий порт удаленного узла последовательность UDP-дейтаграмм.

Алгоритм работы:

  •  Посылаются дейтограммы с TTL=1 (время жизни пакета)
  •  Первый же маршрутизатор уменьшает TTL на 1, т.е. TTL=0 и пакет уничтожается, а отправителю посылается ICMP сообщение Time Exceeded (Время жизни истекло).
  •  Посылаются дейтограммы с TTL=2 (время жизни пакета)
  •  Первый же маршрутизатор уменьшает TTL на 1, т.е. TTL=1 и пакет проходит дальше.
  •  Второй маршрутизатор уменьшает TTL на 1, т.е. TTL=1 и пакет уничтожается, а отправителю посылается ICMP сообщение Time Exceeded.
  •  И т.д.
  •  Попадая на получателя, пакет уничтожается, т.к. получатель не знает, что с ним делать (порт не существует),  и отправителю посылается ICMP сообщение Destination Unreachable (Цель недостижима).

Верификация моделей. Проверка адекватности и корректировка имитационной модели

1) Верификация модели

Проверка адекватности и корректировка модели;

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

Планирование экспериментов;

  •  стратегическое планирование – план эксперимента
    •  тактическое планирование – определение способа проведения каждой серии испытаний, предусмотренных планом

Собственно моделирование;

  •  анализ чувствительности;

Анализ результатов моделирования и принятие решения.

  •  Интерпретация – построение выводов по данным, полученным в результате имитации
    •  Реализация – практическое использование результатов эксперимента
    •  Документирование – регистрация хода осуществления проекта, а также документирование процесса создания и использования модели

2) Проверка адекватности и корректировка модели

А) После написания модели и до начала эксперимента – проверка адекватности модели.

Замечания: На самом деле этот этап – непрерывный процесс с момента создания модели до завершения экспериментов. Почему сразу, а не после начала экспериментов – стоимость эксперимента (если речь идет о сложной системы, сбор данных) и «гипноз» модели.

  1.  Гипноз модели. Проверка модели процесс чрезвычайно важным, поскольку любая ИМ создает впечатление реальности, которым проникаются как разработчики, так и пользователии. Проверка, выполненная без необходимой тщательности, может привести к катастрофическим последствиям.
  2.  Строго регламентированного (научно обоснованного)  формального процесса – «испытание» модели не существует. За исключением тривиальных случаев. Суть не в доказательстве, а в 1) достижении необходимого уровня уверенности пользователя, что любой вывод о поведении системы, сделанный на основании моделирования будет верным.
  3.  Не нужно стремиться доказать, что та или иная имитация является «правдивым» отображением реальной системы (за исключением тривиальных случаев). Важна не «правдивость» модели, не справедливость структуры модели, а ее функциональная полезность – т.е. справедливость тех умозаключений, которые будут получены в результате моделирования. 2) Выводы, полученные в результате моделирования, справедливы и корректны.

Таким образом, оценка адекватности имеет две стороны: 1) Достижение необходимого уровня уверенности пользователя; 2) Выводы, полученные в результате моделирования, справедливы и корректны.

В) Три стадии оценки адекватности имитационной модели:

  •  (этап отладки программы) Верификация– экспериментатор должен убедиться, что модель ведет себя так, как задумано.
  •   (готовая версия программной модели) Обоснованность модели (Адекватность)– проверка соответствия между поведением модели и поведением реальной системы.
  •   (обычно, этап эксперимента) Проблемный анализ – формулирование статистически значимых выводов на основе данных, полученных в результате компьютерного моделирования. Один прогон имитационной модели, в отличие от математических моделей, не значит ничего (с точки зрения общих выводов)

6.Даталогическое проектирование

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

Однако этап логического или даталогического проектирования не заканчивается проектированием схемы отношений. В общем случае в результате выполнения этого этапа должны быть получены следующие результирующие документы:

Описание концептуальной схемы БД в терминах выбранной СУБД.

Описание внешних моделей в терминах выбранной СУБД.

Описание декларативных правил поддержки целостности базы данных.

Разработка процедур поддержки семантической целостности базы данных.

Однако перед тем как описывать построенную схему в терминах выбранной СУБД, нам надо выстроить эту схему. Именно этому процессу и посвящен данный раздел.

Мы должны построить корректную схему БД, ориентируясь на реляционную модель данных.

Корректной назовем схему БД, в которой отсутствуют нежелательные зависимости между атрибутами отношении.

Процесс разработки корректной схемы реляционной БД называется логическим проектированием БД.

Проектирование схемы БД может быть выполнено двумя путями:

путем декомпозиции (разбиения), когда исходное множество отношений, входящих в схему БД заменяется другим множеством отношений (число их при этом возрастает), являющихся проекциями исходных отношений;

путем синтеза, то есть путем компоновки из заданных исходных элементарных зависимостей между объектами предметной области схемы БД.

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

Однако этап логического или даталогического проектирования не заканчивается проектированием схемы отношений. В общем случае в результате выполнения этого этапа должны быть получены следующие результирующие документы:

Описание концептуальной схемы БД в терминах выбранной СУБД.

Описание внешних моделей в терминах выбранной СУБД.

Описание декларативных правил поддержки целостности базы данных.

Разработка процедур поддержки семантической целостности базы данных.

Однако перед тем как описывать построенную схему в терминах выбранной СУБД, нам надо выстроить эту схему. Именно этому процессу и посвящен данный раздел.

Мы должны построить корректную схему БД, ориентируясь на реляционную модель данных.

Корректной назовем схему БД, в которой отсутствуют нежелательные зависимости между атрибутами отношении.

Процесс разработки корректной схемы реляционной БД называется логическим проектированием БД.

Проектирование схемы БД может быть выполнено двумя путями:

путем декомпозиции (разбиения), когда исходное множество отношений, входящих в схему БД заменяется другим множеством отношений (число их при этом возрастает), являющихся проекциями исходных отношений;

путем синтеза, то есть путем компоновки из заданных исходных элементарных зависимостей между объектами предметной области схемы БД.

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

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

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

В теории реляционных БД обычно выделяется следующая последовательность нормальных форм:

первая нормальная форма (1NF);

вторая нормальная форма (2NF);

третья нормальная форма (3NF);

нормальная форма Бойса— Кодда (BCNF);

четвертая нормальная форма (4NF);

пятая нормальная форма, или форма проекции-соединения (5NF или PJNF).

Основные свойства нормальных форм:

каждая следующая нормальная форма в некотором смысле улучшает свойства предыдущей;

при переходе к следующей нормальной форме свойства предыдущих нормальных форм сохраняются.

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

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

При выполнении эквивалентных преобразований сохраняется множество исходных фундаментальных функциональных зависимостей между атрибутами отношений.

Функциональные зависимости определяют не текущее состояние БД, а все возможные ее состояния, то есть они отражают те связи между атрибутами, которые присущи реальному объекту, который моделируется с помощью БД.

Поэтому определить функциональные зависимости но текущему состоянию БД можно только в том случае, 'если экземпляр БД содержит абсолютно полную информацию (то есть никаких добавлений и модификации БД не предполагается). В реальной жизни это требование невыполнимо, поэтому набор функциональных зависимостей задает разработчик, системный аналитик, исходя из глубокого системного анализа предметной области.

Приведем ряд основных определений.

Функциональной зависимостью набора атрибутов В отношения R от набора атрибутов А того же отношения, обозначаемой как

R.A -> R.B или А -> В

называется такое соотношение проекций R[A] и R[B], при котором в каждый момент времени любому элементу проекции R[A] соответствует только один элемент проекции R[B] , входящий вместе с ним в какой-либо кортеж отношения R.

Функциональная зависимость R.A -> R.B называется полной, если набор атрибутов В функционально зависит от А и не зависит функционально от любого подмножества А, то есть R.A -> R.B называется полной, если:

любое А1 с А=> R.A -/-> R.B, что читается следующим образом:

для любого А1, являющегося подмножеством A, R.B функционально не зависит от R.A, в противном случае зависимость R.A -> R.B называется неполной.

Функциональная зависимость R.A -> R.B называется транзитивной, если существует набор атрибутов С такой, что:

С не является подмножеством А.

С не включает в себя В.

Существует функциональная зависимость R.A -> R.C.

Не существует функциональной зависимости R.C -> R.A.

Существует функциональная зависимость R.C -> R.B.

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

А может ли быть ситуация, когда отношение не имеет возможного ключа? Давайте вспомним определение отношения: отношение — это подмножество декартова произведения множества доменов. И в полном декартовом произведении все наборы значений различны, тем более в его подмножестве. Значит, обязательно для каждого отношения всегда существует набор атрибутов, по которому можно однозначно определить кортеж отношения. В .вырожденном случае это просто полный набор атрибутов отношения, потому что если мы зададим для всех атрибутов конкретные значения, то, по определению отношения, мы получим только один кортеж.

В общем случае в отношении может быть несколько возможных ключей.

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

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

Взаимно-независимые атрибуты — это такие атрибуты, которые не зависят функционально один от другого.

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

Для функциональных зависимостей как фундаментальной основы проекта БД

были проведены исследования, позволяющие избежать избыточного их представления. Ряд зависимостей могут быть выведены из других путем применения правил, названных аксиомами Армстронга, по имени исследователя, впервые сформулировавшего их. Это три основных аксиомы:

Рефлексивность: если В является подмножеством А, то А->В

Дополнение: если. А->В , то АС->ВС

Транзитивность: если А->В и В->С , то А->С.

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

Множество всех возможных функциональных зависимостей, выводимое из заданного набора исходных функциональных зависимостей, называется его замыканием.

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

В некотором смысле это определение избыточно, потому что собственно оно определяет само отношение в теории реляционных баз данных. Однако в силу исторически сложившихся обстоятельств и для преемственности такое определение первой нормальной формы существует и мы должны с ним согласиться. Отношения, находящиеся в первой нормальной форме, часто называют просто нормализованными отношениями. Соответственно, ненормализованные отношения могут интерпретироваться как таблицы с неравномерным заполнением, например таблица «Расписание»,