Розробка алгоритму та його програмна реалізація для комп’ютеризованої системи оптимального розподілу квазістохастичного ресурсу

Отже, оптимізація - цілеспрямована діяльність, що полягає в одержанні найкращих результатів при відповідних умовах.

Сфера застосування методів оптимізації:

o розробка прогнозу;

o планування;

o інвестування;

o складання розкладу робіт;

o керування транспортними потоками;

o визначення оптимальної стратегії в конкурентній боротьбі;

o виявлення вузьких місць, меж рентабельності, стійкості бізнесу;

o призначення об'єктів однієї групи об'єктам іншої групи;

o рішення систем рівнянь в економічних і інженерних задачах.

3.2.2 Постановка задачі оптимізації

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

- кількість продукції - "витрати сировини"

- кількість продукції - "якість продукції"

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

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

1. Наявність об'єкта оптимізації й мети оптимізації. При цьому формулювання кожної задачі оптимізації повинно вимагати екстремального значення лише однієї величини, тобто одночасно системі не повинне приписуватися два й більше критерій оптимізації, тому що практично завжди экстремум одного критерію не відповідає экстремуму іншого. Типовий приклад неправильної постановки задачі оптимізації:

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

Правильна постановка задачі могла бути наступна:

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

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

У першому випадку критерій оптимізації - продуктивність, а в другому - собівартість.

2. Наявність ресурсів оптимізації, під якими розуміють можливість вибору значень деяких параметрів об'єкта оптимізації. Об'єкт повинен мати певні ступені волі - керуючими впливами.

3. Можливість кількісної оцінки величини оптимызацыъ, оскільки тільки в цьому випадку можна порівнювати ефекти від вибору тих або інших керуючих впливів.

4. Облік обмежень.

3.2.3 Види обмежень

Незважаючи на те, що прикладні задачі ставляться до зовсім різних областей, вони мають загальну форму. Всі ці задачі можна класифікувати як задачі мінімізації функції f(x) N-мірного векторного аргументу x = (x1, x2,..., xn), компоненти якого задовольняють системі рівнянь hk(x) = 0, набору нерівностей gi(x) ? 0, а також обмежені зверху й знизу, тобто xi(u) ? xi ? xi(l). У наступному викладі функцію f(x) будемо називати цільовою функцією, рівняння hk(x) = 0 - обмеженнями у вигляді рівностей, а нерівності gi(x) ? 0 - обмеженнями у вигляді нерівностей.

Задача загального виду:

мінімізувати f(x) при обмеженнях

hk(x) = 0, k = 1, ..., K,

gj(x) ? 0, j = 1, ..., J,

xi(u) ? xi ? xi(l), I = 1, ..., N

називається задачею оптимізації з обмеженнями або задачею умовної оптимізації. Задача, у якій немає обмежень, тобто

J = K = 0;

xi(u) = xi(l) = ?, i=1, ..., N,

називається оптимізаційною задачею без обмежень або задачею безумовної оптимізації.

3.2.4 Критерії оптимальності

Звичайно величина оптимізації пов'язана з економічністю роботи розглянутого об'єкта (апарат, цех, завод). Оптимізуємий варіант роботи об'єкта повинен оцінюватися якоюсь кількісною мірою - критерієм оптимальності.

Критерієм оптимальності називається кількісна оцінка оптимізуємої якості об'єкта.

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

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

Найбільш загальною постановкою оптимальної задачі є вираження критерію оптимальності у вигляді економічної оцінки (продуктивність, собівартість продукції, прибуток, рентабельність). Однак у приватних задачах оптимізації, коли об'єкт є частиною технологічного процесу, не завжди вдається або не завжди доцільно виділяти прямий економічний показник, який би повністю характеризував ефективність роботи розглянутого об'єкта. У таких випадках критерієм оптимальності може служити технологічна характеристика, що побічно оцінює економічність роботи агрегату (час контакту, вихід продукту, ступінь перетворення, температура). Наприклад, установлюється оптимальний температурний профіль, тривалість циклу - "реакція - регенерація". Але в кожному разі будь-який критерій оптимальності має економічну природу.

Розглянемо більш докладно вимоги, які повинні пред'являтися до критерію оптимальності.

1. Критерій оптимальності повинен виражатися кількісно.

2. Критерій оптимальності повинен бути єдиним.

3. Критерій оптимальності повинен відбивати найбільш істотні сторони процесу.

4. Бажано щоб критерій оптимальності мав ясний фізичний зміст і легко розраховувався.

Будь-який оптимізуємий об'єкт схематично можна представити в такий спосіб:



Мал. 3.1 О б'єкт оптимізації

Позначення: Y - виходи об'єкта;

X - контрольовані вхідні параметри;

U - регульовані вхідні параметри керуючі параметри;

Z - неконтрольовані впливи.

При постановці конкретних задач оптимізації критерій оптимальності повинен бути записаний у вигляді аналітичного вираження. У тому випадку, коли випадкові збудження невеликі і їхній вплив на об'єкт можна не враховувати, критерій оптимальності може бути представлений як функція вхідних, вихідних і керуючих параметрів:

R = R(X1, X2,...,XN, Y1,Y2,...,YN, U1,U2,..., UN)

Тому що Y=f (U), то при фіксованих Х можна записати:

R = R(Ui)

При цьому будь-яка зміна значень керуючих параметрів подвійно позначається на величині R:

- прямо, так як керуючі параметри безпосередньо входять до вираження критерію оптимізації;

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

Якщо ж випадкові збудження досить великі і їх необхідно враховувати, то варто застосовувати експериментально - статистичні методи, які дозволять одержати модель об'єкта у вигляді функції:

Y = j(Xi,Ui)

яка справедлива тільки для вивченої локальної області. Тоді критерій оптимальності прийме наступний вид:

R = R(X,U)

У принципі, для оптимізації замість математичної моделі можна використати й сам об'єкт, однак оптимізація досвідченим шляхом має ряд істотних недоліків:

а) необхідний реальний об'єкт;

б) необхідно змінювати технологічний режим у значних межах, що не завжди можливо;

в) тривалість випробувань і складність обробки даних.

Наявність математичної моделі (за умови, що вона досить надійно описує процес) дозволяє значно простіше вирішити задачу оптимізації аналітичним або чисельним методами.

У задачах оптимізації розрізняють прості й складні критерії оптимізації.

Критерій оптимальності називається простим, якщо потрібно визначити экстремум цільової функції без завдання умов на які-небудь інші величини. Такі критерії звичайно використаються при рішенні приватних задач оптимізації (наприклад, визначення максимальної концентрації цільового продукту, оптимального часу перебування реакційної суміші в апарату й т.п.).

