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

Страницы:
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 

Приклад 1. Продаючи товари двох типів рі і р2 торговельне підприємство використовує чотири види ресурсів Б і, $2, і £4. Нор­ми витрат ресурсів на реалізацію одиниці товару та обсяг ресурсів наведено в таблиці

237


Ресурси

Норма витрат ресурсів

Запаси

 

Pi

P2

ресурсів

Si

2

2

12

S2

1

2

В

S3

4

Q

16

S4

Q

4

12

Прибуток від реалізації одиниці товару Pi становить 2 гр.од., а товару P2 - З гр.од.

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

Нехай Xj - кількість одиниць товару Pj, j Є {1, 2}, яку треба реалізувати. Математична модель задачі має вигляд:

f = 2xi + 3x2 max;

2xi + 2x2 < 12, xi + 2x2 < В, 4xi < 16, 4x2 < 12;

xi > О,    X2 > О.

Побудуємо область допустимих розв'язків. Спочатку проведемо прямі:

2xi + 2x2 = 12 (1), xi +2x2 = 8 (2), 4xi = 16 (З),

2З8

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

2 0 + 2 0 < 12   або   0 < 12.

Оскільки нерівність правильна, то нерівність 2x1 + 2x2 < 12 задо­вольняють координати тих точок, які знаходяться у тій же півпло-щині, що й точка О. Цю півплощину відзначаємо стрілочками на пря­мій (1). Аналогічно знаходимо півплощини, які визначаються другим і третім обмеженнями-нерівностями. Переріз одержаних півплощин й визначає многокутник розв'язків 0ABCD.

Для побудови лінії рівня 2x1 + 3x2 = 0 (/) відкладемо нормаль­ний вектор п = (2; 3) і через точку О проведемо пряму, перпенди­кулярну до цього вектора. Пряму (/) пересуваємо паралельно самій собі у напрямку вектора п. З рисунка 1 випливає, що опорною до многокутника розв'язків П ця пряма є в точці C, де функція / на­буває максимального значення. Очевидно, що точка C лежить на перетині прямих (1), (2), (3). Знайдемо її координати, розв'язавши, наприклад, систему

ґ 2x1 + 2x2 = 12, \ 4xl = 16,

звідки одержуємо, що Xl =4, X2 = 2.

Отже, оптимальний розв'язок X* = (4; 2), /тах = /(X*) = 2 4 + 3 2 = 14, а це означає, що для забезпечення максимального прибутку, що становить 14 гр.од., треба реалізувати чотири одиниці товару Pl і дві одиниці товару P2.

Приклад 2. Розв'язати задачу про складання кормового ра­ціону (приклад 2 з §1), математична модель якої має вигляд:

/ = 4x1 + 6x2 тіп;

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

3x1 + X2 > 9, Xl + 2x2 > 8, Xl + 6x2 > 12;

XI > 0,   X2 > 0.

239

Побудуємо многокутник розв'язків. Для цього в системі коор­динат 0x1x2 зобразимо межові прямі:

3x1 + X2 = 9 XI + 2x2 = 8 XI + 6x2 = 12 XI =0,   X2 = 0

(1) ,

(2) ,

(3) , (4)

і з'ясуємо, яку півплощину визначає кожне обмеження-нерівність відносно відповідної прямої (рис. 2).

Х2 і

Будуємо вектор п = (4; 6) = 2(2; 3) і пряму рівня 4x1+6x2 = 0 (/).

Якщо рухати цю пряму у напрямку вектора п, то вперше вона стає

опорною до многокутника розв'язків П у точці В, а це означає, що в цій точці функція / набуває мінімального значення. Точка В лежить на перетині прямих (1) і (2), а тому для знаходження її координат треба розв'язати систему рівнянь:

звідки випливає, що Хі = 2, а Х2 = 3.

Отже, оптимальний розв'язок X* = (2; 3), а fm■m = /(X*) = 4• 2+ 6 • 3 = 26.

Це означає, що для забезпечення необхідного добового раціону при мінімальних витратах у 26 гр.од. треба скласти раціон з 2 од. корму Р\ і 3 од. корму Р2.

Зауваження. За допомогою графічного методу можна розв'язувати задачі лінійного програмування, система обме­жень яких містить п невідомих і т лінійно незалежних рів­нянь, якщо п т = 2.

9 f

3x1 + X2 XI + 2x2 9, 8,

240

Приклад 3. Розв'язати задачу

/ = хі + 2х3 + х5 тіп;

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

Хі    2    3    4 + Х5 = 5, Х2    3    4 Х5 = 2,

Хз   Х4 + Х5 = 1;

х3- > 0,   з 5}.

Маємо п = 5, т = 3. Оскільки п—т = 5—3 = 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  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лінійна алгебра й аналітична геометрія