Неопределенные системы линейных алгебраических уравнений (СЛАУ). Математические модели задач линейного программирования. Геометрический метод решения задач линейного программирования. Двойственность в задачах линейного программирования. Симплекс-метод. Математическая модель транспортной задачи. Построение опорного плана. Метод потенциалов. Транспортная задача на сети. Задача об оптимальном назначении. Основные понятия теории вероятностей. Основные задачи статистического анализа. Проверка статистических гипотез. Парная линейная регрессия. Парная нелинейная регрессия. Множественная регрессия. Проверка качества уравнения множественной регрессии.

Федеральное агентство железнодорожного транспорта Уральский государственный университет путей сообщения Кафедра «Высшая и прикладная математика» П. И. Гниломедов А. В. Мартыненко ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ Екатеринбург УрГУПС 2015 Федеральное агентство железнодорожного транспорта Уральский государственный университет путей сообщения Кафедра «Высшая и прикладная математика» П. И. Гниломедов А. В. Мартыненко ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ Конспект лекций по дисциплине «Экономико-математические методы и модели» для студентов всех форм обучения направления подготовки 38.03.01 – «Экономика» Екатеринбург УрГУПС 2015 УДК 519.852 Г56 Гниломедов, П. И. Г56 Экономико-математические методы и модели : конспект лекций / П. И. Гниломедов, А. В. Мартыненко. – Екатеринбург : УрГУПС, 2015. − 135, [1] с. Пособие предназначено для методического обеспечения курса лекций по дисциплине «Экономико-математические методы и модели» для студентов, обучающихся по ОП ВО направления 38.03.01 − Экономика. УДК 519.852 Опубликовано по решению редакционно-издательского совета университета Авторы: П. И. Гниломедов, доцент кафедры «Высшая и прикладная математика», канд. пед. наук, УрГУПС; А. В. Мартыненко, доцент кафедры «Высшая и прикладная математика», канд. физ.-мат. наук, УрГУПС Рецензент: Г. А. Тимофеева, зав. кафедрой «Высшая и прикладная математика», д-р физ.-мат. наук, УрГУПС © Уральский государственный университет путей сообщения (УрГУПС), 2015 ОГЛАВЛЕНИЕ Введение……………………………………………………………………………...4 1. Неопределенные системы линейных алгебраических уравнений (СЛАУ)…...5 2. Математические модели задач линейного программирования………………14 3. Геометрический метод решения задач линейного программирования………25 4. Двойственность в задачах линейного программирования……………………32 5. Симплекс-метод………………………………………………………………….37 6. Математическая модель транспортной задачи. Построение опорного плана. Метод потенциалов………………………………………………………………...46 7. Транспортная задача на сети……………………………………………………60 8. Задача об оптимальном назначении……………………………………………66 9. Основные понятия теории вероятностей………………………………………72 10. Основные задачи статистического анализа…………………………………..82 11. Проверка статистических гипотез…………………………………………….88 12. Парная линейная регрессия……………………………………………………97 13. Парная нелинейная регрессия………………………………………………. 107 14. Множественная регрессия……………………………………………………114 15. Проверка качества уравнения множественной регрессии………………….125 Список использованных источников…………………………………………….135 3 Введение Учебный курс «Экономико-математические методы и модели» предназначен для студентов – бакалавров всех форм обучения. Содержание данного курса ориентировано на применение математических методов к решению прикладных задач. В основу курса положены классические и современные математические теории и практика, авторские разработки коллектива кафедры «Естественнонаучные дисциплины». Цель дисциплины: Дать систематические знания о построении и исследовании математических моделей на основе теории линейного программирования и понятийного аппарата математической статистики и эконометрики. Способствовать формированию компетенций, необходимых для использования математических моделей и методов решения управленческих задач. Задачами изучения дисциплины являются: – развить логическое и алгоритмическое мышления студентов; – воспитать культуру применения математических и информационных технологий для решения прикладных задач аналитическими и вычислительными методами; – освоить математические методы исследования реальных процессов и явлений. Изучение дисциплины направлено на формирование общекультурных и профессиональных компетенций. В результате изучения дисциплины студент должен: 1. знать основные понятия линейного программирования и эконометрики; методы сбора данных, характеризующих деятельность хозяйствующих субъектов; экономические и социально-экономические показатели, характеризующие деятельность хозяйствующих субъектов. 2. уметь применять стандартные модели линейного программирования и эконометрики для изучения экономических явлений и процессов; собирать данные, характеризующих деятельность хозяйствующих субъектов; делать рас- 4 четы экономических и социально-экономических показателей, характеризующих деятельность хозяйствующих субъектов. 3. владеть:методами идентификации и формулирования в терминах линейного программирования и эконометрики профессиональных задач в области управления социальными и экономическими системами; методами сбора данных, характеризующих деятельность хозяйствующих субъектов; типовыми методиками расчета экономических и социально-экономических показателей, характеризующих деятельность хозяйствующих субъектов. 5 1. НЕОПРЕДЕЛЕННЫЕ СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (СЛАУ) 1.1. Неопределенные системы Пусть задана система m линейных алгебраических уравнений с n неизвестными x1, x2, …, xn       a11x1  a12 x2  ...  а1n xn  b1 , a21x1  a22 x2  ...  а2 n xn  b2 ,  am1x1  am 2 x2  ...  аmn xn  bm , (1) i  1, 2, ..., n; j  1, 2, ..., m, где aij – постоянные коэффициенты при неизвестных переменных. Решением системы линейных уравнений является множество чисел X   x1, x2 ,..., xn  , при подстановке которых в каждое из уравнений системы получается верное равенство. Часто бывает так, что число неизвестных переменных не совпадает с числом уравнений, то есть, в общем случае m  n . Такая система может быть: – несовместной – не имеющей решений; – совместной – имеющей хотя бы одно решение. Если совместная система имеет одно решение, то ее называют определенной, если более одного решения – неопределенной. Несовпадение числа неизвестных переменных с количеством уравнений (обычно m < n) является характерным признаком неопределенности системы. Основным методом решения неопределенной системы является метод Гаусса – метод последовательного исключения неизвестных посредством элементарных преобразований исходной системы. К таким преобразованиям относятся: 1. Умножение любого уравнения на число, отличное от нуля; 2. Прибавление к одному из уравнений любого другого, умноженного на любое число; 6 3. Вычеркивание из системы уравнений, у которых все коэффициенты при неизвестных и свободные члены в правой части равны нулю. Общее решение для неопределенной системы представляет собой эквивалентную систему линейно независимых уравнений, в которой часть переменных, называемых базисными выражена через другие переменные – свободные. Каждая базисная переменная входит только в одно уравнение с коэффициентом один и отсутствует в других уравнениях, остальные переменные системы будут свободными. Если во всех уравнениях системы выделены базисные переменные, то говорят, что в системе выделен единичный базис. Частным решением системы уравнений называется решение, получающиеся из общего при конкретных значениях свободных переменных. Базисным решением называется частное решение, получающееся из общего при нулевых значениях свободных переменных. Разделить переменные на базисные и свободные удобно непосредственно в системе с помощью линейных операций над уравнениями системы. Пример Решить систему линейных уравнений, найти одно общее решение, соответствующее базисное и одно частное решение  x4  5,  x1  2 x2   x4  x5  1,  2 x1  x2 3 x  x  x  x  x  6. 3 4 5  1 2 (2) Система содержит три уравнения и пять неизвестных переменных, следовательно, она не имеет единственного решения. Последовательно исключим переменную x1 из второго и третьего уравнения, переменную x2 из первого и третьего, а x3 – из первого и второго уравнений. 1. В первом уравнении коэффициент у переменной х1 равен единице, поэтому ее удобно взять в качестве первой базисной переменной. Исключим х1 из оставшихся уравнений. Для этого первое уравнение умножим на –2 и –3 и вычтем соответственно из второго и третьего уравнений 7  x4  5,  x1  2 x2  x4  5,  x1  2 x2    x4  x5  1,   3 x2  x4  x5  11, (3)  2 x1  x2 3 x  x  x  x  x  6.  5 x2  x3  4 x4  x5  21. 3 4 5  1 2  2. Исключим переменную х2 из первого и третьего уравнений. Для этого разделим второе уравнение на 3 и, умножив его сначала на –2, а затем на 5, вычтем соответственно из первого и третьего уравнений. Таким образом переменная х2 становится второй базисной переменной   x1  x4  5,  x1  2 x2   1 1 11   x2  x4  x5  ,    3 3 3   5 x2  x3  4 x4  x5  21.     x2 1 2 7  x4  x5  , 3 3 3 1 1 11  x4  x5  , 3 3 3 7 8 8 x3  x4  x5  . 3 3 3 (4) Заметим, что переменная х3 также является базисной, поскольку она содержится только в третьем уравнении с единичным коэффициентом. Выразим базисные переменные и сформируем общее решение системы 7 1 2   x1  3  3 x4  3 x5 ,  11 1 1   x2   x4  x5 , 3 3 3  8 7 8  x x x5 ,    3 4  3 3 3  (5) где х4 и х5 – свободные переменные. Соответствующее базисное решение получим, полагая свободные переменные равными нулю 7 11 8  7 11 8  x1  , x2  , x3  , x4  x5  0, или X Б1   , , , 0, 0  . 3 3 3 3 3 3  Частное решение найдем, придав какое-либо значение свободным переменным, например х4 = 1 и х5 = 1, тогда x1  10 11 7  10 11 7  , x2  , x3   , x4  x5  1, или X 1   , ,  , 1, 1  . 3 3 3 3  3 3  8 1.2. Матричная форма записи решения системы методом Гаусса Решение системы линейных уравнений удобно проводить в матричной форме, проводя аналогичные элементарные преобразования над соответствующей расширенной матрицей системы, составленной из коэффициентов при неизвестных переменных и свободных членов уравнений. Покажем нахождение общего решения в матричной форме для рассмотренной системы уравнений.  1 2 0 1 0 5    Расширенная матрица системы,  2 1 0 1 1 1  ,  3 1 1 1 1 6    (6) тогда исключение х1 из второго и третьего уравнений соответствует получению нулевых элементов во второй и третьей строках первого столбца матрицы  1 2 0 1 0 5   1 2 0 1 0 5           2 1 1 1 1 3 1 1 11    .  3 1 1 1 1 6   0 5 1 4 1 21     (7) Соответственно исключение х2 из первого и третьего уравнений соответствует получению нулевых элементов в первой и третьей строках второго столбца матрицы 1 2 7  1 0 0    0 5   1 2 0 1 3 3 3     1 1 11   1 1 11  0 . 1 0   0 1 0   3 3 3  3 3 3  0   5 1 4 1 21 7 8 8    0 0 1   3 3 3   (8) В итоговой матрице в первых трех столбцах содержатся только три ненулевых единичных элемента, расположенные построчно. Это означает, что в исходной матрице, а соответственно и в исходной системе выделен базис с базисными переменными х1, х2, и х3. 1.3. Переход к другому базису 9 Полученное ранее общее решение системы линейных уравнений (5) можно представить в другом виде. Для этого нужно какую-либо базисную переменную вывести из базиса, а свободную переменную ввести в базис. Это означает, что в исходной системе линейных уравнений будет выделен другой базис и найдено новое общее решение системы. Выделим другой базис в нашей системе линейных уравнений, используя найденное решение. Проделаем это в матричной форме. Преобразуем итоговую матрицу (8). Умножим первую строку на (–3), далее, умножив ее на 1 7 и , вычтем 3 3 соответственно из второй и третьей строки   3 0 0   0 1 0    0 0 1  1 2 1 1  3 3 7 8 3 3  7    3 0 0 1 2 7  11      1 1 0 0 1 6  . 3  7 0 1 0 2 19  8    3 (9) В последней матрице второй, третий и четвертый столбцы содержат по одному ненулевому единичному элементу в разных строках. Это означает, что найден новый базис с базисными переменными х2, х3, и х4. Соответствующее общее решение системы имеет вид  x4  7  3 x1  2 x5 ,   x2  6  x1  x5 ,  x  19  7 x  2 x , 1 5  3 (10) где х1 и х5 – свободные переменные. Соответствующее базисное решение x2  6, x3  19, x4  7, x1  x5  0, или X Б 2   0, 6, 19, 7, 0  . Найдем частное решение. Положим х1 = 1 и х5 = 2, тогда x1  1, x2  7, x3  16, x4  8, x5  1, или X 2  1, 7, 16, 8, 2  . 1.4. Линейная зависимость уравнений системы 10 Система уравнений может содержать как линейно независимые уравнения, так и «лишние» уравнения, которые являются следствием линейных операций над другими уравнениями системы. Поэтому по виду системы линейных уравнений нельзя сразу определить число базисных и свободных переменных. Метод последовательного исключения неизвестных позволяет выявить линейную зависимость между уравнениями системы, исключить «лишние» и определить число базисных и свободных переменных. Пример Решить систему линейных уравнений, найти одно общее решение и соответствующее базисное и одно частное решение  x1  x2  5 x3  x4  7 x5  3,   2 x1  x2  x3  4 x4  2 x5  0,  x  2 x  4 x  5 x  5 x  3. 2 3 4 5  1  1 1 5 1 7 3    Расширенная матрица системы  2 1 1 4 2 0  .    1 2 4 5 5 3  1. Вычтем первую строку из третьей и, умножив на 2, – из второй  1 1 5 1 7 3   1 1 5 1 7 3      2 1 1 4 2 0    0 3 9 6 12 6  .  1 2 4 5 5 3   0 3 9 6 12 6      2. Вычтем вторую строку из третьей  1 1 5 1 7 3   1 1 5 1 7 3      0 3 9 6 12 6    0 3 9 6 12 6  .  0 3 9 6 12 6   0 0 0 0 0 0     Получившаяся третья строка, полностью состоящая из нулевых элементов, свидетельствует о том, что одно из уравнений исходной системы «лишнее», то есть является линейной комбинацией двух других уравнений. Наличие такого уравнения, или его отсутствие не изменяет общего решения системы и, 11 следовательно, «лишнее» уравнение можно убрать из системы. Это соответствует вычеркиванию нулевой строки в последней матрице. 3. Удалим нулевую строку в последней матрице и разделим вторую строку на –3  1 1 5 1 7 3     1 1 5 1 7 3  1 3  2 4 2     0 1 3 2 4 2  .  0 0 0 0 0 0    4. Вычтем вторую строку из первой  1 1 5 1 7 3   1 0 2 1 3 1   .  0 1 3 2 4 2   0 1 3 2 4 2  В последней матрице первый и второй столбцы содержат по одному ненулевому единичному элементу в разных строках. Это означает, что выделен базис с базисными переменными х1 и х2. Общее решение системы имеет вид  x1  1  2 x3  x4  3 x5 ,   x2  2  3 x3  2 x4  4 x5 , где х3, х4 и х5 – свободные переменные. Соответствующее базисное решение x1  1, x2  2, x3  x4  x5  0, или X Б1  1, 2, 0, 0, 0  . Найдем частное решение. Положим х3 = 1, х4 = 2, х4 = 3, тогда x1  12, x2  9, x3  1, x4  2, x5  3, или X 1   12, 9, 1, 2, 3  . Таким образом, число базисных и свободных переменных в неопределенной системе линейных уравнений можно определить, если система состоит только из линейно независимых уравнений. 1.5. Несовместность системы линейных уравнений Если количество уравнений меньше, чем количество переменных, то система может быть неопределенной, а может не иметь решения, то есть быть несовместной. Пример Решить систему линейных уравнений 12  4 x1  3 x2  2 x3  x4  3,  3 x1  2 x2  x3  3 x4  7,  5 x1  3 x2  x3  8 x4  1.  4 3 2 1 3    Запишем расширенную матрицу системы  3 2 1 3 7  .  5 3 1 8 1    1. Вычтем вторую строку из первой и запишем получившуюся первую строку, кроме того, исходную первую строку вычтем из третьей и результат запишем в третью строку. Саму вторую строку не изменяем  4 3 2 1 3   1 1 1 2 1      3 2 1 3 7 3 2 1 3 7         .  5 3 1 8 1   1 0 1 7 7      2. Вычтем первую строку из третьей и, умножив на 3, – из второй  1 1 1 2 1   1 1 1 2 1       3 2 1 3 7    0 1 2 9 4  .  1 0 1 7 7   0 1 2 9 8      3. Вычтем вторую строку из третьей  1 1 1 2 1   1 1 1 2 1       0 1 2 9 4    0 1 2 9 4   0 1 2 9 8   0 0 0 0 12      Последняя полученная матрица соответствует системе  x1  x2  x3  2 x4  1,  x2  2 x3  9 x4  4,   0  12.  В последнем уравнении возникло противоречие, которое свидетельствует о несовместности исходной системы линейных уравнений. Таким образом, если в ходе элементарных преобразований расширенной матрицы возникает строка вида (0 …0| λ), дальнейшие преобразования системы можно не проводить, поскольку такая система решения не имеет. 13 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 2.1. Основные понятия линейного программирования Линейное программирование (ЛП)  это раздел математики о методах исследования и поиска наибольших и наименьших значений некоторой линейной функции, причем ограничения задачи тоже линейны. Математические модели задач линейного программирования (ЗЛП) различаются между собой по виду ограничений. Определение 1. Математическая модель ЗЛП называется стандартной, если ограничения в ней представлены в виде линейных неравенств, а целевая функция минимизируется или максимизируется, при этом если целевая функция задачи ЛП максимизируется, то знак во всех неравенствах должен быть «», а если целевая функция минимизируется, то знак должен быть «». Например, пусть в модели n неизвестных: х1, х2, …xn. Надо найти среди решений системы неравенств такие, которые дают целевой функции наибольшее значение. Тогда такая модель имеет вид:  a11x1  a12 x2  ...  а1n xn  b1 ,  a x  a x  ...  а x  b ,  21 1 22 2 2n n 2                                 a x  a x  ...  а x  b ; mn n m  m1 1 m 2 2 (1) x j  0, j  1,2,... n; f ( X )  c1 x1  c2 x2  ..cn xn  c0  max , (2) где X   x1, x2 , ..., xn   искомое решение системы. Система m линейных неравенств, определяющая допустимое множество решений задачи (1), называется системой ограничений задачи линейного программирования, а линейная функция f(Х) (1.2) называется целевой функцией или критерием оптимальности. Определение 2. Искомое решение системы (план) X   x1, x2 ,..., xn  , при котором целевая функция принимает свое наибольшее (наименьшее) значение, называется оптимальным решением. 14 Определение 3. Математическая модель ЗЛП называется основной, если ограничения в ней представлены в виде уравнений при условии неотрицательности переменных хj и правой части ограничений. Такая модель имеет вид:  a11x1  a12 x2  ...  а1n xn  b1 ,  a x  a x  ...  а x  b ,  21 1 22 2 2n n 2                                a x  a x  ...  а x  b ; mn n m  m1 1 m 2 2 (3) x j  0, j  1,2,... n; f ( Х )  c1 x1  c 2 x 2  ...  c n x n  c 0  max(min), (4) Найденное множество X   x1, x2 ,... xn , удовлетворяющее системе ограничений и условию (4),  искомое решение системы. Система уравнений (3) обычно имеет конечное множество решений. Целевая функция f(Х) − линейная, поэтому ее частные производные постоянны, а это значит, что внутри области решений системы (3) экстремальных точек нет. Если целевая функция имеет оптимальное решение, то оно достигается в точках границ области. Таким образом, в линейном программировании исследователя интересуют вершины многогранника (многоугольника) решений системы (3) и методы нахождения этих вершин на границах области решений ЗЛП. Рассмотрим другие модели задач линейного программирования. Определение 4. Математическая модель называется канонической, если ее система ограничений представлена в виде системы m линейно независимых уравнений, в системе выделен единичный базис, определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны. Запишем каноническую модель ЗЛП: 15 a1x1  a12 x2  ...  а1s xs  xs 1  b1 , a x  a x  ...  а x  x  b ,  21 1 22 2 s2 2s s 2                                   am1x1  am 2 x2  ...  ams xs  xs  m  bm ;  (5) x j  0, j  1,2,... s  m; f ( X )  c0  c1x1  ...  cs xs  max (6) В рассматриваемой модели переменные x1, ..., хs – свободные, и если их принять равными нулю, то из системы уравнений легко получить значения базисных переменных xs+1, xs+2, ..., xs+m (каждая входит только в одно уравнение с коэффициентом равным единице), приняв свободные переменные равными нулю, тогда базисное решение имеет вид Х Б  (0,... 0; b1,... bm ); f  Х Б   с0 . Базисное решение является угловой точкой множества решений системы (5), или, можно сказать, определяет вершину многоугольника решений модели. Среди таких решений находится и то, при котором целевая функция принимает оптимальное значение. Определение 5. Базисное решение называется опорным, если оно допус- тимо, то есть все правые части уравнений (неравенств) положительны bi  0, i  1,... n . Теорема. Базисное опорное решение в канонической модели ЗЛП на мак- симум будет оптимальным, если все коэффициенты при свободных переменных в целевой функции не положительны, т. е. с j  0, j  1,...n . Базисное опорное решение в канонической модели ЗЛП на минимум будет оптимальным, если все коэффициенты при свободных переменных в целевой функции не отрицательны с j  0, j  1,...n . Рассмотрим правила перехода от одной модели к другой. 2.2. Переход от стандартной модели ЗЛП к канонической При этом переходе требуется преобразовать систему ограничений – неравенств в систему уравнений. 16 Рассмотрим стандартную модель с двумя неизвестными:  a11x1  a12 x2  b1 ,  a x a x b ,  21 1 22 2 2     a x a x b ;  m1 1 m 2 2 m x j  0, j  1, 2; f ( Х )  c1x1  c2 x2  c0  max . Введем дополнительные неизвестные x 3  0, ... x2  m  0 такие, чтобы они уравняли левую и правую части неравенств. Получим новую модель:  a11x1  a12 x2  x3  b1 ,  a x a x  x b ,  21 1 22 2 4 2      am1x1  am 2 x2  x2  m  bm ; x j  0, f ( Х )  c1x1 c2 x2  c0  max, или j  1,2, ... 2  m. f1( Х )   c1x1  c2 x2  c0  min. Это каноническая модель задачи ЛП. Заметим, что для решения задачи на минимум достаточно положить f1( Х )   c1x1  c2 x2  c0  min. 2.3. Переход от канонической модели задачи ЛП к стандартной Если нам задана каноническая модель ЗЛП, то можно перейти к стандартной модели, если отбросить базисные переменные, при этом равенства переходят в неравенства. Пусть дана каноническая модель:  a11x1  a12 x2  ...  a1s xs  xs 1  b1 ,  a x  a x  ...  a x  x  b ,  21 1 22 2 s2 2s s 2       am1x1  am 2 x2  ...  ams xs  xs  m  bm ; x j  0, j  1,2, ... n; n  s  m; f  X   c1x1  ...  cs xs  c0  min. Так как переменные: xs+1, ..., xs+m неотрицательны, то стандартная модель будет иметь вид: 17  a11x1  a12 x2  ...  a1s xs  b1 ,  a x  a x  ...  a x  b ,  21 1 22 2 2s s 2     a x  a x  ...  a x  b ; m  m1 1 m 2 2 ms s x j  0, j  1,2, ... s; f ( Х )  c1 x1  ...  c s x s  c 0  min . 2.4. Переход от основной модели задачи ЛП к канонической Если задана основная модель задачи ЛП, то можно перейти к канонической или стандартной модели, используя элементарные преобразования матрицы коэффициентов. Рассмотрим такой переход на конкретном примере. Пример Пусть дана основная модель задачи ЛП на нахождение минимума целевой функции. Необходимо перейти к канонической модели задачи линейного программирования.  8 x1  7 х 2  2 х3  3 x 4  68 ,   18 х1  8 x 2  2 x3  4 x5  96 ,  2 x  3 x  x  36 , x j  0 , j  1,...5 2 4  1 (7) f ( X )   x1  2 х2  х3  х4  x5  2  min. Для перехода к канонической модели запишем расширенную матрицу системы уравнений  8   18  2  7 8 2 2 3 3 1 0 68   4 96  0 36  . С помощью элементарных преобразований перейдем к матрице с единичным базисом. Заметим, что в исходной матрице есть столбцы с нулевыми элементами, поэтому первоначально базисные переменные целесообразно выбирать из переменных этих столбцов. Выполним последовательно следующие действия: 1) разделим все элементы первой строки на три и вычтем из соответствующих элементов третьей строки, оставив саму первую строку неизменной 18  8 7 2   3 3  3 18 8 2  3 0 2  68   8 7    3   3 3 0 4 96    18 8   1 0 36    2 16   3 3 1 2 68  1 0 3 3  2 0 4 96  . 2 40   0 0  3 3  Четвертый столбец содержит только один ненулевой элемент, равный единице в первой строке, при этом последний столбец расширенной матрицы неотрицателен. Это означает, что переменная x4 стала допустимой базисной переменной; 2) в получившейся матрице базисные переменные нужно выделить в оставшихся второй и третьей строках, в столбцах, содержащих неотрицательные переменные. Выделим единичный элемент в последней строке, разделив все элементы на 16 . 3 7 Далее, умножив получившиеся элементы третьей строки на 8 и  , вы3 чтем соответственно из элементов второй и первой строки, оставив третью строку неизменной  8 7  3 3   18 8  1  1  8 2 68   19 3 57  1 0 1 0   3 3   8 8 2  2 0 4 96    19 0  1 0 4 76  1 5   1 1 5      0 0 1  0 0 8 2   8 8 2  . Во втором столбце остался только один ненулевой единичный элемент третьей строки. Последний столбец матрицы содержит только неотрицательные элементы. Это означает, что переменная x2 также стала допустимой базисной переменной; 3) разделим все элементы второй строки на 19 и, умножив получившиеся элементы второй строки на 19 1 и  , вычтем соответственно из элементов пер8 8 19 вой и третьей строки. Таким образом выделена последняя допустимая базовая переменная x1 3  19    8 0 8 1 0 57   0  2   1 4  1 0  0  4  1    19 19  5     1 1  1 0 0 2  0  8   8    1 1  1 19  2 2  1 4 0  0  4  19 19  5 1 1  0  3  38 38  . Соответствующая система уравнений с единичным базисом имеет вид 1 1 x  х  x5  19 , 3 4 2 2  1 4  x3  x5  4 ,  х1  19 19  5 1  x  x  x5  3 , 2 3  38 38 (8) x j  0 , j  1,...5 . Для преобразования выражения целевой функции выразим базисные переменные х1, х2, х4 через, свободные переменные х3, х5: 1 4 x3  x5 , 19 19 5 1 x2  3  x3  x5 , 38 38 1 1 х4  19  x3  x5 . 2 2 х1  4  (9) Подставим полученные выражения для базисных переменных в уравнение целевой функции 1 4   5 1  1 1    f ( Х )    4  x3  x5   2  3  x3  x5   x3  19  x3  x5   x5  2 , 19 19   38 38  2 2    тогда целевая функция примет вид f (Х )  7  7 9 x3  x5  min . 38 38 Окончательно каноническая модель ЗЛП: 20 1 1 x  х  x5  19 , 3 4 2 2  1 4  x3  x5  4 ,  х1  19 19  5 1  x  x  x5  3 , 2 3  38 38 f (Х )  7  x j  0 , j  1,...5 . 7 9 x3  x5  min . 38 38 (10) Замечание Заметим, что коэффициенты при свободных переменных в выражении целевой функции (10) положительные, следовательно найденное базисное решение ЗЛП на минимум является оптимальным и равно наименьшему возможному значению f min  X   7 . 2.5. Примеры задач линейного программирования Приведем примеры некоторых типовых задач, решаемых при помощи методов линейного программирования. Такие задачи имеют реальное экономическое содержание. Сформулируем их в терминах ЗЛП, и построим простейшие математические модели задач с конкретными данными. 1. Задача об оптимальном использовании ресурсов Предприятие выпускает два вида продукции А1 и А2. Для их производства требуется три вида сырья В1, В2, В3. Запасы сырья bi, количество единиц сырья aij, затрачиваемого на изготовление единицы продукции, а также величина прибыли cj, получаемой от реализации единицы продукции, приведены в таблице Количество единиц сырья, Вид сырья Запасы сырья затрачиваемого на изготовление Вi bi единицы продукции ( aij) А1 А2 В1 30 3 4 В2 50 7 6 В3 70 9 5 21 Прибыль от реализации единицы продукции cj 25 40 Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль. Решение Обозначим через х1 и х2 количество продукции первого и второго вида в плане предприятия. Поскольку производство продукции ограничено сырьем каждого типа Вi, то получим условия  3 x1  4 x 2  30,   7 x1  6 x 2  50,  9 x  5 x  70, 2  1 (11) x j  0, j  1, 2. Переменные х1 и х2 не могут быть отрицательными по смыслу задачи. Прибыль от реализации продукции составит f ( Х )  25 x1  40 x2  max . Получили стандартную модель ЗЛП на максимум с двумя переменными. 2. Задача составления рациона (диеты) При откормке каждое животное ежедневно должно получать не менее 15 единиц питательного вещества В1, не менее 20 единиц питательного вещества В2 и не менее 10 единиц питательного вещества В3. Для составления рациона используются два вида корма А1 и А2. Содержание количества единиц питательных веществ в 1 кг каждого вида корма aij, а также стоимость cj, 1 кг корма приведены в таблице Питательные вещества Вi Минимальное количество Количество единиц питательных единиц питательного веществ в 1 кг корма ( aij) вещества bi Корм 1 Корм 2 В1 15 8 7 В2 20 9 4 В3 10 6 5 5 7 Стоимость 1 кг корма cj 22 Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными. Решение Обозначим через х1 и х2 массу корма (кг) первого и второго вида в дневном рационе. Поскольку дневной рацион удовлетворяет требуемой питательности только в случае, если количество питательных веществ не меньше предусмотренного, то получим систему ограничений  8 x1  7 x 2  15,   9 x1  4 x 2  20,  6 x  5 x  10, 2  1 (12) x j  0, j  1, 2. Переменные х1 и х2, как и в предыдущей задаче, не могут быть отрицательными. Условие минимальной стоимости рациона можно записать в виде f ( Х )  5 x1  7 x2  min . Получена стандартная модель ЗЛП на минимум с двумя переменными. 3. Транспортная задача Имеющуюся у поставщиков В1 и В2 продукцию в количестве 100 и 150 единиц соответственно необходимо отправить потребителям: А1 – 120 ед. и А2 – 130 ед. (закрытая транспортная задача – общий объем запасов продукции у поставщиков равен суммарному объему запрашиваемой продукции потребителями). Известны стоимости перевозок одной единицы груза от каждого поставщика каждому потребителю. Данные представлены в таблице Потребности потребителей Поставщики Запасы А1 А2 120 130 В2 100 7 9 В3 150 10 12 Необходимо составить такой план перевозок, при котором суммарные транспортные расходы будут минимальными. Решение 23 Обозначим через х1 количество единиц груза, перевозимого от поставщика В1 потребителю А1, через х2 – количество единиц груза, перевозимого от поставщика В1 потребителю А2, через х3 – количество единиц груза, перевозимого от поставщика В2 потребителю А1, через х4 количество единиц груза, перевозимого от поставщика В2 потребителю А2. Задача сводится к определению четырех неизвестных, которые должны удовлетворять следующей системе четырех уравнений:  x1  x2  100,  x  x  150,  3 4   x1  x3  120, x1  0, x2  0,  x2  x4  130, x3  0, x4  0. Среди различных допустимых планов перевозок (х1, х2, х3, х4) необходимо выбрать такой план, при котором суммарные транспортные расходы будут минимальными. Тогда условие минимальной стоимости перевозок f ( Х )  7 x1  9 x2  10 x3  12 x4  min . 24 3. ГЕОМЕТРИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Пусть задана стандартная математическая модель задачи с двумя неизвестными:  a11x1  a12 x2  b1 ,  a x a x b ,  21 1 22 2 2     am1x1  am 2 x2  bm ;  (1) x j  0, j  1, 2; f ( Х )  c0  c1x1  c2 x2  max . (2) Нахождение решения этой модели на основе ее геометрической интерпретации включает следующие этапы. 1. В плоскости х1Ох2 строят прямые, уравнения которых получаются в результате замены в ограничениях (1) модели знаков неравенств на знаки точных равенств. 2. Находят полуплоскости, определенные каждым неравенством системы. 3. Находят выпуклый многоугольник решений всей системы (1).  4. Строят нормальный вектор целевой функции n  c1; c2 , причем, начало вектора совмещают с началом координат и строят линию уровня – прямую c1x1  c2 x2  0 .  5. Передвигают эту прямую в направлении вектора n , в результате либо находят вершину или отрезок, в которой целевая функция принимает наибольшее значение, либо устанавливают неограниченность сверху этой функции на множестве допустимых решений. 6. Если функция ограничена, то определяют X max   x1, x2  вычисляют значение функции в этой точке f max  f  X max  . При геометрической интерпретации задач ЛП могут встретиться случаи, изображенные на рис. 1-4. Рис. 1. Задача ЛП имеет единственное решение f max  f  X max  . 25 Рис. 2. Задача ЛП имеет бесчисленное множество решений, так как целевая функция достигает максимума на отрезке [М; N ]. x2 x2 M f (Хmax ) f (Хmax ) N  n  n О x1 О x1 Рис. 1 Рис. 2 Рис. 3. Задача ЛП не имеет решения – функция неограниченна сверху. Рис. 4. Задача ЛП не имеет решения, так как система (1) несовместна. x2 x2 f (Хmax ) → ∞  n О  n Рис. 3 x1 О Рис. 4 x1 Пример Для производства двух видов изделий А1 и А2 предприятие использует три вида сырья В1 , В2 , В3. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в табл. 1. Прибыль от реализации одного изделия каждого вида равна с1 и с2 , а общее количество сырья вида Вi равно bi , i  1, 2, 3 . Считая, что изделия А1 и А2 могут производиться в любых соотношениях (сбыт обеспечен), требуется со- 26 ставить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий будет максимальной. Таблица 1 Сырье А1 А2 Запасы B1 а 1 1 = 12 а12 = 4 b 1 = 300 B2 а21 = 4 а22 = 4 b 2 = 120 B3 а31 = 3 а 3 2 = 12 b 3 = 252 Прибыль с 1 = 30 с 2 = 40 Обозначим через х1 и х2 количество изделий первого и второго вида в плане предприятия. Поскольку производство продукции ограничено только сырьем каждого типа Вi, то получим условия: 12 x1  4 x 2  300,   4 x1  4 x 2  120,  3 x  12 x  252, 2  1 (3) x j  0, j  1, 2. Переменные х1 и х2 не могут быть отрицательными по смыслу задачи. Вычислим прибыль от реализации продукции и получим f ( Х )  30 x1  40 x2  max, X   x1 , x2  . Итак, мы получили стандартную модель с двумя переменными. Решим задачу линейного программирования геометрически, придерживаясь плана, приведенного ранее. 1. Строим прямые l1, l2, l3 в плоскости х1Ох2 (рис. 5): l1 : 12 x1  4 x2  300 , по двум точкам D1 25;0  и C1 0;75  ; l2 : 4 x1  4 x2  120 , по двум точкам D 2  30;0  и C 2  0;30  ; l3 : 3 x1  12 x2  252 , по двум точкам D3  84;0  и C 3  0;21 . Обратимся к неравенствам (3). Отметим те полуплоскости, которые им удовлетворяют. Учтем на чертеже неотрицательность переменных х1 и х2, и получим многоугольник ОC3ЕFD1 решений данной системы неравенств (рис. 5). 27 2. Построим линию уровня  прямую l: 30 x1  40 x2  0 и нормальный век тор n  30;40 .  3. Передвигая линию уровня l в направлении вектора n , заметим, что в точке Е целевая функция будет иметь наибольшее значение. Найдем координаты этой точки как координаты точки пересечения прямых l2 и l3, решая систему соответствующих уравнений:  4 x1  4 x 2  120,   3 x1  12 x 2  252,  x1  12, x 2  18. Таким образом, точка Е 12;18  определяет наибольшее значение целевой функции. x2 80 70 • C1 60 l2 50 l1 40 •C2 C3 Е 20 • •  n 30 l f(x)=0 10 O 10 20 •F D •D1 • 2 30 l3 D3 40 Рис.505 60 70 80 • 90 100 x1 4. Найдем величину целевой функции, подставив найденные значения переменных, и запишем окончательный ответ Х max  12,18  ,  f max  f ( X max )  1080 . Наибольшая прибыль будет равна 1080 (у.е). Геометрический метод решения можно применять в математических моделях ЗЛП с бóльшим числом переменных при условии, когда число этих переменных в системе ограничений задачи на две больше числа линейно независи- 28 мых уравнений системы. Для этого нужно перейти к канонической модели ЗЛП и использовать условие неотрицательности переменных. Пример Ранее был показан переход от основной модели ЗЛП на нахождение минимума целевой функции к канонической модели. Можно заметить, что число переменных в системе (2.7) на две больше числа ограничений. Рассмотрим полученную каноническую модель задачи 1 1 x  х  x5  19 , 3 4 2 2  1 4  x3  x5  4 ,  х1  19 19  5 1   x 2  38 x 3  38 x 5  3 , f (Х )  7  x j  0 , j  1,...5 . 7 9 x3  x5  min . 38 38 Используем условие неотрицательности базисных переменных х1, х2, х3 1 4 x3  x5  0 , 19 19 5 1 x2  3  x3  x5  0, 38 38 1 1 х4  19  x3  x5  0. 2 2 х1  4  Данные ограничения можно записать в виде системы неравенств, которые содержат только две свободные переменные х2 и х5  x3  4 x5  76,  5 x3  x5  114,  x  x  38.  3 5 (4) Полученная система ограничений определяет область в плоскости х2Ох5, ограниченную прямыми l1, l2, l3 в виде треугольника АВС (рис 6). 29 X5 80 B 70 60 50 40 •  n D 30 20 10 -40 -30 O• -10 -20 Е 10 20 -10 l1 -20 A l2 30 • 40 60 50 70 • C X3 l3 • -30 Рис.6 Учтем условие неотрицательности свободных переменных и выделим в получившейся области треугольник DOE, который представляет собой область планов для рассмотренной канонической модели ЗЛП с соответствующим выбранным единичным базисом. Из уравнения целевой функции (10) (см. лекцию 2) найдем координаты нормального вектора опорной прямой f (Х )  7  7 9  x3  x5  n  7; 9 . 38 38 Первая точка области планов (вершина треугольника DOE), через которую проходит опорная прямая, перемещаясь вдоль нормального вектора – точка О(0; 0). Здесь целевая функция принимает наименьшее значение f ( Х min )  7  7 9 7 9 x3  x5  7   0   0  7 . 38 38 38 38 30 Заметим, что максимальное значение целевой функции достигается в точке D(38; 0). Это последняя точка на области планов, через которую проходит опорная прямая, передвигаясь в направлении нормального вектора (рис. 6) f ( Х max )  7  7 9 7 9 x3  x5  7   0   38  16 . 38 38 38 38 31 ЛЕКЦИЯ 4. ДВОЙСТВЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД 4.1. Построение двойственных моделей Двойственная задача – это вспомогательная задача ЛП, формулируемая с помощью определенного правила непосредственно из условия исходной задачи. Заметим, что для разных моделей исходной задачи правила построения двойственных моделей отличаются. Рассмотрим правила построения двойственной модели, если исходная задача задана в виде стандартной модели ЗЛП на нахождение максимального значения целевой функции:  a11x1  a12 x2  ...  а1n xn  b1,  a x  a x  ...  а x  b , 2 2n n  21 1 22 2      a x  a x2  ...  а x  b ; mn n m  m1 1 m 2 (1) x j  0, j  1,2,..., n. f ( X )  c1 x1  c 2 x 2  ...  c n x n  max . (2) Правила построения двойственной модели: 1. Проверить, отвечает ли исходная модель двум требованиям: а) все неравенства в системе (1) должны иметь одинаковый знак «  ». б) если целевая функция ЗЛП максимизируется, то знак в неравенствах должен быть «  ». В нашей модели это требование выполнено (если целевая функция минимизируется, то знак во всех неравенствах должен быть «  »). 2. Каждому i-тому ограничению исходной задачи соответствует i-тое неизвестное в двойственной задаче: так, неравенству ai1x1  ai 2 x2  ...  ain xn  bi соответствует yi  0 (i  1, ..., m) . 3. Каждому j-тому неизвестному исходной модели соответствует j-тое ограничение двойственной модели. Правые части ограничений равны коэффициентам функции цели прямой задачи. Таким образом, для j -той переменной х j  0  a1 j y1  a 2 j y 2  ...  am j y m  c j , j  1,...n . 4. Матрица коэффициентов при неизвестных двойственной задачи является транспонированной матрицей исходной задачи. 32 5. Целевая функция двойственной модели имеет вид: q (Y )  b1 y1  b2 y 2  ...  bm ym , и решается задача минимизации. Запишем модели по соответствию:  a11x1  a12 x2  ...  a1n xn  b1, a x   21 1 a22 x2  ...  a2 n xn  b2 ,                                a m1x1  am 2 x2  ...  amn xn  bm ,  x  0,  1     xn  0.  y1  0,  y  2  0,    (3)  y m  0,  a y  a y  ...  a y m1 m  c1 ,  11 1 21 2     a1n y1  a2 n y2  ...  amn ym  cn . f ( Х )  c1x1  ...  cn xn  max . q (Y )  b1 у1  ...  bm ym  min . Такие модели задачи ЛП называются симметричными. Заметим, что в симметричных задачах система ограничений как исходной, так и двойственной задачи, задается неравенствами, причем на двойственные переменные накладывается условие неотрицательности. Если исходная задача ЛП − основная задача минимизации, то двойственная ей  стандартная задача максимизации, при этом переменные второй задачи yi (i  1,..., m) могут иметь любой знак. Пара таких задач имеет вид:  a11x1  a12 x2  ...  a1n xn  b1, a x   21 1 a22 x2  ...  a2 n xn  b2 ,                                a m1x1  am 2 x2  ...  amn xn  bm ,  x  0,  1     xn  0.  y1   0,  y   2  0,     0,  ym   a y  a y  ...  a y  c , m1 m 1  11 1 21 2     a1n y1  a2 n y2  ...  amn ym cn . f ( Х )  c1x1  ...  cn xn  min . (4) q (Y )  b1 у1  ...  bm ym  max . Заметим, что для полученной двойственной модели можно также построить по тем же правилам двойственную модель, которая будет представлять исходную модель ЗЛП. 33 4.2. Теоремы двойственности Существующие зависимости между решениями прямой и соответствующей ей двойственной задачи определяются следующими основными теоремами двойственности. Теорема 1. Если одна из взаимно двойственных задач имеет оптимальное решение, то и другая тоже имеет оптимальное решение, причем оптимальные значения целевых функций равны между собой f (X max ) = q (Y min ). Теорема 2. Для того чтобы два допустимых решения Х* и Y* пары двой- ственных задач были оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системе уравнений: m x* j (  a ij *y i  c j )  0, j  1, 2 , ... n . i 1 n y*i (  a i j x*j  bi )  0, i  1, 2 , ... m . j 1 Теорема 3. Пусть одна из взаимно двойственных задач имеет оптималь- ное решение. Тогда для неизвестных и ограничений выполняются следующие условия: 1) если координата хj оптимального плана исходной модели строго положительна, то соответствующее ограничение выполняется при подстановке в него координат оптимального решения как уравнение; 2) если при подстановке Xо п т в какое-либо ограничение исходной задачи оно выполняется как строгое неравенство, то соответствующая ему переменная уi равна нулю. Теорема 4. Если X – любое опорное решение исходной задачи на мини- мум (максимум), а Y – любое опорное решение соответствующей ей двойственной задачи, то f (X) ≤ q (Y) (f (X) ≥ q (Y)). Теорема 5. Если одна из взаимно двойственных моделей не имеет опти- мального решения (например, целевая функция не ограничена), то и другая не 34 имеет допустимых решений, т. е. система ограничений в ней – несовместна в области планов. Зная оптимальное решение одной из двойственных задач, можно с помощью теорем двойственности, найти оптимальное решение другой. Пример Вернемся к задаче из примера 1, рассмотренной на второй лекции. Нам известно, что исходная задача имеет оптимальное решение f  X max   1080. X max  12,18  , Построим для заданной модели по правилам, изложенным выше, двойственную модель и покажем, что ее решение совпадает с решением прямой задачи.  12 x1  4 x 2  300 ,  4 x  4 x  120,  1 2   3 x1  12 x 2  252,  x1  0, x 2  0, 12 y1  4 y 2  3 y3  30 ,   4 y1  4 y 2  12 y 3  40, y  1  0 , y 2  0, y3  0. f ( Х )  30 x1  40 x 2  max . q(Y )  300 у1  120 y2  252 y3  min. Далее, используем теорему 3. Начнем с первой части: x1  12  0  12 y1  4 y2  3 y3  30, x2  18  0  4 y1  4 y2  12 y3  40. Подставим полученное оптимальное решение Xmax в ограничения задачи: 144  72  216  300  y1  0, 48  72  120  120  y2  0, 36  216  252  252  y3  0, Получим систему уравнений для определения оптимального решения двойственной модели:  12 y1  4 y2  3 y3  30,   4 y1  4 y2  12 y3  40,  y  0.  1 Получим:   4 y2  3 y3  30,   4 y2  12 y3  40,  y  0.  1 y 3  10 , y2  1  (30  10 )  20 , Ymin  (0, 20 , 10 ). 3 3 4 3 9 9 35 Проверим расчет: q(Ymin )  120  20  252  10  1080 . 9 3 Таким образом, f  Х max   f  Ymin  – оптимальные решения прямой и двойственной задачи совпадают. 4.3. Экономическая интерпретация двойственной задачи Рассмотрим задачу об использовании ресурсов.  a11x1  a12 x2  b1, a x  a x  b ,  21 1 22 2 2   a31x1  a32 x2  b3,  x1, x2  0. f ( Х )  c0  c1x1  c2 x2  max В этой модели: bi – запас ресурса Bi, aij – число единиц ресурса Bi, потребляемого при производстве единицы продукции Аj, cj – прибыль (выручка от реализации). Предположим, что некоторая организация решила закупить ресурсы B1, B2 и B3 предприятия и необходимо установить оптимальные цены на эти ресурсы: y1, y2 и y3. Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы в количествах b1, b2, b3 по ценам y1, y2, y3 были минимальными, то есть q(Y )  b1 у1  b2 y2  b3 y3  min. С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие могло получить при переработке ресурсов в готовую продукцию. На изготовление продукции A1 расходуется a11 ресурса B1, a21 ресурса B2, а31 ресурса B3 → a11y1 + a21y2 + a31y3 ≥ c1. Аналогично для продукции A2: a12y1 + a22y2 + a32y3 ≥ c2. Также необходимо учесть, что цены на ресурсы (объективно обусловленные оценки) не могут быть отрицательными. Объединяя все вышесказанное, получаем следующую экономикоматематическая модель двойственной задачи: 36  a11 y1  a12 y 2  a13 y3  c1 ,   a 21 y1  a 22 y 2  a 23 y 3  c 2 , y , y , y  1 2 3  0. q(Y )  b1 у1  b2 y2  b3 y3  min. Цены ресурсов y1, y2, y3 называются учетными, неявными, теневыми. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены. В отличие от «внешних» цен c1, c2 на продукцию, известных, как правило, до начала производства, цены ресурсов y1, y2, y3 являются внутренними, так как они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их часто называют оценками ресурсов. Замечание Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи, обусловлена тем, что вычисления при решении двойственной задачи могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных. 37 5. СИМПЛЕКС-МЕТОД В ЗАДАЧАХ ЛП 5.1. Основные положения симплекс-метода Симплексный метод позволяет, отправляясь от известного опорного решения задачи, за конечное число шагов получить оптимальное решение. Каждый из шагов состоит в нахождении нового решения, которому соответствует меньшее значение целевой функции, чем значение этой функции при предыдущем решении. Процесс повторяется до тех пор, пока не будет получен оптимальный план. Пусть задана задача линейного программирования в виде канонической модели.  x1  x 4  x 5  2,   x 2  2 x 4  3 x5  7 ,  x j  0, j  1,...5 ;  x 3  x 4  x 5  2, (1) f ( X )  3  x4  x5  min. Рассмотрим идею симплекс-метода на этом примере. Нетрудно убедиться, что система (1) совместна. Ее ранг r = 3, значит базисных переменных 3, а свободных переменных k  5  3  2 . Полагая свободные переменные x4, x5 равными нулю, получим первое опорное решение: X опор1   2,7, 2,0,0  ;   f X опор1  3. В начальном плане свободными, а значит равными нулю, являются переменные х4, х5. Посмотрим, нельзя ли за счет увеличения х4 и х5 уменьшить значение целевой функции? Так как f  X   3  x4  x5 , то неизвестная х5 входит в выражение целевой функции со знаком плюс, поэтому ее увеличение приводит к увеличению функции. И это нам невыгодно. В то же время неизвестная х4 входит в выражениях со знаком минус, поэтому ее увеличение сопровождается уменьшением значения функции f  X  . Увеличение свободной неизвестной х4 вызывает соответствующие изменения базисных переменных х1, х2, х3. Данные изменения могут оказаться такими, что базисные переменные станут отрицательными. Мы должны позаботиться о том, чтобы этого не произошло. 38 Оставим у переменной х5  значение, равное нулю, и рассмотрим уравнения, которые в этом случае получаются из системы (1): x1  x 2  2 , x2  2 x4  7 , x3  x 4  2 . Так как x1  2  x2 и x1  0 , то x4  2 ; аналогично x2  7  2 x4 и x 2  0 , следовательно, x4  3,5 . Так как x3  2  x4 , то здесь х4 может возрастать неограниченно. Далее выберем максимально возможное значение х4, равное 2; при этом x1  0, x2  3, x3  4, x4  2, x5  0. Мы перешли к новому опорному решению: X опор2   0,3, 4, 2,0  . Сравнивая X опор1 и X опор2 , видим, что х1 стала свободной, а х4  базисной. Модель надо преобразовать так, чтобы х4 присутствовало только в первом уравнении системы (4.1), функция f  X  должна быть выражена через свободные переменные х1 и х5. Из первого уравнения x4  2  x1  x5 , и задача ЛП будет такой:  x2  2 x1  x5  3,   x3  x1  2 x5  4,  x  x  x  2, x  0, j  1,...5; j  4 1 5 (2) f ( X )  1  x1  2 x5  min . Теперь видно, что f  X  не может быть уменьшена за счет увеличения х1 и х 5 . Значит, мы получили оптимальное решение. Запишем его. X min   0,3,4,2,0  ; f min  f  X min   1. Идею, рассмотренную в примере, используем для того, чтобы сформулировать правило преобразования симплекс-таблиц для решения задач симплексным методом. 5.2. Правило преобразования симплекс-таблиц Мы в пункте (1) увидели, что переход от одного опорного решения к другому начинается с исследования коэффициентов целевой функции, затем вычисляются коэффициенты новой модели задачи ЛП. Запишем требования к исходной модели задачи. 39 1. Задача линейного программирования должна быть представлена в виде канонической модели. 2. Целевая функция должна минимизироваться. 3. При занесении в таблицу у целевой функции меняются на противоположные знаки коэффициентов при свободных переменных. Запишем полученную каноническую задачу:  a11x1  a12 x2  x3  b1,   a21x1  a22 x2  x4  b2 ,  a x  a x  x  b , x  0, j  1,...5;  31 1 32 2 5 3 j f ( X )  c0   c1x1  c2 x2   min.  В задаче X опор1   0, 0, b1, b2 , b3  ;  f1  f X опор1  c0 . Внесем коэффици- енты этой модели в симплекс-таблицу 1. Таблица 1 Базис В х1 х2 х3 х4 х5 х3 b1 а11 al2 1 х4 b2 а21 a22 1 х5 b3 а31 a32 1 f(Х) с0 с1 с2 4. Рассмотрим в последней строке табл. 1 коэффициенты целевой функции. Нас интересуют знаки с1 и с2: а) если хотя бы один из коэффициентов положителен, например c1  0 , то отмечаем стрелкой столбец таблицы, где находится с1. Этот столбец назовем ключевым. Если положительны оба коэффициента, то выберем наибольший из них; б) если с1 ≤ 0 и с2 ≤ 0, то таблицу не надо преобразовывать. Из таблицы находится оптимальное решение. 40 5. Выберем ту базисную переменную, которая будет свободной вместо х1, для этого выберем положительные из коэффициентов ai1, i  1, 2, 3. Пусть для определенности у нас a11   a21   a31   . Если все ai1 отрицательны или равны нулю, то задача решений не имеет, так как. целевая функция не ограничена. Пусть, кроме того, b1 b2 .  a11 a21 b b  b 6. У нас a11   a21   , тогда выберем min  1 ; 2   1 . Это означа a11 a21  a11 ет, что х1 будет базисной переменной, а х3  свободной. Переходим к следующей таблице: Таблица 2 Базис В х1 х2 х3 х4 х5 х1 β1 1 al2* al3* х4 β2 a22* a23* 1 х5 β3 a32* a33* 1 f(Х) d0 d2 d3 7. Сначала заполняем первую строку табл. 2, эта строка соответствует базисной переменной х3 в табл. 1. Все коэффициенты первой строки табл. 1. делим на разрешающий элемент а11, результат запишем в первую строку табл. 2. Эта строка называется разрешающей. β1  b1 *  a12 , a*  1 . , a12 13 a 11 a 11 a 11 С помощью разрешающей строки, делая простые вычисления, мы должны получить в остальных строках ключевого столбца нули. 8. Умножим разрешающую строку последовательно на (а 2 1 ), (а 3 1 ), (–с 1 ). Полученные строки чисел прибавим ко второй, потом к третьей, затем к последней строке табл. 1, а результаты вычислений поставим во вторую, третью и последнюю строку табл. 2, 41 где β 2  b2  b1a 21 ; a11 β 3  b3  * a  a 22 22 b1 a 31 ; a 11 a 12 a 21 a 11 ; *   a21 ; a23 a 11 *  a32  a32 a12 a31 a11 ; *  a33 d 2  c2  c1 a12 ; a 11 d3   bc d 0  c 0  a1 1 ; 11 a31 a11 ; c1 . a1 1 9. Мы получили новую таблицу (см. табл. 2), для которой соответствующая каноническая задача имеет вид:  a12* x2  a13* x3  x1  β1,   a * x a * x  x β , 23 3 4 2  22 2  * *  a32 x2  a33 x3  x5  β3 , x j  0, j  1...5. f ( X )  d0   d 2 x2  d3 x3   min. Полагая свободные переменные х2 и х3 равными нулю, получаем новый опорный план: X опор2   β1, 0, 0, β 2 , β 3  ;   f 2  f X опор2  d 0 . 10. Если d1  0, d 2  0 , то решение оптимально. Если среди них есть положительные, то процесс преобразования таблиц надо продолжать. Пример Решим симплекс-методом задачу из примера 1, рассмотренную на третьей лекции. Модель задачи ЛП в этом примере стандартная  12 x1  4 x2  300,   4 x1  4 x2  120,  3x  12 x  252, 2  1 x1  0, x2  0; f ( X )  30 x1  40 x2  max. 1. Перейдем к канонической модели. Для этого подберем х3, х4, х5, уравнивающие левые и правые части системы ограничений. Затем перейдем к задаче минимизации: f ( X )  max , тогда f1 ( X )   f ( X )  min . 42 Запишем каноническую модель:  12 x  4 x  x  300, 1 2 3   4 x1  4 x2  x4  120,   3 x1  12 x2  x5  252, x j  0, j  1, 5; f1 ( X )    30 x1  40 x2   min. 2. Внесем коэффициенты в таблицу: Таблица 3 Базис В х1 х2 х3 х4 х5 х3 300 12 4 1 х4 120 4 4 1 х5 252 3 12 1 30 40 f1(X) В табл. 3 с1 = 30; с2 = 40; max 30; 40  40 , неизвестная х2 – перейдет в базисную. Столбец ее коэффициентов будет ключевым. Все элементы ключевого столбца положительны. 3. Найдем разрешающую строку и разрешающий элемент в таблице  300 120 252  min  ; ;   min 75; 30; 21  21. 4 12   4 Третья строка в таблице является разрешающей. Эта строка базисной переменной х5, поэтому х5 будет свободной переменной. Элемент, находящийся в табл. 3 на пересечении выделенных строки и столбца, будет разрешающим элементом, равным 12. Замена базисной переменной х5 на свободную х2 в табл. 3 показаны стрелками. 4. Разделим все элементы третьей (разрешающей) строки табл. 3 на 12. Далее все полученные элементы строки умножим последовательно на (– 4), (– 4), (– 40) и сложим с первой, второй и последней строкой табл. 3. Составим новую симплекс-таблицу: 43 Таблица 4 Базис В х1 х2 х3 х4 х5 х3 216 11 1 -1/3 х4 36 3 1 -1/3 х2 21 1/4 1 1/12 -840 20 -10/3 f1(X) 5. Снова изучим последнюю строку табл. 4. Там есть положительный коэффициент 20. Отметим ключевой столбец, выберем в нем элемент а21. Тогда  216 36 84  min  ; ;   min19, 6;12; 84  12 .  11 3 1  Будем работать с табл. 4. так же, как и с табл. 3. Делим вторую строку на 3. Затем получаем в столбце для переменной х1 нули в остальных строках, умножая 1 элементы разрешающей строки последовательно на (11), ( ) , (–20). Ре4 зультаты поместим в табл. 5: Таблица 5 Базис В х1 х2 х3 х4 х5 х3 84 1 -11/3 8/9 х1 12 1 1/3 -1/9 х2 18 1 -1/12 1/9 f1(Х) -1080 -20/3 -10/9 В последней строке табл. 5 нет положительных чисел, решение оптимально. Ответ: X min  12,18, 84, 0, 0  ; f1  f  X min   1080. Ответ исходной задачи: X max  12,18, 84, 0, 0  ; f  f  X max   1080. 5.3. Геометрическая интерпретация симплекс-метода Рассмотренная задача ЛП в стандартной модели была решена геометрически (см рис. 5, лекция 3). Многоугольник решений имеет пять вершин с ко- 44 ординатами О (0; 0), В3 (0; 21), Е (12; 18), С (22,5; 7,5), А1 (25; 0). Целевая функция достигает максимального значения в точке Е (12; 18). В модели участвовали только две переменные х1 и х2. Теперь обратимся к симплекс-таблицам и запишем опорные решения, которые там получились: X опор1   0,0,300,120, 252  (табл. 3); X опор2   0, 21, 216,36,0  (табл. 4); X опор3  X max  12,18,84,0,0  (табл. 5). Вывод: переход от одной симплекс-таблицы к другой геометрически соответствует переходу от одной вершины многоугольника к другой: X опор1  O  0; 0  ; X опор2  В3  0; 21 ; X опор3  X max  E 12; 18  . Таким образом переход осуществляется по вершинам многоугольника ОВ 3 ЕСА 1 , достигая своего максимального значения. На каждом шаге происходит переход к соседней вершине по ребру многоугольника, целевая функция уменьшается. 45 6. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ТРАНСПОРТНОЙ ЗАДАЧИ. ПОСТРОЕНИЕ ОПОРНОГО ПЛАНА. МЕТОД ПОТЕНЦИАЛОВ 6.1. Транспортная задача линейного программирования Построим математическую модель, организации рациональной перевозки однородных продуктов между поставщиками и потребителями. Будем считать, что для потребителя не имеет значения, от какого поставщика будет поступать продукт, лишь бы он поступал в нужном объеме. Естественно, что стоимость перевозок между различными поставщиками и потребителями, определяемая многими условиями (расстоянием, грузоподъемностью транспорта и т.д.), будет разной. Поэтому возникает вопрос о наиболее рациональном выборе направлении перевозок груза, при котором потребности удовлетворяются, а затраты на транспортировку минимальны. Пусть имеется m поставщиков некоторого однородного груза, сосредоточенного на станциях А1, А2, … Аm, и имеется n потребителей этого продукта, расположенные на станциях В1, В2 , … Вn. Известны также запасы груза (а1, а2,…, аm ), которые должны быть вывезены в фиксированный период времени. Потребности получателей груза за тот же период времени составляют (b1, b2,…, bn). Пусть запасы равны потребностям, т. е. m  i 1 аi  n  bj . (1) j 1 При выполнении этих условия транспортная задача называется закрытой. Кроме того, известны затраты Сi j на перевозку единицы груза с любой станции Аi на каждую станцию Вj . Требуется составить такой план перевозок, чтобы весь груз был вывезен, все потребности были удовлетворены, а суммарные затраты на перевозки были минимальны. 46 6.2. Математическая модель Обозначим величину перевозки со станции Аi на станцию Bj как xi j . Тогда условия полного вывоза груза со всех станций Аi можно записать в виде системы уравнений:       х11  х12  х13  ...  х1n  a1 , x21  x22  x23  ...  x2 n  a2 , (2)               xm 1  xm 2  xm3  ...  xmn  am . С другой стороны, станции Вj должны получить необходимое количество груза, что тоже записывается в виде системы уравнений:       х11  х21  х31  ...  хm 1  b1 , x12  x22  x32  ...  xm 2  b2 , (3)                x1n  x2 n  x3n  ...  xmn  bn . При этом выполняется условие неотрицательности для переменных xi j : xi j  0, ( i 1, 2 ,... m; j 1, 2 , ... n). Функция цели задачи по критерию минимума суммарных затрат m n f ( Х )   Cij xi j  min. (4) i 1 j 1 Таким образом, транспортная задача представляет собой основную задачу линейного программирования. Часто при решении реальных задач число переменных (следовательно, и число свободных переменных на любом плане) получается значительным, и решение транспортной задачи геометрическим способом бывает малоэффективным или невозможным, поэтому были разработаны специальные методы решения таких задач. Рассмотрим некоторые из них. Вся исходная информация для транспортной задачи организуется в виде матрицы или таблицы. Для примера рассмотрим задачу размерности 3×5, за- 47 данную в виде таблицы, в которую заносится опорный план задачи. В этой же таблице проводится оптимизация плана и записывается решение задачи. Таблица 1 Потребители B1 Поставщики А1 А2 А3 Потребности B2 c12 c11 x11 B3 x12 b1 b2 c25 x25 c34 x34 b3 c15 c24 c33 x33 Запасы x15 x24 c32 x32 c14 c23 x23 c31 B5 x14 c22 x22 x31 c13 x13 c21 x21 B4 c35 x35 b4 a1 a2 a3 b5 Рассмотрим различные методы нахождения первого опорного решения. 6.3. Методы определения начального опорного плана. Метод северо-западного угла Определение начального опорного плана начинается с того, что в верхнюю левую (северо-западную) клетку таблицы заносится максимально возможный объем перевозки груза со станции А1 для удовлетворения потребности первого потребителя В1. Если потребности потребителя полностью удовлетворены, вычеркиваются все клетки первого столбца. Если со станции А1 вывезены все запасы груза, то вычеркивается все клетки первой строки. Далее, все повторяется для оставшейся части таблицы. Рассмотрим построение опорного плана на примере транспортной задачи, исходные данные которой (запасы грузов на станциях Аi, потребности в грузах на станциях Вj, стоимости перевозок между станциями) приведены в табл. 2. Выбираем «северо-западный угол» – левую верхнюю клетку. Объем перевозки, которую нужно поместить в клетку, определяется потребностью потребителя В1 и запасами поставщика А1. В данном случае поставщик может полностью закрыть потребность потребителя, поставив ему 20 единиц груза. 48 Ставим первую максимально допустимую перевозку в клетку А1-В1. Первый столбец закрыт, а в пункте А1 осталось 40 – 20 = 20 единиц груза. Рассуждая аналогично, в клетку А1-В2 ставим максимально возможную перевозку для потребителя В2 равную 20 единицам – оставшееся количество единиц груза на станции А1. Остальные незаполненные клетки первой строки вычеркиваем из дальнейших распределений грузов. Первая строка закрыта. Далее в клетку А2-В2 ставим перевозку, необходимую для закрытия потребности потребителя В2, равную 1, которая осуществляется со станции А2. Закрыт второй столбец, при этом в пункте А2 осталось 30 – 1 = 29 единиц груза. Повторяя все рассуждения для оставшейся части таблицы, окончательно получим распределение грузов, при котором все грузы вывезены от поставщиков, а все потребности удовлетворены. Первоначальный опорный план, полученный методом северо-западного угла показан в табл.2. Таблица 2 Потребители В1 Поставщики А1 В2 4 20 3 А2 3 20 4 1 7 А3 Потребности 20 В3 В4 4 7 7 4 2 21 7 22 В5 11 9 15 8 8 2 24 Запасы 15 8 40 30 10 8 Вычислим стоимость всех перевозок. Она равна f ( Х )  20  4  20  3  1  4  7  7  22  15  2  8  8  15  659. Недостаток данного метода заключается в том, что он не учитывает стоимость перевозок и, как правило, получаемый план далек от оптимального. Метод наименьшей стоимости Рассмотрим другой метод, который учитывает в какой-то мере затраты на перевозки и реализуется следующим образом: в исходной матрице находят клетку с наименьшей стоимостью, в которую заносят максимально допустимую 49 перевозку. После чего вычеркивается либо строка, либо столбец, выбранной клетки. Далее все повторяется для оставшейся части таблицы (находят клетку с наименьшей стоимостью и т. д.). Опишем последовательность действий для данного метода на примере, рассмотренном выше. Выбираем в таблице клетку с наименьшей стоимостью А3-В3 и ставим в нее максимально допустимую перевозку от поставщика А3, равную 7 единицам груза (табл. 3), закрыли третий столбец. В пункте А3 осталось 10 – 7 = 3 единиц груза. Выбираем наименьшую стоимость в оставшихся клетках. Таких клеток две: А2-В1 и А1-В2. выберем любую из них, например, клетку А1-В2. ставим сюда перевозку объемом 21 единица. Второй столбец закрыт, а в пункте А1 осталось 40 – 21 = 19 единиц груза. Далее ставим максимальную перевозку в клетку А2-В1 от второго поставщика. Видно, что она равна 20 единицам груза. Закрыли первый столбец, при этом в пункте А2 осталось 30 – 20 = 10 единиц груза. Рассуждая, аналогичным образом, по мере возрастания тарифов перевозок заполняем клетки: А3-В4 – 3 единицы груза, А2-В5 – 8 единиц груза, А2-В4 – 2 единицы груза, А1-В4 19 единиц груза. Таблица 3 Потребители В1 Поставщики А1 20 А3 – Потребности 4 – А2 В2 3 7 20 В3 3 21 4 – 4 – 4 – 7 – 2 7 21 В4 7 В5 11 19 15 2 8 3 24 – 8 – Запасы 9 40 8 30 15 10 8 Вычислим общую стоимость перевозок f ( Х )  20  3  21  3  2  7  19  11  2  15  3  8  8  8  464 . В большинстве случаев метод дает план, который ближе к оптимальному, однако во всех случаях требуется сравнивать величины функции цели на 50 получаемых планах и выбирать тот, для которого функция принимает наименьшее значение. Метод двойного предпочтения В данном методе выбирают клетки с наименьшей стоимостью в каждой строке и отмечают их каким-нибудь значком, например, ☺. Затем выбирают и отмечают клетки с наименьшей стоимостью в каждом столбце. В дважды отмеченные клетки ☺☺ заносят максимально допустимые перевозки. После чего максимальные допустимые перевозки заносят в клетки, отмеченные один раз значком ☺. Остаток таблицы можно заполнить методом северо-западного угла или методом наименьшей стоимости. Используем алгоритм рассматриваемого метода для того же примера. Выберем в каждой строке минимальную стоимость и отметим эти клетки значком. То же сделаем со столбцами. В клетки с двумя значками: в клетку А1В2 ставим перевозку 21, равную единиц груза; в клетку А2-В1 – 20 единиц груза; в клетку А3-В3 – 7 единиц груза. Теперь, оставшиеся запасы у поставщиков распределяем по клеткам с одним значком: А2-В5 – 8 единиц груза; А3-В4 – 3 единицы груза. Остальные клетки можно заполнить предыдущим методом (табл. 4). Таблица 4 Потребители В1 Поставщики В2 4 А1 – А2 20☺☺ А3 – Потребности 3 7 20 В3 3 21☺☺ 4 – 4 – 21 В4 4 – 7 – 7 ☺☺ 7 2 19 В5 11 15 2 3☺ 24 8 – 8☺ – Запасы 9 40 8 30 15 10 8 Общая стоимость перевозок равна f ( Х )  20  3  21  3  2  7  19  11  2  15  3  8  8  8  464 . 51 Для нашего примера опорные планы двух последних методов совпадают. Выберем метод двойного предпочтения и оценим его на оптимальность по методу потенциалов. 6.4. Решение транспортной задачи методом потенциалов Метод потенциалов позволяет оценить составленный опорный план и при необходимости, последовательно улучшая его, найти оптимальное решение. Теоремы метода Теорема 1. Если опорный план X = (xi j ) является оптимальным, то суще- ствует система из (m + n) чисел, называемых потенциалами, Ui , Vj , такая, что: а) U i +V j = C i j , для xi j > 0 (базисные переменные); б) U i +V j  C i j , для xi j = 0 (свободные переменные). Таким образом, для оптимальности опорного плана необходимо выполнение следующих условий:  для каждой занятой клетки сумма потенциалов равна стоимости перевозки единицы груза, стоящей в этой клетке U i +V j = C i j , (5)  для каждой свободной клетки сумма потенциалов меньше или равна стоимости перевозки единицы груза, стоящей в этой клетке: U i +V j ≤ C i j . (6) Примечание: система (5) содержит (m + n) неизвестных и (m + n – 1) линейно независимых уравнений. Такая система имеет бесчисленное множество решений, которые можно получить, придавая одной из неизвестных конкретное значение. Это значение выбирается произвольно, например можно придать U2 значение равное, нулю, тогда другие потенциалы вычисляются из системы (5). Теорема 2. Любая закрытая транспортная задача имеет решение, которое достигается за конечное число шагов метода потенциалов. 52 Построение цикла и определение величины перераспределения груза Циклом в таблице перевозок называется ломаная линия с вершинами в клетках и ребрами, расположенными вдоль строк или столбцов, удовлетворяющая двум требованиям: а) ломаная должна быть связной, т. е. из любой вершины цикла можно попасть в другую вершину, двигаясь по ребрам; б) в каждой вершине цикла сходятся ровно два ребра  одно по строке, другое по столбцу. В цикле возможны самопересечения, но они происходят только не в вершинах цикла. Примеры построения циклов показаны ниже. Теорема 3. Если в таблице перевозок m строк и n столбцов и перевозками заполнено (m + n – 1) клеток, то существует цикл, одна из вершин которого расположена в свободной клетке, а все остальные вершины в занятых клетках. Такой цикл называется циклом пересчета свободной клетки. Теорема 4. В таблице перевозок для каждой свободной клетки существу- ет единственный цикл пересчета. Метод потенциалов позволяет не только оценить оптимальность плана, но и улучшить его с помощью цикла пересчета свободной клетки. Алгоритм решения методом потенциалов 1. Поставим в соответствие каждой станции А i переменную – потенциал U i , а каждой станции B j – потенциал V j . 2. Придадим одному из потенциалов заполненных клеток (содержащих грузоперевозки xi j  0) некоторое произвольное значение, например значение 53 U i = 0 (можно любое другое). Используя условие U i +V j = C i j для каждой заполненной клетки, найдем все остальные потенциалы. 3. Проверим оптимальность опорного решения, вычисляя сумму потенциалов для свободных клеток. Если найденная сумма (обозначим ее C i j *) меньше стоимости перевозок, т. е. C i j *≤ C i j для всех свободных клеток, то опорное решение является оптимальным (функция цели имеет минимальное значение). Запишем решение задачи, вычислив стоимость перевозок по найденному оптимальному плану. Если это условие не выполняется хотя бы в одной свободной клетке, то в случае такого нарушения разность δij = C i j *– C i j называют невязкой. Наличие невязок означает, что опорное решение не оптимально и надо перейти к следующему опорному плану. Найдем все возможные невязки для свободных клеток и выбираем ту клетку, которой соответствует максимальная невязка max δij > 0 (если есть несколько одинаковых невязок, то выбираем любую из них). 4. В выбранную свободную клетку нужно поставить перевозку и построить цикл пересчета свободной клетки так, чтобы первая вершина цикла находилась в выбранной клетке, а все остальные в занятых. 5. Пронумеруем вершины цикла, начиная с пересчитываемой свободной клетки. Определим величину сдвига по циклу θ как минимальную из перевозок, стоящих в четных вершинах цикла. 6. Вычтем величину θ из перевозок в четных вершинах цикла и прибавим ее к перевозкам в нечетных вершинах. Получен новый опорный план. Далее вновь переходим к пункту 2. Продемонстрируем метод потенциалов на примере. Продолжим решение задачи, в которой рассмотрены методы нахождения первого опорного плана. Напомним, что за опорное решение мы решили принять решение, полученное при расчете методом двойного предпочтения. 54 Придадим потенциалу U2 значение 0, а остальные потенциалы для занятых клеток определим из системы уравнений, удовлетворяющих условию (5): U 2  V1  3 , U1  V4  11, U 3  V3  2, U 2  V4  15 , U1  V2  3 , U 3  V4  8. U 2  V5  8 , Из этой системы, подставляя в нее значение U 2  0 , найдем остальные потенциалы и запишем их в таблицу. Например, V1  3  0  3 , V4  15  0  15 и т. д. Получим таблицу. Таблица 5 Потенциалы V1 = 3 V2 = 7 U1 = – 4 4 U2 = 0 3 U3 = – 7 Потребности 20 21 7 20 21 V3 = 9 V4 = 15 3 4 4 7 4+ 2 7 7 V5 = 8 Запасы 11 9 40 19 +15 8 30 2 8 15 10 3 24 8 8 Проверим выполнение условия оптимальности (6) для опорного плана, полученного методом двойных предпочтений: U1  V1  1  4 , U1  V3  5  4; 13  1 , U1  V5  7  9; U 2  V2  7  4; 22  3 , U 2  V3  9  7; 23  2 , U 3  V1   4  7, U 3  V2  0  4 , U 3  V5  1  15 . План не является оптимальным, так как имеются нарушения условий (6) в клетках A1-B3, A2-B2 и A2-B3. Наибольшая невязка (нарушение) равна δ22 = 3, следовательно, пересчет начинаем с клетки A2-B2. Этой клетке присваивается первый номер и строится цикл пересчета по правилам, изложенным выше. Все клетки, в которых лежат вершины цикла, последовательно нумеруются, четным вершинам приписывается знак «–», а нечетным «+». Величина сдвига по циклу находится как минимальное значение из всех перевозок в четных вершинах цикла и равна q  min 21,2  2 (табл. 5). Она вычитается из перевозок в четных вершинах цикла и прибавляется к перевоз- 55 кам в нечетных. Получаем новый план, для которого вновь находим потенциалы и проверяем условия (6): Таблица 6 Потенциалы V1 = 3 U1 = – 1 U2 = 0 U3 = – 4 20 Потребности V2 = 4 V3 = 6 4 3 3 19 4 7 2 4 20 4 + 7 21 U1  V1  2  4 , 24 40 15 8 30 15 10 + U 3  V2  0  4 , U 2  V4  12  15 , U1  V5  7  9 , 8 U 3  V1  1  7 , U 2  V3  6  7 , U1  V3  5  4; 13  1 , Запасы 9 8 8 3 7 V5 = 8 11 2 7 21 V4 = 12 U 3  V5  4  15 . План не является оптимальным, так как условие (6) не выполняется в клетке A1-B3 с невязкой δ13 = 1, следовательно, пересчет начинаем с клетки A1B3. Величина сдвига по циклу q  min 21, 7   7 вычитается из перевозок в четных вершинах цикла и прибавляется к перевозкам в нечетных. Получаем новый план (табл. 7), для которого вновь находим потенциалы и проверяем условия оптимальности. Из приведенного примера видно, что фактически цикл пересчета освобождает «невыгодные» клетки с большой стоимостью или, по крайней мере, уменьшает величину перевозки в таких клетках. Таблица 7 Потенциалы V1 = 3 4 U1 = – 1 U2 = 0 V3 = 5 3 19 20 V4 = 12 4 7 3 V5 = 8 9 15 8 14 4 7 8 7 4 2 8 15 10 20 Запасы 11 2 U3 = – 4 Потребности V2 = 4 21 7 24 40 30 10 8 Опорный план оптимален, так как все невязки равны нулю (отсутствуют): 56 U 1  V1  2  4 , U 2  V3  5  7 , U 3  V1  1  7 , U 3  V3  1  2 , U 1  V5  7  9 , U 2  V4  12  15 , U 3  V2  0  4 , U 3  V5  4  15 . Вычисляем функцию цели: F  X опт   19  3  7  4  14  11  20  3  2  4  8  8  10  8  451.  0 19 7 14 0   Ответ: X опт   20 2 0 0 8 , → F  X опт   451.  0 0 0 10 0   6.5. Открытая транспортная задача Транспортная задача называется открытой, если запасы груза превышают потребности в нем, или если потребности невозможно удовлетворить имеющимися запасами. Для решения задачи в этих случаях вводят фиктивного потребителя или поставщика груза, на которого и записывают недостающее количество груза или потребности в нем. Стоимости перевозок от фиктивных станций полагаются равными нулю. Тогда задача становится закрытой и решается методом потенциалов. Для примера ниже (табл. 8) приведена задача, в которой введен фиктивный (реально не существующий) потребитель В5, позволяющий вывезти все грузы из пунктов А1, А2, А3. Таблица 8 Потребители В1 Поставщики А1 А2 А3 Потребности В2 5 В3 9 В4 4 В5 * 11 10 Запасы 40* 21 7 15 6 14 10 6 35 7 5 5 40 30 25 40 35 25 50 50 70 40 В данном примере построен опорный план по методу наименьшей стоимости. Фиктивный потребитель и перевозка, равная грузу, который фактически ос- 57 тается на станции А1, помечены звездочкой. Задача, записанная в таблице, является закрытой и ее решение можно довести до получения оптимального плана. 6.6. Проблема вырожденного плана задачи Опорный план транспортной задачи называется невырожденным, если число базисных ячеек равно r = n + m – 1, где m – количество строк, n – количество столбцов транспортной задачи. Если число перевозок меньше чем r = n + m – 1, то такой план называется вырожденным. При определении первого опорного плана нередко возникает ситуация, когда число занятых клеток меньше величины m + n − 1. Тогда система уравнений, удовлетворяющих условию (5), не позволит определить потенциалы потребителей и поставщиков. Решение проблемы рассмотрим на примере другой транспортной задачи, исходные данные которой представлены в табл. 9. При построении опорного плана методом северо-западного угла в клетку А1-В1 была внесена перевозка x11 = 50, при этом первая строка и первый столбец были вычеркнуты одновременно (что и привело к вырожденности плана). Такую клетку следует запомнить или отметить с тем, чтобы после заполнения всей таблицы ввести фиктивную перевозку в вычеркнутую строку или столбец, выбрав клетку с наименьшей стоимостью. В примере это клетка А1-В3, которая в дальнейших расчетах считается занятой с перевозкой равной нулю. Таблица 9 Потребители В1 Поставщики А1 5 В3 9 50 В4 В5 Запасы 4 11 8 6 14 12 10 6 19 21 А2 7 10 40 7 А3 Потребности В2 5 25 50 40 25 35 58 20 25 20 50 50 70 Вырожденность плана также может возникнуть при пересчете свободной клетки, если в четных вершинах цикла стоят равные по величине перевозки, совпадающие с величиной сдвига по циклу θ. В таком случае следует внести фиктивную перевозку, равную нулю, в ту из освобождающихся клеток, в которой стоимость меньше. 59 7. ТРАНСПОРТНАЯ ЗАДАЧА НА СЕТИ 7.1. Постановка задачи Задача минимизации затрат на перевозки или минимизации величины суммарного пробега может быть решена не только в матричной, но и в сетевой постановке. Такой метод обладает большей наглядностью, так как распределение грузопотоков наносят непосредственно на реальную сеть железной дороги. Станции погрузки, разгрузки и транзитные станции являются вершинами сети, а проездные участки ее дугами. На каждой дуге указывается стоимость перевозки единицы груза (или расстояние в километрах). Если затраты на перевозку между двумя станциями в прямом и обратном направлении различны, то между ними проводят две дуги с разной стоимостью. У вершин сети указывают количество груза на станциях отправителях и потребности в нем (со знаком минус) на станциях потребителях. Требуется так распределить грузопотоки, чтобы переместить весь груз с наименьшими затратами. 7.2. Математическая модель Обозначим перевозку от i-той станции на j-тую как xij. Так как необходимо учитывать возможность движения и в противоположном направлении xij, то число переменных задачи будет равно удвоенному числу дуг задачи. Ограничения задачи записываются исходя из условий баланса для каждой вершины – суммарный грузопоток на i-тую станцию минус суммарный поток из нее равен объему выгруженного груза (выгрузке) Ri на этой станции. Выгрузка для станций получателей положительна и равна потребности в грузах, а для отправителей отрицательна и равна по абсолютной величине запасов k k j 1 j 1  x ji   xij  Ri  i  1,2, ..., n  , (1) где k – число связей (дуг) для i-той вершины. При этом выполняется условие неотрицательности переменных: xij  0, (i  1, 2, ... n; j  1, 2, ..., n) . Функция цели задачи по критерию минимума суммарных затрат – 60 n n F ( x)    Cij xij  min. i 1 j 1 (2) Заметим, что данная модель не учитывает возможные ограничения на пропускную способность участков сети. Если возникает необходимость это учесть, то в условие задачи вводят дополнительные ограничения в виде неравенств xij ≤ dij, где dij – пропускная способность дороги на участке между станциями Bi и Bj. 7.3. Построение начального плана задачи Распределим перевозки так, чтобы весь груз был вывезен, все потребности удовлетворены. Грузовые потоки указываются стрелками вдоль дуг с величинами количества перевозимого груза. Введем обозначения: 45 30 – стоимость перевозки единицы продукции, – направление и количество грузоперевозки, (+60), (–20) – запасы или потребности грузов на i-той станции. Общее число загруженных дуг должно быть равно n – 1, где n – число вершин сети. Если загруженных дуг меньше, то следует ввести на одной из дуг фиктивную (нулевую) перевозку. Совокупность загруженных дуг не должна образовывать замкнутый цикл на сети, для этого по-возможности следует обеспечивать одного потребителя от одного поставщика. Рассмотрим такое распределение на примере. Пусть имеется схема железнодорожной сети, состоящей из десяти станций, для каждой указаны запасы груза (со знаком плюс) или потребности в нем (со знаком минус). На каждой дуге показана стоимость грузоперевозки единицы груза для соответствующего проездного участка. Объем запасов грузов на станциях B3, B6 и B9 равен количеству потребностей грузов на оставшихся станциях (рис. 1). 61 (–25) (–25) В2 В4 55 (–30) 45 В5 40 45 В7 40 30 В8 40 (–30) 45 50 45 45 (+55) (–30) (–35) В3 50 60 50 (+60) В1 В6 40 40 40 45 (+80) В9 В10 70 (–20) Рис. 1 Составим первоначальный план грузоперевозок для удовлетворения потребностей грузов на станциях сети и покажем непосредственно на схеме распределение грузопотоков. Вывезем груз со станции В9 (весь запас равен 55 ед.), 30 ед. на станцию В1, 5 ед. на станцию В8 (останется потребность 30 − 5 = 25 ед.), 20 ед. на станцию В10 (рис.2). (–25) (–25) В2 155 (+80) В4 155 55 40 В6 115 15 35 40 40 45 (–30) (+60) 25 В1 140 В3 115 50 45 45 40 25 30 (+55) 5 В9 100 60 50 (–30) (–35) 10 В8 145 40 30 30 В5 165 (–30) В7 175 40 45 50 45 45 20 70 В10 170 (–20) Рис. 2 Теперь вывезем груз (60 ед.) со станции В3: 25 ед. на станцию В2, 10 ед. на станцию В4 (осталось 25 − 10 = 15), 25 ед. на станцию В8 (весь груз на эту стан62 цию доставлен). Вывозим груз со станции В6: 15 ед. на станцию В4 (все потребности здесь удовлетворены), 30 ед. на станцию В7, 35 ед. на станцию В5 и т. д. В полученном начальном плане перевозок весь груз вывезен, и потребители получают необходимое им количество груза (рис. 2), при этом загружено девять дуг при десяти вершинах (план не вырожден). Суммарная стоимость перевозок равна F ( x)  15  40  25  40 10  40  35  50  30  60  25  30  30  40  5  45  20  70  9125 . Полученный план общей стоимости перевозок грузов, возможно, не является оптимальным. 7.4. Метод потенциалов улучшения плана Проверим полученный план перевозок методом потенциалов и при необходимости улучшим его. Введем условные величины, приписываемые каждой вершине сети и называемые потенциалами станций Vi. Их численные значения могут быть определены из решения двойственной к данной задаче. По теоремам двойственности план будет оптимальным, если выполнены условия: V j  Vi  cij (3) – для занятых дуг (базисных переменных); V j  Vi  cij (4) – для свободных дуг (свободных переменных). Таким образом, разность между потенциалами для двух станций, между которыми есть грузоперевозки, равна стоимости перевозок на этой дуге. Для свободных дуг она должна быть меньше или равна стоимости перевозок. Один из потенциалов следует задать произвольно, так же, как и в задаче в матричной постановке. Пусть V9 = 100, тогда, следуя по загруженным дугам, прибавляем к потенциалу стоимость перевозки при попутном грузопотоке и вычитаем стоимость при перемещении против потока, получим V1  100  40  140, V8  100  45  145, 63 V10  100  70  170, V3  145  30  115 (так как грузопоток идет в противоположном направлении), V2  115  40  155, V4  115  40  155, V6  155  40  115 (так как гру- зопоток идет в противоположном направлении), V7  115  60  175, V5  115  50  165 . Проверим выполнение условия оптимальности (3.4) на свободных дугах: V1  V2  155  140  15  45 , V4  V2  155  155  0  55 , V1  V3  140  115  25  50 , V1  V8  145  140  5  45 , V3  V5  165  115  50  40  35  10 , V4  V5  165  155  10  45 , V5  V7  175  165  10  45 , V10  V5  170  165  5  45 , V10  V8  170  145  25  45 , V10  V7  175  170  5  50 Условие оптимальности нарушено лишь на одной дуге В3 – В5 , для которой невязка δ35 = 10. Если таких дуг больше, то для пересчета необходимо выбрать дугу с наибольшей невязкой. Введем на дуге В3 – В5 перевозку x3 5 = θ, с направлением от вершины с меньшим потенциалом к вершине с большим, при этом образуется замкнутый цикл загруженных дуг В3 – В5 – В6 – В4 – В3 . Движение идет только по загруженным дугам, исключая одну незагруженную В3  В5 . Двигаясь в направлении вновь введенного грузопотока по циклу, отметим все перевозки в противопотоках и выберем из них минимальную. Присвоим это численное значение величине θ  min{10,35} 10 . Вычитая из всех противопотоков и прибавляя ко всем попутным потокам груза величину θ, получим новый опорный план задачи. Вычислим потенциалы вершин из условий (3) и убедимся, что условия (4) также выполняются. 64 (– 25) (– 25) В2 155 (+80) В4 145 55 40 В6 105 25 25 40 40 45 (– 30) (+60) 25 В1 140 45 В3 115 50 10 25 40 30 (+55) (– 30) В7 165 40 45 50 45 45 В9 100 В5 155 В8 (– 30) 145 40 5 60 50 (– 35) 45 30 30 20 В10 170 70 (– 20) Рис.3 Полученный оптимальный план представлен в таблице. Таблица 1 № ДУГИ ПЕРЕВОЗКИ 1 В9 – В1 30 2 В9 – В8 5 3 В9 – В10 20 4 В3 – В2 25 5 В6 – В5 25 6 В3 – В5 10 7 В3 – В8 25 8 В6 – В4 25 9 В6 – В7 30 Суммарная стоимость грузоперевозок является наименьшей и равна F ( x)  25  40  25  40  25  50  30  60  10  40  25  30  30  40  5  45  20  70  9025. 65 8. ЗАДАЧА ОБ ОПТИМАЛЬНОМ НАЗНАЧЕНИИ 8.1. Постановка задачи Пусть имеется n работ, которые могут выполнить n исполнителей. Известны затраты Cij (i, j = 1, 2, …, n) при назначении i-того исполнителя на j-тую работу. Требуется так распределить исполнителей по работам, чтобы все работы выполнялись, все исполнители были заняты и суммарные затраты при производстве работ были минимальны. Предполагается, что каждый исполнитель выполняет одну работу и каждая работа будет поручена одному исполнителю. 8.2. Математическая модель Обозначим назначение i-того исполнителя на j-тую работу, как xij. Тогда       х11  х12  х13  ...  х1n  1, x21  x22  x23  ...  x2 n  1, (1)              xn 1  xn 2  x n 3  ...  xn n  1. С другой стороны, каждая работа будет поручена одному исполнителю.        х11  х21  х31  ...  хn1  1 , x12  x22  x3 2  ...  xn 2  1 ,  x1n  x2 n  x3n  ...  xn n  1 , xij  0, i  1,2,... n; j  1,2,... n (2) 1, если i  ю работу выполняет исполнитель j; Кроме того: xij   0, если i  ю работу не выполняет исполнитель j. Функция цели задачи по критерию минимума суммарных затрат: n f (X )   n  C i j xi j  min. i 1 j 1 Очевидно, что данная задача сводится к транспортной задаче, если запасы и потребности равны единице. Как правило, число исполнителей равно числу работ, т. е. рассматривается закрытая задача. Если это условие не выполняется, то вводят либо фиктивного исполнителя, либо фиктивную работу, в результате задача становится закрытой, а в полученном оптимальном 66 назначении одна работа не будет выполнена, либо один исполнитель будет простаивать. Исходные данные задачи записываются в таблицу. Таблица 1 Исполнители B1 Работы А1 А2 c11 x11 x12 x21 cn2 … cn3 c2n 1 … … xn3 1 1 x2n … xn2 1 … x23 cn1 c1n x1n c23 … Запасы Bn … x13 x22 xn1 … c13 c22 … Потребности B3 c12 c21 … Аn B2 … cnn 1 xnn 1 1 1 Здесь А 1 , А 2 , …, А n – работы, В 1 , В 2 , …, В n – исполнители. Так как «запасы» и «потребности» всегда равны 1, то при решении их не принято писать, кроме того величины «перевозок» также равны 1, поэтому занятые клетки можно просто отметить каким-либо образом. Рассмотрим пример задачи о назначениях размерности n = 5. В табл. 2 приведен первый опорный план, построенный по методу северо-западного угла. Таблица 2 Исполните- В1 ли В2 В3 В4 В5 Работы А1 А2 А3 А4 12 8 14 10 24 11 15 22 7 30 25 21 26 26 18 15 8 (1) (1) 20 (1) 11 17 67 (1) А5 6 5 9 9 19 (1) В таблице пять заполненных клеток при необходимых для решения методом потенциалов – девяти. Это означает, что план вырожден 4 раза. Такой особенностью обладают все планы задачи об оптимальном назначении. В результате стандартные методы решения транспортной задачи неэффективны и часто приводят к зацикливанию. Рассмотрим «венгерский метод» решения задачи. 8.3. Решение задачи о назначениях венгерским методом Теорема Кенига. Если к стоимостям какой-либо строки (столбца) задачи о назначениях прибавить одно и то же число, то оптимальный план не изменится. Алгоритм решения, основанный на теореме Кенига: 1) выбрать в каждой строке минимальный элемент и вычесть его из всех элементов этой строки; 2) если в каком-нибудь столбце не появилось нулей, то из всех элементов такого столбца вычитается минимальный элемент этого же столбца; 3) рассматривается множество нулей таблицы и, если оно допустимо, то задача решена, иначе переходим к пункту 4; 4) минимальным числом прямых по строкам и столбцам вычеркиваются все нули, а из невычеркнутых элементов выбирается минимальный элемент α ; 5) величина α вычитается из невычеркнутых и прибавляется к дважды вычеркнутым элементам, после чего переходим к пункту 3. Замечание Допустимое множество нулей определяется следующим образом. Нулевой элемент в таблице с номером ij означает возможность выполнения i-тым исполнителем всей работы j. Поэтому расположение нужного количества нулей в таблице должно позволить выбрать единственным способом распределение всех работ между всеми исполнителями. 68 Сформулируем правило нахождения оптимального решения задачи о назначениях, в которой целевая функция минимизируется. Рассмотрим решение задачи на примере. Пусть задана матрица стоимости выполнения работ, причем для пяти работ имеется пять исполнителей. 1. Выберем в каждой строке матрицы наименьший элемент и вычтем его из каждого элемента этой строки. 2. Выберем столбцы, в которых нет нулей и найдем в них наименьший элемент. Затем вычтем его из каждого элемента столбца.  12 8 14 10 24  4    11 15 22 7 30   4  20 25 21 26 26    0     11 17 18 15 8  3 6  1 5 9 9 19    8 5 9 6 15 1 10 4 2 6 7 4 16  4   23  4 6  0   0  3 1 14   8 5 9 5 14 9 3 2 6 7 4 16   23  6 .  0  14  3. Попробуем составить опорное решение из нулей, входящих в полученную матрицу. Но допустимого множества нулей не получено. В частности, выбрав один из нулей во втором столбце, например, верхний (работа А1 распределена второму исполнителю), мы не сможем использовать нижнюю строку с оставшимся нулем. Это означает, что работа А5 останется нераспределенной. 4. Вычеркиваем все нули, проведя наименьшее число прямых, проходящих через все нули в матрице. Среди незачеркнутых найдем наименьший элемент, это элемент α = 1 (он дважды подчеркнут в получившейся матрице), вычитаем его из всех невычеркнутых и прибавляем ко всем дважды вычеркнутым элементам матрицы. 4  4 0  3  1  8 5 5 14 2 6 9 9 3 7 4 16   23  6   0  14    69 3 0  3 8 0 6   3 10  0 0  4 2 13 7 9 8 2 4 15   22  6   0  13   5. Снова пытаемся составить опорное решение. Допустимое множество нулей получено (выделено двойным подчеркиванием). Из таблицы следует, что первый исполнитель выполняет работу 5, второй – работу 1 и т. д. Запишем решение в виде матрицы X min 0 0   0  0 1  1 1 1 0 0  0 .  1 0  Возвращаясь к исходной матрице, вычисляем минимальное значение функции цели F ( Х min )  F ( X ) min  8  1  7  1  21  1  8  1  6  1  50 . 8.4. Решение задачи максимизации Известно, что переход от задачи минимизации к задаче максимизации в линейном программировании достигается изменением знака функции цели. F  X  max   F1  X  min следовательно, данную задачу на нахождение максимума F ( X ) можно превратить в задачу минимизации, заменив знаки всех элементов в матрице стоимостей. Далее решение находим методом, рассмотренным выше. Пусть известен доход, который можно получить при назначении каждого исполнителя i (i = 1, 2, …, n) на любую работу j ( j = 1, 2, …, n). Найдем распределение исполнителей, которое принесет максимальную прибыль. Дана матрица  12 8 14 10 24     11 15 22 7 30   20 25 21 26 26  , меняя знаки, имеем    11 17 18 15 8   6 5 9 9 19    70   12  8  14  10    11  15  22  7   20  25  21  26    11  17  18  15  6 5 9 9   24    30   26  .  8   19  Прибавим к элементам всех строк модуль максимального элемента этой же строки, а затем проделаем шаги 1 и 2.  12   19  6   7  13  16 10 14 15 8 23 1 1 5 3 14 10 10 0  6 15   0  13 14 0 0    10  1  7 13 0   10 8 5 10 0  23 0  0 . 3 10  10 0  14 Множества допустимых нулей в матрице нет, следовательно, продолжаем решение.  6 15 10 14 0     13 14 8 23 0  0 0 5 0 0    1 0 0 3 10   7 13 10 10 0    0  7 0  1 1  9 8 4 2 5 8 17 3 7 4 4 0   6    0   1 0 0   6 16 9 4 8 7 1 16 5 3 6 3 3 1  0  7   17  0  Получили оптимальное решение. Вычислим максимум функции цели, наложив эти нули на исходную матрицу. 0 6  1  2 0  8 3 7 6 15 5 5 2 3 2 1  0  8   18  0  F  X max   12  22  26  17  19  96 . Первый исполнитель выполняет первую работу, второй – четвертую, третий  вторую и т. д. 71 9. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ВЕРОЯТНОСТЕЙ 9.1. Случайные величины Случайной называют величину, которая в результате испытания примет одно и только одно возможное значение, наперед не известное и зависящее от случайных причин. Дискретной называют случайную величину, которая принимает отдельные, изолированные значения с определенными вероятностями. (ДСВ) Непрерывной называют случайную величину, которая может принимать все значения из некоторого промежутка. (НСВ) Закон распределения ДСВ X можно записать в виде таблицы X x1 x2 … xn P p1 p2 … pn где p1  p2  ...  pn  1 . Если закон распределения известен, то мы можем находить вероятность события «случайная величина X приняла значение xk» P ( X  xk )  pk . Соответственно, P( X  xk или X  xm или X  xs )  pk  pm  ps . Всегда можно считать, что НСВ X принимает значения на промежутке (, ) . Если Вы хотите работать с НСВ, то нужно уметь вычислять вероятность события «случайная величина X приняла значение из интервала (a,b)»: P ( a  X  b) . Задать НСВ – это значит задать способ вычислять вероятность P ( a  X  b) . НСВ можно задать двумя способами. 72 Способ 1. С помощью функции распределения, под которой понимают такую функцию F(x), что P( X  b)  F (b) . Если F(x) задана, то P(a  X  b)  F (b)  F (a) , P(a  X )  1  F (a) . Рис. 9.1 Функция распределения непрерывной случайной величины Способ 2. С помощью плотности распределения вероятности f(x), под которой понимают производную функции распределения F(x), т.е. F ( x )  f ( x ) . Если плотность распределения известна, то b P (a  X  b)   f ( x) dx , a b P ( X  b)   f ( x) dx ,   P(a  X )   a 73 f ( x) dx . Рис. 9.2. Плотность распределения вероятности непрерывной случайной величины Замечание. Очевидно, что для любой НСВ X и любого с P( X  с)  0 . 9.2. Числовые характеристики случайных величин Математическое ожидание для ДСВ M ( X )  x1 p1  x2 p2    xn pn , для НСВ  M (X )   xf ( x)dx .  Дисперсия для ДСВ и НСВ D( X )  M  X  M ( X )  , 2 D( X )  M ( X 2 )   M ( X )  . 2 Среднее квадратичное отклонение (СКО) для ДСВ и НСВ  ( X )  D( X ) . Свойства мат ожидания. 74 1. Если C=const, то M (С )  С ; 2. M ( X )   M ( X ) ; 3. M ( X  Y )  M ( X )  M (Y ) ; 4. Если СВ X и Y являются независимыми, то M ( XY )  M ( X ) M (Y ) . Свойства дисперсии. 1. Если C=const, то D(C )  0 ; 2. D ( X )   2 D( X ) ; 3. Если СВ X и Y являются независимыми, то D( X  Y )  D( X )  D(Y ) ; для произвольных СВ X и Y будет справедливо соотношение D( X  Y )  D( X )  D(Y )  2cov( X , Y ) . 4. Для любой СВ X справедливо D( X )  0 . Смысл математического ожидания и дисперсии. Пусть даны две лотереи: 1) Есть 100 билетов, среди них 10 билетов дают выигрыш 4 рубля, 20 других билетов дают выигрыш 3 рубля, остальные билеты проигрышные. 2) Есть 100 билетов, среди них 1 билет дает выигрыш 100 рублей, остальные билеты проигрышные. В какую лотерею «выгоднее» играть, если у Вас есть возможность приобрести только один билет? Неограниченно много билетов? Чему равна «справедливая» цена за билет для каждой из этих лотерей? Рассмотрим случайные величины X1 и X2 – величина выигрыша при покупке одного билета в лотереях 1 и 2. X1 4 3 X2 100 P 0,1 0,2 0,7 P 0,01 0,99 75 M ( X 1 )  4  0,1  3  0, 2  0  0,7  1 , M ( X 2 )  100  0,01  0  0,99  1 . X 12 16 9 X 22 10000 P 0,1 0,2 0,7 P 0,01 0,99 M ( X 12 )  16  0,1  9  0,2  0  0,7  3, 4 , M ( X 22 )  10000  0,01  0  0,99  100 , D( X 12 )  M ( X 12 )   M ( X 1 )   2,4 , D( X 22 )  M ( X 22 )   M ( X 2 )   99 . 2 2 Математическое ожидание выигрыша равно справедливой цене билета. При такой цене участники лотереи и ее владелец ничего не проигрывают и не выигрывают. Дисперсия показывает риск проигрыша. Чем больше дисперсия, тем выше риск. 9.3. Теоретический коэффициент корреляции Пусть даны две случайные величины X и Y. Если они независимые, то мы знаем, что M ( XY )  M ( X ) M (Y ) . Это не верно, если они зависимы. Поэтому величина cov( X , Y )  M ( XY )  M ( X ) M (Y ) является мерой зависимости между X и Y. Она называется ковариацией. Если ковариация равна нулю, то это означает, что X и Y независимы. Чем сильнее ковариация отличается от нуля, тем больше зависимость. Ковариация плоха тем, что она зависит от единиц измерения величин X и Y. Чтобы избавиться от этого недостатка, используют коэффициент корреляции  XY  cov( X , Y ) .  ( X ) (Y ) 76 Коэффициент корреляции играет очень важную роль. Он является основным показателем тесноты линейной связи между случайными величинами. Свойства коэффициента корреляции. 1. Коэффициент корреляции  xy принимает значения от 1 до 2. При  xy  1 связь между X и Y является линейной функцио- 1 . нальной зависимостью (самая сильная связь); 3. При  xy  0 линейная корреляционная связь между X и Y от- сутствует; 4. При  xy  0 корреляционная связь между X и Y является пря- мой, т.е. Y увеличивается при увеличении X, а при  xy  0 – обратной, т.е. Y уменьшается при увеличении X. 9.4. Основные вероятностные распределения Нормальное распределение f ( x)  1 e  2  ( x  m )2 2 2 , где m – математическое ожидание,  – среднее квадратичное отклонение. 77 Рис. 9.3. Плотность распределения вероятности нормального распределения Центральная предельная теорема. Сумма достаточно большого числа независимых случайных величин имеет приближенно нормальное распределение при любом распределении слагаемых. Чем больше случайных величин суммируется. тем точнее приближение. Нормальное распределение реализовано в Microsoft Excel с помощью функции НОРМРАСП(x; m; ; интегральная), которая возвращает значение плотности распределения в точке x , если интегральная=”ложь”(0); возвращает значение функции распределения, если интегральная=”истина”(1). Тогда P{a  X  b}  НОРМРАСП  b; m; ;1  НОРМРАСП  a; m; ;1 . Распределение χ2 Пусть X1, X2, …, Xk – независимые случайные величины, имеющие стандартное нормальное распределение, то есть нормальное распределение с m  0 , D  1 . Тогда говорят, что случайная величина  2 (k )  X 12  ...  X k2 имеет распределение χ2 (хи-квадрат) с k степенями свободы. С увеличением числа слагаемых в сумме распределение χ2 постепенно приближается к нормальному распределению. 78 Рис. 9.4. Плотность распределения вероятности распределения χ2 Распределение χ2 реализовано в Microsoft Excel с помощью функции ХИ2РАСП(x, k), которая возвращает вероятность того, что случайная величина, имеющая распределение χ2 с k степенями свободы, больше, чем число x. Т.е. F 2 ( x)  1  ХИ 2 РАСП (x, k) , P(a  X  b)  F 2 (b)  F 2 (a)  ХИ 2 РАСП (a, k)-ХИ 2 РАСП (b, k) Распределение Стьюдента Пусть X1, X2, …, Xk – независимые случайные величины, имеющие стандартное нормальное распределение, то есть нормальное распределение с m=0, D=1, тогда про случайную величину, равную T (k )  X0 ( X  ... X k2 ) / k 2 1 говорят, что она имеет распределение Стьюдента с k степенями свободы. Это симметричное распределение, похожее на стандартное нормальное распределение. При любых k основная часть графика лежит в интервале (-3; 3), так как при x  3 плотность распределения Стьюдента близка к нулю. 79 Рис. 9.5. Плотность распределения вероятности нормального распределения Распределение Стьюдента реализовано в Microsoft Excel с помощью функции СТЬЮДРАСП(x, k, a), которая возвращает вероятность того, что случайная величина, имеющая распределение Стьюдента с k степенями свободы, больше x , если a=1, и лежит вне интервала (-x,x), если a=2. Параметр a – коли- чество «хвостов», может принимать только два значения: a=1 и a=2. Т.е. FT ( x)  1  СТЬЮДРАСП (x, k,1) , P ( a  X  b)  FT (b)  FT ( a )  СТЬЮДРАСП (a, k,1)-СТЬЮДРАСП (b, k,1) Распределение Фишера Пусть X1, X2, …, Xk и Y1, Y2, …, Ys – независимые случайные величины, имеющие стандартное нормальное распределение, то есть нормальное распределение с m=0, D=1, тогда про случайную величину, равную F (k , l )  ( X 12  ...  X k2 ) / k (Y12  ...Ys2 ) / s 80 говорят, что она имеет распределение Фишера (F-распределение) с k и s степенями свободы. Рис. 9.6. Плотность распределения вероятности нормального распределения В программе Microsoft Excel распределение Фишера реализовано при помощи функции FРАСП(х, k, s), которая возвращает вероятность того, что случайная величина, имеющая распределение Фишера с k и s степенями свободы, больше x . 81 10. ОСНОВНЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОЙ СТАСТИКИ 10.1. Основные определения Математическая статистика – это раздел математики, который изучает методы сбора, систематизации, обработки результатов наблюдений массовых случайных явлений. Любое множество, подлежащее изучению в статистике, называется ге- неральной совокупностью (ГС). Любое подмножество генеральной совокупности называется выборкой. Количество элементов в генеральной совокупности или в выборке называется объемом. Элементы выборки могут характеризоваться числами, отражающими какой-либо признак изучаемого объекта. Эти числа называются вариантами, так как от выборки к выборке эти значения меняются. Первым шагом в обработке полученных данных является составление статистического (вариационного) ряда. Статистический ряд – это таблица, в которой перечислены варианты в порядке возрастания и указаны соответствующие им частоты и относительные частоты. Пример. Допустим, мы хотим изучить вопрос о том, насколько трамваи пользуются спросом у жителей Екатеринбурга и для этого мы опросили 10 человек. В ходе опроса спрашивали: сколько поездок в месяц Вы совершаете на трамвае? В этом примере: Генеральная совокупность – все жители Екатеринбурга; Выборка – те люди, которых мы опросили; Объем генеральной совокупности – примерно 1,5 млн. чел; Объем выборки – 10 чел; Варианты – число поездок на трамвае в месяц. Пусть получены след. результаты опроса: 82 0, 44, 6, 25, 0, 44, 0, 31, 0, 50. Тогда статистический ряд имеет вид: Варианта 6 25 31 44 50 Частота 4 1 1 1 2 1 Относительная 0,4 0,1 0,1 0,1 0,2 0,1 частота Выборка должна быть репрезентативной, т.е. её свойства должны отражать свойства генеральной совокупности. Для этого она должна быть случайной, т.е., все элементы генеральной совокупности должны иметь одинаковые шансы попасть в неё, и попадание в выборку одного элемента не должно влиять на попадание другого элемента. Зачем нам нужна выборка? Очевидно, мы хотим по полученной выборке делать какие-то суждения относительно всей генеральной совокупности. Однако, здесь возникает вопрос: возможно ли это? Если да, то о каких именно суждениях может идти речь? Чтобы ответить на эти вопросы, нужно про «все это» думать следующим образом: 1) генеральная совокупность – это случайная величина; 2) выборка – конкретные значения (реализации) случайной величины. Тогда основная задача статистики будет заключаться в том, что по нескольким конкретным значениям случайной величины необходимо получить значения числовых характеристик (например, мат. ожидания и дисперсии) этой случайной величины и ее закон распределения. Разумеется, получить точные значения невозможно и если взять другую выборку, то результат будет другим. Поэтому речь идет о получении приближенных значений, которые называют оценками. 83 Значение числовых характеристик для случайной величины, представляющей генеральную совокупность, будем называть истинными или теоре- тическими характеристиками, а их оценки называются выборочными или эмпирическими характеристиками. Замечание. Выборочная характеристика зависит от выборки, но выборка (репрезентативная) выбирается случайно, поэтому всякая выборочная характеристика сама по себе является случайной величиной и можно говорить о ее мат. ожидании, дисперсии, распределении и т.д. 10.2. Точечные оценки теоретических характеристик Что значит быть «хорошей» оценкой? Оценка называется несмещенной, если ее математическое ожидание равно истинному значению оцениваемой величины. Оценка называется эффективной в некотором классе оценок, если она имеет наименьшую дисперсию по сравнению с любой другой оценкой в данном классе оценок. Оценка называется состоятельной, если ее дисперсия стремиться к нулю, когда число наблюдений стремится к бесконечности. Основные характеристики выборки Пусть из некоторой генеральной совокупности получена выборка X x1 x2 … xn Для этой выборки можно рассмотреть следующие выборочные характеристики: 1) выборочное среднее (оценка мат. ожидания) x x i, n 2) неисправленная выборочная дисперсия (смещенная оценка дисперсии) DB (x  x ) (X )   i n 2 x  2 i n  x2, 3) исправленная выборочная дисперсия (несмещенная оценка дисперсии) 84 DBиспр ( X )  n DB ( X ) n 1 4) выборочные средние квадратичные отклонения (исправленное и неис- правленное) S ( X )  DB ( X ) , S испр ( X )  DBиспр ( X ) . Оценки 1) – 4) являются точечными оценками. Утверждение 1. Выборочная средняя X является несмещенной оценкой математического ожидания случайной величины X , поскольку  x  1 1 1 M ( X )  M   i    M ( xi )   M ( X )  nM ( X )  M ( X ) . n n  n  n Утверждение 2. Выборочная средняя X является состоятельной оценкой математического ожидания случайной величины X , поскольку  x  1 1 1 1 D( X )  D   i   2  D( xi )  2  D( X )  2 nD( X )  D( X )  0 n n n  n  n при n   . Утверждение 3. Выборочная неисправленная дисперсия будет смещенной оценкой дисперсии случайной величины X. Можно показать, что M  DB ( X )   n 1 D( X ) . n Исправленная дисперсия является несмещенной оценкой теоретической дисперсии. При больших объемах выборки разница между исправленной и неисправленной дисперсиями мала. 10.3. Интервальные оценки Интервальной называют оценку, которая определяет интервал, внутри которого находится оцениваемый параметр. 85 Пусть для выборки объема n случайной величины X получена оценка m некоторого истинного параметра μ. Рассмотрим промежуток длины 2∆ с серединой в точке m и обозначим через α вероятность того, что неизвестный истинный параметр μ расположен внутри интервала  x  , x    , т.е. Pm      m     . Промежуток 2∆ называется доверительным интервалом. Величина ∆ называется точностью. Величина α называется доверительной вероятностью или надежностью. Возникают три задачи 1)построение доверительного интервала по заданной надёжности α; 2) определение надёжности α при заданной точности ∆, 3) определение минимального количество испытаний n, обеспечивающих необходимые надёжность α и точность ∆. Интервальная оценка для математического ожидания. Пусть случайная величина X (генеральная совокупность) распределена нормально и для выборки объема n получено выборочное среднее x и пусть истинное значение мат. ожидания случайной величины X равно μ. Рассмотрим случайную величину T x  , S n где S – исправленное среднее квадратичное отклонение. Можно доказать, что случайная величина T имеет распределение Стьюдента с k = n-1 степенями свободы. Это означает, что P  tk ,  T  tk ,    , где tk , – такое значение случ. величины, что вероятность попадания хотя бы в один из «хвостов», отсекаемых этим числом равна 1-α, т.е. tk ,  СТЬЮДРАСПОБР(1- ,k) . 86 Таким образом,   x  P  tk ,   tk ,    , S n   t S t S  P  x  k ,    x  k ,    . n n   Мы построили доверительный интервал по заданной надёжности α, т.е. с вероятностью α истинное значение математического ожидания лежит в интервале tk , S t S  ; x  k ,  . x  n n   Замечание. Случайными величинами являются концы интервала, поэтому более точно было бы сказать, что с вероятностью α доверительный интервал накрывает истинное значение математического ожидания. 87 11. ПРОВЕРКА СТАТИСТИЧЕСКИХ ГИПОТЕЗ 11.1. Вводный пример Рассмотрим гипотезу Н0: все вороны черные; при альтернативной гипотезе Н1: есть хотя бы одна белая ворона. Если у нас есть выборка из n ворон, то всегда легко понять подтверждает она или опровергает гипотезу Н0: 1) если выборка содержит только черных ворон, то она под- тверждает гипотезу Н0; 2) если выборка содержит хотя бы одну белую ворону, то она опровергает гипотезу Н0. Если выборка подтверждает гипотезу Н0, то говорят, что у нас нет осно- ваний отвергнуть гипотезу Н0 или, коротко, гипотеза Н0 не отвергается. Также в этом случае можно говорить, что гипотеза Н0 принимается (это не значит, что она верна!). Если выборка подтверждает гипотезу Н1, то говорят, что гипотеза Н0 от- вергается в пользу альтернативной гипотезы Н1. Рассмотрим теперь гипотезу Н0: белых ворон столько же сколько и чер- ных; при альтернативной гипотезе Н1: количество белых ворон составляет20% от всех ворон. Пусть в выборке из 10 ворон обнаружилось 4 белые вороны. Вопрос: такая выборка подтверждает или опровергает гипотезу Н0? Попробуем понять, как правильно отвечать на такой вопрос. Рассмотрим случайную величину K – количество белых ворон в выборке. Распределение случайной величины K является дискретным и зависит от того, какая из гипотез верна. Это распределение можно посчитать, используя формулу Бернулли 88 P ( K  m)  n! p m (1  p)nm , (n  m)!m! где n – объем выборки, m – количество белых ворон в выборке, p – вероятность появления белой вороны при выборе одной вороны. Если гипотеза Н0 верна, то p=0,5 и при n=10 закон распределения случайной величины K имеет вид: К Р 1 2 3 4 5 6 7 8 9 10 0,001 0,0098 0,0439 0,1172 0,2051 0,2461 0,2051 0,1172 0,0439 0,0098 0,001 Если верна альтернативная гипотеза, то p=0,2 и при n=10 закон распределения случайной величины K имеет вид: K 1 2 3 4 5 6 7 8 9 10 P 0,1074 0,2684 0,3020 0,2013 0,0881 0,0264 0,0055 0,0008 0,0001 0,0000 0,0000 Нужно придумать правило по которому мы будем принимать решение о том, принять или отвергнуть гипотезу Н0. Например, такое Правило 1. Если для данной выборки K  3 , то будем считать, что ги- потеза Н0 принимается, если же K  3 , то будем считать, что гипотеза Н0 отвергается в пользу гипотезы Н1. Если будем действовать по правилу 1, то мы можем ошибиться. Мы можем совершить одну из двух ошибок: 1) отвергнуть верную гипотезу Н0; 2) принять неверную гипотезу Н0. Ошибка 1) называется ошибкой первого рода, ошибка 2) называется ошибкой второго рода. Вероятность ошибки первого рода обозначают через α, вероятность ошибки второго рода обозначают через β. Вычислим α и β. Если верна гипотеза Н0, то распределение величины K имеет вид 89 9 10 0,001 0,0098 0,0439 0,1172 0,2051 0,2461 0,2051 0,1172 0,0439 0,0098 0,001 К Р 1 2 3 4 5 6 7 8 Если верна гипотеза Н1, то распределение величины K имеет вид K 1 2 3 4 5 6 7 8 9 10 P 0,1074 0,2684 0,3020 0,2013 0,0881 0,0264 0,0055 0,0008 0,0001 0,0000 0,0000 Поэтому для правила 1 α=0,001+0,0098+0,0439+0,1172=0,172; β=0,0881+0,0264+0,0055+0,0008+0,0001+0,0000+0,0000=0,121. Попробуем другое правило. Правило 2. Если для данной выборки K  2 , то будем считать, что ги- потеза Н0 принимается, если же K  2 , то будем считать, что гипотеза Н0 отвергается в пользу гипотезы Н1. Если верна гипотеза Н0, то распределение величины K имеет вид К Р 1 2 3 4 5 6 7 8 9 10 0,001 0,0098 0,0439 0,1172 0,2051 0,2461 0,2051 0,1172 0,0439 0,0098 0,001 Если верна гипотеза Н1, то распределение величины K имеет вид K 1 2 3 4 5 6 7 8 9 10 P 0,1074 0,2684 0,3020 0,2013 0,0881 0,0264 0,0055 0,0008 0,0001 0,0000 0,0000 Поэтому для правила 2 α=0,001+0,0098+0,0439=0,055; β = 0,1172+0,0881+0,0264+0,0055+0,0008+0,0001+0,0000+0,0000=0,322. Те значения K, при которых гипотезу Н0 отвергаем, будем называть критической областью. Нельзя выбрать критическую область так, чтобы и α и β были малы. Поэтому поступают следующим образом: выбирают и фиксируют значение α (его называют уровнем надежности), а затем выбирают критическую область так, 90 чтобы α не превышало зафиксированного значения, а β при этом было наименьшим. Рассмотрим теперь гипотезу Н0: белых ворон столько же сколько и черных; при альтернативной гипотезе Н1: количество белых ворон не равно количеству черны. Здесь все намного сложнее, чем в предыдущем случае, поскольку мы не знаем, как распределена случайная величина K, если верна гипотеза Н1. Она может быть распределена бесконечным числом способов, в зависимости от того каков на самом деле процент белых ворон. Это означает, что выбирать критическую область (при заданном уровне значимости α) нужно так, чтобы минимизировать все возможные значения β, если верна гипотеза Н1. 11.2. Точные определения и утверждения На основе собранных в статистических исследованиях данных после их обработки делаются выводы об изучаемых явлениях. Эти выводы делаются путём выдвижения и проверки статистических гипотез. Статистической гипотезой называется любое утверждение о виде или свойствах распределения наблюдаемых в эксперименте случайных величин. Статистические гипотезы проверяются статистическими методами. Проверяемая гипотеза называется основной (нулевой) и обозначается Н0. Кроме нулевой выдвигается ещё и альтернативная (конкурирующая) гипотеза Н1, отрицающая основную. Таким образом, в результате проверки будет принята одна и только одна из гипотез, а вторая будет отвергнута. Пример 1. Сравнение исправленной выборочной дисперсии с гипотетической генеральной дисперсией нормальной совокупности. Пусть из нормально распределенной генеральной совокупности X сделана выборка объема n и по данной выборке найдена исправленная выборочная 91 испр дисперсия Dвыб . Пусть D(X) – истинное значение дисперсии генеральной сово- купности X и D0 – некоторое положительное число. Требуется по данной выборке проверить гипотезу H 0 : D( X )  D0 . В качестве альтернативной гипотезы может выступать H1 : D( X )  D0 или H1 : D( X )  D0 или H1 : D( X )  D0 . Типы ошибок. Выдвинутая гипотеза проверяется на основании выборки, полученной из генеральной совокупности. Из-за случайности выборки в результате проверки не всегда получается правильный вывод. При этом могут возникать следующие ситуации: 1. Основная гипотеза верна и она принимается. 2. Основная гипотеза верна, но она отвергается. (ошибка первого рода) 3. Основная гипотеза не верна и она отвергается. 4. Основная гипотеза не верна, но она принимается. (ошибка второго ро- да) Вероятность ошибки первого рода называется уровнем значимости и обозначается α. Вероятность ошибки второго рода обозначают через β. Статистический критерий. Для проверки гипотезы используют случайную величину K, значения которой зависят от выборки. Случайная величина K называется статистической характеристикой, статистическим критерием или просто статистикой. 92 Наблюдаемым (эмпирическим) значением критерия называют значение критерия, вычисленное по данной выборке. Множество значений статистики K можно разделить на два непересекающихся подмножества:  подмножество значений статистики, при которых гипотеза Н0 не отклоняется, называется допустимой областью;  подмножество значений статистики, при которых гипотеза Н0 отклоняется и принимается гипотеза Н1, называется критической обла- стью. Основной принцип проверки статистических гипотез: если наблюдаемое значение критерия принадлежит критической области, то нулевую гипотезу отвергают; если наблюдаемое значение критерия принадлежит допустимой области, то нулевую гипотезу не отвергают (говорят, что нет оснований для отклонения гипотезы). Определение критической области Критическими точками Kкр называются точки, которые отделяют критическую область от области принятия гипотезы. Правосторонняя критическая область – критическая область, определяемая неравенством K>Kкр. Левосторонняя критическая область – критическая область, определяемая неравенством KKправ,кр и K< Kлев,кр. Выбор области принятия гипотезы и критической области зависит от того, какую именно гипотезу мы проверяем и то, какая гипотеза выбирается в качестве альтернативной. Величина 1–β называется мощностью критерия. Т.е. мощность критерия – это вероятность попадания критерия в критическую область при условии, что справедлива конкурирующая гипотеза. 93 Пример 1 (продолжение). Сравнение исправленной выборочной дисперсии с гипотетической генеральной дисперсией нормальной совокупности (продолжение). В данном примере статистика K имеет вид испр (n  1) Dвыб K . D0 Можно доказать, что так определенная статистика имеет распределение χ2 (при условии, что верна гипотеза H0), поэтому для заданной выборки ее значе2 . ние обозначается через  набл 1) Пусть проверяется гипотеза H 0 : D( X )  D0 при альтернативной гипотезе H1 : D( X )  D0 , тогда критическая область будет правосторонней K   кр2   кр2 ( , k ) , где α – уровень значимости, k=n-1 – число степеней свободы;  кр2 ( , k ) – критическое значение критерия, т.е. это такое число, что вероятность того, что СВ, имеющая распределение χ2 с k степенями свободы, примет значение большее, чем  кр2 ( , k ) равно α. 2) Пусть проверяется гипотеза H 0 : D( X )  D0 94 при альтернативной гипотезе H1 : D( X )  D0 , тогда критическая область будет левосторонней K   кр2   кр2 (1   , k ) , где α – уровень значимости, k=n-1 – число степеней свободы;  кр2 (1   , k ) – критическое значение критерия, т.е. это такое число, что вероятность того, что СВ, имеющая распределение χ2 с k степенями свободы, примет значение меньшее, чем  кр2 (1   , k ) равно α. 3) Пусть проверяется гипотеза H 0 : D( X )  D0 при альтернативной гипотезе H1 : D( X )  D0 , тогда критическая область будет двусторонней 2 2 2 2 K   лев ,кр   кр (1   / 2, k ) или K   прав , кр   кр ( / 2, k ) . где α – уровень значимости, k=n-1 – число степеней свободы;  кр2 ( / 2, k ) и  кр2 (1   / 2, k ) определяются так же как выше. 95 96 12. ПАРНАЯ ЛИНЕЙНАЯ РЕГРЕССИЯ 12.1. Выборочная корреляция Выборочная ковариация cov( X , Y )    ( xi  x )( yi  y ) n xi yi n xy. Выборочный коэффициент корреляции rB  rxy  cov( x, y ) . S ( X )  S (Y ) Смысл обозначений (см. лекцию 2) x x i n , DB (x  x ) (X )   i n 2 x  2 i n  x 2 , S ( X )  DB ( X ) . В программе Excel есть функция КОРРЕЛ для вычисления коэффициента корреляции. Выборочный коэффициент корреляции rxy является оценкой для истинного коэффициента корреляции  xy . Проверка значимости коэффициента корреляции Выборочный коэффициент корреляции rxy отличается от теоретического коэффициента корреляции  xy . В частности, если rxy не равен нулю, то это еще не говорит о том, что  xy также отличен от нуля. Для того чтобы установить наличие значимой линейной связи между X и Y, следует проверить гипотезу о статистической значимости коэффициента корреляции rxy . В этом случае используется следующая нулевая гипотеза: H 0 :  xy  0, при альтернативной гипотезе H1 :  xy  0. 97 Для проверки H 0 по выборке  x , y  ,  x , y  ,...,  x , y  1 1 2 2 n n объема n необ- ходимо вычислить выборочный коэффициент корреляции rxy , а затем наблюдаемое значение критерия Tнабл  rxy n  2 1  rxy2 . Если H 0 верна, то статистика Тнабл имеет распределение Стьюдента с   n  2 степенями свободы. При помощи функции СТЬЮДРАСПОБР по заданному уровню значимости  и числу степеней свободы  определяем критическую точку tкр  t ,  СТЬЮДРАСПОБР( , ) . Если Tнабл  t , , то нет оснований для отклонения H 0 . Если Tнабл  t , , то H 0 отклоняется в пользу альтернативной гипотезы H1 . Если H 0 отклоняется, то фактически это означает, что коэффициент корреляции статистически значим (существенно отличен от нуля). Следовательно, Х и Y – коррелированны, т.е. между ними существует линейная связь. 12.2. Уравнение регрессии. Метод наименьших квадратов (МНК) Пусть случайные величины Х и Y связаны соотношением Y    X  , где α и β – заданные числа (параметры модели), ε – случайная величина. Такое уравнение называется теоретическим уравнением регрессии, ε называется слу- чайным членом регрессии, Y называется зависимой переменной регрессии, X – объясняющей переменной регрессии (регрессором, фактором). Пусть у нас есть результаты наблюдений величин Х и Y (выборка): X x1 x2 … x n Y y1 y2 … yn 98 Задача регрессионного анализа состоит в получении оценок a и b для параметров  и  по выборочным данным ( xi , yi ) . Так как нам доступна лишь некоторая выборка из генеральной совокупности, по которой точные значения параметров  и  определить невозможно, то мы можем найти только оценки для  и  , которые, естественно, будут отличаться от истинных значений параметров. Уравнение, содержащее оценки a и b , называется эмпирическим уравне- ние линейной регрессии: y* ( x)  a  bx . y* ( x) будем называть прогнозным значением величины Y при заданном значении X. Теоретическое и эмпирическое уравнения могут быть записаны для каждого наблюдения Yi     X i   i , yi*  yi* ( x)  a  bxi , i  1,2,, n. Остаток в i-ом наблюдении – разность между i-ым наблюдаемым значением величины Y и ее прогнозным значением ei  yi  yi* . Очевидно, что чем меньше величина остатков, тем лучше полученные оценки a и b . Минимизировать остатки можно различными способами, но наиболее общеупотребительным и хорошо разработанным является метод, основанный на минимизации суммы квадратов остатков: n n i 1 i 1 S  e12  e22  ...  en2   ei2 ; S (a, b)    yi   a  bxi   . 99 2 Рис. 12.1. Возможные положения регрессионной прямой Метод наименьших квадратов (МНК) – метод нахождения оценок па- раметров регрессии, основанный на минимизации суммы квадратов остатков всех наблюдений. Заметим, что данное выражение S ( a, b) является квадратичной функцией от a и b . Если предположить, что значения ( xi , yi ) зафиксированы, то влиять на величину S можно, изменяя значения a и b . Для того чтобы величина S (a, b) была минимальной, необходимо, чтобы частные производные равнялись нулю, то есть n S  2 ( yi  (a  bxi ))  0, a i 1 n S  2 ( yi  (a  bxi )) xi  0. b i 1 Эти уравнения известны как нормальные уравнения для коэффициентов регрессии. Используя обозначение для средних значений, эти уравнения можно переписать в виде: a  bx  y , ax  b 1 1 xi2   xi yi .  n n Решая полученные уравнения относительно a и b , находим 100 1  xi yi  x  y n b , 1 2 2  xi  x n a  y  bx . Можно записать b S Cov( x, y )  rxy y . Dx Sx В программе Excel для нахождения оценок a и b используются функции ОТРЕЗОК и НАКЛОН. Почему метод МНК работает? Теорема Гаусса – Маркова. Пусть для теоретического уравнения рег- рессии Yi     X i   i выполнены условия: 1) εi – случайная величина, Xi – неслучайная (детерминированная) величина; 2) M(εi)=0 для всех значений i; 3) дисперсия εi не зависит от i, т.е. D(εi)=σ для всех значений i; 4) εi и εj не коррелированны, т.е. cov(εi, εj)=0 для всех значений i  j . Тогда оценки параметров α и β, полученные по МНК будут несмещенными, состоятельными и эффективными в классе линейных несмещенных оценок. 12.3. Основное тождество дисперсионного анализа. Коэффициент детерминации Пусть по выборке  x , y  ,  x , y  ,...,  x , y  1 1 2 2 n n уравнение регрессии yi*  yi* ( x)  a  bxi . 101 построено эмпирическое После того как найдено уравнение линейной регрессии, необходимо оценить его качество. Очевидно, справедливо равенство yi  y   yi*  y    yi  yi*  . Возведем обе части этого равенства в квадрат и просуммируем по i :   yi  y  2    yi*  y   2 2 Можно проверить, что  y i y * i  y  yi  yi*     yi  yi*  . 2  yi*  yi*  y   0 и мы получаем основное дисперсионное тождество регрессионного анализа   yi  y  2    yi*  y     yi  yi*  . 2 2 Суммы, которые содержатся в этом тождестве имеют специальные названия, представленные в таблице.  y i  y  y 2 * i  y  y 2 i Сумма квадратов Общая (полная) отклонений объясненная сумма квадратов от- регрессией (объясненная клонений сумма, регрессионная 2 Остаточная (необъясненная) сумма квадратов отклонений сумма) Σобщ  yi*  Σрег Σост Коэффициент детерминации R 2 – это отношение объясненной суммы квадратов к общей, т.е. R2  y  y    y  y  * i 2 2 i    рег . общ Коэффициент детерминации характеризует долю дисперсии результативного признака, объясняемую регрессией, в общей дисперсии результативного признака. Соответственно, величина 102 1  R2  y  y    y  y  * 2 i 2 i i    ост общ характеризует долю дисперсии y , вызванную влиянием остальных неучтенных в модели факторов. Отметим, что коэффициент детерминации R 2 связан с коэффициентом корреляции rxy соотношением R 2  rxy2 . Коэффициент детерминации может принимать значения от 0 до 1. Равенство R 2  0 возможно тогда и только тогда, когда  рег  0 . Это означает, что дисперсия результативного признака вызвана исключительно влиянием неучтенных в модели факторов. Другой крайний случай R 2  1 означает точную подгонку: все наблюдаемые значения лежат на регрессионной прямой. Чем ближе к 1 значение R 2 , тем лучше качество подгонки, y* более точно аппроксимирует наблюдаемые значения yi . 12.4. Проверка значимости уравнения регрессии Проверка значимости линейной регрессионной модели сводится к проверке нулевой гипотезы H 0 :   0 (модель незначима) при альтернативной гипотезе H1 :   0 (модель значима). Чтобы проверить H 0 по выборке  x , y  ,  x , y  ,...,  x , y  1 1 2 2 n n объема n , необходимо вычислить наблюдаемое значение критерия Fнабл   рег  (n  2) ост  R 2 (n  2) . 1  R2 Если H 0 верна, то статистика Fнабл имеет распределение Фишера со степенями свободы 1 и (n  2) . При помощи функции FРАСПОБР по заданному 103 уровню значимости  и степеням свободы 1 и (n  2) определяем критическую точку Fкр  F  ,1, n  2   FРАСПОБР  ,1, n  2  . Если Fнабл  Fкр с некоторым уровнем значимости  (обычно берут   0,05 ), то нулевая гипотеза отвергается и регрессия считается значимой. В противном случае нет оснований для того чтобы отвергнуть нулевую гипотезу, поэтому полученное уравнение регрессии считается незначимым. Замечание. Для парной линейной регрессии гипотеза H 0 :   0 равносильна гипотезе H 0 :  xy  0 . То есть значимость линейной регрессионной моде- ли равносильна наличию линейной корреляции между X и Y. 12.5. Доверительные интервалы для коэффициентов регрессии Стандартная ошибка оценки b определяется по формуле mb   S2 xi  x  2 . Доверительный интервал для коэффициента регрессии  при заданном уровне значимости  определяется как b  t ( , n  2)  mb . Это означает, что коэффициент  b  t ( , n  2)  mb ; b  t ( , n  2)  mb   принадлежит интервалу с вероятностью 1   . Например, при   0,05 такой интервал называют 95% доверительным интервалом. Стандартная ошибка параметра a определяется по формуле: ma  S 2 x  n   x  x 2 i 2 . i Доверительный интервал для параметра a при заданном уровне значимости  определяется по формуле: a  t ( , n  2)  ma . 12.6. Инструмент «Регрессия» программы Excel 104 Рис. 12.2. Диалоговое окно «Регрессия» Замечание. Обратите внимание, что интервалы $C$1:$C$9 и $B$1:$B$9 содержат заголовки столбцов, а не только числовые данные (для этого ставим флажок Метки). Это удобно при отображении результатов проводимого анализа. 105 Рис. 12.3. Результаты применения инструмента «Регрессия» Поскольку терминология, используемая в Microsoft Excel, несколько отличается от той, которая принята в российской научной литературе, то укажем соответствие между введенными ранее величинами и значениями на рисунке. Величина Ячейка Коэффициент корреляции rxy F5 Коэффициент детерминации R2 F6 Стандартная ошибка регрессии S F8 Регрессионная сумма Σрег G13 Остаточная сумма Σост G14 Общая сумма Σобщ G15 Наблюдаемое значение F-статистики Fнабл I13 Коэффициент регрессии a F18 Коэффициент регрессии b F19 Стандартная ошибка ma G18 Стандартная ошибка mb G19 Доверительный интервал для  J18-K18 Доверительный интервал для  J19-K19 106 13. ПАРНАЯ НЕЛИНЕЙНАЯ РЕГРЕССИЯ 13.1. Виды нелинейных регрессий Если между экономическими явлениями существуют нелинейные соотношения, то они выражаются с помощью нелинейных функций. Различают два класса нелинейных регрессий: регрессии, нелинейные относительно объясняющих переменных, но линейные по оцениваемым параметрам (нелинейные по переменным); регрессии, нелинейные по оцениваемым параметрам (нелинейные по параметрам). Также рассматривают внутренне нелинейные регрессии, однако мы ограничимся двумя вышеуказанными типами. Примером нелинейной регрессии по включенным в нее объясняющим переменным могут служить следующие функции: логарифмическая y     ln x   ; равносторонняя гипербола y    x  . К нелинейным регрессиям по оцениваемым параметрам относятся функции: степенная y   x ; экспоненциальная y   x . Для оценки параметров перечисленных выше регрессий можно воспользоваться методом наименьших квадратов для парной линейной регрессии, который был подробно рассмотрен в предыдущей главе. Однако для этого необходимо выполнить линеаризацию нелинейного уравнения, т.е. привести его к линейному виду. 107 13.2. Линеаризация нелинейных регрессий Рассмотрим более подробно процесс линеаризации для каждого вида зависимости. Пусть дана выборка {(x1, y1), (x2, y2),…, (xn, yn)}. Наша задача заключается в построении эмпирического уравнения регрессии по этим данным, т.е. в получении наилучших оценок a и b для теоретических параметров и. Логарифмическая регрессия y     ln x   . Линеаризация производится путем замены x  ln x (здесь и всюду далее штрих играет роль метки и не связан с дифференцированием). Это приводит к тому, что исходная выборка  x, y  ,  x , y  ,...,  x , y  , где 1 1 2 2 n n заменяется новой выборкой xi  ln xi и исходное уравнение становится ли- нейным: y     x   . Его параметры могут быть оценены по выборке  x, y  i i с помощью МНК для линейной регрессии, т.е. по формулам b cov( X , Y ) , a  y  bx . Dx В результате получим эмпирическое уравнение регрессии y*  a  b ln x . Гиперболическая регрессия y     x  . Линеаризация производится путем замены x  что исходная выборка заменяется новой выборкой где xi  1 . Это приводит к тому, x  x, y  ,  x , y  ,...,  x , y  , 1 1 2 2 n n 1 и исходное уравнение становится линейным: xi y     x   . Его параметры могут быть оценены по выборке МНК для линейной регрессии, т.е. по формулам 108  x, y  i i с помощью b cov( X , Y ) , a  y  bx . Dx В результате получим эмпирическое уравнение b y*  a  . x Степенная регрессия y   x   . Эта модель относится к моделям нелинейным по параметрам. Линеаризация производится путем логарифмирования обеих частей уравнения: ln y  ln( x   ) , ln y  ln    ln x  ln  . После выполнения замены   ln  , y  ln y , x  ln x ,    ln  получаем линейное уравнение y      x    . При этом исходная  x, y  ,  x , y  ,...,  x , y  , где 1 1 2 2 n n выборка заменяется новой yi  ln yi , xi  ln xi . Параметры уравнения могут быть оценены по выборке  x, y  щью МНК для линейной регрессии, т.е. по формулам b выборкой cov( X , Y ) , c  y  bx ( c – оценка для  ). Dx В результате получим эмпирическое уравнение ln y*  c  b ln x . После потенцирования будем иметь * eln y  ec eb ln x . Наконец, вводя обозначение a  ec , приходим к уравнению y*  axb . Экспоненциальная регрессия y   x . 109 i i с помо- Линеаризация производится путем логарифмирования обеих частей уравнения: ln y  ln( x ) , ln y  ln   x ln   ln  . После выполнения замены   ln  , y  ln y ,   ln  ,    ln  получаем линейное уравнение y     x    . При этом исходная  x , y  ,  x , y  ,...,  x , y  , где 1 1 2 2 n n выборка заменяется новой выборкой yi  ln yi . Параметры уравнения могут быть оценены по выборке  x , y  i i с помо- щью МНК для линейной регрессии, т.е. по формулам d cov( X , Y ) , c  y  bx ( c – оценка для  , d – оценка для  ). Dx В результате получим эмпирическое уравнение ln y*  c  dx . После потенцирования будем иметь * eln y  ec edx . Наконец, вводя обозначение a  ec , b  e d приходим к уравнению y*  ab x . 13.3. Выбор нелинейной зависимости В случае парной регрессии выбор вида зависимости обычно осуществляется по графическому изображению реальных статистических данных в виде точек, которое называется корреляционным полем. Для того, чтобы по корреляционному полю подобрать вид зависимость, необходимо знать, как выглядит ее график. Приведем изображения графиков зависимостей, которые были рассмотрены выше. 110 Рис. 13.1. График логарифмической зависимости y  a  b ln x Свойства логарифмической зависимости существенно зависят от знака коэффициента b . Если b  0 , то логарифмическая функция возрастает и выпукла вверх, а если b  0 , то убывает и выпукла вниз. Рис. 13.2. График гиперболической зависимости y  a  111 b x Свойства гиперболической зависимости существенно зависят от знака коэффициента b . Если b  0 , то гиперболическая функция возрастает и выпукла вверх, а если b  0 , то убывает и выпукла вниз. Рис. 13.3. График степенной зависимости y  a  xb Свойства степенной зависимости существенно зависят от значения коэффициента b . Если b  1, то степенная функция возрастает и выпукла вниз, если 0  b  1, то она возрастает и выпукла вверх, а если b  0 , то она убывает и выпукла вниз. 112 Рис. 13.4. График показательной зависимости y  a  b x Свойства показательной зависимости существенно зависят от значения коэффициента b . Если b  1, то функция возрастает и выпукла вниз, если 0  b  1, то она убывает и выпукла вниз. При выборе вида зависимости также необходимо иметь ввиду, что обычно степенная функция моделирует зависимости с постоянной эластичностью; показательная функция моделирует зависимости с постоянным темпом роста; логарифмическая функция моделирует зависимости с постоянным уменьшением прироста; гиперболическая функция моделирует зависимости с нижним или верхним пределом. 113 14. МНОЖЕСТВЕННАЯ ЛИНЕЙНАЯ РЕГРЕССИЯ 14.1. Основные понятия Множественный регрессионный анализ является развитием парного регрессионного анализа применительно к случаям, когда зависимая переменная связана более чем с одной независимой переменной. Рассмотрим, например, следующую модель спроса на продукты питания y   0  1 x   2 p   , где y – общая величина расходов на питание, x – располагаемый личный доход (первый регрессор), p – цена продуктов питания (второй регрессор). Очевидно, что такая модель будет более точной, чем парная регрессия, связывающая y только с x или только с p . Для геометрической иллюстрации этой зависимости необходима трехмерная диаграмма с осями y , x и p . Основание диаграммы содержит оси x и p , и если пренебречь текущим влиянием случайного члена, то координата показывает величину y , соответствующую произвольному сочетанию x и p . Учет случайного члена приводит к тому, что фактическое значение y не будет лежать на данной плоскости. Точки, построенные по данной выборке ( xi , pi , yi ) , представляют собой трехмерный аналог поля корреляции, которое мы ранее использовали при рассмотрении парной регрессии. При этом вместо линии регрессии имеем плоскость регрессии. Уравнение для данной плоскости имеет вид y  b0  b1 x  b2 p, где b0 , b1 , b2 являются оценками неизвестных параметров  0 , 1 ,  2 . Соответствующая трехмерная диаграмма может выглядеть, например так, как показано на рис. 14.1. 114 Рис. 14.1. Трехмерная корреляционная диаграмма Из этого примера видно, что визуальный анализ даже в случае двух факторных переменных становится очень сложным. В случае большего числа переменных он практически неосуществим. 14.2. Оценка коэффициентов регрессии по МНК для двух независимых переменных Рассмотрим случай, когда имеются две независимые переменные x (1) и x (2) (два регрессора), и будем рассматривать линейную регрессионную модель вида: y   0  1  x (1)   2  x (2)   , для которой попытаемся построить уравнение регрессии: y  b0  b1  x (1)  b2  x (2)  e. В этом случае для каждого наблюдения должны быть известны значения каждого регрессора x (1) , x (2) и значения зависимой переменной y . Следовательно, множество значений регрессоров будет представлять матрицу с двумя столбцами и n строками, при этом нижний индекс изменяеться от 1 до n и определять номер измерения, а верхний индекс принимает два значения 1 или 115 2, в зависимости от номера регрессора. В этом случае матрица значений будет иметь вид  x1(1)  (1)  x2 X     x (1)  n x1(2)   x2(2)  .   (2)  xn  Аналогичным образом значения переменной y будут задаваться вектором-столбцом  y1  y   2 Y  .     y   n Обозначим через yi* прогнозируемое значение по уравнению регрессии yi*  b0  b1 xi(1)  b2 xi(2) , i  1, n , а остаток в i -м наблюдении будет: ei  yi  yi*  yi   b0  b1 xi(1)  b2 xi(2)  , i  1, n . Как и для случая парной регрессии будем минимизировать сумму квадратов остатков: n S  e  e  ...  e   ei2 . 2 1 2 2 2 n i 1 Необходимым условием первого порядка для минимума есть равенство нулю всех частных производных по всем параметрам S S S  0,  0,  0. b0 b1 b2 Данные условия имеют следующий вид: 116 n S  2 ( yi  (b0  b1  xi(1)  b2  xi(2) ))  0, b0 i 1 n S  2 xi1  ( yi  (b0  b1  xi(1)  b2  xi(2) ))  0, b1 i 1 n S  2 xi2  ( yi  (b0  b1  xi(1)  b2  xi(2) ))  0. b2 i 1 Эти уравнения также называются нормальными уравнениями для коэффициентов регрессии и, в данном случае, имеется три уравнения с тремя неизвестными значениями b0 , b1 и b2 . Применяя обозначения для средних значений, подобные парной регрессии, из первого уравнение можно легко выразить значение величины b0 через b1 и b2 , тогда b0  y  b1  x (1)  b2  x (2) . Используя это выражение и два других уравнения, путем преобразований можно получить следующее выражение для других элементов регрессии: b1  b2  Cov( x (1) , y ) D( x (2) )  Cov( x (2) , y )Cov( x (1) , x (2) ) D( x ) D( x )  Cov( x , x ) (1) (2) (1) (2) 2 Cov( x (2) , y ) D( x (1) )  Cov( x (1) , y )Cov( x (1) , x (2) ) D( x ) D( x )  Cov( x , x ) (1) (2) (1) (2) 2 , . 14.3. Оценка коэффициентов по МНК для множественной регрессии Модель множественной линейной регрессии – это линейная модель зависимости между переменными, содержащая более двух независимых переменных (регрессоров): y   0  1 x (1)   2 x (2)  ...   k x ( k )   . Парная регрессии, а также случай двух независимых переменных являются частным случаем множественной регрессии, а следовательно, все ре- 117 зультаты, которые будут получены нами далее распространятся и на эти частные случаи. В модели множественной регрессии за изменение зависимой переменной регрессии y отвечают некоторые экономические факторы – объясняющие переменные (регрессоры) x (1) , x (2) , …, x ( k ) . Параметры множественной регрессии 1 ,  2 ,...,  k показывают степень влияния на зависимую переменную экономических факторов, обозначенных соответствующими регрессорами. Как и в случае парной линейной регрессии, основная задача заключается в оценке неизвестных значений, то есть получении b0 , b1 , b2 ,..., bk , при этом эмпирическое уравнение регрессии будет иметь вид: y *  b0  b1 x (1)  b2 x (2)  ...  bk x ( k ) . В общем случае, если имеется k различных регрессоров, то матрица наблюдений будет иметь вид:  x1(1)  (1) x X  2   (1)  xn x1(2) x2(2) xn(2) x1( k )   x2( k )  ,   xn( k )  где xi( j ) – значение j-го регрессора в i-м испытании, i  1, n , j  1, k . Множество полученных значений зависимой переменной также как и для случая двух независимых переменных можно записать в виде векторастолбца. Оценим уравнение для данного множества наблюдений по методу наименьших квадратов. Это означает минимизацию суммы квадратов остатков, которые в данном случае имеют вид: ei  yi  yi*  yi   b0  b1 xi(1)  b2 xi(2)  ...  bk xi( k )  . Данное выражение в векторном виде будет: 118  e1   y1   b0   x1(1)  e   y   b   (1)  2    2    0    x2               (1)  en   yn   b0   xn x1( k )   b1     x2( k )   b2  .        xn( k )   bk  x1(2) x2(2) xn(2) Если добавить в матрице X столбец, состоящий из единиц, тем самым, расширив её до размера n   k  1  1 x1(1)  1 x2(1) X    (1)  1 xn x1( k )   x2( k )  ,   xn( k )  то значения остатков в векторном виде будут иметь вид:  e1   y1   1 x1(1) e   y   (1)  2    2    1 x2           (1)  en   yn   1 xn x1( k )   b0    x2( k )   b1  .     xn( k )   bk  Последнее выражение можно записать в матричном виде: e  Y  X b, Сумма квадратов отклонений может быть записана в матричном виде, как произведение вектора строки eT на вектор столбец e S  eT  e   y  X  b    y  X  b  . T Используя известные правила матричных операций, преобразуем значения суммы S   y  X  b    y  X  b    y T  bT  X    y  X  b  T  yT  y  bT  X T  y  yT  X  b  bT  X T  X  b   yT  y  2  bT  X T  y  bT  X T  X  b. Здесь воспользовались соотношениями  X  b T  bT  X ,  y  X  b   y T   X  b  , b T  X T  y  y T  X  b . T 119 T Теперь, чтобы минимизировать сумму квадратов отклонений, необходимо найти все частные производные и приравнять их нулю, то есть решить систему уравнений S S S S  0,  0,  0,...,  0. b0 b1 b2 bk В векторной форме система будет иметь вид S  0,  S S S S  где S   , , ,...,  - градиент функции S .     b b b b 1 2 k   0 Из этих уравнений можно легко найти свободный член: b0  y  b1 x (1)  b2 x (2)  ...  bk x ( k ) . Найдем вектор коэффициентов b . Очевидно, что: S    yT  y  2  bT  X T  y  bT  X T  X  b      yT  y   2  .  bT  X T  y     bT  X T  X  b  . Далее, вводя для удобства обозначения X T  y  p и X T  X  H , получаем   yT  y   0,  n  n   bT  p      b j  p j     b j  p j  p  X T  y ,  j 0  j 0   bT  H  b   2 H  b. Следовательно, S  2  X T  y  2   X T  X   b. Таким образом, уравнение S  0 равносильно уравнению X T  y   X T  X   b. Откуда b   X T  X  X T  y. 1 120 Здесь  X T  X  – матрица, обратная к матрице  X T  X  . 1 14.4. Условия применения МНК Рассмотрим теоретическое уравнение линейной множественной регрессии y   0  1 x (1)   2 x (2)  ...   k x ( k )   . Для индивидуальных наблюдений это уравнение будет иметь вид (2) (k ) y j   0  1 x (1) j   2 x j  ...   k x j   j , j  1, n. В предыдущем пункте мы получили формулы для эмпирических коэффициентов b0 , b1 , b2 ,..., bk при помощи МНК: b   X T  X  X T  y. 1 Однако возникает вопрос: насколько «хорошими» являются полученные оценки? Прежде всего, уточним, что понимать под «хорошей» оценкой. Оценка называется несмещенной, если ее математическое ожидание равно нулю. Оценка называется эффективной, если она имеет наименьшую дисперсию по сравнению с любыми другими оценками данных параметров. Оценка называется состоятельной, если ее дисперсия стремиться к нулю, когда число наблюдений стремится к бесконечности. Теперь, после уточнения понятия «хорошей» оценки, можно дать ответ на поставленный выше вопрос. Оценки b0 , b1 , b2 ,..., bk параметров модели множественной регрессии, полученные по МНК, является несмещенными, эффективными и состоятельными оценками, если выполнены следующие условия применения МНК: 1) Математическое ожидание случайного отклонения равно нулю, т.е. M  i   0 для любого i ; 2) Дисперсия  2 ( i ) не зависит от номера наблюдения i (гомоскедастичность); 121 3) cov( i ,  j )  0, если ij (отсутствие автокорреляции случайных отклонений); 4) Случайное отклонение должно быть независимо от объясняющих переменных, т.е. cov  xi( k ) ,  i   0 для любых i и k ; 5) Между объясняющими переменными отсутствует строгая (сильная) линейная зависимость ( отсутствие мультиколлинеарности); 6) Случайное отклонение имеет нормальное распределение. Таким образом, использование МНК является целесообразным только в том случае, когда случайная составляющая  удовлетворяет вышеуказанным условиям. При этом надо иметь ввиду, что мы не можем осуществить непосредственную проверку этих условий, поскольку теоретическая случайная составляющая  нам недоступна. В нашем распоряжении имеются только лишь остатки ei, которые сами являются реализацией для  . О том, как по величине остатков проверять выполнимость предпосылок МНК, будет рассказано ниже. 14.5. Спецификация модели Включение в уравнение множественной регрессии того или иного набора факторов связано прежде всего с представлением исследователя о природе взаимосвязи моделируемого показателя c другими экономическими явлениями. Факторы, включаемые во множественную регрессию, должны отвечать следующим требованиям: 1) быть количественно измеримыми; 2) факторы не должны быть коррелированы между собой и тем более находиться в точной функциональной связи. Отметим, что в случае нарушения второго требования обратная матрица ( X T X ) 1 не существует. Включение в модель факторов с высокой интеркорреляцией может привести к нежелательным последствиям – система нормальных уравнений 122 может оказаться плохо обусловленной, что повлечет за собой неустойчивость и ненадежность оценок коэффициентов регрессии. Если между факторами существует высокая корреляция, то нельзя определить их изолированное влияние на результативный показатель, и параметры уравнения регрессии оказываются неинтерпретируемыми. Несмотря на то, что теоретически регрессионная модель позволяет учесть любое число факторов, практически в этом нет необходимости. Отбор факторов проводится на основе качественного теоретико-экономического анализа. Однако качественный анализ часто не позволяет однозначно ответить на вопрос о количественной взаимосвязи рассматриваемых признаков и целесообразности включения фактора в модель. Поэтому отбор факторов обычно проводится в две стадии: на первой отбираются факторы исходя из сути проблемы; на второй – на основе матрицы показателей корреляции и оценок их статистической значимости. Коэффициенты интеркорреляции (т.е. корреляции между объясняющими переменными) позволяют исключать из модели дублирующие факторы. Считается, что две переменных явно коллинеарны, т. е. находятся между собой в линейной зависимости, если rxixj  0,7 xi . Для выявления коллинеарных факторов строят корреляционную матрицу 1 r  21  ...   rk 1 r12 1 ... rk 2 ... r1k  ... r2 k  , ... ...   ... 1  где rij – парные коэффициенты корреляции между регрессорами и x j . Поскольку одним из условий построения уравнения множественной регрессии является независимость действия факторов, то коллинеарность факторов нарушает это условие. Если факторы явно коллинеарны, то они дублируют друг друга и один из них необходимо исключить из регрессии. Исключе- 123 нию подлежит фактор, который менее коррелирован с зависимой переменной y. Включение в модель мультиколлинеарных факторов нежелательно по следующим причинам: 1) затрудняется интерпретация параметров множественной регрессии как характеристик действия факторов в «чистом» виде, ибо факторы коррелированы; параметры линейной регрессии теряют экономический смысл; 2) оценки параметров ненадежны, обнаруживают большие стандартные ошибки и меняются с изменением объема наблюдений (не только по величине, но и по знаку), что делает модель непригодной для анализа и прогнозирования. Отбор факторов, включаемых в регрессию, является одним и из важнейших этапов практического использования методов регрессии. При отборе факторов рекомендуется пользоваться следующим правилом: число включаемых факторов k обычно в 6-7 раз меньше объема совокупности n , по которой строится регрессия. 124 15. ПРОВЕРКА КАЧЕСТВА УРАВНЕНИЯ МНОЖЕСТВЕННОЙ РЕГРЕССИИ 15.1. Коэффициент детерминации Коэффициент детерминации R 2 , также как и для парной регрессии, является характеристикой тесноты связи между y и набором регрессоров x (1) , x (2) ,…, x ( k ) и определяется по формуле: R2    рег 1 общ где  общ  ( yi  y ) 2 ,  рег  ( yi*  y ) 2 и   ост , общ  ост  ( yi  yi* )2 . Как и для случая парной регрессии, множественный коэффициент корреляции изменяется в пределах от 0 до 1. Приближение R 2 к единице свидетельствует о сильной зависимости. Если R 2 мал по величине, то можно утверждать, что либо не все важные факторы взаимосвязи учтены, либо выбрана неподходящая форма уравнения. В случае парной регрессионной зависимости было показано, что коэффициент детерминации совпадает с квадратом выборочного коэффициента корреляции. В случае множественной регрессии коэффициент детерминации R 2 может быть определен по значениям парных коэффициентов корреляции следующим образом: 1 r10 R2  1  r20 ... rk 0 r01 1 r02 r12 r0 k r1k r21 1 ... r2 k ... ... ... ... rk1 rk 2 ... 1 1 r12 ... r1k r21 1 ... r2 k ... ... ... ... rk 1 rk 2 ... 125 .. .. 1 где rij – парные коэффициенты корреляции между регрессорами x ( i ) и x ( j ) , a ri 0 – парные коэффициенты корреляции между регрессором x ( i ) и y . В числители данной формулы находится обобщенный коэффициент корреляции, для всей системы переменных, а в знаменателе обобщенный коэффициент корреляции регрессоров. Рассмотрим частные случаи данной формулы. В случае парной зависимости формула имеет вид R2  1  1 r10 r01 1 1  r012 , что совпадает с формулой, полученной нами ранее. Для случая зависимости результативного признака от двух факторных признаков формула коэффициента множественной корреляции имеет вид: R2  1  r102  r202  2r102 r202 r122 . 1  r122 Коэффициент R 2 показывает абсолютный размер влияния регрессоров на зависимую переменную. При увеличении числа объясняющих переменных значение R 2 возрастает, поэтому данный показатель становится ненадежным. Скорректированный (нормированный) коэффициент детерминации R 2 накладывает штраф за увеличение числа независимых переменных. Этот коэффициент определяется следующим образом: R 2  1  1  R 2  n 1  ост   n  1 , 1 n  k 1  общ  n  k  1 где n – количество наблюдений, k – количество объясняющих переменных. Добавление объясняющей переменной в модель всегда уменьшает  ост , хотя бы незначительно. Если это уменьшение мало, то оно скорректи- руется уменьшением знаменателя и R 2 не изменится, в отличии от обычного 126 коэффициента детерминации R 2 , значение которого будет возрастать в любом случае. 15.2. Проверка значимости линейной регрессионной модели Проверка значимости линейной регрессионной модели, как и в случае парной регрессии, осуществляется с помощью критерия Фишера. Рассмотрим нулевую гипотезу H 0 : 1   2  ...   k  0 при альтернативной гипотезе H1 : среди коэффициентов 1 ,  2 ,...,  k хотя бы один отличен от нуля. Справедливость гипотезы H 0 означает, что модель незначима, соответственно, справедливость гипотезы H1 означает значимость модели. Чтобы проверить H 0 по имеющейся выборке объема n , необходимо вычислить наблюдаемое значение критерия Fнабл   рег   n  k  1  ост k  R 2   n  k  1 1  R   k 2 , Если H 0 верна, то статистика Fнабл имеет распределение Фишера со степенями свободы k и (n  k  1) . При помощи функции FРАСПОБР по заданному уровню значимости  и степеням свободы k и (n  k  1) определяем критическую точку Fкр  F  , k , n  k  1  FРАСПОБР  , k , n  k  1 . Если Fнабл  Fкр с некоторым уровнем значимости  (обычно берут   0,05 ), то нулевая гипотеза отвергается и регрессия считается значимой. В противном случае нет оснований для того чтобы отвергнуть нулевую гипотезу, поэтому полученное уравнение регрессии считается незначимым. 15.3. Сравнение «короткой» и «длинной» моделей Помимо проверки уравнения в целом можно также проверить значимость совместного вклада группы регрессоров. Предположим, что сначала оценивается регрессия с k независимыми переменными («короткая» модель): 127 y   0  1 x (1)   2 x (2)  ...   k x ( k )   . Остаточную сумму квадратов для этой модели обозначим через  кор ост . Затем добавляются еще q переменных и рассматривается регрессия с k  q независимыми переменными («длинная» модель): y   0  1 x (1)   2 x(2)  ...   k x( k )     k q x( k q )   . Остаточную сумму квадратов для этой модели обозначим через  длн ост . Разумеется, добавление дополнительных регрессоров x( k ) , x( k 1) ,, x( k q ) не ухудшает качество модели в том смысле, что, в силу очевидного соотношения  , коэффициент детерминации «длинной» модели не меньше  ост  ост длн кор коэффициента детерминации «короткой модели». Однако, если все коэффициенты  k 1 ,  k  2 ,...,  k  q равны нулю, то дополнительные регрессоры не оказывают какого-либо влияния на y и их включение в модель не является целесообразным. Для проверки значимости совместного вклада регрессоров x( k ) , x( k 1) ,, x ( k q ) рассмотривают нулевую гипотезу H 0 :  k 1   k  2     k  q  0 при альтернативной гипотезе H1 : среди коэффициентов  k 1 ,  k  2 ,...,  k  q хотя бы один отличен от нуля. Чтобы проверить H 0 по имеющейся выборке объема n , необходимо вычислить наблюдаемое значение критерия Fнабл    кор ост длн ост   ост длн q. (n  k  q  1) Если H 0 верна, то статистика Fнабл имеет распределение Фишера со степенями свободы q и (n  k  q  1) . При помощи функции FРАСПОБР по заданному уровню значимости  и степеням свободы q и (n  k  q  1) опре128 деляем критическую точку Fкр  FРАСПОБР  , q, n  k  q  1 . Если Fнабл  Fкр с некоторым уровнем значимости  (обычно берут   0,05 ), то нулевая гипотеза отвергается, следовательно, все дополнительные регрессоры признаются значимыми. В противном случае делается вывод о том, что дополнительные регрессоры не улучшают качество модели и их введение не целесообразно. 15.4. Оценка значимости коэффициентов регрессии по t-критерию Стьюдента В случае множественной регрессии, для каждого отдельного фактора используется формула оценки значимости tнабл, j  bj Sj где b j – коэффициент чистой регрессии при факторе x j , S j – стандартное квадратичное отклонение оценки коэффициента регрессии  j . Для уравнения множественной регрессии y*  a  b1 x1  b2 x 2  ...bp x p стандартное квадратичное отклонение оценки коэффициента регрессии может быть определено по следующей формуле: Sj  S y 1  Ryx2 1... xp 2 S xj 1  Rxjx 1... xp  1 , n  p 1 где S y – среднее квадратичное отклонение y , Ryx2 1... xp – коэффициент детерминации для уравнения множественной регрессии, S xj – среднее квадратич2 ное отклонение для признака x j , Rxjx 1... xp - коэффициент детерминации для за- висимости фактора x j со всеми другими факторами уравнения множественной регрессии, n – число наблюдений. Значение tнабл, j сравнивается с tкр  t ( , n  p  1) . Если tнабл, j  tкр , то коэффициент  j признается статистически значимым. 129 Доверительный интервал для коэффициента регрессии  j определяется как b j  t ( , n  p  1)  S j . Отметим, что условие tнабл, j  tкр равносильно тому, что доверительный интервал содержит ноль. Это означает, что если концы доверительного интервала для коэффициента регрессии  j имеют разные знаки, то коэффициент  j признается статистически незначимым. 15.5. Фиктивные переменные В большинстве случаев в модель регрессии включаются количественные факторные переменные. Однако при проведении некоторых исследований может возникнуть необходимость во включении в модель регрессии качественных факторных переменных. Это могут быть разного рода атрибутивные признаки, такие, например, как профессия, пол, образование, возраст, климатические условия, принадлежность к определенному региону. Для того, чтобы ввести такие переменные в регрессионную модель, им должны быть присвоены те или иные цифровые метки, т. е. качественные переменные необходимо преобразовать в количественные. Такого вида сконструированные переменные в эконометрике принято называть фиктивными переменными. Качественные признаки могут приводить к неоднородности исследуемой совокупности, что может быть учтено при моделировании двумя путями: – регрессия строится для каждой качественно отличной группы еди- ниц совокупности, т.е. для каждой группы в отдельности, чтобы преодолеть неоднородность единиц общей совокупности; – общая регрессионная модель строится для совокупности в целом, учитывающей неоднородность данных. В этом случае в регрессионную модель вводятся фиктивные переменные, т.е. строится регрессионная модель с переменной структурой, отражающей неоднородность данных. 130 Фиктивная переменная – это атрибутивная, или качественная, факторная переменная, которая может принимать только значения 0 и 1. Модель регрессии, включающая в себя в качестве факторной переменной фиктивную переменную, называется моделью регрессии с переменной структурой. В качестве примера модели регрессии с переменной структурой можно привести модель зависимости размера заработной платы от стажа работников с различным образованием (среднее, среднее специальное и высшее). Для включения факторной переменной в модель регрессии нужно использовать две фиктивные переменные, потому что количество фиктивных переменных в модели регрессии должно быть на единицу меньше чем значений качественной переменной. Общий вид модели размера заработной платы с фиктивными переменными: y*  a  bx  cz1  dz2 , где x – стаж (количественная факторная переменная), z1  1 для работников с высшим образованием и z1  0 для остальных, z2  1 для работников со средним специальным и z2  0 для остальных. 15.6. Нарушение предпосылок МНК Выше были указаны условия применимости метода МНК. Три первых условия касались случайной составляющей  . Напомним эти условия: 1) математическое ожидание случайного отклонения равно нулю, т.е. M  i   0 , для любого i ; 2) дисперсия  2 ( i ) не зависит от номера наблюдения i (гомоскедастичность); 3) cov( i ,  j )  0, если i  j (отсутствие автокорреляции случайных отклонений). Рассмотрим эти условия более подробно. 131 Первое условие означает, что нет постоянно действующего фактора, не включенного в модель, но оказывающего влияние на результативный фактор y . Другими словами, случайное слагаемое не должно иметь систематического смещения. Если постоянное слагаемое включено в уравнение регрессии, то можно считать, что это условие выполняется автоматически, так как роль постоянного слагаемого как раз и заключается в том, чтобы учитывать постоянную тенденцию показателя y , не учтенную в уравнении регрессии. Если не выполнено это условие, то оценки параметров уравнения регрессии, поученное с помощью МНК, будут неэффективными и смещенными. Второе условие означает, что дисперсия случайного слагаемого в каждом наблюдении имеет одно и то же значение. Другими словами, не должно быть априорной причины для того, чтобы в одних наблюдениях величина  была больше, чем в других, хотя на практике величина остатков уравнения регрессии в разных наблюдениях будет разной. Если дисперсии случайного слагаемого зависят от номера наблюдения, то оценки коэффициентов регрессии, полученные с помощью МНК, будут неэффективными и смещенными. Поэтому (по крайней мере, формально) можно получить более надежные оценки с использованием других методов. Например, с помощью обобщенного метода наименьших квадратов. Третье условие указывает, что между значениями случайного слагаемого в разных наблюдениях нет систематической связи, т.е. указывает на некоррелированность (на независимость) случайных слагаемых для разных наблюдений. Если это условие нарушается (например, для временных рядов), то имеет место автокорреляция остатков, оценки коэффициентов регрессии, полученные МНК, оказываются неэффективными. Существуют методы диагностирования и устранения автокорреляции. Поскольку случайная величина  недоступна для непосредственного наблюдения, то проверка выполнимости условий 1)-3) осуществляется на основе 132 анализа остатков ei  yi  yi* . Здесь, yi – наблюдаемые значения, yi* – значения, рассчитанные по уравнению регрессии. Условие 1) для остатков выполняется автоматически, т.к. e  y  y *  y  ( a  b  x)  y  ( y  b  x  b  x)  0 . 15.7. Проверка гомоскедастичности. Критерий Голдфелда-Квандта Нарушение гомоскедастичности называется гетероскедастичностью. В некоторых случаях явление гетероскедастичности можно обнаружить при помощи визуального анализа. Для этого удобно анализировать графики квадратов остатков. На рис. 15.1 приведены некоторые возможные ситуации. Рис. 15.1. Визуальный анализ квадратов остатков: а) – гомоскедастичные остатки; б)-д) – гетероскедастичные остатки Тест Голдфелда-Квандта. Наиболее популярным формальным критерием является критерий, предложенный С. Голдфелдом и Р. Квандтом. При проведении проверки по этому критерию предполагается, что стандартное отклонение пропорционально значению одной из факторных переменных z  x j в 133 этом наблюдении. Предполагается также, что случайный член распределен нормально и не подвержен автокорреляции. Тест Голдфелда-Квандта – тест на гетероскедастичность, устанавливающий, что стандартное отклонение остаточного члена регрессии растет, когда растет объясняющая переменная. Все наблюдений в выборке упорядочиваются по величине z , после чего оцениваются отдельные регрессии для первых m и для последних m наблюдений; средние  n  2m  наблюдений отбрасываются. Если предположение о гетероскедастичности верно, то дисперсия в последних m наблюдениях будет больше, чем в первых m , и это будет отражено в сумме квадратов остатков в двух указанных частных регрессиях. Обозначая суммы квадратов остатков в регрессиях для первых m и последних m наблюдений соответственно через ношение  m  k  1    1 ост и  2 ост рассчитаем от- 2 ост 1 , которое имеет распределение Фишера c  m  k  1 и ост степенями свободы, где k – число объясняющих переменных в рег- рессионном уравнении. Если данное значение превышает критическое значение F  m  k  1, m  k  1 , то нулевая гипотеза об отсутствии гетероскедастичности отклоняется. 134 Список использованных источников 2. Акулич И. Л. Математическое программирование в примерах и задачах: учеб. пособие. Москва: Лань, 2011. 3. Миносцев В. Б.Курс математики для технических высших учебных заведений. Часть 4. Теория вероятностей и математическая статистика. Москва: «Лань», 2013. 4. Кремер Н. Ш., Путко Б. А., Кремер Н. Ш. Эконометрика: учебник для студентов вузов, обучающихся по специальностям экономики и управления. Москва: ЮНИТИ-ДАНА, 2008. 5. Гмурман В. Е. Теория вероятностей и математическая статистика: учеб. пособие для вузов. Москва: Высшая школа, 2002. 6. Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике: учеб. пособие для вузов. Москва: Высшая школа, 2002. 7. Гниломедов П. И., Пирогова И. Н., Скачков П. П. Математическое моделирование: учебно-методическое пособие для занятий и самостоятельной работы студентов заочной формы обучения. Екатеринбург: УрГУПС, 2012. 135 Учебное издание Гниломедов Павел Иванович Мартыненко Александр Валерьевич ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ Конспект лекций по дисциплине «Экономико-математические методы и модели» для студентов всех форм обучения направления подготовки 38.03.01 – «Экономика» Редактор С. В. Пилюгина Подписано в печать 20.11.15. Формат 60х84/16 Усл. печ. л. 7,9. Электронная версия. Заказ 514 УрГУПС 620034, Екатеринбург, Колмогорова, 66