лекции(II курс)

4.4. Линейная корреляционная зависимость.

Пусть по виду эмпирической линии регрессии сделано предположение о нелинейной функциональной зависимости между переменными x и y, тогда корреляционные уравнения (1) и (2) примут вид

y −				= ρy=x(x −			),	(1′)
	y				x
x −				= ρx=y(y −			),	(2′)
		x				y

ãäå x è y общие средние переменных X è Y . Коэффициент ρy=x−коэффициент регрессии y/x и равен

ρy=x =			−				=		−
	xy			xy				xy		xy	,
		x2	−			2			σx2
				x
Коэффициент ρx=y−коэффициент регрессии x/y и равен
ρx=y =			−				=		−		.
	xy			xy				xy		xy
		y2 −			2				σy2
				y

Свойства коэффициента регрессии.

1)коэффициенты регрессии y/x è x/y имеют одинаковые знаки;

2)ρy=x показывает на сколько единиц в среднем измениться переменная y при увели- чении переменной x на 1 единицу;

3)ρx=y показывает на сколько единиц в среднем измениться переменная x при увели-

чении переменной y на 1 единицу;

4) Коэффициент ρy=x является угловым коэффициентом прямой регрессии y/x, а коэффициент ρx=y является угловым коэффициентом прямой регрессии x/y.

4.5. Коэффициент корреляции и его свойства.

Коэффициент корреляции число, равное среднему геометрическому из коэффициентов регрессии и имеющее их знак.

r = ±√ρx=yρy=x.

Свойства коэффициента корреляции.

1) Абсолютная величина коэффициента корреляции не превосходит 1.

|r| ≤ 1.

2) Åñëè r = 0, то связь между x и y отсутствует, в этом случае прямые регрессии

параллельны осям координат.

3) Åñëè r = ±1, то связь между x и y точно линейная, в этом случае прямые регресcии

совпадают.

4) Коэффициент корреляции r является показателем тесноты связи, чем ближе, тем теснее, т.е. |r| → 1.

5)Коэффициент корреляции является показателем, направлением связи: если r > 0, òî

связь между переменными прямая, т.е. с ростом одной величины x другая в среднем так же возрастает, если r < 0, то связь между переменными обратная.

81

Пример: В таблице дано распределение 100 рабочих по стажу работы:

	7,5	12,5	17,5	22,5	27,5
X Y	5-10	10-15	15-20	20-25	25-30	Итого:
2
1-3	11	4	-	-	-	15
4
3-5	9	8	3	-	-	20
6
5-7	6	9	9	7	1	32
8
7-9	-	2	9	9	2	22
10
9-11	-	-	4	4	3	11
Итого:	26	23	25	20	6	100

1)Необходимо вычислить групповые средние и построить эмпирические линии регрес-

ñèè.

2)Найти уравнения прямых регрессии и построить их графики на том же чертеже.

3)Вычислить коэффициент корреляции, сделать вывод о тесноте и направлении связи x и y.

4)Оценить среднюю производительность рабочего со стажем 7 лет, используя соответ-

ствующее уравнение прямой регрессии.

Решение.

1) Вычислим групповые средние для xi:

x

= 2;

=

7, 5 · 11 + 12, 5 · 4

≈

8, 83;

1

y

1

15

x2 = 4,

2 ≈ 11;

x3 = 6,

3 ≈ 15, 6;

y

y

x4 = 8,

4 ≈ 20;

x5 = 10,

5 ≈ 22, 1;

y

y

Для удобства систематизируем вычисленные групповые в таблице:

xi			2	4	6	8	10
		i
	y		8,83	11	15,6	20	22,1

Вычислим групповые средние для yj:

y

= 7, 5;

=

2 · 11 + 4 · 9 + 6 · 6

≈

3, 6;

1

x

1

15

y2 = 12, 5,

2 ≈ 4, 8;

y3 = 17, 5,

3 ≈ 7, 12;

x

x

y4 = 22, 5,

