Последовательность построения

Сценар, деят-ти

|

классов

|

состоян, деят, последов, кооперац, компонентов (->тополог)

 

2) 1:M – объекту из первого кл соответ несколько об втор класса, но ∀ об втор класса соответ только 1 об перв класса (<–>>)

3) M:N - одному объекту перв класса соотв несколько об второго класса, также объекту второго класса соотв неск объектов перв класса (<<–>>)

Полнота связи:

1) Необязат св (сущес-твование об-та класса не зависит от налич связи)

2) Обязат св (зависит)

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

Построен реляц модели данных

Переход от модели пр обл к реляц модели:

1.Построить схемы отно-шения для классов объектов.

a)Для каждого класса об-ов сформиров отдельное отно-шение, атрибутами кот будут св-ва этого класса.

b)Далее, для каждого атрибута опр домен и привести отношение к 1НФ.

c)Затем, необ выделить в отношении ключ или ввести искусственный ключ – новый атрибут с целочисленным доменом.

2)Построив схемы отношений для каждого класса об, м перейти к построению отношений для связей м/у об-ми.

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

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

 

 

2) Челов ошибки

Пользов ош, в основном вина разработчика.

Ошибки: 1) вызванные недостат знанием пр обл

2) опечатки

3) несчитывание показаний сист

4) моторные ош

Для преодол необх:

- плавное обучение пользователей в процессе работы

- снижение требований к бдительности

- повышение разборчивости и заметности индикаторов.

- снижение чувствительности системы к ошибкам.

3) обучение работе с сист

- обеспеч понятность системы

- подготовит грамотный обуч материал

а)использов метафор(модель работы ИС, взятая из реальн мира)

б)аффорданс(объект показывает субъекту способ своего использования)

в)стандарт(сделать опр вещи в ИС везде одинак, напр F1 везде справка)

4)субъективн удовлетв

-эстетическ воспр/-скорсоть раб/-отсутств напряж при работе

Ошибка – стресс, след она д б правильн(в чем заключ?как исправить пробл сейчас?как сделать чтобы пробл не повтор?)

 

 

4) конструирование отдельных блоков

Детализация функ блоков

5) создание глоссария

необходимо зафиксировать все используемые в системе понятия и дать на проверку пользователям, если они поним знач прав, значит успех

-Согласовать с потенц-иальным пользователем

-Заменить названия команд на глаголы-инфинитивы

-Исключить синонимы

-Установить одинак стиль

-Уменьшить длину всех получившихся элементов

6) сбор и тестирование

Прототипы интерф:

Первая версия – бумажная

Вторая версия – презентация

Третья версия – почти реальная

Четвертая версия – реальная
25 Задача линейного, цело-численного линейного и смешанногоцелочисленного линейного программир.

Матем программ– раздел математ кот изуч теорию и методы решения зад оптимизации. Для решения необх построить качеств модель задачи(четкое словес описание), а затем мат модель (абстракция реальн мира записываемая в виде соотношен). Целев ф-я – ф-я большему или меньш знач кот соотв нилучш решен с точки зр критер оптим-ти

Задача ЛП

 

x_j ≥0 j=1..n

m – кол-во ограничений

n – кол-во переменных

x_j – переменные

c_j – коэффициенты целевой функции

b_i – правые части (огр)

a_ij – коэффициенты матрицы ограничений

Пример: Задача об оптим распределении ресурсов. Имеется предприятие, кот выпускает n различных видов продукции. с_j – прибыль от реализации единицы j-го вида продукции.

26 Приведение задачи линейного программирования к канонической форме

Канонический вид задачи ЛП

i=1..m, x_j ⩾0, j=1..n

Приведение к канонич форме1. Если целевая функция à max, умножаем à min.

2. Если есть условия вида левой части дополнительную неотрицательную перемен-ную, и ставим знак «=».
3. Если есть условия вида

 

 

, прибавляем к левой части дополнительную неотрицат переменную, и ставим знак «=».

 

 

27 Графический метод решения задачи лин прогр

c₁x₁+c₂x₂ →max

a_k1x₁+a_k2x₂ ⩽b_k

1. По огранич задачи строится область допустимых значений (ОДЗ). ∀ неравенству на плоскости соотв полуплоскость, ∀ уравнению соотв прямая, ОДЗ будет пересечением построенных полуплоскостей и прямых. Возможны несколько вариантов ОДЗ (замкнутая область, неограниченная область, луч, отрезок, точка, пустое множество). Если ОДЗ – пустое множество, то задача не имеет решения. Если ОДЗ не пусто, то идем на шаг 2.
2. Строим вектор градиента, координаты начала вектора - (0, 0), координаты конца вектора – (с1, с2), где с1, с2 коэффиц целевой функции.

3. Строим линию уровня целевой функции. Линия уровня цел ф-и перпендикулярна вектору градиента и должна проходить по ОДЗ задачи.