Критерій оптимальності називається складним, якщо необхідно встановити экстремум цільової функції при деяких умовах, які накладаються на ряд інших величин (наприклад, визначення максимальної продуктивності при заданій собівартості, визначення оптимальної температури при обмеженнях по термостійкості каталізатора й ін.).

Процедура рішення задачі оптимізації обов'язково включає, крім вибору керуючих параметрів, ще й установлення обмежень на ці параметри (термостійкість, вибухобезпечність, потужність перекачувальних пристроїв). Обмеження можуть накладатися як по технологічним, так і по економічних міркуванням.

Отже, для рішення задачі оптимізації необхідно:

а) скласти математичну модель об'єкта оптимізації:

Y = f(X,U)

б) вибрати критерій оптимальності й скласти цільову функцію:

R = ц(Y) = F(X,U)

в) установити можливі обмеження, які повинні накладатися на змінні:

шi(X,U) = 0

шi(X,U) < 0

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

Прийнято розрізняти задачі статичної оптимізації для процесів, що протікають у сталих режимах, і задачі динамічної оптимізації.

У першому випадку вирішуються питання створення й реалізації оптимальної моделі процесу, у другому - задачі створення й реалізації системи оптимального керування процесом при несталих режимах експлуатації.

3.2.5 Класифікація задач

Задачі оптимізації можна класифікувати відповідно до виду функцій f, hk, gi і розмірністю вектора x. Задачі без обмежень, у яких x являє собою одномірний вектор, називаються задачами з один змінної й становлять найпростіший, але разом з тим досить важливий підклас оптимізаційних задач. Задачі умовної оптимізації, у яких функції hk, і gi є лінійними, звуться задачами з лінійними обмеженнями.

В таких задачах цільові функції можуть бути або лінійними, або нелінійними. Задачі, які містять тільки лінійні функції вектора безперервних змінних x, називаються задачами лінійного програмування; у задачах цілочислового програмування компоненти вектора x повинні приймати тільки цілі значення.

Задачі з нелінійною цільовою функцією й лінійними обмеженнями іноді називають задачами нелінійного програмування з лінійними обмеженнями. Оптимізаційні задачі такого роду можна класифікувати на основі структурних особливостей нелінійних цільових функцій. Якщо f(x) - квадратична функція, то ми маємо справу із задачею квадратичного програмування; якщо f(x) є відношення лінійних функцій, то відповідна задача зветься до задачі дробно - лінійного програмування, і т.д. Ділення оптимізаційних задач на ці класи становить значний інтерес, оскільки специфічні особливості тих або інших задач відіграють важливу роль при розробці методів їхнього рішення (Мал. 3.2).



Мал. 3.2 Класифікація задач математичного програмування:

3.2.6 Методи рішення задач оптимізації.

Задачі одномірної мінімізації являють собою найпростішу математичну модель оптимізації, у якій цільова функція залежить від однієї змінної, а припустимою множиною є відрізок речовинної осі:

f(x) > min , x належить [a, b].

Максимізація цільової функції (f(x) > max) еквівалентна мінімізації протилежної величини ( -f(x) > min ), тому, не применшуючи спільності можна розглядати тільки задачі мінімізації.

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

Для рішення задачі мінімізації функції f(x) на відрізку [a, b] на практиці, як правило, застосовують наближені методи. Вони дозволяють знайти рішення цієї задачі з необхідною точністю в результаті визначення кінцевого числа значень функції f(x) і її похідних у деяких точках відрізка [a, b]. Методи, що використовують тільки значення функції і не потребують обчислення її похідних, називаються прямими методами мінімізації.

Більшим достоїнством прямих методів є те, що від цільової функції не потрібно диференціювання й, більш того, вона може бути не задана в аналітичному виді. Єдине, на чому засновані алгоритми прямих методів мінімізації, це можливість визначення значень f(x) у заданих точках.

Розглянемо найпоширеніші на практиці прямі методи пошуку точки мінімуму. Самою слабкою вимогою на функцію f(x), що дозволяє використати ці методи, є її унімодальність. Тому далі будемо вважати функцію f(x) унімодальною на відрізку [a, b].

Метод перебору.

Метод перебору або рівномірного пошуку є найпростішим із прямих методів мінімізації й полягає в наступному. Розіб'ємо відрізок [a,b] на n рівних частин точками ділення:

xi = , i = 0, ... n

Обчисливши значення F(x) у точках xi, шляхом порівняння знайдемо точку xm, де m - це число від 0 до n, таку, що

F(xm) = min F(xi) для всіх i від 0 до n.

Погрішність визначення точки мінімуму xm функції F(x) методом перебору не перевершує величини eps = .

Метод ділення навпіл.

Розглянемо функцію F, що потрібно мінімізувати на інтервалі [a1, b1]. Припустимо, що F строго квазівипукла. Очевидно, що найменше число обчислень значень функції, які необхідні для скорочення інтервалу невизначеності, дорівнює двом. Однієї зі стратегій є вибір цих двох крапок симетрично на відстані eps > 0 від середини інтервалу. Тут число eps настільки мало, щоб довжина нового інтервалу невизначеності eps+(b1-a1)/2 була досить близькою до теоретичного значення (b1-a1)/2, і в той же час таке, щоб значення функції в цих двох точках були помітні.

Алгоритм дихотомічного методу для мінімізації квазівипуклої фунції на інтервалі [a1,b1].

Початковий етап.

Вибрати константу розрізнення 2еps > 0 і припустиму кінцеву довжину інтервалу невизначеності l > 0. Нехай [a1,b1] - початковий інтервал невизначеності. Покласти k = 1 і перейти до основного етапу.

Основний етап.

Крок 1. Якщо bk-ak < l, то зупинитися; точка мінімуму належить інтервалу [ak,bk]. У противному випадку обчислити

і перейти до кроку 2.

Крок2. Якщо F(pk) < F(qk), покласти a[k+1]=ak і b[k+1]=qk. У противному випадку покласти a[k+1]=pk і b[k+1]=bk. Замінити k на k+1 і перейти до кроку 1.

Методи безумовної мінімізації функцій багатьох змінних.

Задача безумовної оптимізації складається в знаходженні мінімуму або максимуму функції під час відсутності яких-небудь обмежень. Незважаючи на те що більшість практичних задач оптимізації містить обмеження, вивчення методів безумовної оптимізації важливо з декількох точок зору. Багато алгоритмів рішення задачі з обмеженнями припускають відомість її до послідовності задач безумовної оптимізації. Інший клас методів заснований на пошуку підходящого напрямку й наступної мінімізації уздовж цього напрямку. Обґрунтування методів безумовної оптимізації може бути природно поширене на обґрунтування процедур рішення задач із обмеженнями.

