Белгілеу(үлестіру) туралы есеп

n механизмдерді үлестіру туралы есепте әрбір механизм тек бірден бір жұмысты орындайтын етіп және әрбір механизмнің берілген өнімділігі бойынша әрбір жеке жұмыстың жалпы тиімділігі максимальды болатындай етіп, n жұмысқа бөлу керек.

Белгілеулер:

a_ij, i=1,n, j=1,n – i-ші механизмнің j-ші жұмыстағы өнімділігі,

x_ij –i-ші механизмді j-ші жұмысқа белгілеу.

Қарапайым актілер:

1) Процесс тиімділігін максимальдау.

2) Бір механизм бір жұмысты орындайды.

3) Бір жұмыс тек бір механизммен орындалу керек.

Есептің математикалық моделі:

x →max,

=1,j=1,n

 

=1,i=1,n

 

x_ij =

 

Оңтайландыру есебінің айқын математикалық өрнегінің өңделіп, жетілдіруі

Келесі белгілеуді енгізейік:

γ_ij – бір бояу маркасынан басқа маркаға көшкен кезде шығатын шығындар;

Тәуелсіз айнымалылар:

xij – i-ші химиялық агрегаттан j-ші маркаға жіберілген бояу мөлшері.

Қарапайым актілер:

1)Химиялық агрегатта бояуды қайта өңдеуге болатын шығындарды минималдау;

 

Максатты функция:

Z=x12+7*x13+3*x14+14*x15+2*x16+3*x21+6*x23+9*x24+x25+24*x26+6*x31+14*x32+3*x34+7*x35+3*x36+2*x41+3*x42+5*x43+9*x45+11*x46+15*x51+7*x52+11*x53+2*x54+4*x56+20*x61+5*x62+13*x63+4*x64+13*x65→ min

 

 

Шектеулер:

x12+x13+x14+x15+x16=1

x21+x23+x24+x25+x26=1

x31+x32+x34+x35+x36=1

x41+x42+x43+x45+x46=1

x51+x52+x53+x54+x56=1

x61+x62+x63+x64+x65=1

 

x21+x31+x34+x35+x36=1

x12+x32+x42+x52+x62=1

x13+x23+x43+x53+x63=1

x14+x24+x34+x54+x64=1

x15+x25+x35+x45+x65=1

x16+x26+x36+x46+x56=1

 

X_{ij =} { 1,егер i-ші механикалық шеберханадан, j-ші операция белгіленген болса,

0,егер і-ші механикалық шеберханадан, j-ші операция белгіленбеген болса

 

Алгоритмнің негізгі ойын баяндау

Коммивояжер есебі

Коммивояжер n пункте (немесе қалаға) минимальды жолмен бір-бір реттен ғана кіріп,алғашқы (басқы) қалаға оралу керек. Қалалар арасындағы жол құны матрицасымен берілген,мұнда i=1,n; j=1,n.

 

Қарапайым актілер:

1. Коммивояжердің жол шығындарын минималдау

2. Коммивояжердің ең тиімді жол желісін табу

 

Негізгі түсінектемелер:

Цикл (t) деп реттелген қалалар жиынтығын (маршрутты) айтады, егер коммивояжер әрбір қаладан бір-бір реттен ғана өтсе

 

t=[(i ,i ),(i ,i ),…,(i ,i ),(i ,i )]

 

Сонда коммивояжердің жалпы жол шығыны t циклна:

 

 

Циклға матрицаның әрбір жолының және әрбір бағанының бір элементі ғана кіреді.

Егер i-ші жолдың әрбір элементәнен немесе j-ші бағанның әрбір элементінен минималдысын алсақ. онда келтірілген матрицаны табамыз.

Келтіру процесінде табылған минималды элементтерінің қосындысы ол келтірілген константа болады , k-келтіру процесінің нөмері.

 

Коммивояжер туралы есептің математикалық моделі:

x →min,

=1,j=1,n

 

=1,i=1,n

 

=

 

Литтл алгоритмі

 

1- қадам. k=1

2- қадам. Келтірілген матрицаны табу

=

= -

=

= -

Келтірілген матрицаны табу үшін әрбір жолдың оң жағына ең кіші (минималды) элементі(коэффицентті) жазып, жолдың әрбір элементінен алып тастаймыз.Сонда соң матрицаның төмен жағына әрбір бағанның минималды элементін жазып,бағанның әрбір

элементінен алып тастаймыз.

3-қадам. Келтірілген константаны табу. , ол Х жиынының төменгі шекарасы болады ω(x)=h^(k) .

4-қадам. Тарауға (Y жиыны) үміткерлер жұбын таңдау.

Тарауға тек =0 (i,j) жұптарын қарастырамыз.

5-қадам. Үміткерлер үшін бағаларын анықтау.

θ(i,j)= +

6-қадам. Барлық бағалар ішінен ең үлкенін таңдаймыз.

θ(k,j)=max θ(i,j)

7-қадам. Y жиыны үшін бағасын есептеу.

ω(Y)=ω(x)+ θ(k,l)

8-қадам. Әрбір пунктен(қаладан) бір реттен ғана шығатын болғандықтан,k-жолды матрицадан сызып тастаймыз.Әрбір пункте(қалаға) бір-бір реттен ғана кіргендіктен,l-

бағанды да матрицадан сызып тастаймыз(шығарып тастаймыз).Пункттердің(қалалардың)

барлығын аралау үшін (l,k) жұбына шексіздік (∞) қоямыз.

9-қадам. Тексеру алынған матрицаның шамасы 2x2 болса,екі жұп тарауға таңдалады.

Есептің шешімі табылды.Егер матрица шамасы 2x2 болмаса,онда 10 қадамға көшу.

10-қадам. Келтіру рәсімі жасалады, h есептелінеді, Y жиынының бағасы есептеледі

ω (Y)=ω(x)+h ,k=k+1 болады 4 қадамға көшу.