В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія - страница 76

Страницы:
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  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 

233

X > о,

(4)

де СХ - скалярний добуток векторів С = (е\ \ С2;...; сп) і X (хі; х2;...; хп), а вектори

Аі

( аіі \

а>2і ,...,А , . . . , Ап ( аіп \

а2п

\ ат2 /

Ао

Ь2

складаються відповідно з коефіцієнтів при змінних Хі, Х2, ..., хп і вільних членів.

З обмежень (3), (4) випливає, що X = і; Х2;...; хп), Х] > 0, і Є {1,...,п}, є планом або допустимим планом задачі (2) - (4) тоді й тільки тоді, коли вектор-стовпчик Ао є невід'ємною лінійною комбінацією векторів Аі, А2, ..Ап, де коефіцієнтами є координати вектора X.

План X = і; х2;...; хп) задачі (2) - (4) називається опор­ним, якщо вектори-стовпчики , які відповідають додатним ху, є лінійно незалежними.

З цього означення випливає, що число додатних координат опорного плану не перевищує т, бо вектори Ау, і Є {1,..., п}, є т-вимірними, а в т-вимірному просторі Мт максимальне чис­ло лінійно незалежних векторів дорівнює т.

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

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

Доводиться [13], що множина планів задачі лінійного про­грамування є опуклим многогранником (многокутником) або

234опуклою многогранною (многокутною) областю. Надалі на­зиватимемо цю множину многогранником (многокутником) розв'язків і позначатимемо символом 0.

Відповідь на питання, в якій точці многогранника (много­кутника) досягається екстремум цільової функції дає така тео­рема.

Теорема [14]. Якщо цільова функція / має максимум на опуклому многограннику допустимих планів (розв'язків), то він досягається у вершині (кутовій точці) цього многогран­ника.

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

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

Доводиться, що вектор X = і; х2;...; хп) є опорним пла­ном задачі (2) - (4) тоді й тільки тоді, коли X є вершиною многогранника 0 допустимих планів.

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

235

§3. Графічний (градієнтний) метод розв'язування задач лінійного програмування

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

Розглянемо спочатку задачу лінійного програмування у ви­падку двох незалежних змінних:

/ = Є\Х\ + с2Х2 тах (тіп) (1)

при обмеженнях

(   а\\Х\ + аі2Х2 < Ьі,

I     аХі + а22Х2 < Ь2, (2)

^ атіХі + ат2Х2 < Ьт;

Хі > 0,   Х2 > 0. (3)

Вважатимемо, що система умов-обмежень (2) при виконан­ні обмежень (3) сумісна і її многокутник розв'язків обмежений.

Кожна з нерівностей (2) за умов (3), як відомо [13], визначає півплощину з межею йцХі + ец2Х2 = Ьі, і Є {1,..., т}, Хі = 0, Х2 = 0. Переріз цих півплощин визначає опуклу множину -многокутник допустимих планів (розв'язків) О.

З геометричної точки зору розв'язати задачу лінійного про­грамування (1) - (3) означає, що треба знайти таку кутову точку або набір точок з О, де досягається екстремум цільо­вої функції /. Для цього використовують вектор П = і; С2), який є нормальним вектором прямої / = Н або сі Хі + С2Х2 = Н, Н Є М. Прямі сіХі + С2Х2 = Н, Н Є К, називають лініями рівня функції /. Вони зростають найшвидше у напрямку вектора П.

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

236

1) Знаходимо область допустимих розв'язків П. Якщо ця множина порожня, то задача розв'язку немає.

2) Будуємо вектор п = (сі; с2).

3) Проводимо лінію рівня (/), яка перпендикулярна до п і проходить через початок координат. При збільшенні Н пряма / = Н зсувається паралельно у напрямку вектора п. Якщо А -перша точка зустрічі прямої рівня з многокутником розв'язків П, /(А) = Но, то пряма рівня /(х) = Н при Н < Но не має спільних точок з П. Звідси випливає, що Но = тіп / на П. Ана­логічно, якщо В - остання точка перетину лінії рівня з П, то /(В) = тах/ на П.

Якщо першої точки перетину лінії рівня (/) з П не існує, тобто при всіх Н з деякого проміжку (—то; Но) пряма рівня пе­ретинає П, то /тіп = то, і задача на мінімум нерозв'язна. Як­що не існує останньої точки перетину, то /тах = +то, і задача на максимум нерозв'язна.

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

х * = лх* + л)х**,

де 0 < Л < і, X* і X** - оптимальні розв'язки (кутові точки).

4) Знаходимо координати точки екстремуму і значення ці­льової функції в ній. Для знаходження координат точки А екс­тремуму (вершини многокутника П) треба розв'язати систему лінійних рівнянь вигляду

Г агіхі + аг*Х2 = Ьі,

\ (ОдХі + (0/2X2 = Ь/,

де і та і - номера прямих, що обмежують область допустимих розв'язків П, на перетині яких знаходиться вершина А.

Страницы:
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  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 


Похожие статьи

В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія