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

 

 

Содержание.

  • Минимизация затрат на выполнение комплекса работ при заданном времени.

 

  • Расчетная часть

 

 

  • Минимизация времени выполнения комплекса работ при заданных затратах

 

  • Минимизация суммарных затрат по комплексу работ и обьекту

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

MN-83,значит A=3.

Дано:

Комплекс, состоящий из 8 работ, порядок выполнения которых  определяется сетевым графиком.

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

Таблица 1

Порядковый № работы

 

 

Характеристики

 

 

1

 

 

2

 

 

3

 

 

4

 

 

5

 

 

6

 

 

7

 

 

8

аk

15

20

10

15

10

15

20

10

вk

-1

-2

-3

-4

-1

-2

-3

-4

dk

4

3

2

1

4

3

2

1

Dk

10

8

3

3

9

7

6

2


 

Расчетная часть

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

L₁{1;2;5;8}  4+3+4+1=12    10+8+9+2=29

L₂{3;5;8}      2+4+1=7          3+9+2=14

L₃{4;6;8}      1+3+1=5          3+7+2=12

L₄{1;8}          4+1=5              10+2=12

L₅{1;2;5;6;7}  4+3+4+3+2=16     10+8+9+7+6=40

L₆ {3;5;6;7}     2+4+3+2=11          3+9+7+6=25

L ₇{4;7}           1+2=3                     3+6=9

Tmin=16                 Tmax=40

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

16≤ T ≤40

2.Построим математическую  модель данной задачи.

2.1 Строим систему ограничений:

1 гр. dx=t₁ ≥4 ; t₂ ≥3 ; t₃ ≥2 ; t₄  ≥1 ; t₅ ≥4; t₆ ≥3 ; t₇ ≥2 ; t₈≥1

2гр. Dk= t₁ ≤ 10 ; t₂ ≤ 8 ; t₃ ≤ 3 ; t₄ ≤ 3 ; t₅ ≤ 9 ; t₆ ≤ 7 ;t₇ ≤ 6 ; t₈≤ 2

Система ограничений примет следующий  вид:

τ₁≤6 ; τ₂≤5 ; τ₃≤1 ; τ₄≤2 ; τ₅≤5 ; τ₆≤4 ; τ₇≤4 ; τ₈≤1

t₁+t₂+t₅+t₈≤T

t₃+t₅+t₈≤T

t₄+t₆+t₈≤T

t₁+t₈≤T

t₁+t₂+t₅+t₆+t₇≤T

t₃+t₅+t₆+t₇≤T 

t₄+t₇≤T

 

 

τ₁=t₁-4   »   t₁=τ+4

τ₂=t₂-3   »   t₂=τ₂+3

τ₃=t₃-2   »   t₃=τ₃+2

τ₄=t₄-1   »   t₄=τ₄+1

τ₅=t₅-4    »  t₅=τ₅+4

τ₆=t₆-3    »   t₆=τ₆+

τ₇=t₇-2    »    t₇=τ₇+2

τ₈=t₈-1    »   t₈=τ₈+1

После несложных преобразований система  ограничений примет вид:

t₁+t₂+t₅+t₈≤T-12

t₃+t₅+t₈≤T-7

t₄+t₆+t₈≤T-4

t₁+t₈≤T-5

t₁+t₂+t₅+t₆+t₇≤T-16

t₃+t₅+t₆+t₇≤T-11 

t₄+t₇≤T-3

2.2.Строим целевую функцию по  формуле: Z=

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

Z=15+20+10+15+10+15+20+10=100

100+(-1)t₁+(-2)t₂+(-3)t₃+(-4)t₄+(-1)t₅+(-2)t₆+(-3)t₇+(-4)t₈→min

При замене tkᵥ на  τk получим:

Z=100+(-1)(τ₁+4)+(-2)(τ₂+3)+(-3)(τ₃+2)+(-4)(τ₄+1)+(-1)(τ₅+4)+(-2)(τ₆+3)+(-3)(τ₇+2)+

+(-4)(τ₈+1)→min

или

Z=60-τ₁ - 2τ₂ - 3τ₃ - 4τ₄ - τ₅ - 2τ₆ - 3τ₇ - 4τ₈→min

 Исключив константу, полученную целевую функцию запишем в следующем виде:

Z'=τ₁+2τ₂+3τ₃+4τ₄+τ₅+2τ₆+3τ₇+4τ₈→max

Целевая функция Z будет стремиться к минимуму при Z', стремящемуся к  максимуму.

 

3.Представим исходную  задачу в матричной форме.

 

 -Ԏ₁

