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

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

 

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

 

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 + 2x4  ≤ 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 + 2x4  + 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 + 2x4  ≤ 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 + 3y2  + 1y3 ≥35,

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

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

  xi  (  ∑ aij·yi  –  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 + 3y2  + 1y3 –35) = 0      

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

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

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

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

 

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

 y1 = 0                                       y1 = 0                              y1 = 0   


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


2y1 + 3y2  +  y3 –35 = 0             3y2  +  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,

       t2  ≥ 0, t3  ≥ 0;                           t2  ≥ 0, t3  ≥ 0.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                   

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

t2  = 0, t2  = 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-х фабриках-филиалах и общие транспортные расходы  по доставке продуктов были минимальными

 

Решение.

 

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

Исходные данные задачи имеют вид: А (а1, а2, а3) = (45, 55, 70); В (b1, b2, b3) = (59, 27, 40, 35);

Общий объем производства больше, чем требуется всем магазинам , т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 170-161 = 9 ед., при этом тарифы на перевозку в этот пункт будут равны нулю.

 

Первое базисное допустимое решение строится по методу северо-западного  угла:

Определяем минимальные  транспортные расходы по доставке продукции:

L1 = 45 ·1 + 14 · 3 + 27 · 2 + 14 · 4 + 26 · 3 + 35 · 1 + 9 · 0 = 310 ед.

 

Вычисление потенциалов    Вычисление оценок всех свободных клеток

D11=0

q1+ p1-c11=0

q1+0-1=0

q1=1

  

D31=q1+p3-c31=1+1-4= -2

D21=0

q1+p2-c21=0

1+p2-3=0

p2=2

  

D12=q2+p1-c12=0+0-3= -3

D22=0

q2+p2-c22=0

q2+2-2=0

q2=0

  

D13=q3+p1-c13=2+0-2=0

D23=0

q3+p2-c23=0

q3+2-4=0

q3=2

  

D14=q4+p1-c14=0+0-2= -2

D33=0

q3+p3-c33=0

2+ p3-3=0

p3=1

  

D15=q5+p1-c15= -1+0-0= -1

D34=0

q4+p3-c34=0

q4+1-1=0

q4=0

  

D25=q5+p2-c25= -1+2-0= 1

D35=0

q5+p3-c35=0

q5+1-0=0

q5= -1

          

Находим в транспортной таблице наибольшую положительную  оценку свободной клетки Dij.  В нашем случае – это одна единственная клетка с25=1. Оценка свободной клетки Dij показывает, насколько уменьшатся суммарные расходы по перевозке груза, если поставить единицу груза от i-го производителя j-му потребителю (перераспределив остальные поставки так, чтобы сохранился баланс по строкам и столбцам).

 

Для найденной свободной  клетки 25 строим цикл пересчета:

 

14

 

 

®

14-ρ

ρ

®

ρmax=9

5

9

26

35

9

26+ρ

9-ρ

35

  

 

Получаем второе базисное допустимое решение:

 

 

L2 = 45 ·1 + 14 · 3 + 27 · 2 + 5 · 4 + 9 · 0 + 35 · 3 + 35 · 1 = 301 ед.

 

Все оценки свободных  клеток £ 0, следовательно, мы получили оптимальное базисное допустимое решение:

 

 

 

 

 

 

 

 

 

 

 

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

 

Пусть производственное объединение состоит из четырех  предприятий (n=4). Общая сумма капитальных  вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 4.1., где, например, число 38 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 38 тыс. руб.

 


Таблица 4.1.

xj

0

100

200

300

400

500

600

700

f1(x1)

0

10

20

30

38

43

49

52

f2(x2)

0

13

25

37

47

55

61

66

f3(x3)

0

6

13

20

27

33

38

41

f4(x4)

0

24

36

42

46

48

48

49


 

 

Решение.

 

Прежде всего заполняем  табл. 4.2. Значения f2(x2) складываем со значениями F1(x - x2) = f1(x- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение .

 

Табл. 4.2.

 

 

 

 Заполняем таблицу  4.3.

 

Табл. 4.3.

x

0

100

200

300

400

500

600

700

F2(x)

0

13

25

37

47

57

67

77

0

100

200

300

300/400

300/400

300/400

400


 

 

 

Продолжая процесс, табулируем функции F3(x), (x)  (см. Табл. 4.4. и 4.5.) и т.д.

 

Табл. 4.4.

 

 

Табл. 4.5.

 

x

0

100

200

300

400

500

600

700

F3(x)

0

13

25

37

47

57

67

77

0

0

0

0

0

0

0

0


 

В табл. 4.6. заполняем только одну диагональ для значения x= 700.

Табл. 4.6.

 

 

Наибольшее число на этой диагонали:

 

Zmax = 93 тыс. руб.,

 

причем четвертому предприятию  должно быть выделено:

 

 тыс. руб.

 

На долю остальных  трех предприятий остается 500 тыс. руб. Из Таб. 4.5. видно, что третьему предприятию  должно быть выделено:

 

 тыс. руб.

 

 

Продолжая обратный процесс, находим:

 

1) тыс. руб.

 

2) тыс. руб.

  На долю первого предприятия остается:

 

1) тыс. руб.

 

2) тыс. руб.

 

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

 

1)

 

2)

 

Оно обеспечивает производственному  объединению наибольший воможный прирост прибыли 93 тыс. руб.

 

Проверка выполнения равенства:

 

 

1)

 

2)

 

 

 

 

 

 

 

 

 

 

 

 

               

 

     Теория игр

 

 

Игроки

B1

B2

B3

B4

a = min(Ai)

A1

-1

-3

-5

0

-5

A2

2

0

2

-1

-1

b = max(Bi)

2

0

2

0

  



 

 

 

 

 

 

Находим гарантированный  выигрыш, определяемый нижней ценой  игры a = max(ai) = -1, которая указывает на максимальную чистую стратегию A2. 
Верхняя цена игры b = min(bj) = 0. 
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах -1 <= y <= 0. Находимо решение игры в смешанных стратегиях. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии)

В матрице присутствуют отрицательные элементы. Для упрощения  расчетов добавим к элементам  матрицы (5). Такая замена не изменит  решения игры, изменится только ее цена.

4

2

0

5

7

5

7

4


 
Решим задачу геометрическим методом, который включает в себя следующие  этапы: 
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2). 
2. На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2. 
Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет. 
Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B2B2 и B4B4, для которых можно записать следующую систему уравнений: 
y = 2 + (5 - 2)p2 
y = 5 + (4 - 5)p2 
Откуда 
p1 = 1/4 
p2 = 3/4 
Цена игры, y = 41/4

 

Оптимальные стратегии  игрока А: Sа ( 1/4 ; 3/4 )

 
Теперь можно найти минимаксную  стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B1,B3, которая дает явно больший проигрыш игроку B, и, следовательно, q1 = 0,q3 = 0. 

2q2+5q4 = y 
5q2+4q4 = y 
q2+q4 = 1 
или 
2q2+5q4 = 41/4 
5q2+4q4 = 41/4 
q2+q4 = 1 
Решая эту систему, находим: 
q2 = 1/4 
q4 = ¾

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
Поскольку ранее к элементам матрицы  было прибавлено число 5, то вычтем это число из цены игры. 
Цена игры: y = 41/4 - 5 = -3/4

Оптимальные стратегии  игрока B: SB ( 0; ¼; 0; 3/4)

 

 

 

 

 


Контрольная работа по Прикладной математике 📙 Курсовая → 🆔 109457

Контрольная работа по Прикладной математике 📙 Курсовая → 🆔 109457

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