Методи безумовної мінімізації функцій багатьох змінних містить у собі багатомірний пошук без використання похідних і пошук, що використає похідні.

Багатомірний пошук без використання похідних.

Розглянемо методи рішення мінімізації функції декількох змінних f, які опираються тільки на обчислення значень функції f(x), не використовують обчислення похідних, тобто прямі методи мінімізації. Важливо відзначити, що для застосування цих методів не потрібно не тільки диференціювання цільової функції, але навіть аналітичного завдання. Потрібно лише мати можливість обчислювати або вимірювати значення f у довільних точках. Такі ситуації часто зустрічаються в практично важливих задачах оптимізації. В основному всі описані методи полягають у наступному. При заданому векторі х визначається припустимий напрямок d. Потім, відправляючись із крапки х, функція f мінімізується уздовж напрямку d одним з методів одномірної мінімізації. Задача лінійного пошуку полягає в мінімізації f(x+lym·d) при умові, що lym належить L, де L задається в формі L = E1, L = {lym: lym ? 0} або L = {l: a ? lym ? b}. Будем вважати, що точка мінімума lym існує. Однак в реальних задачах це припущення може не виконуватися. Оптимальне значення цільової функції в задачі лінійного пошуку може бути не обмежене або оптимальне значення функції кінцеве, але не досягається не при якому lym.

Багатомірний пошук без використання похідних реалізується з використанням наступних методів: циклічного покоординатного спуску; Хука й Дживса; Розенброка; мінімізації по правильному симплексі; пошуку точки мінімуму по деформованому симплексу.

Метод циклічного покоординатного спуску.

У цьому методі як напрямки пошуку використовуються координатні вектори. Метод циклічного покоординатного спуску здійснює пошук уздовж напрямків d1, ..., dn, де dj - вектор, всі компоненти якого, за винятком j-ого, дорівнюють нулю. Таким чином, при пошуку по напрямку dj міняється тільки змінна xj, у той час як всі інші змінні залишаються зафіксованими.

Алгоритм циклічного покоординатного спуску.

Початковий етап.

Вибрати eps > 0, що буде використовуватися для зупинки алгоритму, і взяти в якості d1, ..., dn координатні напрямки. Вибрати початкову точку x1, покласти y1 = x1, k=j=1 і перейти до основного етапу.

Основний етап.

Крок 1. Покласти lymj рівним оптимальному рішенню задачі мінімізації f(yj+lym·dj) при умові, що lym належить E1. Покласти y[j+1]= yj+lymj·dj. Якщо j < n, то замінити j на j+1 і повернутися до кроку 1. Якщо j=n, то перейти до кроку 2.

Крок 2. Покласти x[k+1] = y[n+1]. Якщо || x[k+1] - xk || < eps, то зупинитися. У противному випадку покласти y1= x[k+1], j=1, замінити k на k+1 і перейти до кроку 1.

Метод Хука й Дживса.

Метод Хука й Дживса здійснює два типи пошуку - пошук, що досліджує, і пошук за зразком. Перші дві ітерації процедури показані на малюнку 3.3.

Мал. 3.3 Метод Хука й Дживса: 1-пошук за зразком; 2- пошук, що досліджує, уздовж координатних осей.

При заданому початковому векторі x1 пошук, що досліджує, по координатних напрямках приводить у точку x2 . Наступний пошук за зразком у напрямку x1- x2 приводить у точку y. Потім, досліджуючий пошук, що починається із точки y, дає точку x3. Наступний етап пошуку за зразком уздовж напрямку x3- x2 дає y*. Потім процес повторюється.

Алгоритм Хука й Дживса з використанням одномірної мінімізації.

Розглянемо варіант методу, що використовує одномірну мінімізацію уздовж координатних напрямків d1,..., dn і напрямків пошуку за зразком.

Початковий етап.

Вибрати число eps > 0 для зупинки алгоритму. Вибрати початкову крапку x1, покласти y1= x1, k=j=1 і перейти до основного етапу.

Основний етап.

Крок 1. Знайти lymj - оптимальне рішення задачі мінімізації f(yj+lym · dj) при умові що lym належить E1. Покласти y[j+1]= yj+lymj·dj. Якщо j < n, то замінити j на j+1 и повернутися до кроку 1. Якщо j = n, то покласти x[k+1] = y[n+1]. Якщо ||x[k+1] - xk|| < eps , то зупинитися; у противному випадку перейти до кроку 2.

Крок 2. Покласти d = x[k+1] - xk і знайти lym - оптимальне рішення задачі мінімізації f(x[k+1]+lym·d) при умові lym належить E1. Покласти y1= x[k+1]+lym·d, j=1, замінити k на k+1 и перейти до кроку 1.

Метод Розенброка.

Розглянемо варіант методу із застосуванням одномірної мінімізації. На кожній ітерації процедура здійснює ітеративний пошук уздовж n лінійно незалежних і ортогональних напрямків. Коли отримана нова точка наприкінці ітерації, будується нова множина ортогональних векторів. На малюнку 3.4 нові напрямки позначені через q1 і q2.



Мал. 3.4 Побудова нових напрямків пошуку в методі Розенброка.

Побудова напрямків пошуку.

Нехай d1,..., dn - лінійно незалежні вектори, по нормі рівні одиниці. Будемо вважати, що ці вектори взаємно ортогональні, тобто (di · dj) = 0 для i != j. Починаючи з поточної точки xk, цільова функція послідовно мінімізується вздовж кожного з напрямків, в результаті чого отримується точка x[k+1]. Слід зазначити, що x[k+1]- xk = Sum(lymj · dj), де lymj - довжина кроку по напрямку dj. Новий набір напрямків q1,..., qn будується за допомогою процедури Грамма-Шмідта наступним шляхом:

aj =

bj

qj = bj /|| bj ||.

Нові напрямки побудовані в такий спосіб є лінійно незалежними й ортогональними.

Алгоритм методу Розенброка з мінімізацією по напрямку.

Початковий етап.

Нехай eps > 0 - скаляр, використовуваний у критерії зупинки. Вибрати в якості d1,..., dn координатні напрямки, початкову точку x1, покласти y1= x1, k=j=1 і перейти до основного етапу.

Основний етап.

