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

Страницы:
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.  ат1Х1 + ат2Х2 + . . . + атпХп Ьт;

Х,- > 0, І є{1,...,и]. (12)

У канонічній задачі кількість невідомих завжди більша за кількість рівнянь, тобто п > т. Справді, якщо кількість неві­домих дорівнює кількості рівнянь і рівняння лінійно незалежні, то система має єдиний розв'язок. Якщо при цьому принаймні одне з Х,, І є {1,... ,п} від'ємне, то це означає, що одержаний розв'язок не є допустимим, і, отже, задача не має розв'язку. Якщо ж всі Х, > 0, І Є {1,...,п}, то знайдений розв'язок є допустимим, і він є оптимальним, бо інших розв'язків немає.

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

223

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

Частинним випадком канонічної задачі є задача в базис­ній формі, яка характерна тим, що всі Ьі > 0, і Є {1,..., т}, і в кожному рівнянні є змінна з коефіцієнтом, що дорівнює оди­ниці, яка не входить в жодне з решти рівнянь. Така змінна називається базисною. Наприклад,

f = C1X1 + C2 X2 + ... + Cn Xn max;

X1

X2

+a1m+1Xm+1 + +a2m+1Xm+1 +

+ a1nXn + Cl2nXn

b1, b2,

Xm

+атт+1хт+1 атпхп

хі > 0, і Є {1,^^,п}; Ьі > 0, і Є {1, •, т}^ Тут змінні Хі, і Є {1, •, т}, є базисними.

bm;

(13)

(14)

(15) (16)

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

Стандартні і канонічні задачі можна записувати у різних формах

Матрична форма. Введемо позначення: С

A

(  a11 a12 a21 a22

\ am1 am2

a1n \

X

X1 Xn

(C1 C2

Ao =

Cn) ,

b1

b2

bm

Тоді стандартна задача (7) - (9) записується у вигляді

f = CX max;

AX < Ao; (1T) X > 0.

224а канонічна (10) - (12) - у вигляді

f = CX max;

АХ = Ао; X > 0.

Зауваження. Якщо А = (а^) і&{і,..,т}-

ІЄ{1,..,п}

В   =   (Ьі/ ) іе{1,..., т} ,

матриці однакового розміру, то нерівність А < В рівносильна нерівностям аі/ < Ьі/, і Є {1,..., т}, і Є {1,..., п}.

Векторна форма. Якщо позначити через А/ і-й стовпчик матриці А, тобто

Aj

a1j a2j

amj j Є {1,...,n},

то задачі (7) - (9) і (1O) - (12) можна подати відповідно у вигляді:

f = CX max;

X1 A1 + X2A2 + . . . + XnAn < Ao;

X > О; f = CX max;

X1 A1 + X2A2 + . . . + XnAn = Ao;

X > О,

(2О)

(21)

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

1; х2;^ ^ ^ ; хп).

1.3. Еквівалентні перетворення задач лінійного програмування. Очевидно, що стандартна і канонічна зада­чі є частинними випадками загальної. У той же час всі ці типи задач еквівалентні між собою : загальна задача за допомогою простих перетворень зводиться до стандартної або канонічної, а останні перетворюються одна в одну. Тому, розв'язавши одну з них, ми однозначно дістанемо розв'язок другої.

225

На конкретних прикладах опишемо перетворення, які доз­воляють звести один тип задачі до іншого.

Приклад 4. Звести до канонічного вигляду задачу

f = 8жі + 2x2 max;

Страницы:
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лінійна алгебра й аналітична геометрія