ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ  
 
 
 
 

Кафедра прикладной математики 
 
 
 
 

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

по дисциплине "Прикладная математика" 
 
 
 
 
 
 
 
 
 
 

Выполнила                  Горбачева Екатерина Николаевна

Институт                      Заочного Обучения

Специальность            Управление персоналом

Курс                             1 курс

Группа                         УП-3,5-08/8

Руководитель              Ершов А. Т.

Дата  сдачи на проверку .................................................................

Дата защиты                ....................................................................

Оценка                          ....................................................................

Подпись руководителя _________________________________ 
 
 
 
 
 
 
 
 
 
 
 
 

Москва, 2009 

Содержание

1. Линейная производственная задача
2. Двойственная задача
3. Задача о «расшивке узких мест производства»
4. Динамическое программирование. Распределение капитальных вложений
5. Динамическая задача управления производством и запасами
6. Анализ доходности и риска финансовых операций

1. Линейная  производственная задача

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

     Технологическая матрица A, в которой каждый элемент a_ij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:

     Вектор B объемов ресурсов, каждый элемент  которого b_i означает предельное количество i-го ресурса для выпуска всего объема продукции:

     Вектор  удельной прибыли C, элементы которого c_j означают прибыль от производства единицы продукции j-го вида:

     Количество  каждого из товаров задаётся с  помощью производственной программы:

     x1, x2, x3, x4  - кол-во 1-ой, 2-ой, 3-ей и 4-ой  продукции соответственно.

     Технологическая матрица затрат показывает какое  количество ресурсов требуется для  производства 1 единицы продукции. Каждому  виду продукции соответствует столбец в технологической матрице затрат А. Каждая строка матрицы А соответствует одному из видов ресурсов. Чтобы получить расход каждого ресурса при заданной производственной программе перемножим матрицу А и вектор производственной программы X:

     Каждый  элемент полученного вектора  равен расходу соответствующего ресурса при заданной производственной программе, т.е. при x1, x2, x3, x4 . Так как  матрица А указывает на необходимое  количество определённого ресурса  для производства 1 единицы продукции, то умножая это число на общее количество продукции данного вида мы получим расход данного ресурса для производства заданного количества определённого вида продукции. Сложив расход ресурса по всем видам продукции, мы получим общий расход ресурса.

     Вектор  В указывает на располагаемое  количество ресурсов. Каждый элемент  соответствует одному виду ресурса. Таким образом, при производстве при заданной производственной программе X и объеме располагаемых ресурсов B должны выполняться неравенства для каждого ресурса:

  3x₁ + 2x₂ + 6x₃ ≤ 150;   4x₁ + 2x₂ + 3x₃ + 5x₄ ≤ 130;   4x₁ + 3x₂ + 2x₃ + 4 x₄ ≤ 124

Вектор  С указывает на прибыль от продажи 1 единицы продукции каждого вида. Каждый элемент вектора соответствует  одному виду продукции. Чтобы найти прибыль от каждого вида продукции следует помножить вектор производственной программу X на вектор удельной прибыли С:

     Сложив  элементы полученного вектора, мы получим  совокупную прибыль от продажи всей продукции при заданном векторе производственной программы X. Так как x₁, x₂, x₃, x₄ – неизвестные запишем полученное выражение в виде функции:

Z = 30x₁ + 11x₂ + 45x₃ + 6x_{4   (8)}

     Для достижения максимальной прибыли требуется  найти максимум полученной функции  Z. При этом x₁, x₂, x₃, x₄ по смыслу ³ 0. Учитывая условия ограничения по ресурсам, получим задачу на условный экстремум:

Z = 30x₁ + 11x₂ + 45x₃ + 6x₄ → max

x₁$ 0, x₂ $ 0, x₃ $ 0, x₄ $ 0   

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

Z = 30x₁ + 11x₂ + 45x₃ + 6x₄ → max

x₁$ 0, x₂ $ 0, x₃ $ 0, x₄ $ 0   

где дополнительные переменные имеют смысл остатков соответствующих ресурсов, а именно

     х₅ – остаток ресурса 1-го вида,

     х₆ – остаток ресурса 2-го вида,

     х₇ – остаток ресурса 3-го вида.

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

      (15)

     Мы  пока сохраняем в общем решении  х₁=х₂=х₄=0 и увеличиваем только х₃. При этом значения базисных переменных должны оставаться неотрицательными, что приводит к системе неравенств

           или             т.е. 0 £ х₃ £

     Дадим х₃ наибольшее значение х₃ =150/6, которое она может принять при нулевых значениях других свободных неизвестных, и подставим его в (15). Получаем для системы уравнений (11) частное неотрицательное решение

х₁=0, х₂=0, х₃= , х₄=0; x₅=0; x₆=55; x₇=74    (16)

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

