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

Інтерфейс повинен бути простим  та зрозумілим користувачу. Необхідно  створити довідкову систему, яка  б надавала інформацію за кардою формою.

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

Мінімальні системні потреби:

- CPU Pentium 450Mhz;

- 96Mb оперативної пам'яті;

- 64Mb відеокарта;

- 100Mb вільного місця на жорсткому диску;

Рекомендовані системні потреби:

- CPU Pentium 600Mhz;

- 128Mb оперативної пам'яті;

- 96Mb відеокарта;

- 200Mb вільного місця на жорсткому диску.

 

2. Теоретичні основи метода
1. Загальні положення

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

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

Ідея методу містить три  суттєвих моменти. По-перше, вказується спосіб обчислення опорного плану. По-друге, з’ясовується ознака, яка дозволяє з’ясувати, чи є обраний опорний  план оптимальним. По-третє, приводиться  спосіб, який дозволить за вибраним опорним планом збудувати інший  опорний план, більш близький  до оптимального. Доводиться, що таким  шляхом можна через кінцеве число  кроків отримати оптимальне план-рішення  задач лінійного програмування. Таким чином, метод полягає у  послідовному поліпшенні плану.

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

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

Запишемо задачу лінійного програмування у канонічній формі. Необхідно обчислити максимум лінійної форми

за умов

Тут A=(A1,A2,…,An) – матриця умов, Aj та - відповідно вектори умов та вектор обмежень даної задачі, С = (с₁,с₂,...,с_п) – заданий вектор коефіцієнтів лінійної функції. Будемо вважати, що ранг матриці А дорівнює m. Надамо визначення опорного плану та його базису. 
План =(x₁, ..., x_n) задачі лінійного програмування, яка записана у канонічній формі, називається опорним, якщо система векторів умов Aj, відповідно до його додатних компонент (xj > 0), лінійно незалежна.

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

Компоненти опорного плану  відповідають векторам його базису, будемо називати базисними, а інші її складові – позабазісними.

Припустимо, що нам відомий  певний опорний план з базисом

F_s =(A_sl,A_S2,...,A_Sj,...,A_Sm). Подальше буде зручно характеризувати вектор базіка, окрім його номера Si, позицією i, яку він займає в розглядаємому базисі. Зафіксуємо довільний вектор умов Aj, та випишемо його розкладення за векторами базису A_Sl,A_S2,...,A_Si,...,A_Sm

Тут x_ij – це складова розкладення векторів Aj за векторами базису при векторі A_si, що розташований в i-й позиції базісу.

Введемо множину індексів I_x вектора базису опорного плану Х (I_x – множина номерів базисних змінних). Очевидно,

 

(поза базисні змінні  дорівнюють нулю).

Розкладання вектору обмежень за векторами базису можна також записати у вигляді:

X_i0=X_si – базисна змінна, яка відповідає вектору A_s розташованому в i-й позиції базису. Позначивши вектор обмежень через А₀ отримаємо загальну формулу

яка визначає складові розкладання  усіх векторів умов та вектора обмежень за векторами базису.

Складемо набори параметрів Z_j та ∆_j  j= за наступними формулами:

 

Параметри Z_j та ∆_j  визначаються опорним планом , який відповідає базису

F_s =(A_sl,A_S2,...,A_Sj,...,A_Sm). Щоб підкреслити це доречно було б позначити ці параметри відповідно через Z_j^(x) та ∆_j^(x). Однак, не бажаючи ускладнювати записи будемо, де це можливо опускати індекс X при  Z_j та ∆_j.

У метод послідовного поліпшення плану параметри ∆_j грають дуже важливу роль. Знаки параметрів дозволяють визначити чи є вибраний опорний план оптимальним.

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

для усіх

3. Метод послідовного поліпшення плану(1 алгоритм)

При застосуванні даного методу задачу ЛП необхідно представити у канонічній формі запису:

 

де =(х_1,…,х₂) – план задачі, =(b₁,…,b₂) – вектор обмежень, А=(₁,…,_n) – матриця умов, = (с₁,с₂,...,с_п) – вектор коефіцієнтів лінійної форми L. Окрім того необхідно вказати опорний план ₀=(х₁⁰,…,х_n⁰)задачі з базисом F_s ={A_sl,A_S2,...,A_Sm}. Послідовне просування за базисами опорних планів задачі до отримання оптимального базису – це і є ідея методу послідовного поліпшення плану. 

Перший алгоритм починається  з заповнення таблиці 1.1 для вихідного  базису F_s.

У перший стовпець таблиці  заносять номера позицій базису, у  другий стовпець – базисні компоненти C_Si вектора , i=.

Таблиця 1.1 – Початкова  таблиця симплекс метода.

 

Стовпець F_s містить інформацію про номери S_i  векторів умов  A_Si , які належать F_s. Стовпчики A₀, A₁,…,A_n заповняють елементами матриці Х, яка визначається по формулі:

де  - розширена матриця умов, x_i0 – базисні компоненти опорного плану ₀, х_ij (i=, j=)- коефіцієнти розкладення векторів умов _j за базисом F_s. Остання m+1 строчка заповнюється на основі інформації попередніх строчок

 Параметри  X_m+10=Z₀=L(₀) визначає значення функції цілі (,_o) на опорному плані _o. Рух до оптимальної вершини (перехід від вихідної таблиці до наступної) починається з встановлення наявності ситуації 1, для якої виконується умова:

Якщо серед ∆j нема негативних чисел, то опорний план, що було досліджено є оптимальним та процес розв’язання задачі припиняється. Якщо серед ∆j є від’ємні числа, то встановлюється ситуація 2 

