Контрольная работа по "Прикладной математике"

Автор работы: Пользователь скрыл имя, 18 Декабря 2012 в 12:06, курсовая работа

Описание

1. Линейная производственная задача.
....
Задание:
Сформировать задачу, двойственную линейной производственной задаче и найти ее решение, пользуясь первой, а потом второй теоремами двойственности. Указать оценку единицы каждого ресурса, минимальную суммарную оценку всех ресурсов, оценки технологий.

Работа состоит из  1 файл

курсовая приклад.doc

— 234.00 Кб (Скачать документ)

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

 

Исходные данные:

 

59

27

20

35

 

1

3

2

2

102

3

2

0

3

204

4

2

3

1

188


 

Задание:

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


        a11    a12    a13    a14                          b1

A =  a21    a22    a23    a24   ,   B =   b2    ,  C = ( c1         c2     c3     c4 )

        a31    a32    a33    a34                          b3

 

которые компактно записаны в виде

  c1         c2     c3     c4

a11    a12    a13    a14       b1

a21    a22    a23    a24       b2

a31    a32    a33    a34       b3

 

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

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

 

Решение:

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


           1   3   2   2             102


А =  3   2  0   3   ;   В =  204   ;   С = ( 59   27   20   35 ).

        4   2   3   1               188

 

Математическая же модель задачи: найти производственную программу 

(x1, x2 ,x3,,x4), максимизирующую прибыль

                Z(x1, x2 ,x3,,x4) = 59 x1 + 27 x2 + 20x3 +35 x4 → max ,

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

1x1 + 3x2 + 2x3 + 2x ≤ 102

3x1 + 2x2 + 0x3 + 3x4 ≤ 204

4x1 + 2x2 + 3x3 + 1x4  ≤ 188

где по смыслу задачи x1, x2, x3, x4 ≥ 0.

Получили задачу линейного  программирования. Чтобы решить ее, заменяем неравенства системы уравнениями при помощи дополнительных неотрицательных неизвестных x5, x6 , x7, называемых балансовыми, оптимальные значения которых имеют экономический смысл остатков ресурсов. Получается каноническая задача ЛП:

59 x1 + 27 x2 + 20x3 +35 x4 → max,

1x1 + 3x2 + 2x3 + 2x + x5 = 102,

3x1 + 2x2 + 0x3 + 3x4 + x6 = 204,

4x1 + 2x2 + 3x3 + 1x4  + x7 =188,

x1,…, x7 ≥ 0.

2.Будем решать эту  задачу симплексным методом.

 

 

     

  59

  27

  20

  35

   0

   0

   0

СБ

   Б

   Н

   X1

   X2

   X3

   X4

   X5

   X6

   X7

0

0

0

  X5

   X6

   X7

102

204

188

   1

   3

   4

   3

   2

   2

   2

   0

   3

   2

   3

   1

   1

   0

   0

   0

   1

   0

   0

   0

   1

 

  Z

   0

-59

-27

-20

-35

   0

   0

   0

0

0

59

   X5

   X6

   X1

  55

  63

  47

  0

   0

   1

  5/2

  1/2

  1/2

  5/4

-9/4

  3/4

  7/4

  9/4

  1/4

   1

   0

   0

   0

   1

   0

-1/4

-3/4

  1/4

 

  Z

2773

   0

  5/2

97/4

-81/4

   0

   0

59/4

0

35

59

   X5

   X4

   X1

   6

  28

  40

   0

   0

   1

19/9

  2/9

  4/9

   3

  -1

   1

   0

   1

   0

   1

   0

   0

-7/9

  4/9

-1/9

  1/3

-1/3

  1/3

 

   Z

3340

   0

   7

   4

   0

   0

    9

   8


 

 

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

                bi                      102     204     188        188


  min  —―̶̶̶̶̶̶  ̶ ̶̶̶ ̶ = min    ―̶̶̶̶̶̶  ̶ ̶̶̶ ; ―̶̶̶̶̶̶  ̶ ̶̶̶ ; ―̶̶̶̶̶̶  ̶ ̶̶̶        = ―̶̶̶̶̶̶ ̶ ̶̶̶ .

            ai1>0                   1         3         4            4

 

Оно соответствует третьему уравнению. Это означает, что за решающее уравнение в системе принимается  третье. Коэффициент а31 = 4 будет разрешающим. Применив формулы исключения, переходим к новому предпочитаемому виду системы с соответствующим базисным допустимым решением. При этом неизвестная х1 становится базисной. Придется ее исключить из целевой функции, чтобы иметь возможность исследовать новое базисное допустимое решение на оптимальность. Получаем первую симплексную таблицу. Аналогично поступаем и далее, пока в последней строке третьей таблицы не осталось ни одного отрицательного оценочного коэффициента Δ j , т.е. выполняется критерий оптимальности для максимизируемой функции цели.

Производная программа

х1 = 40, х2 = 0, х3 = 0, х4 = 28

является оптимальной  и обеспечивает предприятию наибольшую возможную прибыль Zmax = 3340. При этом второй и третий ресурсы будут использованы полностью х6 = 0, х7 = 0, а первый ресурс будет иметь остаток х5 = 6, т.е. второй     и третий ресурсы образуют “узкие места производства”.

                             

 

 

 

 

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

 

Исходные данные:

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

          59 x1 + 27 x2 + 20x3 +35 x4 → max ,

1x1 + 3x2 + 2x3 + 2x ≤ 102,