-Ԏ₂

-Ԏ₃

-Ԏ₄

-Ԏ₅

-Ԏ₆

-Ԏ₇

-Ԏ₈

b

y₁

1

             

6

y₂

 

1

           

5

y₃

   

1

         

1

y₄

     

1

       

2

y₅

       

1

     

5

y₆

         

1

   

4

y₇

           

1

 

4

y₈

             

1

1

y₉

1

1

   

1

   

1

T-12

y₁₀

   

1

 

1

   

1

T-7

y₁₁

     

1

 

1

 

1

T-4

y₁₂

1

           

1

T-5

y₁₃

   

1

 

1

1

1

 

T-11

y₁₄

1

1

   

1

1

1

 

T-16

y₁₅

     

1

   

1

 

T-3

Z дв

-1

-2

-3

-4

-1

-2

-3

-4

0 max




Таблица 2.

 

 

 

 

 

Составим двойственную(сопряженную)задачу.

Таблица 3.

 

 

-y₁

-y₂

-y₃

-y₄

-y₅

-y₆

-y₇

-y₈

-yֹ₉

-y₁₀

-y₁₁

-y₁₂

-y₁₃

-y₁₄

-y₁₅

b

τ₁

-1

             

-1

   

-1

 

-1

 

-1

τ₂

 

-1

           

-1

       

-1

 

-2

τ₃

   

-1

           

-1

   

-1

   

-3

τ₄

     

-1

           

-1

     

-1

-4

τ₅

       

-1

     

-1

-1

   

-1

-1

 

-1

τ₆

         

-1

       

-1

 

-1

-1

 

-2

τ₇

           

-1

         

-1

-1

-1

-3

τ₈

             

-1

-1

-1

-1

-1

     

-4

Z

дв.

-6

-5

-1

-2

-5

-4

-4

-1

12-Т

7-Т

4-Т

5-Т

11-Т

16-Т

3-Т

0

min


 

Перейдем от задачи на минимум  к задаче на максимум. Для этого  целевую функцию умножим на -1.                                    

Таблица 4.

                             

 

-y₁

-y₂

-y₃

-y₄

-y₅

-y₆

-y₇

-y₈

-yֹ₉

-y₁₀

-y₁₁

-y₁₂

-y₁₃

-y₁₄

-y₁₅

b

τ₁

-1

             

-1

   

-1

 

-1

 

-1

τ₂

 

-1

           

-1

       

-1

 

-2

τ₃

   

-1

           

-1

   

-1

   

-3

τ₄

     

-1

           

-1

     

-1

-4

τ₅

       

-1

     

-1

-1

   

-1

-1

 

-1

τ₆

         

-1

       

-1

 

-1

-1

 

-2

τ₇

           

-1

         

-1

-1

-1

-3

τ₈

             

-1

-1

-1

-1

-1

     

-4

Z

дв.

6

5

1

2

5

4

4

1

Т-12

Т-7

Т-4

Т-5

Т-11

Т-16

Т-3

0

max


 

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

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

  Таблица 5.

 

-τ₁

-y₂

-y₃

-y₄

-y₅

-y₆

-y₇

-y₈

-yֹ₉

-y₁₀

-y₁₁

-y₁₂

-y₁₃

-y₁₄

-y₁₅

b

у₁

-1

             

1

   

1

 

1

 

1

τ₂

 

-1

           

-1

       

-1

 

-2

τ₃

   

-1

           

-1

   

-1

   

-3

τ₄

     

-1

           

-1

     

-1

-4

τ₅

       

-1

     

-1

-1

   

-1

-1

 

-1

τ₆

         

-1

       

-1

 

-1

-1

 

-2

τ₇

           

-1

         

-1

-1

-1

-3

τ₈

             

-1

-1

-1

-1

-1

     

-4

Z

дв.

6

5

1

2

5

4

4

1

Т-18

Т-7

Т-4

Т-11

Т-11

Т-22

Т-3

6

max


 

2шаг.Выберем ведущими 2-ю строку и 2-й столбец(табл.5) и произведем пересчет элементов.                                                                                                                              

Таблица 6. 

 

-τ₁

-τ₂

-y₃

-y₄

-y₅

-y₆

-y₇

-y₈

-yֹ₉

-y₁₀

-y₁₁

-y₁₂

-y₁₃

-y₁₄

-y₁₅

b

у₁

-1

             

1

   

1

 

1

 

1

у₂

 

-1

           

1

       

1

 

2

τ₃

   

-1

           

-1

   

-1

   

-3

τ₄

     

-1

           

-1

     

-1

-4

τ₅

       

