Задачи линейного программирования

Лекция 1 Задачи линейного программирования 1. Задача оптимального планирования производства Пусть предприятие из видов ресурсов производит видов продукции. При этом для производства одной единицы j-го вида продукции расходуется единиц i-го вида ресурса, т.е. норма расхода i-го ресурса на производство j-го вида продукции. Матрица, составленная из норм расхода , называется матрицей норм расхода или технологической матрицей. Обозначим через величину прибыли от реализации одной единицы j-го вида продукции. Эти значения прибыли запишем матрицей-строкой . План производства продукции х1, х2, …, хп обозначим матрицей-столбцом Х. Тогда произведение матриц представляет собой величину прибыли, полученной после реализации продукции. Количество i-го ресурса обозначим . Значения b1, b2, …, bm запишем матрицей-столбцом B. Тогда матричное неравенство означает необходимость, учитывать ограниченность ресурсов при рассмотрении планов производства Х. Если это неравенство выполняется, то план является реальным или допустимым. Естественно, нужно найти такой допустимый план, который бы обеспечил наибольшую прибыль. Эту задачу можно записать так: . Или в матричной форме: , , . Такая задача называется задачей оптимального планирования производства. Функция называется целевой функцией. Множество всех планов Х, удовлетворяющих неравенствам , , называется множеством допустимых планов, и обозначается D. Тогда нашу задачу можно сформулировать так: найти максимум целевой функции на множестве допустимых планов. Область ограничений задается линейными функциями. Сама целевая функция также является линейной. Задачи такого вида называются задачами линейного программирования. К ним относятся, например, задачи о диете, о раскрое материала и другие. Задача линейного программирования в общем виде такова: найти максимум или минимум линейной целевой функции при линейных ограничениях на переменные. 2. Графический метод решения задач линейного программирования Пусть задача линейного программирования содержит две переменные, и . Графический метод ее решения состоит в следующем. В системе координат строим многоугольник, который определяется системой ограничений. Целевая линейная функция при фиксированном значении является уравнением прямой , называемой опорной прямой. Значение целевой функции возрастает при движении прямой в направлении нормального вектора этой прямой . Перемещая эту прямую параллельно себе в направлении вектора по построенному многоугольнику ограничений, определяем вершины входа и выхода (может быть отрезок или луч). Вершина, из которой выходит опорная прямая, дает максимальное значение, в которую приходит минимальное значение целевой функции. Определяем координаты этих вершин, и находим соответствующие значения целевой функции, подставляя координаты в выражение для целевой функции. Пример. Решить графическим методом задачу линейного программирования: найти максимальное значение функции при ограничениях , ; ,. Решение. В системе координат на плоскости строим прямую по двум точкам с координатами и в первой четверти, так как . Прямая делит плоскость на две полуплоскости, из которых нужно выбрать одну, удовлетворяющую первому неравенству в системе. Для этого возьмем точку и подставим в неравенство. Если неравенство выполняется, то нужно заштриховать ту полуплоскость, в которой находится точка . Аналогично поступают с прямой . Получаем, что областью решений неравенств является четырехугольник . Строим опорную прямую , и перемещаем ее параллельно себе в направлении вектора по четырехугольнику , определяем вершину выхода – точку В. Находим координаты точки В, для этого решаем систему уравнений: Найденные координаты точки подставляем в целевую функцию, и определяем максимальное значение: . Данное значение можно найти, если подставить координаты вершин четырехугольника в целевую функцию и выбрать среди них максимальное значение. 3. Алгоритм симплекс-метода решения задач линейного программирования Решение задачи линейного программирования геометрическим методом является наглядным в случае двух или даже трех переменных. Для случая же большего числа переменных геометрический метод становится невозможным. При решении задачи линейного программирования графическим методом фактически перебирали все вершины многоугольной допустимой области. Такой перебор можно сократить, если учитывать линейность целевой функции, чтобы каждая следующая вершина была лучше предыдущей. Идея последовательного улучшения решения легла в основу симплекс-метода решения задач линейного программирования. Для реализации симплекс-метода необходимо определить: 1) первоначальное допустимое решение задачи, 2) правило перехода к лучшему решению, 3) критерий проверки оптимальности найденных решений. Для этого составляются различные алгоритмы симплекс-метода. Рассмотрим один из них для нахождения максимального значения целевой функции на следующем примере. Найти максимальное значение функции , если переменные удовлетворяют системе ограничений: 1. Вводим новые переменные , с помощью которых неравенства системы преобразуем в уравнения: У коэффициентов целевой функции меняем знак или записываем ее в виде . Заполняем первую симплексную таблицу, в нулевой строке записываем х1, х2 и (свободные коэффициенты). В нулевом столбце – х3, х4, х5 и F. Заполняем эту таблицу по полученной системе уравнений и преобразованной целевой функции. X1 X1 b X3 5 3 15 X4 -2 3 6 X5 3 -2 3 F -2 -3 Проверяем критерий оптимальности на нахождение максимального значения: в последней строке все коэффициенты должны быть положительными. Этот критерий не выполняется, переходим к составлению второй таблицы. 2. Находим разрешающий элемент первой таблицы следующим образом. Среди элементов последней строки выбираем наибольший по модулю отрицательный коэффициент (это -3) и второй столбец принимаем как разрешающий. Если же все коэффициенты столбца неположительные, то . Для определения разрешающей строки свободные коэффициенты делим на соответствующие элементы разрешающего столбца и выбираем минимальное отношение, при этом отрицательные коэффициенты не берем. Имеем , вторая строка является разрешающей. Пересечение разрешающей строки и столбца дает разрешающий элемент – это 3. 3. Заполняем вторую симплексную таблицу. Переменные на пересечении которых получаем разрешающий элемент, меняем местами, т.е. и . Разрешающий элемент заменяем ему обратным, т.е. на . Элементы разрешающей строки и столбца (кроме разрешающего элемента) делим на разрешающий элемент. При этом у коэффициентов разрешающего столбца меняем знак. Остальные элементы второй таблицы получаем по правилу прямоугольника из элементов первой таблицы. Для заполняемой клетки и клетки с разрешающим элементом составляем прямоугольник. Затем из элемента для заполняемой клетки вычитаем произведение элементов двух других вершин, деленное на разрешающий элемент. Покажем расчеты по этому правилу для заполнения первой строки второй таблицы: . Заполнение таблиц по таким правилам продолжаем до тех пор, пока не будет выполнен критерий. Имеем для нашей задачи еще две таблицы. х1 х4 b х3 х2 b х3 7 -1 9 х1 х2 2 х2 х5 5 х5 2 F -4 1 6 F 4. Результат выполнения этого алгоритма записывают следующим образом. В заключительной таблице элемент, стоящий на пересечении строки и столбца b, дает максимальное значение целевой функции. В нашем случае . Значения переменных по строкам равны свободным коэффициентам. Для нашей задачи имеем . Существуют и другие способы составления и заполнения симплексных таблиц. Например, для этапа 1 в нулевой строке таблицы записывают все переменные и свободные коэффициенты. После нахождения разрешающего элемента по тем же правилам в следующей таблице заменяем переменную в нулевом столбце, а в строке нет. Все элементы разрешающей строки делим на разрешающий элемент, и записываем в новой таблице. Для остальных элементов разрешающего столбца записываем нули. Далее выполняем указанный алгоритм с учетом этих правил. При решении задачи линейного программирования на минимум в последней строке выбирают наибольший положительный коэффициент, и выполняют указанный алгоритм до тех пор, пока в последней строке не будет положительных коэффициентов. 4 Решение задач линейного программирования средствами Excel Для решения задач линейного программирования используется надстройка Поиск решения. Сначала необходимо убедиться, что эта надстройка присутствует на вкладке Данные в группе Анализ (для 2003 года смотреть Сервис). Если команда Поиск решения или группа Анализ отсутствует, необходимо загрузить эту надстройку. Для этого щелкните Файл Microsoft Office (2010), далее щелкните кнопку Параметры Excel. В появившемся окне Параметры Excel выберите слева поле Надстройки. В правой части окна должно быть установлено значения поля Управление равным Надстройки Excel, нажмите кнопку «Перейти», которая находится рядом с этим полем. В окне Надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК. Далее можно работать с установленной надстройкой Поиск Решения. До вызова Поиск Решения необходимо подготовить данные для решения задачи линейного программирования (из математической модели) на рабочем листе: 1) Определить ячейки, в которые будет помещен результат решения для этого, в первом строке вводим переменные и целевую функцию. Вторую строку не заполняем (изменяемые ячейки) в этих ячейках будет получен оптимальный результат. В следующую строку вести данные для целевой функции, а в следующие строки системы ограничений (коэффициенты при неизвестных). Правую часть ограничений (свободные коэффициенты) вводим, оставляя свободную ячейку после записи коэффициентов системы ограничений. 2) Ввести зависимость от изменяемых ячеек для целевой функции и зависимости от изменяемых ячеек для левых частей системы ограничений в оставленные свободные ячейки. Для введения формул зависимостей удобно пользоваться математической функцией СУММПРОИЗВ. Далее необходимо воспользоваться надстройкой Поиск решения. На вкладке Данные в группе Анализ выберите команду Поиск решения. Появится диалоговое окно Поиск решения, которое необходимо заполнить следующим образом: 1) Указать ячейку, содержащую целевую функцию в поле «Оптимизировать целевую функцию» (эта ячейка должна содержать формулу для целевой функции). Выбираем вариант оптимизации значения целевой ячейки (максимизация, минимизация): 2) В поле «Изменяя ячейки переменных» вводим изменяемые ячейки. В следующем поле «В соответствии с ограничениями» вводим заданные ограничения с помощью кнопки «Добавить». В появившемся окне вводим ячейки, содержащие формулы системы ограничений, выбираем знак ограничения и значение ограничения (свободный коэффициент): 3) Ставим флажок в поле «Сделать переменные без ограничений неотрицательными». Выбрать метод решения «Поиск решения линейных задач симплекс-методом». После нажатия кнопки «Найти решение» запускается процесс решения задачи. В итоге появляется диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками для значений переменных и оптимальным значением целевой функции. Пример. Решить, используя надстройку «Поиск решения» Excel задачу линейного программирования: найти максимальное значение функции при ограничениях , ; ,. Решение. Для решения нашей задачи на рабочем листе Excel выполним указанный алгоритм. Вводим исходные данные в виде таблицы A B C D 1 x1 x2 F 2 3 1 1 4 3 1 3 5 1 3 3 Вводим зависимости для целевой функции и системы ограничений. Для этого в ячейку С2 вводим формулу =СУММПРОИЗВ(A2:B2;A3:B3). В ячейки С4 и С5 соответственно формулы: =СУММПРОИЗВ(A2:B2;A4:B4) и =СУММПРОИЗВ(A2:B2;A5:B5). В результате получаем таблицу. A B C D 1 x1 x2 F 2 3 1 1 4 3 1 3 5 1 3 3 Запускаем команду «Поиск решения» и заполняем появившееся окно Поиск решения следующим образом. В поле «Оптимизировать целевую функцию» вводим ячейку С2. Выбираем оптимизации значения целевой ячейки «Максимум». В поле «Изменяя ячейки переменных» вводим изменяемые ячейки A2:B2. В поле «В соответствии с ограничениями» вводим заданные ограничения с помощью кнопки «Добавить». Ссылки на ячейку $C$4:$C$5 Ссылки на ограничения =$D$4:$D$5 между ними знак <= затем кнопку «ОК». Ставим флажок в поле «Сделать переменные без ограничений неотрицательными». Выбрать метод решения «Поиск решения линейных задач симплекс-методом». Нажатием кнопки «Найти решение» запускается процесс решения задачи. В итоге появляется диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками для значений переменных и оптимальным значением целевой функции. A B C D 1 x1 x2 F 2 0,75 0,75 1,5 3 1 1 4 3 1 3 3 5 1 3 3 3 В диалоговом окне «Результаты поиска решения» сохраняем результат x1=0,75, x2=0,75 , F=1,5-равный максимальному значению целевой функции. Лекция 2. Элементы теории матричных игр 1. Платежная матрица. Нижняя и верхняя цена игры Теория игр - это математическая теория конфликтных ситуаций. Математическая модель конфликтной ситуации называется игрой. Конфликтная ситуация возникает тогда, когда ее участники (игроки) имеют противоположные интересы. Задачей теории игр является выработка рекомендаций для игроков, т.е. определение для них оптимальной стратегии. Стратегией игрока называется система правил, однозначно определяющих поведение игрока на каждом ходе в зависимости от ситуации, сложившейся в процессе игры. Оптимальной называется стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш. Рассмотрим простейшую математическую модель конечной конфликтной ситуации, когда имеются два участника и когда выигрыш одного равен проигрышу другого (антагонистическая игра двух лиц с нулевой суммой). Задача первого игрока – максимизировать свой выигрыш. Задача второго игрока – минимизировать свой проигрыш. Игру можно представить в виде матрицы, в которой строки – стратегии первого игрока, столбцы – стратегии второго игрока, а элементы матрицы – выигрыши первого игрока. Такую матрицу называют платежной. В общем случае парную игру с нулевой суммой можно записать платежной матрицей Найдем наилучшую стратегию первого игрока: минимальное число в каждой строке обозначим , . Зная, первый игрок выберет ту стратегию, для которой максимально. Обозначим это максимальное значение , тогда . Величина - гарантированный выигрыш, который может обеспечить себе первый игрок, - называется нижней ценой игры. Аналогично для определения наилучшей стратегии второго игрока находят максимальные значения выигрыша по столбцам и, выбрав из них минимальное значение, получаем , где – верхняя цена игры. Для матричной игры справедливо неравенство . Если , то такая игра называется игрой с седловой точкой, а пара оптимальных стратегий – седловой точкой матрицы. В этом случае элемент , называемый ценой игры, является минимальным в -й строке и максимальным в j-м столбце. Рассмотренные оптимальные стратегии первого и второго игроков называются соответственно максиминными и минимаксными. Пример 1. Решить игру, заданную матрицей А=. Решение. Находим нижнюю и верхнюю цены игры Так как матрица Н имеет седловую точку , то цена игры равна 0, при этом первый игрок должен выбрать третью строку, а второй игрок должен выбрать третий столбец. Отклонение от указанной стратегии приводит к уменьшению выигрыша первого игрока или к увеличению проигрыша второго игрока. 2 Приведение матричной игры к задаче линейного программирования. Теория игр находится в тесной связи с линейным программированием, т.к. каждая игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования и решена симплексным методом. Рассмотрим стратегии игроков, основанные на вероятностном выборе ходов. Такие стратегии называются смешанными. Пусть я строка выбирается первым игроком с вероятностью ( = 1,2,...,m), a j-й столбец выбирается вторым игроком с вероятностью (j = l,2,...,n). Так как одна из строк и один из столбцов будут обязательно выбраны (каждый игрок обязан сделать ход), то Цена игры V определяется как математическое ожидание величины а, т. е. V= Для первого игрока математическая модель задачи записывается в виде при ограничениях: Математическую модель можно упростить, разделив все (+1) ограничений на цену игры. Полагая, что >0, систему ограничений можно записать так: Пусть . Так как →max, то . Получим задачу линейного программирования вида при ограничениях: Задача второго игрока является двойственной по отношению к задаче первого игрока и имеет вид. при ограничениях: где Можно найти решение одного из игроков, а затем по теоремам двойственности – решение другого. Пример 2. Решить игру, заданную матрицей . Решение Находим нижнюю и верхнюю цену игры. = max(l;3) = 3; Так как они не равны, то применяем смешанные стратегии. Находим сначала оптимальную стратегию второго игрока, т.е. находим наибольшее значение функции и соответствующие значения неотрицательных переменных , , если выполняются неравенства: Для решения этой задачи используем симплексный метод, проводя вычисления в таблицах. Таблица 1 Таблица 2 1 9 1 1/9 1/9 1/9 6 3 1 51/9 -3/9 6/9 -1 -1 -8/9 1/9 1/9 Таблица 3 Таким образом, имеем: = 6/51, t2 = 5/51, = 51/11,y= 6/51 • 51/11 = 6/11, у2 = 5/51 • 51/11 = 5/11. Итак, второй игрок должен выбирать первый столбец с вероятность 6/11, а второй 5/11.Используем соответствие t3 u, t 4 u, то из таблицы 3 имеем: u= 3/51, u2 = 8/51. Следовательно, x= 3/51 • 51/11 = 3/11, х2 = 8/51 • 51/11 = 8/11. . Итак, первый игрок должен выбирать первую строку с вероятность 3/11, а вторую 8/11 . 3 Пример решения матричной игры средствами Excel Решим, используя надстройку «Поиск решения» Excel игру, заданную матрицей . Нижняя и верхняя цены игры: = max(l;3) = 3; не совпадают, поэтому применяем смешанные стратегии. Для нахождения оптимальной стратегии первого игрока решаем задачу линейного программирования: найти минимальное значение функции при ограничениях , ; ,. Здесь , где вероятность выбора первой строки вероятность выбора второй строки, цена игры. Для ее решения на рабочем листе Excel выполним указанный выше алгоритм. Вводим исходные данные в виде таблицы A B C D 1 u1 u2 L 2 3 1 1 4 1 6 1 5 9 3 1 Вводим зависимости для целевой функции и системы ограничений. Для этого в ячейку С2 вводим формулу =СУММПРОИЗВ(A2:B2;A3:B3). В ячейки С4 и С5 соответственно формулы: =СУММПРОИЗВ(A2:B2;A4:B4) и =СУММПРОИЗВ(A2:B2;A5:B5). В результате получаем таблицу. A B C D 1 u1 u2 L 2 3 1 1 4 1 6 1 5 9 3 1 Запускаем команду «Поиск решения» и заполняем появившееся окно Поиск решения следующим образом. В поле «Оптимизировать целевую функцию» вводим ячейку С2. Выбираем оптимизации значения целевой ячейки «Минимум». В поле «Изменяя ячейки переменных» вводим изменяемые ячейки A2:B2. В поле «В соответствии с ограничениями» вводим заданные ограничения с помощью кнопки «Добавить». Ссылки на ячейку $C$4:$C$5 Ссылки на ограничения =$D$4:$D$5 между ними знак => затем кнопку «ОК». Ставим флажок в поле «Сделать переменные без ограничений неотрицательными». Выбрать метод решения «Поиск решения линейных задач симплекс-методом». Нажатием кнопки «Найти решение» запускается процесс решения задачи. В итоге появляется диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками для значений переменных и оптимальным значением целевой функции. A B C D 1 u1 u2 L 2 0,058824 0,156863 0,215686 3 1 1 4 1 6 1 1 5 9 3 1 1 В диалоговом окне «Результаты поиска решения» сохраняем результат u1=0,058824, u2=0,156863, L=0,215686-равный минимальному значению целевой функции. Заметим, что нужное количество знаков после запятой можно ввести, выбрав команду Формат ячеек. Так как и , , то находим, что =4,63637, =0,2727280,27, =0,7272740,73 с такими вероятностями первый игрок должен выбирать первую и вторую строки. Находим оптимальную стратегию второго игрока, т.е. находим наибольшее значение функции и соответствующие значения неотрицательных переменных , , если выполняются неравенства: Здесь , где вероятность выбора первогостолбца вероятность выбора второго столбца, цена игры. Решение этой задачи с использованием надстройки «Поиск решения» Excel дано в таблице A B C D 1 t1 t2 L 2 0,117647 0,098039 0,215686 3 1 1 4 1 9 1 1 5 6 3 1 1 Так как и , , то находим, что =4,63637, =0,5454550,55, =0,4545460,45 с такими вероятностями второй игрок должен выбирать первый столбец и второй. Лекция 3. Транспортная задача 1 Закрытая транспортная задача Транспортная задача возникает при планировании наиболее рациональных перевозок груза, т.е. определении такого плана перевозок, при котором стоимость последних была бы минимальна. Рассмотрим решение этой задачи на примере. Пример 1. В двух пунктах отправления А1 и А2 находится соответственно 150 и 90 тонн груза. В пункты В1, В2 и В3 требуется доставить соответственно 60, 70 и 110 тонн груза. Стоимости перевозок тонны грузы из пункта Аi в пункты Bj записаны матрицей: . Составить оптимальный план перевозок груза так, чтобы общая сумма транспортных расходов была наименьшей. Сумма поставок 150+90=240, сумма потребностей 60+70+110=240. Сумма поставок равна сумме потребностей, поэтому мы имеем закрытую модель транспортной задачи. Запишем исходные данные в таблицу 1. В правом верхнем углу клетки пишем транспортные расходы по перевозке груза из пункта в пункты Таблица 1 60 70 110 150 10 60 12 70 - 6 + 20 10 90 5 4 5 λ + 6 8 - 90 4 2 4 Составим опорный план по методу северо-западного угла. Заполнение начинаем с клетки (1; 1): , первый столбец закрыт. Переходим к клетке (1; 2): , второй столбец закрыт; далее, переходим к клетке (1; 3): . Т.к. в третьем столбце остался остаток, равный 90, то переходим к заполнению клетки (2; 3): . Опорное исходное решение построено. Число загруженных клеток должно равно m+n-1=2+3-1=4 – невырожденный план. Если это условие нарушается, то добавляем нулевую поставку. Чтобы это условие выполнялось. Этому плану соответствуют затраты в количестве: руб. Получив исходное решение, перейдем теперь к построению новых опорных решений, улучшающих друг друга: для этого применим метод потенциалов. После построения опорного решения все переменные разбиты на 2 группы: xkl – базисные и xpq – свободные, где (p, q) – пустая клетка. Линейные функции выразятся через свободные так: . (1) Для нахождения коэффициентов γpq при свободных переменных сопоставим каждому пункту отправления Ai некоторую величину ui, которую назовем потенциалом пункта Ai, и каждому пункту назначения Bj величину vj – потенциал пункта Bj. Эти величины связаны равенством , (2) где ckl – стоимость перевозки одной тонны груза из Ak в Bl. Доказывается, что совокупность уравнений (2), составленных для всех базисных переменных, составляет совместную систему линейных уравнений, причем значение одной из переменных можно задавать произвольно, тогда значения остальных переменных находятся из системы однозначно. Обозначим для свободных переменных сумму соответствующих потенциалов через , т.е. и назовем ее косвенной стоимостью. Тогда коэффициенты γpq в (1) определяются так: . Если все величины γpq неотрицательны, то исходное решение является оптимальным. В нашем случае γ22= -1. Следовательно, оптимальное решение не достигнуто. План можно улучшить, «загружая» максимально клетку (2; 2). В данную клетку поместим λ (т.). Осуществляем перераспределение груза, выбрав подходящий контур (цикл), состоящий их горизонтальных и вертикальных отрезков. Выбираем λ с таким расчетом, чтобы вместо клетки, в которую поместили λ, пустой стала ранее «загруженная» клетка, баланс груза по строкам и столбцам сохранился, поставки не были отрицательными, количество загруженных клеток не превышало m+n-1. Получается квадратный цикл: 70- λ 20+ λ λ 90- λ По циклу перемещают наименьшую отрицательную поставку Таким образом, λ можно принять равной 70, и получаем второй базисный план перевозок, который представлен в таблице 2. Таблица 2 Bj Ai 60 70 110 ui 150 10 60 - 12 3 6 + 90 90 5 λ + 12 5 70 8 - 20 2 vj 10 3 6 Вычисляем транспортные расходы: руб. Находим потенциалы и косвенные тарифы. В клетке (2; 1) отрицательная разность. Следовательно, оптимальное решение не достигнуто. План можно улучшить максимально «загружая» клетку (2; 1). Повторяя предыдущее рассуждение, получим Таблица 3 Bj Ai 60 70 110 ui 150 10 40 12 10 6 110 10 90 5 20 12 5 70 8 1 5 vj -4 Вычисляем транспортные расходы: руб. Вычисляем потенциалы и косвенные тарифы. Т.к. все величины γpq неотрицательны, то оптимальный план достигнут и тем самым задача решена. 2. Открытая транспортная задача Может оказаться, что сумма поставок не равна сумме потребностей, в этом случае имеем открытую модель транспортной задачи. Рассмотрим решение открытой транспортной задачи на примере. Пример 2. Минимизировать транспортные расходы по доставке грузов от поставщиков А1, А2, А3 к потребителям В1, В2, В3, если заданы объем поставок и потребностей, а также тарифы по доставке единицы груза от каждого поставщика до каждого потребителя (в д.е.). В А 7 17 23 8 2 4 10 20 5 11 7 24 3 6 5 Сумма поставок 8+20+24=52, сумма потребностей 7+17+23=47. Сумма поставок не равна сумме потребностей, поэтому мы имеем открытую модель транспортной задачи. Введем фиктивного потребителя с потребностью, равной 52-47=5 (ед. товара). В А 7 17 23 5 8 2 7---- 4 ----1 10 -5 -5 20 5 + ----- 9 4 11 --- 16 7 4 2 2 2 24 3 7 4 6 9 5 19 5 7 9 5 0 Дочертим еще один столбец в таблице. Основные тарифы в этом столбце возьмем равные нулю. Далее решаем задачу как закрытую модель. Составим опорный план по методу северо-западного угла. Число загруженных клеток должно равно m+n-1=3+4- -1=6 – невырожденный план. Улучшаем план по методу потенциалов. В двух клетках получается одинаковая разность (косвенный тариф минус основной), она составляет 4 единицы. Если построить циклы с обеими этими клетками, то оба цикла дадут перемещение одинаковой стоимости, поэтому можно брать любой из них. Построим цикл с загружаемой клеткой (2;1). По циклу перемещаем наименьшую отрицательную поставку 7. В А 7 17 23 5 8 2 -2 4 8 10 -5 -7 20 5 7 11 9----- 7 ---- 4 2 2 24 3 3 6 + ----- 9 3 5 -----19 5 -2 5 11 7 2 По циклу перемещаем поставку 9. В А 7 17 23 5 8 2 1 4 8 10 3 -4 -2 20 5 7 11 8 7 13--- -- +0 2 2 2 24 3 3 6 9 5 10--- ----5 3 6 5 0 По циклу перемещаем поставку 5. В А 7 17 23 5 8 2 1 4 8 10 3 -4 -4 20 5 7 11 8 7 8 5 24 3 3 6 9 5 15 -2 2 5 8 7 0 Последний план перевозок оптимален, так как все косвенные тарифы  основных тарифов. Посчитаем минимальную стоимость перевозок товаров (д.е.). 3 Пример решения транспортной задачи средствами Excel Рассмотрим решение транспортной задачи заданной таблицей Bj Ai 60 70 110 150 10 12 6 90 5 5 8 используя надстройку «Поиск решения» Excel. На рабочем листе Excel вводим исходные данные в виде таблицы A B C D E 1 10 12 6 2 5 5 8 3 4 150 5 90 6 7 60 70 110 Здесь в ячейках введены стоимости перевозок. Ячейки отведены под неизвестные значения объемов перевозок. В ячейках введены объемы поставок, а в ячейках объемы потребностей. В ячейку , вводится формула для целевой функции =СУММПРОИЗВ(A1:C2;A4:C5) . В ячейки вводятся формулы: =СУММ(A4:A5); =СУММ(B4:B5): =СУММ(C4:C5) определяющие объемы потребностей. В ячейки введены формулы: =СУММ(A4:C4); =СУММ(A5:C5) характеризующие объемы поставок Запускаем команду «Поиск решения» и заполняем появившееся окно Поиск решения следующим образом. В поле «Оптимизировать целевую функцию» вводим ячейку . Выбираем оптимизации значения целевой ячейки «Минимум». В поле «Изменяя ячейки переменных» вводим изменяемые ячейки . В поле «В соответствии с ограничениями» вводим заданные ограничения с помощью кнопки «Добавить». $A$6:$C$6=$A$7:$C$7 $D$4:$D$5<=$E$4:$E$5. Ставим флажок в поле «Сделать переменные без ограничений неотрицательными». Выбрать метод решения «Поиск решения линейных задач симплекс-методом». Нажатием кнопки «Найти решение» запускается процесс решения задачи. В итоге появляется диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками для значений переменных и оптимальным значением целевой функции. A B C D E 1 10 12 6 2 5 5 8 3 4 40 110 150 150 5 20 70 90 90 6 60 70 110 1510 7 60 70 110 Здесь в ячейках получаем план перевозок, а в ячейке минимальные затраты. Лекция 4. Сетевое планирование 1. Сетевой график и его элементы Методы сетевого планирования получили широкое распространение в строительстве, промышленности, проведении научно-исследовательских разработок и конструировании, т.е. там, где тесно переплетаются сами работы, действие исполнителей и результаты работ. В процессе разработки сетевых моделей используются специальные понятия, термины и обозначения. Сетевой график строят с помощью двух элементов  событий и работ. Работа изображается на сетевом графике стрелкой, соединяющей два кружка  события. На сетевом графике события располагают в порядке возрастания, а стрелки не должны пересекаться. Каждому событию приписывают определенный номер . Работа обозначается , где . Длительность работы записывают на стрелке. Ранний возможный срок  наступления события определяется как наименьший момент времени, когда может осуществиться событие . Ранний возможный срок считают по входящим в событие стрелкам. Вычисления производим от первого события до последнего события. У первого события ранний срок берем равный нулю. Чтобы посчитать ранний срок второго события, нужно к раннему сроку первого события прибавить длительность работы и т.д. Если в событие входит несколько стрелок, то берем max из полученных сроков. Поздним допустимым сроком наступления события называется такой максимальный срок наступления события, который не нарушает поздних допустимых сроков наступления следующих за ним событий. Поздний допустимый срок считают по выходящим стрелкам. Вычисления производят от последнего до первого события. Для последнего события поздний срок принимают равным раннему сроку этого события. Поздний срок предпоследнего события будет равен разности позднего срока последнего события и длительности работы и т.д. Если из события выходит несколько стрелок, то берем min из поздних сроков. Критическим путем называют самую длинную из последовательностей событий и работ, соединяющих первое и последнее события. События и работы, лежащие на критическом пути, имеют совпадающие ранние и поздние сроки. Складывая длительность работ, лежащих на критическом пути, можно посчитать минимальный срок выполнения всего комплекса работ. Понятие критического пути очень важно для анализа сетевого графика. Последовательность работ, лежащих на критическом пути, определяет общую продолжительность планируемого процесса, поэтому эти работы самые важные и на их выполнение должно быть в первую очередь обращено внимание. Сокращение срока выполнения всего комплекса работ может быть произведено только при сокращении критических работ. 2. Резервы времени выполнения работ сетевого графика Резервы времени построенного сетевого графика оценивают только для некритических работ, так как для работ, лежащих на критическом пути все резервы равны нулю. Можно рассчитать четыре вида резервов времени выполнения работы : 1) полный резерв: ; 2) гарантированный резерв: ; 3) свободный резерв: ; 4) независимый резерв: Полный резерв – это максимальное время, на которое можно перенести начало работы или увеличить продолжительность работы без изменения общего срока выполнения комплекса работ. Полный резерв времени определяется как резерв времени максимального пути, проходящего через эту работу. Если полный резерв времени работы использовать именно для этой работы, то все остальные работы максимального пути, проходящего через эту работу, резервов времени иметь не будут. Гарантийный резерв есть часть полного резерва времени этой работы за вычетом резерва времени работ, предшествующих событию. Свободный резерв представляет собой максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы при условии, что все события сети наступают в свои ранние сроки. Этот резерв – часть полного резерва. Использование резерва одной работы может уменьшать резервы последующих или предыдущих работ. Иногда продолжительность времени выполнения работы может быть увеличена без изменения резервов времени предшествующих и последующих работ. Такое возможное увеличение времени работы называется независимым резервом времени (если НР получается отрицательным, то его нужно считать нулевым). В отличие от полного резерва времени, который в случае его использования отнимает резервы времени работ, лежащих на предшествующем и последующем отрезках максимального пути, проходящего через эту работу, независимый резерв времени работы принадлежит только для данной работы. Его нельзя передать ни предшествующим, ни последующим работам, находящимся на ее максимальном пути, проходящим через эту работу. Использование независимого резерва времени на работе, которая его имеет, не влияет на ранние и поздние сроки свершения всех событий и работ сети. Независимый резерв времени работы представляет собой остаток от ее полного резерва времени, если за счет последнего полностью сохранены резервы времени начального и конечного событий данной работы. Таким образом, величина независимого резерва времени работы показывает продолжительность вынужденного ожидания наступления конечного события данной работы, что позволяет снять с этой работы часть ресурсов, чтобы перебросить их на более напряженные работы. На критическом пути резервов времени для выполнения работы нет. Следовательно, задержка в выполнении какой-либо одной работы приведет к задержке выполнения всего комплекса работ. Следовательно, руководителю необходимо следить за выполнением работ, составляющих критический путь, в первую очередь, выделяя для него ресурсы – трудовые и материальные. Работы, лежащие не на критическом пути, имеют достаточный резерв времени, значит, их выполнение можно отнести на период менее загруженный, и контролировать их выполнение выборочно или возложить на подчиненных руководство ими. Сетевой график может быть оптимизирован, т.е. разработан новый план, в соответствии с которым комплекс работ может быть выполнен с меньшей затратой материальных средств или в более короткие сроки. 3 Пример построения сетевого графика и расчета резервов времени Предприятие намечает реконструкцию складов и подсобных помещений. Последовательность работ и их продолжительность даны в таблице. Построить сетевой график. Определить критический путь, минимальный срок выполнения всего комплекса работ и рассчитать таблицу резервов времени. Работа Содержание Продолжительность, дни (1, 2) Определение объема работы 5 (2, 3) Составление сметы 10 (2, 6) Выбор проекта реконструкции 5 (3, 4) Выбор подрядчика 3 (3, 5) Открытие счета в банке 2 (3, 8) Утверждение сметы вышестоящей организацией 5 (4, 8) Составление договора с подрядчиком 3 (5, 8) Сообщение заказчику об открытии счета в банке 1 (6, 7) Экономическое обоснование проекта 4 (7, 8) Привязка проекта к площади предприятия 5 (8, 9) Работы по реконструкции 60 Рассчитываем ранние и поздние сроки наступления событий: 1) Ранние возможные сроки: (1) = 0 (2) = 0+5 = 5 (3) = 5+10 = 15 (4) = 15+3 = 18 (5) = 15+2 = 17 (6) = 5+5 = 10 (7) = 10+4 = 14 (8) = (14+5;18+3;15+5;17+1)=(19;21;20;18)=21 (9) = 21+60 = 81 2) Поздние допустимые сроки: (9) = (9) = 81 (8) = 81-60 = 21 (7) = 21-5 = 16 (6) = 16-4 = 12 (5) = 21-1 = 20 (4) = 21-3 = 18 (3) = (18-3; 21-5; 20-2) = (15; 16;18) = 15 (2) = (12-5; 15-10) = (7;5) = 5 (1) = 5-5 = 0 Критический путь содержит 5 работ: (1,2); (2,3); (3,4); (4,8); (8,9). Минимальный срок: 5+10+3+3+60 = 81 день. Таблица резервов времени Работа Длительность работы Начало работы Конец работы Резервы времени ПР ГР СР НР (2,6) 5 5 5 10 12 2 2 (6,7) 4 10 12 14 16 2 (7,8) 5 14 16 21 21 2 2 (3,5) 2 15 15 17 20 3 3 (3,8) 5 15 15 21 21 1 1 1 1 (5,8) 1 17 20 21 21 3 3 Лекция 5. Динамическое программирование 1. Задача о распределении средств между предприятиями Динамическое программирование- это метод нахождения оптимальных решений в задачах с многошаговой структурой, когда на каждом шаге находиться оптимальное решение. Пусть имеется некоторое количество ресурсов х, которое необходимо распределить между п различными предприятиями, объектами, работами и т.д. так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения. Пусть – количество ресурсов, выделенных - му предприятию (); – функция полезности, величина дохода от использования ресурса xi, полученного - м предприятием; – наибольший доход, который можно получить при использовании ресурсов от первых k различных предприятий. Сформулированную задачу можно записать в математической форме: при ограничениях: Для решения задачи необходимо получить рекуррентное соотношение, связывающее и . Обозначим через количество ресурса, используемого k-м способом (), тогда для (k-1) способов остается величина ресурсов, равная (). Наибольший доход, который получается при использовании ресурса () от первых (k-1) способов, составит. Для максимизации суммарного дохода от k-го и первых (k-1) способов необходимо выбрать таким образом, чтобы выполнялись соотношения Эти соотношения называются функциональными уравнениями Беллмана: 2. Пример решения задача о распределении средств между предприятиями Для расширения производства совет директоров выделяет средства в объеме 100 млн. руб. с дискретностью 20 млн. руб. Прирост выпуска продукции на предприятиях зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице 1. Найти распределение средств между предприятиями, обеспечивающее максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить не более одной инвестиции. Выделяемые средства, млн.руб. Прирост выпуска продукции, млн. руб. Предприятие № 1 Предприятие № 2 Предприятие № 3 Предприятие № 4 20 3 2 2 1 40 5 4 4 3 60 7 5 5 6 80 9 7 8 7 100 10 9 10 9 Решение. Разобьем решение задачи на четыре этапа по количеству предприятий, на которых предполагается осуществить инвестиции. Решение будем проводить согласно рекуррентным соотношениям . Этап 1. Инвестиции производим только первому предприятию. Тогда f1(20)=3, f2(40)=5, f3(60)=7, f4(80)=9, f5(100)=10. Этап 2. Инвестиции выделяем первому и второму предприятиям. Рекуррентное соотношение (1) примет вид: f2(x)=max{g2(x2)+f1(x-x2)}. Следовательно f2(20)=max(3+0, 0+2)=max(3, 2)=3. f2(40)=max(5+0, 3+2, 0+4)=max(5, 5, 4)=5. f2(60)=max(7+0, 5+2, 3+4, 0+5)=max(7, 7, 7, 5)=7. f2(80)=max(9+0, 7+2, 5+4, 3+5, 0+7)=max(9, 9, 9, 8, 7)=9. f2(100)=max(10+0, 9+2, 7+4, 5+5, 3+7, 0+9)=max(10, 11, 11, 10, 10, 9)=11. Этап 3. Финансируем второй этап и третье предприятие. В этом случае соотношение (1) принимает вид: f3(x)=max{g3(x3)+f2(x-x3)}. Тогда f3(20)=max(3+0, 0+2)=max(3, 2)=3. f3(40)=max(5+0, 3+2, 0+4)=max(5, 5, 4)=5. f3(60)=max(7+0, 5+2, 3+4, 0+5)=max(7, 7, 7, 5)=7. f3(80)=max(9+0, 7+2, 5+4, 3+5, 0+8)=max(9, 9, 9, 8, 8)=9. f3(100)=max(11+0, 9+2, 7+4, 5+5, 3+8, 0+10)=max(11, 11, 11, 10, 11, 10)=11. Этап 4. Инвестиции в объеме 100 млн.руб. распределяем между третьим этапом и четвертым предприятием. Соотношение (1) принимает вид: f4(x)=max{g4(x4)+f3(x-x4)}. Следовательно f4(20)=max(3+0, 0+1)=max(3, 1)=3. f4(40)=max(5+0, 3+1, 0+3)=max(5, 4, 3)=5. f4(60)=max(7+0, 5+1, 3+3, 0+6)=max(7, 6, 6, 6)=7. f4(80)=max(9+0, 7+1, 5+3, 3+6, 0+7)=max(9, 8, 8, 9, 7)=9. f4(100)=max(11+0, 9+1, 7+3, 5+6, 3+7, 0+9)=max(11, 10, 10, 11, 10, 9)=11. Максимальный прирост выпуска продукции в 11 млн.руб. получен на четвертом этапе как, например, 5+6 , т.е. 6 млн.руб. соответствуют выделению 60 млн.руб. четвертому предприятию. Согласно третьему этапу 5 млн.руб. получено как 3+2, т.е. 2 млн.руб. соответствует выделению 20 млн.руб. третьему предприятию. Согласно второму этапу 3 млн.руб. получено как 3+0, те. 3 млн.руб. соответствует выделению 20 млн.руб. первому предприятию. Таким образом, инвестиции в объеме 100 млн. руб. целесообразно выделить четвертому предприятию в объеме 60 млн.руб. и первому и второму предприятиям в объеме по 20 млн.руб. каждому, при этом прирост продукции будет максимальным и составит 11 млн.руб. Все вычисления можно упростить, воспользовавшись следующей расширенной таблицей: x 20 3 3 2 2 1 40 5 5 4 4 3 60 7 7 5 5 6 80 9 9 7 7 7 100 10 10 9 9 9 . Чтобы вычислить значения для столбца , надо по столбцу двигаться от 0 вниз до заполняемой клетки, а по столбцу двигаться вверх от заполняемой клетки до числа 0, образовывая сумм. Среди которых выбирают максимальную. Аналогично заполняют остальные столбцы. В итоге получаем таблицу: x 20 3 3 2 3 2 3 1 3 40 5 5 4 5 4 5 3 5 60 7 7 5 7 5 7 6 7 80 9 9 7 9 7 9 7 9 100 10 10 9 11 9 11 9 11 Число, записанное в нижнем правом углу таблицы, равно наибольшей прибыли, полученной от вложения всех средств.. Распределение средств предприятиям находим, подчеркивая слагаемые соответствующих максимальных сумм, перемещаясь из конца таблицы в начало. Лекция 6. Ковариационный анализ 1. Коэффициенты ковариации и корреляции В экономических исследованиях одной из важных задач является анализ зависимостей между изучаемыми переменными. Кроме функциональной зависимости между экономическими явлениями и процессами, существуют стохастические (вероятностные, статистические) зависимости. Статистической называется зависимость между случайными величинами, при которой изменение одной из величин влечет за собой изменение закона распределения другой величины. Для оценки тесноты и направления связи между изучаемыми переменными при их стохастической зависимости пользуются показателями ковариации и корреляции. Ковариацией случайных величин Х и Y называется среднее произведение отклонений каждой пары значений величин Х и Y в исследуемых массивах данных: Ковариация есть характеристика системы случайных величин, описывающая помимо рассеивания величин Х и Y еще и линейную связь между ними. Доказано, что для независимых случайных величин Х и Y их ковариация равна нулю, а для зависимых случайных величин она отличается от нуля (хотя и необязательно). Поэтому ненулевое значение ковариации означает зависимость случайных величин. Однако обращение в нуль ковариации не гарантирует независимости, бывают зависимые случайные величины, ковариация которых равна нулю. Из формулы определения ковариации видно, что ковариация характеризует не только зависимость величин, но и их рассеивание. Действительно, если, например, одна из величин Х или Y мало отличается от своего математического ожидания (почти не случайна), то показатель ковариации будет мал, какой бы тесной зависимостью ни были связаны величины Х и Y. Так что обращение в нуль ковариации величин Х и Y является недостаточным условием для их независимости, а только необходимым. Использование ковариации в качестве меры связи признаков не совсем удобно, так как показатель ковариации не нормирован и при переходе к другим единицам измерения меняет значение. Поэтому в статистическом анализе показатель ковариации сам по себе используется редко; он фигурирует обычно как промежуточный элемент расчета линейного коэффициента корреляции : . В начале 90-х годов 19 века Пирсон, Эджворт и Велдон получили формулу линейного коэффициента корреляции . Линейный коэффициент корреляции характеризует степень тесноты не всякой, а только линейной зависимости. При нелинейной зависимости между явлениями линейный коэффициент корреляции теряет смысл, и для измерения тесноты связи применяют так называемое корреляционное соотношение, известное также под названием «индекс корреляции». Линейная вероятностная зависимость случайных величин заключается в том, что при возрастании одной случайной величины другая имеет тенденцию возрастать (или убывать) по линейному закону. Эта тенденция к линейной зависимости может быть более или менее ярко выраженной, т.е. более или менее приближаться к функциональной. Если случайные величины Х и Y связаны точной линейной функциональной зависимостью y = aх + b, то . В общем случае, когда величины Х и Y связаны произвольной вероятностной зависимостью, линейный коэффициент корреляции принимает значение в пределах , тогда качественная оценка тесноты связи величин Х и Y может быть выявлена на основе шкалы Чеддока Теснота связи Значение коэффициента корреляции при наличии: прямой связи обратной связи Слабая 0,1–0,3 (–0,1)–(–0,3) Умеренная 0,3–0,5 (–0,3)–(–0,5) Заметная 0,5–0,7 (–0,5)–(–0,7) Высокая 0,7–0,9 (–0,7)–(–0,9) Весьма высокая 0,9–0,99 (–0,9)–(–0,99) 2. Расчет коэффициентов ковариации и корреляции в табличном процессоре Microsoft Excel Режим работы «Ковариация» служит для расчета генеральной ковариации на основе выборочных данных. Режим работы «Корреляция» предназначен для расчета генерального и выборочного коэффициентов корреляции соответственно на основе генеральных и выборочных данных. В диалоговых окнах данных режимов задаются следующие параметры: 1. Входной интервал. 2. Группирование. 3. Метки в первой строке/ Метки в первом столбце. 4. Выходной интервал/ Новый рабочий лист/ Новая рабочая книга. Пример 1. Показатели уровня образования, уровня преступности, а также отношение числа безработных к числу вакансий в некоторых центральных областях России в 1995 году (по данным Госкомстата РФ) приведены в таблице, сформированной на рабочем листе Excel B C D E 4 Область Уровень образования Отношение числа безработных к числу вакансий Уровень преступности 5 Брянская 735 22,3 908 6 Владимирская 788 10,8 791 7 Ивановская 779 52,9 804 8 Калужская 795 2,2 701 9 Костромская 740 10,4 685 10 г. Москва 902 0,4 496 11 Московская 838 2,4 536 12 Нижегородская 763 5,4 936 13 Орловская 762 4,1 662 14 Рязанская 757 4,1 671 15 Смоленская 772 1,0 920 16 Тверская 764 4,2 1040 17 Тульская 764 2,1 809 18 Ярославская 755 25,1 882 По выборочным данным, представленным в таблице, требуется установить наличие взаимосвязи между указанными показателями в центральном регионе России. Для решения задачи используем режим работы «Ковариация» и «Корреляция». Значения параметров, установленных в одноименных диалоговых окнах следующие: 1. Входной интервал: С4:E18. 2. Группирование: по столбцам. 3. Метки в первой строке: устанавливаем флажок. 4. Выходной интервал: G4 для «Ковариации» и G9 для «Корреляции». Рассчитанные в данных режимах показатели представлены в таблицах. Ковариация Уровень образования Отношение числа безработных к числу вакансий Уровень преступности Уровень образования 1750,245 Отношение числа безработных к числу вакансий -149,859 192,5135 Уровень преступности -4159,28 498,4541 22905,66 Корреляция Уровень образования Отношение числа безработных к числу вакансий Уровень преступности Уровень образования 1 Отношение числа безработных к числу вакансий -0,25817 1 Уровень преступности -0,6569 0,237369 1 Как видно из таблиц, между парами всех исследуемых показателей существуют стохастические связи. Причем характер всех выявленных связей различен и состоит в следующем: – связь «уровня образования» – «отношение числа безработных к числу вакансий» является слабой и обратной (rxy = -0,25817), т.е. с повышением уровня образования отношение числа безработных к числу вакансий уменьшается; – связь «уровень образования» – «уровень преступности» является заметной и обратной (rxy = -0,6569), т.е. с повышением уровня образования преступность уменьшается; – связь «отношение числа безработных к числу вакансий» – «уровень преступности» является слабой и прямой (rxy = 0,237369), т.е. с увеличением отношения числа безработных к числу вакансий увеличивается и уровень преступности. Ковариация (корреляционный момент) вычисляется в Excel с помощью стандартной статистической функции КОВАР. Аргументом этой функции являются диапазоны ячеек, содержащие значения наблюдаемых величин Х и Y. Коэффициент корреляции вычисляется в Excel одной из двух функций: КОРРЕЛ или ПИРСОН. Эти функции выдают одинаковый результат, если значения наблюдаемых величин записаны в виде чисел. Пример 2. Получены данные о числе работников магазинов (Х) и объем розничного товарооборота в млн. руб. (Y): Х 73 85 102 115 122 126 134 147 Y 0,5 0,7 0,9 1,1 1,4 1,4 1,7 1,9 Предполагается, что в исследуемой группе магазинов значения факторов, влияющих на объем товарооборота, примерно одинаковы. Поэтому влияние различия их значений на изменение объема розничного товарооборота сказывается незначительно. Исследовать связь объема розничного товарооборота магазинов и числа работников в них, т.е. найти ковариацию, коэффициент корреляции. Для выполнения этого задания необходимо проделать следующие пункты. 1. Наберите исходные данные в два столбца, в заголовке которых наберите буквы Х и Y, соответственно, в ячейки А1 и В1. Тогда данные Х займут диапазон А2:А9, а данные Y займут диапазон В2:В9. 2. Вычислите ковариацию. Для этого в ячейку А10 наберите «». В ячейку В10 наберите формулу для вычисления ковариации: =КОВАР(А2:А9; В2:В9). Должно получиться: μхy = 10,475. 3. Вычислите коэффициент корреляции. Наберите в ячейку А11 «». В ячейку В11 наберите формулу для вычисления коэффициента корреляции: КОРРЕЛ(А2:А9; В2:В9). Должно получиться: . 3. Понятие о методе ранговой корреляции При изучении признаков с непрерывными и неизвестными законами распределения классические подходы корреляционного анализа неэффективны. В этих случаях для изучения тесноты связей применяют, например, метод ранговой корреляции. Пусть дан вариационный ряд признака Х: . Рангом наблюдаемого значения признака Х называется номер этого наблюдения в вариационном ряду, т.е. R() = j при условии, что неравенства строгие. Если встречаются одинаковые члены, то в качестве ранга берется среднее арифметическое соответствующих номеров. Например, сумма оценок, полученных студентами на двух экзаменах, образуют вариационный ряд: 5, 5, 5, 7, 8, 9, 10, 10. Ранг трех студентов в начале ряда (1 + 2 + 3) / 3 = 2 или R(5) = 2; R(7) = 4, R(8) = 5, R(9) = 6, R(10) = (7 + 8) / 2 = 7,5. При изучении связи между Х и Y предположим, что выборка упорядочена по Х. Тогда ей соответствует следующая матрица (подстановка): , в которой первая строка состоит из рангов наблюдений Х, а вторая из рангов наблюдений Y. Для изучения связи между Х и Y используют эти подстановки или ранги. Жесткой функциональной положительной связи между Х и Y соответствует подстановка: , а жесткой отрицательной связи подстановка: . Остальные n-2 подстановки получаются при той или иной степени связи. Два элемента перестановки R() и R() инверсны (не образуют порядка), если R() стоит левее R(j) и больше его. Если при этом условии R() меньше R(j), то инверсии нет, и они образуют порядок. В качестве меры связи берут разность между суммами чисел порядков N и чисел беспорядков Q, образованных элементами второй строки подстановки. С помощью комбинаторики можно определить вероятности получения перестановок заданной меры связи. Например, для подстановок из четырех элементов рассмотрим расчетную таблицу: Число порядков N Число инверсий Q Мера сходства Подстановки Вероятность 6 -6 4321 1/24 1 5 -4 3421, 4231, 4321 3/24 2 4 -2 3412, 4132, 4213, 2431, 3241 5/24 3 3 3214, 2413, 4123, 3142, 1432, 2341 6/24 4 2 2 2143, 1423, 2314, 3124, 1342 5/24 5 1 4 2134, 1324, 1243 3/24 6 6 1234 1/24 Из таблицы видно, что распределения вероятностей симметричны относительно центра = N – Q = 0. Отсюда следует, что таблицы для решения задач проверки гипотез относительно меры сходства (или связи) можно давать для неотрицательных значений. Коэффициент ранговой корреляции Кендалла определяется по формуле: . Коэффициент ранговой корреляции Спирмена определяется по формуле: , где . Пример 3. В таблице приведены данные о стаже работы (Х) и времени выполнения печати текста (Y) 10 машинисток. Вычислить коэффициенты ранговой корреляции Кендалла и Спирмена. № машинистки Стаж, Х Время выполнения задания, Y 1 32 12 2 15 24 3 16 23 4 18 21 5 20 20 6 28 9 7 21 11 8 29 10 9 23 15 10 17 16 Решение. Расположим пары наблюдений в порядке возрастания Х, получаем таблицу: Х 15 16 17 18 20 21 23 28 29 32 Y 24 23 16 21 20 11 15 9 10 12 По этой таблице составляем матрицу подстановок, в которой первая строка состоит из рангов наблюдений Х, а вторая – Y: . Подсчитываем меру сходства , приписывая числу инверсий, образуемых элементами второй перестановки (строки), знак минус. Так, например, для 10 имеем -9, для 6 – (2 – 5) = -3, …, для 4 – 1. Суммируя их, получаем = -31. Вычисляем коэффициент ранговой корреляции Кендалла: . Вычисляем коэффициент корреляции Спирмена. Сначала вычисляем ; . Итак, связь между стажем машинистки и временем, затраченным на работу, можно считать доказанной, т.е. чем больше стаж, тем меньше затраты времени. Коэффициент корреляции Спирмена и Кендалла можно рассчитать в пакете «Stadia». Тема 7. Парная линейная регрессия 1. Линейное уравнение регрессии Регрессией называется односторонняя вероятностная зависимость между случайными величинами. Эта зависимость выражается с помощью функции, которая называется регрессией. Регрессии различают по числу переменных (между двумя переменными – простая, или несколькими – множественная); по форме зависимости (линейная, выражаемая линейной функцией, нелинейная). Результаты измерений или наблюдений величин и (случайных) фиксируют в таблице наблюдений, если данные наблюдаются по одному разу. … … Эти результаты можно изобразить на координатной плоскости в виде точек, координатами которых являются значения признака и одного объекта = 1, 2, …, n. В итоге получаем корреляционное поле. Пусть представление выборки на корреляционном поле следующие (рис. 2). Рис. 2. Представление выборки В случае а) видно, что следует искать линейную зависимость, в случае б) – нелинейную зависимость, а в случае в) вряд ли зависимость существует. Конкретный вид функциональной зависимости между величинами и называется эмпирической функцией. Простейшим видом эмпирической функции является линейная функция . Для получения линейной эмпирической формулы самым простейшим является метод «натянутой нити». В этом методе на корреляционном поле надо так провести прямую, чтобы по обе стороны ее оставалось примерно одинаковое количество точек. Выбираем на этой прямой две точки и (они могут и не принадлежать выборке). Подставляем эти координаты в формулу , получаем систему линейных уравнений: Решив эту систему относительно а и b, получаем эмпирическую формулу. Условным средним называется среднее арифметическое наблюдений значений , при фиксированном значении переменной . Корреляционной зависимостью от называется функциональная зависимость условной средней от х, в случае линейной корреляционной зависимости уравнение прямой линии регрессии имеет вид: = kx + c, где угловой коэффициент k называется выборочным коэффициентом регрессии Y на X и обозначается . Параметры и находятся из системы уравнений (метод наименьших квадратов): где n – число наблюдений значения параметра. Уравнение регрессии принято записывать в виде , где . Коэффициенты и можно также найти по формулам: , Уравнение регрессии на имеет вид: , где , . Если выборка многочисленна, то одно и то же значение может встретиться раз, одно и то же значение соответственно раз. Одна и та же пара значений может наблюдаться раз. Поэтому наблюдаемые значения могут быть сгруппированы и записаны в корреляционной таблице: Y Х 16 18 20 25 10 1 4 20 9 10 25 6 6 2 30 1 18 6 Здесь Х – количество удобрений, Y – урожайность, на пересечении строки и столбца указано количество участков, в которых при вносимом количестве удобрений получен соответствующий урожай. 2. Построение линейного уравнения регрессии в пакете «Stadia» В пакете «Stadia» процедура простой регрессии (в блоке «Статистические методы» «Регрессивный анализ») предоставляет возможность для экспериментальной зависимости от одной переменной строить наиболее употребительные регрессивные модели. Если в предполагаемом списке моделей нет подходящей, то следует обратиться к разделу общей регрессии, где можно задать по формуле любую алгебраическую модель. В ходе анализа можно получить следующие результаты: – выбрать из нескольких математических моделей ту, которая с большей точностью описывает экспериментальную зависимость (нами будет рассмотрена только линейная модель); – построить прогноз на будущее на основе выбранной модели с 95 % доверительным интервалом; – провести анализ регрессивных остатков; Исходные данные представляют собой две парные X и Y переменные, заданные в электронной таблице. Для получения результатов сначала в типовом бланке выбора переменных для регрессивного анализа нужно выбрать две парные X и Y переменные из электронной таблицы. Затем из специального меню «Регрессия» необходимо выбрать регрессивную модель. В правой части в меню выбора, для информации приведены формулы регрессивных моделей. Выбор ускоряется нажатием на быстрые клавиши, сопоставленные моделям (так для линейной это 1). Затем идет выдача результатов и диалог. Стандартная выдача результатов регрессивного анализа включает следующие последовательные компоненты: 1. Уравнение регрессии или модель, записанную в общем виде. 2. Таблицу значений коэффициентов модели со стандартными ошибками вычисления каждого коэффициента. 3. Таблицу дисперсионного анализа со столбцами: Источник Сумма квадратов Степ. свободы Средняя сумма квадратов и тремя строками для параметров: регрессивные, остаточные и общие. 4. Таблицу проверки нулевой гипотезы со следующими статистическими характеристиками: – множественный коэффициент корреляции R; – или коэффициент корреляции; – приведенная или несмещенная оценка ; – стандартная ошибка вычисления; – значения статистики Фишера и уровень значимости нулевой гипотезы о равенстве нулю коэффициента множественной корреляции. Нулевая гипотеза. Принятие последней нулевой гипотезы означает отсутствие соответствий между исходными данными и математической моделью. Иными словами – модель неадекватно описывает экспериментальные данные. Если нулевая гипотеза может быть принята, а модель отвергается как неадекватная. Далее появляется бланк запроса значений независимой переменной (интерполяция) для которого по полученному уравнению регрессии нужно прогнозировать или же интерполировать значение отклика Y. Запросы повторяются до нажатия кнопки «Отменить». Затем можно построить регрессивный график, на котором изображаются экспериментальные данные с регрессивной кривой и зона доверительного интервала регрессии. Случай однопараметрической модели следующим появляется в меню выбора дальнейшего направления анализа из четырех пунктов. («Что дальше?») При выборе прогноза в правое поле меню дальнейшего анализа нужно ввести число точек прогноза и величину шага прогноза и нажать клавишу прогноза. Затем выдается таблица, которая для каждого прогнозируемого X содержит следующие параметры: значение независимой переменной , регрессивный отклик Yрегр, стандартная ошибка прогноза индивидуального значения отклика dYрегр и 95 % доверительного интервала прогноза iYрегр. Пример 1. Получены данные о числе работников магазинов (Х), и объем розничного товарооборота в млн. руб. (Y): Х 73 85 102 115 122 126 134 147 Y 0,5 0,7 0,9 1,1 1,4 1,4 1,7 1,9 Предполагается, что в исследуемой группе магазинов значения факторов, влияющих на объем товарооборота, примерно одинаковы. Поэтому влияние различия их значений на изменение объема розничного товарооборота сказывается незначительно. Получить уравнение линейной регрессии Y и Х. Определить, какой объем розничного товарооборота в млн. руб. можно ожидать при увеличении числа работников магазинов до 170. Для выполнения задания ввести данные в виде таблицы X1 = X, X2 = Y. В бланке переменных можно выбрать X2 = Y, X1 = X. Затем из появившегося окне «Регрессия» в списке «Модели» выбрать линейную. Для получения значения объема товарооборота при увеличении числа работников до 170 в окне «Интерполяция» задать 170. Затем утвердить просмотр графика регрессии. В итоге получаем следующий результат. ПРОСТАЯ РЕГРЕССИЯ. Файл: Переменные: x1, x2 Модель: линейная Y = a0+a1*x Y=x2 x1 Коэфф. a0 a1 Значение -0,9739 0,01924 Ст.ошиб. 0,1562 0,001353 Значим. 0,001227 9,393E-5 Источник Сум.квадр. Степ.св Средн.квадр. Регресс. 1,612 1 1,612 Остаточн 0,04787 6 0,007978 Вся 1,66 7 Множеств R R^2 R^2прив Ст.ошиб. F Значим 0,98548 0,97116 0,96636 0,089321 202,1 8,113E-6 Гипотеза 1: <Регрессионная модель адекватна экспериментальным данным> x1=170, x3=2,297 Итак, уравнение линейной регрессии имеет вид: Y = -0,9739 + 0,01924x, а объем розничного товарооборота следует ожидать 2,297 млн. руб. Лекция 8. Множественная линейная регрессия 1 Построение множественного линейного уравнения регрессии в Excel В пакете анализа Microsoft Excel в режиме «Регрессия» реализованы следующие этапы множественной линейной регрессии: 1. Задания аналитической формы уравнения регрессии и определение параметров регрессии = α0 + α1x1 + α2x2 + …+ αmxm, где - теоретические значения результативного признака, полученные путем подстановки соответствующих значений факторных признаков в уравнении регрессии; x1, x2,…, xm – значение факторных признаков; α0, α1,…, αm – параметры уравнения (коэффициенты регрессии). Эти параметры определяются с помощью метода наименьших квадратов. Для нахождения параметров модели (), минимизируется сумма квадратов отклонений эмпирических (фактических) значений результативного признака от теоретических, полученных по выбранному уравнению регрессии. 2. Определение в регрессии степени стохастической взаимосвязи результативного признака и факторов, проверка общего качества уравнения регрессии. Здесь необходимо знать следующие дисперсии: – общую дисперсию результативного признака , отображающую влияние как основных, так и остаточных факторов: , где – среднее значение результативного признака ; – факторную дисперсию результативного признака , отображающую влияние только основных факторов: ; – остаточную дисперсию результативного признака , отображающую влияние только остаточных факторов: . При корреляционной связи результативного признака и факторов выполняется соотношение , при этом . Для анализа общего качества уравнение линейной многофакторной регрессии используют множественный коэффициент детерминации (квадрат коэффициента множественной корреляции ), которые рассчитываются по формуле . Этот коэффициент определяет долю вариации результативного признака, обусловленную изменению факторных признаков, входящих в многофакторную регрессивную модель. Так как уравнение регрессии строят на основе выборочных данных, то возникает вопрос об адекватности построенного уравнения генеральным данным. Для этого проверяется статистическая значимость коэффициента детерминации . В математической статистике доказывается, что если гипотеза :=0 выполняется, то величина , имеет распределение (Фишера) с числом степеней свободы и . При значениях >считается, что вариация результативного признака обусловлена в основном влиянием включенных в регрессионную модель факторов . Для оценки адекватности уравнения регрессии так же используют показатель средней ошибки аппроксимации: . 3. В тех случаях, когда часть вычисленных коэффициентов регрессии не обладает необходимой степенью значимости, их исключают из уравнения регрессии. Поэтому проверка адекватности построенного уравнения регрессии включает в себя проверку значимости каждого коэффициента регрессии. В математической статистике доказывается, что если гипотеза :=0 выполняется, то величина , имеет распределение Стьюдента с числом степеней свободы , где - стандартное значение ошибки для коэффициента регрессии . Гипотеза :=0 о незначимости коэффициента регрессии отвергается, если . Зная значение можно найти границы доверительных интервалов для коэффициентов регрессии (; ). При экономической интерпретации уравнения регрессии используются частные коэффициенты эластичности: показывающие, насколько процентов в среднем изменится значение результативного признака при изменении значения соответствующего факторного признака на один процент. В диалоговом окне режима работы «регрессии» задаются следующие параметры: 1. Входной интервал – вводятся ссылки на ячейки, содержащие данные по результативному признаку (состоят из одного столбца). 2. Входной интервал – вводятся ссылки на ячейки, содержащие факторные признаки (максимальное число столбцов - 16). 3. Метки в первой строке/метки в первом столбце – устанавливаются в активное состояние, если первая строка (столбец) в обходном диапазоне содержит заголовки. 4. Уровень надежности – устанавливается в активное состояние, если необходимо ввести уровень надежности отличный от уровня 95 %, применяемого по умолчанию. 5. Константа – ноль – флажок устанавливается в активное состояние, если требуется чтобы линия регрессии прошла через начало координат (). 6. Выходной интервал/Новый рабочий лист/Новая рабочая книга – указывается, куда необходимо вынести результаты исследования. 7. Остатки – флажок устанавливается в активное состояние, если требуется включить выходной диапазон в столбец остатков. 8. Стандартизованные остатки – флажок устанавливается в активное состояние, если требуется включить выходной диапазон столбец стандартизованных остатков. 9. График остатков – флажок устанавливается в активное состояние, если требуется вывести на рабочий лист точечные графики зависимости остатков от факторных признаков . 10. График подбора – флажок устанавливается в активное состояние, если требуется вывести на рабочий лист точечные графики зависимости теоретических результативных значений от факторных признаков . 11. График нормальной вероятности – флажок устанавливается в активное состояние, если требуется вывести точечный график зависимости, наблюдаемых значений от автоматически формируемых интервалов персентилей. 2 Пример построения линейной производственной функции Рассмотрим пример построения линейной производственной функции в пакете анализа Microsoft Excel в режиме «Регрессия» Данные о прибыли предприятия , затраченный капитал затраты на труд и общие затраты приведены в таблице по кварталам за 2011-2013 годы. Прибыль , тыс. руб. Затраты капитала, тыс. руб. Затраты на труд , тыс. руб. Общие затраты тыс. руб. 31972 18719,5 10939,5 29659 32290 18218,4 11410,6 29629 33698 19086,6 13436,4 32523 33568 20523,1 13611,9 34135 36098 21118,7 15286,3 36405 40724 23407,8 16495,2 39903 42081 22368,4 19346,6 41715 44174 25901,7 18194,3 44096 44237 24667,7 17538,3 42206 49300 22197,4 19849,6 42047 50701 24292,3 20305,7 44598 55338 27731,4 19880,6 47612 По этим данным определим уравнение линейной регрессии прибыли от затрат на капитал и труд и проведем анализ уравнения. Для решения задачи используем режим «Регрессия». На рабочем листе наберем данные: 31972 18719,5 10939,5 29659 32290 18218,4 11410,6 29629 33698 19086,6 13436,4 32523 33568 20523,1 13611,9 34135 36098 21118,7 15286,3 36405 40724 23407,8 16495,2 39903 42081 22368,4 19346,6 41715 44174 25901,7 18194,3 44096 44237 24667,7 17538,3 42206 48300 22197,4 19849,6 42047 50701 24292,3 20305,7 44598 55338 27731,4 19880,6 47612 выручка зат. кап. зат. Труд. общ. Зат. которые вводим в режим «Регрессия». Первый столбик – значения Y, второй и третий – значения X. Указываем выходной интервал. После выполнения (ОК) получаем следующие таблицы: ВЫВОД ИТОГОВ Регрессионная статистика Множественный R 0,948205 R-квадрат 0,899093 Нормированный R-квадрат 0,876669 Стандартная ошибка 2729,753 Наблюдения 12 Дисперсионный анализ   df SS MS F Значимость F Регрессия 2 5,98E+08 2,99E+08 40,09548 3,29E-05 Остаток 9 67063958 7451551 Итого 11 6,65E+08         Коэффициенты Стандартная ошибка t-статистика P-Значение Нижние 95% Верхние 95% Нижние 95,0% Верхние 95,0% Y-пересечение -4138,27 6541,76 -0,63259 0,54273 -18936,8 10660,2 -18936,8 10660,2 Переменная X 1 1,002626 0,49372 2,03075 0,07284 -0,11425 2,11949 -0,11425 2,11949 Переменная X 2 1,395363 0,4363 3,1977 0,0108 0,4082 2,3824 0,4082 2,3824 В таблице «Регрессивная статистика» сгенерированы результаты по регрессивной статистике: множественный R коэффициент корреляции; коэффициент детерминации ; стандартная ошибка; число наблюдений n. В таблице «Дисперсионный анализ» сгенерированы результаты дисперсионного анализа, который используется для проверки значимости коэффициента детерминации . В следующей таблице сгенерированы значения коэффициентов регрессии и их статистические оценки. В частности первый столбец дает значения коэффициентов , и . Рассчитанные в этой таблице коэффициенты регрессии позволяют построить уравнение, выражающее зависимость прибыли предприятия Y от затрат капитала и затрат на труд . Значение множественного коэффициента детерминации (из первой таблицы) показывает, что 94,8 % общей вариации результативного признака объясняется вариацией факторных признаков и . Значит, выбранные факторы существенно влияют на прибыль предприятия, что подтверждает правильность их включения в построенную модель. Экономическая сущность коэффициентов и состоит в том, что они показывают степень влияния каждого фактора на прибыль предприятия. Так, например, увеличение затрат капитала на один миллион рублей ведет к росту прибыли на 1,002626 миллиона рублей, увеличение трудовых затрат на один миллион рублей ведет к росту прибыли на 1,395363 миллион рублей. Лекция 9. Кластерный анализ 9 Иерархические кластер-структуры В статистических исследованиях группировка первичных данных является основным приемом решения задачи классификации. Обычно эта задача решается так. Из множества признаков, описывающих объект, отбирается один, наиболее информативный с точки зрения исследователя, и проводится группировка в соответствии со значениями данного признака. Если требуется провести классификацию по нескольким признакам (по степени важности), то сначала производится классификация по первому признаку, затем каждый из полученных классов разбивается на подклассы по второму признаку и т.д. Задача классификации при наличии нескольких признаков может быть решена и другими методами, одним из которых является метод кластерного анализа. Пусть исследуется совокупность n объектов, каждый из которых характеризуется по k замеренным на нем признакам X, то есть исходными данными служит таблица: . Требуется разбить эту совокупность на однородные в некотором смысле группы (классы). Полученные в результате разбиения группы называются кластерами. Методы нахождения кластеров называются кластер-анализом. Основным этапом решения задачи поиска кластеров является выбор способа вычисления расстояний или близости между объектами или признаками. Так может быть использовано обычное евклидово расстояние: , где – величина l-ой компоненты у i-ого признака (j-ого) объекта l=1,2,…,k, i,j=1,2,…,n. Расстояние между группами элементов особенно важно в так называемых иерархических кластер-процедурах. Принцип работы иерархических процедур состоит в последовательном объединении различных групп элементов сначала самых близких (далеких), а затем все более отдаленных (близких) друг от друга. Расстояние между кластерами Sl и S(m,q) можно найти по формуле: . Существуют и другие формулы для нахождения расстояний между элементами и кластерами. При реализации алгоритма иерархической классификации предусматривается графическое представление классификации в виде дендрограммы. Пример. Провести классификацию 6 объектов, каждый из которых характеризуется двумя признаками. номер объекта 1 2 3 4 5 6 хi1 5 6 5 10 11 10 хi2 10 12 13 9 9 7 Решение. Расстояние между объектами будем вычислять, как обычное евклидово. . Очевидно, что р11=0. Аналогично находим расстояния между остальными объектами и строим матрицу расстояний: R1=p(xi,xj)=. Из этой матрицы расстояний следует, что наиболее близки четвертый и пятый объект (4,5)=1 и поэтому их объединяем в один кластер. После объединения имеем пять кластеров: № кластера 1 2 3 4 5 Состав кластера (1) (2) (3) (4,5) (6) Расстояние между кластерами будем определять по указанной выше формуле. Так расстояние между объектом S1 и кластером S(4,5): . Таким образом, расстояние равно расстоянию от объекта 1 до ближайшего к нему объекта, входящего в кластер S(4,5), то есть . В этом случае говорят, что расстояние между кластерами определяем по принципу «ближайшего соседа». Следующая матрица расстояний имеет вид: R2=. Здесь наименьшее расстояние , то есть объекты 2,3 объединяем в кластер S(2,3) и получаем четыре кластера S(1), S(2,3), S(4,5), S(6). Находим вновь матрицу расстояний, используя матрицу R2. Например: =. После расчетов, получим матрицу расстояний: R3=. Здесь наименьшее расстояние . Объединяем эти элементы в один кластер. В результате получаем три кластера: S(1), S(2,3), S(4,5,6). Для этих кластеров матрица расстояний имеет вид: R4=. В этой матрице наименьшее расстояние . Объединяем кластеры S(1) и S(2,3). Получаем два кластера S(1,2,3), S(4,5,6). Результаты такой иерархической классификации объектов можно представить в виде дендрограммы:  5 4 3 2 1 1 2 3 4 5 6 2. Проведение кластерного анализа в пакете «Stadia» В пакете Stadia метод кластерного анализа позволяет: – строить дерево классификации n объектов посредством иерархического объединения их в группы или кластеры все более высокой общности на основе критерия минимума расстояния в пространстве m переменных, описывающих объекты; – находить разбиение некоторого множества объектов на заданное число компактных кластеров. Заметим, что кластерный анализ не содержит вычислительного механизма проверки гипотезы об адекватности получаемых классификаций. Исходные данные представляют в виде матрицы размером m·n., содержащую информацию одного из следующих трех типов: – измерение значений m переменных для n объектов; – квадратная (m=n) матрица расстояний между парами объектов; – квадратная (m=n) матрица близостей всех пар n объектов. В матрице близостей или расстояний может быть заполнена лишь нижняя левая половина (т. е поддиагональные элементы), а верхняя половина заполнена нулями. После запуска процедуры (Q =кластерный) в типовом бланке «Анализ переменных» нужно выбрать для анализа переменные из электронной таблицы, или же все переменные. Далее выбором из меню «Исходные данные» необходимо указать тип исходных данных: прямоугольная матрица, переменные (столбцы) и объекты (строки) или же квадратная матрица взаимных расстояний или близостей между всеми парами объектов. Если исходные представляют собой значение m переменных для n объектов, то далее из меню «Метрика вычисления расстояний» необходимо выбрать метод вычисления расстояния между объектами в многомерном пространстве. После этого из появившегося меню «Объединяющая» выбирают стратегию объединения (ближайшего соседа, дальнего соседа и т.д). В случае объединяющего метода задается вопрос о необходимости вывода диагональной матрицы расстояний между объектами, в которой строки будут соответствовать объектам (i=2,…, m), а столбцы – объектам от 1 до i – 1. Далее производится выдача последовательности кластеров возрастающей общности с указанием номеров входящих в кластеры объектов и расстояние, на уровне которого произошло объединение каждого кластера. После этого строится дендрограмма – дерево объединения кластеров с порядковыми номерами объектов по горизонтальной оси и со шкалой расстояний по вертикальной оси. Заметим, что в случае выбора дивизионной стратегии необходимо указать число кластеров, на которые желательно разбить множество объектов в соответствующем меню, причем окончательное количество кластеров может получиться меньше этого числа, если затребованного разбиения для этих данных невозможно. Пример. Провести классификацию 6 объектов, каждый из которых характеризуется двумя признаками. номер объекта 1 2 3 4 5 6 хi1 5 6 5 10 11 10 хi2 10 12 13 9 9 7 Для выполнения задания проделайте следующие пункты: 1. Откройте чистый рабочий лист в пакете Stadia. 2. Заполните таблицу на этом листе (без «Номер объекта», далее по столбцам). 3. Выполните команды: Статист=F9, среди многомерных методов выбрать Q – кластерный. 4. В появившемся окне «Анализ переменных» выбрать все. В окне «Исходные данные» выбрать «Переменные объекты». В окне «Метрика вычисления расстояний» выбрать «1 - Эвклид» после этого в меню «Объединяющие» выбрать «Ближайшего соседа». Вывод графиков проекции отменить. В итоге получаем результаты: КЛАСТЕРНЫЙ АНАЛИЗ. Файл: klastan.std Эвклид+Ближ.сосед Таблица расстояний (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (2) 2,236 (3) 3 1,414 (4) 5,099 5 6,403 (5) 6,083 5,831 7,211 1 (6) 5,831 6,403 7,81 2 2,236 К л а с т е р ы: (список объектов) -> расстояние (5,4) --> 1 (3,2) --> 1,414 (6,5,4) --> 2 (3,1,2) --> 2,236 (6,3,1,2,5,4) --> 5 Лекция 10. Дискриминантный анализ 1. Основные сведения о дискриминантном анализе Дискриминантный анализ это раздел многомерного статистического анализа, содержанием которого является разработка методов решения задач различия (дискриминации) объектов наблюдения по определенным признакам. Если перед вами стоит задача как по результатам измерений отнести объект к одному из нескольких классов, то применяется дискриминантный анализ. Методы дискриминантного анализа позволяют построить на основе ряда предположений классификационное правило отнесения объекта к одному из нескольких классов, минимизируя некоторый разумный критерий, например, вероятность ложной классификации или заданную пользователем функцию потерь. Выбор критерия определяется пользователем из соображений ущерба, который он понесет из-за ошибок классификации. Методы дискриминантного анализа находят применение в различных областях: социологии, психологии, медицине, экономике и т.д. Например они применяются для разбиения совокупности предприятий на несколько однородных групп, по значениям каких–то показателей производственно–хозяйственной деятельности. Для оценки финансового состояния своих клиентов при выдаче им кредита банк классифицирует их на надежных и не надежных по ряду признаков. Пусть результатом наблюдения над объектом является реализация k – мерного случайного вектора . Задача дискриминации состоит в разбивке всего множества реализаций рассматриваемой величины на некоторое число групп и последующем отнесении нового наблюдения в одно из них, используя некоторое решающее правило. При этом информация об истинной принадлежности объекта считается недоступной. Правило дискриминации выбирается в соответствии с определенным принципом оптимальности на основе априорной информации о совокупностях извлеченного объекта. Наиболее изучен случай, когда известно, что распределение векторов признаков каждой совокупности нормально, но нет информации о параметрах этого распределения. Здесь естественно заменить неизвестные параметры распределения дискриминантной функции их лучшими оценками. Правило дискриминации можно основывать на отношении правдоподобия. Аппарат дискриминантного анализа разрабатывался, начиная с конца 50 – х годов XX века. Дискриминантным анализом занимались П. Ч Махалонобис, Р. Фишер, Г. Хоттелинг и др. Исторически первой в дискриминантном анализе была модель Фишера, в которой предполагается, что наблюдаемые векторы имеют многомерное нормальное распределение с невырожденной ковариационной матрицей и вектором средних, разным для разных классов. 2. Проведение дискриминантнрого анализа в пакете «Stadia» В пакете Stadia для дискриминантного анализа исходные данные представляют в виде матрицы размеров в которой, первые столбцов содержат значения переменных для объектов, а - я переменная в качестве своих значений содержат для каждого объекта номер его класса (натуральные числа от 1 до , где - число классов). Объекты (строки) матрицы могут располагаться произвольно относительно номеров классов. Если кроме вычисления дискриминантной функции нужно с ее помощью классифицировать ряд новых объектов, то такие объекты также исходно включают матрицу данных с номером класса 0. В Блоке «Статистические методы» в разделе «многомерные методы» при выборе «p – Дискриминантный» в ходе вычислений ищется набор дискриминирующих функций , обеспечивающих классификацию объектов на заданное число классов: , Выдача результатов включает – суммарное межкластерное расстояние Махалонобиса = между классами с уровнем значимости = . Для нулевой гипотезы (о невозможности разбиения совокупностей объектов на заданное число классов) по хи – квадрат критерию с степенями свободы; – коэффициенты дискриминирующей функции, обеспечивающей отнесение объектов к данному классу, отдельно для каждого класса; – таблицу, где для каждого объекта (первый столбец) указывается номер его класса (второй столбец), расстояние Махаланобиса (от объекта до центра класса), уровень значимости нулевой гипотези «» (объект может быть отнесен к данному классу) по критерию хи – квадрат с - степенями свободы и апостеорная вероятность отнесения объекта к этому классу. Если соответствующая нулевая гипотеза может быть принята. Пример 1. Даны данные о 10 объектах (см. таблицу), каждый из которых представлен измерениями по двум переменным. Третья переменная представляет номера предполагаемых классов отнесения этих объектов. Причем объект №7 не отнесен ни к какому классу (имеет №0). Требуется определить, к какому классу он принадлежит? № объекта Признак 1 Признак 2 Класс 1 1.4 2.1 1 2 2.8 2.2 1 3 10.3 3.7 2 4 13.2 4.2 2 5 3.5 3.1 1 6 12.8 8.899 2 7 11.9 3.3 8 3.8 11.7 3 9 6.1 13.1 3 10 1.3 9.399 3 Для выполнения задания проделайте следующие пункты 1. Откройте чистый рабочий лист в пакете Stadia. 2. Заполните таблицу на этом листе без 1 столбца. 3. Выполните команды: Статист=F9, среди многомерных методов выбрать P – дискриминантный (P означает нажать букву P для быстрого выполнения команды). В итоге получаем результаты: ДИСКРИМИНАНТНЫЙ АНАЛИЗ. Файл: dikrim.std Расстояние Махаланобиса=42,59, значимость=5,157E-6 Класс <--- Коэффициенты дискриминантной функции:a[0],a[1],... ---> 1 -1,116 0,6394 0,2395 2 -26,44 5,137 -1,668 3 -19,03 -1,794 3,938 Объект Класс D^2 Значим Вероят.отнесения 1 1 0,5596 0,7559 1 2 1 0,1083 0,9473 1 3 2 1,152 0,562 1 4 2 2,623 0,2694 1 5 1 0,2813 0,8688 1 6 2 3,526 0,1715 1 7 2 2,077 0,354 1 8 3 0,03831 0,981 1 9 3 1,794 0,4078 1 10 3 1,917 0,3835 1 Выводы: как показывают результаты дискриминантного анализа, предполагаемая классификация оказалась эффективной (уровень значимости близок к нулю для гипотезы о нулевом межкластерном расстоянии ). Объект №7 с вероятностью 1 отнесен ко второму классу.