Краткий конспект лекций

1

Геометрическое моделирование

1 Векторная и растровая графика.

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

Растровое изображение можно сравнить с детской мозаикой, когда картинка составляется из цветных квадратиков. Компьютер запоминает цвета всех квадратиков подряд в определенном порядке. Поэтому растровые изображения требуют для хранения большего объема памяти. Их сложно масштабировать и еще сложнее редактировать. Чтобы увеличить изображение, приходится увеличивать размер квадратиков, и тогда рисунок получается "ступенчатым". Для уменьшения растрового рисунка приходится несколько соседних точек преобразовывать в одну или выбрасывать лишние точки. В результате изображение искажается, его мелкие детали становятся неразборчивыми. Этих недостатков лишена векторная графика. В векторных редакторах рисунок запоминается как совокупность геометрических фигур - контуров, представленных в виде математических формул. Чтобы пропорционально увеличить объект, достаточно просто изменить одно число: коэффициент масштабирования. Никаких искажений ни при увеличении, ни при уменьшении рисунка не возникает. Поэтому, создавая рисунок, вы можете не думать о его конечных размерах - вы всегда можете изменить их.

4

2 Геометрические преобразования

Ве́кторная гра́фика — это использование геометрических примитивов, таких как точки, линии, сплайны и многоугольники, для представления изображений в компьютерной графике. Рассмотрим, к примеру, окружность радиуса r. Список информации, необходимой для полного описания окружности, таков:

радиус r;

координаты центра окружности; цвет и толщина контура (возможно прозрачный);

цвет заполнения (возможно прозрачный).

Преимущества этого способа описания графики над растровой графикой:

Минимальное количество информации передаётся намного меньшему размеру файла (размер не зависит от величины объекта).

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

При увеличении или уменьшении объектов толщина линий может быть постоянной.

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

У векторной графики есть два фундаментальных недостатка.

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

Перевод векторной графики в растр достаточно прост. Но обратного пути, как правило, нет — трассировка растра обычно не обеспечивает высокого качества векторного рисунка.

Векторные графические редакторы, типично, позволяют вращать, перемещать, отражать, растягивать, скашивать, выполнять основные аффинные преобразования над объектами, изменять z-order и комбинировать примитивы в более сложные объекты.

Более изощрённые преобразования включают булевы операции на замкнутых фигурах: объединение, дополнение, пересечение и т. д.

Векторная графика идеальна для простых или составных рисунков, которые должны быть аппаратно-независимыми или не нуждаются в фотореализме. К примеру, PostScript и PDF используют модель векторной графи

Линии и ломаные линии. Многоугольники.

5

Окружности и эллипсы. Кривые Безье. Безигоны.

Текст (в компьютерных шрифтах, таких как TrueType, каждая буква создаётся из кривых Безье).

Этот список неполон. Есть разные типы кривых (Catmull-Rom сплайны, NURBS и т.д.), которые используются в различных приложениях.

Также возможно рассматривать растровое изображение как примитивный объект, ведущий себя как прямоугольник.

3 Основные виды геометрических моделей

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

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

В трёхмерной компьютерной графике все объекты обычно представляются как набор поверхностей или частиц. Минимальную поверхность называют полигоном. В качестве полигона обычно выбирают треугольники.

Всеми визуальными преобразованиями в 3D-графике управляют матрицы (см. также: аффинное преобразование в линейной алгебре). В компьютерной графике используется три вида матриц:

матрица поворота матрица сдвига матрица масштабирования

Любой полигон можно представить в виде набора из координат его вершин. Так, у треугольника будет 3 вершины. Координаты каждой вершины представляют собой вектор (x, y, z). Умножив вектор на соответствующую матрицу, мы получим новый вектор. Сделав такое преобразование со всеми вершинами полигона, получим новый полигон, а преобразовав все полигоны, получим новый объект, повёрнутый/сдвинутый/промасштабированный относительно исходного

6

4 Получение реалистичных изображений

Способ представления изображения Растровое изображение строится из множества пикселей. Векторное изображение описывается в виде последовательности команд. Представление объектов реального мира

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

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

Итак, в конечном счете любое изображение на экране представляет собой совокупность пикселей Информация о текущем состоянии экрана хранится в памяти видео-карты. Если подобным же образом организован и графический файл с данными, то мы имеем дело с растровой графикой. Например, такие файлы получаются при использовании программ Paint, Adobe Photoshop и других. В таких программах существенную часть работы по построению изображения надо делать вручную. В связи с этим растровые пакеты можно отнести к средствам компьютерной живописи. Другой подход заключается в том, чтобы при построении изображения в максимальной степени использовать математическое описание. Например, для описания отрезка прямой достаточно указать координаты его концов, а окружность можно описать, задав координаты центра и радиус. Этот подход реализован в программах векторной графики. Примерами таких программ могут служить Corel Draw, Macromedia FreeHand. Такая технология позволяет давать компьютеру указания (команды), руководствуясь которыми он строит изображения с помощью заложенных в программу алгоритмов. Этот метод больше походит на черчение, причем часто трехмерное

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

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

7

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

Применение методов оптимизации при решении задач автоматического и автоматизированного управления,

прогнозирования ситуаций, принятия решений

1.Методологические основы оптимизации.

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

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

Внастоящее время для решения оптимальных задач применяют в основном следующие методы:

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

Лагранжа; вариационное исчисление;

динамическое программирование; принцип максимума; линейное программирование; нелинейное программирование.

Впоследнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.

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

-менее общими. Наконец, целую группу методов (методы исследования функций классического анализа, метод множителей Лагранжа, методы

8

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

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

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

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

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

·количество продукции - расход сырья

·количество продукции - качество продукции

Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.

9

При постановке задачи оптимизации необходимо:

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

Типичный пример неправильной постановки задачи оптимизации:

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

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

Правильная постановка задачи могла быть следующая:

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

В первом случае критерий оптимизации - производительность а во втором - себестоимость.

2.Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.

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

4.Учет ограничений.

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

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

10

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

изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского

«linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в

Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».

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

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

2. Оптимизационная модель.

ОПТИМАЛЬНАЯ (ИЛИ ОПТИМИЗАЦИОННАЯ) МОДЕЛЬ

[optimization model] — экономико-математическая модель, которая охватывает некоторое число вариантов (технологических способов)