Axborot texnologiyalari va jarayonlarni matematik modellashtirish

Matematik model. Ob`ektlarni aylanib o`tish rejasi |x_ij| - matritsa orqali berilgan bo`lsin. Matritsa elementlari ikkilik sonlardan iborat, ya`ni x_i =1, agar i - ob`ektdan j – ob`ektga o`tsa va x<sub>i</sub> =0, agar i - ob`ektdan j – ob`ektga bormasa.
Maqsad funktsiyasining
F=
Minimumini quyidagi cheklovlarda aniqlashni talab etiladi:
=1, j=

faqat bir marta j – ob`ektga kirish.



faqat bir marta i– ob`ektdan chiqish.
=1, i=

Bu turdagi masalalarda yana bir qo`shimcha shart qo`yiladi:
u_i-u_j+(m-1)x_ij ≤m-2, i≠j, i,j=2 , m
Bu maxsus shart o`zaro bog`lanmagan bir qancha yo`nalish va takrorlanishlarni bartaraf etadi, ya`ni muhandisning ob`ektlarni aylanib chiqishi yopiq marshrut bo`ylab amalga oshadi.
Demak, muhandisning ob`ektlarni aylanib chiqishining shunday rejasi
tuzilishi kerakki, “Umumiy masofa” = “Masofalar matritsasi” * “Aylanib o`tish rejasi” minimal qiymatni quyidagi cheklovlarda qabul qilishi kerak:

• 
  “Kirish” = 1 (muhandisning ob`ektga kirishi).
  
• 
  “Chiqish” = 1 (muhandisning ob`ektdan chiqishi).
  
• 
  o`zaro bog`lanmagan yo`nalishlar mavjudligini istisno qilish.
  

Excel dasturida masalani yechish: beshta ob`ekt berilgan bo`lib, ular orasidagi
c_ij masofa (km da) quyidagi jadvalda berilgan.

Ob`ekt raqami	1	2	3	4	5
1	∞	11	10	6	12
2	8	∞	6	7	9
3	7	5	∞	8	4
4	3	9	4	∞	5
5	4	6	7	4	∞

Jadvalning diagonal kataklarida cheksiz belgisi (∞) yozilgan. Ob`ektning o`zidan o`ziga marshrut bo`lmagani uchun bu belgi o`rniga amaldagi jadvaldagi sonlarga nisbatan katta son ko`rsatiladi.
Excel dasturining ish sahifasiga boshlang`ich ma`lumotlarni, cheklovlar va maqsad funksiyasining hisoblash formulalarini kiritamiz.

1. 
   “O`zgaruvchilar matritsasi” va “cheklovlar” matnini mos ravishda B2 va G2 kataklarga yozamiz.
   
2. 
   Qulaylik uchun birdan beshgacha bo`lgan raqamlarni B3:F3 va A4:A8 kataklar sohasiga kiritamiz.
   
3. 
   O`zgaruvchilar matritsasi uchun B4:F8 kataklar sohasini ajratamiz va ularning qiymati sifatida nolni kiritamiz.
   
4. 
   Cheklovlar formulalarini (ob`ektga faqat bir marta kirish) G4:G9 kataklar sohasiga yozamiz: СУММ(B4:F4). =СУММ(B5:F5). =СУММ(B6:F6).
   

=СУММ(B7:F7). =СУММ(B8:F8).

5. 
   Cheklovlar so`zini A9 katakka kiritamiz.
   
6. 
   Cheklovlar formulalarini (ob`ektdan faqat bir marta chiqish) mos ravishda B4:F9 kataklarga yozamiz: =СУММ(B4:B8). =СУММ(C4:C8).
   

=СУММ(D4:D8). =СУММ(E4:E8). =СУММ(F4:F8).

7. 
   “B10 da maqsad funksiyasi” va “C11:F11 sohada u o`zgaruvchilar matnini A10 va A11 kataklarga kiritamiz.
   
8. 
   B10 katakka – СУММПРОИЗВ(B4:F8.B14:F18) formulani yozamiz.
   
9. 
   “Masofalar matritsasi” matnini, birdan beshgacha raqamlarni mos ravishda B12, B13:F13, A14:A18 kataklarga kiritamiz.
   
10. 
    Masofalar matritsasi qiymatini B14:F18 kataklar sohasiga yozamiz.
    
11. 
    “Qo`shimcha u o`zgaruvchilar bo`yicha cheklovlar uchun formulalar”
    

matnini A19 katakka yozamiz.

12. 
    A21:A24, B20:E20 kataklar sohasiga u2, u3, u4, u5 belgilarni kiritamiz.
    
13. 
    A21:E24 kataklar sohasiga “o`zaro bog`lanmagan yo`nalishlar mavjudlik holatini istisno qiluvchi” cheklovlarni, ya`ni:
    

B21:E21 kataklarga:
=C11-C11+4*C5: =C11-D11+4*D5. =C11-E11+4*E5. =C11-F11+4*F5.
B22:E22 kataklarga:
=D11-C11+4*C6: =D11-D11+4*D6. =D11-E11+4*E6. =D11-F11+4*E6.
B23:E23 kataklarga:
=E11-C11+4*C7: =E11-D11+4*D7. =E11-E11+4*E7. =E11-F11+4*F7.
B24:E24 kataklarga:
=F11-C11+4*C8: =F11-D11+4*D8. =F11-E11+4*E5. =F11-F11+4*F8.
formulalarni yozamiz.

14. 
    “Поиск решения” elementini ishga tushirib, unga quyidagi kattaliklarni kiritamiz:
    

Maqsad katagi - $B$10.
U kichik qiymatga teng (Равной: * минимальному значению).
Qiymatlari o`zgaruvchi kataklar (Изменяя ячейки): $B$4:$F$8.
$B$11:$F$11. Bunda faqat qiymatlari o`zgaruvchi va masalaning yechimi yoziluvchi kataklar ($B$4:$F$8) bilan bir qatorda u_i o`zgaruvchini o`zida saqlovchi va qiymatlari o`zgaruvchi $C$11:$F$11 kataklar ham kiritiladi.
Cheklovlar:
$B$21:$E$24≤3.
$B$4:$F$8 =ikkilik son.
$B$9:$F$9=1.
$G$4:$G$8=1.
$B$4=0.
$C$5=0.
$D$6=0.
$E$7=0.
$F$8=0.
Kattaliklar: chiziqli model (линейная модель), manfiy bo`lmagan qiymatlar (неотрицательные значения), to`g`ridan-to`g`ri masshtablash (автоматическое масштабирование).



“Поиск решения” muloqot oynada kursorni “Выполнить” tugmasiga keltirib sichqonchaning chap tugmasi bosilsa, dasturning ish sahifasida masalaning yechimi hosil bo`ladi.
Optimal yechim: maqsad funksiyasining qiymati F=28 bo`lib, ob`ektlarni aylanib chiqish 1, 4, 3, 5, 2, 1 ketma-ketlikda amalga oshiriladi.