Смекни!
smekni.com

Технические средства автоматизизированных систем управления в строительстве (стр. 3 из 5)

Матрицу решаем методом двойного предпочтения.

Таблица 3 – Базисный план.

J 1 2 3 4 5 6 7 ∑=
i 40 55 45 30 35 35 42 282
1 20

+5

(15)

9 6 12 7

+2

(5)

13 0
2 25 12 13

+3

(15)

9

(7)

8

(3)

10 11 1
3 40

8

(25)

9 10

13

(15)

19 7 9 -3
4 35 9

++4

(35)

7 8 +6 12 10 2
5 50 10 11 9

12

(8)

15 5

++2

(42)

-2
6 30 7 16

++1

(30)

+5 9 17 10 3
7 30 17 14 9 7 11

++1

(30)

4 1
8 52 13

++4

(20)

19

8

7

(32)

15 12 2
∑= 282 5 6 4 10 9 2 0

Проверяем количество заполненных клеток, которое должно быть равно m+n-1, т.е. суммарному количеству строк и столбцов без единицы.

8+7-1=14, количество заполненных клеток N=14, условие выполняется.

Целевая функция плана:

Для улучшения первоначального базисного плана применяется метод потенциалов. Потенциалами называются такие численные характеристики строк Uiи столбцов Vj, при которых соблюдается условие оптимальности плана. Математически это условие записывается так:

(условие для занятых клеток);

(условие для свободных клеток);

,

Подбор потенциалов начинаем с первой строки. Принимаем U1=0.

U1=0 V1=0+5=5
U2=10-9=1 V2=2+4=6
U3=5-8=-3 V3=1+3=4
U4=6-4=2 V4=-3+13=10
U5=1+8=9 V5=10-12=-2
U6=4-1=3 V6=0+2=2
U7=2-1=1 V7=9-7=2
U8=9-7=2

Далее производим проверку условия для свободных клеток по формуле:

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

Оптимизируем план.

Итерация 1.

Для этого от клетки ∆6,4 строим контур перераспределения.

Получаем: до перераспределения условные затраты на перевозку

15*3+7*9+30*1=138;

После перераспределения условные затраты на перевозку составили

22*3+23*1+7*5=124.

Таблица 4 – Оптимизированный базисный план.

J 1 2 3 4 5 6 7 ∑=
i 40 55 45 30 35 35 42 282
1 20

+5

(15)

9 6 12 7

+2

(5)

13
2 25 12 13

+3

(22)

9

8

(3)

10 11
3 40

8

(25)

9 10

13

(15)

19 7 9
4 35 9

++4

(35)

7 8 +6 12 10
5 50 10 11 9

12

(8)

15 5

++2

(42)

6 30 7 16

++1

(23)

+5

(7)

9 17 10
7 30 17 14 9 7 11

++1

(30)

4
8 52 13

++4

(20)

19

8

7

(32)

15 12
∑= 282

Далее от клетки ∆1,5 строим контур перераспределения

Получаем: до перераспределения условные затраты на перевозку

15*5+3*8+22*3+23*1+7*5+15*13+25*8=618;

После перераспределения условные затраты на перевозку составили

12*5+3*7+25*3+20*1+10*5+12*13+28*8=606.


Таблица 5 – Оптимизированный базисный план.

J 1 2 3 4 5 6 7 ∑=
i 40 55 45 30 35 35 42 282
1 20

+5

(12)
9 6 12

7

(3)

+2

(5)

13
2 25 12 13

+3

(25)

9

8

10 11
3 40

8

(28)

9 10

13

(12)

19 7 9
4 35 9

++4

(35)

7 8 +6 12 10
5 50 10 11 9

12

(8)

15 5

++2

(42)

6 30 7 16

++1

(20)

+5

(10)

9 17 10
7 30 17 14 9 7 11

++1

(30)

4
8 52 13

++4

(20)

19

8

7

(32)

15 12
∑= 282

Далее от клетки ∆7,4 строим контур перераспределения