5018
.pdf2) Найти базисное решение системы уравнений:
2x1 |
x2 |
x3 |
2x4 |
2x5 |
1; |
x1 |
x3 |
2x4 |
x5 2; |
|
|
3x1 |
2x2 |
x3 |
2x4 |
x5 |
0. |
Составим таблицу Жордана – Гаусса. |
|||||
Столбец |
aio |
содержит |
свободные члены соответствующих уравнений, |
||
столбцы x j |
содержат |
коэффициенты при соответствующих переменных в |
уравнениях. В столбец “Б” будем записывать базисные переменные соответствующих уравнений.
Б |
|
ai 0 |
|
|
x1 |
x2 |
|
x3 |
x4 |
|
|
x5 |
|
|||
|
|
1 |
|
|
2 |
|
-1 |
-1 |
|
-2 |
|
2 |
|
|
||
|
|
2 |
|
|
-1 |
|
0 |
|
1 |
|
2 |
|
-1 |
|
таблица 1 |
|
|
|
0 |
|
|
3 |
|
-2 |
|
|
|
-2 |
|
-1 |
|
|
|
|
|
|
|
|
|
-1 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
1 |
|
-1 |
0 |
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
|
2 |
|
|
-1 |
|
0 |
1 |
|
2 |
|
-1 |
|
таблица 2 |
||
|
|
2 |
|
|
2 |
|
-2 |
0 |
|
0 |
|
-2 |
|
|
||
x5 |
|
3 |
|
|
1 |
|
-1 |
0 |
|
0 |
|
1 |
|
|
||
x3 |
|
5 |
|
|
0 |
|
-1 |
1 |
|
2 |
|
0 |
|
таблица 3 |
||
|
8 |
|
|
4 |
|
0 |
0 |
|
0 |
|
0 |
|
|
|||
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x5 |
|
1 |
|
|
0 |
|
-1 |
0 |
|
0 |
|
1 |
|
|
||
x3 |
|
5 |
|
|
0 |
|
-1 |
1 |
|
2 |
|
0 |
|
таблица 4 |
||
|
2 |
|
|
1 |
|
0 |
0 |
|
0 |
|
0 |
|
|
|||
x1 |
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1. Выбираем |
в таблице 1 разрешающий элемент, любой |
из коэффициентов, не |
||||||||||||||
равный нулю, например |
a23 |
1 . |
|
|
|
|
|
|
|
|
|
2.Элементы разрешающей строки делим на 1 и записываем полученные значения во второй строке таблицы 2.
3.В разрешающем столбце таблицы 2 остальные элементы обращаются в ноль. Во втором уравнении неизвестная x3 становится базисной.
4.Оставшиеся элементы таблицы 2 находим по правилу прямоугольника. Приведем расчёты некоторых из них:
a10 |
1 1 ( 1) 2 |
3 , |
a30 |
1 0 ( 1) 2 |
|
2 , a11 |
|
1 2 ( 1) ( 1) |
1, |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
1 |
|
|
1 |
|
|
1 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
1 3 ( 1) ( |
1) |
|
2 , |
|
|
1 ( 2) ( |
1) 2 |
|
0 , |
1 ( 1) |
( 1) ( 1) |
( 2) . |
|||||
a31 |
|
|
|
|
a14 |
|
|
|
|
|
|
a35 |
|
|
||||
1 |
|
|
1 |
|
|
|
|
|
1 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
21
5. Повторяя алгоритм метода Жордана – Гаусса, перейдем к таблице 4. Полученная система уравнений является системой с базисом. Базисные переменные – x1 , x3 , x5 , свободные ─ x2 , x4 .
x2 |
x5 |
1; |
x2 x3 |
2x4 |
5; |
x1 |
2. |
|
Чтобы записать базисное решение, базисные переменные приравниваем к соответствующим свободным членам, свободные переменные ─ к нулю. Полученное базисное решение имеет вид X (2,0,5,0,1) .
Задание 4. Действия над векторами
Даны длины двух векторов a, b и известен угол между ними aˆ; b. Требуется найти:
1)длину соответствующего вектора в задачах: 1, 4, 7, 10, 13, 16, 19;
2)скалярное произведение в задачах: 2, 5, 8, 11, 14, 17, 20;
3)скалярный квадрат в задачах: 3, 6, 9, 12, 15, 18.
Таблица 3 – Данные задания 4 «Действия над векторами»
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
|
b |
|
|
|
|
|
ˆ |
|
|
|
Найти |
|||
|
|
|
|
|
|
|
|
|
|
a ; b |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1 |
2 |
|
3 |
|
|
|
|
|
|
|
|
|
2a |
3b |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|||
2 |
4 |
|
2 |
|
45 |
|
|
2a 3b,2a b |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
3 |
3 |
|
4 |
|
2 |
|
|
|
|
a |
b 2 |
|||||||
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|||
4 |
2 |
|
4 |
|
135 |
|
|
3a |
2b |
|
|
|||||||
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
5 |
3 |
|
2 |
|
|
|
|
|
|
|
|
|
3a 2b, a 2b |
|||||
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|||
6 |
2 |
|
5 |
|
|
|
|
|
|
|
|
|
a |
b 2 |
||||
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|||
7 |
5 |
|
3 |
|
5 |
|
|
|
|
2a |
3b |
|
||||||
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|||
8 |
4 |
|
3 |
|
60 |
|
|
3a 2b, a 2b |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
9 |
4 |
|
5 |
|
7 |
|
|
|
|
2a |
b 2 |
|||||||
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|||
10 |
5 |
|
4 |
|
120 |
|
|
3a |
2b |
|
||||||||
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
|
b |
|
|
|
|
ˆ |
|
|
|
Найти |
||||
|
|
|
|
|
|
|
|
|
a ; b |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
11 |
6 |
|
4 |
|
60 |
|
|
2a 3b,2a b |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
12 |
5 |
|
2 |
|
|
|
|
|
|
|
|
2a |
b 2 |
|||||
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
||
13 |
6 |
|
2 |
|
30 |
|
|
2a |
2b |
|
|
|||||||
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
14 |
3 |
|
6 |
|
3 |
|
|
|
|
2a 2b, a b |
||||||||
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
||
15 |
6 |
|
5 |
|
5 |
|
|
|
|
b |
3a 2 |
|||||||
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
||
16 |
1 |
|
6 |
|
|
|
|
|
|
|
|
2a |
2b |
|
||||
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
||
17 |
6 |
|
3 |
|
120 |
|
|
2a |
2b, a b |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
18 |
2 |
|
6 |
|
2 |
|
|
|
|
a |
3b 2 |
|||||||
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
||
19 |
4 |
|
6 |
|
|
|
|
|
|
|
|
3a |
2b |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
||
20 |
5 |
|
1 |
|
135 |
|
|
3a |
3b, a 2b |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22
Пример 4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ˆ |
|
0 |
|
|
||
Найти длину вектора 5a |
b , если известно, что |
a |
|
|
3, |
|
b |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
2, a ; b |
135 . |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Решение: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
5 |
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
5 |
a |
|
|
|
b |
|
|
|
|
|
|
a |
b |
|
a |
|
|
2 5 |
a |
|
|
b b 2 |
25 |
a |
2 |
10 |
a |
,b b 2 |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 ; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
25 |
|
|
|
|
|
10 |
|
|
|
|
b |
cos |
|
|
ˆ; b |
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
a |
a |
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
2 |
|
|
|
|
|
2 |
32 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
2 |
22 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
|
|
a |
a |
9; |
|
|
|
|
|
b |
|
|
|
|
b |
|
|
|
4; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
cos1350 |
|
cos 900 |
450 |
|
|
|
|
|
|
|
|
|
sin 450 |
|
|
|
|
|
|
2 |
; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
cos |
|
ˆ; b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
5 |
a |
b |
|
|
|
|
|
|
25 9 |
10 3 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
225 |
30 |
2 |
|
4 |
|
229 |
30 2 |
|
16,48. |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Задание 5. Координаты вектора в новом базисе |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, b , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Показать, что система векторов |
|
|
c |
|
|
|
|
образует базис, разложить вектор d |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
a |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
по этому базису. Решить систему уравнений, используя формулы Крамера. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Координаты векторов даны в таблице 6. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблица 6 – Данные задания 5 «Координаты вектора в новом базисе» |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
№ |
|
|
|
|
|
|
|
|
a a1 , a2 , a3 |
|
|
|
|
|
b b1 , b2 , b3 |
|
|
|
|
|
|
|
|
|
c c1 , c2 , c3 |
|
|
|
|
d d1 , d2 , d3 |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(3,1,4) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-1,-3,1) |
|
|
|
|
|
|
|
|
|
(-2,1,-5) |
|
|
|
|
|
|
|
|
(3,-1,4) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(5,3,3) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(3,-2,2) |
|
|
|
|
|
|
|
|
|
|
|
(2,4,1) |
|
|
|
|
|
|
|
|
|
|
(9,-5,6) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(1,3,2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(1,5,2) |
|
|
|
|
|
|
|
|
|
|
|
|
(-2,-1,3) |
|
|
|
|
|
|
|
|
(-1,0,5) |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2,3,3) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(4,1,-4) |
|
|
|
|
|
|
|
|
|
|
|
(1,2,5) |
|
|
|
|
|
|
|
|
|
|
(3,1,5) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(4,2,1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-1,-2,1) |
|
|
|
|
|
|
|
|
|
(2,1,2) |
|
|
|
|
|
|
|
|
|
|
(9,3,5) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(1,3,4) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-3,1,1) |
|
|
|
|
|
|
|
|
|
|
|
(1,-2,-1) |
|
|
|
|
|
|
|
|
(-2,-1,3) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(3,1,1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(1,2,4) |
|
|
|
|
|
|
|
|
|
|
|
|
(-2,-1,-5) |
|
|
|
|
|
|
|
|
|
(5,3,1) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(1,2,2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(3,5,-1) |
|
|
|
|
|
|
|
|
|
|
|
(-2,2,3) |
|
|
|
|
|
|
|
|
|
|
(-1,3,-2) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2,4,1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-1,-2,-3) |
|
|
|
|
|
|
|
|
(-1,-3,3) |
|
|
|
|
|
|
|
|
|
(-1,-3,-2) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
10 |
|
|
|
|
|
|
|
|
|
|
|
|
(2,3,4) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2,-2,3) |
|
|
|
|
|
|
|
|
|
|
|
(-1,2,1) |
|
|
|
|
|
|
|
|
|
|
(-3,1,2) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
11 |
|
|
|
|
|
|
|
|
|
|
|
|
(2,2,1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-3,4,-2) |
|
|
|
|
|
|
|
|
|
(2,-5,-3) |
|
|
|
|
|
|
|
|
|
(3,-4,-7) |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
12 |
|
|
|
|
|
|
|
|
|
|
|
|
(3,2,1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2,1,-4) |
|
|
|
|
|
|
|
|
|
|
|
(5,3,3) |
|
|
|
|
|
|
|
|
|
|
|
(6,3,0) |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||
13 |
|
|
|
|
|
|
|
|
|
|
|
|
(2,3,1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-1,2,-3) |
|
|
|
|
|
|
|
|
|
(-1,2,-5) |
|
|
|
|
|
|
|
|
|
(3,1,2) |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
14 |
|
|
|
|
|
|
|
|
|
|
|
|
(1,5,2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2,3,3) |
|
|
|
|
|
|
|
|
|
|
|
|
(4,-4,1) |
|
|
|
|
|
|
|
|
|
|
(3,5,1) |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||
15 |
|
|
|
|
|
|
|
|
|
|
|
|
(4,1,2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2,2,1) |
|
|
|
|
|
|
|
|
|
|
|
|
(-1,1,-2) |
|
|
|
|
|
|
|
|
|
(-1,3,1) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
16 |
|
|
|
|
|
|
|
|
|
|
|
|
(3,1,1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-1,4,3) |
|
|
|
|
|
|
|
|
|
|
|
(-1,-1,-2) |
|
|
|
|
|
|
|
|
|
(2,3,-1) |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||
17 |
|
|
|
|
|
|
|
|
|
|
|
|
(1,4,2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-2,-5,-1) |
|
|
|
|
|
|
|
|
(3,1,1) |
|
|
|
|
|
|
|
|
|
|
|
(0,-5,1) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
18 |
|
|
|
|
|
|
|
|
|
|
|
|
(3,1,5) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-1,-3,2) |
|
|
|
|
|
|
|
|
|
(1,-2,2) |
|
|
|
|
|
|
|
|
|
|
(-2,1,3) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
19 |
|
|
|
|
|
|
|
|
|
|
|
|
(1,2,3) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(-2,-4,-1) |
|
|
|
|
|
|
|
|
(1,3,-3) |
|
|
|
|
|
|
|
|
|
|
(1,4,1) |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
20 |
|
|
|
|
|
|
|
|
|
|
|
|
(2,2,3) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2,3,4) |
|
|
|
|
|
|
|
|
|
|
|
|
(-3,2,1) |
|
|
|
|
|
|
|
|
|
|
(-6,5,3) |
|
|
23
Пример 5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2,3,1) |
|
|||
|
|
|
|
|
|
|
|
|
|
(1,1,2) , b (5,3, |
1) , |
|
|
|||||||||||
|
|
Показать, |
что система векторов |
a |
c |
образует |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
базис, найти разложение |
|
d (5,2,2) в этом базисе. |
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
Решение: |
Покажем, что векторы |
|
, b , |
|
|
образуют |
базис. Найдём |
|||||||||||||||
|
|
a |
c |
|||||||||||||||||||||
определитель, составленный из координат этих векторов. |
|
|||||||||||||||||||||||
|
a1 |
b1 |
c1 |
|
1 |
5 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
a2 |
b2 |
c2 |
|
1 |
3 |
3 |
1 3 1 5 3 2 2 1 1 2 3 2 1 1 3 5 1 1 17 0. |
||||||||||||||||
|
a3 |
b3 |
c3 |
|
2 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т.к. определитель не равен нулю, следовательно, векторы линейно независимы и образуют базис.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Разложим вектор |
|
d по векторам данного базиса: d |
|
|
1a |
2b |
3c , здесь |
||||||
|
|
|
|
c |
. |
В координатной |
|||||||
1 , 2 , 3 − искомые координаты вектора d в базисе a , b , |
|||||||||||||
форме это уравнение |
1 (1, 1, 2) + 2 (5, 3, -1) + 3 (2, 3, 1) = (5, 2, 2) принимает |
||||||||||||
вид: |
|
|
|
|
|
|
|
|
|
|
|
|
|
15
13
2 1
2
2
2
2
3
3
3
3
5;
2;
2.
|
|
|
Решим приведённую систему по формулам Крамера |
|
i |
, i 1,2,3 ; для |
|||||||||||||||||||||||||||||||
|
|
|
i |
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
этого вычислим |
дополнительные |
|
определители |
|
i i |
1,2,3 |
полученные из |
||||||||||||||||||||||||||||||
основного определителя |
|
|
заменой i –го столбца столбцом свободных членов: |
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
5 |
|
|
2 |
|
|
|
|
|
|
1 |
5 |
2 |
|
|
|
|
|
1 |
5 |
5 |
|
|
|
|
|
|
|
|||
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
1 |
2 |
|
|
|
3 |
|
|
3 |
|
|
34; |
2 |
|
1 |
2 |
3 |
|
17; |
3 |
|
1 |
3 |
2 |
|
1. |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
2 |
|
|
|
1 |
|
1 |
|
|
|
|
|
|
2 |
2 |
1 |
|
|
|
|
|
2 |
1 |
2 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
Таким образом, находим коэффициенты разложения вектора d : |
||||||||||||||||||||||||||||||||||
|
|
|
1 |
|
|
34 |
|
|
|
|
2; |
|
2 |
|
17 |
1; |
|
|
|
3 |
|
17 |
1. |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
1 |
|
|
|
|
17 |
|
|
|
|
2 |
|
|
17 |
3 |
|
|
|
17 |
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
d 2 a |
|
b |
c |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Задание 6. Решение задач линейного программирования симплексным методом
Затраты трёх видов сырья А, В, С на производство единицы каждого из трёх типов продукции заданы векторами – d1(a1,b1,c2 ) , d2 (a2 ,b2 ,c2 ) , d3 (a3 ,b3 , c3 ) . Запасы каждого вида сырья заданы вектором Q(qA , qB , qC ) , прибыль от реализации единицы продукции каждого типа − вектором P( p1 p2 p3 ) . Определить оптимальный план выпуска продукции, при котором прибыль от реализации выпущенной продукции будет максимальной. Составить математическую
24
модель задачи, решить задачу симплексным методом. Составить двойственную задачу к данной и найти её решение.
Таблица 7 – Данные задания 6 «Симплексный метод решения задач»
№ |
d1(a1,b1,c2 ) |
d2 (a2 ,b2 ,c2 ) |
d3 (a3 ,b3 , c3 ) |
Q(qA , qB , qC ) |
P( p1 p2 p3 ) |
|
1 |
(3, 2, 4) |
(5, 4, 3) |
(6, 2, 2) |
(270, 90, 190) |
(2, 1,1) |
|
2 |
(3, 2, 4) |
(1, 2, 3) |
(5, 4, 1) |
(230, 210, 130) |
(1, 2, 3) |
|
3 |
(3, 2, 4) |
(4, 7, 6) |
(2, 1, 1) |
(230, 270, 190) |
(1, 1, 2) |
|
4 |
(7, 1, 3) |
(1, 2, 1) |
(3, 1, 6) |
(200, 90, |
150) |
(3, 1, 2) |
5 |
(4, 5, 3) |
(4, 7, 6) |
(2, 1, 1) |
(230, 270, 190) |
(2, 1, 3) |
|
6 |
(2, 5, 4) |
(3, 2, 7) |
(6, 1, 2) |
(190, 140, 100) |
(2, 1, 3) |
|
7 |
(2, 6, 1) |
(8, 4, 3) |
(1, 5, 4) |
(325, 325, 215) |
(1, 3, 2) |
|
8 |
(5, 3, 1) |
(3, 5, 4) |
(2, 1, 3) |
(270, 240, 145) |
(3, 1, 2) |
|
9 |
(4, 1, 3) |
(1, 3, 3) |
(2, 4, 5) |
(200, 120, 260) |
(1, 2, 3) |
|
10 |
(6, 1, 2) |
(9, 1, 1) |
(3, 2, 4) |
(480, 90, 140) |
(2, 5, 4) |
|
11 |
(2, 2, 4) |
(1, 1, 5) |
(3, 5, 1) |
(150, 190, 230) |
(2, 3, 4) |
|
12 |
(4, 2, 5) |
(2, 6, 1) |
(5, 1, 2) |
(200, 150, 160) |
(2, 3, 1) |
|
13 |
(3, 2, 1) |
(5, 3, 4) |
(4, 4, 5) |
(160, 120, 180) |
(2, 1, 3) |
|
14 |
(2, 3, 5) |
(4, 1, 3) |
(3, 8, 1) |
(100, 150, 130) |
(1, 2, 1) |
|
15 |
(3, 7, 2) |
(5, 1, 2) |
(1, 1, 6) |
(125, 165, 150) |
(3, 2, 1) |
|
16 |
(9, 3, 1) |
(4, 3, 5) |
(1, 4, 1) |
(290, 175, 155) |
(1, 2, 1) |
|
17 |
(2, 6, 4) |
(4, 2, 1) |
(1, 3, 5) |
(130, 200, 150) |
(2, 1, 1) |
|
18 |
(1, 4, 2) |
(1, 5, 3) |
(7, 1, 6) |
(175, 170, 210) |
(1, 2, 1) |
|
19 |
(2, 3, 2) |
(2, 3, 4) |
(7, 4, 1) |
(150, 160, 280) |
(1, 1, 2) |
|
20 |
(3, 1, 2) |
(1, 2, 4) |
(5, 3, 1) |
(170, 115, 105) |
(2, 2, 3) |
Пример 6. Составим математическую модель. |
|
|
|
|
|
Пусть предприятие выпустит x1 единиц |
|
продукции |
I, х2 |
единиц |
|
продукции II, х3 единиц продукции III. |
|
|
|
|
|
Расход сырья А на все виды продукции – |
а х а2 х2 а3 х3 . По условию |
||||
|
1 |
1 |
|
|
|
задачи расход сырья А не должен превышать запаса qa , т.е. а х |
а2 х2 |
а3 х3 ≤ qa |
|||
|
|
1 |
1 |
|
|
Аналогично составляем ограничения расхода сырья В и С. Получим систему неравенств:
a1x1 |
a2 x2 |
a3 x3 |
qa ; |
b1x1 |
b2 x2 |
b3 x3 |
qb ; |
c1x1 |
c2 x2 |
c3 x3 |
qc . |
Прибыль от реализации выпущенной продукции будет равна max .
Запишем модель задачи:
25
a1x1 |
a2 x2 |
a3 x3 |
|
qa ; |
|
|||
b1x1 |
b2 x2 |
b3 x3 |
|
qb ; |
(12) |
|||
c1x1 |
c2 x2 |
c3 x3 |
|
qc . |
|
|||
x1 |
0, x2 |
0, x3 |
|
0 |
|
|
||
Z p1x1 |
p2 x2 |
|
p3 x3 max . |
(13) |
||||
(13) |
называют целевой функцией. |
|
||||||
Пусть d1 (7,2,5), d2(0,3,1), d3(5,2,1), Q(220,140,100), Р(2,1,1) |
||||||||
7х1 |
0х2 |
5х3 |
220; |
|
||||
2x1 |
3x2 |
2x3 |
140; |
(14) |
||||
|
||||||||
|
5x1 |
x2 |
x3 |
100. |
|
|||
x1 |
0, x2 |
0, x3 |
0 |
|
||||
Z |
|
2x1 |
x2 |
x3 |
max . |
(15) |
||
Введем балансовые переменные x4 , |
x5 , x6 в каждое неравенство для приведения |
|||||||
модели к каноническому виду |
|
|||||||
7x1 |
|
0x2 |
5x3 |
|
x4 |
220; |
|
|
2x1 |
|
3x2 |
|
2x3 |
|
x5 |
140; |
(16) |
5x1 |
|
x2 |
x3 |
x6 |
|
100. |
|
|
x j |
|
0, (j=1,2,…6) |
|
|||||
Z |
2x1 |
x2 |
x3 |
|
max . |
(17) |
Алгоритм симплексного метода
1.Записываем данную задачу в исходную симплексную таблицу.
2.Если все элементы оценочной строки симплексной таблицы неотрицательны, то соответствующий план является оптимальным.
3.Если в оценочной строке содержится отрицательный элемент, а в столбце над ним нет ни одного положительного элемента, то целевая функция не ограничена сверху на множестве допустимых планов и задача не имеет решения.
4.Если в каждом столбце соответствующем отрицательной оценке содержится хотя бы один положительный элемент, то можно перейти к “лучшему ” плану следующим образом:
а) выбираем разрешающий столбец по наименьшей отрицательной оценке;
б) выбираем разрешающую строку по минимальному значению ; равно отношению свободных членов к соответствующим положительным
элементам разрешающего столбца;
26
в) на пересечении разрешающего столбца и разрешающей строки лежит разрешающий элемент; г) элементы разрешающей строки делим на разрешающий элемент и
записываем в новой таблице, сохраняя порядок строки, оставшиеся элементы разрешающего столбца заполняем нулями; д) элементы остальных строк, в том числе и оценочной строки, вычисляем по
формулам прямоугольников (см. метод Жордана – Гаусса).
Составим симплексную таблицу.
Таблица заполняется следующим образом:
Встолбце “ai0” записываются свободные члены уравнений (16), в столбцах “ x1”, “x2”, …, “x6” − коэффициенты при соответствующих неизвестных этой системы.
Встолбце “базис” выписываются базисные переменные, содержащиеся в соответствующих уравнениях системы (16).
Верхняя строчка и крайний левый столбец содержат коэффициенты при соответствующих неизвестных целевой функции Z выражения (17).
Последняя строка таблицы называется оценочной строкой, а её элементы a0j оценками. Первый элемент a00 оценочной строки равен значению целевой функции Z для начального опорного плана
X0 (0,0,0,220,140,100) .
Это значение может быть получено как результат скалярного умножения вектора – столбца “сj “ на вектор – столбец свободных членов “ai0” :
Z( X 0) = a00 = 0∙220 + 0∙140 + 0∙100 = 0.
Остальные значения a0к оценочной строки получаются в результате скалярного умножения вектора – столбца “сj “ на вектор – столбец коэффициентов при переменной хк с последующим вычитанием соответствующего элемента ск верхней строки:
a01 = 0∙7 + 0∙2 +0∙5 – 2 = -2; a02 = 0∙0 + 0∙3 +0∙1 – 1 = -1; a03 = 0∙5 + 0∙2 +0∙1 – 1 = -1.
Оценки для базисных переменных всегда равны 0.
27
|
Базис |
|
2 |
|
1 |
|
1 |
0 |
0 |
0 |
|
|
|
|
|
|
||
cj |
xj |
ai0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
|
x3 |
x4 |
x5 |
x6 |
|
|
|
|
|
|
|||||
0 |
x4 |
220 |
7 |
|
0 |
|
5 |
1 |
0 |
0 |
220/7 |
|
||||||
0 |
x5 |
140 |
|
2 |
|
3 |
|
2 |
0 |
1 |
0 |
140/2 |
|
|||||
0 |
x6 |
100 |
|
5 |
|
1 |
|
1 |
0 |
0 |
1 |
100/5 min |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Z |
0 |
-2 |
|
-1 |
|
-1 |
0 |
0 |
0 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
x4 |
80 |
0 |
|
-7/5 |
|
18/5 |
1 |
0 |
-7/5 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
100 |
|
|
min |
|
0 |
x5 |
100 |
0 |
|
13/5 |
|
8/5 |
0 |
1 |
-2/5 |
5 /13 |
|
||||||
2 |
x1 |
20 |
1 |
|
1/5 |
|
1/5 |
0 |
0 |
1/5 |
20 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1/ 5 |
|
|
|
|
|
|
Z |
40 |
0 |
|
-3/5 |
|
-3/5 |
0 |
0 |
2/5 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1740 |
min |
|||
0 |
x4 |
1740/13 |
0 |
|
0 |
|
|
58/13 |
1 |
7/13 |
-21/13 |
|
||||||
|
|
|
|
|||||||||||||||
|
|
|
58 |
|
|
|
||||||||||||
1 |
x2 |
500/13 |
0 |
|
1 |
|
8/13 |
0 |
5/13 |
-2/13 |
|
|
|
|||||
|
|
500/8 |
|
|||||||||||||||
2 |
x1 |
160/13 |
1 |
|
0 |
|
1/13 |
0 |
-1/13 |
3/13 |
160 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Z |
820/13 |
0 |
|
0 |
|
-3/13 |
0 |
3/13 |
4/13 |
|
|
|
|
|
|
||
1 |
x3 |
30 |
0 |
|
0 |
|
1 |
13/58 |
7/58 |
-21/58 |
|
|
|
|
|
|
||
1 |
x2 |
20 |
0 |
|
1 |
|
0 |
-8/58 |
18/58 |
4/58 |
|
|
|
|
|
|
||
2 |
x1 |
10 |
1 |
|
0 |
|
0 |
-1/58 |
-5/58 |
15/58 |
|
|
|
|
|
|
||
|
Z |
70 |
0 |
|
0 |
|
0 |
3/58 |
15/58 |
13/58 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y1 |
y2 |
y3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
Исходное |
|
опорное |
решение X 0 (0;0;0;220;140;100) , |
Z0 |
0 |
не |
является |
||||||||||||
оптимальным, в оценочной строке три отрицательные оценки |
(-2), |
(-1), |
(-1), |
|||||||||||||||||
ситуация соответствует пункту 4 алгоритма симплексного метода. |
Перейдём к |
|||||||||||||||||||
новому опорному плану: |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
а) разрешающий столбец соответствует переменной |
x1 , т.к. оценка (-2) ─ |
||||||||||||||||||
наименьшая отрицательная оценка оценочной строки; |
|
|
|
|
|
|
||||||||||||||
|
б) |
третья |
|
строка является |
разрешающей, |
т.к. |
для |
неё |
||||||||||||
min |
min |
|
220 |
; |
140 |
; |
100 |
|
min 31,4;70;20 |
20 ; |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
7 |
|
2 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
в) на пересечении разрешающих столбца и строки лежит разрешающий элемент 5, при этом в базис войдёт переменная x1 , а переменная x6 выйдет из базиса.
Далее заполнение новой таблицы осуществляется по методу Жордана – Гаусса.
28
|
|
|
|
|
|
|
В |
|
результате |
первой |
|
итерации получим |
новое опорное |
решение |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
X1 (20;0;0;80;100;0) , Z1 40 . |
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
Вторая итерация приводит к решению: |
|
|
|||||||||||
|
|
|
|
|
|
2 ( |
160 |
; |
500 |
;0; |
1740 |
;0;0) , |
|
|
820 |
. |
|
|
|
|
X |
Z2 |
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||
13 |
13 |
|
13 |
|
|
13 |
|
|
|
|
||||||||||
|
|
|
|
|
|
|
После |
|
третьей |
итерации |
получаем |
оптимальное |
решение: |
|||||||
|
|
|
|
|
Zmax |
70 . Дальнейшее увеличение Z невозможно, т.к. все |
||||||||||||||
X 3 (10;20;30;0;0;0) , |
||||||||||||||||||||
оценки оценочной строки стали неотрицательными. |
|
|
||||||||||||||||||
|
|
|
|
|
|
|
Оптимальное |
решение |
исходной задачи получаем отбрасыванием из |
|||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||
X3 компонент, |
|
связанных |
с |
|
балансовыми переменными x4 , x5 , x6 , т.е. |
|||||||||||||||
|
|
опт (10,20,30) , при этом значение Zmax |
70 не изменится. |
|
||||||||||||||||
X |
|
Двойственность в линейном программировании
Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования, так называемую двойственную задачу.
Рассмотрим задачу об оптимальном выпуске продукции (12)-(13):
a1x1 |
a2 x2 |
a3 x3 |
qa |
y1; |
|
b1x1 |
b2 x2 |
b3 x3 |
qb |
y2 ; |
(12) |
c1x1 |
c2 x2 |
c3 x3 |
qc |
y3. |
|
x1 |
0, x2 |
|
0, x3 |
|
0 |
|
|
|
Z p1x1 |
p2 x2 |
p3 x3 |
max . |
(13) |
||||
Каждому ограничению ставится в соответствие переменная двойственной |
||||||||
задачи yi |
. Двойственная задача имеет вид: |
|
||||||
|
|
|
|
|
|
|||
a1 y1 |
b1 y2 |
a3 y3 |
|
p1 |
x1; |
|
||
a2 y1 |
b2 y2 |
c2 y3 |
p2 |
x2 ; |
(18) |
|||
a3 y1 |
b3 y2 |
c3 y p3 |
x3. |
|
||||
|
y1 |
0, y2 |
0, y3 |
0 |
|
|
||
W |
qa y1 |
qb y2 |
qc y3 |
min. |
(19) |
|||
Для |
составления |
модели двойственной задачи необходимо |
учесть |
следующие свойства:
1.Число ограничений исходной задачи равно числу неизвестных двойственной.
29
2.Матрица коэффициентов при неизвестных одной задачи транспонируется для неизвестных другой задачи.
3.Знаки в неравенствах исходной задачи и двойственной имеют противоположный смысл, в исходной знак “ ”, в двойственной знак “ ”.
4.Свободные члены ограничений исходной задачи становятся коэффициентами
целевой функции двойственной задачи, |
коэффициенты целевой функции |
|
исходной задачи ─ свободными членами неравенств двойственной задачи. |
||
5. |
В исходной задаче целевая функция |
Z max , в двойственной задаче |
W |
min . |
|
Задачи (12)–(13) и (18)–(19) называются симметричными взаимно двойственными задачами. Модель двойственной задачи к исходной (14) – (15) имеет вид:
7 y1 2 y2 |
5 y3 |
2; |
|
||
0 y1 |
3y2 |
1y3 |
1; |
|
|
|
5 y1 |
2 y2 |
y |
1. |
|
y1 |
0, y2 |
0, y3 |
0 |
|
|
W |
220y1 |
140y2 |
100y3 |
min. |
Если одну из задач решить симплексным методом, то неизвестные в двойственной задаче равны соответствующим оптимальным оценкам базисных переменных исходной задачи плюс коэффициент ( c j ), стоящий в таблице над
соответствующей базисной переменной.
y1 |
3 /1 |
0 |
3 /13 , |
y2 15/ 58 |
0 |
15/ 58, |
y3 |
13/ 58 |
0 |
13/ 58 . |
|||||||
W |
220 |
3 |
|
140 |
15 |
|
100 |
13 |
|
4060 |
70. |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|||||||
min |
|
58 |
|
58 |
58 |
|
|
58 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
Задание 7. Транспортная задача |
|
|
|
|
||||||||||||
|
В пунктах |
производства |
А1, А2 , А3 , А4 имеется |
однородный груз в |
|||||||||||||
количестве соответственно а1 , |
а2 , а3 , а4 . Данный груз необходимо доставить в 3 |
||||||||||||||||
пункта назначения |
В1 , В2 , В3 в количестве соответственно |
b1 , b2 , b3 . Стоимость |
|||||||||||||||
перевозки единицы груза (тариф) из пункта |
Аi |
в пункт |
Bj |
равна cij . Требуется |
составить план перевозок, при котором все грузы будут вывезены с минимальными затратами.
30