Крок 1. Знайти lymj - оптимальне рішення задачі мінімізації f(yj+lymj · dj) при умові lym належить E1 и покласти y[j+1]= yj+lymj · dj. Якщо j < n, то замінити j на j+1 и повернутися до кроку 1. В іншому випадку перейти до кроку 2.

Крок 2. Покласти x[k+1]= y[n+1]. Якщо ||x[k+1] - xk|| < eps, то зупинитися. У противному випадку покласти y1= x[k+1], замінити k на k+1 покласти j=1 і перейти до кроку 3.

Крок 3. Побудувати нову множину лінійно незалежних і взаємно ортогональних напрямків відповідно до процедури Грамма-Шмідта. Позначити нові напрямки d1,..., dn і повернутися до кроку 1.

Мінімізация по правильному симплексу.

Правильним симплексом у просторі En називається множина з n+1 рівновіддалених один від одного точок (вершин симплекса). Відрізок, що з'єднує дві вершини, називається ребром симплекса.

У просторі E2 правильним симплексом є сукупність вершин рівностороннього трикутника, а в E3 - правильні тетраедри. Якщо x0 - одна з вершин правильного симплекса в En, то координати інших n вершин x1,..., xn можна знайти, наприклад, по формулах:

xji = (1)

де d1 = a(sqrt(n+1) - 1) / n · sqrt(2), d2 = a(sqrt(n+1) + n - 1) / n · sqrt(2), a - довжина ребра.

Вершину x0 симплекса, побудованого по формулах (1), будемо називати базовою. В алгоритмі симплексного методу використовується наступна важлива властивість правильного симплекса. По відомому симплексі можна побудувати новий симплекс шляхом відбиття якої-небудь вершини, наприклад, xk симетрично щодо центра ваги xc інших вершин симплекса. Нова й стара вершини y і xk пов'язані співвідношенням:

де для всіх i!=k.

В результаті одержуємо новий симплекс із тим же ребром і вершинами y=2xс-xk, xi, i=0,...,n, i!=k. У такий спосіб відбувається переміщення симплекса в просторі. На малюнку 3.5 представлена ілюстрація цієї властивості симплекса для двовимірної області.

Мал. 3.5 Побудова нового симплекса в Е2 відбиттям точки х2.

Пошук точки мінімуму функції f(x) за допомогою правильних симплексів виробляється в такий спосіб. На кожній ітерації порівнюються значення функції у вершинах симплекса. Потім проводиться описана вище процедура відбиття для тієї вершини, у якій f(x) приймає найбільше значення. Якщо у відбитій вершині виходить менше значення функції, то переходять до нового симплекса. Якщо ж спроба відбиття не приводить до зменшення функції, то скорочують довжину ребра симплекса, наприклад, удвічі й будують новий симплекс із цим ребром. У якості базової вибирають ту вершину x0 старого симплекса, у якій функція принимет мінімальне значення. Пошук точки мінімуму f(x) закінчують, коли або ребро симплекса, або різниця між значеннями функції у вершинах симплекса стають досить малими.

Алгоритм мінімізації по правильному симплексу.

Початковий етап.

Вибрати параметр точності eps, базову точку x0, ребро a і побудувати початковий симплекс по формулах (1). Обчислити f(x0).

Основний етап.

Крок 1. Обчислити значення f(x) у вершинах симплекса x1,..., xn.

Крок 2. Упорядкувати вершини симплекса x0,..., xn так, щоб

f(x0) ? f(x1) ? ... ? f (x[n-1]) ? f(xn).

Крок 3. Перевірити умову (1/n)Sum[f(xi)-f(x0)]2 < eps2, i=[1,n].

Це одне з можливих умов зупинки. При його виконанні "дисперсія" значень f(x) у вершинах симплекса стає менше e2, що, як правило, відповідає або малому ребру a симплекса, або влученню точки мінімуму x* усередину симплекса, або тому й інший одночасно.

Якщо ця умова виконана, то обчислення припинити, думаючи x*= x0. У противному випадку перейти до кроку 4.

Крок 4. Знайти xс і виконати відбиття вершини xn : y = 2 · xс- xn. Якщо f(y) < f(xn), то покласти xn = y і перейти до кроку 2. Інакше - перейти до кроку 5.

Крок 5. Перейти до нового правильного симплекса із удвічі меншим ребром, вважаючи базовою вершиною x0. Інші n вершин симплеска знайти по формулі xi=( xi+ x0)/2, i=1,..., n. Перейти до кроку 1.

Пошук крапки мінімуму по деформованому симплексу.

Алгоритм мінімізації по правильному симплексі можна модифікувати, додавши до процедури відбиття при побудові нового симплекса процедури стиску й розтягання. А саме, положення нової вершини y замість вершини xn, що відповідає найбільшому значенню функції, знаходиться порівнянням і вибором найменшого серед значень цільової функції в точках:

z1 = xс - a(xc - xn), 0 < a < 1;

z2 = xc + a(xc - xn), 0 < a <1; (2)

z3 = xc + b(xc - xn), b приблизно дорівнює 1;

z4 = xc + g(xc - xn), g<1.

Геометрична ілюстрація цих процедур для двовимірного простору наведена на малюнку 3.6.

Мал. 3.6 Пробні точки z1, z2, z3, z4 для переходу до нового симплекса

Так як величина a належить інтервалу (0;1), то вибір точок z1 і z2 відповідає стиску симплекса; b приблизно дорівнює 1, тому вибір точки z3 відповідає відбиттю, а g >1 і вибір точки z4 приводить до розтягання симплекса.

Необхідно відзначити, що при деформаціях втрачається властивість правильності вихідного симплекса.

На практиці добре зарекомендував себе наступний набір параметрів a = 1/2, b = 1, g = 2.

Алгоритм методу пошуку точки мінімуму функції по деформованому симплексу.

Початковий етап.

Вибрати параметр точності eps, параметри a, b і g, базову точку x0, параметр a і побудувати початковий симплекс. Обчислити значення функції f(x0).

Основний етап.

Крок 1. Обчислити значення функції у вершинах симплекса x1,..., xn.

Крок 2. Упорядкувати вершини симплекса x0,..., xn так, щоб

f(x0) ? f(x1) ? ... ? f (x[n-1]) ? f(xn).

Крок 3. Перевірити умову (1/n)Sum[f(xi)-f(x0)]2 < eps2, i=[1,n].

Це одне з можливих умов зупинки. При його виконанні "дисперсія" значень f(x) у вершинах симплекса стає менше e2, що, як правило, відповідає або малому ребру a симплекса, або влученню точки мінімуму x* усередину симплекса, або тому й іншому одночасно.

