[ «МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ Кафедра прикладной математики ( x - a )2 1 f N ( a ; ...»
90. Для определения среднего дохода налогоплательщиков города налоговой инспекцией была проведена проверка 250 жителей этого города, отобранных случайным образом. Оценить вероятность того, что средний годовой доход жителей города отклонится от среднего арифметического X = i = более, чем на 1 000 руб., если известно, что среднее квадратичное отклонение годового дохода не превышает 2 500 руб.
РЕШЕНИЕ. Согласно неравенству (3.2.2), которым можно пользоваться, поскольку все DX i (2 500), P Задачи для самостоятельного решения 91. Средние ежедневные расходы на покупку канцелярских принадлежностей для офиса банка составляют 1000 руб., а среднее квадратичное отклонение этой случайной величины не превышает 200 руб. Оценить вероятность того, что расходы на канцелярские принадлежности в любой наугад выбранный день не превысят 2000 руб, используя неравенство Чебышёва.
92. Для определения вероятности того, что случайно выбранный избиратель отдаст на выборах голос за некоторого кандидата в депутаты, в избирательном округе планируется провести выборочный опрос 1000 избирателей. Оценить вероятность того, что относительная частота голосов «за кандидата» отклонится от искомой вероятности не более, чем на 0,1.
Законы больших чисел устанавливают факт приближения среднего значения большого числа случайных величин к некоторым постоянным в виде сходимости последовательностей случайных величин по вероятности и почти наверное. Но этим не ограничиваются закономерности, возникающие в результате суммарного действия случайных величин. Центральная предельная теорема представляет собой группу теорем, утверждающих, что достаточно большая сумма сравнительно малых случайных величин распределена приближённо по нормальному закону.
Следствие одной из таких теорем (теоремы Ляпунова) утверждает, что если независимые случайные величины X 1, X 2,…, X n имеют одинаковое распределение с распределению к нормальной случайной величине с параметрами a X = a, X =.
В ряде задач приходится сталкиваться с ситуацией, когда исследуемая случайная величина является суммой большого числа независимых слагаемых, влияние каждого из которых на сумму очень мало. Такими случайными величинами являются, например, капиталы банков и страховых компаний (доля каждого отдельно взятого вкладчика не зависит от доли других вкладчиков и относительно мала, но в сумме все эти доли весьма весомы), выручка торговых предприятий (покупатели действуют независимо друг от друга и покупают товары на относительно небольшие суммы) и др.
На основании центральной предельной теоремы часто можно до наблюдения того или иного явления сказать, что соответствующая случайная величина должна иметь нормальное распределение или близкое к нему.
С двумя следствиями из центральной предельной теоремы мы уже знакомы: это локальная и интегральная теоремы Муавра – Лапласа.
93. Суточная выручка в универсаме равна в среднем 100 000 руб. и в 90% случаев отличается от 100 000 руб. не более, чем на 10 000 руб. Найти вероятность того, что очередная суточная выручка окажется в пределах от 80 000 до 120 000 руб.
РЕШЕНИЕ. Пусть X — суточная выручка. Как было отмечено выше, покупатели действуют независимо друг от друга и покупают товары на относительно небольшие суммы X X, но покупателей в районе достаточно много, так что можно считать, что их количество n •. Поэтому суммарная выручка будет иметь нормальное распределение с некоторыми параметрами a и. Поскольку для нормального распределения a = MX, то по условию a = MX = 100 000. Также в условии сказано, что = 2 0 (2 1,65) = 2 0 (3,3) = 2 0, 4995 = 0,999.
Задача для самостоятельного решения 94. Банкомат выдает стандартные суммы в 500, 100 и 50 долл., причём первые составляют 10%, а последние — 60% всех выдач. В среднем банкомат производит 100 выдач в сутки. Определить размер денежной суммы, которую необходимо заложить в банкомат утром, чтобы этой суммы с вероятностью 0,9 хватило для выдачи наличности вкладчикам до следующего утра.
Глава 4. Основы выборочного метода. Точечные Генеральной совокупностью называют совокупность результатов всех мысленно возможных наблюдений над какой-либо случайной величиной X (в том числе, и повторяющихся), проводимых в одинаковых условиях. Иными словами, генеральная совокупность представляет собой набор всех возможных значений данной случайной величины. Как правило, огромный объём генеральной совокупности не позволяет просто переписать все её элементы, в таких случаях подвергают изучению ограниченное количество значений, отобранных из всей совокупности.
Выборочной совокупностью (или просто выборкой) называют результаты ограниченного числа наблюдений над случайной величиной X. Сущность выборочного метода состоит в том, чтобы по выборке как некоторой части генеральной совокупности делать выводы о всей генеральной совокупности в целом.
Выборку называют репрезентативной, если она адекватно отражает исследуемые свойства генеральной совокупности. Чтобы выборка была репрезентативной, можно организовать её следующим образом. Из генеральной совокупности случайным образом отбирается элемент и обследуется, после чего возвращается в общую совокупность и может быть отобран и обследован повторно.
Такая выборка называется повторной случайной. В повторной случайной выборке наблюдения X 1, X 2,…, X n независимы и проводятся в одинаковых (с вероятностной точки зрения) условиях, т. е. FX i ( x) = FX ( x), i = 1, 2,…, n.
Конкретной выборкой называется конкретный набор чисел x1, x2,…, xn, полученный в результате наблюдений за случайной величиной X, т. е. набор, состоящий из n реализаций случайной величины X.
Выборочным средним называется величина Эта величина является выборочным аналогом математического ожидания MX. Из теоремы Чебышёва (3.2.1) следует, что если DX < B, то поэтому при объёме выборки с вероятностью, большей, выполняется неравенство | X - MX |, т. е. гарантируется меньшая, чем, ошибка репрезентативности при замене математического ожидания MX выборочным средним X.
Пусть выборка состоит из n испытаний Бернулли, в которых произошло m успехов. Тогда выборочным аналогом вероятности успеха является относительная частота (или выборочная частость) Из теоремы Бернулли (3.2.3) следует, что поэтому при объёме выборки с вероятностью, большей, выполняется неравенство | p - p |, т. е. гарантируется меньшая, чем, ошибка репрезентативности при замене вероятности p относительной частотой p. Поскольку для любых p [0,1] p (1 - p ) 1, то при неизвестной p неравенство для n можно заменить на Если случайная величина X распределена по нормальному закону с параметрами a и, а DX = 2 < B, то согласно центральной предельной теореме (см. § 3.3) поэтому при объёме выборки (где u / 2 — такое число, что 0 (u / 2 ) = / 2 ) с вероятностью, большей, выполняется неравенство | X - MX |, т. е. гарантируется меньшая, чем, ошибка репрезентативности при замене математического ожидания MX выборочным средним X. Эту же формулу для объёма выборки используют и в случае, когда n велико, и есть основания пользоваться центральной предельной теоремой.
В частности, при большом числе испытаний Бернулли n и не очень малой вероятности p (такой, что np > 10 ) в силу локальной и интегральной теорем МуавраЛапласа (1.5.4) – (1.5.5) относительная частота p имеет нормальное распределение с (где u / неравенство | p - p |, т. е. гарантируется меньшая, чем, ошибка репрезентативности при замене вероятности p частостью p.
Выборочным аналогом дисперсии является, например, величина называемая выборочной дисперсией.
( x2 ; y2 ),…,( xn ; yn ) можно вычислить выборочную ковариацию или и выборочный коэффициент корреляции Предлагаем читателю самостоятельно убедиться в эквивалентности формул (4.1.13) и (4.1.14).
Несложно также показать, что выборочный коэффициент корреляции заключён в пределах от (–1) до 1 и характеризует близость зависимости между выборками x и y к линейной (рис. 4.1.1).
Чем ближе точки (xi; yi) расположены к некоторой прямой, тем ближе значение модуля выборочного коэффициента корреляции | ( X, Y ) | к единице, и наоборот, чем ближе | ( X, Y ) | к единице, тем ближе точки (xi; yi) расположены к некоторой прямой.
При этом выборочный коэффициент корреляции ( X, Y ) положителен [отрицателен] тогда и только тогда, когда при увеличении одной из величин x, y значения другой имеют тенденцию к увеличению [соответственно, к уменьшению], т. е. прямая, около которой расположены точки (xi; yi), имеет положительный [соответственно, отрицательный] наклон.
Рис. 4.1.1. Виды зависимости между выборками: а — сильная линейная прямая, ( X, Y ) 1 ; б — слабая линейная прямая, ( X, Y ) -0,5 ; в — отсутствие зависимости, ( X, Y ) 0 ; г — сильная нелинейная, ( X, Y ) 0 ; д — зависимость, не являющаяся корреляционной, ( X, Y ) 0 ; е — слабая линейная обратная, ( X, Y ) -0,5 ;
Значение выборочного коэффициента корреляции, близкое к нулю, означает отсутствие линейной связи между переменными, но при этом может наблюдаться сильная нелинейная корреляционная зависимость (как на рис. 4.1.1, г, где точки расположены близко к некоторой параболе) или статистическая связь, которую в виде функциональной зависимости переменных представить невозможно, так, на рис. 4.1.1, д приведён пример статистической зависимости, когда с увеличением x растёт разброс точек по оси y, однако никакой функцией y = f(x) (линейной или нелинейной) такую зависимость выразить нельзя.
95. Дисперсия случайной величины X не превышает 10. Требуется: а) оценить вероятность того, что отклонение выборочного среднего , рассчитанного по 16 000 результатов наблюдений случайной величины (независимых, проведенных в одинаковых с вероятностной точки зрения условиях) от математического ожидания MX не превысит 0,25;
б) определить, сколько следует провести наблюдений, чтобы с вероятностью, не меньшей 0,99, можно было утверждать, что ошибка репрезентативности при замене математического ожидания MX выборочным средним x не превысит 0,2.
РЕШЕНИЕ. а) По формуле (4.1.2), в которой n = 16 000, B =10, = 0, 25, получаем:
б) По формуле (4.1.3), в которой случайной величины и воспользовавшись (4.1.9) и тем, что u / 2 =u0,99 / 2 =u0,495 = 2, (так как 0 (2,55) = 0, 495 — см. табл. П.1 в пособии [3]), получим:
96. Известно, что в среднем из каждой тысячи кредитов, выданных на развитие малого предпринимательства 30 не возвращаются. Определить, сколько нужно отобрать предприятий, чтобы с вероятностью, не меньшей 0,9, можно было бы ожидать, что доля предприятий в выборке, не возвращающих кредиты, будет отличаться от доли аналогичных предприятий в генеральной совокупности меньше, чем на 0,01.
(1 - ) (1 - 0,9)0, При этом, поскольку np > 792, 25 0,03 = 23 > 10, есть основания пользоваться теоремами Муавра — Лапласа. Таким образом, необходимо отобрать 793 предприятия.
97. Вычислить выборочный коэффициент корреляции по результатам наблюдений двумерной случайной величины:
РЕШЕНИЕ.
Y = 10, 25; X 1,58; Y = 3, 20 и подставляем рассчитанные значения в формулу 98. Определить количество респондентов, которых необходимо опросить, чтобы рейтинг президента (доля граждан, поддерживающих Президента), вычисленный по выборке, с вероятностью, не меньшей 0,99, отличался от истинного рейтинга президента для всех жителей страны не более, чем на 5% по абсолютной величине.
99. Компания, управляющая зданиями, желает по выборке оценить среднюю стоимость эксплуатации квартир определенного типа с надежностью 99% и ошибкой репрезентативности ±10 ден. ед. Определить объем выборки, необходимой для такой оценки, если из подобного же исследования, проведенного ранее, известно, что среднее квадратичное отклонение стоимости эксплуатации не превышает 50 ден. ед.
100. Вычислить выборочный коэффициент корреляции по результатам наблюдений двумерной случайной величины:
Расположив элементы выборки в порядке неубывания, получим вариационный ряд.
Далее будем считать, что именно в таком порядке уже расставлены выборочные наблюдения. Выборочной случайной величиной называется при этом дискретная случайная величина X, задаваемая рядом распределения Если в вариационном ряде есть повторяющиеся элементы, то выборку можно записать в виде статистического ряда распределения, т. е. дискретной случайной величины в которой xi (i = 1, 2,…, l ) — это варианты (расположенные по возрастанию различm ные элементы выборки), а p i = i (i = 1, 2,…, l ) — отвечающие этим значениям часn тости (здесь mi — частота варианты x, т. е. количество ее появлений в статистиi ческом ряде распределения). При этом, очевидно, n = mi.
Выборочное среднее и выборочную дисперсию можно при этом вычислить пор формулам Для н е п р е р ы в н ы х случайных величин при достаточно больших объемах выборки n вместо статистического ряда распределения используют интервальный вариационный ряд Ширина интервала (здесь x(min) — минимальный элемент выборки, а x(max) — максимальный, расчет производится с числом знаков после запятой, на один большим, чем в исходных данных). Границы интервалов рассчитываются по правилу:
a1 = x(min) -, a2 = a1 +, a3 = a2 +,… ; формирование интервалов заканчивается, как только для конца a +1 очередного интервала выполняется условие a +1 > x(max). Значеmi ния p i = — это выборочные интервальные частости: mi — число вариант, поn павших в i -й интервал ( i = 1, 2,…, ).
По интервальному вариационному ряду оценки математического ожидания и дисперсии вычисляются точно так же, как и по статистическому ряду распределения, при этом xi = i и, например, выборочное среднее можно рассчитывать по формуле (4.2.3), а выборочную дисперсию — по формуле (4.2.4).
Выборочным аналогом плотности распределения f X ( x) случайной величины X служит выборочная плотность распределения, рассчитываемая по интервальному вариационному ряду как график этой функции называется гистограммой, а ломаная с вершинами в точках тот. Кривая распределения частостей — это ломаная с вершинами ( xi; p i ).
По выборочной плотности распределения легко построить выборочную функцию распределения при этом ломаная с вершинами в точках xi; p k называется кумулятой.
101. Ежедневные суммарные денежные вклады населения (в тыс. руб.) в отделение банка в течение последних 20 рабочих дней были такими: 60;
20; 70; 70; 30; 20; 50; 50; 40; 60; 30; 40; 30; 50; 50; 60; 50; 60; 40; 40. Построить статистический ряд распределения, оценить средний суммарный дневной вклад и его среднее квадратичное отклонение.
РЕШЕНИЕ. Расположив элементы выборки в порядке возрастания, получим вариационный ряд:
20; 20; 30; 30; 30; 40; 40; 40; 40; 50; 50; 50; 50; 50; 60; 60; 60; 60; 70; 70.
Построим теперь статистический ряд распределения:
Средний суммарный дневной вклад оценим с помощью выборочного среднего — с помощью выборочной дисперсии (4.2.4) X = ( xi) p i - xi p i = = 2330 – 2116 = 214, при этом выборочное среднее квадратичное отклонение составит X = 214 = 14,63.
102. Построить интервальный вариационный ряд, полигон частот, гистограмму и кумуляту, оценить средний рост студента и его среднее квадратичное отклонение по данным о росте 30 студентов (в см): 182; 171; 186;
175; 188; 177; 176; 178; 183; 187; 167; 180; 182; 179; 176; 179; 172; 173;
183; 168; 180; 179; 172; 177; 175; 173; 189; 176; 190,5; 172.
РЕШЕНИЕ. Определим длину интервала:
При этом интервальный вариационный ряд будет иметь вид X [165;169) [169;173) [173;177) [177;181) [181;185) [185;189) [189;193) Теперь по интервальному вариационному ряду построим выборочную плотность распределения и выборочную функцию распределения:
Гистограмма (тонкая линия) и полигон частот (полужирная линия) представлены на рис. 4.2.1, а, а кумулята — на рис. 4.2.1, б соответственно. По их внешнему виду можно предположить, что рост студента подчиняется нормальному закону распределения.
Средний рост студента оценим с помощью выборочного среднего (4.2.3) при этом выборочная дисперсия (4.2.4) составит X = ( xi) p i - xi p i = 0, 0, 0, 0, 0, 0, 0, Рис. 4.2.1. Гистограмма (тонкая линия), полигон частот (полужирная линия) (а) и 103. По данным задачи 101 построить вариационный ряд, статистический ряд распределения, полигон частот, гистограмму, кумуляту.
104. По выборке 11; 11; 11; 9; 9; 5; 10; 10; 10; 14 построить вариационный ряд, статистический ряд распределения, полигон частот, гистограмму, кумуляту, вычислить выборочное среднее и выборочную дисперсию.
Статистикой называется любая функция = ( X 1, X 2,…, X n ) от элементов выборки X 1, X 2,…, X n (на конкретной выборке x1, x2,…, xn эта статистика принимает конкретное значение = ( x1, x2,…, xn ) ). Очевидно, любая статистика является случайной величиной, поскольку она является функцией случайных величин.
Напомним, что оценкой числовой характеристики или параметра называется любая статистика = ( x1, x2,…, xn ), используемая в качестве приближенного значения. Качество оценки определяется по выполнению следующих трех свойств: состоятельности, несмещенности и эффективности.
Прежде всего, от оценки n хотелось бы требовать, чтобы по мере роста числа наблюдений она сходилась по вероятности к оцениваемому параметру, т. е. чтобы для любого, сколь угодно малого, > 0 было справедливо предельное равенство Оценка n, обладающая свойством (4.3.1), называется состоятельной оценкой параметра.
Также от «хорошей» оценки n естественно требовать, чтобы она не содержала систематической ошибки, т. е. при любом фиксированном объеме выборки n результат осреднения оценки по всем возможным выборкам данного объема должен приводить к точному значению параметра:
Оценка n, обладающая свойством (4.3.2), называется несмещенной оценкой параметра.
Наконец, от оценки n желательно требовать, чтобы ее дисперсия была минимальной в некотором классе оценок :
Оценка n, обладающая свойством (4.3.3), называется эффективной оценкой параметра в классе оценок.
Выборочное среднее X (4.1.1) является состоятельной, несмещенной и эффективной (в классе линейных несмещенных оценок) оценкой математического ожидания Выборочная частость p (4.1.4) является состоятельной, несмещенной и эффективной (в классе линейных несмещенных оценок) оценкой вероятности успеха p.
Выборочная дисперсия X (4.1.11) является смещенной оценкой дисперсии DX :
Однако это легко исправимо, если в качестве оценки дисперсии выбрать величину называемую исправленной выборочной дисперсией; исправленная выборочная дисперсия s X является состоятельной и несмещенной оценкой дисперсии.
Если известно точное значение a = MX математического ожидания нормальной случайной величины X, то статистика является состоятельной, несмещенной и эффективной (в классе всех несмещенных оценок) оценкой дисперсии DX случайной величины X. Однако на практике оценка (4.3.6) не используется, так как точное значение математического ожидания почти никогда не известно.
Будем считать, что известен общий вид p ( x;) закона распределения случайной величины X, соответствующей генеральной совокупности, из которой извлечена выборка x1, x2,…, xn (функция вероятности p ( xi ;) = P{ X = xi } для дискретной случайной величины или плотность распределения p ( x;) = f X ( x) для непрерывной случайной величины), где — некоторый неизвестный параметр закона распределения.
Теоретическим начальным моментом порядка k (k = 0,1, 2,…) случайной величины X называется величина k = M ( X k ) Выборочным начальным моментом порядка k (k = 1, 2,…) называется статистика k = X k.
Метод моментов заключается в следующем. Определяется зависимость параметра от начальных моментов с первого по k-й и центральных моментов с первого по l-й, после чего для вычисления оценки мм параметра по методу моментов в эту зависимость (4.3.7) вместо неизвестных теоретических моментов подставляют их выборочные аналоги i и µ j :
Очевидным достоинством метода моментов является его простота, однако качество оценок, полученных с помощью этого метода, не всегда бывает высоким, особенно при небольших объемах выборки.
Изложим теперь алгоритм метода максимального правдоподобия. По выборке x1, x2,…, xn составляется функция правдоподобия равная вероятности получения именно набора x1, x2,…, xn при извлечении выборки объемом n из генеральной совокупности в случае дискретной случайной величины (и плотности распределения этой вероятности — в случае непрерывной случайной величины). Чем больше L(), тем вероятнее (или правдоподобнее) получить при наблюдениях именно данную конкретную выборку x1, x2,…, xn.
Оценкой максимального правдоподобия параметра называют при этом такое значение ммп, которое максимизирует функцию правдоподобия L() :
Для многих распределений вместо оптимизационной задачи (4.3.10) удобнее решать эквивалентную задачу так как натуральный логарифм является монотонно возрастающей функцией.
Если существует состоятельная и эффективная оценка параметра (в классе всех оценок — несмещенных и смещенных), то при весьма общих условиях = ммп, если при этом оценка ммп оказывается смещенной, то ее подправляют аналогично тому, как это было сделано с выборочной дисперсией [см. формулу (4.3.5)].
105. Доказать, что выборочное среднее X является состоятельной и несмещенной оценкой математического ожидания MX.
РЕШЕНИЕ. Выборочное среднее X является состоятельной оценкой математического ожидания, если генеральная совокупность имеет ограниченную дисперсию, поскольку предельное равенство lim P{ X - MX } = 1 непосредственно следует из Из того, что M X = MX, следует также, что выборочное среднее X является несмещенной оценкой математического ожидания MX.
106. Доказать, что выборочная дисперсия X является смещенной оценn - РЕШЕНИЕ. Действительно, при этом: по определению дисперсии M( X i2 ) = DX i + (MX i ) 2 = 2 + a 2 ; поскольку наблюдения X i и X j независимы, M ( X i X j ) = MX i MX j (при i j ), и наконец, Подставляя найденные выражения для математических ожиданий в формулу для M X, получим:
поэтому выборочная дисперсия является смещенной оценкой дисперсии.
107. Доказать, что для того, чтобы несмещенная оценка n была состоятельной, достаточно, чтобы lim D n = 0.
P{ | n - M n | } > 1 - 2, откуда, учитывая несмещенность оценки n (т. е.
M n = ), получаем: P{ | n - | } > 1 - 2, и поскольку lim D n = 0, окончательно имеем, что lim P{ | n - | } = 1, т. е. n является состоятельной оценкой.
108. По выборке x1, x2,…, xn найти оценку параметра распределения Пуассона: а) методом моментов; б) методом максимального правдоподобия.
РЕШЕНИЕ. а) Известно, что начальный момент первого порядка распределения Пуассона равен 1 = MX =, откуда = 1 = MX. Поэтому оценкой метода моментов для параметра будет мм = 1 = x.
правдоподобия:
Ее логарифм равен Чтобы функция l () достигала максимального значения, необходимо, чтобы ее производная l () = 0, а вторая производная l () < 0. В нашем случае поэтому оценку максимального правдоподобия найдем из условия ммп = = x. При этом вторая производная отрицательна, так как в числителе дроn би стоит положительное число (поскольку генеральная совокупность распределена по закону Пуассона и ее элементы не могут принимать отрицательных значений), в знаменателе дроби также стоит положительное число ммп, а перед дробью стоит знак «минус».
109. Случайная величина X R(a; b). По выборке x1, x2,…, xn найти оценки параметров a и b : а) методом моментов; б) методом максимального правдоподобия.
РЕШЕНИЕ. а) Найдем оценки a мм и b мм методом моментов. Известно, что тельно a и b (учитывая, что a < b ), получим: a = 1 - 3µ 2, b = 1 + 3µ 2, а потому a ммп = min{x1, x2,…, xn } и b ммп = max{x1, x2,…, xn }.
110. Доказать, что частость является состоятельной, несмещенной и эффективной (в классе всех несмещенных оценок) оценкой вероятности наступления события.
111. Построить по выборке x1, x2, …, xn оценку p мом метода моментов и оценку p мп метода максимального правдоподобия для параметра p геометрического распределения.
112. По выборке x1, x2,…, xn найти оценку параметра µ показательного распределения: а) методом моментов; б) методом максимального правдоподобия.
113. Случайная величина X N (a;). По выборке x1, x2,…, xn найти оценки параметров a и : а) методом моментов; б) методом максимального правдоподобия.
114. По данным социологического опроса получено распределение числа групп по числу респондентов в группе, отрицательно отзывающихся о новой рекламной политике фирмы (в каждой группе по 10 респондентов):
Число респондентов, не поддерживающих Предполагая, что число респондентов в группе, не поддерживающих новую рекламную политику, распределено по закону Пуассона, оценить параметр этого закона и определить долю групп, в которых все респонденты поддерживают новую рекламную политику.
Глава 5. Интервальные оценки параметров. Проверка статистических гипотез Вычисляя по выборке оценку какого-либо параметра, мы отдаём себе отчёт, что даже если она будет обладать свойствами состоятельности, несмещенности и эффективности, она всё равно остаётся всего лишь приближённым значением параметра. Насколько же может отклониться это приближённое значение от истинного?
Иными словами, можно ли указать интервал (1 ; 2 ), который с заранее заданной вероятностью (близкой к единице) накрывал бы истинное значение параметра. Такой интервал называется доверительным интервалом или интервальной оценкой, а вероятность — доверительной вероятностью или надёжностью интервальной оценки.
Предположим, что наблюдения независимы и проводятся в одинаковых условиях, т. е. элементы выборки X 1, X 2,…, X n представляют собой независимые случайные величины, распределённые по одному и тому же закону с математическим ожиданием a и дисперсией 2. Тогда, если объём выборки n велик (на практике — при n > 30 ), то в силу центральной предельной теоремы (см. § 3.3) случайная величина X = имеет нормальное распределение с параметрами a и, поэтому, как несложно поn параметрами 0 и 1.
Найдём по таблице значений функции Лапласа 0 такое значение u/2, чтобы Если выбрать уровень значимости, то и критическая область определяется неравенством Обратим внимание на то, что критерий Пирсона можно использовать только в том случае, когда npiтеор 5, поэтому разряды, для которых это условие не выполняется, необходимо объединить с соседними.
119. Из многолетнего опыта руководитель отдела продаж знает, что в среднем каждые три из десяти визитов коммерческого представителя к предполагаемым клиентам заканчиваются подписанием контракта. Продавец Иванов за последний месяц провел 100 встреч с предполагаемыми клиентами и заключил 48 договоров, после чего потребовал повышения зарплаты. Какое решение должен принять начальник Иванова: «Иванов — выдающийся продавец» либо «Иванов — такой же, как все остальные, и его высокие результаты объясняются только случайностью»?
РЕШЕНИЕ. Выберем уровень значимости = 0,05, т. е. допустим возможность ошибки первого рода с вероятностью 0,05. Будем проверять нулевую гипотезу H0: p = p0, состоящую в том, что Иванов — такой же, как все остальные, т. е. вероятность заключения договора Ивановым равна средней вероятности заключения договора p = = 0, 3. В качестве альтернативной выберем гипотезу H1: p > p0, соответствующую тому, что Иванов выдающийся продавец, и у него вероятность заключения контракта выше, чем у остальных его коллег.
В предположении справедливости нулевой гипотезы (т. е. если p = p0) можно записать, согласно (5.1.3), формулу = 0,05 частость окажется правее этого интервала и с вероятностью = 0,05 — левее).
Отметим этот интервал на координатной оси (рис. 5.2.1). Он разобьет всю числоp (1 - p0 ) — справа от интервала.
Если справедлива гипотеза H0: p = p0, то частость p =, рассчитанная по выбоn рочным данным, скорее всего (с вероятностью ), попадет в центральную область;
при этом такая ситуация, чтобы при истинной гипотезе H0 частость попала в самую вероятна, если считать, что p > p0, поэтому критической областью является область нулевая гипотеза H0: p = p0 отвергается, и принимается гипотеза H1: p > p0.
Рис. 5.2.1 Критическая область (заштрихована) и область принятия нулевой гипотезы в задаче В нашем случае = 0,9, n = 100, p = = 0, 48, p0 = 0,3, с помощью Microsoft Exp (1 - p ) cel получаем u/2 = u0,45 = НОРМСТОБР((1 + 0,9)/2)) = 1,64, p0 + u / 2 0 0= = 0,3 + 1,65 = 0,3 + 1,65 0,38, поэтому неравенство (*) выполняется, что является основанием отвергнуть нулевую гипотезу и принять альтернативную гипотезу, состоящую в том, что вероятность заключение контракта Ивановым выше, чем средним сотрудником.
Преобразуем неравенство (*):
Теперь можно при проверке нулевой гипотезы H0: p = p0 при альтернативной гипотезе H1: p > p0 вычислить по выборочным данным значение статистики Z= и сравнить его с критическим значением u/2. Критической области при этом соответствует неравенство Z > u / 2.
120. Торговая компания собирается открыть в новом районе города филиал. Из опыта работы компании известно, что филиал будет работать прибыльно, если за неделю средний доход жителей района превышает ден. ед.; также известна дисперсия дохода 2 = 400. Требуется:
а) определить правило принятия решения, с помощью которого, основываясь на выборке объемом n = 100 и уровне значимости = 0, 05, может быть установлено, что филиал будет работать прибыльно;
б) предположив, что в действительности средний доход за неделю достигает 406 ден. ед., рассчитать вероятность того, что при применении предложенного правила принятия решения будет совершена ошибка второго рода.
РЕШЕНИЕ. а) Компания не откроет филиал, если средний доход жителей не превысит 400 ден. ед. Потому будем считать, что H 0 : a = a0 = 400, H1 : a > a0. Так как значение генеральной дисперсии 2 = 400 известно, то гипотезу H 0 принимают, если H1 : a > a0 принимают и, следовательно, филиал открывают, если если недельный среднедушевой доход 100 жителей x > 400 + 2 1,65 = 403,3.
б) Альтернативное значение среднего дохода равно a1 = 430, и гипотеза H1: a = 406 > a0. В этом случае вероятность ошибки второго рода 121. Производитель электроламп утверждает, что средний срок их службы составляет a0 = 1000 ч. Проверить эту гипотезу на 5%-ном уровне значимости по выборке из n = 25 ламп, для которой x = 875 ч, s = 50 ч.
РЕШЕНИЕ. Будем проверять на уровне значимости = 5% = 0,05 нулевую гипотезу H 0 : MX = a0 о том, что математическое ожидание срока службы лампы равно a0 = 1 000 ч при альтернативной гипотезе H1 : MX < a0, что на самом деле математическое ожидание срока службы лампы меньше, чем заявляет их произtn-1; 2 = t24; 0,1 = 21,71, T = ( x - as0 ) n = (875-1000) 25 = -12,5. Поскольку T > -tn -1;2, нулевую гипотезу H 0 не отвергаем, т. е. считаем, что производитель не завышает истинный срок службы ламп.
122. Были случайно отобраны 80 банковских счетов, и зафиксированы остатки на них. Результаты представлены в виде таблицы:
Остаток на счете, [2, 5; 3, 5) [3, 5; 4, 5) [4, 5; 5, 5) [5, 5; 6, 5) [6, 5; 7, 5) [7, 5; 8, 5) [8, 5; 9, 5) [9, 5; 10, 5) тыс. ден. ед.
Число вкладчиков Проверить на 5%-ном уровне значимости гипотезу о том, что остаток на счете распределен по нормальному закону.
РЕШЕНИЕ. Построим по данному интервальному вариационному ряду гистограмму и полигон (рис. 5.2.2). По их виду, действительно, можно предположить, что наблюдаемая случайная величина распределена по нормальному закону с параметрами a и. Значения параметров возьмем равными их несмещенным, состоятельным и эффективным оценкам: a = x; = s. Вычислим эти оценки:
s = 2,38 1,54.
На том же рис. 5.2.2 начертим график кривой нормального распределения с параметрами a = 6,5125, = 1,54.
Рис. 5.2.2 Гистограмма, полигон и кривая теоретического распределения в задаче Между гистограммой и кривой распределения есть различия. Выясним, можно ли на 5%-ном уровне значимости отнести эти различия на счет случайности, или же мы выдвинули ложную гипотезу.
торые приходятся на каждый интервал (при этом первый интервал считаем начинающимся в точке ( -• ), а последний интервал — заканчивающимся в точке ( +• )).
Аналогично, p2 = P{3,5 X < 4,5} = 0,0704, p3 = P{4,5 X < 5,5} = 0,1598, p4 = = P{5,5 X < 6,5} = 0, 2413, p5 = P{6,5 X < 7,5}= 0, 2426, p6 = P{7,5 X < 8,5}=0,1623, p7 = P{8,5 X < 9,5} = 0,0722, p8 = P{ X 9,5} = 0,0262. Дальнейшие вычисления для удобства и наглядности сведем в табл. Критерий Пирсона можно использовать только в том случае, когда npiтеор 5, поэтому интервалы, для которых это условие не выполняется, объединим с соседними. Новое число интервалов обозначим = 6.
Окончательное значение 2 -l -1 равно сумме величин в последнем столбце, т. е.
3,0934.
Теперь найдем критическую точку 2 -l -1;. Для этого, прежде всего, рассчитаем число степеней свободы: при расчете 2 -l -1 использовалось = 6 интервалов, у предполагаемого нормального распределения были неизвестны l = 2 параметра, поэтому - l - 1 = 6 - 2 - 1 = 3. С помощью Microsoft Excel находим не отвергаем.
Задачи для самостоятельного решения 123. Инвестиционный фонд объявил, что доходность по вложениям в него превысила среднерыночную на 0,003. В течение последнего года средняя доходность по рынку составила 0,005, а средняя доходность по фонду составила 0,0065 с исправленным средним квадратичным отклонением 0,019. Проверить на 5%-ном уровне значимости, насколько справедливо заявление фонда.
124. Продюсер некоторой телепередачи утверждает, что она должна привлечь внимание, по крайней мере, трети телезрителей. Из 64 опрошенных только 16 заявили о своем намерении посмотреть эту передачу. Оценить утверждение продюсера на 5%-ном уровне значимости.
125. Средняя оценка контрольной работы в студенческой группе из 25 человек оказалась равной 3,25. После контрольной работы преподаватель провел консультацию, после чего была повторно написана контрольная работа, и средняя оценка оказалась равной 3,3. Проверить на 5%-ном уровне значимости, помогла ли консультация, считая средние квадратичные отклонения оценок известными и в обоих случаях равными 126. Такси оснащается двумя видами шин A и B. Десять шин вида A имеют x1 = 40 000 км, s1 = 5 950 км, двенадцать шин вида B — x2 = км, s2 = 5150 км. Определить, существенно ли различие между стойкостью двух видов шин, если генеральные совокупности нормальны и 127. Для каждого из 100 компьютеров в офисе фирмы регистрировалось число поломок в течение года:
Проверить на 5%-ном уровне значимости гипотезу о том, что число поломок компьютера за год распределено по закону Пуассона.
128. Дано распределение успеваемости 50 студентов, сдавших 4 экзамена в сессию:
Проверить на уровне значимости = 0,1 гипотезу о том, что число сданных экзаменов (из четырех) имеет биномиальный закон распределения.
Глава 6. Основы корреляционно-регрессионного По результатам ( X 1; Y1 ),( X 2 ; Y2 ),…,( X n ; Yn ) наблюдений двумерной случайной величины ( X ; Y ) можно вычислить выборочную ковариацию по формулам или и выборочный коэффициент корреляции Результаты ( x1 ; y1 ),( x2 ; y2 ),…,( xn ; yn ) наблюдений двумерной случайной величины ( X ; Y ), отмеченные на двумерном графике, называются полем корреляции (или диаграммой рассеяния).
По выборке ( x1 ; y1 ),( x2 ; y2 ),…,( xn ; yn ) из двумерной непрерывной генеральной совокупности ( X ; Y ) можно составить двумерный интервальный вариационный ряд, который записывается обычно в виде корреляционной таблицы:
Интервалы переменных X и Y образуются по тем же правилам, что и для одномерных выборок. По такой корреляционной таблице можно вычислить коэффициент корреляции при этом будет вычисляться по формуле (6.1.3).
Выборочный коэффициент корреляции характеризует линейность связи между случайными величинами X и Y и обладает следующими свойствами:
Предположим, что зависимость фактора Y от фактора X описывается уравнением где — случайная величина, отражающая влияние на Y прочих, неконтролируемых, факторов.
Метод наименьших квадратов рекомендует находить оценки и неизвестных параметров, уравнения (6.1.13), исходя из требования означающего, что сумма квадратов отклонений значений Yi, рассчитанных по уравнению линейной регрессии от наблюдений yi случайной величины Y, зафиксированных при значениях xi фактора X, должна быть минимальной.
Метод наименьших квадратов гарантирует получение «наилучших» оценок параметров регрессии при выполнении следующих условий:
• наблюдения случайной величины Y должны быть независимыми;
• при каждом фиксированном значении фактора наблюдения случайной величины Y проводятся в типичных условиях, а их результаты распределены по нормальному закону с дисперсией, не изменяющейся при переходе от одного значения фактора к другому;
• случайный эффект влияния прочих неконтролируемых факторов в регрессии (6.1.13) в среднем равен нулю, т. е. M = 0.
Отметим, что «качество» оценок, полученных с помощью метода наименьших квадратов, растёт с ростом числа наблюдений.
Запишем частные производные, взятые от суммы квадратов отклонений T :
Необходимые условия минимума в (6.2.2) приводят к так называемой нормальной системе уравнений:
В результате решения этой системы получаем оценки параметров парной линейной регрессии (6.1.13). Предлагаем самостоятельно получить эти оценки из системы (6.1.16).
Подставляя оценки (6.1.17) в уравнение линейной регрессии (6.1.15), получаем:
129. Исследуется зависимость между годовыми рекламными бюджетами X (тыс. ден. ед.) дилеров некоторой компании и среднемесячными объемами продаж Y (тыс. ден. ед.) соответствующих дилеров. Сведения по 60 дилерам сгруппированы в корреляционную таблицу:
[0,05;1,40) [1,40;2,75) [2,75;4,10) [4,10;5,45) [5,45;6,80) m y Построить поле корреляции и вычислить коэффициент корреляции между объемами средств, вложенных в рекламу, и объемами продаж.
РЕШЕНИЕ. Построим на рис. 6.1.2 поле корреляции — прямоугольную сетку, в каждом прямоугольнике [a j ; a j +1 ) [bi ; bi +1 ) которой проставляется mij точек.
Последовательно вычисляем x = 2,62, y = 0,65, X = 9, 46 - (2,62) 2 = 2,62, Y = =0,52-(0,65) 2 = 0,10, cov( X,Y ) = 2,07 - 2,62 0,65 = 0, 37.
Таким образом, выборочный коэффициент корреляции по формуле (6.1.3) равен 130. В следующей таблице приведены значения численности персонала предприятий холдинга X (тыс. чел.) и годовой прибыли Y (млн. ден. ед.):
Требуется оценить степень зависимости между прибылью и численностью персонала.
РЕШЕНИЕ. Отметим на рис. 6.1.2 пары точек (Xi ; Yi ). Видно, что наблюдается тенденция одновременного роста обоих показателей: чем больше численность сотрудников, тем больше прибыль предприятия.
Вычислим выборочную ковариацию. Для удобства расчётов составим табл.
Выборочная ковариация (6.1.1) при этом равна сумме элементов последнего столбца: cov( X, Y ) = 7,75.
о наличии слабой линейной корреляционной связи между между прибылью и численностью персонал.
Риc. 6.1.2. Поле корреляции и график линейной регрессионной зависимости Линейное уравнение регрессии Yi - y = Y ( X, Y )( xi - x) после подстановки оцеX нок примет вид Yi = 6,5 + 0,65( xi - 6,5). График этой линии представлен на рис.
6.1.2.
Задачи для самостоятельного решения 131. Построить поле корреляции и вычислить коэффициент корреляции между среднемесячной квартирной платой X в долл. США и уровнем преступности Y по данным 140 небольших земельных участков города Чикаго, сгруппированным в корреляционную таблицу:
132. Построить диаграммы рассеяния и вычислить выборочные коэффициенты корреляции по результатам наблюдений двумерных случайных величин:
133. Для измерения склонности учащихся к абстрактному мышлению X и их склонности к вербальному мышлению разработаны два теста, по 50 вопросов каждый. Результаты тестирования 15 школьников таковы (результатом теста является число верных ответов):
xi 19 32 33 44 28 35 39 39 44 44 24 37 29 yi 10 19 17 45 27 31 20 17 35 43 10 28 20 Построить диаграмму рассеяния, вычислить выборочный коэффициент корреляции.
134. Средние месячные значения фондового индекса I и котировок акции E за один год таковы:
Составить уравнение линейной регрессии котировок акции на значения индекса. На одном рисунке построить график эмпирической функции регрессии и отметить точки наблюдения.
135. Провести регрессионный анализ зависимости оценки социального статуса Y от дохода X в тыс. ден. ед., предположив линейность функции регрессии по следующим данным:
На графике изобразить наблюдения, прямую регрессии, интервальный прогноз оценки социального статуса при данных размерах дохода. Убедиться в том, что прямая регрессии пройдет через точку ( X ; Y ).
136. Определить функцию спроса (зависимости сбыта от цены товара) по следующим данным:
137. Исследовать линейную регрессионную зависимость между котировками двух ценных бумаг X и Y по среднемесячным значениям за десять месяцев:
§ 6.2. Множественная корреляция и регрессия Назовём выборочный коэффициент корреляции ( X, Y ), рассчитанный по формуле (6.1.3), парным коэффициентом корреляции. В случае, когда факторов более одного, парных коэффициентов корреляции оказывается недостаточно ни для определения тесноты корреляционной зависимости, ни для определения уравнений регрессии. Рассмотрим трёхмерную модель, когда исследуется зависимость некоторого признака Y от факторов X (1), X (2), X (3). Вначале будем предполагать, что факторы X (1), X (2), X (3) распределены по нормальному закону. Пусть есть выборка по которой рассчитаны парные коэффициенты корреляции Здесь cov ( X ( i ), X ( j ) ) рассчитывается по формулам (6.1.1)—(6.1.2):
Частным коэффициентом корреляции ( X (1), X (2) | X (3) ) называется величина измеряющая степень связи между факторами X (1) и X (2) независимо от влияния фиксируемого фактора X (3). При этом ( X (1), X (2) | X (3) ) 1, и чем ближе он по абсолютной величине к единице, тем теснее связь между факторами X (1) и X (2) после элиминирования влияния на них X (3).
Множественным коэффициентом корреляции называется число измеряющее степень связи между фактором X (3) и двумерной случайной величиной ( X (1), X (2) ), при этом R ( X (3) | X (1), X (2) ) [0;1], чем ближе он к единице, тем теснее данная связь.
Теперь абстрагируемся от нормального распределения факторов X (1), X (2), X (3), и будем считать их произвольными величинами — возможно, случайными, возможно, детерминированными.
Для исследования линейной регрессионной зависимости результативного признака Y от факторных признаков X (1), X (2), …, X ( k ) можно воспользоваться методом наименьших квадратов.
Метод наименьших квадратов рекомендует находить оценки a0, a1, a2,..., ak неизвестных параметров a0, a1, a2,..., ak уравнения (6.2.1), исходя из требования означающего, что сумма квадратов отклонений значений Yi, рассчитанных по уравнению линейной регрессии от наблюдений yi случайной величины Y, зафиксированных при конкретных (наблюдавшихся) значениях факторных признаков, должна быть минимальной.
Метод наименьших квадратов гарантирует получение «наилучших» оценок параметров регрессии при выполнении следующих условий:
• наблюдения случайной величины Y должны быть независимыми;
• при каждом фиксированном наборе значений факторных признаков наблюдения случайной величины Y проводятся в типичных условиях, а их результаты распределены по нормальному закону с дисперсией, не изменяющейся при переходе от одного набора значений факторных признаков к другому;
• случайный эффект влияния прочих неконтролируемых факторов в регрессии (6.2.1) в среднем равен нулю, т. е. M = 0.
Отметим, что «качество» оценок, полученных с помощью метода наименьших квадратов, растёт с ростом числа наблюдений.
Решение задачи оценивания параметров уравнения (6.2.1) с помощью метода наименьших квадратов (6.2.2) реализована в надстройке «Анализ данных» пакета Microsoft Excel.
138. В следующей таблице приведены данные о курсе доллара X1, фондовом индексе X2 и котировке акции Y за последние 10 дней:
X 1 28,75 28,70 28,54 28,90 28,88 28,35 27,98 28,10 28,05 27, Y 43, 46 43, 44 40,01 39,87 41,57 40,91 38,55 41,85 41,07 40, Требуется с помощью линейной регрессии спрогнозировать котировку акции, если курс доллара составит 30 руб., а значение фондового индекса окажется при этом равным 5.
РЕШЕНИЕ. Введём данные в столбцы, как показано на рис. 6.2.1, а, и запустим пакет «Анализ данных» (меню «Сервис | Анализ данных»). Выберем регрессию в качестве инструмента анализа (рис. 6.2.1, б). В появившемся окне укажем в качестве входного интервала Y область, в которой находятся данные о котировке акции Y (т. е.
$C$2:$C$11), а в качестве входного интервала X — область, в которой находятся данные об X1 и X2 (т. е. $A$2:$B$11), организуем вывод результатов на новый рабочий лист (рис. 6.2.1, в). Результаты расчётов представлены на рис. 6.2.2.
Поясним смысл наиболее важных результатов работы программы.
Регрессионная статистика:
1. Множественный R = 0,94 – такова, судя по наблюдениям, степень линейной зависимости котировки акции Y от двух факторов: курса доллара Х1 и фондового индекса Х2, (множественный R – это множественный коэффициент корреляции R (Y | X (1), X (2) ) = 0,94 ).
2. R – квадрат = 0,89 – судя по наблюдениям, 78% вариации котировки акции Y связано с линейным влиянием курса доллара Х1 и фондового индекса Х2.
3. Стандартная ошибка = 0,58 – ошибка s = i = не фактических наблюдений Yi рассчитываемыми Yi по линейному уравнению регрессии Y = a + a X 1 + a X 2. Здесь n - число наблюдений, m - число факторов (в заi 0 1 i 2 i даче n = 10, m = 2).
Дисперсионный анализ:
1. В п е р в о й таблице приведены результаты, необходимые для проверки гипотезы H0: a1 = a2 = 0 (неизвестные параметры линейного уравнения регрессии Y = a + a X 1 + a X 2 одновременно равны нулю). Если Значимость F больше требуемого уровня значимости (как привило, принимают =0,05), то гипотезу H0 принимают: линейное уравнение регрессии Y = a0 + a1 X 1 + a2 X 2 лишено смысла и отвергается; если же Значимость F меньше, гипотезу Н0 отвергают: регрессионная модель правомерна. В задаче Значимость F составила 0,0004 — значит, модель правомерна.
2. Во в т о р о й таблице:
а) Y – пересечение = 5,27 — это оценка a0, б) Переменная Х1 = 2,27 – это оценка a1, в) Переменная Х2 = – 3,97 – это оценка a2, Рис 6.2.1. Последовательность действий при расчете параметров множественной линейной регрессии в пакете Microsoft Excel
ВЫВОД ИТОГОВ
Регрессионная статистика Нормированный R-квадрат 0, Дисперсионный анализ Коэффициенты Стандартная ошибка t-статистика P-значение Нижние 95% Верхние 95% Окончательно линейное уравнение регрессии принимает вид:Во второй и третьей строках этой таблицы приведены 95%-ные интервальные оценки генеральных параметров a 1 и a 2 :
т. е. в качестве разрешающей можно принять только такую неизвестную, при которой хотя бы в одном уравнении имеется положительный коэффициент. Если же разрешающая неизвестная выбрана, то разрешающее уравнение должно быть выбрано так, чтобы откуда следует притом особо подчеркнем, что минимум берется по всем тем индексам i, где g is > 0, так как справедливость неравенств вида (7.2.16) при g is 0 не вызывает сомнений.
Таким образом, для того чтобы при последовательном исключении неизвестных для приведения СЛАУ к предпочитаемому виду или перехода от одного предпочитаемого вида к другому свободные члены всех уравнений системы оставались неотрицательными, необходимо руководствоваться следующими правилами выбора разрешающей неизвестной и разрешающего уравнения. В качестве разрешающей неизвестной можно принять любую неизвестную, при которой есть хоть один положительный коэффициент, а затем в качества разрешающего уравнения следует взять то уравнение, которое соответствует наименьшему среди отношений свободных членов уравнений к соответствующим положительным коэффициентам при выбранной неизвестной в этих уравнениях. Условимся говорить, что СЛАУ подвергается симплексным преобразованиям, если процесс исключения неизвестных осуществляется в соответствии с указанными правилами выбора разрешающей неизвестной и разрешающего уравнения.
Может случиться, что указанное минимальное отношение достигается при нескольких значениях индекса i. Тогда любое из соответствующих им уравнений можно принять за разрешающее. Принято говорить в этом случае, что рассматриваемая СЛАУ является вырожденной. Характерная особенность вырожденной системы в том, что после выполнения очередного преобразования, как нетрудно видеть, один или несколько свободных членов обращаются в нуль. На этом основании вырожденной СЛАУ называют такую систему, у которой в какой-либо предпочитаемой форме хотя бы один свободный член ранен нулю.
Остается заметить, что СЛАУ не будет иметь ни одного неотрицательного решения, если в процессе симплексных преобразований в ней появится уравнение, в котором свободный член строго положителен, а среди коэффициентов при неизвестных нет ни одного положительного.
Будем теперь искать небазисные неотрицательные решения системы уравнений (7.2.1), по-прежнему считая, что правые части уравнений во всех системах неотрицательны. В общем решении (7.2.11) будем придавать различные неотрицательные значения только одной свободной неизвестной, например xs, сохранив значения остальных свободных неизвестных равными нулю, так, чтобы базисные неизвестные принимали неотрицательные значения. Если g1s < 0, g 2 s < 0,…, g ms < 0, то неизвестной xs можно дать любое положительное значение если же при неизвестной xs хотя бы в одном уравнении системы (7.2.9) имеется положительный коэффициент, то xs может изменяться лишь в ограниченной области:
При любом значении xs, взятом из этой области, соответствующее частное решение будет неотрицательным. Границами замкнутой области (7.2.20) отвечают крайние решения, которые, как нетрудно видеть, совпадают с базисными неотрицательными решениями. Поэтому в линейном программировании вместо крайнего решения, отвечающего верхней границе, мы будем искать соответствующее чающего верхней границе, мы будем искать соответствующее базисное неотрицательное решение.
Система m алгебраических неравенств первой степени с n неизвестными может быть записана в виде Совокупность n чисел 1, 2,…, n, взятых в определенном порядке, называется решением системы неравенств (7.2.21), если при подстановке этих чисел на место соответствующих неизвестных неравенства системы не нарушаются. Решение (1, 2,…, n ) системы неравенств называется неотрицательным, если все j > 0.
Определения совместности, несовместности, определенности, неопределенности и эквивалентности систем линейных алгебраических неравенств формулируются точно так же, как и соответствующие определения для систем линейных алгебраических уравнений.
В задачах линейного программирования часто систему линейных алгебраических неравенств вида (7.2.21) путем введения дополнительных неотрицательных неизвестных xn +1, xn + 2,…, xn + m преобразовывают в систему линейных алгебраических уравнений:
Каждому решению (1, 2,…, n, n +1, n + 2,…, n + m ) системы линейных уравнений (7.8.2), где последние m компонент n +1, n + 2,…, n + m неотрицательны, можно поставить в соответствие вполне определенное решение (1, 2,…, n ) системы линейных неравенств (7.2.21), и наоборот. В этом смысле говорят, что система уравнений (7.2.22) заменяет систему неравенств (7.2.21). Исследование и решение системы m линейных неравенств с n неизвестными сводится к исследованию и решению соответствующей системы m линейных уравнений с (n + m) неизвестными. В частности, вопрос о нахождении неотрицательных решений системы линейных неравенств (7.2.21) сводится к вопросу о нахождении.неотрицательных решений системы линейных уравнений (7.2.22).
Решение системы линейных неравенств удобно иллюстрировать геометрически в случае двух и трех неизвестных. Например, каждое неравенство системы с двумя неизвестными определяет полуплоскость вместе с ограничивающей прямой, а вся система - общую часть таких полуплоскостей, которая, очевидно, будет выпуклым многоугольником, называемым многоугольником решений данной системы неравенств, Важнейшее свойство выпуклого многоугольника состоит в том, что он вместе с любыми двумя своими точками содержит весь соединяющий их отрезок. По аналогии, каждое неравенство системы с тремя неизвестными определяет полупространство вместе с граничной плоскостью, а множество решений такой системы, в случае ее совместности, образует выпуклый многогранник.
149. Дана СЛАУ Требуется исключить неизвестную x3 из всех уравнений системы, кроме второго (т. е. x3 — разрешающая неизвестная, разрешающее уравнение — второе, a23 = 5 — разрешающий элемент).
РЕШЕНИЕ. Коэффициенты при неизвестных и правые части первого и третьего уравнений (кроме a13 и a33 ) преобразовываем по правилу прямоугольника. Например, и т. д., а второе уравнение делим на разрешающий элемент. Получаем эквивалентную данной систему уравнений 150. Исследовать СЛАУ (*) из pflfxb 149.
РЕШЕНИЕ. Процесс исследования данной системы мы начали с исключения неизвестной x2 и получили систему (**), при этом неизвестная x2 стала базисной.
В системе (**) примем за разрешающий элемент a11 = 1/ 5 и исключим неизвестную x1 из всех уравнений, кроме первого, для чего сначала первое уравнение прибавим к третьему, затем умножим первое уравнение на (–2) и прибавим ко второму и наконец, разделим первое уравнение на разрешающий элемент.
Процесс исследования данной системы уравнений записан в табл. 7.2.1 в виде последовательности расширенных матриц получающихся систем.
На следующем этапе исключаем неизвестную x4 из всех уравнений, кроме третьего. Приходим к системе уравнений, где каждое уравнение содержит свою базисную неизвестную. Для системы уравнений (*) мы получим предпочитаемый эквивалент (***) с базисными неизвестными x1, x3, x4 :
Приравнивая свободные неизвестные x2 и x5 к нулю, находим базисное решение:
а выражая базисные неизвестные через свободные, получим общее решение 151. Для СЛАУ (*) из задач 149—150 найти еще один предпочитаемый эквивалент.
РЕШЕНИЕ. В первой предпочитаемой форме (**) системы уравнений (*) примем за разрешающий элемент a22 = 1 и исключим неизвестную x2 из всех уравнений, кроме второго. Получаем систему уравнений где базисными являются неизвестные x1, x2, x4, свободными — x3, x5, т. е. неизвестные x2 и x3 поменялись ролями. Получили для системы уравнений (*) другой предпочитаемый эквивалент и соответственно базисное решение Для рассматриваемой системы уравнений можно найти не более C3 = 10 базисных решений.
152. Преобразовать первый предпочитаемый эквивалент (***) СЛАУ (*) из задач 149—151, приняв неизвестную x2 за разрешающую, так, чтобы правые части уравнений остались неотрицательными.
РЕШЕНИЕ. Для этого делим правые части уравнений на соответствующие коэффициенты при выбранной неизвестной в первом и втором уравнениях, где эти коэффициенты положительны, и среди полученных отношений находим наименьшее:
Оно соответствует первому уравнению системы (***). Поэтому первое уравнение принимаем за разрешающее и исключаем x2 из второго и третьего уравнений. Система (***) преобразуется к виду представляющему следующий предпочитаемый эквивалент системы (*), но уже с неотрицательными правыми частями. Получаем новое базисное неотрицательное решение:
Задачи для самостоятельного решения 153. Данные СЛАУ исследовать методом последовательного исключения неизвестных и в случае совместимости найти общее решение, не менее двух базисных решений и какое-нибудь частное небазисное решение 154. Найти не менее двух базисных неотрицательных решений данных СЛАУ или доказать, что неотрицательных решений нет 155. Дана технологическая матрица A = 5 2 1 3 и вектор запасов ресурсов B = 150. Являются ли следующие планы производства допустимыми, т.е. хватит ли для выполнения плана имеющихся ресурсов, если Пусть A — квадратная матрица. Если существует матрица B, такая, что произведение A на B совпадает с единичной матрицей AB = E, то говорят, что матрица A обратима, а матрицу B называют обратной матрице A. Таким образом, по определению, Обратная матрица перестановочна с исходной и что матрица, обратная обратной, совпадает с исходной:
Если для данной матрицы обратная матрицы существует, то она определяется единственным образом.
Как узнать, является ли данная матрица обратимой? Искомая матрица должна служить решением матричного уравнения (7.3.1):
которое можно записать в виде системы n 2 линейных алгебраических уравнений относительно n 2 неизвестных элементов xij обратной матрицы. Для этого умножим первую, вторую и т. д. строки матрицы A на первый столбец обратной матрицы A- и, приравняв к соответствующим элементам первого столбца стоящей справа единичной матрицы, получим n линейных уравнений. Затем все строки данной матрицы последовательно умножим на второй столбец обратной матрицы и, приравняв к соответствующим элементам второго столбца единичной матрицы, получим еще n уравнений и т. д., т. е. получим систему линейных уравнений где ij — символ Кронекера: ij = 1 при i = j и ij = 0 при i j.
Вопрос о том, является ли данная матрица A обратимой и если да, то как найти обратную матрицу, сводится к исследованию и решению СЛАУ специального вида (7.3.3).
Как решить систему уравнений (7.3.3)? Можно решать каждую подсистему или методом Жордана, или методом Крамера. В зависимости от способа решения получим два метода обращения матрицы.
Для решения СЛАУ (7.3.3) целесообразно воспользоваться методом Жордана. Как известно, этот метод не требует предварительного исследования системы уравнений на совместность — процессы исследования и решения происходят одновременно.
Особенно важно то, что этим методом можно решать все n подсистем системы (7.3.3) одновременно, так как они имеют общую матрицу коэффициентов при неизвестных, совпадающую с данной матрицей A. Выпишем матрицу A и припишем к ней столбцы свободных членов всех n подсистем:
Как обычно, будем подвергать элементарным преобразованиям систему строк этой вспомогательной матрицы. Приписанные столбцы свободных членов подсистем уравнений образуют единичную матрицу того же порядка, что и данная матрица A. В случае совместности системы уравнений (7.3.3) на некотором этапе преобразований на месте матрицы A получится единичная матрица и тогда каждый столбец пристроенной матрицы будет представлять решение соответствующей подсистемы уравнений, т. е. на месте приписанной единичной матрицы появится обратная матрица.
Схема обращения невырожденной матрицы A кратко может быть записана в виде:
Если же на некотором этапе процесса преобразований вспомогательной матрицы (7.3.4) в матрице A появится строка нулей, то это означает необратимость матрицы необратимости.
РЕШЕНИЕ. Воспользуемся методом Жордана. Искомая обратная матрица где для большей наглядности мы обозначили столбцы различным буквам и оставили только один индекс у переменных, должна удовлетворять матричному уравнению Перемножив матрицы, стоящие слева, и приравняв элементы произведения соответствующим элементам единичной матрицы, получаем систему 9 линейных алгебраических уравнений с 9 неизвестными элементами обратной матрицы:
Коэффициенты при неизвестных Правые части уравнений Процесс решения этой системы приведен в табл. 7.3.1 (решаются одновременно подсистемы по 3 уравнения в каждой). При этом, естественно, можно переставлять строки вспомогательной матрицы, а столбцы - нельзя. На месте данной матрицы получилась единичная матрица, рядом с ней - обратная матрица Чтобы убедиться, что нигде в вычислениях не было допущено ошибки, следует проверить, что произведение А–1А совпадает с единичной матрицей.
Задача для самостоятельного решения 157. Для данных матриц найти обратные матрицы или доказать необратимость:
Глава 8. Линейное программирование § 8.1. Модели линейного программирования Задача о рациональном использовании производственных мощностей является одной из первых задач, для решения которой были применены методы линейного программирования. В общем виде математическая модель задачи об использовании производственных мощностей может быть получена следующим образом.
Предположим, что предприятие или цех выпускает n видов изделий, имея m групп оборудования. Известны нормы времени на обработку каждого изделия на каждой группе оборудования, например, в минутах или часах, и фонд времени работы каждой группы оборудования. Требуется составить план производства, при котором предприятие получит наибольшую прибыль.
Примем следующие обозначения:
i — номер группы оборудования ( i = 1, 2,, m );
j — номер вида изделия ( j = 1, 2,, n );
aij — норма времени на обработку единицы j -го изделия на i -й группе оборудования;
bi — действительный фонд времени работы i-й группы оборудования;
c j — прибыль на одно изделие j-го вида;
x j — планируемое количество единиц j -го изделия;
( x1, x2,…, xn ) — искомый план производства.
Какова бы ни была производственная программа ( x1, x2,…, xn ), ее компоненты должны удовлетворять условию, что суммарное время обработки всех изделий на данной группе оборудования не должно превышать фонда времени работы этой группы оборудования. На обработку x1 единиц первого изделия на i -й группе оборудования будет затрачено ai1 x1 единиц времени, на обработку x2 единиц второго изделия на той же группе оборудования будет затрачено ai 2 x2 единиц времени и т. д. Необходимое время на обработку всех x1, x2,…, xn изделий на i -й группе оборудования будет равно сумме Эта сумма не может превышать фонд времени работы i -й группы оборудования, т. е. должна быть меньше, либо равна bi. Выписывая такие условия для всех m групп оборудования, получаем:
Так как компоненты плана суть количество изделий и, следовательно, не могут быть выражены отрицательными числами, то естественным образом добавляются условия При плане производства ( x1, x2,..., xn ) прибыль предприятия будет равна Мы хотим составить производственную программу x( x1, x2,…, xn ) так, чтобы функция z приняла наибольшее возможное значение при выполнении всех других условий.
Система линейных неравенств (8.1.1), (8.1.2) и линейная форма (8.1.3) образуют математическую модель задачи о рациональном использовании производственных мощностей. Среди всех решений системы линейных неравенств (8.1.1), удовлетворяющих условию неотрицательности (8.1.2), необходимо найти такое решение, при котором линейная форма (8.1.3) принимает наибольшее возможное значение. Это — задача линейного программирования.
Исходные параметры задачи могут быть представлены в виде матрицы A удельных затрат ресурсов, вектора B объемов ресурсов и вектора C удельной прибыли:
Рассмотрим теперь задачу о диете. Необходимые в дневном рационе питания m видов питательных веществ содержатся в n видах продуктов. Пусть aij — количество единиц i -го питательного вещества в единице j -го продукта, bi — необходимое количество единиц i -го питательного вещества в дневном рационе, c j — стоимость единицы j -го продукта. Задача состоит в том, чтобы найти план покупок x( x1, x2,…, xn ), минимизирующий суммарные затраты при условии, что каждое питательное вещество будет содержаться в купленных продуктах в количестве не менее требуемого причем по смыслу задачи Следующая задача — задача о раскрое материалов. Предположим, что предприятие получает листы (проката, фанеры и т. п.) одного и того же размера. Из них нарезают заготовки различных видов, располагая шаблоны различными способами. При каждом способе из одного листа будет получаться некоторое количество заготовок различных размеров. Требуется указать, сколько листов каждым из возможных способов следует раскроить, чтобы получить необходимое количество заготовок каждого типа при наименьшем расходе листов.
Обозначим через m число видов заготовок; i — номер вида заготовки; n — число способов раскроя; aij — количество заготовок i -го вида, получаемых при разрезании одного листа j -м способом; x j — число листов, разрезаемых j -м способом;
x( x1, x2,…, xn ) — искомый план раскроя.
Задача состоит в том, чтобы найти план раскроя x( x1, x2,…, xn ), минимизирующий общее количество расходуемых листов при условии, что заготовок каждого вида будет получено не менее требуемого количества причем число листов, разрезаемых любым способом, не может быть отрицательным Еще одна классическая задача линейного программирования — задача о распределении производственной программы. Производственное объединение получило заказ на изготовление n видов изделий в количествах d1, d 2,…, d n соответственно.
Объединению подчинены m предприятий, на каждом из которых может быть выполнен заказ на любое изделие. Пусть bi — действительный фонд времени работы i -го предприятия, aij и cij — соответственно норма расхода времени и себестоимость изготовления единицы j -го изделия на i -м предприятии. Обозначим через xij число изделий j -го вида, которое поручается изготовить i-му предприятию.
Задача состоит в том, чтобы найти распределение x( xij ) заказов между предприятиями, которое минимизирует суммарную себестоимость изготовления всех изделий при условии, что будут соблюдены ограничения по фонду времени работы каждого предприятия и будет изготовлено необходимое количество изделий каждого вида причем по смыслу задачи В задаче о загрузке требуется загрузить корабль различными типами грузов так, чтобы их суммарная ценность была наибольшей.
Пусть j — номер типа груза, n — число типов грузов, a1 j, a2 j, c j — масса, объем и стоимость единицы j -го груза, b1,b2 — грузоподъемность и вместимость грузового отсека корабля, x j — количество единиц j -го типа груза, который мы хотели бы погрузить.
Задача состоит в том, чтобы найти набор x( x1, x2,…, xn ), максимизирующий суммарную ценность при ограничениях по грузоподъемности и вместимости где В задаче коммивояжера имеется n городов, занумерованных числами от 1 до n.
Коммивояжер, выезжая из города 1, должен побывать в каждом городе ровно один раз и вернуться в исходный пункт. Известны расстояния cij между городами. Требуется найти самый короткий маршрут.
Введем переменные 1, если в маршрут входит переезд из города i в город j (i, j = 1, 2,, n, i j ), 0, в противном случае.
Требования однократного въезда и выезда из каждого города запишутся в виде:
Однако эти ограничения полностью не описывают допустимые маршруты, так как не исключают возможности разрыва пути, т. е. появление нескольких не связанных между собой маршрутов для части городов. Поэтому вводят дополнительно n переменных ui, принимающих неотрицательные значения, и записывают еще (n - 1) 2 - (n - 1) ограничений Нетрудно показать, что ограничения (8.1.5) не исключают допустимый маршрут, но исключают возможность существования подмаршрутов.
Таким образом, задача коммивояжера состоит в минимизации при условиях (8.1.4), (8.1.5), где переменные xij, ui принимают только неотрицательные целые значения. Это — задача целочисленного программирования.
Многие проблемы, возникающие в экономических исследованиях, планировании и управлении, будучи сформулированными математически, представляют собой задачи, в которых необходимо решить систему линейных алгебраических уравнений или неравенств и среди всех неотрицательных решений найти то решение, при котором линейная однородная функция принимает наибольшее или наименьшее значение. Изучение методов исследования и решения математических задач указанного типа составляет содержание того раздела математики, который принято называть линейным программированием.
Основную задачу линейного программирования мы сформулируем следующим образом.
Дана система m линейных уравнений с n неизвестными:
где все неизвестные могут принимать только неотрицательные значения и линейная однородная функция от тех же переменных требуется среди всех решений системы уравнений (8.1.7) найти такое неотрицательное решение, при котором линейная форма (8.1.9) принимает наименьшее возможное значение.
Любое неотрицательное решение системы уравнений (8.1.7) называют допустимым решением, а то допустимое решение, при котором целевая функция (8.1.9) принимает наименьшее значение, называют оптимальным решением задачи линейного программирования (8.1.7)—(8.1.9). Кратко задачу формулируют так: найти вектор ( x1, x2,…, xn ), минимизирующий линейную форму (8.1.9) при линейных ограничениях (8.1.7) и (8.1.8).
Мы остановились на вполне определенной формулировке основной задачи линейного программирования, имея в виду, что если в математической модели какой-либо конкретной задачи планирования будут содержаться линейные неравенства, то их можно заменить линейными уравнениями с помощью дополнительных неотрицательных неизвестных. Кроме того, если в конкретной задаче будет необходимо найти наибольшее возможное значение некоторой линейной формы u = c1 x1 + c2 x2 + … + c n xn при линейных ограничениях, то для приведения такой задачи к принятому нами виду основной задачи линейного программирования достаточно линейную форму u заменить противоположной ей формой v = -c1 x1 - c2 x2 - … - c n xn, так как если форма v принимает наименьшее значение при некоторых значениях переменных, то при тех же значениях переменных форма u примет наибольшее возможное значение. Может случиться также, что в математической модели конкретной задачи некоторые переменные по своему физическому смыслу могут принимать и отрицательные значения.
Тогда для каждой такой переменной x j вводят две новые неотрицательные переменные xj и x так, чтобы x j = x j - x, и заменяют x j этой разностью в системе ограниj j чений и целевой функции, после чего задача приводится к стандартному виду.
В теоретических исследованиях не всегда удобно пользоваться приведенной выше формулировкой (8.1.7)—(8.1.9) задачи линейного программирования. В частности, вместо системы линейных уравнений (8.1.7) целесообразнее иногда иметь систему линейных неравенств. Чтобы перейти от системы линейных уравнений к системе линейных неравенств, достаточно заметить, что уравнение равносильно системе двух неравенств:
где можно получить оба неравенства вида «больше или равно» или «меньше или равно».
С другой стороны, если в математической модели конкретной задачи условия, которыми связаны переменные целевой функции, представляют собой систему линейных алгебраических неравенств, то ее можно заменить некоторой системой линейных алгебраических уравнений с бльшим числом неизвестных и привести задачу к принятому нами виду основной задачи линейного программирования.
Поэтому задачу линейного программирования нередко формулируют как задачу минимизации или максимизации линейной формы (8.1.9) при линейных ограничениях (8.1.8) и Такую запись называют общей задачей линейного программирования.
Обозначим через A матрицу системы линейных уравнений (8.1.7), через X и B — матрицы-столбцы (векторы) неизвестных и свободных членов:
а также введем в рассмотрение n -мерный вектор компонентами которого служат коэффициенты линейной формы (8.1.9) и n-мерный нуль-вектор 0(0,0,…,0). Тогда линейную форму (8.1.9) можно рассматривать как скалярное произведение:
и систему линейных уравнений (8.1.7) заменить одним матричным уравнением:
а условия (8.1.8) записать в виде поэтому часто основную задачу линейного программирования кратко записывают как задачу минимизации линейной формы (8.1.12) при линейных ограничениях (8.1.13) и (8.1.14).
158. Предприятие производит продукцию двух видов, используя при изготовлении этой продукции ресурсы четырех видов. Известна матрица затрат ресурсов A, вектор запасов ресурсов B и вектор цен C:
Требуется найти производственную программу, максимизирующую прибыль.
РЕШЕНИЕ. Математическая формулировка задачи состоит в том, что требуется найти такой вектор производственной программы (x1, x2), который бы максимизировал прибыль при условиях:
Полученную задачу линейного программирования с двумя переменными можно решить графически (рис. 8.1.1). Система линейных неравенств (**), (***) определяет выпуклый многоугольник OPQRS допустимых решений. Линии уровня функции z перпендикулярны вектору-градиенту grad z = (6, 9) и образуют семейство параллельных прямых (градиент указывает направление возрастания функции). Наибольшего значения функция z достигает в точке R. Координаты этой точки определяют оптимальный план производства x1 = 3, x2 = 2, а максимальная прибыль будет равна 36.
Рис. 8.1.1. Графическое решение задачи (*)—(***) Задачи для самостоятельного решения 159. Предприятие может выпускать два вида изделий, используя четыре группы различных станков. По нормативам на изготовление одного изделия первого вида станки первой группы придется занять на 2 дня, второй группы — на 3 дня, третий — на 4, четвертый — на 1 день. Аналогично, на обработку одного изделия второго вида те же станки придется занять в течение 6, 3, 0, 2 дней соответственно. Известен фонд времени работы каждой группы станков. Для первой группы он равен 18, второй — 15, третьей — 16, четвертой — 8 дням. Прибыль предприятия на одно изделие первого вида составляет 6 рублей, на одно изделие второго вида — рублей. Сколько единиц каждого изделия следует выпустить, чтобы предприятие получило наибольшую прибыль?
Составить математическую модель поставленной задачи и решить задачу графическим методом. Указать оптимальную производственную программу, максимальную прибыль, остатки ресурсов.
160. Витамины А,В, и С, которых требуется в день 6, 8 и 2 единицы соответственно, содержаться в двух видах продуктов. Стоимость первого продукта 5 руб/кг, второго — 2 руб/кг. Первый продукт содержит в одном килограмме 2 единицы витамина А, 4 единицы витамина В и 2 единицы витамина С; второй продукт - 2,3,0 единиц соответственно. Требуется поставить задачу составления пищевого рациона минимальной стоимости и решить эту задачу графическим методом.
§ 8.2. Симплексный метод линейного программирования Основную задачу линейного программирования (ЛП) мы сформулировали как задачу минимизации линейной формы, переменные которой связаны некоторой системой линейных уравнений и подчинены условию неотрицательности. Вначале рассмотрим ч а с т н ы й с л у ч а й з а д а ч и л и н е й н о г о п р о г р а м м и р о в а н и я, когда система уравнений имеет предпочитаемый вид, притом правые части всех уравнений неотрицательны.
Минимизировать при условиях Для решения такой задачи применяется симплексный метод линейного программирования.
Одним из допустимых решений задачи линейного программирования (8.2.1)— (8.2.3) будет базисное неотрицательное решение системы (8.2.2):
так как мы предположили, что hi Ему соответствует значение целевой функции, равное Надо исследовать, является ли решение (8.2.4) оптимальным, т. е. является ли значение (8.2.5) наименьшим из всех возможных значений целевой функции (8.2.1), отвечающих различным неотрицательным решениям системы (8.2.2).
Учитывая, что система уравнений (8.2.2) имеет предпочитаемый вид, находим для нее общее решение:
Если свободным неизвестным придавать какие-нибудь неотрицательные значения, то будем получать различные решения системы (8.2.2), среди которых нас интересуют только неотрицательные, и, подставляя их компоненты в линейную форму (8.2.1), можно подсчитать соответствующие значения целевой функции. Очевидно, чтобы легче было следить за поведением целевой функции, целесообразно выразить ее только через свободные неизвестные. Для этого можно подставить в форму (8.2.1) на место базисных неизвестных их выражения (8.2.6) через свободные неизвестные, но лучше пойти другим путем, приводящим к тому же результату. Очевидно, если переписать выражение (8.2.1) в виде то для того, чтобы исключить базисные неизвестные из (8.2.7), достаточно умножить первое уравнение системы (8.2.2) на c1, второе — на c2 и т. д. m -е — на cm, сложить полученные произведения и из результата вычесть уравнение (8.2.7). Получим где приняты обозначения или а также учтено равенство (8.2.5). Заметим, что целесообразно ввести в рассмотрение вектор C (c1, c2,..., cm ) компонентами которого служат коэффициенты при тех неизвестных в линейной форме (8.2.1), которые являются базисными в системе уравнений (8.2.2), притом коэффициенты линейной формы записываются в том порядке, в котором расположены соответствующие базисные неизвестные в системе уравнений. Тогда z j можно представить как скалярное произведение вектора C на вектор G j ( g1 j, g 2 j,..., g mj ) из коэффициентов при неизвестной x j в системе уравнений (8.2.2), a L0 — как скалярное произведение вектора C на вектор H (h1, h2,…, hm ) свободных членов системы (8.2.2) и записать:
Для проведения указанных вычислений обычно составляют таблицу, выписав матрицу системы уравнений (8.2.2) и приписав к ней сверху строку C всех коэффициентов линейной формы (8.2.1), слева против каждой строки — соответствующую базисную неизвестную и коэффициент при ней из целевой функции, т. е. вектор C, а снизу — коэффициенты при неизвестных и свободный член уравнения (8.2.8). Такую таблицу называют первой симплексной таблицей (табл. 8.2.1).
Полезно составить вспомогательную систему линейных уравнений, приписав к системе (8.2.2) уравнение (8.2.8):
Тогда первую симплексную таблицу можно рассматривать как расширенную матрицу системы линейных уравнений (8.2.10) с указанными выше дополнениями.
Теперь, наряду с общим решением (8.2.6) системы ограничений, из уравнения (8.2.8), совпадающего с последним уравнением вспомогательной системы (8.2.10), получаем выражение целевой функции L только через свободные неизвестные:
С помощью этого выражения мы исследуем базисное допустимое решение (8.2.4) на оптимальность и выясним, как следует поступить, если оно окажется не оптимальным.
Прежде всего, из выражения (8.2.11) непосредственно следует, что базисное решение (8.2.4) является оптимальным решением задачи линейного программирования (8.2.1)—(8.2.3) тогда и только тогда, когда в уравнении (8.2.8) среди коэффициентов j при неизвестных нет ни одного положительного, т. е. условие оптимальности имеет вид Действительно, если в общем решении (8.2.6) мы станем придавать различные неотрицательные значения свободным неизвестным так, чтобы соответствующие базисные неизвестные также принимали неотрицательные значения, то одновременно с частными неотрицательными решениями системы ограничений мы будет получать согласно выражению (8.2.11) соответствующие им значения целевой функции. В частности, при нулевых значениях свободных неизвестных получится базисное решение (8.2.4) и соответствующее ему значение линейной формы (8.2.5). Если хотя бы один из коэффициентов при неизвестных в последнем уравнении вспомогательной системы (8.2.10), например, m+1, положителен, то мы можем соответствующей свободной неизвестной xm +1 дать в общем решении какое-нибудь положительное значение, сохранив xm + 2 = = xn = 0, и получить частное неотрицательное решение с меньшим значением линейной формы.
При выполнении условий оптимальности (8.2.12) базисное решение (8.2.4) будет единственным оптимальным решением задачи линейного программирования (8.2.1)—(8.2.3) тогда и только тогда, когда все коэффициенты m +1, m + 2,..., n при свободных неизвестных в последнем уравнении вспомогательной системы (8.2.10) строго отрицательны. Если же хотя бы один из коэффициентов при свободных неизвестных равен нулю, то будут и небазисные оптимальные решения. Действительно, если, например, m+1 = 0, то как бы мы не изменяли в общем решении (8.2.6) свободную неизвестную xm +1 в ее неотрицательной области изменения при xm + 2 = = xn = 0, целевая функция (8.2.11) будет сохранять одно и то же значение (8.2.5), т. е. мы получим некоторую совокупность оптимальных решений задачи (8.2.1)—(8.2.3). Очевидно, оптимальных решений будет еще больше, если среди коэффициентов при свободных неизвестных в уравнении (8.2.8) окажется несколько нулевых.
Предположим, что базисное решение (8.2.4) не является оптимальным, т. е. среди коэффициентов j есть по меньшей мере один положительный. Проще всего проследить за поведением целевой функции тогда, когда изменяется только одна свободная неизвестная, а остальные свободные неизвестные сохраняют нулевые значения, которые они имели в базисном решении (8.2.4). Вспомним, что каждая свободная неизвестная при нулевых значениях других свободных неизвестных имеет свою неотрицательную область изменения, нижняя граница которой всегда равна нулю, а верхняя граница является конечной или бесконечной в зависимости от того, есть или нет при данной неизвестной в соответствующей предпочитаемой форме системы уравнений хотя бы один положительный коэффициент. При исследовании задачи линейного программирования последнее обстоятельство имеет существенное значение.
Если есть хотя бы одна свободная неизвестная, такая, что коэффициент j при ней в последнем уравнении системы (8.2.10) положителен, а в первых m уравнениях той же системы (8.2.10) среди коэффициентов g1 j, g 2 j,..., g mj при ней нет ни одного положительного, то задача линейного программирования (8.2.1)—(8.2.3) неразрешима в силу неограниченности линейной формы (8.2.1) на множестве неотрицательных решений системы ограничений (8.2.2). Действительно, если, например, n > 0 в уравнении (8.2.8), но g1n 0, g 2 n 0,..., g mn 0 в предпочитаемой форме (8.2.2) системы ограничений, то в общем решении (8.2.6) системы ограничений мы можем переменную xm +1 = = xn -1 = 0 неограниченно увеличивать, положив xn, и тогда, как видно из выражения (8.2.11), целевая функция будет неограниченно убывать и, следовательно, оптимального решения не существует.
Предположим теперь, что базисное решение (8.2.4) не оптимально и что для любой свободной неизвестной x j, с положительным коэффициентом j можно указать конечную неотрицательную область ее изменения при нулевых значениях других свободных неизвестных. Как в этом случае искать оптимальное решение? Прежде всего, заметим, что скорость изменения целевой функции L относительно независимой переменной x j при нулевых значениях других свободных неизвестных, как видно из стро целевая функция будет убывать при возрастании той свободной переменной, при которой в последнем уравнении вспомогательной системы (8.2.10) стоит наибольший положительный коэффициент j. Пусть таким коэффициентом является s, т. е.
Так как неизвестная xs при нулевых значениях других свободных неизвестных не может возрастать неограниченно, а целевую функцию мы хотим минимизировать, то придадим неизвестной xs наибольшее возможное значение, которое она может принять, тем самым выделив из общего решения (8.2.6) крайнее неотрицательное решение системы ограничений (8.2.2). Мы знаем, что это крайнее решение совпадает с новым базисным неотрицательным решением, соответствующим новому предпочитаемому виду системы (8.2.2), для получения которого достаточно принять неизвестную xs за разрешающую и подвергнуть систему (8.2.2) симплексному преобразованию. Если то за разрешающее уравнение при этом преобразовании мы должны будем взять r -е.
Как только мы получим новое базисное неотрицательное решение системы ограничений, т. е. новое допустимое решение задачи линейного программирования (8.2.1)— (8.2.3), придется это решение сразу исследовать на оптимальность. Для этого мы должны будем выразить целевую функцию через новые свободные неизвестные, т. е.
из уравнения (8.2.8) исключить неизвестную xs, переходящую в число базисных. Поэтому мы преобразуем всю вспомогательную систему уравнений (8.2.10), исключая неизвестную xs из всех уравнений, кроме r -го. Система (8.2.10) преобразуется к виду Коэффициенты при неизвестных и свободные члены системы уравнений (8.2.15) связаны с коэффициентами и свободными членами системы (8.2.10) формулами исключения:
Определяемое первыми m уравнениями системы (8.2.15) базисное неотрицательное решение является одним из допустимых решений задачи линейного программирования (8.2.1)—(8.2.3). Отвечающее ему значение линейной формы равно правой части L последнего уравнения системы (8.2.15). Из последнего уравнения системы (8.2.14) получаем выражение целевой функции через новые свободные неизвестные:
с помощью которого можем исследовать решение (8.2.17') на оптимальность по схеме, изложенной выше.
Можно сказать, что решение задачи линейного программирования сводится к составлению вспомогательной системы уравнений (8.2.10) и ее преобразованию к виду (8.2.15) и далее. Расширенную матрицу системы (8.2.15) с указанными выше дополнениями естественно назвать второй симплексной таблицей, аналогично определится третья симплексная таблица и т. д. Решение конкретной задачи линейного программирования сводится к составлению первой симплексной таблицы и ее преобразованиям по рекуррентным формулам (8.2.16), т. е. по обычным формулам исключения, с той лишь особенностью, что теперь по определенным правилам выбирается разрешающий элемент. Записывается процесс решения в виде последовательности симплексных таблиц.
Заметим, что есть возможность контроля вычислений. После того как получена очередная симплексная таблица из предыдущей по правилам исключения, можно еще раз вычислить элементы последней строки по тем правилам, по которым вычислялись элементы последней строки первой симплексной таблицы.
Подчеркнем, что за каждой симплексной таблицей необходимо видеть некоторую систему линейных уравнений, из которых первые m определяют один из предпочитаемых видов системы ограничений, а из ( m + 1 )-го уравнения легко получается выражение целевой функции через свободные неизвестные.
Таким образом, процесс перехода к новым и новым решениям продолжается до тех пор, пока не будет получено оптимальное решение или не будет доказана неограниченность линейной формы (8.2.1) на множестве решений системы ограничений (8.2.2), (8.2.3). Но это утверждение справедливо только при условии невырожденности рассматриваемой задачи (8.2.1)—(8.2.3), т. е. если ни на одном этапе процесса решения ни один из свободных членов системы уравнений (8.2.2) не обращается в нуль. При hr 0, как следует из (8.2.16в), новое значение линейной формы строго меньше предыдущего и через конечное число шагов мы придем к оптимальному решению или докажем неразрешимость задачи, так как число шагов не может быть больше числа базисных решений Cm, среди которых неотрицательных значительно меньше. В вырожденном случае на одном или нескольких этапах свободный член разрешающего уравнения может оказаться равным нулю, и значение линейной формы не изменится. Появляется возможность выбрать последовательность базисных решений, приводящую к циклу, т. е. возможность возвращения к одному из прежних решений, и приведенные выше рассуждения теряют силу. Известны различные способы устранения возможности зацикливания при решении задачи линейного программирования, суть которых состоит в преодолении появляющейся неоднозначности в выборе разрешающего уравнения в вырожденной системе и, следовательно, неизвестной, исключаемой из числа базисных, но мы их не будем рассматривать, так как до сего времени ни одна из практических задач не привела к зацикливанию; при машинных вычислениях обычно в случае неоднозначности в качестве разрешающего берут уравнение с наименьшим номером из числа тех, которые можно принять в качестве разрешающего, хотя можно взять любое из них.
Метод искусственного базиса применяется к решению задач линейного программирования в о б щ е м с л у ч а е, когда система ограничений не имеет предпочитаемого вида.
Займемся исследованием такой задачи, записав ее в виде основной задачи линейного программирования. Пусть требуется минимизировать при ограничениях К данной задаче линейного программирования непосредственно нельзя применить симплексный метод, рассмотренный в предыдущем параграфе, так как система (8.2.20) не имеет предпочитаемого вида, хотя правые части всех ее уравнений можно считать неотрицательными. Поэтому к левой части каждого уравнения системы (8.2.20) добавим по одной искусственной неотрицательной неизвестной и образуем следующую систему m линейных уравнений с n + m неизвестными:
где Очевидно, в системе (8.2.22) неизвестные xn +1, xn + 2,..., xn + m образуют базисный набор, который принято называть искусственным.
Кроме того, образуем искусственную линейную форму и сформулируем следующую вспомогательную задачу линейного программирования:
минимизировать линейную форму (8.2.24) при линейных ограничениях (8.2.22) и (8.2.23).
Для решения вспомогательной задачи (8.2.22)—(8.2.24) мы можем применить симплексный метод, так как система (8.2.22) имеет предпочитаемый вид, искусственные неизвестные xn +1, xn + 2,..., xn + m являются базисными, а правые части всех уравнений неотрицательны по предположению относительно системы (8.2.20). В процессе решения задачи (8.2.22)—(8.2.24) система уравнений (8.2.22) будет подвергаться симплексным преобразованиям, в результате которых искусственные базисные неизвестные будут переходить в число свободных, а в базисный набор будут постепенно включаться исходные неизвестные. На некотором этапе процесса решения вспомогательной задачи (8.2.22)—(8.2.24) система уравнений (8.2.22) примет такой предпочитаемый вид, что соответствующее базисное решение будет оптимальным решением этой задачи. При этом минимальное значение целевой функции может быть или положительным, или равным нулю, так как функция S представляет сумму неотрицательных переменных.
Если S min > 0, то исходная задача (8.2.19)—(8.2.21) не имеет решения ввиду противоречивости условий (8.2.20) и (8.2.21). Действительно, если допустить, что система уравнений (8.2.20) имеет неотрицательное решение (1, 2,..., n ), то вспомогательная задача будет иметь решение (1, 2,..., n,0,0,...,0), для которого S = 0, что противоречит предположению.
Если же S min = 0, то оптимальное решение задачи (8.2.22)—(8.2.24) должно иметь вид (1, 2,..., n,0,0,...,0), так как из условия S = 0 следует xn +1 = = xn + m = 0. Первые n компонент этого решения образуют некоторое неотрицательное решение (1, 2,..., n ) системы ограничений (8.2.20) исходной задачи (8.2.19)—(8.2.21), притом оно является базисным по построению, т. е. среди компонент 1,..., n не более m отличных от нуля. В этом случае в полученной предпочитаемой форме системы (8.2.22) мы отбрасываем все искусственные неизвестные и, рассматривая результат как предпочитаемый эквивалент исходной системы уравнений (8.2.20), приступаем к решению исходной задачи (8.2.19)—(8.2.21).
Последние рассуждения справедливы в предположении, что рассматривается невырожденная задача. Если же задача является вырожденной, то может случиться, что S min = 0, но не все искусственные неизвестные выведены из базиса. Тогда следует учесть, что правая часть уравнения, содержащего искусственную базисную неизвестную, должна быть равна нулю, и потому мы можем либо отбросить это уравнение, если оно содержит только искусственные неизвестные xn +1,..., xn + m, либо, если оно содержит хотя бы одну из исходных неизвестных x1,..., xn, принять это уравнение за разрешающее и исключить какую-нибудь из этих неизвестных из всех других уравнений, чтобы вытеснить искусственную базисную неизвестную в число свободных, помня, что в случае необходимости можно рассматриваемое уравнение умножить на ( -1).
На практике вместо последовательной минимизации двух функций S и L часто рассматривают одну целевую функцию где число М предполагается положительным и бльшим любого числа, с которым его придется сравнивать, и решают задачу минимизации линейной формы (8.2.25) при условиях (8.2.22) и (8.2.23).
В пакете Microsoft Excel решение задач математического (в том числе, линейного) программирования проводится при помощи надстройки «Поиск решения».
161. Минимизировать при условиях:
РЕШЕНИЕ. Одним из допустимых решений задачи линейного программирования (*)—(***) будет базисное неотрицательное решение системы (**) Ему соответствует значение целевой функции, равное Учитывая, что система уравнений (**) имеет предпочитаемый вид, находим для нее общее решение:
Очевидно, если переписать целевую функцию в виде то для того, чтобы исключить из выражения для целевой функции базисные неизвестные, достаточно умножить первое уравнение системы (**) на 3, второе — на (– 4) и т. д. пятое — на 1, сложить полученные произведения и из результата последнее выражение для целевой функции (****). Получим Первая симплексная таблица представлена в табл. 8.2.2. Элементы последней строки табл. 8.2.2 вычислены по формулам (8.2.5) и (8.2.9), имея в виду при этом, что 1 и 2 равны нулю как соответствующие базисным неизвестным, При этом первую симплексную таблицу можно рассматривать как расширенную матрицу системы линейных уравнений При этом Полученное базисное решение не является оптимальным, так как целевая функция убывает как при возрастании свободной неизвестной x3 при сохранении x4 = x5 = 0, так и при возрастании x5, если также сохранить значения остальных свободных неизвестных x3, x4 равными нулю.
«