4. Определяем точки-кандидаты из ОДЗ для оптимального решения. Если цел функция на максимум, то линию уровня целевой функции перемещаем параллельно самой себе в направлении градиента до последней точки ОДЗ.

28 Симплексный метод решения задачи лин прогр

Допустимое решение наз-ся Базисным Допустимым Решением, если оно имеет следующую структуру: X=(x₁,..,x_m,x_m+1,..,x_n), x_i ⩾ 0, i=1..m, x_m+1=…=x_n=0,где m – число ЛНЗ базисных векторов.

Перед началом работы симплекс-метода, исходную задачу нужно привести к каноническому виду. Доп условие:b_j⩾0. Так же нам нужно получить БДР (базисное допустимое решение).

Далее строится начальная симплексная таблица:

 

 

m – число ненулевых элем в БДР, с_i – коэфф цел функции,

x_i – наименования базисных векторов, b_i – правые части ограничений, a_ij – коэфф ограничений, ∆ – оценки переменных.

- оценка значения целевой функции.

- вспомогательные оценки.

1) Просматрив все оценки ∆₁.. ∆_m. Если все оц ⩽0, то нашли опт реш конец

Иначе след шаг

2) среди положительных оц выбираем max и столб соответ данной оц объявляем ведущ (s)

3) просматриваем ведущ столбец, если все элем ведущ столб ⩽0, то целев функ неограниченна конец

Иначе сл шаг

4) выбираем ведущую строку (r) по мин симпл отношен

5) на пересеч вед столб и вед стр находи вед элемент

 

Для продукции требуется сырье. b_i – запас каждого из видов сырья. Норма расхода i-го вида сырья для производства j-го вида продукции – a_ij. x_j – объем выпуска j-го вида продукции. Требуется максимизировать прибыль.

Задача целочисленного ЛП:Добавляется доп. условие: все переменные должны быть целочисленными:

Пример: Задача о ранце. Определить, какие товары в каком кол-ве нужно загрузить в ранец так, чтобы суммарная стоимость была max. n – число товаров, m – кол-во параметров ранца (макс. вес, макс. объем и т.д.). a_ij – характ-ка j-го товара по i-му пар-ру. c_j – стоимость товара, b_i – ограничение ранца по i-му параметру. x_j – количество j-го товара.
Задача смешенного целочис ЛП:Добавляется доп. условие: часть переменных должны быть целочисленными:

 

4. Если есть x_i⩽0, производим замену на x_i ⩾0;x_i* =-x_i.

5. Если есть x_i любого знака, производим замену на
6.'Для некоторых задач требуется, чтобы b_i ⩾0. В этом случае мы умножаем левую и правую части

 

 

Если целевая функция на минимум, то линию уровня перемещаем в направлении противоп градиенту.

5. Находим точн решен. Если очевидно, что точка-кандидат является оптимальным решением, то подставляем ее значение в целевую функцию и записываем решение ЗЛП в виде – оптимальное значение ц фун, и соответствующие значения X1 и X2. Если точек кандидатов несколько, то для каждой такой точки составляется система двух уравнений с двумя неизвестными, линии кот в пересечении дают данные точки. Для каждой точки решается система уравнений. Полученные решения подставляются в цел функ. В качестве оптимальной выбирается та точка, для кот значение целевой функции лучше.

Замечание. Возможны неск вар-ов решений: оптимальное реш единственно, оптимальн решений множество, целевая функция неограниченна.

 

 

6) рисуем нов симпл табл без наполнения, в нов табл в столбце базиса в строке r ставим вед элемент; пересчитываем таблицу с помощ преобраз Жордана-Гаусса

Преоббраз ЖГ:

В ведущем столбце все значен, кроме ведущ знач =0, ведущ = 1. В ведущей строке все значения делятся на значение ведущего элемента, все остальные рассчитываются по правилу креста

Построение нач базисного реш методами дополнит или искусств-х переменных.Если для исходной задачи P нет нач БДР, тогда мы создаем новую искусств зад P₁, в рез-те решения кот симплекс-методом мы получаем искомый БДР. Задача P₁ строится следующим образом: Мы добавляем искусственные переменные – по числу недостающих переменных в БДР. Тогда новая задача будет иметь вид:

, к – число дополнительных переменных

 

 

x_j ⩾0, j=1..n,y_j ⩾0,j=1..k

Далее, решаем эту задачу прямым симплекс-методом. Алгоритм останавливается на шаге, когда ∆ = 0 (если оптим знач ц ф задачи P1 > 0, то P не имеет решен). При этом, если в БДР входят переменные y_i, они выводятся из него преобразованием Жордана-Гаусса: среди положительных оценок123 выбирается любая оценка, для кот соответствующая переменная x_i не входит в БДР, этот столбец объявл ведущим. Дальше – все, как обычно.
29 Методы решения задач ЦЛП (метод ветвей и границ, метод отсечений)

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

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