Математические методы в экономике

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ (ГОУВПО)

«ТВЕРСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

 

 

 

 

КУРСОВАЯ РАБОТА

ПО МАТЕМАТИКЕ

 

 

 

 

 

 

 

 

 

 

 

Ржев, 2011

 

Содержание

 

 

 

 

Раздел 1. Графы

 

Графом Г=(V,X) называется пара множеств: V – множество, элементы которого называются вершинами, X – множество неупорядоченных пар вершин, называемых ребрами.

Если v, wÎV, x = (v,w)ÎX, то говорят, что ребро x соединяет вершины v и w или x инцидентноv и w. Таким образом, {v,w} – обозначение ребра.

 Если Х представляет собой упорядоченные пары (т. е. X – подмножество декартова произведения V×V), то граф называется ориентированным, а пары {v,w} называют дугами.

Если множеству X принадлежат пары v=w, то такие ребра (v,v) называют петлями.

Существование одинаковых пар {v,w} соответствует наличию параллельных или кратных ребер (дуг), а кратностью ребер называют количество таких одинаковых пар.

Псевдограф − граф, в котором есть петли и/или кратные ребра.

Мультиграф − псевдограф без петель.

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

 

Понятия смежности, инцидентности, степени

Если x={v,w} - ребро, то v и w − концы ребраx.

Если x=(v,w) - дуга ориентированного графа, то v − начало, w – конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, еслиv является концом ребра x (началом или концом дуги x ).

Вершины v, w называются смежными, если {v,w}ÎX.

Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

 

Пусть D=(V,X) ориентированный граф, V={v1,...,vn}, X={x1,...,xm}.

Матрица смежности ориентированного графа D − квадратная матрица A(D)=[aij] порядка n, где

Матрица инцидентности − матрица B(D)=[bij] порядка n´m, где

 

Маршруты и пути

Последовательность v1x1v2x2v3…xkvk+1, (где k³1, viÎV, i=1,…,k+1, xiÎX, j=1,…,k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,…,k ребро (дуга) xj имеет вид {vj,vj+1} (для ориентированного графа (vj,vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).

 

Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.

 

 Путь в графе или орграфе - это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины A в вершину B начинается в A и проходит по набору ребер до тех пор, пока не будет достигнута вершина B. С формальной точки зрения, путь из вершины vi в вершину vj это последовательность ребер графа vivi+1, vi+1vi+2, ..., vj-1vj. Требуется, чтобы любая вершина встречалась на таком пути не более, чем однажды. У всякого пути есть длина - число ребер в нем.

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

Задача 1. Для заданной матрицы смежности изобразить сетевой ориентированный граф, построить матрицу инцидентности, определить полный и критический пути. Веса ребер x12 = 3, x13 = 7, x14 = 4,  
x23 = 4, x32 = 5, x34 = 2.

Решение.

Изобразим сетевой ориентированный граф по заданной матрице смежности (рис. 1.1)

Построим матрицу инцидентности

Определим полный путь:

1 → 2 → 3 → 4, вес равен 9.

Определим критический путь – путь с наибольшим весом:

1 → 3 → 2, его вес 12. 
Раздел 2. Задача линейного программирования

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

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

W=C1x1+C2x2+…+Cnxn ,                  {2.1}

где W – показатель эффективности;

 – постоянные коэффициенты;

 –  отдельные частные  показатели, ресурсы или технические                                                              характеристики, от которых зависит  W.

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

------------------------------------            {2.2}

                        {2.3}

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

            {2.4}

            {2.5}

содержательная формулировка задачи следующая: определить такую совокупность переменных , для которых выполнялись бы ограничения {2.5}, а целевая функция {4} принимала бы экстремальное значение.

Такая задача получила название задачи линейного программирования (ЗЛП).

Примеры постановки ЗЛП.

1. Задача о пищевом рационе

2. Задача о переработке нефти

3. Задача о перевозках

4. Задача распределения ресурсов

Основная задача ЛП (ОЗЛП)

ЗЛП с ограничениями-равенствами называется ОЗЛП. ОЗЛП ставится следующим образом. Имеется ряд переменных x1, x2, …, xn. Требуется определить такие неотрицательные значения этих переменных , которые бы удовлетворяли системе линейных уравнений:

  {2.6}

и, кроме того, обращали бы в минимум линейную функцию

W=C1x1+C2x2+Cnxn®min     {2.7},

то есть   

при   {2.8}     

или     {2.9}

если maxW, то W’ = –W= –C1x1–C2x2

 

Задача ЛП с ограничениями - неравенствами

Если ЗЛП сформулирована выражениями {2.6},{2.7}, то порядок ее решения сводится к следующему:

a) приравнивая k=n-m переменных  задачи определяем опорное решение  в вершине ОДР (определяется совокупность  значений всех базисных переменных);

б) перебирая все возможные вершины ОДР и определяя каждый раз значение W, находят такую совокупность базисных переменных в некоторой вершине, при которой W ®min. Однако на практике ограничения в ЗЛП задаются часто не уравнениями, а неравенствами. Чтобы воспользоваться правилами и решениями задачи (а и б), необходимо  ограничения-неравенства привести к ограничениям-равенствам.

Пусть имеется ЗЛП с n неизвестными x1, х2,..., хn в которой ограничения заданы в виде линейных неравенств.

A11x1+a12x2+…+a1nxn+b1³0

…………………………….    {2.10}

am1x1+am2x2+…+amnxn+bm³0

Все неравенства линейно независимы.

