66315 (685059), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

При цьому на параметри системи накладаються лінійні обмеження:

Р₁₁Х₁ + Р₁₂Х₂ + … + Р_1іХ_і + … + Р_1пХ_п = В₁;

Р₂₁Х₁ + Р₂₂Х₂ + … + Р_2іХ_і + … + Р_2пХ_п = В₂;

Р_j1Х₁ + Р_j2Х₂ + … + Р_jіХ_і + … + Р_jпХ_п = В_j;

Р_t1Х₁ + Р_t2Х₂ + … + Р_tіХ_і + … + Р_tпХ_п = В_t;

Х₁ ≥ 0,Х₂ ≥ 0,Х_і ≥ 0,…,Х_п ≥ 0, (1.2)

де: В_j – обмеження, переробки молока, що накладаються умовами, на проектованому підприємстві (наприклад, ресурси молока, чисельність тих, що працюють, допустимі витрати пари, холоди, електроенергії і тому подібне);

Р_jі – коефіцієнт впливу параметра системи на величину обмеження.

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

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

А’’ = -С₁Х₁ + -С₂Х₂ + … -С_іХ_і + … -С_пХ_п (1.3)

Якщо в завданні обмеження дані як нерівності

Р_j1Х₁ + Р_j2Х₂ + … + Р_jіХ_і + … + Р_jпХ_п ≥ В_j, (1.4)

або

Р_j1Х₁ + Р_j2Х₂ + … + Р_jіХ_і + … + Р_jпХ_п ≤ В_j, (1.5)

То вона приводиться до канонічної форми, відповідно, відніманням або збільшенням додаткових змінних Х_n+k (з ціною С_n+k =0):

Р_j1Х₁ + Р_j2Х₂ + … + Р_jіХ_і + … + Р_jпХ_п+к = В_j;

Р_t1Х₁ + Р_t2Х₂ + … + Р_tіХ_і + … + Р_tпХ_t+m = В_t; (1.6)

При

А = С₁Х₁ + С₂Х₂ + … С_іХ_і + … С_пХ_п + 0*Х_п+к + 0*Х_t+m (1.7)

Після запису завдання в канонічній формі її вирішують симплекс-методом в наступній послідовності.

Складання початкової симплекс-таблиці.

– Визначається початковий план, в який включаються вільні члени В_j з обмежень - рівності, що має один з коефіцієнтів Р_ji, рівний +1, за умови, що в решті обмежень - рівності коефіцієнт Р_ji = 0. Наприклад, для завдання

А = С₁Х₁ + С₂Х₂ + С₃Х₃;

Р₁₁Х₁ + Р₁₂Х₂ + Р₁₃Х₃ = В₁;

Р₂₁Х₁ + Р₂₂Х₂ + Р₂₃Х₃ = В₂;

Р₃₁Х₁ + Р₃₂Х₂ + Р₃₃Х₃ = В₃; (1.8)

Значення В₁ включається в опорний план, якщо Р₁₁ = 1, Р₂₁ = 0, Р₃₁ =0 або якщо Р₁₂=1, Р₂₂ = 0, Р₃₂ = 0 або Р₁₃ = 1, Р₂₃ = 0, Р₃₃ = 0.

Значення В₂ включається в план, якщо Р₁₁ = 0, Р₂₁ = 1, Р₃₁ = 0 або Р₁₂ = 0, Р₂₂ = 1, Р₃₂=0 або Р₁₃ = 0, Р₂₃ = 1, Р₃₃ = 0.

Значення В₃ включається в план, якщо Р₁₁ = 0, Р₂₁ = 0, Р₃₁ = 1 або Р₁₂ = 0, Р₂₂ = 0, Р₃₂=1 або Р₁₃ = 0, Р₂₃ = 0, Р₃₃ = 1.

Якщо при складанні початкового плану є обмеження-рівність, в яких більше одного коефіцієнта Р_ji = +1, або він один, але в інших обмеженнях-рівності є значення Р_ji відмінні від нуля, то включають штучну змінну Х_n+k+r з ціною С_n+k+r =М (М = ∞ - скільки завгодно велике позитивне число), тобто

Р_j1Х₁ + Р_j2Х₂ + … + Р_jіХ_і + … + Р_jп + Х_п + Х_п+к + Х_n+k+r = В_j;

Α = С₁Х₁ + С₂Х₂ + … С_іХ_і + … С_пХ_п + 0*Х_п+к + МХ_n+k+r (1.9)

– початковий план записують в стовпець «В» початковою симплекс-таблиці (таблиця 1)