4 ≈ 7, 7; y5 = 27, 5,

5 ≈ 8, 7;

x

x

Для удобства систематизируем вычисленные групповые в таблице:

	yj		7,5	12,5	17,5	22,5	27,5
		j
	x		3,6	4,8	7,12	7,7	8,7

По данным двух таблиц, построим эмпирические линии регрессии

82

Yj
22,8
22,1
15,6				!"ямая "&'"&((ии y/x
11
8,83
8,4
				Xi
2	4	6	8	10
Xj
10,74
8,7				!"ямая "&'"&((ии x/y
7,7
7,12

4,8

3,6

2,74

Yj

7,5 12,5 17,5 22,5 27,5

2) Чтобы найти уравнения прямых линий регрессии, составим вспомогательные таблицы:

										xi				nxi				xi · nxi			xi2 · nxi								i						xinxi			i
																											y										y
										2			15				30				60				8,83										264,9
								4					20				80				320				11										880
								6					32				192				1152				15,6										2995,2
								8					22				176				1408				20										3520
										10			11				110				1100				22,1										2431
Из таблицы находим										∑			100				588				4040				-										10091,1
					588								4040									2													2 = 40, 4 − (5, 88)2 ≈ 5, 8.
	x		=				= 5, 88; x2						=						= 40, 4; σ				= x2 −										x
					100											100						x
										yj				nyj				yj · nyj			yj2 · nyj											j				yjnyj				j
																														x									x
									7,5				26				19,5				146,25					3,6										702
									12,5				23				287,5				3593,75					4,8										1380
									17,5				25				437,5				7656,25					7,12										3115
									22,5				20				450				10125					7,7										3465
									27,5				6				165				4537,5					8,7										1435,5
									∑				100				1535				26058,75					-										10097,5
Из таблицы находим
					1535												26058, 75														2			= 260, 6 − (15, 35)2 ≈ 25.
				=				= 15, 35;						y2 =							≈ 260, 6;								σ
		y
					100												100														y

83

Кроме того, найдем xy по формуле

	∑i	∑
5		5
xy	=	xi · yj · nij

=1 j=1

ïðи этом обходим все заполненные клетки корреляционной таблицы, в итоге получим xy = 10090/100 ≈ 101.

Иногда бывает проще в качестве величины xy взять наименьшую из величин

∑

∑j

l

m

xinxi

y

i èëè

yjnyj

x

j

i=1

=1

Далее, находим коэффициенты ρx=y è ρy=x

=

−

·

=

101 − 5, 88 · 15, 35

ρ

xy

x

y

≈

1, 8.

y=x

σ

2

5, 8

x

=

−

·

=

101 − 5, 88 · 15, 35

ρ

xy

x

y

≈

0, 4.

x=y

σ

2

25

y

Тогда уравнения прямых регрессий принимают вид

y −

= ρy=x(x −

),

y = 1, 8x + 4, 8.

y

x

x −

= ρx=y(y −

),

x = 0, 4y − 0, 26.

x

y

Построим их на тех же графиках, что и эмпирические линии регрессии. Составим вспомогательные таблицы

x	y
2	8,4
10	22,8

y	x
7,5	2,74
27,5	10,74

√

3) Вычислим коэффициент корреляции r = 1, 8 · 0, 4 = 0, 8. Связь между переменны-

ми достаточно сильная, прямая.

4) Используем уравнение y = 1, 8x + 4, 8. Подставим в него вместо x заданный стаж рабочего, т.е. 7, получим

y = 1, 8 · 7 + 4, 8 = 17, 4 дет./ч средняя производительность.

84

Линейное программирование.

Математическое программирование это прикладная отрасль математики, которая является теоретической основой решения задач оптимального планирования.

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

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

Тема 1. Общая постановка задачи линейного программирования.

Понятие об экономико математических моделях, их классификация. Общая задача линейного программирования. Сведение ее к канонической и стандартной форме.

1.1. Экономико математическая модель.

