2.1.2. Спеціальні методи лінійного програмування


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 

Загрузка...

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

До них, зокрема, відноситься транспортна задача, її модифіка-ції і так звані розподільчі задачі. Методи їх розв'язування роз-глянуті відповідно в розділах 3.3 і 3.2.

На практиці доводиться розв'язувати задачі, в яких на множи-ні допустимих розв'язків, вимагається знайти xt >0, і = \,п, при яких цільова функція у вигляді

 -       fix)         , „.

Z-(x) =     _   -»extr,    (2-lUj

u(x)

n          m

де fix) = YJCJXJ,   U(x) = ^djxj Ф 0

i=\        i=\

для всіх x, що належать області допустимих значень G, ct, dt, i = \,n відомі значення.

Функція (2.10) називається дробово-лінійною, а задачі оптимі-зації з лінійними обмеженнями і дробово-лінійною цільовою фу-нкцією називаються задачами дробово-лінійного програмування (ЗДЛП) [25].

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

Запишемо загальну модель ЗДЛП у векторно-матричній формі:

Знайти х>0,   (2-11)

що належать області G , визначеної умовами:

 

Ах = Ь (2-12)

і надають екстремуму функції цілі

(2.13)

 fix)      .  .

Z = —fc=4 —> max (mm). U\x)

Для викладення алгоритму розв'язування задачі дробово-лінійного програмування розглянемо лише випадок, коли Z -» max *).

Позначимо через X множину допустимих планів задачі (2.11)—(2.13), коли Z->max. Необхідною умовою існування розв'язку довільної задачі математичного програмування є непо-рожність множини її допустимих планів, тобто

ХФ0.   (2-14)

Щоб переконатися у виконанні або невиконанні цієї умови, потрібно скористатися методом пошуку допустимого опорного плану канонічної ЗЛП, оскільки маємо повну відповідність між множиною допустимих планів ЗДЛП та множиною допустимих планів канонічної ЗЛП. Надалі вважатимемо, що множина X до-пустимих планів ЗДЛП непорожня, тобто умова (2.19) виконана.

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

допустимих планів. Для ЗДЛП це означає, що u(xj не дорівнює нулю для всіх х є X, тобто

U\xj= ^djXj Ф 0 для всіх х є X .        (2-15)

7=1

Опуклість множини X та лінійність функції U\xJ означають,

що умову (2.15) може бути виконано тоді і тільки тоді, коли ця функція зберігає знак на всій множині допустимих планів, тобто

и[х), або лише додатня, або лише від'ємна на множиніХ. Припу-стимо, що функція U\xJ додатня на множині X

и(х)>0 для всіх хеХ . (2-16)

* Випадок, коли Z —> min зводиться до задач оптимізації, коли Z —> max іпляхом заміни цільової функції на протилежну за знаком.

Надалі будемо вважати, що ЗДЛП задовольняє вимо-гу(2.16). /Перевірити виконання цієї умови можна шля-хом обчислення методами лінійного програмування екстре-

мумів лінійної функції U\x) на множині допустимих планів Х.І

Ефективний алгоритм розв'язування ЗДЛП полягає у пере-ході від неї до такої допоміжної ЗЛП, розв'язок якої дозволяє визначити розв'язок вихідної ЗДЛП. Покажемо, як здійснити такий перехід.

Введемо нові змінні:

 

У  =

 

X

t.dixi

(=1

 

і = \,п

 

■У п+\

 

 

 

1

Е^л

(=1

 

(2.17)

 

та розглянемо допоміжну ЗЛП, побудовану за інформацією про

задачу (2.11)—(2.13):           

визначити уі > 0,   і = 1, п +1,          (2-18)

що належать області Gl, яка обмежена умовами:

 

п                    

'Eaijyi-bjyn+l=0,   j = \,m,

 

(2.19)

 

 

 

 

±d,

г=\

 

УІ

 

1

 

(2.20)

 

і максимізують функцію цілі

Z = 'YJciyi —> max

(=1

Множину допустимих планів цієї задачі позначимо через Y. Між ЗДЛП (2.11)—(2.13) та допоміжною ЗЛП (2.18)— (2.21) існує взаємозв’язок, про що свідчать наступні твердження.

— 0