Линейная алгебра и математическое программирование

ЦЕНТРОСОЮЗ РОССИЙСКОЙ ФЕДЕРАЦИИ

СИБИРСКИЙ УНИВЕРСИТЕТ ПОТРЕБИТЕЛЬСКОЙ КООПЕРАЦИИ

Контрольная работа

ЛИНЕЙНАЯ АЛГЕБРА И МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Новосибирск 2009

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

8.

Решение

 

Используя формулы Крамера

Вычислим определитель системы линейных уравнений

Д =  = (-4)(-5)1 + 3(5)3 + (-2)(-2)(-4) – (-2)(-5)(3) – (-4)(5)(-4) -3(-2)(1) =

= 20 + 45 – 16 – 30 – 80 + 6 = - 55

Так как Д # 0, то система линейных уравнений невырожденная и имеет единственное решение.

Вычислим определители Д1, Д2, Д3

Д1 =  = (31)(-5)1 + (-6)(5)3 + (-11)(-2)(-4) – (-11)(-5)(3) – (31)(5)(-4) – (-6)(-2)(1) = - 155 – 90 – 88 – 165 + 620 – 12 = 110

Д2 =  = (-4)(-6)1 + 3(-11)3 + (-2)(31)(-4) – (-2)(-6)(3) – (-4)(-11)(-4) – 3(31)(1) = 24 – 99 + 248 – 36 + 176 - 93 = 220

Д3 =  = (-4)(-5)(-11) + (3)(5)31 + (-2)(-2)(-6) – (-2)(-5)(31) – (-4)(5)(-6) – 3(-2)(-11) = - 220 + 465 – 24 – 310 – 120 – 66 = - 275

Отсюда, X₁ =  =  = - 2, X₂ =  =  = - 4, X₃ =  =  = 5

 

Проверка:

 ,

что подтверждает правильность найденного решения системы линейных уравнений.

·                   Решение матричным способом

A * X = B X =  * В

 =  *  * . Д =  = - 55

здесь  - алгебраические дополнения, которые и вычислим:

A11 = = (-5)1 – 5(-4) = 15

A12 = = -(3(1) –(-2)(-4)) = 5

A13 = = 3(5) – (-2)(-5) = 5

A21 = = -( (-2)1 – 5(3) ) = 17

A22 =  = (-4)1 – (-2)3 = 2

A23 = = - ( (-4)5 – (-2)(-2) ) = 24

A31 = = (-2)(-4) – (-5)3 = 23

A32 = = - ( (-4)(-4) – 3(3) ) = - 7

A33 = = (-4)(-5) – 3(-2) = 26

 =  *  *  =   

=  =  =

Ответ: X₁ = - 2, X₂ = - 4, X₃ = 5

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

18.

 

Решение

Составим расширенную матрицу (А|B)

Приведем матрицу (А|B) к ступенчатому виду.

Оставив без изменения первую строку и умножая её соответственно на -3, -5, 4, прибавим полученное к строкам 2, 3 и 4

Оставив без изменения первую и вторую строки и умножая последнюю соответственно на -3, -5, прибавим полученное к строкам 3 и 4

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

Так как эта система состоит из двух уравнений, но содержит три переменные, одну из переменных можно выбрать произвольно, например, положим х₃. Перенося слагаемые с х₃ в правую часть, получим систему

Решая ее, находим: x₂ = , x₁ =  где х₃ – любое действительное число.

Общим решением системы линейных алгебраических уравнений называется такая их запись, в которой часть ее переменных, называемых базисными, выражены через оставшиеся переменные, называемые свободными. В данном примере переменные х₁ и х₂ – базисные, а х₃ – свободная. И запись

называется общим решением системы.

Частные решения получаются из общего, если задать произвольно свободные переменные. Например, если , то X₁ = 1, X₂ = 2. Это частное решение системы.

Базисным решением системы линейных алгебраических уравнений называют такое частное решение, при котором свободные переменные равны нулю. Например, если , то X₁ = , X₂ = . Это базисное решение системы линейных алгебраических уравнений

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

23.

Решение

Построим область допустимых решений. Для этого наносим на чертеж границы области допустимых решений. Каждое из неравенств системы ограничений задачи линейного программирования определяет прямую, которая делит всю числовую плоскость на две полуплоскости. Знак - будет обозначать ту полуплоскость, которая соответствует выполнению неравенства. Область допустимых решений представляет собой многоугольник ABCDE.

 

X₂

4х₁ + х₂ = 0

5 X₁ ≤ 3

4 X₁ - X₂ ≤ 2

 B(0,3) 3 C(3, )

2

1 D(3,1) X₁ + 4 X₂ ≤ 12

E(2,0) X₂ ≥ 0

A(0,0) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 X₁

 X₁ ≥ 0

Найдем координаты точек A, B, C, D, E. Для этого последовательно решим несколько систем уравнений, образуемых из неравенств системы ограничений задачи линейного программирования.

Для точки А:

 Отсюда,  , т.е. А(0,0).

Для точки В:  отсюда, , Х₂ = 3, т.е. В(0,3).

Для точки C:  отсюда, , Х₂ =  , т.е. С(3,).

Для точки D:  отсюда, , Х₂ = 1, т.е. D(3,1).

Для точки E:  отсюда, , Х₁ = 2, т.е. E(2,0).

Координаты точек: A(0,0) , B(0,3), C(3, ), D(3,1), E(2,0)

В соответствии с коэффициентами целевой функцией

z = 4 x₁ + x₂  max

построим вектор  ( 4, 1) и прямую 4х₁ + х₂ = 0.

