Њзбекистон республикаси олий ва њрта махсус

DISKREТ DASТURLASHNING MAТEMAТIK MODELLARI

1. Diskret dasturlash masalalari turlari

Asosiy tushunchalar. Ko„pgina iqtisodiy masalalar shu yo„l bilan xarakterlanadiki (u yoki bu ob‟ektiv xususiyatlar ta‟sirida), boshqaruvchi resurslar hajmlari faqat butun qiymatlarni qabul qilishi mumkin. Bunday holatlarning matematik ifodalash diskret dasturlash modellariga olib keladi. Umumiy holda

diskret dasturlash masalasi D to„plamda
f (x₁, x₂ ,..., x_n )
maqsad funksiyasining

maksimum (yoki minimum) qiymatini topish sifatida shakllanishi mumkin hamda quyidagi chegaraviy shartlar tizimi bilan aniqlanadi:

^_x  Rⁿ , g (x , x
,..., x
)  0,
i  0 : m^_

d  _
_
i 1 2
n
x  
_, (6.1)
_

bu yerda  - tugallangan yoki sanoqli to„plam.
x  sharti esa diskretlik sharti deb ataladi. Diskret masalalar o„rtasida chiziqli
dasturlashning butun sonli masalasining kanonik shakli alohida o„rin egallaydi.

f (x)  _c_j x _j  max
j 1
(6.2)


D  ^x  Rⁿ




j 1


^ai, j
 x _j
 b_i , i 1: m; x _j
 Z ^ , j 1: n^, (6.3)




bu yerda
Z ^  0,1, 2,... - nomanfiy butun sonlar to„plami.

Eslatib o„tamiz, ba‟zi hollarda “butun sonlilik” ka talab x _j ning ba‟zi bir

o„zgaruvchilariga qo„yilgan bo„ladi. Bu esa masala xarakterini butunlay o„zgartiradi. Natijada masala diskret ko„rinishidagi holga keltiriladi.

Optimallashtirish masalasidagi chegaraviy shartlar tizimida butun sonlik sharti mavjudligi bilan bog„liq qiyinchilik shundan iboratki, ko„pchilik hollarda diskret masalani uning uzluksiz o„xshashi bilan almashtirish va uning komponentlarini eng yaqin butun qiymatga yaxlitlash hamda mos yechimni topish murakkab masala hisoblanadi.

])
^[x1^*] [x₁^*]+1
6.1-rasm
6.1-rasmda keltirilgan misoldan ko„rish mumkinki, oddiy chiziqli dasturlash

masalasida x* optimal rejali butun qiymatlargacha yaxlitlanganda
x^* , x^* 
nuqta

1 2
hosil qilinadi, u nuqta esa D masalasining mumkin bo„lgan rejalar sohasiga

kirmaydi. x _j
sonning butun qismini x  bilan, kasr qismini esa x  bilan belgilashni

j j
shartlashib olamiz. Bunda esa
x  x  x  kelib chiqadi. Shuni alohida ta‟kidlash

j j

j
kerakki, hatto komponentlari qiymatlarini butun songacha yaxlitlangan uzluksiz masalaning optimal rejasi mumkin bo„lgan yechim bo„lsa ham, maqsad funksiyaning qiymati butun sonli masala optimal rejasidan ancha “yomonroq” bo„lishi mumkin.
Sanab o„tilgan muammolar diskret va butun sonli masalalarni yechishning maxsus usullarini ishlab chiqishni talab qiladi. Ushbu masalalarni yechish usullari to„g„risida gapirishdan oldin, diskret dasturlash masalalari tasnifiga batafsil to„xtab o„tamiz. Ko„plab adabiyotlarda, qoidaga ko„ra diskret optimizatsion masalalarning quyidagi turlarini ajratadi:

• 
  bo„linmasliklar masalasi;
  
• 
  ekstremal kombinatorika masalalari;
  
• 
  bo„lingan maqsad funksiyali masalalar;
  

• 
  bog„liq bo„lmagan va noqavariq sohalar masalalari va boshqalar.
  

Bo„linmaslik masalasi. Ko„pchilik hollarda bo„linmaslik sharti modellashtirilayotgan ob‟ektlarning jismoniy xususiyatlari orqali aniqlanadi. Masalan, ular qo„shimcha shartlar sifatida paydo bo„lishi mumkin.
Bu osma xalta ( ryukzak) to„g„risidagi masala hisoblanadi. Uning g„oyasi yetarlicha shartli bo„lib, uningcha sayyoh sayohatga chiqishda W kilogrammdan ortiq yukni olib yura olmaydi. Ushbu yuk n turdagi predmetlar to„plamidan iborat bo„lib,

j turdagi har bir predmet w_j
kilogramm og„irlikka ega va ba‟zi
u _j , j 1: n

“foydalilik” bilan xarakterlanadi. Izohlashgan ushbu holat doirasida tabiiy savol tug„iladi: ryukzakka har bir turdagi predmetlardan qancha joylashtirilsa. Ularning

umumiy foydaliligi eng maksimal bo„ladi? Agar x _j reja komponenti sifatida j

tipdagi joylashtiriladigan predmetlar miqdori qabul qilinsa, u holda masalani quyidagicha yozish mumkin:

f (x)  _u _j  x _j  max
j 1
(6.4)


D  ^x  Rⁿ



^wj j 1
 x _j


 W ;
x  Z ^* , j 1: n^



j

(6.5)

Shuni aytish kerakki, keltirilgan model universal xarakterga ega bo„lib, ko„pgina iqtisodiy masalalarni unga keltirish mumkin.
Kombinator masalalar. Ushbu sinfga n ob‟ektlar tanlamasidan iborat elementlarning chekli to„plamda berilgan funksiyalarini optimallash masalalari kiradi.
Ushbu turga kiruvchi klassik masala vakili bo„lib, kommivoyajer masalasi hisoblanadi. U ba‟zi boshlang„ich punktda mavjud savdo agentining n ta boshqa shaharlarga tashrif buyurishining marshrutini tuzishdan iborat. Bunda bir shahardan boshqasiga borishda quyidagi xarajatlar matritsasi berilgan deb shart qo„yilgan bo„ladi:
^{C  ci, j} (n1)(n1) ^.

Shu bilan birga barcha shaharlarga bir marta tashrif buyurish va dastlabki punktga qaytish mumkin bo„lgan (joiz) marshrut hisoblanadi. Shubhasiz, eng yaxshi marshrut shaharlardan shaharlarga qatnovlarning umumiy xarajatlarini minimallashtirishi lozim.
Masalaning rejasi bo„lib, kommivoyajer marshruti hisoblanadi va uni quyidagi bog„langanlik matritsasi yordamida berish mumkin:

i, j
X  x .
(n1)(n1)

Ushbu matritsaning elementlari quyidagicha aniqlanadi:

^xi, j
_ <sup>1, agar

</sup>0, agar

marshrutda i punktdan j punktga borish ko„zda tutilgan bo„lsa, marshrutda i punktdan j punktga borish ko„zda tutilmagan bo„lsa.

Shu bilan birga masalaning sharti bo„yicha

x_ii  0,
i 1: n

Joiz rejalar bo„lib, tashrif buyurilgan punktlarning bir qiymatli aniqlangan tartibli to„plami bo„lgan bog„lovchi marshrutlar xizmat qiladi:

N(x)  0, i₁ , i₂ , i₃ ,...,i_n , 0.
Bunday har bir marshrutni n raqamlarni o„rniga qo„yish bilan bir-biriga tenglashtirish mumkin. (n bo„yicha n elementlarni tartibli tanlash orqali). O„z navbatida, bunday o„rniga qo„yish Х, u matritsalarga o„zaro qiymatli mos keladi, ularning har bir qatori va har bir ustunida aniq bitta bir mavjud bo„ladi.
Aytilganlarni hisobga olganda kommivoyajer masalasi chiziqli dasturlashning butun sonli masalasiga keltiriladi.
n n

f (x)  _c_ij x_ij  min
i0 j 0
(6.6)

D  x  Rⁿ
x_ij 0; 1, i  0 : n,
j  0 : n
(6.7)

 ^xi, j j 0
 1,
i  0 : n
(6.8)

 ^xi, j i0
 1,
j  0 : n
(6.9)

x_ii  0,
i 1: n
(6.10)

(6.8) va (6.9) shartlar mohiyat nuqtai nazaridan har bir punktga faqat bir marta kirish va bir marta chiqishni anglatadi. Kommivoyajer to„g„risida keltirilgan (6.6)- (6.10) masalaning yozilish shakli eng ratsional hisoblanmaydi va uning diskret dasturlashdagi boshqa masalalar bilan umumiyligini ko„rsatadi. Ushbu muammoning kombinator xarakterini yaxshiroq aks ettiruvchi boshqa shakl ham mavjud

n1
f i₁ , i₂ , i₃ ,...,i_n   C_{0, j1}  _C_ik , C_{ik 1} C_{in ,0}  min
k 1
(6.11)

i₁, i₂ , i₃ ,...,i_n , (6.12)
bu yerda D - 1 dan n gacha bo„lgan sonlarni o„rnini almashtirish to„plami.
Alohida shuni ta‟kidlash lozimki, kommivoyajer masalasi mohiyati o„xshash ko„plab turlarga ega. Aytaylik, o„xshash modelga chiqish masalasini keltirish mumkin. Ushbu masalada turli tipdagi detallarni ishlab chiqarish talab etildi va bir texnologik rejimdagi boshqa rejimga o„tishda ma‟lum xarajatlarni talab qiladi.