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

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

3) / = 4хі + 2х2 хз х4 тах; хі + хз + х4 = 8, —5хі + хз + хб = 5, хі + х2 хз = 4; х3 > 0,і Є{1,..., 5};

2) / =

+2х4

—хі - хб

+ 4х2 + — тах;

хі 5х2 + хз = 5, хі + х2 + х4 = 4, хі + х2 + хб = 8; х3 > 0,і Є{1,..., 5};

4) / = хі + 5х2 16хз+ +5х4 + хб тах; 4хі + 2хз х4 = 8, хі + 2хз + хб = 10, 3хі + х2 2хз = 6; > 0,3 Є {1,..., 5};

243

5) / = 2х4 + Зж5 max; w

_ ^ 6) / = 7хі + 7х2 + х3 — х5 — 50 max;

Хі    Х4    о'      9 f ^хі + 7х2 + хз = 55,

х4 + х5 +2хб = 8' <   11хі + 12х2 + х4 = 132,

хі       х2 х5

,> 0,j Є{1'..., 6}; х > 0,J Є{1'---' 5};

7) / = хі 3х2 — хз — х4 — х5 +88 max; 2хі + х2 + хз = 2, —хі + 5х2 + х4 = 37, 5хі + х2 + х5 = 49, 3хі 4х2 + хб = 11, 3хі + 4х2 х7 = 19;

Відповіді

1. 1) X* = (2, 25; 0, 5), /тах = 7, 25; 2) X* = (0; 1), /тіп = —10; 3) X* = (2; 5), /max = 17; 4) X* = XX** + (1 A)X2*, 0 < А < 1, X* = (6; 1), X2* = (2; 5), /max = 14; 5) /max = +ос; 6) X* = AX* + (1 A)X2*, 0 < A < 1, X* = (3; 1), X2*(4;0), /тіп = —4; 7) X* = (3;3), /max = 12;

8) /min = —O.

2. 1) X* = (6; 2; 0; 6; 4; 0), /max = 26; 2) X* = (2; 6; 33; 0; 0), /max = 22; 3) X* = (6; 0; 2; 0; 33), /max = 29; 4) X* = (4; 0; 3; 14; 0), /max = 18; 5) X* = (1;0;1;3;0;2), /max = 12; 6) X* = (5; 5; 0; 17; 0), /max = 20; 7) a) X* = (8;9;9;0;0;23;41), /max = 6; б) X* = AX* + (1 A)X*, X** = (1;4;0;18;40;24;0), X2* = (5; 1; 11; 37; 23;0;0), 0 < A < 1, /min =

19.

244

§4. Симплексний метод розв'язування задач лінійного програмування

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

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

4.1. Алгоритм симплексного методу. Розглянемо за­дачу лінійного програмування, записану в базисній формі

/ = с\Х\ + С2 Х2 + ... + Сп Хп тах;

{Х\                \т+іхт+і +-----+ сііпХп = Ьі, Х2              2тХт+1 +-----+ Сі2пХп = Ь>2, хт    +атт+1Хт+1 + ' ' ' + атпХп Ьт;

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