– заповнюють решту кліток початкової симплекс-таблиці:

а) у стовпець «V» – записують умовні позначення параметрів Х_і, по яких формувався початковий план;

б) у стовпець «С» – записують ціну, що стоїть в цільовій функції перед параметрами, по яких формувався початковий план;

в) у вільні клітки верхнього рядка послідовно записують умову позначення параметрів Х_і і відповідні ним значення ціни С_і з рівняння цільової функції;

г) у рядки з номерами від 1 до t послідовно записують значення коефіцієнтів Р_jі;

д) у рядку з номером t +1 першу і другу клітки не заповнюють, в третю записують значення А, якщо воно визначалося, або 0, а в решту кліток послідовно записують значення С_і з рівняння цільової функції, узяті з протилежним знаком;

е) якщо в початковий план включалися змінні з ціною М = ∞ то заповнюють рядок з номером t +2, елементи якої визначають як постійну суму відповідних елементів що стоять в цьому ж стовпці. При складанні враховують тільки ті рядки, у яких в стовпці «С» коштує нескінченно велике число М, тобто

,

де j – номер рядка, у якого в стовпці «С» стоїть число «М»;

При вирішенні завдань, що не вимагають включення штучних змінних з ціною М, рядок з номером t +2 не будується, а елементи рядка з номером t +1 визначаються оскільки описано вищим.

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

N

V

C

B

С1

С2

- -

Сj

- -

Сn

Сn+1

- -

Сn+k

Сn+k+1

- -

Сn+k+r

Х1

Х2

Хj

Хn

Хn+1

Хn+k

Хn+k+1

Хn+k+r

1

Х1

С1

B1

P11

P12

-

P1i

-

P1n

P1n+1

-

P1n+k

P1n+k+1

-

P1n+k+r

2

Х2

С2

B2

P21

P22

-

P2i

-

P2n

P2n+1

-

P2n+k

P2n+k+1

-

P2n+k+r

j

Хj

Сj

Bj

Pj1

Pj2

-

Pji

-

Pjn

Pjn+1

-

Pjn+k

Pjn+k+1

-

Pjn+k+r

t

Хt

Сt

Bt

Pt1

Pt2

-

Pti

-

Ptn

Ptn+1

-

Ptn+k

Ptn+k+1

-

Ptn+k+r

t+1

--

--

α

-C1

-C2

-

-Ci

-

-Cn

-Cn+1

-

-Cn+k

-Cn+k+1

-

-Cn+k+r

t+2

--

--

W0

W1

W2

-

Wi

-

Wn

0

-

0

0

-

0

Оптимізація початкової симплекс-таблиці

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

При переході від плану до плану необхідно:

– вибрати стовпець, що дозволяє, по найбільшому позитивному елементу (t+2) -о рядка. При вирішенні завдань, що не вимагають включення в цільову функцію штучних змінних з ціною М = Ѕ, стовпець, що дозволяє визначається відразу по рядку з номером t+1. Стовпцю, що дозволяє привласнити номер q=1;

– за порядком розділити величину B_j на позитивний елемент P_jq цього ж рядка, що стоїть у стовпці, що дозволяє q (елементи рядків «t+1» і «t+2» пропускаються і якщо P_jq≤0, то елементи цього рядка теж пропускаються). Знайти мінімальне відношення, тобто обчислити як:

при P_jq > 0, j < t+1.

Якщо опиниться, що у стовпці, що дозволяє, немає позитивних елементом, а оптимум ще не досягнутий, то рішення припиняється і приймається рішення про відсутність оптимуму цільової функції. Якщо продовження рішення можливе, то рядку, що містить елементи B_j і P_jq, що задовольняють цій умові привласнюється номер s = j і рядок вважається такою, що вирішує;

– знайти елемент, що дозволяє, P_sq, який знаходиться на перетині стовпця, що дозволяє, і рядка;

– перейти до нової симплекс-таблиці, відповідній новому опорному плану, для чого:

а) замінити елемент s-строки, що стоїть в стовпці «V», на Х_i, узяте з верхнього рядка стовпця, що дозволяє;

б) елементу s-строки, що стоїть в стовпці «С», привласнити значення С_i, узяте з верхнього рядка стовпця, що дозволяє;

в) заповнити вільні місця в стовпцях «V» і «С», переписуючи відповідні елементи цих стовпців з попередньої симплекс-таблиці;

г) елементи s-строки, що стоять в стовпцях «В» і «Х_i » розділити на елемент, що дозволяє, тобто обчислити

Характеристики

Список файлов ВКР