а разрешающим  элементом будет а₁₃=6. Применив известные формулы исключения, получаем для системы уравнений (11) новый предпочитаемый эквивалент

      x₁ + x₂ + x₃         +  x₅                           = 25

     x₁ +    x₂ +       5 x₄ - x₅ + x₆          = 55              (17)

              3 x₁ + x₂ +      4 x₄ - x₅           + x₇ = 74

     Приравняв к нулю свободные переменные х₁, х₂, х₄, х₅ получаем базисное неотрицательное решение, совпадающее с (16), причем первые четыре компоненты его определяют новую производственную программу

                                х₁=0, х₂=0, х₃=25, х₄=0.       (18)

  Исследуем, является ли эта программа наилучшей, т.е. обеспечивает ли она наибольшую прибыль. Для этого выразим функцию прибыли (8) через новые свободные переменные х₁, х₂, х₄, х₅.

  Из  последнего уравнения системы (17) выражаем базисную переменную х₃ через свободные и подставляем в (8). Получаем

  Видим, что программа (18) не является наилучшей, так как прибыль будет расти, если мы начнем производить или первую, или вторую, или четвертую продукцию, но наиболее быстро функция z растет при возрастании х₁. Поэтому принимаем х₁ в системе (17) за разрешающую неизвестную, находим разрешающее уравнение по 

       (20)

и исключаем  х₁ из всех уравнений системы (17), кроме третьего уравнения. Получим следующий предпочитаемый эквивалент системы условий, который определит для системы (11) новое базисное неотрицательное решение и уже третью производственную программу, для исследования которого нам придется выразить функцию (19) через новые свободные переменные, удалив оттуда переменную х₁, ставшую базисной. Мы видели выше, как это делается (удаляли х₃ из (8)).

  Важно обратить внимание на то, что эти  удаления можно выполнить очень просто. Представим соотношение (8) в виде уравнения

-30х₁ - 11х₂ - 45х₃ - 6х₄ = 0 – z      (21)

и припишем его к системе (11). Получается вспомогательная  система уравнений

          (22)

  Напомним, что разрешающую неизвестную в системе (11) мы выбрали х₃. Этой переменной в последнем уравнении системы (22) отвечает наименьший отрицательный коэффициент D₃=-45. Затем мы нашли разрешающий элемент а₁₃=6 и исключили неизвестную х₃ из всех уравнений системы (11), кроме первого. Далее нам пришлось х₃ исключать и из функции (8). Теперь это можно сделать очень просто, если посмотреть на систему уравнений (22). Очевидно, достаточно умножить первое уравнение системы (22) на 15/2 и прибавить к четвертому; получим

  Таким образом, мы преобразовывали вспомогательную  систему уравнений (22) к виду

      x₁ + x₂ +  x₃         +  x₅                           = 25

      x₁ +    x₂ +       5 x₄ -  x₅ + x₆           = 55              (24)

              3 x₁ + x₂ +      4 x₄ - x₅           + x₇ = 74

   Первые три уравнения этой системы  представляют некоторый предпочитаемый эквивалент (17) системы уравнений (11) и определяют базисное неотрицательное решение (16) и производственную программу (18), а из последнего уравнения системы (24) получается выражение (19) функции цели через свободные переменные. Очевидно, если имеется хотя бы один отрицательный коэффициент D_j при какой-нибудь переменной x_j в последнем уравнении системы (24), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. С помощью (19) мы выяснили, что следует начинать производить продукцию первого вида, т.е. фактически мы нашли в последнем уравнении системы (24) наименьший отрицательный коэффициент

     min(D_j<0) = min(-15/2, -4, -6) = -15/2 = D₁  

и решили перевести  свободную переменную х₁  в число базисных, для чего, согласно (20) определили разрешающее уравнение и указали разрешающий элемент а₁₁=1/2

     Решаем  полученную задачу симплексным методом (методом направленного перебора базисных допустимых решений):

Оптимальная производственная программа: x₁=22 x₂=0 x₃=14 x₁=0

Остатки ресурсов: первого вида -  второго вида -   третьего вида - 

Узкими  местами производства, т.е. ресурсами, использующимися полностью, являются 1-й и 2-й ресурсы, и соответственно.

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

      z = 1290 - 7х₂ - 9х₄ - 6х₅ - 9х₆     (29)

то становится совершенно очевидным (в силу того, что все x_j³0), что прибыль будет наибольшей тогда, когда x₂=0, x₄=0, x₅=0, x₆=0     (30)

  Это означает, что производственная программа (27) является наилучшей и обеспечивает предприятию наибольшую прибыль z_max = 1290      (31)

  Итак, организовав направленный перебор  базисных неотрицательных решений системы условий задачи, мы пришли к оптимальной производственной программе и указали остатки ресурсов, а также максимальную прибыль. Следует обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Например, коэффициент D₂=7 при переменной х₂ показывает, что если произвести одну единицу продукции второго вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.

  Воспользуемся тем, что в оптимальной производственной программе х₂=0, х₄=0. Предположим, что вторую и четвертую продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

     Из  графика видно, что результаты совпадают.

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

     Для того, чтобы убедиться в правильности полученного решения, следует проверить  отношение Н = Q^-1 * В:

2. Двойственная задача

  Некое предприятие, использующее те же ресурсы  что и предприятие из предыдущей задачи, желает приобрести все эти  ресурсы. Оно желает приобрести их по ценам y₁, y₂ и y₃ соответственно за единицу каждого из трёх ресурсов. Величины у₁, у₂, у₃ принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие. Из условий предыдущей задачи нам известны затраты всех 3-х ресурсов для производства для каждого из 4-х видов продукции, количество ресурсов на производстве и прибыль от единицы каждой продукции:

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

  Для производства продукции 1-ого вида требуется 3 единицы 1-ого ресурса, 4 единицы 2-ого ресурса и 4 единицы 3-его ресурса, что соответствует элементам 1-ого столбца матрицы А. Прибыль от продажи продукции 1-ого вида равна 30. Следовательно, для целесообразности продажи ресурсов прибыль от продажи 3 единиц 1-ого ресурса, 4 единиц 2-ого ресурса и 4 единиц 3-его ресурса должна быть больше, либо равна 30, т.е. прибыли от продажи продукции 1-ого вида:

  Соответственные условия должны выполняться и  для продукции других видов. Им соответствуют 2-ой, 3-ий и 4-ый столбцы матрицы А, а также 2-ой, 3-ий и 4-ый элементы матрицы-строки прибыли С:

  Но  при продаже требуется учитывать  и интересы покупателя. Естественным желанием покупателя является снижение расходов. Так как предприятие  желает закупить весь объём имеющихся ресурсов, то его затраты при ценах y₁, y₂ и y₃ составят , где коэффициенты при y₁, y₂ и y₃ - количество имеющихся ресурсов. Таким образом:

Кроме того, так как цены не могут быть отрицательными, то .

   Решение полученной задачи легко найти  с помощью второй основной теоремы  двойственности, согласно которой для  оптимальных решений х(х₁,х₂,х₃) и у(у₁,у₂,у₃) пары двойственных задач необходимо и достаточно выполнение условий:

x ₁ (3y₁ + 4y₂ + 4y₃ - 30) = 0  y₁ (3x₁ + 2x₂ + 6x₃          - 150) = 0

x ₂ (2y₁ + 2y₂ + 3y₃ - 11) = 0  y₂ (4x₁ + 2x₂ + 3x₃ + 5x₄ - 130) = 0

x ₃ (6y₁ + 3y₂  + 2y₃  - 45) = 0  y₃ (4x₁ + 3x₂ + 2x₃ + 4x₄ - 124) = 0         .

x ₄ (     + 5y₂ + 4y₃  - 6) = 0  

  Ранее (см. Задачу 1) было найдено, что в решении исходной  задачи х₁>0 и х₃>0. Поэтому

3y₁ + 4y₂ + 4y₃ - 30 = 0

6y₁ + 3y₂  + 2y₃  - 45 = 0

     Учитывая, что 3-ой ресурс был избыточным, то, согласно теореме двойственности, его двойственная оценка , получим систему:

3y₁ + 4y₂ - 30 = 0

6y₁ + 3y₂ - 45 = 0          откуда следует у₁ = 6, у₂ = 3.

Таким образом, получили двойственные оценки ресурсов: у₁ = 6, у₂ = 3, у₃ = 0,

причем  общая оценка всех ресурсов равна f_min = 900+390=1290

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

  Данные  значения y₁, y₂ и y₃ являются двойственными оценками соответствующих ресурсов, т.е. оценка единицы 1-ого ресурса равна 6, оценка единицы 2-ого ресурса равна 3, а оценка 3-его ресурса равна 0. Эти оценки являются «теневыми» ценами ресурсов. Экономически они указывают, на сколько увеличится прибыль при выполнении оптимальной производственной программы, если количество соответствующего ресурса увеличить на единицу, при неизменном количестве остальных ресурсов.

  Задача о «расшивке узких мест  производства»

  При выполнении оптимальной производственной программ второй и второй  ресурсы  используются полностью, то есть образуют “узкие места производства”. Будем заказывать их дополнительно. Пусть T = (t₁, t₂, t₃) – вектор дополнительных объёмов ресурсов.

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

  Так как мы используем найденные оценки ресурсов, то должно выполняться условие:

  H + Q^-1T ³ 0

  Задача  состоит в том, чтобы найти  вектор Т(t₁; t_2; 0), максимизирующий суммарный прирост прибыли W = 6t₁ + 3t₂ при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы).

  Обращённый  базис Q, соответствующий оптимальной  производственной программе, содержатся в последней симплексной таблице в первой, второй, третьей строках восьмого, девятого и десятого столбцов:

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

предполагая, что дополнительно  можно надеяться получить не более 1/3 первоначального объёма ресурса каждого вида, то есть

причём по смыслу задачи t₁  ³ 0, t₂ ³ 0. Перепишем неравенства в другом виде. Получим:

1. -4/5* t₁+1/5 t₂=14

t₁=0 t₂=70

t₁=-35/2 t₂=0

2) 1/5*t₁- 2/5*t₂=22

t₁=0 t₂=-55

t₁=110 t₂=0

3) -4/5* t₁+6/5 t₂=8

t₁=0 t₂=20/3

t₁=-10 t₂=0

M (50; 160/9)

Программа «расшивки» имеет вид t₁=50 t₂=160/9 t₃=0, и прирост прибыли составит 1060/3

Сводка  результатов: