Контрольная работа по «Экономико-математическому моделированию»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

 

 

 

 

 

Контрольная работа

 по дисциплине: «Экономико-математическое  моделирование»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

1 Практическая часть. Метод наименьших квадратов…………………….3

2 теоретическая часть. Симплекс-метод  решения ЗЛП…………………...7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Практическая часть. Решение  задач методом наименьших квадратов.

 

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

Рассмотрим процедуру оценки параметров линейной эконометрической модели с помощью метода наименьших квадратов более подробно. Такая модель в общем виде может быть представлена уравнением (1.2):

yt = a0 + a1 х1t +...+ an хnt + εt .

Исходными данными при оценке параметров a0 , a1 ,..., an является вектор значений зависимой переменной y = (y1, y2 , ... , yT )' и матрица значений независимых переменных

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

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

 

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

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

 

 

 

 

 

 

 

Таблица 1.

Номер магазина	Годовой товарооборот, млн руб.	Торговая площадь, тыс. м2
1	19,76	0,24
2	38,09	0,31
3	40,95	0,55
4	41,08	0,48
5	56,29	0,78
6	68,51	0,98
7	75,01	0,94
8	89,05	1,21
9	91,13	1,29
10	91,26	1,12
11	99,84	1,29
12	108,55	1,49

Решение методом наименьших квадратов. Обозначим   — годовой товарооборот  -го магазина, млн руб.;  — торговая площадь  -го магазина, тыс. м2.

Рис. 1. Диаграмма рассеяния для примера 1.

Для определения формы функциональной зависимости между переменными   и   построим диаграмму рассеяния (рис. 1.).

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

Информация для проведения дальнейших расчетов представлена в табл. 2. С помощью метода наименьших квадратов оценим параметры линейной однофакторной эконометрической модели

Таблица 2.

t	yt	x1t	yt2	x1t 2	x1t yt
1	2	3	4	5	6
1	19,76	0,24	390,4576	0,0576	4,7424
2	38,09	0,31	1450,8481	0,0961	11,8079
3	40,95	0,55	1676,9025	0,3025	22,5225
4	41,08	0,48	1687,5664	0,2304	19,7184
5	56,29	0,78	3168,5641	0,6084	43,9062
6	68,51	0,98	4693,6201	0,9604	67,1398
7	75,01	0,94	5626,5001	0,8836	70,5094
8	89,05	1,21	7929,9025	1,4641	107,7505
9	91,13	1,29	8304,6769	1,6641	117,5577
10	91,26	1,12	8328,3876	1,2544	102,2112
11	99,84	1,29	9968,0256	1,6641	128,7936
12	108,55	1,49	11783,1025	2,2201	161,7395
S	819,52	10,68	65008,554	11,4058	858,3991
Среднее	68,29	0,89

Таким образом,

Cледовательно, при увеличении торговой  площади на 1 тыс. м2 при прочих равных условиях среднегодовой товарооборот увеличивается на 67,8871 млн руб.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 
Симплексный метод решения задач линейного программирования (симплекс-метод) - вычислительная процедура, основанная на принципе последовательного улучшения решений — перехода от одной базисной точки к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице).  
 
Данный метод является методом целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует. Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением т.н. вырожденной задачи, при которой возможно явление «зацикливания», т.е. многократного возврата к одному и тому же положению).  
 
Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.  
 
Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как 
 
К такому виду можно привести любую совместную систему, например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.  
 
Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ≥ 0. 
 
Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.  
 
Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям.  
 

 

Реализация решения задачи симплекс-методом наглядно показана на блок-схеме (рис.1). 

 
Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения. При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода.  
 
Приведенная схема симплексного метода явно выражает его алгоритмический характер (характер четкого предписания о выполнении последовательных операций), что позволяет успешно программировать и реализовать этот метод на ЭВМ. Задачи же с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.  
 
