Главная | Обратная связь

Застосування блокового програмування у системному аналізі

Блокове програмування –розділ лінійного програмування, який вивчає методи зведення розв’язування задач лінійного програмування великого обсягу до розв’язування послідовності задач меншої розмірності.Основу блокового програмування становить метод декомпозиції. Американські математики Дж. Данциг і Ф. Вулф 1960 р. вперше спробували формалізувати розв’язок математичних моделей великої розмірності, розробивши так званий принцип розкладу для задач лінійного програмування. На цьому принципі базується запропонований ними метод блокового програмування. Суть цього методу зводиться до наступного. Розглядаючи структуру деяких реальних економічних задач, можна зауважити, що вони складаються з декількох часткових задач, пов’язаних певними загальними обмеженнями. Прикладом такого випадку є ситуація розвитку виробництва декількох галузей на одній території. Ці галузі можуть не залежати одна від одної, і їхній розвиток лімітований різними умовами, проте територія у них одна, а це означає, що трудові, енергетичні, природні ресурси, транспортна мережа у них спільні. Спільні у них і екологічні проблеми. Аналогічні ситуації можуть траплятися і з однією галуззю, коли виробництво її продукції мало пов’язано між собою, однак існує певне число спільних обмежень, які накладаються на розвиток галузі загалом. У такому випадку матриця умов задачі оптимального розвитку регіону чи галузі набуває спеціальної, так званої блоково-діагональної структури у вигляді:

Де Ω - – число видів продукції, виробництво яких слабо пов’язане між собою; A^(w) = ||a_ij^(w)|| - матриця коефіцієнтів затрат-випуску продукції групи wрозмірності n_xm_w n - число обмежень у виробництві продукції групи w , які впливають і на інші групи продукції, виробництво яких ми оптимізуємо у регіоні загалом. Таку структуру матриці коефіцієнтів затрат-випуску задачі оптимізації розвитку виробництва продукції даного регіону у загальному вигляді можна записати так:

Де Х = (Х⁽¹⁾_, Х⁽²⁾ , …, Х^(w)_,…., X^(Ω)) – розв’язок задачі (7.34) - (7.37);

B^(w) _- обмеження, властиві тільки групі продуктів w , представлених вектором - стовпчиком розмірності n_w; B^(w) B⁽⁰⁾ – обмеження спільні для всіх видів продукції, предствалених вектором, стовпчиком розмірності n. Основне положення, на якому ґрунтується метод блокового програмування, полягає у наступному: виходячи з того, що обмеження кожного блоку утворюють випуклі множини, будь-який розв’язок окремого блоку можна представити у вигляді лінійної комбінації його базисних розв’язків:

X^(w) = . Виходячи з цього, задача (7.34)-(7.37) розпадається на координуючу задачу:

7.39

l=1,2,…..L^(w); w = 1,2,….Ω; 7.42

Де 7.43 7.44

І підзадачі:

X^(w) ≥0, 7.47

Де U = (U₁, U₂ , …., U_j,…….,U_n) - вектор двоїстих оцінок умов (7.40).

Реалізуючи метод блокового програмування, спочатку розв’язують координуючу задачу (7.39)-(7.42), визначають двоїсті оцінки, які відповідають спільним обмеженням (7.40). З їхньою допомогою будують цільові функції окремо для кожної з підзадач. Оптимальні значення цих цільових функцій, отриманих у результаті розв’язування підзадач, використовують з метою перевірки базисного розв’язку координуючої задачі на оптимальність та вибору вектора, який потрібно ввести у базис, для якої даний базисний розв’язок виявиться неоптимальним. З метою перевірки базисного розв’язку координуючої задачі на оптимальність використовують умову:

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

54.Застосування дискретного програмування у системному аналізі

Дискретне програмування є розділом математичного програмування, що вивчає задачі, в яких на значення частини чи всіх змінних величин накладено вимогу дискретності.

У термінах дискретного програмування формулюють різноманітні економічні задачі: планування і управління, проектування та розміщення; задачі розміщення, комівояжера

та про призначення; задачі теорії розкладів, чимало інших економічних , військових задач.

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

Задачі з неоднорідною розривною цільовою функцією:

∑ⁿ_j=1C_j(x_j)→min

∑ⁿ_j=1a_ijx_j≥A_i, i=1,2,…m

x_j≥0 j=1,2,…,n

C_j(x_j)=

Такі задачі ще називають задачами з постійною складовою.

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

∑^m_i=1∑ⁿ_j=1 (C_ijx_ij+d_ijy_ij),

де y_ij=

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

В m (i=1, 2, …, m) можливих точках розміщення виробництва потрібно розмістити виробництво продукції. Щодо кожної з цих точок існує набір можливих варіантів проектів підприємств. До цих варіантів належать не тільки проекти нових підприємств, але

й варіанти реконструкції діючих підприємств, їхня ліквідація тощо. Загальна їхня кількість дорівнює H (h=1, 2, …, H). Відомо n (j=1, 2, …, n) споживачів продукції, потреба кожного з них становить Bj. Вартість реалізації проекту (враховуючи термін окупності) разом із затратами на випуск продукції дорівнює Aih.

Математична модель цієї задачі має вигляд:

∑^m_i=1∑^H_h=1A_ihx_ih+∑^m_i=1∑ⁿ_j=1t_ijy_ij→min

∑ⁿ_j=1y_ij=∑^H_h=1A_ihx_ih, i=1,2,..m

∑ⁿ_j=1y_ij=B_j, j=1,2,..n

∑^H_h=1x_ih=1, i=1,2,..m

де xih – цілочислова змінна, яка вказує на прийняття h-го проекту в і-ій точці можливого розміщення виробництва; yij – транспортні зв’язки і-го підприємства (виробника продукції) і j-го споживача цієї продукції; tij – затрати на перевезення одиниці продукції від і-го виробника до j-го споживача. Умови (7.52) і (7.53) забезпечують прийняття в кожній точці розміщення виробництва лише одного з можливих проектів підприємств.

Найпоширенішими методами розв’язування таких задач є:метод відсікання, комбінаторні методи, наближені методи.

Виникнення дискретного програмування пов’язують з опублікуванням американськими вченими Фулкерсоном-Джонсоном і Данцігом ідеї методу відсікання, проте розвиток методів розв’язування задач дискретного програмування почався після створення Гоморі першого алгоритму відсікання.