3x1 + 2x2 + 0x3 + 3x4 ≤ 204,

4x1 + 2x2 + 3x3 + 1x4  ≤ 188,

                                 x1-4  ≥ 0.

 

Задание:

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

 

Решение:

Необходимо найти оценку единицы каждого вида ресурса, т.е. необходимо найти вектор двойственных оценок (y1, y2, y3), минимизирующий общую оценку ресурсов всех ресурсов

102y1 + 204y2 + 188y3 → min,

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

1y1 + 3y2 + 4y3 ≥59,

3y1 + 2y2 + 2y3 ≥27,

2y1 + 0y2 + 3y3 ≥20,

2y1 + 3y + 1y3 ≥35,

причем оценки ресурсов не могут быть отрицательными y1-3 ≥0.

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений  x(x1, x2, x3, x4 ) и y(y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий

  xi  (  ∑ aij·y –  cj ) = 0                  yi   ( bi  – ∑ aij·xj ) = 0

              i                                                                                                   i

      x1 (1y1 + 3y2 + 4y3 –59) = 0           y1 (1x1 + 3x2 + 2x3 + 2x4 –102 ) = 0

x2 (3y1 + 2y2 + 2y3 –27) = 0           y2 (3x1 + 2x2 + 0x3 + 3x4 –204 ) = 0

x3 (2y1 + 0y2 + 3y3 –20) = 0           y3 (4x1 + 2x2 + 3x3 + 1x4 –188 ) = 0

x4 (2y1 + 3y + 1y3 –35) = 0      

В предыдущей задаче было найдено 

x1 = 40, x2 = 0, x3 = 0, x4 = 28, т.е. x1 >0, x4 >0. Поэтому

1y1 + 3y2 + 4y3 –59 = 0,

2y1 + 3y + 1y3 –35 = 0.

 

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

 y1 = 0                                       y1 = 0                              y1 = 0   


 y1 + 3y2 + 4y3 –59 = 0            3y2 + 4y3 = 59                  y2 = 9


2y1 + 3y +  y3 –35 = 0             3y +  y3 =35                    y3 = 8

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

y1 = 0, y2 = 9, y3 = 8, причем общая оценка всех ресурсов равна 3340.

   

Экономический смысл  двойственных оценок:

  • двойственная оценка второго ресурса у2=9 показывает, что добавление одной единицы второго ресурса обеспечит прирост прибыли в 9 единиц;
  • двойственная оценка третьего ресурса у3=8 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли в 8 единиц.

 

 

 

 

 

 

 

 

 

 

 

                    

 

 

 

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

 

Исходные данные:

из задачи 1.1. получили следующие данные

 

   X5

   X4

   X1

   6

  28

  40

   0

   0

   1

19/9

  2/9

  4/9

   3

  -1

   1

   0

   1

   0

   1

   0

   0

-7/9

  4/9

-1/9

  1/3

-1/3

  1/3

 

   Z

3340

   0

   7

   4

   0

   0

    9

   8


 

Задание:

Решить задачу о “расшивке  узких мест”.

 

Решение:

При выполнении оптимальной  производственной программы второй и третий ресурсы используются полностью, т.е. образуют “узкие места производства”. Будем их заказывать дополнительно. Пусть Т(0, t2, t3) – вектор дополнительных объемов ресурсов. Так как используются найденные двойственные оценки, то должно выполняться следующее условие:

H + Q-1T ≥ 0.

Задача состоит в  том, чтобы найти вектор , максимизирующий суммарный прирост прибыли:

W = 9 t2 + 8 t3

при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры  производственной программы), предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида


0                  102

t2         ≤  1/3   204

   t3                  188  ,

причем по смыслу задачи  t2 ≥0, t3 ≥ 0.

Следовательно, получаем


6              1   -7/9   1/3          0                 0

28   +      0    4/9  -1/3    •    t2            0

40            0   -1/9   1/3         t3           0    .

Перемножим матрицы  и получим следующую систему  неравенств:

-7/9t2  + 1/3t3  ≥ -6,                  -7t2  + 3t3  ≥ -54,         (I)        


4/9t2    – 1/3t3   ≥ -28,                  4t2   – 3t3   ≥ -252,      (II)

-1/9t2  + 1/3t3   ≥ -40,     Þ        - t2   + 3t3    ≥ -360;      (III)

  t2 ≤ 204/3, t3 ≤ 188/3,                t2 ≤204/3, t3 ≤ 188/3,

       t ≥ 0, t ≥ 0;                           t ≥ 0, t ≥ 0.

 

Решим данную задачу графически.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                   

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

t = 0, t = 242/7 , t3 = 188/3,

и прирост прибыли  составит maxW = 9∙242/7+ 8∙188/3 =17062/21 ≈ 812,48 в точке М(242/7,188/3)

 

                                                Транспортная задача.

   

Кондитерской фабрике  необходимо распределить между 4 (n) магазинами шоколадные конфеты из 3-х (m) фабрик-филиалов в количестве 45, 55, 70 единиц, которым необходимо соответственно 59, 27, 40, 35 единиц. Стоимости перевозок единицы продукта из пункта отправления в пункт назначения равна:

Необходимо составить  план перевозок, при котором запросы  всех магазинов были бы удовлетворены  за счет имеющихся продуктов на 3-х фабриках-филиалах и общие транспортные расходы  по доставке продуктов были минимальными

Информация о работе Контрольная работа по "Прикладной математике"