Экономико математическая модель математическое описание исследуемого экономического процесса или объекта.

В настоящее время разработано большое количество моделей, которое можно класси-

фицировать по различным признакам:

1) Задача об использовании ресурсов или о планировании производства.

Пусть некоторое предприятие выпускает 2 вида продукции P1 è P2, используя при этом сырье 4 видов: S1, S2, S3, S4. В таблице представлены затраты сырья на выпуск 1

единицы продукции каждого вида, запасы сырья, прибыль, стоимость каждой единицы продукции:

Вид ресурса	Запас ресурса	Число единиц ресурса, затрачиваемых
		на изготовление единицы продукции
		P1	P2
S1	18	1	3
S2	16	2	1
S3	5		1
S4	21	3
Прибыль		2	3

Необходимо составить такой план производства продукции при котором прибыль от ее реализации будет максимальной.

Составим экономико математическую модель задачи: обозначим x1−план выпуска продукции P1; x2−план выпуска продукции P2.

Для их изготовления потребуется (x1 +3x2) единиц ресурса S1, 2x1 +x2 единиц ресурса S2, x2 ресурса S3, 3x1 ресурса S4. Так как потребление ресурсов S1, S2, S3, S4 не должно превышать их запасов, соответственно 10, 4, 20, 7 единиц то связь между потреблением ресурсов и их запасами выразится системой неравенств:

	x1 + 3x2		18;
		≤
	2x1 + x2	≤	16;	(1.1)
	4x2≤		5;
	3x1	≤ 21.

85

По смыслу задачи переменные

x1 ≥ 0, x2 ≥ 0.

(1.2)

Суммарная прибыль F составит 2x1 руб. от реализации продукции P1 è 3x2 ðóá. îò реализации продукции P2, ò.å.

F = 2x1 + 3x2 → max.

(1.3)

Итак, экономико математическая модель задачи: найти такой план выпуска про-

дукции X = (x1, x2), удовлетворяющий системе (1.1) и условию (1.2), при котором функция (1.3) принимает максимальное значение.

Задачу легко обобщить на случай выпуска n видов продукции с использованием m

видов ресурсов.

Обозначим, xj, (j = 1, 2, . . . , n)−число единиц продукции Pj, запланированной к производству; bi, (i = 1, 2, . . . , m)−запас ресурса Si, aij−число единиц ресурса Si, затрачи- ваемого на изготовление единицы продукции Pj (числа aij часто называют технологи- ческими коэффициентами); cj−прибыль от реализации единицы продукции Pj.

Тогда экономико математическая модель задачи об использовании ресурсов в общей постановке примет вид:

найти такой план X = (x1, x2, . . . , xn) выпуска продукции, удовлетворяющей

системе

	a11x1 + a12x2 + . . . + a1nxn
	a21x1	+ a22x2 + . . . + a2nxn
		. . . . . . . . . . . .
		+ am2x2 + . . . + amnxn
am1x1

≤b1;

≤b2;

≤bm.

и условию

x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0,

при котором функция

F = c1x1 + c2x2 + . . . + cnxn

принимает максимальное значение.

2) Задача составления рациона (задача о диете, задача о смесях).

Имеется два вида корма I и II, содержащие питательные вещества (витамины) S1, S2 è S3. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице

Питательное	Необходимый	Число единиц питательных веществ
вещество	минимум пита-		в 1 кг корма
(витамин)	тельных веществ	I		II
S1	9	3		1
S2	8	1		2
S3	12	1		6

Стоимость 1 кг корма I и II соответственно равна 4 руб. и 6 руб.

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

Составим экономико математическую модель задачи.

Обозначим x1, x2−количество кормов I и II, входящих в дневной рацион. Тогда этот рацион, согласно таблице, будет включать (3x1 + x2) единиц питательного вещества S1,

86

X = (x1, x2, . . . , xn), удовлетворяющий

найти такой рацион

