Математична модель та чисельні методи розв'язання задачі оптимізації розміщення прямокутників

Розділ 2
Математична модель задачі оптимізації розміщення прямокутників
2.1. Постановка задачі оптимізації, визначення множини її припустимих
розв’язків
Нехай є m взаємоорієнтованих геометричних об’єктів прямокутної форми (Dj М R2,
j = 1,…, m) та область їх розміщення Щ.
Основними характеристиками прямокутного об’єкту є його розміри lj(l1j,l2j) та
положення у просторі, яке визначається координатами його полюсу zj(оj1, оj2), j
= 1, 2,…, m [12]. Полюсом прямокутника будемо називати точку перетину його
діагоналей. Очевидно, що розміщення m прямокутних об’єктів буде визначатись
вектором z = (z1, z2, ..., zm).
Необхідно знайти таке розміщення прямокутних об’єктів в області Щ, при якому
досягає екстремуму обраний критерій якості:
f(z) ® extr, zОG, (2.1)
де f(z) – неперервно диференційована функція, G ­– множина припустимих
розв’язків поставленої задачі оптимізації.
Область розміщення
Розглянемо область розміщення прямокутників Щ. Вона може мати наступний вигляд.
Область розміщення являє собою прямокутник (рис. 2.1.).
Система координат задається таким чином, щоб її початок знаходився в вершині
прямокутника , розміри якого визначаються вектором a(a1,a2), а координатні вісі
співпадають з ребрами паралелепіпеда і спрямовані так, щоб всі точки мали
невід’ємні координати.
Тоді область розміщення описується наступною системою обмежень:
Рис. 2.1. Приклад розміщення прямокутників для двовимірного випадку в
n-вимірному паралелепіпеді.
Область розміщення являє собою перший квадрант (рис. 2.2.).
Рис. 2.2. Приклад розміщення прямокутників для двовимірного випадку в
необмеженій області розміщення.
Область розміщення являє собою напівскінчену смугу (рис. 2.3.).
Рис. 2.3. Приклад розміщення прямокутників для двовимірного випадку в
напівскінченній смузі.
Область розміщення являє собою прямокутник, який містить прямокутні зони
заборони.
Рис. 2.4. Приклад розміщення прямокутників для двовимірного випадку в
n-вимірному паралелепіпеді із зонами заборони.
Множина припустимих розв’язків G
Розглянемо множину припустимих розв’язків G поставленої задачі оптимізації.
На розміщення об’єктів прямокутної форми накладаються геометричні обмеження,
які являють собою:
умови взаємного неперетинання прямокутників;
умови належності прямокутників області розміщення Щ у випадку, коли область
розміщення не співпадає з R2.
Так як положення j-го (j = 1, ..., m) прямокутника в просторі визначається
координатами його полюсу zj(оj1, оj2), а розміри – вектором lk(l1k,l2k), то:
умови взаємного неперетинання прямокутників D1,...,Dm можна записати так – для
кожної пари Ds, Dp прямокутників існує хоча б одне і О {1,2} таке, що
; (2.2)
умови належності прямокутника області W мають наступний вигляд
– для кожного прямокутника Dj виконується
. (2.3)
Наведені обмеження (2.2), (2.3) описують множину G, яка є багатовимірною,
багатозв’язною, а також може бути незв’язною.
Таким чином, задача (2.1) є задачею оптимізації опуклої функції цілі на множині
складної структури.
Розглянемо особливості поставленої задачі:
Задача має велику вимірність, оскільки вимірність простору параметрів
розміщення дорівнює , де – кількість прямокутників, які розміщуються в цій
області.
Область зміни параметру z в загальному випадку є багатовимірною,
багатозв’язною, а також може бути незв’язною.
Кількість нерівностей, що визначають множину припустимих розв’язків G, залежить
від кількості прямокутників, що розміщуються.
Множина припустимих розв’язків G поставленої задачі описується лінійними
нерівностями (2.2)-(2.3).
Обмеження (2.2)-(2.3), що визначають множину припустимих розв’язків G, містять
велику кількість нульових коефіцієнтів.
Таким чином, класичних методів умовної оптимізації для розв’язання поставленої
задачі (2.1) не існує. Це пов’язано із складною структурою множини її
припустимих розв’язків G. Необхідною умовою застосування таких методів є
опуклість множини припустимих розв’язків.
Розроблена методологія вирішення цієї проблеми та розв’язання поставленої
задачі (2.1) є такою:
Представити множину припустимих розв’язків G у вигляді об’єднання опуклих
підмножин, кожна з яких описується системою лінійних обмежень.
Розв’язати підзадачі оптимізації заданої функції цілі на побудованих
підмножинах множини припустимих розв’язків G, обравши для цього відповідні
методи умовної оптимізації.
Забезпечити перехід від однієї побудованої підзадачі до іншої з обов’язковим
поліпшенням функції цілі (для скорочення часу розв’язання вихідної задачі).
2.2. Декомпозиція множини припустимих розв’язків
Представимо множину припустимих розв’язків поставленої задачі, що має складну
структуру, у вигляді об’єднання опуклих підмножин [27-29].
Нерівність (2.2), яка описує умову взаємного неперетинання прямокутників Ds та
Dp , можна представити в наступному вигляді:
(2.2’)
Очевидно, перша нерівність з умов (2.2’) визначає випадок, коли прямокутник Ds
повинен знаходитися праворуч від прямокутника Dp по відповідній вісі і не
перетинати його.
Відповідно, друга нерівність визначає випадок, коли прямокутник Ds повинен
знаходитися ліворуч від прямокутника Dp по відповідній вісі і не перетинати
його.
Для того, щоб два прямокутника не перетиналися достатньо, щоб одна з
нерівностей (2.2’) виконувалась хоча б для одного і О {1,2}.
Оберемо для кожної пари прямокутників одну з координат, за якою буде задана
умова неперетинання, та для обраної координати визначимо одну з двох умов
неперетинання (2.2’). До побудованих таким чином умов додамо нерівності (2.3),
що визначають умови належності прямокутників області .
(2.2’’)
Кожна з систем (2.2’’) є системою лінійних нерівностей і тому визнач