Перемещаем прямую по направлению вектора. Точкой выхода из области допустимых решений является точка С(3,).

В точке С(3,) и будет оптимальное решение (максимальное), то есть при х₁ = 3; х₂ =  значение целевой функции будет максимальным

Zmax = 4 * 3 +  = 14.

 

Проверка:

В соответствии с одной из теорем теории линейного программирования линейная функция z = 4 x₁ + x₂ достигает максимального значения в вершинах многогранника, т.е. в точках A(0,0) , B(0,3), C(3, ), D(3,1), E(2,0).

Вычислим значения z = 4 x₁ + x₂ в этих точках:

·                   z (A(0,0)) = 4*0 + 0 = 0

·                   z (B(0,3)) = 4*0 + 3 = 3

·                   z (D(3,1)) = 4*3 + 1 = 13

·                   z (E(2,0)) = 4*2 + 0 = 8

·                   z (C(3, )) = 4*3 + = 14. , что и подтверждаем максимальность значения целевой функции.

Задачи 31–40. На трех базах А₁, А₂, А₃ имеется однородный груз в количестве а₁, а₂, а₃ единиц. Этот груз нужно перевезти в пять пунктов В1, В2, В3, В4, В5 в количестве b1, b2, b3, b4, b5 единиц соответственно. Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов С:

.

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

 40.

Решение:

Вычислим y =  = 350 + 400 + 250 = 1000,

 к =  = 175 + 225 + 240 + 160 + 200 = 1000, так как к = y , то решаемая транспортная задача является закрытой.

Обозначим через  количество груза, перевозимого из пункта  в пункт .

Рассмотрим закрытую транспортную задачу. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения.

Математическая модель закрытой транспортной задачи имеет вид

при ограничениях ,

,

X ij ≥ 0 , i =  j =  , m = 5.

Оптимальным решением задачи является матрица Xopt = ( Xij )3x5, удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

Условия задачи и ее исходное решение будем записывать в распределительную таблицу. Клетки, в которые поместим грузы, называются занятыми, остальные клетки – незанятыми, или пустыми. В верхнем правом углу каждой клетки будем записывать тарифы. Существует несколько способов нахождения исходного решения.

Рассмотрим один из них – метод минимального тарифа (элемента). Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок Cij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей.

Процесс распределения продолжается до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m + n -1 = 5 + 3 – 1 = .

В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми.

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

Найдем исходное решение по методу минимального тарифа. Для этого составим следующую распределительную таблицу:

bi  ai		1	2	3	4	5
		175	225	240	160	200
1	350	5 175	15 175	18	16	8
2	400	6	10 40	15	6 160	4 200
3	250	25	20 10	10 240	15	18

Число занятых клеток в таблице, приведенной выше, равно m + n – 1 = 5 + 3 – 1 = 7, то есть условие невырожденности выполнено. Получили исходное решение, которое запишем в виде матрицы

Х₁ = 

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

f₁ = 175 * 5 + 175 * 15 + 40 * 10 + 160 * 6 + 200 * 4 + 10 * 20 + 240 * 10 = 8260.

Проверим найденное решение транспортной задачи на оптимальность Найденное исходное решение проверяется на оптимальность методом потенциалов по следующему критерию: если решение транспортной задачи является оптимальным, то ему соответствует система m+n ( 5 + 3 = 8 ) действительных чисел  и , удовлетворяющих условиям  для занятых клеток и  – для свободных клеток. Числа  и  называются потенциалами. В распределительную таблицу добавляют столбец  и строку .

Потенциалы  и  находят из равенства , справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например , тогда остальные потенциалы определяются однозначно. Так, если известен потенциал , то ; если известен потенциал , то .

Обозначим . Эту оценку называют оценкой свободных клеток. Если , то опорное решение является оптимальным. Если хотя бы одна из оценок , то решение не является оптимальным и его можно улучшить, перейдя от одного решения к другому.

Проверим найденное решение на оптимальность, добавив в распределительную таблицу, приведенную ниже, столбец  и строку .

Полагая , запишем это значение в последнем столбце
таблицы.

bi  ai		1	2	3	4	5
		175	225	240	160	200	𝛼i
1	350	5  175	15 175	18	16	8	0
2	400	6	10 40	15	6 160	4 200	-5
3	250	25	20 10	10 240	15	18	0
	𝛽i	5	15	10	11	9

Для клетки (1,1) : 1 + 1 = 5, 1 = 0, 1 = 5

Для клетки (1,2) : 1 + 2 = 15, 1 = 0, 2 = 15

Для клетки (2,2) : 2 + 2 = 10, 2 = -5, 2 = 15

Для клетки (2,4) : 2 +  = 6, 2 = -5, 4 = 11

Для клетки (2,5) : 2 +  = 4, 2 = -5, 5 = 9

Для клетки (3,3) :  +  = 10, 3 = 0, 3 = 10

Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:

Δ13 = 1 + 3 – с 13 = 0 + 10 – 18 = - 8  0

Δ14 = 1 +  – с 14 = 0 + 11 – 16 = - 5  0

Δ15 = 1 +  – с 15 = 0 + 9 – 8 = 1 0

Δ21 =  +  – с 21 = -5 + 5 – 6 = -6  0

Δ23 =  +  – с 23 = -5 + 10 – 15 = -10  0

Δ31 =  +  – с 31 = 0 + 5 – 25 = -20  0

Δ34 =  +  – с 34 = 0 + 11 – 15 = -4  0

Δ35 =  +  – с 35 = 0 + 9 – 18 = -9  0

Получили одну оценку Δ15 = 1