-1

     

-1

-1

   

-1

-1

 

-1

τ₆

         

-1

       

-1

 

-1

-1

 

-2

τ₇

           

-1

         

-1

-1

-1

-3

τ₈

             

-1

-1

-1

-1

-1

     

-4

Z

дв.

6

5

1

2

5

4

4

1

Т-23

Т-7

Т-4

Т-11

Т-11

Т-27

Т-3

-16

max


 

3 шаг. Выберем ведущими 3-ю строку и 3-й столбец   (табл.6) и произведем пересчет элементов.                                                                                                              

Таблица 7.

 

-τ₁

-τ₂

-τ₃

-y₄

-y₅

-y₆

-y₇

-y₈

-yֹ₉

-y₁₀

-y₁₁

-y₁₂

-y₁₃

-y₁₄

-y₁₅

b

у₁

-1

             

1

   

1

 

1

 

1

у₂

 

-1

           

1

       

1

 

2

у₃

   

-1

           

1

   

1

   

3

τ₄

     

-1

           

-1

     

-1

-4

τ₅

       

-1

     

-1

-1

   

-1

-1

 

-1

τ₆

         

-1

       

-1

 

-1

-1

 

-2

τ₇

           

-1

         

-1

-1

-1

-3

τ₈

             

-1

-1

-1

-1

-1

     

-4

Z

дв.

6

5

1

2

5

4

4

1

Т-23

Т-8

Т-4

Т-11

Т-12

Т-27

Т-3

-19

max


 

4 шаг.Выберем ведущими 4-й столбец и 4-ю строку (табл.7) и произведем пересчет элементов.

Таблица 8.

 

-τ₁

-τ₂

-τ₃

-τ₄

-y₅

-y₆

-y₇

-y₈

-yֹ₉

-y₁₀

-y₁₁

-y₁₂

-y₁₃

-y₁₄

-y₁₅

b

у₁

-1

             

1

   

1

 

1

 

1

у₂

 

-1

           

1

       

1

 

2

у₃

   

-1

           

1

   

1

   

3

у₄

     

-1

           

1

     

1

4

τ₅

       

-1

     

-1

-1

   

-1

-1

 

-1

τ₆

         

-1

       

-1

 

-1

-1

 

-2

τ₇

           

-1

         

-1

-1

-1

-3

τ₈

             

-1

-1

-1

-1

-1

     

-4

Z

дв.

6

5

1

2

5

4

4

1

Т-23

Т-8

Т-6

Т-11

Т-12

Т-27

Т-5

-27

max


 

 

 

 

5 шаг.Выберем ведущими 5-й столбец и 5 строку (табл.8) и произведем пересчет элементов.

 

Таблица 9.

 

-τ₁

-τ₂

-τ₃

-τ₄

-τ₅

-y₆

-y₇

-y₈

-yֹ₉

-y₁₀

-y₁₁

-y₁₂

-y₁₃

-y₁₄

-y₁₅

b

у₁

-1

             

1

   

1

 

1

 

1

у₂

 

-1

           

1

       

1

 

2

у₃

   

-1

           

1

   

1

   

3

у₄

     

-1

           

1

     

1

4

у₅

       

-1

     

1

1

   

1

1

 

1

τ₆

         

-1

       

-1

 

-1

-1

 

-2

τ₇

           

-1

         

-1

-1

-1

-3

τ₈

             

-1

-1

-1

-1

-1

     

-4

Z

дв.

6

5

1

2

5

4

4

1

Т-28

Т-13

Т-6

Т-11

Т-17

Т-32

Т-5

32

max


 

6 шаг.Выберем ведущими 6-й столбец и 6 строку (табл. 9 ) и произведем пересчет элементов.

 

Таблица 10.

 

 

-τ₁

-τ₂

-τ₃

-τ₄

-τ₅

-τ₆

-y₇

-y₈

-yֹ₉

-y₁₀

-y₁₁

-y₁₂

-y₁₃

-y₁₄

-y₁₅

b

у₁

-1

             

1

   

1

 

1

 

1

у₂

 

-1

           

1

       

1

 

2

у₃

   

-1

           

1

   

1

   

3

у₄

     

-1

           

1

     

1

4

у₅

       

-1

     

1

1

   

1

1

 

1

у₆

         

-1

       

1

 

1

1

 

2

τ₇

           

-1

         

-1

-1

-1

-3

τ₈

             

-1

-1

-1

-1

-1

     

-4

Z

дв

6

5

1

2

5

4

4

1

Т-28

Т-13

Т-10

Т-11

Т-21

Т-36

Т-5

40

max

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