Шифр 35: 5 задач. Показать, что система линейных уравнений имеет единственное решение

  • ID: 10017 
  • 8 страниц

Фрагмент работы:

Шифр 35: 5 задач. Показать, что система линейных уравнений имеет е…

Задача 5.

Показать, что система линейных уравнений имеет единственное решение, и найти его двумя способами: а) по правилу Крамера; б) матричным способом

Решение:

а) решим эту систему по формулам Крамера

Найдем главный определитель системы

-4 1 -4

= 4 3 -3 = -12-16-6+24-12-4 = -26

2 1 1

Т.к. определитель системы не равен 0, то система имеет единственное решение. Найдем его по правилу Крамера

10 1 -4

1= 15 3 -3 = 30-60+3-12+30-15 = -24

-1 1 1

-4 10 -4

Y= 4 15 -3 = -60+16-60+120+12-40 = -12

2 -1 1

-4 1 10

Z= 4 3 15 = 12+40+30-60+60+4 = 86

2 1 -1

б) решим эту систему матричным методом. В этом случае решение находится по формуле:

X=A-1B

Найдем алгебраические дополнения:

A11=(-1)1+1 3 -3 = 6 A21=(-1)1+1 1 -4 = -5 A31=(-1)1+1 1 -4 = 9

1 1 1 1 3 -3

A12=(-1)1+2 4 -3 = -10 A22=(-1)1+2 -4 -4 = 4 A32=(-1)1+2 -4 -4 = -28

2 1 2 1 4 -3

A13=(-1)1+3 4 3 = -2 A23=(-1)1+3 -4 1 = 6 A33=(-1)1+3 -4 1 = -16

2 1 2 1 4 3

Задача 17.

Пользуясь методом Гаусса, найти общее решение системы линейных уравнений, а также два частных ее решения, одно из которых базисное.

Решение:

Запишем расширенную матрицу системы и преобразуем ее методом Гаусса:

-2 4 3 5 ~ -2 4 3 5 ~ -2 4 3 5

-2 6 4 8 0 2 1 3 0 2 1 3

-8 18 13 23 0 2 1 3 0 0 0 0

-6 20 13 27 0 8 4 12 0 0 0 0

По виду этой матрицы заключаем, что система совместная и неопределенная. Система, соответствующая полученной матрице, имеет вид:

Выберем в качестве свободной переменную x3 и перенесем слагаемые с x3 в правую часть.

Решая эту систему, находим:

Получили общее решение системы.

Базисное решение системы. Полагаем x3=0, тогда

Найдем еще какое-нибудь решение системы. Пусть x3=1, тогда:

Задача 26.

Решить графически задачу линейного программирования.

Z=4x1+x2max

Решение:

Решим задачу графическим методом. Для этого составим уравнения граничных прямых и построим их в одной системе координат.

I. 2x1+x2=8

x1 0 8

x2 4 0

II. 2x1-x2=4

x1 2 3

x2 0 2

III. x1+2x2=2

x1 0 2

x2 1 0

Каждая из прямых делит плоскость на две полуплоскости. На основе знаков неравенств определяем, что область допустимых решений – это многоугольник ABCD. Строим вектор (4;1) и прямую 4x1+x2=0. Перемещаем прямую по направлению вектора. Точкой выхода из области допустимых решений является точка C. Ее координаты определяются как пересечение прямых, заданных уравнениями 1 и 2:

Т.е. точка C имеет координаты C(3;2). Найдем максимальное значение целевой функции:

Zmax=4x1+x2=43+2=14

Задача 37.

На трех базах, имеется груз в количестве 270, 300, 230 единиц. Этот груз нужно перевезти в пять, пунктов в количестве 170, 110, 200, 140, 180 единиц соответственно. Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов :

Спланировать перевозки так, чтобы их общая стоимость была минимальной.

Решение:

Запишем данные задачи в виде матрицы перевозок.

bj

ai 1 2 3 4 5

170 110 200 140 180

1 270 25 12 7 18 10

2 300 35 13 12 15 3

3 230 30 16 11 25 16

Проверим, является ли задача закрытой:

=270+300+230=800

=170+110+200+140+180=800

=,  транспортная задача закрытая.

Заполним матрицу перевозок методом минимального тарифа.

bj

ai 1 2 3 4 5 i

170 110 200 140 180

1 270 25 70 12 200 7 18 10 0

2 300 35 40 13 12 80 15 180 3 1

3 230 170 30 16 11 60 25 16 11

j 19 12 7 14 2

Стоимость перевозок при таком плане

Z=1270+7200+1340+1580+3180+30170+2560=11100 тыс. руб.

Проверим план на оптимальность методом потенциалов. Для этого найдем потенциалы строк и столбцов. Составим систему уравнений для заполненных клеток.

Пусть 1=0, тогда 2=1

3=11

1=19

2=12

3=7

4=14

5=2

Проверим на оптимальность пустые клетки:

клетка (1;1): 0+19<25

клетка (1;4): 0+14<18

клетка (1;5): 0+2<10

клетка (2;1): 1+19<35

клетка (2;3): 1+7<12

клетка (3;2): 11+12>16

клетка (3;3): 11+7>11

клетка (3;5): 11+2<16

Выберем в качестве неоптимальной клетку (3;3) и перейдем к следующей матрице перевозок.

bj

ai 1 2 3 4 5 i

170 110 200 140 180

1 270 25 110 12 160 7 18 10 0

2 300 35 13 12 120 15 180 3 -6

3 230 170 30 16 40 11 20 25 16 4

j 26 12 7 21 9

Найдем потенциалы.

Пусть 1=0, тогда 2=-6