(x1 +2x2) единиц вещества S2 è (x1 +6x2) единиц питательного вещества S3. Так как содер- жание питательных веществ S1, S1, S3 в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим систему неравенств:

	3x	+ x2	≥	9;
	x1	1+ 2x2		8;	(1.4)
	x1 + 6x2		≥	12.
Кроме того, переменные			≥
	x1 ≥ 0, x2 ≥ 0.				(1.5)
Общая стоимость рациона составит (в руб.)
	F = 4x1 + 6x2.				(1.6)

Итак, экономико математическая модель задачи: составить дневной рацион X =

(x1, x2), удовлетворяющий системе (1.4) и условию (1.5), при котором функция (1.6) принимает минимальное значение.

Для формулировки задачи в общем виде обозначим: xj(j = 1, 2, . . . , n)−число единиц корма n−ãî âèäà; bi(i + 1, 2, . . . , m), −необходимый минимум содержания в рационе питательного вещества Si; aij− число единиц питательного вещества Si в единице корма j−ãî âèäà; cj− стоимость единицы корма j−го вида. Тогда экономико математическая модель задачи примет вид:

системе

	a11x1 + a12x2 + . . . + a1nxn		b1;
a21x1 + a22x2 + . . . + a2nxn			≥ b2;
. . . . . . . . . . . .			≥
		+ . . . + amnxn ≥ bm.
am1x1 + am2x2

и условию

x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0,

при котором функция

F = c1x1 + c2x2 + . . . + cnxn

принимает максимальное значение.

3)Задача об использовании мощностей (о загрузке оборудования).

4)Задача о раскрое материалов.

5)Транспортная задача(o наиболее оптимальном распределении груза между по-

ставщиками и потребителями).

1.2. Общая задача линейного программирования.

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

Дана система m линейных уравнений и неравенств с n переменными

a11x1 + a12x2 + . . . + a1nxn

b1;

a21x1 + a22x2 + . . . + a2nxn

≤ b2;

≤

. . .

ak1x1 + ak2x2 + . . . + aknxn

≤

bk;

(1.7)

a

x + a

x + . . . + a

x = b

;

k+11 1

k+12

2

k+1n

n

k+1

. . .

a

x

+ a

x

+ . . . + a

x

= b

;

m1

m2

n

m

1

2

mn

87

и линейная функция

F = c1x1 + c2x2 + . . . + cnxn.	(1.8)
Необходимо найти такое решение системы X = (x1, x2, . . . , xj, . . . , xn) ãäå
xj ≥ 0 (j = 1, 2, . . . , l; l ≤ n),	(1.9)

