Элементы высшей математики

Наряду с гипотезой Н0, рассматривается альтернативная (конкурирующая) гипотеза Н_ь которая противоречит Н₀. Например, если проверяется гипотеза о равенстве математического ожидания некоторому значению А, т.е. Н₀: М(Х) = А, то в качестве альтернативной гипотезы можно рассмотреть гипотезу Н₁: М(Х) ф А.

Правило, по которому принимается решение принять или отклонить гипотезу Н₀, называется критерием К. Далее необходимо выбрать подходящую величину (называемую статистикой Z критерия К), которая служит для проверки критерия с использованием выборки. Например, при проверки гипотезы, что М(Х)= А, в качестве статистики можно принять среднюю Z = (x₁ + х2+... хп)/п.

Принцип проверки статистической гипотезы. Перед анализом выборки фиксируется некоторая малая вероятность а, называемая уровнем значимости. Пусть R - множество значений статистики Z, а R^ - такое подмножество R, что при условии истинности гипотезы Н₀ вероятность попадания статистики Z В R_Kp равна а, т.е. P[ZeR_K/H₀] = а. R^ называется критической областью.

Обозначим через m значение статистики Z, вычисленное по выборке xbx^..^ наблюдений. Критерий формулируется следующим образом: отклонить гипотезу Н₀, если meR^, и принять нулевую гипотезу, если meR/R^ (рис. 5.6).

При этом возможны следующие ошибки:

1) ошибка первого рода - отвергнуть верную гипотезу;

2) ошибка второго рода -принять неверную гипотезу. Критическая область R^ выбирается таким образом, чтобы минимизировать ошибки первого и второго рода.

К известным критериям относятся: t-критерий, F- критерий, критерий Уилкоксона и т.д.

Рассмотрим случай, при котором какие-то факторы Х₁, Х₂,..., Х_п оказывают влияние на признак Y.

Например, количество выпавших осадков за сезон (X₁), средняя температура (Х2) оказывают влияние на урожай картофеля (Y) в конкретном хозяйстве.

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

22.5 Корреляционный анализ

Рассмотрим наиболее простой случай, когда фактор Х влияет на признак Y.

По данным парных экспериментальных замеров получаем корреляционную таблицу:

Х	Xl	X2	X3	Хп
Y	у1	у2	уз	уп

Для количественной оценки тесноты связи между Х и Y используют коэффициент корреляции:

Коэффициент R_xy принимает значения от -1 до +1.

Принято считать, что если

|R_xy | < 0,3, то корреляционная связь слабая,

|R_Xy| = 0,3 0,7 - средняя,

0,7 < \R_xy\ < 1, то корреляционная связь сильная.

При коэффициенте корреляции R_xy > 0 возрастание Х приводит к росту и Y и, наоборот, уменьшение значений Х приводит к снижению значений и Y.

Если же R_Xy < 0, то изменение Х в одну сторону приводит к противоположному изменению Y.

Если на признак Y действует несколько факторов, то рассматривают тесноту связи между изменениями всех факторов Х_ЬХ₂,..., Х_п и изменениями Y.

22.6 Регрессионный анализ

Регрессионный анализ предназначен для представления влияния факторов X1, Х2,., Х_п на признак Y в виде уравнения регрессии:

У = f(x_b x2,..., xn). (5.35)

В случае парной корреляции, т.е. влияния одного фактора Х на признак Y, уравнение регрессии выбирают в виде:

у = а₀ + a₁x, или

у = а₀ + a₁x + a₂ x, или (5.36)

у = а₀ * EXP(a₁x).

В случае множественной линейной регрессии в качестве модели выбирают уравнение вида:

у = а0 + arx! + a2^2 +... + an^. (5.37)

Для определения неизвестных коэффициентов а0 или ai применяют метод наименьших квадратов (МНК).

Согласно этому методу, коэффициенты а₀ и a_i должны быть выбраны такими, чтобы обеспечить наименьшее значение суммы квадратов отклонений теоретических значений уравнения регрессии от экспериментальных, выбранных из корреляционной таблицы. То есть требуется выполнение условия:

I[f(xi,a0,a₁)-yj = mm. (5.38)

Графически отклонения теоретических значений признака от его замеров в случае линейной модели регрессии можно представить следующим образом (рис. 5.7).

Обозначим через

h_i = [ f(x_i, a₀, a₁) - y_i ].

Тогда условие (5.38) запишем в виде:

h₁² + h₂² +... + h_n ² = min. (5.39)

Рис. 5.7 Геометрическая интерпретация МНК

Рассмотрим применение МНК для определения неизвестных коэффициентов а₀ и a₁ в случае выбора линейной модели уравнения регрессии: у = а₀ + ai-x.

Запишем функционал (5.38) для случая линейной модели:

F(ao,a,) = ^ (ao + a,-Xi - Yi) = min (5.40)

Для определения минимального значения функционала F(a₀, a₁) необходимо приравнять его частные производные по переменным а₀ и а₁ к нулю.

В результате получаем:

Отсюда получаем систему линейных уравнений для определения неизвестных коэффициентов а₀ и a₁:

Замечание

Если R_xy > 0 ( или R_xy < 0), то в случае построения линейного регрессионного уравнения у = а + Ьх его график может иметь вид

Рис. 5.8 Разброс экспериментальных значений ( точки *) относительно регрессионных прямых для различных R_xy

ПРИМЕР 1

Выработка бригады (Y) зависит от ее численности (X) согласно следующей таблице:

Х	1	2	3	4	5	6	7	8
Y	5	11	14	21	24	31	34	41

Определить коэффициент корреляции R^ между этими случайными величинами и построить линейное уравнение регрессии.

Решение.

По формулам (5.30), ( 5.31) находим: х = 4,5; у = 22,6;

Окончательно, R ху = ^ ₅ ⁼ °,⁸⁸.

Cледовательно, между Х и Y - сильная корреляционная связь.

Далее для определения коэффициентов а и b в выбранном линейном регрессионном уравнении:

у=а+ bx воспользуемся формулами (5.42).

В результате получаем:

8 а + 36 b =181 36 а + 204 b = 1024.

В результате решения этой системы находим а « 0, b В результате регрессионное уравнение примет вид: у = 5-х.

ПРИМЕР 2

Характеризовать степень влияния СВ Х на СВ Y, если коэффициент корреляции между ними равен:

а). = 0,5 б). = - 0,8

Изобразить графически линейные уравнения связи y=f(x) и примерное расположение экспериментальных точек для обоих случаев.

Решение

ПРИМЕР 3

Бригада из N тракторов за некоторое время Т вспахивает поле. Оценить коэффициент корреляции R_NT.

Решение

Заметим, что при увеличении числа N тракторов время Т выполнения работы будет снижаться, т.е. R_NT < 0.

Если тракторы одинаковой марки и работники одинаковой квалификации, то R_NT = - 0,8 ^ (- 0,9).

Если тракторы разных марок, то возможен разброс в производительности труда трактористов, нарушается пропорциональность их вклада в общий объем работы и R_NT = - 0,7 ^ (- 0,8).

ПРИМЕР 4

Автосалон за первые 8 месяцев года (Т= 1,2,3,4,5,6,7,8) продал соответственно N = 54, 56, 57, 59, 62, 64, 66, 68 машин. Оценить (не считая) коэффициент корреляции RTN.

Решение

Если бы прирост продаж машин был бы строго пропорциональным ( т.е. увеличивался каждый месяц ровно на 2 машины), то RTN = 1.

Однако в марте (Т=3 ) и в мае (Т = 5) произошло изменение этой строгой пропорциональности ( прирост составил 1 и 3 машины).

Вследствие незначительного нарушения этой пропорциональности можно предположить, что коэффициент корреляции составит R_tn = 0,85 - 0,95.

Больший разброс в числах реализации машин по месяцам приводит к снижению ( по абсолютной величине) коэффициента корреляции RTN.

ЗАДАНИЕ

1). На метеорологической станции проводились замеры температуры Т за некоторый период времени прошлого года:

Определить вероятность Р, что в этом году в этот же период времени Т будет находиться в пределах 18 < T < 21 C.

2). На полигоне проводились замеры скорости V новой модели трактора:

Определить вероятность Р, что на основных испытаниях этот трактор покажет скорость в пределах 48 < V < 54 км/ч.

3). В результате статистических исследований производительности труда n = 36 рабочих цеха установлено, что один рабочий в среднем выпускает в смену р = 50 деталей.

Разброс числа выпускаемых деталей одним рабочим характеризуется дисперсией а² = 64 (дет.)². Найти с вероятностью да = 0,95 доверительный интервал для математического ожидания М(р) производительности труда рабочих цеха.

4). Определить коэффициент корреляции R_xy и построить уравнение регрессии между случайными величинами Х и Y, заданными таблицей:

Y	2	4	6	9	10	11
X	1	2	4	5	6	6

5). Грузовой машине требуется за несколько рейсов доставить груз со склада на станцию. Оценить ( не считая) коэффициенты корреляции: а). R_rN между грузоподъемностью машины Г и количества необходимых рейсов N; b). RLN между Г и длиной L маршрута от склада до станции.

6).Характеризовать степень влияния случайной величины Х на случайную величину Y, если коэффициенты корреляции между ними: а). R_xy = - 0,5 b) R_xy = 0,9.

Представить графически линейные уравнения регрессии y = a + bx для обоих случаев а) и b) и примерное расположение точек экспериментальных замеров на графике.

7). Характеризовать степень влияния случайной величины Х на случайную величину Y, если коэффициенты корреляции между ними:

а). R_xy = - 0,9 b) R_xy = 0,5.

Представить графически уравнения регрессии (параболы)

y = a + bx для обоих случаев а) и b) и примерное расположение точек экспериментальных замеров на графике