для кожного від’ємного параметру ∆j. Якщо існує ∆j<0, Ω_j=Ø, то задачу не можна розв’язати через необмеженість лінійної форми зверху на множені планів D_M.

Якщо ситуація 2 не має  місця бути, тоді переходимо до ситуації 3, при якій можна перейти у  нову вершину D_M , яка більш близька до оптимальної. Цей перехід починається з визначення k – номеру направляючого стовпчика таблиці, який задає номер вектора умов, що повинен увійти до базису. При визначення k можна реалізувати два методи.

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

Приблизний метод. У якості направляючого стовпчика обирають той, на якому досягається найменше від’ємне значення ∆k.

Для знаходження r – номера направляючої строчки, який визначає номер S_r вектора умов _Sr , виводимо з базису F_s пре переході у нову вершину, обчислюють Θ₀

 та відшукують позиції базису, на яких досягається Θ₀. Якщо Θ₀ досягається на тільки на одному рядку таблиці, то він є направляючим рядком. Якщо Θ₀ досягається на кількох рядках, то у якості направляючого рядка обирають той, якому у стовпчику F_s відповідає вектор умов з найменшим порядковим номером. Після знаходження номерів k та r формують базис F’_S нового опорного плану ’₀ заміною в F_s вектора умов _Sr на _k, та формують новий стовпчик _S заміною C_Sr на С_k . Інші елементи стовпців  F_s та C_s таблиці лишаються колишніми.

Елементи нової матриці, яка відповідає новому опорному плану  ’₀ з базисом F’_S перераховуються по формулам:

де i=1,2,3,…, m+1, та j=0,1,2,…, n.

Знову отриманий опорний  план  ’₀ беруть у якості початкової вершини, якій відповідає симплекс таблиця з елементами x’_ij.

 

4. Загальні положення М-методу

Для розв’язання задачі ЛП М-методом необхідно виконати наступні кроки:

   а) записати початкову задачу у канонічному вигляді;

   б) забезпечити невід’ємність вектора обмежень шляхом множення лівої та     правої частин і-ї умови задачі, для якої b_i<0, на мінус одиницю;

   в) побудувати  допоміжну задачу (М-задачу)

де I_m – одинична матриця розміром m×n,  _m =(x_n+1,…, x_n+m) – невід’ємний вектор штучних змінних x_n+i, i=, М-додатне число, яке перевищую за величиною будь-яке інше число порівняне з ним.

   г) розв’язати задачу методом послідовного поліпшення плану (1, 2 алгоритм), взявши у якості вихідного одиничний базис F_s^*={_n+1,…,_n+m} опорного плану ₀ =(0,). При розв’язанні задачі необхідно мати на увазі, що величина М не фіксована та ∆_j є функціями параметра М. У зв’язку з цим необхідно:

    1. Вектор коефіцієнтів лінійної форми представити у вигляді лінійної     залежності від М.

де 

    2.При обчисленні та аналізі використовувати їх лінійну незалежність

   3.Знаки параметрів ∆_j визначають на основі знаків параметрів α_j  β_j залежності

Якщо у процесі розв’язання  задачі виникла ситуація 2, то задачу не можна розв’язати через необмеженості L зверху. У протилежному випадку знаходять оптимальний план ^** та оптимальний базис F_s^** задачі.

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

Випадок 1. Усі x_n+i^**   = 0, i=, F_S⁰∩F_S^**=Ø. У цьому випадку ^**=(x₁^**,…,x_n^**) є рішенням задачі з оптимальним базисом F_s^*=F_s^**. Значення задачі буде β₀=(,^*).

Випадок 2. Усі x_n+i^**   = 0, F_S⁰∩F_S^**≠Ø. У цьому випадку ^* є вироджений опорний план задачі з кінцевим числом оптимальних базисів F. У якості F_s^* беруть будь-який з них, якій задовольняє умові F_S⁰∩F_S^**=Ø.

Випадок  3. Серед x_n+i^** є строго додатні числа. У цьому випадку задачу не можна розв’язати через несумісність умов.

5. Перший алгоритм М-методу

При вивченні першого алгоритму  М-методу слід мати на увазі, що він  являє собою перший алгоритм метода послідовного полібшення плану, модифікований  з урахуванням особливостей М-задачі.  Для розв’язання задачі першим алгоритмом М-методу необхідно виконати наступні етапи:

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

   б) побудувати М-задачу  з матрицею умов (A, I_m), вектором обмежень , вектором коефіцієнтів лінійної форми ,  які мають n+m компонент;

   в) заповнити   таблицю М-задачі для одиничного базису F_S={A_n+1,…,A_n+m};

Таблиця 1.2 – Вихідна тоблиця  М-метода.

При заповненні таблиці слід мати на увазі, що матриця Х  коефіцієнтів розкладань співпадає з матрицею (b,A,I_m), _s(M)=M_s+_s ,∆_j визначається у відповідності з α₀=_s, β₀=_s.

   г) перевірити наявність ситуації 1, для якої ∆М ≥ 0, j=. Якщо ситуація 1 має місце, то оптимальний план задачі лінійного програмування знайден, інакше переходять до етапу «д»;

   д) перевірити наявність  ситуації 2, для якої існує ∆_j(M) < 0 та Ω_j = Ø. Якщо ситуація 2 має місце, то процес розв’язання М-задачі припиняється та робиться висновок про те, що вихідна інформація не може бути розв’язана через необмеженість L зверху. У протилежному випадку переходять до пункту «е».

   е) застосовуючи  точний чи приблизний метод  знаходять k – номер направляючого стовпчика;