Якщо ця умова виконана, то обчислення припинити, думаючи x*= x0. У противному випадку перейти до кроку 4.

Крок 4. Знайти xс і пробні точки zk , k=1,...,4 по формулах (2). Знайти f(z*) = minf(zk). Якщо f(z*) < f(xn), то покласти xn = z* і перейти до кроку 2. Інакше - перейти до кроку 5.

Крок 5. Зменшити симплекс, думаючи xi = (xi+ x0)/2, i=1,...,n перейти до кроку 1.

Багатомірний пошук, що використовує похідні.

Нехай функція f(x) диференційована в Еn . У цьому розділі розглядається ітераційна процедура мінімізації виду:

xk = x[k-1] + lym[k] · dk, k=1,... ,

де напрямок убування dk визначається тим або іншом способом з урахуванням інформації про частки похідних функції f(x), а величина кроку lym[k] >0 така, що

f(xk) < f(xk-1), k=1,2,....

Тому що функція передбачається диференційованою, то у якості критерію зупинки у випадку нескінченної ітераційної послідовності { xk }, як правило, вибирають умову ||grad(f(xk))|| < eps, хоча, зрозуміло, можуть бути використані й інші критерії.

Багатомірний пошук, що використовує похідні містить у собі метод найшвидшого спуску.

Метод найшвидшого спуску.

Метод найшвидшого спуску є одним з найбільш фундаментальних процедур мінімізації диференційованої функції декількох змінних. Вектор d називається напрямком спуска для функції f у точці x, якщо існує таке d > 0, що f(x+lym · d) < f(x) для всіх lym, що належать інтервалу (0, d).

У методі найшвидшого спуску здійснюється рух уздовж напрямку d, для якого ||d|| = 1 і яке мінімізує наведену вище межу. Якщо f диференційована в точці x і grad(f(x)) != 0, те -grad(f(x))/||grad(f(x))|| є напрямком найшвидшого спуску. У зв'язку з цим метод найшвидшого спуску іноді називають градієнтним методом.

Алгоритм методу найшвидшого спуску.

При заданій точці x алгоритм найшвидшого спуску полягає в реалізації лінійного пошуку уздовж напрямку -grad(f(x))/||grad(f(x))|| або, що те ж саме, уздовж напрямку -grad(f(x)).

Початковий етап. Нехай eps > 0 - константа зупинки. Вибрати початкову точку x1, покласти k =1 і перейти до основного етапу.

Основний етап. Якщо ||grad(f(x))|| < eps , то зупинитися; у противному випадку покласти dk = -grad(f(x)) і знайти lym[k] - оптимальне рішення задачі мінімізації f(xk + lym · dk) при lym ? 0. Покласти x[k+1]=xk+lym[k] · dk, замінити k на k+1 и повторити основний етап.

Застосування алгоритмів мінімізації функцій багатьох змінних.

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

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

Потужним інструментом теоретичного дослідження алгоритмів є теореми про збіжність методів. Однак, як правило, формулювання таких теорем абстрактні, при їхньому доказі використовується апарат сучасного функціонального аналізу. Крім того, найчастіше непросто встановити зв'язок отриманих математичних результатів із практикою обчислень. Справа в тому, що умови теорем важкоперевіряємі в конкретних задачах, сам факт збіжності мало що дає, а оцінки швидкості збіжності неточні й неефективні. При реалізації алгоритмів також виникає багато додаткових обставин, строгий облік яких неможливий (помилки округлення, наближене рішення різних допоміжних задач і т.д.) і які можуть сильно вплинути на хід процесу.

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

4. ПРОГРАМНА РЕАЛІЗАЦІЯ ТА ОПИС ФУНКЦІОНАЛЬНИХ МОЖЛИВОСТЕЙ АЛГОРИТМУ

4.1 Алгоритм розподілу

Алгоритм розподілу елементів попиту по випадково сформованому ресурсі складається з наступних блоків:

1. Формування множини, що містить елементи ресуру.

2. Формування множини, що містить елементи попиту.

3. Чи закінчився список попиту?

4. Виключення із загального ресурсу елементів, які неможливо використати при розподілі поточного елемента попиту.

5. Чи можна сформувати новий кластер?

6. Отримання повідомлення про невдалий розподіл поточного елемента попиту.

7. Формування кластера, що містить елементи вільного ресурсу по необхідних параметрах елемента поточного попиту. Для даної мети використаються заздалегідь сформовані функції.

8. Чи містить кластер необхідну кількість елементів?

9. Розподіл поточного елемента попиту по елементах кластера. При цьому елемент ресурсу в загальному масиві заміняється сполученням поточного елемента попиту й елемента ресурсу.

4.2 Введення даних. Способи вводу.

4.2.1 Формування списку ресурсу

Ресурс являє собою 4-мірний масив, що складається з 0 і 1, розподілених випадковим шляхом. Значення 0 вказує на вільний елемент ресурсу, значення 1 - зайнятий елемент.

Співвідношення зайнятих та вільних елементів ресурсу представлено наступною діаграмою (Мал. 4.1):

Масив ресурсу відображає зайнятість аудиторій на всі дні семестру, на кожній з пар. Текстовий файл dano.txt зберігає початкові значення елементів масиву ресурсу. Щоб використати дані файлу в робочому файлі, необхідно його імпортувати. Для цього використовуємо функцію пакета Mathematica - Import.

У загальному виді функція записується в такий спосіб:

Import [“file”, “format”] - де в якості “file” необхідно вказати повний шлях імпортованого файлу, а в якості “format” - формат імпортованого файлу.

Для визначення розмірності масиву М використовуємо вбудовану функцію пакета Mathematica - Dimensions. Параметром даної функції є розглянутий масив - М. Значення розмірності масиву М привласнимо змінній d.

Щоб кожному значенню масиву d відповідала окрема змінна, використовуємо цикл Do. Загальний вид циклу:

Do [expr, {i, imin, imax}] - у циклі з лічильником i, починаючи з imin і до imax з кроком рівним 1 виконується вираження expr.

Таким чином, кожна зі змінних (d1, d2, d3, d4) буде відповідати певному параметру: d1 - кількість тижнів у семестрі; d2 - кількість всіх аудиторій; d3 - кількість навчальних днів у тиждень; d4 - кількість пар у день. Надалі ці змінні можна буде використати для перебору елементів масиву ресурсу.

Для визначення кількості всіх зайнятих аудиторій використаємо функцію пакета Mathematica - Sum. У загальному виді функція виглядає:

Sum[f, {i, imin, imax}, {j, imin, jmax}, …] - визначення суми значень вираження f, перебираючи елементи i, j,..., починаючи з min до max із кроком 1.

Функція Sum підраховує суму всіх елементів масиву М. Так як масив М складається з 0 і 1 (0 - аудиторія вільна, 1 - аудиторія зайнята), то функція Sum визначить кількість зайнятих аудиторій.

Для визначення вільного ресурсу необхідно від загального ресурсу відняти зайнятий ресурс.

Загальний ресурс визначаємо перемноживши значення розмірності вихідної матриці М. % - вказує на результат попереднього вираження, тобто від загального ресурсу віднімаємо суму зайнятих аудиторій.

Щоб виразити в процентному співвідношенні вільний ресурс необхідно знайти відношення вільного ресурсу до загального й помножити на 100%:



Створимо новий масив мм, розмірністю вихідного масиву М. Масив мм складається з тих же значень, що й масив М.

У новому масиві мм замінимо ячейки рівні 0 на змінні A{i, j, k, z} з індексами, які відповідають координатам ячейки. Ячейки рівні 1 - очистимо.

Для реалізації даного завдання використаємо цикл For для перебору елементів масиву мм.

У пакеті Mathematica цикл For записується з наступними параметрами:

For [start, test, incr, body] - спочатку один раз обчислюється вираження start, потім по черзі обчислюються вираження в body і incr до тих пір, поки умова test не перестане давати логічне значення True.

Використовуючи вкладені цикли For, здійснюємо перебір всіх елементів масиву М. У тілі циклу застосовуємо оператор умови If. Загальний вид:

If [condition, t, f] - Якщо умова (condition) є істина, тоді виконується дія t, інакше - f.

За допомогою умови If порівнюємо кожне значення елемента масиву М з 1. Якщо умова істина, тоді елементу масиву мм с тими ж координатами привласнюємо порожнє значення - {}. Якщо ж умова - неправда, тоді елементу масиву мм привласнюємо змінну А с відповідними індексами (i, j, k, z) - які дорівнюють координатам поточнї ячейки.

Перебравши всі елементи масиву М и здійснивши всі задані заміни, у підсумку одержимо новий масив мм, у якому наочно видно вільні елементи ресурсу.



Створимо масив, що складається тільки зі змінних A{i, j, k, z}, тобто масив буде містити тільки елементи вільного ресурсу. Для цього в пакеті Mathematica можна скористатися функцією Flatten[ ]. В якості параметра вказується масив, що буде обробляти функція.

Новому масиву привласнимо ім'я fм. Запис: fм = Flatten[мм] формує масив, у якому функція Flatten [ ] виключає порожні значення - {} і залишає змінні A{i, j, k, z}

Сформуємо масив ffм, шляхом перетворення попереднього масиву, таким чином, щоб індекси {i, j, k, z} змінної А, перебували на одному рівні зі змінною. Тобто масив ffм повинен містити тільки змінні А і набір масивів з відповідними індексами змінної А. Для цієї мети в пакеті Mathematica скористаємося функцією Level[expr, levelspec]. Дана функція представляє список всіх підвиражень значення expr на рівнях levelspec.

У програмі як параметри функції Level використаємо ім'я попереднього масиву - fм, значення рівня задаємо - {2}.

Сформуємо загальний список ресурсу. Кожний з елементів масиву ресурсу являє собою підмножину параметрів - {i, j, k, z}. Кожне зі значень визначають: i - порядковий номер тижня; j - індекс аудиторії; k - порядковий номер дня тижня; z - порядковий номер пари в день.

Для створення подібного масиву в пакеті Mathematica можна використати функцію Cases [expr, pattern ]. У параметрах функції необхідно вказати ім'я масиву (expr) з якого будуть відбиратися елементи, що відповідають зазначеному зразку(pattern).

Зміннійresurs привласнимо масив, що утворився. Це й буде загальний список ресурсу, який можна буде використати для складання розкладу.

Для визначення довжини масиву ресурсу використаємо функцію Length[].



Для того щоб масив ресурсу зберігся в первісному вигляді, експортуємо його в окремий файл формату текст (Resurs.txt). Пакет Mathematica містить вбудовану функцію Export, що і реалізує дане завдання. Загальний вид:

Export [“file”, expr, “format”] - як параметри функції необхідно вказати ім'я створюваного файлу, вираження, яке потрібно експортувати у файл і формат файлу.

Щоб скористатися даними файлу Resurs.txt , необхідно його імпортувати в робочий файл. Для цього використовується функція Import. Як параметри функції Import необхідно вказати повний шлях до імпортованого файлу й формат файлу.

Використання функції Import дозволяє в будь-який момент часу переглянути загальний список ресурсу й порівняти його з поточними перетвореннями. Також це допомагає в процесі створення алгоритму не акцентувати увагу на всіх вищеописаних функціях при створенні списку ресурсу.

4.2.2 Формування списку попиту

Список попиту являє собою одномірний масив, що складається з підмножин - {i, j, k, z, r}. Кожне значення підмножини відповідає певному параметру: i - вид аудиторії необхідний для проведення заняття , j - індекс дисципліни, k - індекс викладача, z - необхідна кількість пар для проведення заняття, r - індекс групи.

Співвідношення занять за їх видами виражено діаграмою (Мал 4.2):

Мал. 4.2 Співвідношення занять

Так як протягом семестру попит є відносно постійним, то для зручності роботи з масивом, експортуємо його значення в окремий файл, формату текст. Привласнимо йому ім'я NewSpros.txt.

Дане завдання реалізуємо з використанням функції Export. Як параметри функції вказуємо ім'я створюваного файлу, дані які потрібно експортувати в окремий файл і формат цього файлу.

Щоб скористатися даними файлу NewSpros.txt, необхідно його імпортувати в робочий файл. У пакеті Mathematica використаємо функцію Import. Як параметри функції вказуємо повний шлях до імпортованого файлу й формат файлу.

Використання функції Import дозволяє в будь-який момент часу переглянути загальний список попиту, виконати необхідні дії над ним, редагувати.

4.3 Генерація функцій користувача

4.3.1 Розрахункові функції

Створення кластерів.

Формування розкладу вимагає перебору всіх елементів попиту й розподіл їх по існуючому ресурсі, дотримуючись всіх обмежень і критерій. Варіантів таких розподілів величезна кількість. Вручну перебрати всі практично неможливо.

Якщо ж перебирати всі можливі варіанти з використання ЕОМ, по-перше, цей процес забере якийсь час, а по-друге, не раціонально перебирати таку велику кількість елементів.

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