Опишем его вычислительную сторону. Вычисления по симплекс-методу организуются в виде симплекс-таблиц, которые являются сокращенной записью задачи линейного программирования в канонической форме. Перед составлением симплекс-таблицы задача должна быть преобразована, система ограничений приведена к допустимому базисному виду, c помощью которого из целевой функции должны быть исключены базисные переменные. Вопрос об этих предварительных преобразованиях мы рассмотрим ниже. Сейчас же будем считать, что они уже выполнены и задача имеет вид: 
 
Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X1, X2, ..., Xr и что при этом b1, b2,..., br ≥ 0 (соответствующее базисное решение является опорным).  
 
Для составления симплекс-таблицы во всех равенствах в условии задачи члены, содержащие переменные, переносятся в левую часть, свободные оставляются справа, т.е. задача записывается в виде системы равенств: 
 
 
Далее эта система оформляется в виде симплекс-таблиц: 
 
Примечание. Названия базисных переменных здесь взяты лишь для определенности записи и в реальной таблице могут оказаться другими. 
 
Порядок работы с симплекс таблицей. Первая симплекс-таблица подвергается преобразованию, суть которого заключается в переходе к новому опорному решению. 
 
Алгоритм перехода к следующей таблице такой: 
 
просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней; 
 
просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке- ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет; 
 
среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой; 
 
в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных:  
 
1.разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы; 
 
2.строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место;  
 
3.в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1;  
 
4.столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же; 
 
5.строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же; 
 
6.в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:  
 
В результате получают новую симплекс-таблицу, отвечающую новому базисному решению. Теперь следует просмотреть строку целевой функции (индексную), если в ней нет отрицательных значений (в задачи на нахождение максимального значения), либо положительных (в задачи на нахождение минимального значения) кроме стоящего на месте  (свободного столбца), то значит, что оптимальное решение получено. В противном случае, переходим к новой симплекс таблице по выше описанному алгоритму.  
3.Алгоритм симплексного метода решения задач линейного программирования. 
 
Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее: 
 
1.     Привести задачу к каноническому виду. 
 
2.     Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости Привести системы ограничений). 
 
3.     Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода. 
 
4.     Если выполняется признак единственности оптимального решения, то решение задачи заканчивается. 
 
5.     Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения. 
4.Пример решения задачи симплексным методом 
 
Решение: 
 
Приводим задачу к каноническому виду. 
 
Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x6 с коэффициентом +1. В целевую функцию переменная x6 входит с коэффицентом ноль (т.е. не входит). 
 
Получаем: 
 
 
      Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0. 
 
Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6). 
 
Вычисляем оценки разложений векторов условий по базису опорного решения по формуле: 
Δk = CбXk — ck 
Где Cб = (с1, с2, ... , сm ) — вектор коэффициентов целевой функции при базисных переменных; 
 
Xk = (x1k, x2k, ... , xmk ) — вектор разложения соответствующего вектора Ак по базису опорного решения; 
 
Ск — коэффициент целевой функции при переменной хк. 
 
Оценки векторов входящих в базис всегда равны нулю. Опорное решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу 
 
 
    Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных неизвестных в уравнениях ограничениях. Во втором столбце таблицы "Сб" записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце "Сб" оценки единичных векторов, входящих в базис, всегда равных нулю. 
 
В последней строке таблицы с оценками Δk в столбце "А0" записываются значения целевой функции на опорном решении Z(X1). 
 
Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -2, Δ3= -9 для векторов А1 и А3 отрицательные. 
 
По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше. 
 
Определим, введение какого из двух векторов приведет к большему приращению целевой функции. 
 
Приращение целевой функции находится по формуле:  . 
Вычисляем значения параметра θ01 для первого и третьего столбцов по формуле: 
 
Получаем θ01 = 6 при l = 1, θ03 = 3 при l = 1 (табл.1). 
 
Находим приращение целевой функции при введении в базис первого вектора ΔZ1 = — 6*(- 2) = 12, и третьего вектора ΔZ3 = — 3*(- 9) = 27. 
 
Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1). 
 
Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (табл.2) 
 
Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения. 
 
Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (табл.3). 
 
Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные 
 
Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2. 
 
Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).