3=4

1=26

2=12

3=7

4=21

5=9

Проверим на оптимальность пустые клетки:

клетка (1;1): 0+26>25

клетка (1;4): 0+21>18

клетка (1;5): 0+9<10

клетка (2;1): -6+26<35

клетка (2;2): -6+12<13

клетка (2;3): -6+7<12

клетка (3;2): 4+12=16

клетка (3;5): 4+9<16

Выберем в качестве неоптимальной клетку (1;4) и перейдем к следующей матрице перевозок.

bj

ai 1 2 3 4 5 i

170 110 200 140 180

1 270 25 110 12 140 7 20 18 10 0

2 300 35 13 12 120 15 180 3 -3

3 230 170 30 16 60 11 25 16 4

j 26 12 7 18 6

Найдем потенциалы.

Пусть 1=0, тогда 2=-3

3=4

1=26

2=12

3=7

4=18

5=6

Проверим на оптимальность пустые клетки:

клетка (1;1): 0+26>25

клетка (1;5): 0+6<10

клетка (2;1): -3+26<35

клетка (2;2): -3+12<13

клетка (2;3): -3+7<12

клетка (3;2): 4+12=16

клетка (3;4): 4+18<25

клетка (3;5): 4+6<16

Выберем в качестве неоптимальной клетку (1;1) и перейдем к следующей матрице перевозок.

bj

ai 1 2 3 4 5 i

170 110 200 140 180

1 270 140 25 110 12 7 20 18 10 0

2 300 35 13 12 120 15 180 3 -3

3 230 30 30 16 200 11 25 16 5

j 25 12 6 18 6

Найдем потенциалы.

Пусть 1=0, тогда 2=-3

3=5

1=25

2=12

3=6

4=18

5=6

Проверим на оптимальность пустые клетки:

клетка (1;3): 0+6<7

клетка (1;5): 0+6<10

клетка (2;1): -3+25<35

клетка (2;2): -3+12<13

клетка (2;3): -3+6<12

клетка (3;2): 5+12>16

клетка (3;4): 5+18<25

клетка (3;5): 5+6<16

Выберем в качестве неоптимальной клетку (3;2) и перейдем к следующей матрице перевозок.

bj

ai 1 2 3 4 5 i

170 110 200 140 180

1 270 170 25 80 12 7 20 18 10 0

2 300 35 13 12 120 15 180 3 -3

3 230 30 30 16 200 11 25 16 4

j 25 12 7 18 6

Найдем потенциалы.

Пусть 1=0, тогда 2=-3

3=4

1=25

2=12

3=7

4=18

5=6

Проверим на оптимальность пустые клетки:

клетка (1;3): 0+7=7

клетка (1;5): 0+6<10

клетка (2;1): -3+25<35

клетка (2;2): -3+12<13

клетка (2;3): -3+7<12

клетка (3;1): 4+25<30

клетка (3;4): 4+18<25

клетка (3;5): 4+6<16

Условие оптимальности выполняется для всех пустых клеток, поэтому план оптимальный. Стоимость перевозок при таком плане минимальна и равна:

Zmin=25170+1280+1820+15120+3180+1630+11200=10590 тыс. руб.

Задача 45.

Составить экономико-математическую модель. Найти решение задачи линейного программирования при помощи средств Excel на ПК.

При подкормке посева нужно внести на 1 га почвы не менее 10 ед. химического вещества А, 25 ед. вещества Б, 20 ед. вещества В. Сельскохозяйственное предприятие закупает комбинированные удобрения четырех видов (I, II, III, IV). В таблице указаны содержание химических веществ и цена за единицу массы каждого вида удобрений. Минимизировать расходы по закупке необходимого количества удобрений.

Химическое вещество Содержание вещества в единице массы удобрения

I II III IV

А 1 5 2 1

Б 12 3 3 2

В 4 4 2 2

Цена 5 3 2 3

Решение:

Пусть x1, x2, x3, x4 – количество комбинированных удобрений каждого вида. Очевидно, что x10, x20, x30, x40.Составим ограничения по каждому химическому веществу:

А: x1+5x2+2x3+x410

Б: 12x1+3x2+3x3+2x425

В: 4x1+4x2+2x3+2x420

Требование минимизации затрат:

f=5x1+3x2+2x3+3x4min

Требуется найти x1, x2, x3, x4, минимизирующие целевую функцию и удовлетворяющую указанным ограничениям, т.е. решить задачу линейного программирования:

f=5x1+3x2+2x3+3x4min

Решим эту задачу с помощью Excel. Вводим в ячейки таблицы исходные данные:

A B C D E F G

1 1 5 2 1 0 10

2 12 3 3 2 0 25

3 4 4 2 2 0 20

4 5 3 2 3

5

6 x1 x2 x3 x4 f

7 0 0 0 0 0

8

9

10

В ячейках E1-E3 и E7 введены формулы.

E1: =СУММПРОИЗВ(A1:D1;A7:D7)

E2: =СУММПРОИЗВ(A2:D2;A7:D7)

E3: =СУММПРОИЗВ(A3:D3;A7:D7)

E7: =СУММПРОИЗВ(A7:D7;A7:D7)

Затем даем команду Сервис/Поиск решения:

Задаем следующие параметры:

в поле «Установить целевую ячейку»: $E$7

минимальное значение

в поле «Изменяя ячейки»: $A$7:$D$7

Далее задаем ограничения:

$A$7:$D$70

$E$1:$E$3$F$1:$F$3

Затем нажимаем на кнопку «Выполнить».

Получаем ответ: x1=10/9, x2=35/9, x3=0, x4=0, fmin=155/9 (ден. ед.)