Взадачах рассматриваемого класса параметры размещения {

Вид материала

Задача

Подобный материал:

• Элективный курс по математике для учащихся 9 класса тема: «уравнения и неравенства,, 248.15kb.
• Isbn 978-5-7262-1377 нейроинформатика 2011, 136.96kb.
• Дневные программы обучения без размещения. Кроме занятий в школе курс Junior Day Programme, 162.83kb.
• Проекта, 43.2kb.
• Вопрос Параметры звука, 183.33kb.
• Лобанов Михаил Михайлович (научный сотрудник Института экономики ран, аспирант географического, 74.38kb.
• Рабочая программа элективного курса по математике «Знакомьтесь: модуль и параметры!», 100.3kb.
• Программа обучения на курсах продвижения сайтов: Тема Виды и методы продвижения сайтов, 61.1kb.
• Темы контрольных работ по индустрии гостеприимства Классификация средств размещения, 9.25kb.
• За курс 9 класса билет, 42.57kb.

Оcобенности программной реализации нелинейных оптимизационных задач размещения геометрических объектов

Novozhilova M.V., Chub I.А., Belenchenko I.V., Murin М.N.

Рассмотрим класс задач оптимизационного геометрического проектирования [1], состоящих в поиске оптимального размещения конечного набора T={T_i}, i=1,2,…I, геометрических объектов произвольной пространственной формы (int T_i  ), геометрические характеристики которых могут изменяться, в заданной области Т₀ без взаимных наложений при наличии различных ограничений и критериев качества размещения.

В общем случае геометрическая информация g_i [1] об объекте Т_i состоит из:

•  совокупности пространственных форм {s_i}, составляющей объект Т;
  
•  набора метрических характеристик {m_i}, определяющих размеры точечных множеств, имеющих пространственную форму {s};
  
•  параметров размещения {u_i} объекта Т_i в области Т₀ [1].
  

В задачах рассматриваемого класса параметры размещения {u_i} объекта Т_i в области Т₀ могут содержать как параметры трансляции , так и угловой параметр .

Оптимизационные задачи такого рода возникают во многих областях человеческой деятельности – управление ресурсами проекта, задачи энергосбережения, задачи раскроя материалов. К данной задаче в указанной постановке могут быть сведены также задачи оптимизации распределения ресурсов в календарном планировании [2].

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

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

В Украине ведущей в этом направлении является научная школа проф. Стояна Ю.Г. (г. Харьков). 

Приведем некоторые постановки задач рассматриваемого класса.

Задача 1. Поиск оптимального размещения конечного набора неориентированных многоугольных геометрических объектов в заданной многосвязной многоугольной области.

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

, (1)

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

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

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

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




Математическая модель Задачи 1 имеет вид:

найти: , (2)

где ;  область допустимых решений задачи;  – подобласть, выделяемая ограничениями на размещение в полосе ; ,  задаются условиями попарного взаимного непересечения (, , и условиями попарного взаимного непересечения объектов размещения , соответственно.

Задача 2. Поиск оптимального размещения конечного набора прямоугольных геометрических объектов с изменяемыми метрическими характеристиками.

Пусть заданы область размещения R₀ E² (s_0­ = «прямоугольник», m₀= (W, Z), W – const, Z – var) и конечный набор R = {R_i}, i=1,…, I объектов размещения (s_i = «прямоугольник», m_і= (а_і, b_i), а_і, b_i – var, u_i=(х_i,у_i) - параметры размещения объекта R_i в E²) (рис.2).




Рис.2.


Метрические характеристики а_i и b_i объектов R_i в процессе размещения могут изменяться


a_i[a_i min, a_i max], b_i[b_i min, b_i max], a_{i  min} >0, b_{i  min} > 0. (3)


причем площадь S_i размещаемых объектов остается неизменной:


b_i= S_i / a_i. (4)

Необходимо разместить набор объектов R_і в полубесконечной полосе R₀ без наложений друг на друга так, чтобы величина Z была минимальной:

, (4)

где область допустимых решений D =D₁ Ç D₂ определяется условиями

D₁: intR_i (х_i, у_i, а_і, b_i) Ç intR_j (х_j, у_j, а_j, b_j) = Æ, i,j=1,2,…,N, ij, (5)

D₂: R_i (х_i, у_i, а_i)  R₀, i=1,2,…,N. (6)


Задача 3. Поиск оптимального распределения ресурсов проекта во времени с учетом различной динамики изменения стоимости ресурсов

Рассмотрим проект, который состоит из N работ (операций) R=R{R_i}, i=1, 2,…, N. На множестве работ R задано условие частичной упорядоченности вида R_iR_j, i, j  {1,2, …N}, i  j, определенное конкретной последовательностью выполнения работ. Для каждой работы R_i известны ее величины ресурсов, необходимых для ее выполнения: : где  продолжительность работы,  два других вида ресурсов в стоимостном выражении.

В пространстве ресурсов Е³ работа  параллелепипед. Положение каждой работы в Е³ характеризуется вектором параметров размещения u_i=, задающим положение полюса собственной системы координат X_iY_iZ_i. Ограничения на возможные ресурсы проекта в целом выделяют в Е³ параллелепипед R₀:(T^M,B₁^M,B₂^M), где T^М  время, максимально возможное для выполнения данного проекта, B₁^M, B₂^M  максимальное финансовое обеспечение проекта по видам ресурсов.

Дисконтирование инвестиционных затрат по видам ресурсов учитывается изменением метрических характеристик объектов (что моделирует применение показателя наращения денег V(t)1) по линейному закону вида

, j=1,2. (7)

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

, (8)

 , (9)

D:, (10)

, (11)

Несмотря на разнообразие постановок задач, основными ограничениями на область допустимых решений D являются геометрические ограничения на размещение объекта R_i в области размещения R₀ и условия попарного взаимного непересечения объектов.

Основные свойства оптимизационных задач 1-3. таковы:

Свойство 1. Область D  невыпуклое, несвязное ограниченное точечное множество, имеющее кусочно-гладкую границу .

Свойство 2. Область D допускает представление в виде объединения конечного числа выпуклых подобластей D_g вида

, (12)

Алгоритмическая и программная реализация математических моделей представленных задач предполагает учет следующих факторов: 1) неточность задания исходных данных задачи (вектора метрических характеристик набора объектов размещения и области размещения), 2) наличие вычислительной ошибки метода решения, вызванной нелинейностью функций ограничений области допустимых решений D и, возможно, функции цели. Кроме того, область допустимых решений D является существенно вырожденной – оптимальная вершина области описывается переопределенной системой уравнений, что вызывает необходимость разработки и реализации специальных программных средств учета ошибок округления алгоритма решения задачи.

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

ЛИТЕРАТУРА

1. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. – К.: Наук. думка, 1986. – 268 с.

2. Управление проектами: Справочное руководство / Под ред. И.И. Мазура и В.Д. Шапиро. – М.: Высшая школа, 2000. – 875 с.

3. Гилл Дж., Мюррей К., Райт М. Практическая оптимизация. – М.: Наука, 1984, 459с.