Тапсырманы орындау мысалы

Жоғарыда суреттелген алгоритмді мысалмен көрсетейік. w₀=0 болсын, ал w_j=- . 3-кестедегі мәліметтерді ескере отырып t_ij мәндерін есептейміз.

0-қадам.

Т: t₁₀= C₁₀- w₀=1-0=1

t₂₀= C₂₀- w₀=4-0=4

t₃₀= C₃₀- w₀=3-0=3

t₁₂= C₁₂- w₂=2+ w₂= , t₁₃= ;

t₂₁= C₂₁- w₁=3+ w₁= , t₂₃= ;

t₃₁= C₃₁- w₁=1+ w₁= ; t₃₂= .

1-қадам. min {tij}-ді анықтаймыз.

min {t_ij}= t₁₀=1

9 – сурет. S₁ және S₀ тораптар жалғануы

2-қадам. а₁=2>0; r₁₀=5; a₁<r₁₀.

Шарттың орындалуы 3-қадамға өтуге мүмкіндік береді.

3-қадам. Жаңа мәндерді есептейміз:

а¹₁=0; a¹₀=-8+2=-6; r¹₁₀=5-2=3; F=C₁₀=1.

w₁=0; t₁₀= қойып, 0-қадамға өтеміз.

0-қадам. Есептейміз:

Т¹: t₂₁= C₂₁- w₁=3-0=3;

t₃₁= C₃₁- w₁=1-0=1.

1-қадам. min {TUT¹}= t₃₁, т.е. S₃=>S₁.

2-қадам. а₃=3>0; r₃₁=5>a₃; a₁¹+a₃=0+3 r₁₀=3.

3-қадам. a₃¹=0; a₀¹¹=-6+3=-3.

r₁₀¹¹=3-3=0.

r₃₁¹=5-3=2.

F¹=F=C₃₁=1+1=2

10 – сурет. S₁ және S₃ тораптар жалғануы

w₃=0; t₃₁= қойып, 0-қадамға өтеміз.

0-қадам.

Т²: t₂₃=С₂₃- w₃=1.

1-қадам. min {TUT¹ UT²}= min {t_ij}=t₂₃ анықтаймыз.

2-қадам. а₂=3>0; r₂₃=5>a₂; r₃₁¹=2<a₂, сәйкесінше S₂=>S₃ қосылуы мүмкін емес, t₂₃= қойып, 1-қадамға өтеміз.

1-қадам. min {TUT¹ UT²}= t₂₀=2.

2-қадам. а₂=3>0; r₂₀=5>а₂.

3-қадам.. а₂¹=0; r₂₀¹=5-3=2; а₀¹¹¹=-3+3=0

F=2+4=6

Барлық а_i¹=0 болғандықтан, тапсырма шешімі табылды.

11 – сурет. Прим әдісі бойынша құрылған желі сұлбасы

Дата добавления: 2015-07-11