Требуется найти такую совокупность неотрицательных переменных , которая удовлетворяла бы {2.10} и, кроме того, обращала бы в минимум линейную функцию

W=C1x1+C2x2+…+Cnxn  {2.11}

Заменим систему неравенств {2.11} на системой неравенств {2.12}

{2.12} 

а линейную функцию {3.1} выражением {2.13}

W=C1x1+C2x2+…+Cnxn+0y1+0y2+…+0ym  {2.13}, где –  некоторые новые (дополнительные) переменные yi³0. Поэтому любая совокупность неотрицательных переменных x1, x2, …, xn³0, удовлетворяющая совместно с системе {2.12}, будет удовлетворять и системе {2.10}.

Теперь {2.12, 2.13} можно рассматривать как типичную ЗЛП с ограничениями-равенствами, если принять в качестве базисных переменных , а в качестве свободных .

Хотя общее количество переменных увеличилось l=m+n, но зато такую задачу можно решать как ОЗЛП.

 

Геометрическая интерпретация ОЗЛП

Рассмотрим случай, когда в ОЗЛП число переменных на 2 больше числа уравнений-ограничений, то есть k=n-m=2. В этом случае можно выбрать две переменные задачи в качестве свободных (например, x1 иx2), а остальные m переменных сделать базисными, и выразить их через свободные. Тогда система {2.6} примет вид:

  {2.14} m-уравнений

Так как значения свободных переменных могут быть произвольными (в положительной области определения, так как все xj³0, ), то их геометрическим местом являются квадранты x10x2. 

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

 

По условию ОЗЛП все xj³0, . Значит, x3=a31a1+a32x2+a3³0. Крайнее левое значение x3=0. В системе координат x10x2 уравнение x3= 0 =a31a1+a32x2+a3=0 есть уравнение прямой. Линия x3=0 делит плоскость x10x3 на две полуплоскости, в одной из которых x3>0 , в другой x3<0.

Обозначим сторону, где x3>0 штриховкой (это зависит от знаков a31, a32, a3). Аналогично можно нанести все n-2 линии , соответствующие x3, x4, ..., xn.

 

При этом на плоскости x10x2 эти штрихованные линии образуют некоторую область, которая может принадлежать всем m=n-2 положительным плоскостям (штриховка внутрь области), а может и не принадлежать. В последнем случае говорят, что ЗЛП не имеет ОДР.

Пример:

Любая точка, принадлежащая ОДР, является допустимым решением ОЗЛП, так как любая точка удовлетворяет ограничениям и ³0.

Теперь рассмотрим вопрос о нахождении из числа допустимых оптимального решения. Для рассматриваемого случая k = n – m = 2 (m = n – 2).

W=C1x1+C2x2+...+Cnxn{2.15}

Подставим в {2.15} значения x3, x4, ..., xnиз {2.14} и выразим W=W(x1,x2).

W=g0+g1x1+g2x2  {2.16}

Функция W достигает минимума при тех значениях переменных x1 иx2, что и W'=W–g0, так как g0не зависит от x1 иx2.

Пусть или   {2.17}

Построим прямую х2 на плоскости x10x2.

При изменении значения на при заданных g1 и g2 прямая x2 будет перемещаться параллельно самой себе ( > >0)  при W’=0 прямая проходит через начало координат.

Нетрудно выяснить то направление движения прямой, при котором W’ (а, следовательно, и W) стремится к минимуму.

т. А – оптимальное решение.

 

Нет оптимального решения (ОДР не имеет границы снизу (сверху)).

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

 

 

 

 

 

Задача 2.1.

Для выпуска двух видов продукции, используются три вида ресурсов. Известна матрица норм расхода  , цены Q = (2, 1, 3) на ресурсы, цены реализации Р = (14, 10) продукции и запасы ресурсов. Планируется произвести Х  единиц продукции. Составить целевые функции выручки и прибыли и найти их максимум.

Решение

Стоимость необходимых ресурсов

Предполагаемая выручка

Функция прибыли

Таким образом, получим следующую задачу

1. Графический способ (рис. 2.1)

Построим соответствующие данным ограничениям-неравенствам прямые

Так как , областью допустимых решений является четырехугольник ОАВС

Построим для задачи

Перпендикулярно этим векторам проведем опорные прямые и .

Параллельным перемещением этих прямых найдем точку В, в которой целевая функции РХ  достигает максимума и точку А (0; 9), в которой W максимальна.

Решая совместно уравнения граничных прямых АВ и ВС

находим координаты точки В:

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

2. Аналитический способ

Имеем координаты вершин многоугольника

О (0;0), А (0;9), В(2,4; 7,8), С(5;0)

Вычислим значения функций в этих точках

	О	А	В	С
РХ	0	90	111,6	70
W	0	27	23,4	0

 

 

Ответ:maxРХ = 111,6; maxW=27.

 

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

1. Графический метод  (рис. 2.2)

Построим прямые, соответствующие ограничениям-неравенствам (1) – (3)

и полуплоскости, которые определяют неравенства.

Так как , областью допустимых решений является четырехугольник АВСD.

Построим для целевой функции вектор

Перпендикулярно этому вектору проведем опорную прямую .

Параллельным перемещением этой прямой в направлении, противоположном вектору , найдем точку В, в которой целевая функции F  достигает минимума.

Решая совместно уравнения граничных прямых АВ и ВС

находим координаты точки В:

Таким образом,  
Раздел 3. Теория вероятностей и элементы математической статистики

Случайные события. Основные понятия теории вероятностей.

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

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

Достоверное событие – это событие, которое обязательно произойдет в результате испытания.

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

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