Створимо функцію в результаті роботи, якої формується кластер, що містить вільні елементи ресурсу. Елементи ресурсу відбираються по заданих днях тижня, з деякою періодичністю.

У пакеті Mathematica створимо функцію з параметрами. Ім'я функції привласнимо aT1. Як параметр вкажемо порядковий номер дня до якого необхідно формувати кластер і з якою періодичністю перебирати дні.

Використаємо функцію пакета Mathematica - Block. У загальному виді функція має вигляд:

Block [{x, y,...}, expr], де {x, y,...} - локальні змінні, еxpr - тіло функції.

У якості локальної змінної використаємо змінну r - для перебору днів тижня.

У тілі функції використаємо вкладені цикли For. Функція починає перебір елементів ресурсу починаючи з понеділка й до дня (D_), зазначеного в параметрах функції aT1. У вкладених циклах перебираються тижні, обмежуючи число тижнів змінною d1, описаною вище. Потім здійснюється перебір по індексах аудиторій. Кількість аудиторій обмежена змінною d2, описаною вище. Далі перебір по парах у день , обмежуючи їхню кількість змінною d4. В останньому вкладеному циклі здійснюється перебір по днях тижня. Але на відміну від попередніх циклів, де крок дорівнював 1, крок перебору днів тижня (р_) задається з використанням параметра функції aT1, тобто вказується з якою періодичністю варто перебрати елементи.

Сформувавши в такий спосіб деякі значення {i, j, k, z} і скориставшись функцією Cases можна створити список елементів, обраних із загального масиву ресурсу по заданих параметрах.

Функція Join у пакеті Mathematica дозволяє об'єднати в один масив всі списки, що формуються на етапах виконання функції aT1.

У загальному виді функція Join має вигляд:

Join [list1, list2, ...] - де list1, list2 - списки, які необхідно об'єднати в один масив.

В результаті виконання функції aT1 формується кластер, що містить елементи вільного ресурсу із заданою періодичністю в днях, починаючи з понеділка кожного тижня й до зазначеного дня.

Якщо необхідно відібрати елементи з періодичністю 5 днів, починаючи з понеділка й до середи, тоді функція aT1 запишеться в такий спосіб:

Створимо функцію, результатом роботи якої, є формування кластера, що містить вільні елементи ресурсу. Елементи кластера відповідають наступним параметрам: дотримується періодичність (р_); елементи відбираються, починаючи з понеділка кожного тижня й до зазначеного дня (D_); у списку тільки задані індекс аудиторії (а_) і порядковий номер пари в день на якій буде проводитися заняття (para_).

У пакеті Mathematica створимо функцію з ім'ям аТ2, для виклику якої необхідно вказати всі перераховані вище параметри.

Опис функції аТ2 здійснюємо з використанням вбудованої функції пакета Mathematica - Block. У якості локальної змінної використаємо змінну r - для перебору днів тижня.

У тілі функції описуємо вкладені цикли For. Функція починає перебір елементів списку ресурсу, починаючи з понеділка й до зазначеного в параметрах функції дня тижня (D_). Для кожного дня тижня формується окремий масив з ім'ям APrbeg. Індекс rbeg відповідає порядковому номеру дня тижня. Викликавши функцію аТ2 і запросивши APrbeg, де rbeg задати конкретне значення дня тижня, можна одержати кластер вільного ресурсу із заданими параметрами для певного дня тижня.

Далі здійснюється перебір по тижнях, обмежуючи їхнє число змінною d1, описаної вище. Потім провадиться перебір по днях тижня, обмеживши число днів змінною d3. В останньому вкладеному циклі крок, з яким перебираються елементи, задається з використанням параметра функції аТ2 (р_).

Так як в параметрах функції аТ2 можна вказати необхідний індекс аудиторії (а_) і порядковий номер пари для проведення заняття (para_), то ці ж значення використаються при створенні зразка вибірки в параметрах функції Cases - {i, a, r, para}.

Функція Join дозволяє об'єднати в один масив всі списки, що формуються на етапах виконання тіла функції аТ2. Змінна allT зберігає загальний список обраних елементів.

Таким чином, формується кластер, що містить елементи ресурсу із заданими параметрами періодичності, необхідного індексу аудиторії, порядкового номера пари в день і дня до якого здійснюється вибірка.

Якщо необхідно відібрати елементи з періодичністю 5 днів, починаючи з понеділка й до п'ятниці, по індексу аудиторії 1 для першої пари, тоді функція аТ2 запишеться в такий спосіб:

Створимо функцію, результатом роботи якої є формування кластера, що містить значення елементів вільного ресурсу із заданою періодичністю, параметрами аудиторії й дня тижня до якого здійснюється вибірка елементів.

У пакеті Mathematica створимо функцію з ім'ям аТ3, для виклику якої необхідно вказати наступні параметри: періодичність з якою відбираються дні (р_), порядковий номер дня тижня для якого провадиться вибірка (D_) і індекс аудиторії, у якій необхідно проводити заняття (а_).

Використаємо функцію пакета Mathematica - Block. У якості локальної змінної використаємо змінну r - для перебору днів тижня.

У тілі функції опишемо вкладені цикли For. Функція здійснює перебір елементів ресурсу, починаючи з понеділка й до дня (D_), зазначеного в параметрах функції аТ3. Потім провадиться перебір по тижнях, обмежуючи їхнє число змінною d1. Далі реалізується перебір по парах у день, обмеживши їхню кількість змінною d4. В останньому вкладеному циклі здійснюється перебір по днях тижня. При цьому крок, з яким перебираються елементи в циклі, задається з використанням параметра функції (р_).

Вказавши в параметрах функції аТ3 індекс необхідної аудиторії, можна задати зразок вибірки в параметрах функції Cases - {i, a, r, z}.

Використовуючи функцію Join поєднуємо всі підмножини, що формуються на етапах виконання тіла функції аТ3.

При формуванні підмножини елементів для кожного дня тижня (понеділка, вівторка й т.д.) використаємо змінну Arbeg. Індекс rbeg відповідає порядковому номеру дня тижня. Викликавши функцію аТ3 і запросивши Arbeg, де rbeg конкретне значення дня тижня, можна одержати кластер вільного ресурсу із заданими параметрами для певного дня тижня. Але, крім цього, у результаті роботи функції аТ3 формується загальний кластер, що містить список обраних елементів вільного ресурсу з певними параметрами для всіх необхідних днів тижня.



Якщо необхідно відібрати елементи з періодичністю 5 днів, починаючи з понеділка й до середи, по індексу аудиторії 2, тоді функція аТ3 запишеться в такий спосіб:

Створимо функцію, в результаті роботи якої формується кластер, що містить елементи вільного ресурсу з наступними параметрами: періодичність днів, вказівка дня тижня до якого здійснюється вибірка й необхідна кількість пар в тиждень для проведення занять.

У пакеті Mathematica створимо функцію з ім'ям arasp4, для виклику якої необхідно задавати параметри: періодичність, з якої будуть перебирати дні тижня (р_); порядковий номер дня тижня, до якого буде провадитися вибірка елементів (D_) і необхідна кількість пар для проведення заняття на тиждень (k_).

Для реалізації даного завдання в пакеті Mathematica використаємо функцію Block. У якості локальної змінної використаємо змінну r - для перебору днів тижня.

У тілі функції використаємо вкладені цикли For. Перший цикл здійснює перебір елементів ресурсу, починаючи з понеділка й до дня (D_), зазначеного в параметрах функції arasp4. Для кожного дня тижня формується окрема підмножина rasprbeg. Індекс відповідає порядковому номеру дня тижня. Викликавши функцію arasp4 і запросивши rasprbeg, де rbeg привласнити конкретне значення дня тижня, можна одержати кластер вільного ресурсу із заданими параметрами для окремого дня тижня.

У другому циклі перебираються тижні семестру, починаючи з першої й до останньої, значення якої зберігається в змінній d1. В останньому вкладеному циклі здійснюється перебір по днях тижня, де крок перебору елементів задається з використанням параметра функції (р_).

Таким чином, формуються деякі значення {i, _, r, _}, де «_» відповідає будь-якому значенню, що знаходиться на цьому місці. {i, _, r, _} можна використати як зразок у параметрах функції Cases.

Пакет Mathematica дозволяє використати функцію Cases з додатковими параметрами, у яких можна вказати кількість елементів вибірки. У функції це й буде змінна (k_), що задається як параметри функції arasp4.

Функція Join поєднує підмножини, що формуються на етапах виконання тіла функції arasp4.

В результаті, задаючи необхідні параметри при виконанні функції arasp4, формується кластер, яким можна маніпулювати в процесі складання розкладу.



Якщо необхідно відібрати елементи з періодичністю 5 днів, починаючи з понеділка й до п'ятниці, у кількості 2 пар у тиждень, тоді функція arasp4 запишеться в такий спосіб:

Створимо функцію, у результаті роботи якої, формується кластер, що містить елементи вільного ресурсу з параметрами: необхідного порядкового номера дня тижня й кількості пар для проведення занятть на тиждень.

У пакеті Mathematica створимо функцію з ім'ям Klaster1 для виклику якої необхідно задавати наступне: день тижня (den_) і необхідну кількість пар на тиждень (kvo_).

Для реалізації даного завдання в пакеті Mathematica скористаємося функцією Block. У якості локальної змінної використаємо змінну r - для перебору днів тижня.

У тілі функції використаємо вкладені цикли For. Перший цикл здійснює перебір елементів ресурс по тижнях, обмежуючи кількість тижнів змінною d1, описаної вище. У другому циклі проводиться перебір по днях тижня, обмежуючи їхнє число змінною d3. При цьому крок перебору елементів задається не 1, як у попередньому циклі, а зі збільшенням на 5. Такий крок дозволяє здійснювати вибірку з необхідною періодичністю. У циклі перебір починаємо з дня, зазначеного в параметрах функції Klaster1.

За допомогою функції Cases реалізуємо вибірку по заданому зразку. В якості зразка сформуємо наступне вираження {i, _, r, _} - де i, r - задані параметри (i - порядковий номер тижня, r - порядковий день тижня). Функцію Cases використаємо з додатковими параметрами, у яких можна вказати кількість елементів, що відбирають, по заданому зразку.

За допомогою функції Join поєднуємо підмножини, що формуються на етапах виконання функції Klaster1.

У результаті виконання функції, задаючи необхідні параметри, формується кластер, що містить значення вільного ресурсу, що задовольняють задані умови. Сформований у такий спосіб кластер можна використати при складанні розкладу.

Якщо необхідно відібрати елементи ресурсу для вівторка, у кількості 2 пар у тиждень, тоді функція Klaster1 запишеться в такий спосіб:



Створимо функцію, в результаті роботи якої здійснюється розподіл заданого попиту по заздалегідь сформованому ресурсу. При цьому є необхідність вказати порядковий номер дня тижня, з якого починається розподіл.

В пакеті Mathematica для рішення поставленого завдання створимо функцію з ім'ям Rasp. Для виклику функції необхідно задати в якості параметру порядковий номер дня тижня, з якого починається розподіл попиту по ресурсу (dned_).

Функцію Rasp опишемо за допомогою функції пакета Mathematica - Block. Локальні змінні, які буде використовувати функція не передбачені, тому на їхньому місці вкажемо порожню множину - { }.

У тілі функції використаємо вкладені цикли For. Перший цикл здійснює перебір по елементах масиву попиту, починаючи з першого й до останнього. Останній елемент списку попиту визначається за допомогою функції Length. Функція повертає довжину списку, ім'я якого вказанно в параметрах функції.

Другий цикл здійснює перебір по днях тижня, починаючи з дня, зазначеного в параметрах функції Rasp. Тіло циклу складається з наступних операторів: при кожному кроці формується порожній кластер { }. Потім за допомогою оператора If порівнюємо кількість пар поточного елемента попиту з кількістю тижнів у семестрі. Якщо кількість пар обраної дисципліни менше кількості тижнів у семестрі, тоді формується кластер Kl з використанням функції Klaster1, описаної вище. При цьому в параметрах функції Klaster1 необхідно вказати кількість обраних елементів ресурсу рівне 1. Якщо ж умова не виконується тоді формується кластер Kl з використанням функції Klaster1, але при цьому кількість обраних елементів ресурсу рівне 2.

Далі, використовуючи оператор If, здійснюємо перевірку, порівнюючи кількість пар обраної дисципліни з довжиною кластера, що сформувався, Kl (Довжина визначається за допомогою функції Length). Якщо умова задовольняється, тоді виконується цикл за допомогою функції For. У циклі перебираються заняття обраної дисципліни, починаючи з першого й до останнього, вираженим четвертим параметром у значенні елемента попиту. У тілі циклу виконуємо наступні дії: змінній f привласнюємо значення позиції в якій перебуває зазначений елемент. Для визначення позиції елемента в списку в пакеті Mathematica використаємо функцію Position. Загальний вид функції: