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

Страницы:
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) виходячи з мети досліджень, визначити цільо­ву функцію; 3) враховуючи обмеження на параметри задачі та їхні кількісні величини, записати систему обмежень.

217

1.1. Приклади задач лінійного програмування.

Приклад 1 (задача про використання сировини або планування виробництва). Для виготовлення двох видів продукції Р\ і Р2 використовують чотири типи сировини. За­паси сировини, кількість одиниць сировини, що витрачається на виготовлення одиниці продукції, а також величина доходу, одержувана від реалізації одиниці продукції наведені в таблиці

Тип

Кількість од. сир. , що

Запаси

сировини

витрач. на вигот. од. прод. Ру

сировини

 

Рі

 

 

 

2

3

19

 

2

1

13

5з

0

3

15

5*4

3

0

18

Доход

 

 

 

від реалізації

7

5

 

од. прод.

 

 

 

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

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

2хі +3x2 < 19, 2х1 + х2 < 13, 3х2 < 15, 3хі < 18,

яка стверджує, що кількість сировини, яка витрачається на ви­готовлення продукції, не повинна перевищувати запасів сиро­вини. Якщо продукція Ру не випускається, то ху =0, і Є {1, 2}, а якщо випускається, то ху > 0, і Є {1, 2}. Отже, одержуємо знакові обмеження на невідомі хі,

х1 > 0,    х2 > 0.

218

Реалізація Х\ одиниць продукції Р\ і х2 одиниць продукції Р2 дає відповідно 7хі і 5х2 грошових одиниць доходу, а тому сумарний доход

/ = 7хі + 5Х2 (гр. од.). Отже, ми одержали математичну модель задачі:

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

/ = 7х1 + 5х2 — тах;

і +3х2 < 19, 2х1 + х2 < 13, 3х2 < 15, 3хі < 18;

х3 > 0,   І е{1, 2}.

(1)

(2) (3)

І

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

Сукупність векторів X = (хі;х2), координати яких задо­вольняють нерівності (2), (3), називається областю допусти­мих планів (розв'язків) задачі. Той з цих планів (розв'язків) X* = (хі; х*), який реалізує екстремум цільової функції /, на­зивається оптимальним планом (розв'язком) задачі.►

Приклад 2 (задача про складання кормового раціо­ну або задача про дієту). При відгодівлі кожна тварина щоденно повинна отримувати не менше 9 одиниць поживної речовини Бі, не менше 8 одиниць речовини 52 і не менше 12 одиниць речовини Бз. Для складання раціону використовують два види корму Рі і Р2. Вміст кількості одиниць поживної ре­човини в одиниці кожного виду корму і вартість одиниці корму наведено в таблиці

219


Поживні

Кількість од. поживної

Кількість

речовини

речовини в од. корму

поживної

 

Рі

Р2

речовини

 

3

1

9

 

1

2

8

 

1

6

12

Вартість од. корму

4

6

 

Треба скласти математичну модель формування добово­го раціону потрібної поживності при мінімальних витратах на нього.

А Нехай х3 - кількість одиниць корму , і Є {1, 2}, яку треба придбати для організації добового раціону. Тоді з умови задачі випливає, що повинні виконуватись обмеження:

3х1 + х2 > 9, х1 + 2х2 > 8, х1 + 6х2 > 12.

Якщо корм Р1 не використовується в раціоні, то х1 = 0, а коли використовується, то х1 > 0. Аналогічно маємо, що х2 > 0. Отже, х1 > 0, х2 > 0.

Нашою метою є добитися мінімальних витрат при скла­данні добового раціону. Оскільки сумарна вартість раціону / = 4х1 + 6х2, то цю функцію треба дослідити на мінімум.

Отже, математична модель задачі така:

/ = 4х1 + 6х2 —>■ тіп; (4) 3х1 + х2 > 9,

х1 +2х2 > 8, (5) х1 + 6х2 > 12

х1 > 0,  х2 > 0. (6)

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

Приклад 3 (транспортна задача). У пунктах А1, А2, Аз розміщені кар'єри, які видобувають глину, а в пунктах Е>1,

220

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

Постачальники

Споживачі

Запаси

 

Ві

В2

Вз

В4

 

Аг

5

8

24

30

49

А2

8

10

20

32

48

Аз

17

28

35

40

42

Потреби

32

57

32

15

 

А Нехай      - кількість глини, яку одержує з кар'єру Аі, і є {1, 2, 3}, цегельний завод     , і є {1, 2, 3, 4}. Тоді система нерівностей

Х\\ + Х\2 + Х\3 + Ж14 < 49, Х21 + Х22 + Х23 + Х24 < 48,

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