Задания для самостоятельного выполнения. Решить задачу о школьном кондитерском цехе, рассмотренную в новой постановке
Задание 1
Решить задачу о школьном кондитерском цехе, рассмотренную в новой постановке. Пусть цех производит четыре вида продукции:
‒ пирожки (максимально возможно произвести 2000 штук в день, если ничего больше не производить);
‒ шанежки (максимальный выпуск 1500 штук в день);
‒ булочки (максимальный выпуск 1200 штук в день);
‒ пирожные (максимальный выпуск 700 штук в день).
Соотношение стоимости изделий таково:
‒ пирожок/булочка — 2/1;
‒ пирожок/шанежка — 1/2;
‒ пирожок/пирожное —1/4.
Емкость склада равна 1100 изделий независимо от их вида.
Составить оптимальный план выпуска продукции исходя из той же цели — достижения максимальной выручки цеха. При решении задачи использовать средство Excel «Поиск решения».
Задание 2
Составить оптимальный план проведения экскурсионных поездок школьников во время каникул в следующей ситуации. Областной департамент образования может профинансировать поездки школьников из пяти районов области (районы будем обозначать номерами) в три города (назовем эти города X, Y и Z).
Количество учащихся, которых следует отправить в поездки, таково:
| Номер района | |||||
| Количество экскурсантов |
Экскурсионное бюро может в данные каникулы обеспечить поездку следующего числа учащихся в каждый из этих городов:
| Город | X | Y | Z |
| Количество экскурсантов |
Стоимость (в рублях) поездки одного учащегося из районов в города приведена в следующей таблице.
| Города | Стоимость поездок из районов | ||||
| X | |||||
| Y | |||||
| Z |
Смысл чисел в таблице таков: если в ячейке Y2 стоит 600, то это значит, что поездка одного учащегося из района 2 в город Y обходится в 600 рублей.
Необходимо составить такой план экскурсий, который:
1) позволяет каждому из числа намеченных к поездке учащихся побывать на экскурсии;
2) удовлетворяет условию, определяющему общее число экскурсантов, едущих в каждый из городов;
3) обеспечивает максимально низкие суммарные расходы финансирующей стороны.
Математическая формулировка.План перевозок, который нам надлежит составить, будет отражен в следующей таблице:
| Города | Количество учащихся, едущих из районов | ||||
| X | x1 | x2 | x3 | x4 | x5 |
| Y | y1 | y2 | y3 | y4 | y5 |
| Z | z1 | z2 | z3 | z4 | z5 |
Итак, мы имеем все для полной математической формулировки задачи: требуется найти наименьшее значение функции (4) при условии, что входящие в нее переменные удовлетворяют системам уравнений (1) и (2) и неравенств (3).
Это — весьма непростая задача. Однако ее вполне можно решить (как и существенно более сложные задачи) с помощью средств «Поиск решений» программы Excel, которым вам и надлежит воспользоваться.
Приведем результат решения этой задачи:
Величины, стоящие в этой таблице, и являются объектами поиска. Так, х3 есть число учащихся из района № 3, которые, по разрабатываемому плану поедут в город X.
Первое условие (ограничение задачи) состоит в том, что все учащиеся из каждого района поедут на экскурсию. Математически оно выражается следующими уравнениями:
x1 + y1+ z1 = 300
x2+y2+z2 = 250,
x3+y3+z3 = 400, (1)
х4 + у4 + z4 = 350,
x5+y5+z5 = 200.
Второе условие: в каждый город поедут столько учащихся, сколько этот город в состоянии принять:
х1 + х2 + х3 + х4 + х5 = 400,
y1+y2+y3+y4+y5 = 500, (2)
z1+z2+z3+z4+z5 = 600.
Кроме того, искомые величины, разумеется, неотрицательны:
х1 > 0,..., х5 > 0, у1 > 0,..., у5 >0, z1> 0,..., z5 > 0. (3)
Теперь запишем общую стоимость расходов на экскурсии. Поскольку привезти, например, на экскурсию хг учащихся стоит х1 • 500 рублей (см. таблицу стоимости поездки), то общие расходы составят
S = x1 • 500 + х2 • 700 + х3 • 750 + х4 • 1000 +
+ х5 • 1100 + y1• 700 + у2 • 600 + y3 • 400 +
+ y4 • 500 + y5 • 800 + z1• 1200 + z2 • 1000 +
+ z3 • 800 + z4 • 600 + z5 • 500 (4).
| x1 | x2 | x3 | x4 | x5 | y1 | y2 | y3 | y4 | y5 | z1 | z2 | z3 | z4 | z5 |
Итак, в город X поедут на экскурсию 300 учащихся из района № 1 и 100 учащихся из района № 2, в город У — 100 учащихся из района № 2 и 400 из района № 3, в город Z — 50 учащихся из района № 2, 350 из района № 4 и 200 — из района № 5.
Или скажем то же самое по другому: все учащиеся из района № 1 уедут в город X, учащиеся из района № 2 поделятся между городами X, Y и Z (соответственно 100, 100 и 50), все учащиеся из района № 3 уедут в город Y, а все учащиеся из районов № 4 и № 5 поедут в город Z. Такое неочевидное разделение обеспечивает в данном случае наибольшую экономию средств.
Вопросы и задания
1) В чем состоит задача оптимального планирования?
2) Что такое плановые показатели, ресурсы, стратегическая цель? Приведите примеры.
3) Попробуйте сформулировать содержание оптимального планирования своей учебной деятельности.
4) Что такое математическое программирование, линейное программирование?
5) Сформулируйте задачу оптимального планирования для того же школьного кондитерского цеха, в котором выпускается три вида продукции: пирожки, пирожные и ковржики.
6) Внесите изменение в постановку рассмотренной задачи оптимального планирования для двух видов продукции с учетом еще одного условия ограничения: число пирожных должно быть не меньше числа пирожков. На координатной плоскости постройте область поиска решения.
Общие положения
| Для упрощения изложения рассмотрим сначала случай линейной функции одного аргумента. Пусть из опыта получены точки: |
| x1, y1, | 
| |
| x2, y2, ... | 
| (1) |
| xn, yn | 
|
(см. рисунок). Требуется найти уравнение прямой
| y=ax+b, | (2) |
наилучшим образом согласующейся с опытными точками.
Пусть мы нашли такую прямую. Обозначим через 
расстояние опытной точки от этой прямой (измеренное параллельно оси y).
Из уравнения (2) следует, что
| (3) |
Чем меньше числа по абсолютной величине, тем лучше подобрана прямая (2). В качестве характеристики точности подбора прямой (2) можно принять сумму квадратов
| (4) |
Покажем, как можно подобрать прямую (2) так, чтобы сумма квадратов S была минимальной. Из уравнений (3) и (4) получаем
| (5) |
Условия минимума S будут
| (6) |
| (7) |
Уравнения (6) и (7) можно записать в таком виде:
| (8) |
| (9) |
Из уравнений (8) и (9) легко найти a и b по опытным значениям xi и yi. Прямая (2), определяемая уравнениями (8) и (9), называется прямой, полученной по методу наименьших квадратов (этим названием подчеркивается то, что сумма квадратов S имеет минимум). Уравнения (8) и (9), из которых определяется прямая (2), называются нормальными уравнениями.
Можно указать простой и общий способ составления нормальных уравнений. Используя опытные точки (1) и уравнение (2), можно записать систему уравнений для a и b
| y1=ax1+b, |
| |
| y2=ax2+b, ... |
| (10) |
| yn=axn+b, |
|
Умножим левую и правую части каждого из этих уравнений на коэффициент при первой неизвестной a (т.е. на x1, x2, ..., xn) и сложим полученные уравнения, в результате получится первое нормальное уравнение (8).
Умножим левую и правую части каждого из этих уравнений на коэффициент при второй неизвестной b, т.е. на 1, и сложим полученные уравнения, в результате получится второе нормальное уравнение (9).
Этот способ получения нормальных уравнений является общим: он пригоден, например, и для функции
| y=a0+a1x+a2x2+...+anxn. | (11) |
Естественно, что здесь получится система из n+1 нормального уравнения для определения величин
a0, a1, a2, ..., an.
Рассмотрим частный случай применения метода наименьших квадратов. Пусть из теории известно, что
| k=y/x | (12) |
есть величина постоянная и ее нужно определить по опытным данным (1).
Систему уравнений для k можно записать:
| k=y1/x1, |
| |
| k=y2/x2, ... |
| (13) |
| k=yn/xn, |
|
Для получения нормального уравнения умножим каждое из этих уравнений на коэффициент при неизвестной k, т.е. на 1, и сложим полученные уравнения
| (14) |
отсюда
| (15) |
Следовательно, среднее арифметическое, полученное из опытных отношений yi/xi, дает решение поставленной задачи по методу наименьших квадратов. Это важное свойство средней арифметической объясняет ее широкое применение в практике обработки опытных данных.
Пример 1
На опыте получены значения x и y, сведенные в таблицу
| x | ||||||
| y | 5,2 | 6,3 | 7,1 | 8,5 | 9,2 | 10,0 |
Найти прямую (2) по методу наименьших квадратов.
Решение. Находим:
xi=21, yi=46,3, xi2=91, xiyi=179,1.
Записываем уравнения (8) и (9)
91a+21b=179,1,
21a+6b=46,3,
отсюда находим
a=0,98 b=4,3.
Линейная регрессия. Использование метода наименьших квадратов (МНК)
Выбрав вид функции регрессии, т.е. вид рассматриваемой модели зависимости Y от Х (или Х от У), например, линейную модель yx=a+bx, необходимо определить конкретные значения коэффициентов модели.
При различных значениях а и b можно построить бесконечное число зависимостей вида yx=a+bx т.е на координатной плоскости имеется бесконечное количество прямых, нам же необходима такая зависимость, которая соответствует наблюдаемым значениям наилучшим образом. Таким образом, задача сводится к подбору наилучших коэффициентов.
Линейную функцию a+bx ищем, исходя лишь из некоторого количества имеющихся наблюдений. Для нахождения функции с наилучшим соответствием наблюдаемым значениям используем метод наименьших квадратов.
Обозначим: Yi - значение, вычисленное по уравнению Yi=a+bxi. yi - измеренное значение, εi=yi-Yi - разность между измеренными и вычисленными по уравнению значениям, εi=yi-a-bxi.
В методе наименьших квадратов требуется, чтобы εi, разность между измеренными yi и вычисленными по уравнению значениям Yi, была минимальной. Следовательно, находим коэффициенты а и b так, чтобы сумма квадратов отклонений наблюдаемых значений от значений на прямой линии регрессии оказалась наименьшей:
Исследуя на экстремум эту функцию аргументов а и с помощью производных, можно доказать, что функция принимает минимальное значение, если коэффициенты а и b являются решениями системы:
(2)
Если разделить обе части нормальных уравнений на n, то получим:
Учитывая, что 
(3)
Получим 
, отсюда 
, подставляя значение a в первое уравнение, получим:
При этом b называют коэффициентом регрессии; a называют свободным членом уравнения регрессии и вычисляют по формуле:
Полученная прямая является оценкой для теоретической линии регрессии. Имеем:
Итак, 
является уравнением линейной регрессии.
Регрессия может быть прямой (b>0) и обратной (b<0). Прямая регрессия означает, что при росте одного параметра, значения другого параметра тоже увеличиваются. А обратная, что при росте одного параметра, значения другого параметра уменьшаются.
Пример 1. Результаты измерения величин X и Y даны в таблице:
| xi | -2 | ||||
| yi | 0.5 | 1.5 |
Предполагая, что между X и Y существует линейная зависимость y=a+bx, способом наименьших квадратов определить коэффициенты a и b.
Решение. Здесь n=5
xi=-2+0+1+2+4=5;
xi2=4+0+1+4+16=25
xiyi=-2•0.5+0•1+1•1.5+2•2+4•3=16.5
yi=0.5+1+1.5+2+3=8
и нормальная система (2) имеет вид 
Решая эту систему, получим: b=0.425, a=1.175. Поэтому y=1.175+0.425x.
Пример 2. Имеется выборка из 10 наблюдений экономических показателей (X) и (Y).
| xi | ||||||||||
| yi |
Требуется найти выборочное уравнение регрессии Y на X. Построить выборочную линию регрессии Y на X.
Решение. 1. Проведем упорядочивание данных по значениям xi и yi. Получаем новую таблицу:
| xi | ||||||||||
| yi |
Для упрощения вычислений составим расчетную таблицу, в которую занесем необходимые численные значения.
| xi | yi | xi2 | xiyi |
| ∑xi=1729 | ∑yi=1761 | ∑xi2299105 | ∑xiyi=304696 |
| x=172.9 | y=176.1 | xi2=29910.5 | xy=30469.6 |
Согласно формуле (4), вычисляем коэффициента регрессии
а по формуле (5)
Таким образом, выборочное уравнение регрессии имеет вид y=-59.34+1.3804x.
Нанесем на координатной плоскости точки (xi; yi) и отметим прямую регрессии.
Рис 4
На рис.4 видно, как располагаются наблюдаемые значения относительно линии регрессии. Для численной оценки отклонений yi от Yi, где yi наблюдаемые, а Yiопределяемые регрессией значения, составим таблицу:
| xi | yi | Yi | Yi-yi |
| 168.055 | -0.945 | ||
| 170.778 | -0.222 | ||
| 172.140 | 6.140 | ||
| 172.140 | 0.140 | ||
| 174.863 | -5.137 | ||
| 176.225 | 0.225 | ||
| 177.587 | 0.587 | ||
| 178.949 | -3.051 | ||
| 184.395 | 2.395 | ||
| 185.757 | -0.243 |
Значения Yi вычислены согласно уравнению регрессии.
Заметное отклонение некоторых наблюдаемых значений от линии регрессии объясняется малым числом наблюдений. При исследовании степени линейной зависимости Y от X число наблюдений учитывается. Сила зависимости определяется величиной коэффициента корреляции.