Министерство  образования РФ

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

Институт  информационных систем управления

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

Курсовой  проект

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

Вариант №17 
 
 
 
 
 
 
 
 
 
 

Выполнила:

студентка II курса 1 группы

Молодова  А.М.

Проверил  преподаватель:

Никифорова  О.П.  
 

Москва 2011

Содержание

   Задание  на курсовую работу……………………………………………………................3

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

2. Двойственная задача линейного программирования…………......................................12

3. Задача о "расшивке узких мест производства"………………………………................14

4.Транспортная задача линейного программирования…………………….......................17

5. Динамическое программирование. Задача распределения капитальных вложений....20

6. Динамическая  задача управления производственными  запасами.................................23

7. Анализ доходности и риска финансовых операций...............…………….....................27

8. Матричная модель производственной программы………………………......................30

    Список  использованной литературы……………………………………………….........33 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Задание на курсовую работу

 

1. Составить математическую модель линейной производственно  задачи, имея следующие исходные данные:

     ,

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

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

В последней  симплексной таблице указать  обращённый базис  соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения .

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

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

Применить наёденные двойственные оценки ресурсов к решению следующей задачи.  

3.       Сформулировать задачу о «расшивке узких мест производства» и составить математическую модель. Определить область устойчивости двойственных     оценок, где сохраняется структура программы производства. Решить задачу о «расшивке узких мест производства» при условии, что дополнительно можно получить от поставщиков не более одной трети первоначально выделенного объёма ресурса любого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объёмов ресурсов, дополнительную возможную прибыль.

Составить сводку результатов.

  4.     Составить математическую модель транспортной задачи по следующим      данным:

Вектор  объёма производства

Вектор  объёма потребления 

Матрица транспортных издержек:

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

5.       Методом динамического программирования решить задачу распредения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб., причем выделяемые суммы должны быть кратны 100 тыс. руб. по следующим исходным данным:

 

6.       Рассмотреть динамическую задачу  управления производством и запасами с исходными данными:

     d₁ d₂ d₃  a b c  h₁ h₂ h₃      y₁

           2 2 2  1 1 5  1 2 4         2 ,

где  d_1,d_2,d₃ - заказ на изделия на каждый месяц, a, b, с – коэффициенты в квадратичной функции, h_1,h_2, h₃ – затраты на хранение единицы изделия для каждого месяца, y₁  - к началу первого месяца на складе имеется 2 единицы изделия. 

7.       Провести анализ доходности и  риска финансовых операций по исходным    данным:

  17. (0,1/2) (4,1/4) (8,1/8) (32, 1/2)

  18. (-6,1/2) (-4,1/4) (-2,1/8) (10, 1/8)

  19. (0,1/4) (8,1/4) (12,1/3) (24, 1/6)

  20. (-6,1/4) (-2,1/4) (0,1/3) (-6, 1/6) 
 
 
 
 
 
 
 

8.       Составить матричную модель производственной программы предприятия   по следующим исходным данным:

          структурная матрица производства  А =

     матрица коэффициентов прямых затрат (затраты  на физический выпуск)

     B = 

      матрица коэффициентов прямых затрат внешних ресурсов  Y =

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

    

 
 
 
 

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

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

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

      Применим следующие обозначения:

  i – номер группы оборудования (i=1,2, … , m);

  j – номер вида изделия (j=1,2, … , n);

  a_ij – норма времени на обработку единицы i-го изделия на j-ой группе оборудования;

  b_i – действительный фонд времени работы i-й группы оборудования;

  x_i – планируемое количество единиц  j-го изделия;

  (x₁, x₂, … , x_n) – искомый план производства. 

Дано:

                  1 4 3 4  120

            A= 3 0 2 2 B= 168 C= (31,10,14,20)

                  2 5 0 3  80 

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

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

   В последней симплексной таблице  указать обращенный базис Q^-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения

H = Q^-1*B

и решить графически.

Решение

 

Математическая  модель задачи имеет вид:

найти производственную программу

          (Х₁,Х₂,Х₃,Х₄) 

максимизирующую прибыль

          Z=31Х₁+10Х₂+14Х₃+20Х₄    