8). Утеряны некоторые результаты замеров зависимости случайной величины Y от случайной величины Х.

Y	10	y2	y3	y4	y5	y6
X	1	2	4	5	6	6

Восстановить (примерно) значения y₂, y₃, y₄, y₅, y₆: если коэффициент корреляции между Х и Y равен: а). Rxy = 0,6 b) Rxy = - 0,9.

8). Утеряны некоторые результаты замеров зависимости случайной величины Y от случайной величины Х.

Y	-8	y2	y3	y4	y5	y6
X	4	2	0	-2	-4	-6

Восстановить (примерно) значения y2, y3, y4, y5, y6: если коэффициент корреляции между Х и Y равен: а). Rxy = 0,9 b) Rxy = - 0,6.

22.7 Временные ряды

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

Дискретные ряды получаются путем регистрации данных через определенные промежутки времени - через месяц, год и т.д.

Непрерывные ряды динамики получаются в случае непрерывной записи изменения явления.

На практике чаще всего встречаются дискретные представления исследуемых процессов. В этом случае ряд динамики можно представить в виде:

Уровень ряда	x1	x2	x3		xn
Время	t1	t2	t3		tn

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

Уровнем ряда (xj) является каждый член ряда динамики. Различают начальный (x₀), конечный (x_n) и средний (x^) уровни ряда. Уровень ряда, относительно которого предполагается рассматривать изменение процесса, выбирается в качестве базисного ^(x6⁾.

Абсолютный прирост (dj _б, dj) характеризует размер изменения исследуемого явления во времени и определяется разностью двух уровней. Абсолютные приросты могут быть базисными и цепными:

di б = xi - x6, di = xi - xi-1, (5.43)

где xi - уровень ряда в период i, x6 - уровень ряда в базисный период.

Темпом роста (kj _б, kj) является отношение двух уровней ряда динамики, выраженное в процентах. Различают базисные и цепные темпы роста:

K_i б = ^x -100%; K_i = -^x^ -100%. (5.44)

Темпом прироста (Тб, Tj) называется отношение абсолютного прироста к базисному или предыдущему уровню, выраженное в процентах:

T_i б = ^-100%; T_i = -4--100%. (5.45) ^x6 ^xi-1

Темпы роста и прироста связаны следующим образом:

K_i = T_i + 100. (5.46)

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

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

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

Кроме того, требуется выполнение условий независимости, случайности и нормального распределения данных наблюдений.

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

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

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

1). Тенденция (тренд) ^хтр(0, представляющая собой долговременное направление развития процесса.

2). Систематические периодические колебания g(t), связанные с влиянием сезонности или цикличности развития процесса.

3). Случайная составляющая z(t), которая является результатом влияния на динамику процесса случайных факторов.

Следует отметить, что не всегда ряды динамики состоят из всех рассмотренных компонент. Единственной составляющей, которая всегда встречается в рядах, является случайная составляющая z(t), но и она может быть только в сочетании с одной или обеими составляющими.

В результате ряд динамики представим в виде:

^х(0 = xpW + g(t) + z(t). ⁽⁵.⁴⁷⁾

Геометрическая интерпретация модели (5.47) ряда динамики представлена на рисунке 5.9.

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

1-я компонента - определение характеристик исследуемых рядов и их разложение на три составляющие;

2-я компонента - всесторонний анализ отдельных составляющих и разработка модели процесса;

3-я компонента - прогнозирование исследуемого ряда динамики на основе полученной модели.

1. Анализ тренда.

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

Для решения этой задачи применяются различные методы сглаживания, наиболее известным из которых является метод наименьших квадратов. Согласно МНК в качестве тренда выбирается кривая y = f(t), сумма квадратов расстояния от точек которой до уровней ряда xi (i = 1, 2... n) является минимальной.

Основной проблемой при определении тенденции с помощью МНК является выбор формы кривой f(t). Обычно для решения этой задачи анализируется набор статистических данных или сам процесс.

2. Исследование периодических колебаний.

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

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

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

Общую задачу гармонического анализа - выявление периодичности процесса - можно сформулировать следующим образом. Допустим, что на конечном интервале (-L, L) задана функция x(t). Выдвигают гипотезу о том, что функция x(t) содержит периодическую компоненту g(t), так что

^x(t) = g^(t) + ^{z(t) (5}.⁴⁸⁾

где z(t) - случайная функция с нормальным распределением.

Задача, по существу, сводится к аппроксимации процесса x(t) процессом y(t) определенным соотношением:

y(t) = A0 + ^ [^Ak - cos(®_kt) + B_k- sin( ©_kt)], (5.49)

где неизвестные параметры Ak, Bk и ю определяются методом наименьших квадратов, минимизирующим функцию

S[x(t) - y(t)]² ^ min. (5.50)

В результате получаем следующие оценки параметров:

A₀ = - Jx(t) dt, Ak = -- - jx(t) - cos (2^kt/T)dt, (5.51)

Bk = -- - J x(t) - sin(2 n kt/T) dt.

Введем амплитуду k-ой гармоники: Rk = д/(Л_к²+В_к²)

Тогда вклад каждой гармоники равен:

- для нулевой и n-ой соответственно R0 и Rn,

- для k-й - 2Rk².

3. Анализ случайного компонента.

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

Раздел 6. Избранные разделы высшей математики

23. Задачи математического программирования.

23.1 Постановка задачи математического программирования

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

В общем виде постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции F(X) = F(x₁,..., x_n) при условии, что ее переменные x₁,

..., x_n удовлетворяют системе неравенств и уравнений:

здесь F(x₁,., x_n) и g_i(x₁,., x_n) - известные функции n переменных, bi - заданные числа.

Указанная система неравенств и уравнений определяет некоторую область D в n-мерном пространстве Rⁿ. Среди точек M(x₁,..., x_n) этой области D и ищется экстремальное значение функции F(x₁, x₂,., x_n).

Если F(x₁,..., x_n), g_i(x₁,..., x_n) - линейные функции, то получаем задачу линейного программирования.

Если F(x₁,..., x_n), g_i(x₁,..., x_n) (i = 1,..., m) - нелинейные функции, то получаем задачу нелинейного программирования.

23.2 Основные понятия линейного программирования

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

F(X) = ад + c2x2 +. + cnxn (6.2)

при условиях:

где а_i j, bi, cj - заданные постоянные величины, x = (х_ь х2,. xn).

Система неравенств (6.3) определяет некоторое множество, на котором и ищется максимальное (или минимальное) значение F(X).

Функция F(X) - целевая функция, условия (6.3) - ограничения данной задачи.

Совокупность точек Х = (x₁, x₂,..., x_n), удовлетворяющих ограничениям (6.3) задачи ЛП, называется допустимым решением (или планом).

План X* = (x₁, x₂,..., x_n), при котором целевая функция принимает свое максимальное (или минимальное) значение, называется оптимальным. То есть F(X*) > F(X) (при поиске минимального значения целевой функции F(X*) < F(X)).

Множество планов задачи ЛП, которое задается системой неравенств (6.3), образует выпуклый многогранник. Каждая из вершин этого многогранника определяет так называемый опор- ныи план. В одной из вершин многогранника решений, т.е. для одного из опорных планов, значение целевой функции является максимальным. Если максимальное значение функция принимает более чем в одной вершине, то это значение она принимает в любой точке, являющейся выпуклой комбинацией данных вершин.

Вершину многогранника решений, в которой целевая функция принимает максимальное значение, найти сравнительно просто, если задача содержит не более двух-трех свободных переменных, т.е. n-r < 2-3, где n - число переменных, г - ранг матрицы А.

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

Б(х_ь х2) = 01x1 + С2 x2 (6.4)

при условиях:

Каждое из неравенств (6.5) системы ограничений геометрически определяет полуплоскость, ограниченную прямыми

^ai1 x1 + ai2 x2 = bi, x1 = 0, x2 = 0. (6.6)

В том случае если система неравенств (6.5) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей выпуклое, то областью допустимых решений задачи (6.5) является выпуклое множество, которое называется многоугольником решений (рис. 6.1). Стороны этого многоугольника лежат на прямых (6.6).

Рис. 6.1 Геометрическая интерпретация задачи линейного программирования

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

Для геометрической интерпретации этого объяснения построим линию уровня С1Х1 + c₂x₂ = h, где h - некоторая постоянная. Пусть эта линия пересекает многоугольник решений и передвигается в направлении вектора C(c₁, c₂) до тех пор, пока она не пройдет через последнюю точку многоугольника решений (см. рис.6.1).

Отметим, что максимальное значение целевая функция может принимать только в одной точке или в любой точке отрезка (см. рис. (6.1).

Нахождение минимального значения линейной функции при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня c₁x₁ + с₂х₂ = h передвигается не в направлении вектора С = (c₁, с₂), а в противоположном направлении.

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

1. Проведение прямых, уравнения которых получаются в результате замены в ограничениях (6.5) знаков неравенства на знаки точных равенств (6.6).

2. Нахождение полуплоскостей, определяемых каждым из ограничений.

3. Нахождение многоугольника решений.

4. Построение вектора С(с₁, с₂).

5. Построение прямой c₁x₁ + с₂х₂ = h, проходящей через многогранник решений.

6. Передвижение прямой c₁x₁ + с₂х₂ = h в направлении вектора С. В результате необходимо найти точку (линию), в которой целевая функция принимает максимальное значение, либо установить неограниченность сверху функции на множестве планов.

7. Определение координат точки максимума функции и вычисление значения целевой функции в этой точке.

ПРИМЕР 1

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

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

Вид продукта	Нормы расхода продуктов на 1 порцию, кг или л	Количество продуктов,
	Мороженое	Шербет	отпускаемых на смену
1. Молоко	0,15	0,05	50
2. Сахар	0,1	0,15	50
Прибыль от продажи 1-й порции, руб.	1	1,2

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

Решение.

Постановка задачи:

найти MAX(lx₁ + 1,2х₂) при ограничениях:

0,15 * x₁ + 0,05 * x₂ < 50;

0,1 * x₁ + 0,15 * x₂ < 60.

Решение задачи представлено на рисунке ниже.

Графическое решение задачи дает x₁ = 260, x₂ = 220.

СИМПЛЕКС-МЕТОД

Одним из основных методов решения задачи ЛП является симплекс-метод. Метод основан на том, что решением задачи ЛП является одна из вершин выпуклого многогранника (оптимальный опорный план). Следовательно, решение задачи ЛП следует искать среди вершин этого многогранника решений.

Симплекс-метод предусматривает поэтапный перебор вершин многогранника, который обеспечивает возрастание значения целевой функции F(x) до полного решения задачи (определения оптимального плана).

Пусть на первом этапе выбрана вершина В_к (координаты которой называются базисным решением задачи). Тогда переход из вершины В_к в соседнюю вершину выбирают в направлении того из ребер, выходящих из В_к, вдоль которого целевая функция F(x) быстрее всего возрастает. Например, если функция F(x) быстрее всего возрастает вдоль ребра В_к В_к+1, то переход осуществляется в вершину В_к+1, и на следующем этапе рассматривается значение функции в этой вершине (рис. 6.2).

Рис. 6.2 Геометрическая интерпретация симплекс -метода

Алгоритм продолжается до определения вершины В*, координаты которой и являются решением задачи ЛП: F(B*) > F(B).

ТРАНСПОРТНАЯ ЗАДА ЧА

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A₁, A₂,..., A_m в n пунктов назначения В₁, B₂,..., B_n.

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

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок груза. Обозначим через Су тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через ai - запасы груза в i-м складе, через bj - потребности в грузе в j-м пункте назначения. Пусть также Ху - количество груза, перевозимого из i- го склада в j-й пункт назначения (рис. 6.3).

Пункты отправления груза

Тогда математическая формулировка транспортной задачи состоит в определении минимального значения функции

Всякое неотрицательное решение системы линейных уравнений (6.8), определяемое матрицей Х = (xij), называется планом транспортной задачи. План X*, при котором функция (6.7) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записываются в виде следующей таблицы.

Таблица 6.1

Пункты отправления	Пункты назначения	Запасы
	В1...	Bj...	Bn...
A1	c11 xn	c1j x1i	1c n 1x n	a1
Ai	ci1 xi1	cij xij	cin xin	ai
Am	cm1 xm1	c mj x mj	cmn xmn	am
Потребности	b1	bj	bn

Очевидно, что общее количество груза у поставщиков Ј ^ai,

а общая потребность в этом грузе в пунктах назначения Ј bi.

Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

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

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

ТЕОРЕМА

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

Замечание. В случае превышения запасов над потребностью вводится фиктивный (п+1)-й пункт назначения, потребности которого полностью "закрывали" бы транспортную задачу, а соответствующие тарифы в этот пункт назначения считались бы равными нулю.

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

ЗАДАНИЕ

Задача 1. На ферме выращивают лисиц и песцов. Для их выращивания требуются три вида кормов. Нормы расхода кормов в месяц представлены в таблице. Требуется определить количество лисиц и песцов, выращивание которых обеспечит максимальную прибыль ферме.

Таблица условий задачи

Вид кормов	Количество единиц корма, которые должны получать в неделю, кг	Корма, отпускаемые ферме в неделю, кг
	лисица	песец
1 2 3 1800 2 3 4 2600 3 4 8 4000
Прибыль от реализации 1-го зверька, руб.	160	120

Задача 2. Песок поставляется с двух карьеров на 3 комбината по производству строительных конструкций.

Тарифы на перевозку грузов одинаковы и пропорциональны расстояниям. Производительность карьеров: К1= 60 т/сутки и К2 = 80 т/сутки.

Потребности комбинатов:

С1= 30 т/сутки, С2 = 50 т/сутки, С3 = 60 т/сутки.

Расстояния между карьерами (первый индекс) и комбинатами (второй индекс) равны: г₁₁ = 5 км, г₁₂ = 6 км, г₁₃ = 8 км; г₂₁ = 7 км, г₂₂ = 5 км, г₂₃ = 5 км.

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

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

Задача нелинейного программирования (ЗНП) состоит в определении максимального или минимального (экстремального) значения функции F(X) = F(x₁... x_n) при условии, что ее переменные удовлетворяют соотношениям:

gi(xi... Xn) < bi (i = 1... k);

gi(xi... Xn) = bi (i = k+1. m). (6.10)

Здесь F(X) и gi(X) -известные функции n переменных (в общем случае нелинейные), bi - заданные числа.

Соотношения (6.10) задают область допустимых значений ЗНП. В отличие от задачи линейного программирования, эта область не всегда является выпуклой.

Решение ЗНП состоит в определении такой точки

X* = (x₁... x_n) области допустимых решений, в которой функция F(x) достигает экстремального значения, т.е. F(X*) > F(X) или

F(X*) < F(X) для любых точек Х = (х1. x_n) из области допустимых решений ЗНП. В общем случае решение задачи сводится к определению такой точки Х* области допустимых решений, через которую проходит гиперповерхность максимального (или минимального) уровня: F(X) = H_max (или H_min). Указанная точка может находиться как на границе области допустимых решений, так и внутри ее.

Для случая двух переменных решение ЗНП можно получить с использованием ее геометрической интерпретации путем реализации следующих этапов:

1. Построить область допустимых решений.

2. Построить гиперповерхность F(X) = H.

3. Определить гиперповерхность максимального (минимального) уровня или установить неразрешимость задачи из-за неограниченности функции F(X) на множестве допустимых решений.

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

ПРИМЕР

Фирма готова инвестировать не более 200 млн. руб. в два проекта А и В. Прибыль от вложения Х млн. руб. в проект А составит VX млн. руб. от его реализации, прибыль от вложения Y млн. руб. в проект В составит 2л/у млн. руб.

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

Решение.

Требуется найти максимальное значение функции

F = VX + 2л/у.

Область допустимых решений задачи - треугольник АВС, ограниченный прямой X + Y = 200 и отрезками [0, 200] на оси ОХ и [0, 200] на оси OY.

Полагая значение функции F(X, Y) равным некоторому числу Н, получаем линии уровня, представленные на рисунке 16.5. С увеличением Н значения функции F увеличиваются.

Гиперповерхность максимального значения F(X, Y) = 32 достигает последнего контакта с областью допустимых решений в граничной точке области допустимых решений Х* = 40, Y* = 160.

Ниже приведена геометрическая интерпретация решения задачи.

Для аналитического решения ЗПН можно применить метод множителей Лагранжа.

Задача динамического программирования (ЗДН) является многоэтапной, на каждом этапе определяется решение некоторой частной задачи.

Предположим, что некоторая организационноэкономическая система ОЭС в начальный момент времени t₀ находится в определенном состоянии S₀. В результате управления U система переходит из своего начального состояния S₀ в конечное состояние S^. Для оценки качества управления системой выбирается функция W = W(U).

Задача состоит в том, чтобы из множества возможных управлений (U) найти такое U*, при котором функция W(U) принимает экстремальное значение W(U*).

Дадим геометрическую интерпретацию ЗДН (рис. 6.4).

Предположим, что состояние ОЭС характеризуется некоторой точкой S на множестве X₁OX₂ параметров этой точки. Под действием управления U эта точка переходит из одного состояния в другое, перемещаясь вдоль линии, определяемой значениями параметров системы S = S(X_b X₂). Каждому управлению U движением точки, т.е. каждой траектории движения точки, поставим в соответствие значение некоторой функции W(U) (например, прибыль предприятия, полученная за планируемое количество лет его работы). Тогда задача состоит в том, чтобы из всех допустимых траекторий развития ОЭС найти такую, которая в результате реализации управления U* обеспечит экстремальное значение функции W(U).

Рис. 6.4 Геометрическая интерпретация ЗДП

ПРИМЕР

Фирме принадлежит n рентабельных предприятий. В начале каждого года она перераспределяет прибыль, полученную от этих предприятий, на финансирование их хозяйственной деятельности в размере (x₁... x_n). Планируется деятельность фирмы на ближайшие m лет.

Задача состоит в определении таких значений (x₁₁... x_ni), (i = 1, 2... m), т.е. в нахождении таких распределений финансовых средств между предприятиями на каждый i-й год (i = 1, 2... m), при которых за m лет обеспечивается получение максимальной прибыли всем предприятиям фирмы.

Постановка задачи Распределение средств между n предприятиями на i-й год (x₁i... x_ni) будем рассматривать как реализацию некоторого управления u₁. Тогда совокупность векторов (x₁₁... x_ni), (i = 1, 2... m) определяет всю совокупность управлений u1, u2. u_m на m шагах распределения средств.

В качестве критерия оценки качества управления взята суммарная прибыль за m лет, которая зависит от всей совокупности управлений: W = W(u₁... u_m).

Следовательно, задача состоит в выборе таких управлений u*, т.е. в таком распределении средств, при котором функция W принимает максимальное значение.

Рассмотрим в общем виде решение ЗДП. Будем считать, что состояние рассматриваемой ОЭС на каждом шаге определяется совокупностью ее параметров Xk = (x₁k, x₂k... x^). Эти параметры были получены в результате реализации управления u_k, обеспечивающего переход системы из (k-1)-ro состояния в k-е состояние. При этом будем полагать, что k-е состояние зависит от предыдущего (k-1)-ro состояния и выбранного управления uk и не зависит от того, каким образом система перешла в это (k-^-е состояние. Напомним, что каждое состояние системы характеризуется набором своих параметров.

Далее будем считать, что если в результате реализации k-го шага получен определенный доход, также зависящий от предыдущего (к-1)-го состояния системы и выбранного управления и равный W(Xk_-1, uk), то общий доход за n шагов составляет

F =Z W(Xk-_buk). (6.11)

Эти два условия позволяют сформулировать для ЗДП принцип оптимальности, позволяющий устанавливать правило построения для этой задачи оптимальной стратегии управления,

т.е. такой совокупности управлений (u₁, u₂... u_n), в результате реализации которой система за n шагов переходит из начального положения в конечное, и при этом функция W принимает максимальное значение.

ПРИНЦИП ОПТИМАЛЬНОСТИ БЕЛЛМАНА

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

Отсюда следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на последнем k-м шаге, затем на двух последних шагах и т.д. вплоть до первого шага.

Дадим математическую формулировку принципа оптимальности. Для этого обозначим через F_n(X₀) максимальный доход, полученный за n шагов при переходе системы из начального состояния X0 в конечное состояние X_n при реализации оптимальной стратегии управления U = (u₁... u_n), а через F_n-k(Xk) - максимальный доход, полученный при переходе из любого состояния

Xk в конечное состояние X_n при оптимальной стратегии управления на оставшихся (n-k) шагах. Тогда можно получить основное функциональное уравнение Беллмана:

Fn-k(Xk) = max [Wk+1(Xk, uk+1) + Fn-k-1(Xk+ 1)] (6.12)

В результате решения этого уравнения путем определенной итерационной процедуры и получаем решение ЗДП.

24. Введение в теорию исследования операций

Характерной особенностью организационно-экономической системы является наличие цели - достижение какого-либо экономического результата.

Операцией называется совокупность действий, направленных на достижение этой цели.

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

В любой операции для достижения цели оперирующая сторона должна иметь некоторый запас ресурсов (например, сырье, оборудование, финансовые средства, рабочую силу и т.д.). Этот элемент называют активными средствами и обозначают вектором а.

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

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

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

W = F(x, у). (6.13)

В общем случае стратегии и неконтролируемые факторы являются функциями времени.

Тогда достижение цели операции эквивалентно требованию минимизации или максимизации критерия эффективности (например, максимизация прибыли предприятия, минимизация затрат ресурсов и т.д.).

Классификация задач исследования операций проводится по двум признакам: 1) по видам неконтролируемых факторов, 2) по видам критерия эффективности и пространствам стратегий.

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

Внутренняя классификация в разделе математического программирования связана уже с видом критерия эффективности и пространства стратегий.

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

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

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

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

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

25. Теория массового обслуживания

Системой массового обслуживания (СМО) называется любая система, предназначенная для обслуживания каких-либо заявок (требований), поступающих на нее в случайные моменты времени. Примерами СМО могут служить: телефонная станция, бюро ремонта, билетная касса, ЭВМ.

Теория массового обслуживания занимается изучением случайных процессов, протекающих в СМО.

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

СМО делятся на одноканальные и многоканальные.

Различают СМО с отказами, когда заявка, пришедшая в момент, когда каналы заняты, получает отказ, покидает СМО и в дальнейшем в его работе не участвует.

Различают СМО с очередью, когда заявка, пришедшая в момент занятости канала, становится в очередь и ждет, когда один из каналов освободится. Число мест в очереди m может быть ограниченным или неограниченным. При m = 0 СМО с очередью превращается в СМО с отказами.

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

- «СМО с нетерпеливыми клиентами».

СМО с очередью различаются по дисциплине обслуживания:

1) заявки обслуживаются в порядке поступления;

2) некоторые заявки обслуживаются вне очереди - «СМО с приоритетом».

Аналитически СМО наиболее легко исследовать, если все потоки событий, переводящие ее из одного состояния в другое, - простейшие (стационарные пуассоновские). Это значит, что: 1) интенсивность потока становится постоянной (свойство стационарности), 2) каждое событие появляется независимо от того, что и когда произошло до него (свойство отсутствия последствия), 3) вероятность попадания на малый интервал времени двух и более заявок пренебрежимо мала по сравнению с вероятностью попадания на него одной заявки (свойство ординарности).

В этом случае интервалы времени между событиями в потоках имеют показательное распределение с интенсивностью потока q.

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

z = 1/ t^., где t^. - среднее время обслуживания клиента.

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

Рассмотрим две основные задачи ТМО.

1. Многоканальная СМО с отказами (задача Эрланга).

Задача Эрланга описывает поведение СМО с отказами (в случае, когда все каналы заняты, клиент выходит из СМО).

Рис. 6

Состояния СМО:

1) S₀ - СМО свободна;

2) S1 - занят только 1 канал;

к) Sk - занято k каналов, (n-k) каналов свободны;

n) S_n - заняты все n каналов.

В стационарном режиме финальные вероятности определяются формулой

ХАРАКТЕРИСТИКИ ЭФФЕКТИВНОСТИ СМО

1) Среднее число заявок, обслуживаемых СМО в единицу времени