при котором линейная функция F принимает оптимальное (т.е. максимальное или

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

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

Система (1.7) называется системой ограничений, а функция F (x)−линейной функцией,

линейной формой, целевой функцией или функцией цели.

Оптимальным решением(èëè оптимальным планом) задачи ЛП называется решение X = (x1, x2, . . . , xj, . . . , xn) системы ограничений (1.7), удовлетворяющее условию

(1.9), при котором целевая функция (1.8) принимает оптимальное значение.

Если система функциональных ограничений (1.7) состоит только из неравенств, то задача ЛП называется стандартной, если система функциональных ограничений состоит только из уравнений, то канонической, а если система функциональных ограничений

состоит из неравенств и уравнений, то задача ЛП называется общей.

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

Замечание. Если неравенство имеет вид ≤, то дополнительная неотрицательная переменная вводится со знаком "+". Если неравенство имеет вид ≥, то дополнитель-

ная переменная вводится со знаком "−".

Например: систему функциональных ограничений (1.1), которая является стандартной, можно записать в каноническом виде

		x1 + 3x2 + x3 = 18;
		2x1 + x2 + x4 = 16;
x2 + x5 = 5;
					0
		3x1 + x6 = 21.		6 ≥
x	,	x	, , . . . , x			.
1		2

Тема 2. Элементы линейной алгебры и геометрии выпуклых множеств.

Решение системы m уравнений с n неизвестными (понятие базисного допустимого ре-

шения). Выпуклые множества точек. Геометрический смысл решений неравенств, уравнений и их систем. Свойства задачи ЛП.

2.1. Решение систем m уравнений с n неизвестными.

Рассмотрим систему m линейных уравнений с n переменными

a11x1 + a12x2 + . . . + a1jxj + . . . + a1nxn = b1;

a21x1 + a22x2 + . . . + a2jxj + . . . + a2nxn = b2;

. . . . . .

(2.1)

a

i1

x

1

+ a

i2

x

2

+ . . . + a

ij

x

j

+ . . . + a

in

x

n

= b

;

i

. . . . . .

am1x1 + am2x2 + . . . + amjxj + . . . + amnxn = bn.

88

или в краткой записи

∑n

aijxj = bi, (i = 1, 2, . . . , m).

j=1

В задачах линейного программирования представляют интерес системы, в которых ранг r матрицы системы A = (aij) или, что то же самое, максимальное число независимых уравнений системы r меньше числа переменных, т.е. r < n.

Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные n−m переменных называются неосновными (или свободными).

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

переменных не превосходит Cnm.

Пример: Найти все возможные группы основных переменных в системе

{

x1 − x2 − 2x3 + x4 = 0 ;

2x1 + x2 + 2x3 − x4 = 0 .

Решение: Общее число групп основных переменных не более чем C42 = 4 · 3/2 = 6, т.е. возможные группы основных переменных: x1, x2; x1, x3; x1, x4; x2, x3; x2, x4; x3, x4. Выясним, могут ли быть основными переменные x1, x2. Так как определитель матрицы из коэффициентов при этих переменных

	2	1		̸
	1	−1		= 3 = 0,

òî x1, x2 могут быть основными переменными. Рассуждая аналогично, найдем, что могут быть основными переменные x1, x3; x1, x4, но не могут быть основными x2, x3; x2, x4; x3, x4, так как в трех последних группах переменных соответствующие определители равны нулю. Например, для переменных x3, x4

	2	−	1
	−2				= 0.

Теорема 2.1. Если для системы m линейных уравнений с n переменными (m < n) ранг матрицы коэффициентов при переменных равен m, т.е. существует хотя бы одна

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

шение системы.

Пример: Решить систему уравнений

{

x1 − 3x2 + x3 = −4 ; 2x1 + x2 − x3 = 5 .

Т. к. уравнений 2, то основных переменных то же 2, а свободных 3 − 2 = 1. Выясним, какие основные, какая свободная:

= 1 −3 = 7 ≠ 0 2 1

89

значит x1, x2− основные, а x3− свободная. Чтобы решить систему,выразим основные переменные через свободную

{	x1 − 3x2 = −4 − x3 ;
	2x1 + x2 = 5 + x3 .

Применим метод Крамера, для этого составим 1, 2:

1 =

−4 − x3

1

= 11 + 2x3,

2

=

1 −4 − x3

= 13 + 3x3.

5 + x3

2

2 5 + x3

Следовательно:

1 =

11

7

3

x1 =

= 11/7 + 2/7 x3;

+ 2x

2 =

=

7

= 13 7 + 3 7 3

2

13 + 3x3

x

/

/ x .

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

Базисным решением системы m линейных уравнений с n переменными называется

решение, в котором все n − m неосновные (свободные) переменные равны нулю.

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

решения, у которых все компоненты решения неотрицательны.

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

Заметим, что в решенной системе уравнений, первое же базисное решение допустимо:

X1 = (	11	,	13	, 0).
	7		7

Заметим, что система (2.1) имеет бесконечно много решений, из них базисных решений существует конечное число, не превосходящее Cnm.

2.2.Выпуклые множества точек.

Âшкольном курсе математики выпуклыми назывались многоугольники, целиком расположенные по одну сторону от прямых, на которых лежат их стороны.

C

B B M

D D

A M A

N

C N

E E

F F

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

за определение выпуклого множества точек.

Определение. Множество точек называется выпуклым, если оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки.

90