Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
"ИЖЕВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ"
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по оформлению математического раздела
курсовых и дипломных проектов
для студентов специальностей 230102, 230104,
направления 230100 Форма обучения очная и заочная Ижевск 2009 2 УДК 519.87(07) М 54 Рецензент: А.Г. Ложкин, к.т.н., доцент кафедры АСОИУ ИжГТУ.
Ермилов В.В., Исенбаева Е.Н., Кучина Т.Л., Кучуганов В.Н., Соболева Н.В., Соловьева А.Н. Под редакцией В.Н. Кучуганова. Методические указания по оформлению математического раздела курсовых и дипломных проектов. – Ижевск: Издательство ИжГТУ, 2008 г. – 50 с.
Методические указания содержат основные понятия, используемые при оформлении математического раздела пояснительной записки курсового или дипломного проекта, и примеры описания различных задач из области автоматизированных систем обработки информации и САПР.
Учебное пособие предназначено для студентов специальностей 230102, 230104, направления 230100.
Рекомендовано к изданию на заседании кафедры "Автоматизированные системы обработки информации и управления" ИжГТУ (протокол №8 от 11.12.2008 г.).
Кучуганов В.Н., составление, Издательство ИжГТУ,
СОДЕРЖАНИЕ
ВВЕДЕНИЕ1. ОСНОВНЫЕ ПОНЯТИЯ
2. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ “КОМПЛЕКТАЦИЯ
ПРОИЗВОДСТВА” (ФРАГМЕНТ)
3. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ ПОСТРОЕНИЯ
ВЫПУКЛОЙ ОБОЛОЧКИ НАБОРА ТОЧЕК3.1. Математическая модель выпуклой оболочки набора точек на плоскости 3.2. Задача построения выпуклой оболочки набора точек
4. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ "ПРИНЯТИЕ РЕШЕНИЙ
В УСЛОВИЯХ ОПРЕДЕЛЕННОСТИ"
5. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ "ОПТИМИЗАЦИЯ
ПЛАНИРОВАНИЯ ПЕРЕВОЗОК"5.1. Анализ целевой функции
5.2. Построение начального плана
5.3. Описание контрольного примера
6. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ НАХОЖДЕНИЯ
МАКСИМАЛЬНОЙ ПЛОЩАДИ ОКРУЖНОСТИ ВНУТРИ
ЧЕТЫРЕХУГОЛЬНИКАОснованная литература
Дополнительная литература
ВВЕДЕНИЕ
Методические указания содержат основные понятия, используемые при оформлении математического раздела пояснительной записки курсового или дипломного проекта, и примеры описания различных задач из области автоматизированных систем обработки информации и САПР.В математическом разделе пояснительной записки к курсовому или дипломному проекту описывается математическое обеспечение программной системы, подсистемы или модуля, предназначенного для решения поставленной задачи.
По усмотрению автора, математическое описание всех задач может быть собрано в одну главу, либо разнесено по нескольким главам, в соответствии с подсистемами проектируемой программной системы. В этом случае, математическая постановка задачи предшествует описанию реализующего ее программного модуля.
1. ОСНОВНЫЕ ПОНЯТИЯ В русском языке такие слова как: модель, задача, метод, цель, назначение имеют, как и многие другие слова естественного языка, по несколько различных значений. В разных учебниках, а иногда и в одном и том же, эти термины зачастую также трактуются по-разному. На интуитивном уровне мы хорошо понимаем, о чем идет речь в том или ином контексте. Однако в курсовом и, в особенности, в дипломном проектировании, где студенту нужны все эти сущности, каждое из перечисленных слов должно иметь единственное значение.
Чем отличается метод от задачи, задача от модели, цель от задачи или от назначения? Даже лучшие студенты на защите дипломного проекта зачастую теряются в этих вопросах.
Всякое явление реального мира, будь то объект или процесс, может иметь несколько моделей. Кроме физической и виртуальной, все остальные можно считать математическими.
На одной модели, как правило, решается несколько задач.
Задача может быть решена разными методами (способами).
Метод решения задачи должен выбираться такой, который наилучшим образом служит достижению объявленной цели.
Всякий процесс или объект (искусственный) предназначен для выполнения каких-то функций.
Цель всегда связана с процессом. Например, хищник убивает добычу с целью обеспечить собственную жизнедеятельность. Программисты разрабатывают программную систему с целью автоматизировать какие-то процессы, которые в свою очередь, необходимо автоматизировать с целью улучшения экономических, социальных показателей, повышения безопасности, качества, быстродействия и т.п. Обычно цель указывают при решении сложных задач или при разработке новых методов. Тогда в конце работы необходимо привести результаты, подтверждающие достижение поставленной цели.
Математическая модель – приближенное описание какого-либо класса явлений внешнего мира, выраженное с помощью математической символики [1].
Математическая модель устанавливает соотношения (зависимости и ограничения) между совокупностью переменных [2] в виде системы уравнений и ограничений.
Нельзя говорить "математическая модель задачи", потому что задача решается на модели и для модели. На моделях решаются различные конкретные задачи. Собственно, модели и строятся для решения прикладных задач.
Таким образом, понятие "задача" уже, чем понятие "модель".
Математическая постановка задачи включает:
1. Словесная формулировка задачи – это сущность задачи и сущность метода е решения.
2. Математическая постановка задачи:
- исходные данные;
- выходные данные;
- цель, критерии оценки (отбора);
- возможные методы и ограничения – словесно-формульные алгоритмы.
Форма представления метода может быть аналитической или алгоритмической (пошаговой). Возможно и их сочетание, как например, в гл.6, где задача разбита на подзадачи (шаги), решаемые методами аналитической геометрии.
Если приведен полностью или взят за основу ранее опубликованный метод, то нужно обязательно сделать ссылку на первоисточник.
Используемый математический аппарат (чаще всего): алгебра, аналитическая геометрия, математический анализ, теория вероятностей и математическая статистика, численные методы, теория множеств, математическая логика, теория графов, реляционная алгебра, методы искусственного интеллекта и экспертных систем.
3. Доказательство – подтверждение правильности выбранного метода:
- математическое или - на примерах (программа, калькулятор и т.п.).
Не нужно в математической постановке задачи описывать вещи, не принципиальные, не используемые в алгоритме е решения. Например, в задаче поиска максимального числа в массиве вещественных чисел описывать диапазон и способ их представления. Но это должно быть сделано в описании программы.
Если в задаче использованы известные методы, то в описании сущности решения должны быть сделаны ссылки на источники.
Если задача разложена на подзадачи (что весьма приветствуется), то дополнительно нужно описать общий алгоритм.
Пример. Расчет количества услуг.
Задача расчета количества услуг, оказанных некоторым предприятием по производству услуг, например, парикмахерской, заключается в выборке из базы данных с помощью специального запроса и вычислении итогов.
Входные данные:
Дата начала расчетного периода: DateStart.
Дата окончания расчетного периода: DateFin.
Множество оказанных услуг: ServInfo={servinfoi, i = 0,…,L}, где L – количество оказанных услуг.
Услуга: servinfoi = < shifri, datai, fioi >, где shifri – шифр i-той услуги;
datai – дата оказания i-той услуги;
fioi – фамилия, имя, отчество оказавшего i-тую услугу.
Наименование и шифр рассчитываемой услуги: Name, ShifrC.
Выходные данные:
Множество одноименных оказанных услуг за расчетный период:
ServNamePeriod ServInfo.
Количество одноименных оказанных услуг за расчетный период:
ServNameCount.
Алгоритм (метод):
1. Установить ServNamePeriod = 0.
2. Если для множества ServInfo существует такое i, что шифр услуги servinfoi совпадает с заданным и дата исполнения лежит внутри заданного периода, то такая услуга помещается в искомое множество ServNamePeriod:
i(shifri = ShifrC) (DataStart datai < DataFin) ( servinfoi ServNai mePeriod) (ServNamePeriod servinfoi).
3. Количество оказанных услуг вычисляется с помощью функции:
Count(ServNamePeriod, ServNameCount).
Доказательство.
Пусть имеется таблица услуг, оказанных парикмахерской своим клиентам в течение 2006 года (табл. 1).
Задано наименование услуги – окрашивание волос и период – август. В результате получаем таблицу 2 и количество этих услуг, равное 3.
Шифр услуги Наименование услуги Дата оказания услуги Ф.И.О. оказавшего услугу Шифр услуги Наименование услуги Дата оказания услуги Ф.И.О. оказавшего услугу
2. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ
“КОМПЛЕКТАЦИЯ ПРОИЗВОДСТВА” (ФРАГМЕНТ)
Под задачей комплектации производства в АСУ механосборочного цеха понимается обеспечение сборки изделий комплектующими узлами и деталями, поступающими из других цехов путм подготовки соответствующих ведомостей.В приборостроении под собираемыми изделиями понимаются системы или стойки.
На предприятии для идентификации собираемых изделий и входящих в них деталей используется децимальный номер, а сами детали и изделия называются общим термином – детале-сборочная единица (ДСЕ).
Входные данные:
N_цех – множество цехов изготовителей ДСЕ;
№_зак – множество номеров заказов;
№_ДСЕ – множество децимальных номеров ДСЕ;
№_ДСЕ = {№_дсе1, №_дсе2,…, №_дсеn};
n – количество видов ДСЕ;
K_ком – количество комплектов ДСЕ;
N_вед_ш – множество номеров комплектовочных ведомостей-шаблонов;
N_вед – множество номеров комплектовочных ведомостей;
Action – событие; Action {Новая ведомость, Новая ведомость по шаблону};
T_оп – тип собираемого изделия; Т_оп {сборка, стойка, система};
Т_вед – тип ведомости; Т_вед {потребность, дефицит, требование};
Состав_изделий – описание состава собираемых изделий (сборок, стоек, систем) с указанием цехов-изготовителей, заказов, количества ДСЕ и входимости одного ДСЕ в другое:
Состав_изделий = {ДСЕ1, ДСЕ2, …, ДСЕm};
m – количество видов ДСЕ в составе изделия;
ДСЕi Состав_изделий и ДСЕi =, где №_закi №_зак;
№_дсе_1i №_ДСЕ;
№_дсе_2i №_ДСЕ и ДСЕ с номером №_дсе_1i входит в состав ДСЕ с номером №_дсе_2i;
№_цехi N_цех;
K_потрi – потребность в ДСЕ с номером №_дсе_1i, в штуках;
ДСЕ_в_заказах – множество номеров заказов с указанием собираемых изделий:
ДСЕ_в_заказах = {,, …,}, где k – количество заказов;
Для определения состава системы необходимо знать список входящих в не стоек, что можно представить в виде ссылок на заказы:
Zakaz_sos_system = {,, …, где l – количество заказов на стойки;
№_зак_вi - номер заказа стойки;
№_зак_с – множество заказов стоек:
№_зак_с = {№_зак1, №_зак2, …,№_закl}.
Выходные данные:
Список_документов = {Док1, Док2, …, Докd}, где Докi Список_документов и Докi = ;
d – количество ведомостей;
N_ведi N_вед;
Vпеч – печатная ведомость; Vпеч {потребность, дефицит, требование};
I_вед – изменнная комплектовочная ведомость.
Метод решения задачи.
На основании входных данных формируется список ДСЕ, которые должны быть выданы из кладовой на участок для сборки изделия.
Если Action = Новая ведомость и T_оп:
= сборка, то входными данными являются №_зак, K_ком, №_дсе.
Они используются для формирования списка ДСЕ получаемого из Action = Новая ведомость & T_оп = Сборка & Состав_изделий Добавить(), где Добавить – функция добавления элементов из множества Состав_изделий в множество Список_документов;
= стойка, то входными данными являются №_зак, K_ком. Для формирования списка ДСЕ нам необходимо знать стоечный номер ДСЕ. Его мы определяем, используя множество ДСЕ_в_заказах.
Далее формируем список ДСЕ, используя множество Состав_изделий:
Action = Новая ведомость & T_оп = Стойка & Данные_поиска Состав_изделий Найдена = TRUE, Action = Новая ведомость & T_оп = Стойка & Данные_поиска Состав_изделий Найдена = FALSE, Найдена = TRUE Добавить();
= система, то входными данными являются №_зак, K_ком. Система состоит из стоек и других ДСЕ. Значит, нам нужно получить входящие в не стойки (Zakaz_sos_sistem), определить номер ДСЕ каждой стойки (ДСЕ_в_заказах) и сформировать список ДСЕ (Состав_изделий):
где Добавить_з – функция добавления элемента x в множество ДСЕ_в_заказах Добавить_д(x), где Добавить_д - функция добавления элемента x в множество Action = Новая ведомость & T_оп = Система & Данные_поиска Состав_изделий Найдена = TRUE, Action = Новая ведомость & T_оп = Система & Данные_поиска Состав_изделий Найдена = FALSE.
Найдена = TRUE Добавить();
Если Action = Новая ведомость по шаблону, то формируем новую ведомость как копию ведомости-шаблона.
Далее мы сохраняем полученный список в базе данных. По сформированному списку можно сделать групповую выдачу из кладовой на участок, а также получить три ведомости (экранных или печатных):
Потребность. Она представляет собой полный список ДСЕ, в который входят также первоначальная потребность (количество нужное для выдачи на участок), текущая потребность (в зависимости от того делался ли уже расход по этой ведомости, она может быть равной или меньшей первоначальной);
Дефицит. В ней представлены только те ДСЕ, на которые имеется частичный или полный дефицит в кладовой;
Требование. В его состав входят ДСЕ, по которым возможна выдача, т.е. остаток в кладовой больше нуля и потребность не равна нулю.
3. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ ПОСТРОЕНИЯ
ВЫПУКЛОЙ ОБОЛОЧКИ НАБОРА ТОЧЕК
Задача построения выпуклой оболочки для набора точек возникает в процессе выявления компактных кластеров (областей, сгустков) для псевдослучайного распределения каких-либо объектов в пространстве, например, молекул или частиц при исследовании свойств новых материалов.3.1. Математическая модель выпуклой оболочки набора точек на плоскости Выпуклая оболочка набора точек S (обозначается CH(S)) – выпуклый полигон минимальной площади, содержащий все точки набора S [3].
Основные свойства выпуклой оболочки (рис. 3.1):
1. Прямая, проходящая через любое ребро выпуклой оболочки отделяет все точки набора точек S от внешней полуплоскости. Другими словами, все точки набора S лежат по одну сторону от прямой, проходящей через ребро выпуклой оболочки.
2. Хорда выпуклой оболочки – отрезок, соединяющий пару точек набора S. Любая хорда, лежит внутри выпуклой оболочки. Отрезки, ограничивающие полигон тоже являются хордами. Эти отрезки считаются принадлежащими полигону.
3. Точки набора S могут быть либо внутренними, либо крайними по отношению к выпуклой оболочке. В некоторых задачах крайние точки так же классифицируются как выступающие и невыступающие.
3.2. Задача построения выпуклой оболочки набора точек Входные данные: Дан набор S точек плоскости (рис. 3.2).
Выходные данные: Построить выпуклую оболочку CH(S) набора точек (рис. 3.3).
Рис. 3.2. Набор точек S на входе Рис. 3.3. Выпуклая оболочка CH(S) Алгоритм Джарвиса построения выпуклой оболочки набора точек Алгоритм Джарвиса так же известен как «алгоритм заворачивания подарка» [4].
Пошаговое описание алгоритма Джарвиса:
1. Найти экстремальную точку q набора точек S.
Экстремальная точка набора точек – точка с какой-либо экстремальной координатой относительно других точек набора. Таких точек 4. Алгоритм Джарвиса инвариантен к выбору экстремальной точки. Обычно берут самую нижнюю точку.
2. Найти отрезок с минимальным углом поворота к соответствующей оси ( min). Для нижней экстремальной точки необходимо искать точку с минимальным углом поворота к оси OX.
3. Цикл пока не придем в исходную точку q.
3.2. Найти точку с минимальным углом поворота относительно предыдущего ребра (рис. 3.4).
Угол между отрезками можно рассчитать по формуле:
где v1, v2 – вектора отрезков.
1. Вычислительная сложность метода Джарвиса Оценим временную сложность алгоритма Джарвиса. Для начала оценим временную сложность каждого шага алгоритма Джарвиса.
Шаг 1. Поиск экстремальной точки простым последовательным перебором точек занимает за линейное время – O(n).
Шаг 2. Поиск точки с минимальным углом поворота последовательным перебором занимает линейное время – O(n).
Шаг 3. Число итераций в цикле «пока не придем в исходную точку» равно h – числу точек-вершин выпуклой оболочки.
Шаг 3.1. Тело цикла занимает постоянное время – O(c).
Шаг 3.2. Тело цикла аналогично шагу 2 занимает линейное время – O(n).
Запишем итоговую функцию временной сложности для всего алгоритма с учетом его структуры: T(n) O(n n h (c n)) O(h n).
Рассмотрим влияние неопределенного фактора h на вычислительную сложность алгоритма Джарвиса (рис. 3.5., 3.6).
Рис. 3.5. Нет внутренних точек 5.1.1.2. Цикл j = 1..n поиска в i-той строке минимальной стоимости перевозки cmin и е координаты jmin:
5.2. Вычислим остатки запасов и потребностей:
Расчет потенциалов. В процессе решения после каждой итерации проверяется количество k загруженных клеток в таблице перевозок P:
k = 0; (i [1..m]) (j [1..n])(pi,j > 0) до m и j от 1 до n, если pi,j > 0, то увеличить k на 1.
Если k m + n – 1, то план называется вырожденным и дальнейший расчет не возможен.
Потенциалы – это вспомогательные переменные, вводимые для проверки оптимальности плана.
Расчет потенциалов выполняют по загруженным клеткам, для которых должно выполняться следующее равенство:
где i - потенциал i-того поставщика, j - потенциал j-того заказчика.
Алгоритм расчета потенциалов заключается в следующем:
1. Установим начальные значения потенциалов поставщиков:
ALFA = { i}, i [1,m] такие, что ( i ALFA) ( i = 0).
2. Установим начальные значения потенциалов заказчиков:
BETTA = { j}, j [1,n] такие, что ( j BETTA) ( j = 0).
3. Установим начальные значения флажков, сигнализирующих о том, что потенциал поставщика уже рассчитан:
ZA = {zai}, i [1,m] такие, что (zai ZA) ( zai = 0).
4. Установим начальные значения флажков, сигнализирующих о том, что потенциал заказчика уже рассчитан:
ZB = {zbj}, j [1,n] такие, что (zbj ZB) ( zbj = 0).
5. Установим начальные значения:
za1 = 1 – флажок потенциала первого поставщика;
k = 0 – количество загруженных клеток в плане перевозок.
6.1. Потенциал заказчика равняется стоимости первой перевозки к нему, уменьшенной на потенциал поставщика, если между ними есть перевозка и потенциал заказчика не вычислен и потенциал поставщика вычислен:
6.2. Потенциал поставщика равняется стоимости первой перевозки от него, уменьшенной на потенциал заказчика, если между ними есть перевозка и потенциал поставщика не вычислен, а потенциал заказчика вычислен:
Таким образом, если есть перевозка pij, то i = cij - j, j = cij - i, т.е. и то и другое равняется cij.
Если нет ни одной перевозки от i-того поставщика, то i = 0, т.е. поставщик не загружен.
Если нет ни одной перевозки от j-того поставщика, то j = 0, т.е. заказчик не обслужен.
Проверка плана на оптимальность. План считается оптимальным, если во всех его незагруженных клетках (в которых перевозки отсутствуют) выполняется условие i + j cij, т.к. и поставщик и заказчик загружены:
(Flag=false).
Если план не оптимален, то нужно продолжить вычисление.
Поиск звена максимальной неоптимальности. Звено максимальной неоптимальности находится как max( i + j - сi,j) среди незагруженных клеток.
Эту клетку необходимо загрузить за счет перераспределения ресурсов из других загруженных клеток. Клетку в таблице помечаем знаком "+", так как здесь в начальном плане находится вершина максимальной неоптимальности:
Составление контура перераспределения ресурсов. Контур перераспределения представляет собой многоугольник со сторонами, параллельными строкам и столбцам матрицы, и удовлетворяет следующим правилам:
1) все углы контура прямые;
2) в каждой вершине контура встречаются только два звена;
3) число вершин контура четное;
4) все вершины лежат на загруженных клетках, кроме клетки максимальной неоптимальности;
5) в каждой строке (столбце) матрицы имеются только две вершины: одна - загружаемая, другая – разгружаемая.
Контур перераспределения ресурсов (КПР):
где uik – i-координата k-той вершины контура;
ujk – j-координата k-той вершины контура.
ALL(i, j) Алгоритм построения контура перераспределения ресурсов (КПР):
1. Введем рабочее множество TP = {tpij}, i [1,m], j [1,n], элементы которого в исходном состоянии совпадают с элементами множества P перевозок:
(i [1,m]) (j [1,n]) ( tpij = pij).
2. Установим Flag=false – флаг, сигнализирующий, что в таблице остались только вершины КПР.
3. Цикл пока Flag=false – для исключения перевозок, которые не могут быть перераспределены:
3.1. Переустановка Flag=true.
3.2. Обнуление перевозок, которые не могут быть перераспределены вдоль своей строки или столбца:
(Flag=false).
4. Первая вершина КПР совпадает с элементом максимальной неопределенности ла.
5.1. Увеличиваем индекс вершины КПР: k := k +1.
иначе смещение вдоль столбца: j= ujk-1, ujk = j, 6. Длина контура перераспределения l = k 1.
Поиск минимального элемента в контуре перераспределения. Перераспределение ресурсов по контуру осуществляется с целью получения оптимального плана. В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных х, ни одно из этих значений не должно превратиться в отрицательное число. Поэтому анализируют только разгружаемые клетки, из которых выбирают клетку с минимальным объемом перевозок (минимальный элемент в контуре):
MINEL = tpui1,uj1 ;
Перераспределение ресурсов по контуру производится очень просто:
при движении по столбцу от имеющихся компонентов плана надо отнимать минимальный элемент в контуре, а при движении по строке наоборот, прибавлять минимальный элемент в контуре:
(k [1,l]) ( puik,ujk = puik,ujk + MINEL Sign(k)), где функция Sign(k) 5.3. Описание контрольного примера Для описания контрольного примера возьмем процесс построения оптимального плана поставки продукции, выполняемый нашей программой и проведем его вручную.
Фирма имеет 3 склада на которых хранится картофель. С этой фирмой заключили договор на поставку картофеля 4 крупных магазина. Первому магазину необходимо 10 тонн картофеля, второму – 30, третьему – 70, четвертому – 30. На первом складе фирмы хранится 20 тонн картофеля, на втором – 40 тонн, на третьем 80 тонн. Необходимо получать оптимальный план поставки картофеля потребителям. Так же на основе статистических исследований известна стоимость доставки (в сот. руб.) из каждого склада в каждый магазин. Итак, мы имеем начальные данные, которые представлены в таблице 4.
Методом минимальной стоимости по строке определяем начальный план:
Расчет потенциалов загруженных и незагруженных клеток:
Проверка плана на оптимальность по незагруженным клеткам:
План оптимальный, т.к для всех незагруженных клеток выполняется Общие транспортные издержки:
Итак, в результате построения плана поставки мы выяснили что мы достигнем минимальных транспортных издержек в том случае если:
Из 1-го склада доставим во 2-й магазин 20 тонн картофеля.
Из 2-го склада доставим 40 тонн в 3-й магазин.
Из 3-го склада доставим в 1-й магазин 10 тонн, во 2-й магазин 10 тонн, в 3-й магазин 30 тонн, в 4-й магазин 30 тонн. При этом общие транспортные издержки составят 360 сот. руб.
6. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ
НАХОЖДЕНИЯ МАКСИМАЛЬНОЙ ПЛОЩАДИ ОКРУЖНОСТИ
ВНУТРИ ЧЕТЫРЕХУГОЛЬНИКА
Найти площадь максимальной окружности, которую можно нарисовать внутри произвольного четырехугольника.где T = {(x, y) | x, y } – множество точек евклидовой плоскости, на которой задана декартова прямоугольная система координат xOy.
Q = (A, B, C, D) – четырехугольник ABCD, где A, B, C, D T (рис. 6.1).
S – максимальная площадь окружности, которую можно нарисовать внутри четырехугольника ABCD, S.
Далее приведен метод решения задачи в аналитической форме и в алгоритмической.
6.1. Аналитическая форма представления метода Искомое значение максимальной площади S окружности, которая лежит внутри четырехугольника ABCD, можно получить в результате ряда экспериментов:
где Oi = ( i, i) – окружность, i = 0,... n, n – количество произведенных экспериментов, n ;
Inside (t, F)= t T, F = (pt1, pt2, …, ptm) – геометрическая фигура, вершинами которой Окружности Oi находятся внутри четырехугольника Q:
Функция, возвращающая площадь окружности Oi = ( i, i):
Определим функцию Inside(t, Q), характеризующую положение точки t T по отношению к четырехугольнику Q:
Inside(t, Q) = Inside(t, QT1) Inside(t, QT2), где QT1 и QT2– треугольники такие, что QT1 = (q, q mod 4 + 1, q( +1) mod 4 + 1), QT2 = (q, q( +1) mod 4 +1, q( +2) mod 4 + 1), где – такое натуральное число от 1 до 4, что u > 180, если Q – невыпуклый четырехугольник, или произвольное натуральное число от 1 до 4, если Q – выпуклый четырехугольник (рис. 6.2).
Углы четырехугольника: U=( DAB, ABC, BCD, CDA).
Вершины четырехугольника qj Q = (A, B, C, D), j = 1, …, 4.
Пусть вершины треугольника Tr имеют координаты (x1,y1), (x2,y2), (x3,y3).
Значение функции Inside (t, Tr), характеризующее принадлежность точки t треугольнику Tr, определяется как истинность равенства площади Tr сумме площадей трех треугольников, образованных точкой t и каждой из трех сторон Tr (рис. 6.3):
Inside(t, Tr) = + Square (t, (x2, y2), (x3, y3)) + Square (t, (x3, y3), (x1, y1));
где Square (Tri) – функция, возвращающая площадь треугольника Tri = (pt1, pt2, pt3), pt1, pt2, pt3 T:
Длины сторон треугольника: a = length(pt1, pt2), b = length(pt2, pt3), c = length(pt3, pt1), где length(l) – функция, возвращающая длину отрезка l = (pt1, pt2), pt1, pt T. Вершины треугольника – точки pt1 и pt2 имеют координаты (x1, y1) и (x2, y2) соответственно. Тогда length(l) = Определим значение функции Inside (t, Oi), характеризующей положение точки t T по отношению к окружности Oi = ( i, i), i = 0, … n:
Пусть окружность максимального радиуса была получена в результате nго эксперимента: S = Square (On). Square(On) = n, из чего следует, что внутреннюю для четырехугольника окружность максимальной площади можно искать как внутреннюю окружность максимального радиуса. Рассмотрим порядок непосредственного нахождения значения максимального радиуса n внутренней окружности для четырехугольника Q.
Проверим выпуклость четырехугольника Q. Один из критериев выпуклости многоугольника – одинаковый знак определителей всех пар его смежных сторон. Основываясь на этом свойстве, рассмотрим возможные значения суммы этих определителей где (xA, yA), (xB, yB), (xC, yC), (xD, yD) – координаты точек A, B, C и D соответственно.
Выпуклый четырехугольник (| | = 4). Случаю выпуклости четырехугольника Q соответствует значение | | = 4 (все определители (6.2) имеют одинаковый знак).
Для выпуклого четырехугольника внутренняя окружность максимального радиуса касается минимум трех его сторон (рис. 6.4). Следовательно, центр такой окружности лежит на пересечении биссектрис двух углов, имеющих общую сторону. Радиус окружности с центром в этой точке определяется как минимальное из расстояний от этой точки до каждой из сторон.
где Mij – точка пересечения биссектрис углов ui и uj четырехугольника Q, такая, что Inside(Mij, Q) = 1;
qp – вершины четырехугольника Q = (A, B, C, D), p = 1, …, 4;
xpt, ypt – координаты точки pt T, xpt, ypt.
Уравнение биссектрисы угла, образованного поворотом прямой, заданной нормированным уравнением xcos 1 + ysin 1 – 1 = 0;, против часовой стрелки до На рис. 6.4 представлен пример построения внутренней окружности максимального радиуса при i = 1, j = 2.
Четырехугольник с самопересечением (| | = 0). Случаю четырехугольника с самопересечением (рис. 6.5) соответствует значение | | = 0 (два определителя (6.2) положительны, два – отрицательны).
Назовем такое натуральное число из множества {1, 2}, что ( L T) L = CrossingPoint ((q, q mod 4 + 1), (q( + 1) mod 4 + 1, q( + 2) mod 4 + 1)), (6.5) где qj – вершины четырехугольника Q = (A, B, C, D), j = 1, …, 4, CrossingPoint((eн1, eк1), (eн2, eк2)) – функция, возвращающая точку пересечения отрезков (eн1, eк1) и (eн2, eк2); eн1, eк1, eн2, eк2 T.
Определим порядок нахождения точки пересечения:
Пусть = 1, и пересекаются стороны четырехугольника AB и CD, L = CrossingPoint(AB, CD) (см. рис. 6.5).
Определение внутренней окружности максимального радиуса сводится к определению максимальной из окружностей, вписанной в треугольники ALD и BLC.
где функция InnerRadius(Tr) возвращает значение радиуса вписанной окружности для треугольника Tr.
Пусть вершины треугольника Tr имеют координаты (x1, y1), (x2, y2), (x3, y3). Тогда центру вписанной окружности для Tr соответствует точка V с коорb x1 c x2 a x3 b y1 c y2 a y y1), (x2, y2)), b = length((x2, y2), (x3, y3)), c = length((x3, y3), (x1, y1)), p = a + b + c.
Радиус вписанной окружности InnerRadius(Tr) определяется как расстояние от V до любой из сторон треугольника:
Звездчатый четырехугольник (| | = 2). Случаю звездчатого четырехугольника соответствует значение | | = 2 (знак одного из определителей формулы (6.2) отличается от знака остальных).
Полученное значение соответствует значению угла uб>180. Пусть = 2, и поставленному условию удовлетворяет угол BCD (рис. 6.6).
Рассмотрим углы ACD= и ACB=.
Пусть истинно утверждение ( < 90 ) ( < 90 ) (один из углов и меньше 90 ). Представим четырехугольник Q как объединение треугольников ABE и ADF (E = CrossingPoint (AD, BC); F = CrossingPoint (AB, CD).
Окружностью максимального радиуса, которую можно построить внутри Q, в данном случае является максимальная из окружностей, вписанных в ABE и ADF (рис. 6.7):
меньше 90 ) внутренняя окружность максимального радиуса для четырехугольника Q проходит через точку C и касается сторон AB и DA (рис. 6.8).
Радиус n = length( n, C), где n – такая точка внутри четырехугольника, Inside( n, Q) = 1, что pAB = pAD = length( n, C); pv – перпендикуляр, проведенный к стороне v, v {AB, AD}, из точки n.
Поскольку pAB = pAD, точка n лежит на биссектрисе DAB.
Используя формулу (6.4), найдем уравнение биссектрисы угла DAB из уравнений прямых AB и AD. Пусть оно имеет вид K1биссx +K2биссy +K3бисс= 0.
Пусть (x,y ) – центр окружности радиуса 1, вписанной в угол DAB (рис. 6.9). Координаты (x,y ) являются решением системы K1ABx + K2ABy + K3AB = 0 – уравнение прямой AB.
где 1. Математическая энциклопедия: Гл. ред. И.М.Виноградов, т.3 Коо-Од – М: "Советская энциклопедия", 1982. – 1184 стб., ил.
2. Карманов В.Г. Математическое программирование, М.: – Наука, 1975.
3. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение: Пер.
с англ. – М.: Мир, 1989. – 478 с.
4. Ласло М. Вычислительная геометрия и компьютерная графика на С++:
Пер. с англ..: "Издательство Бином", 1997. – 304 с.
5. Фролькис В.А. Введение в теорию и методы оптимизации для экономистов. – СПб.: Питер, 2002.
1. Дальниченко И.А. и др. Автоматизированные системы управления предприятиями: Учебник для инженерных специальностей вузов / И.А.Дальниченко, В.А.Мясников, В.Н.Четвериков. – М.: Машиностроение, 1984. – 360 с.
2. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2000. – 304 с.
3. Гуц А.К. Математическая логика и теория алгоритмов: Уч. пособие. – Омск: Диалог-Сибирь, 2003. – 108 с.
«