при ограничениях по ресурсам 

   Х₁+4Х₂+3Х₃+4X₄  120

 3Х₁              +2Х₃+2X₄  168

 2Х₁+5Х₂               +3X₄  80 

Где X₁ 0, Х₂ 0,Х₃ 0, Х₄ 0.   

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

Z=31Х₁+10Х₂+14Х₃+20Х₄+0Х5+0Х6+0Х7     =>    max 

  Х₁+4Х₂+3Х₃+4X₄ +X₅= 120

3Х₁             +2Х₃+2 X₄          +X₆  = 168

2Х₁+5Х₂             +3X₄                    +X₇  = 80 

Где X₁ 0, Х₂ 0,Х₃ 0, Х₄ 0, Х₅ 0, Х₆ 0, Х₇ 0. 

Дополнительные  переменные имеют смысл остатков соответствующих ресурсов.  

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

              Таблица 1

 
 

Симплексный  метод   решения   линейной  производственной  задачи  представлен  в  Таблице 1. 

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

Х₁=40,  Х₂=0,  Х₃=24,  Х₄=0,

а максимальная прибыль равна 

Z_МАХ = 1576 

При этом  второй и третий  ресурс будут исчерпаны  полностью, а первый ресурс имеет остаток Х₅= 8 единиц т. е. узкие места производства Х₆=0 и Х₇=0 

Проверим выполнение соотношения H=Q^-1 В, где Q^-1 базис в последней симплексной таблице, соответствующий набору базисных неизвестных.  
 
 
 
 

Проверка: Q^-1*B = H 
 

              1    -15/10   175/100                        120             8

   Q^-1 =  0       5/10   -75/100   B=    168            H=      24

         0        0       5/10               80                       40

                                     

           1   -15/10   175/100         120        1*120+(-15/10)*168+175/100*80          8                     H =     0     5/10     -75/100   *    168  =   0*120+5/10*168+(-75/100)*80        =  24

           0         0          5/10          80         0*120+0*168+5/10*80                          40 
 
 

Вывод: при решении  симплексной таблицы ошибок допущено не было.

Графическое решение 

Проверим полученный результат.

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

Z = 31X₁ + 14X₃ max 

X₁  + 3X₃    120  (1)

3X₁  + 2X₃   168  (2)

2X₁  + 0X₃   80    (3) 

X₁ 0, X₃ 0 

1) X₁  + 3X₃ = 120

     X₁=0    X3=40

     X3=0    X1=120 

2) 3X₁  + 2X3=168

      X1=0   X3=84

      X3=0   X1=56    

3) 2X1=80

      X1 =40

Решая эту задачу графически, получим следующее: 

Точка M лежит на пересечении прямых (2) и (3) 

3X₁  + 2X₃ =168

2X₁   = 80 

2X₁ =80  => X₁ = 40 

3*40+2X₃   = 168 

2X₃   = 168-120

2X₃   = 48

X₃   = 24 

Ответ Х₁=40,  Х₃=24,   

Вывод:  решение  в симплексной таблице верно 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Двойственная задача линейного программирования 

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

Теперь представим себе что возникла новая ситуация. Некий предприниматель, занимающийся производством каких-то других видов продукции, но с использованием таких же трех видов ресурсов, какие имеются у нас, предлагает нам «уступить» по определенным ценам все имеющиеся у нас ресурсы и обещает платить y₁ руб. за каждую единицу первого ресурса, у₂ руб. – второго, у₃ руб. – за единицу третьего ресурса. Возникает вопрос: при каких ценах y₁, у₂, у₃ мы можем согласиться с предложение предпринимателя?

Величины y₁, у₂, у₃  принято называть расчетными или двойственными оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие. 

Дано:

                   1 4 3 4  120

            A=  3 0 2 2 B= 168 C= (31,10,14,20)

                   2 5 0 3   80 

A – технологическая матрица

B – вектор объема ресурсов

C – вектор удельной прибыли 

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А,  1 единицу ресурса первого вида, 3 единицы ресурса второго вида и 2 единицы третьего (элементы первого столбца матрицы). В ценах y₁, у₂, у₃ наши затраты составят y₁ + 3у₂ +2y₃,   т.е. столько заплатит предприниматель за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 31 руб.  Следовательно,  мы  можем  согласиться  с предложением предпринимателя только в том случае, если он заплатит не меньше  

   y₁ + 3 у₂ + 2 y₃  31

    4 y₁ +          5 y₃  10

    3 y₁ + 2 у₂               14

    4 y₁ + 2 у₂ + 3 y₃  20 

Поэтому перед предпринимателем мы ставим такие условие по всем видам продукции. Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить

120у₁ + 168у₂ +80у₃ рублей. При поставленных нами условиях предприниматель будет искать такие значения величин y₁, у₂, у₃, чтобы эта сумма была как можно меньше. Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок У (У₁У₂,У₃) минимизирующий общую оценку всех ресурсов

  f =120у₁ + 168у₂ +80у₃ -> min

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

у₁ >=0    у₂>=0   у₃>=0 

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

Х (Х₁, Х₂, Х₃, Х₄) и у (y₁, у₂, у₃) пары двойственных задач необходимо и достаточно выполнение условий 

     X₁( y₁+3 y₂+2 y₃ -31 )=0  y₁ ( Х₁+4Х₂+3Х₃+4 Х₄- 120)=0

    X₂(4 y₁ + 5 y₃ - 10)=0  y₂ (3Х₁+ 2Х₃+2Х₄- 168)=0

    X₃(3 y₁ +2 y₂ - 14)=0  y₃ (2 Х₁+5 Х₂+ 3Х₄- 80)=0

    X₄(4 y₁ +2 y₂+3 y₃ - 20)=0 

Ранее было найдено, что в решении исходной задачи X₁ >0, X₃>0  => (X₁ =40,

X₂=0, Х₃=24, Х₄=0).

Поэтому

          y₁+3 y₂+2 y₃ - 31=0

          3y₁+2 y₂ - 14=0 

Если же учесть, что первый   ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю: y1 =0, то приходим к системе уравнений

          3 y₂+2 y₃ - 31=0

         2 y₂ - 14=0

откуда следует

         y₂=7, у₃=5 

y*= (0;7;5) 

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

f=120*0+168*7+80*5=1576 

Так как первый ресурс был избыточным, согласно теории свойств, его двойственная оценка равна 0 (y1=0) 

Экономический смысл двойственных оценок. Например, двойственная оценка второго ресурса  у₂=7 показывает, что добавление одной единицы этого ресурса обеспечит прирост прибыли в 7 единиц.

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

       При выполнении оптимальной производственной программы второй и третий ресурсы используются полностью, т.е. образуют "узкие места производства". Будем их заказывать дополнительно. Пусть T(t₁,t₂,t₃)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие Н + Q^-1T>=0.

Задача состоит  в том, чтобы найти вектор Т (0, t₂ , t₃) максимизирующий суммарный прирост прибыли (т. к. y₁=0 то t₁=0)

       W = 7 t₂ +5 t₃   → max

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

   8   0                  0

       24       +                           * t₂   0

        40  t₃  0 
 

         0                             120

         t2 ≤    1/3     168

         t3                             80 

причем по смыслу задачи t₂ 0  , t₃ 0 

Составим систему  уравнений для графического решения

      1,5* t₂ -1,75* t₃ 8  (1)  точки (0; -4 ); (5 ;0)

-0,5* t₂ +0,75* t₃ 24 (2)  точки (0;32); (-48;0)

                    -0,5* t₃ 40 (3) 

             t₂ (4) 

                    t₃ (5)

приходим к  задаче линейного программирования 

Эту задачу решим графически:  

1,5* t₂ -1,75* t₃ =8 

t₃

1,5* t₂ -1,75* =8

1,5* t₂  =      =>  t₂ =16 

Программа "расшивки" имеет вид

T_опт = 0;16;26

W_max= 7 t₂ +5 t₃ =7*16+5*26 =388 и прирост прибыли составит 388

При новом плане  выпуска продукции

X₅ ^н =-1,5* 16 +1,75* 26 +8=0

X₃ ^н =0,5* 16 -0,75* 26 +24=22

X₁ ^н =1,5* 16 +40=53

Z ^н =31*53 +14*22 =1964

Z ^н =1576+388 =1964

Графическое решение

 
 
 
 
 
 

Сводка  результатов приведена в Таблице1  

                                                                                    Таблица1