N = q (1 - pn). (6.15)

2) Вероятность обслуживания поступившей заявки

Q = A /q. (6.16)

3) Вероятность отказа поступившей заявки

^pотк = ^pn. ⁽⁶¹⁷⁾

4) Среднее число занятых каналов

K = r * (1 - pn). (6.18)

ПРИМЕР

В гараже - ремонтная база с четырьмя боксами. На нее обращается примерно 2 машины в день. Среднее время обслуживания t^ = 1 день. В случае, когда все боксы заняты, вновь прибывшая машина покидает гараж. Найти финальные вероятности системы и ее характеристики.

ЗАДАЧА

В стоматологическом кабинете работают два врача. В холле

3 кресла для ожидания. Поток посетителей - 4 человека в час, среднее время обслуживания одного больного - 0,5 часа. Найти количество больных, которые не были обслужены в стоматологическом кабинете потому, что все места в холле на момент их прибытия были заняты.

26. Введение в теорию игр

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

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

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

Участники игры - игроки.

В антагонистических играх игроки действуют друг против друга.

В некоторых играх игроки объединяются в коалиции действия. В ряде задач выделяют коалиции интересов.

Если в игре коалиции вообще недопустимы, то игра называется бескоалиционной.

Численная оценка каждого исхода игры, т.е. критерий эффективности, называется в теории игр функцией выигрыша.

Тройка Г = <X, Y, H>, где X и Y - множества, H - функция от двух переменных x и у, называется антагонистической игрой.

Если множества X и Y конечны, то тройка Г = <X, Y, Н> называется конечной антагонистической игрой. Множества X и Y называются множествами стратегий, а их элементы х и у - чистыми стратегиями игрока 1 и 2 соответственно.

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

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

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

Поскольку число возможных действий каждого из игроков конечно, то значения функции Н естественно представить в виде матрицы с элементами H(i, j), в i-ой строке которой последовательно расположены выигрыши игрока i в ситуациях (i, 1), (i, 2), (i, n), а в столбце j - его выигрыши в ситуациях (1, j), (2, j),, (m, j).

Таким образом, всякую конечную антагонистическую игру можно задать вещественной матрицей, которая называется матрицей выигрыша. В этой терминологии конечная антагонистическая игра называется матричной, выбор игроком 1 стратегии i означает выбор строки i, а выбор игроком 2 стратегии j - выбор столбца j. Выигрыш игрока i будет при этом равен элементу матрицы H, стоящему на пересечении i-ой строки и j-го столбца.

Если игрок 1 выбирает стратегию х* из Х, то игрок 2 может выбрать такую стратегию у из Y, при которой выигрыш игрока 1 будет равен наименьшему из чисел Н(х*, у) при различных у из Y. Поэтому игрок 1 будет склонен выбрать свою стратегию х* так, чтобы этот минимальный выигрыш был наибольшим, т.е. равным

max min H(x, y) = v(T). (6.24)

Величину v(T) будем называть нижним значением игры Г = <X, Y, Н>. Такую стратегию игрока 1 называют его максимальной чистой стратегией. Применяя эту стратегию, игрок 1 при любом поведении игрока 2 обеспечивает себе выигрыш, не меньший чем v(T).

Придерживаясь стратегии х*, игрок 1 поступает очень осторожно: он желает получить величину v(T) независимо от действия игрока 2. Принцип, по которому он следует, называется принцип максимина. При этом гарантированный выигрыш игрока 1 как раз равен величине - max min H(x, y).

При этом проигрыш второго игрока 2 не превосходит W(T) при любых действиях игрока 1.

Принцип максимина был впервые сформулирован Дж. фон Нейманом в 1928 году. Это принцип широко используется в теории игр.

Ситуация, когда v(T) = w(T) при некоторой стратегии (х*, у*) обоих игроков, называется ситуацией равновесия в чистых стратегиях.

Для нахождения ситуации равновесия (седловых точек) вначале определяют минимумы элементов матрицы выигрышей по строкам: min hj, min h₂j,., min h_mj, а затем среди этих элементов выбирается максимальный max min hj.

Общее значение максимина и минимакса будем называть матричной игрой с матрицей выигрышей Н.

Если ситуация равновесия в чистых стратегиях отсутствует, то игрок может ввести случайную величину на множестве чистых стратегий, т.е. функцию на этом множестве. Это будет вещественная функция Х = Х(х), для которой Х(х) > 0 и у X(x) = 1. Такие стратегии называются смешанными.

ТЕОРЕМА

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

ПРИМЕР

Фирма планирует выпуск трех видов изделий в количестве X, Y, Z общим числом N.

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

Ситуация	Рентабельность по каждому виду продукции
на рынке	Х	Y	Z
1-я ситуация	Х1	У1	Z1
2-я ситуация	Х2	У2	Z2
3-я ситуация	Хз	Уз	Z3

Определить такое количество каждого из изделий X, Y, Z, которое способно обеспечить прибыль независимо от ситуации на рынке.

...