Mirzo Ulugʻbek nomidagi Oʻzbekiston Milliy universiteti Jizzax filiali “Amaliy matematika” fakulteti

---

Mirzo Ulugʻbek nomidagi 
Oʻzbekiston Milliy universiteti Jizzax filiali 
 
“Amaliy matematika” fakulteti 
“Amaliy matematika va informatika” kafedrasi
 
“
Oʻyinlar nazariyasi va jarayonlar tadqiqoti
” fanidan 
Mustaqil ishi 
 
Mavzu:
Tarmoqli modellar. 
 
 
Bajardi: 102-19-guruh talabasi Kamolov Xusan 
 
 
 
 
 
 
Jizzax-2023 

---

MAVZU: BUTUN SONLI CHIZIQLI DASTURLASH MODELLARI REJA: 

Chiziqli dasturlash haqida tushuncha 

Butun sonli dasturlash masalasining qo’yilishi va uni yechish usuli

Simpleks usuli 

Chiziqli dasturlash masalasini simpleks usulda yechish bosqichlari 
Matematik dasturlash-ekstremal muammolarni echishning nazariy asoslari va 
usullarini ishlab chiqadigan amaliy matematikaning bo'limi. 
Matematik dasturlash-ekstremal muammolarni echishning nazariy asoslari va 
usullarini ishlab chiqadigan amaliy matematikaning bo'limi. 
Matematik dasturlash bir qancha bo'limlarni o'z ichiga oladi, ularning asosiylari 
quyidagilardir: 
1. Chiziqli dasturlash. Bu bo'lim noma'lum o'zgaruvchilar birinchi darajali 
matematik munosabatlarga kiritilgan masalalarni o'z ichiga oladi. 
2. Chiziqli bo'lmagan dasturlash. Ushbu bo'limda maqsad funktsiyasi va (yoki) 
cheklovlar chiziqli bo'lmagan bo'lishi mumkin bo'lgan muammolarni o'z ichiga 
oladi. 
3. Dinamik dasturlash. Ushbu bo'limda hal qilish jarayoni alohida bosqichlarga 
bo'linishi mumkin bo'lgan vazifalar mavjud. 
4. Butun sonli dasturlash. Ushbu bo'lim noma'lum o'zgaruvchilar faqat butun son 
qiymatlarni qabul qilishi mumkin bo'lgan vazifalarni o'z ichiga oladi. 
5. Stokastik dasturlash. Ushbu bo'lim maqsad funktsiyasi yoki cheklovlardagi 
tasodifiy o'zgaruvchilarni o'z ichiga olgan muammolarni o'z ichiga oladi. 
5. Stokastik dasturlash. Ushbu bo'lim maqsad funktsiyasi yoki cheklovlardagi 
tasodifiy o'zgaruvchilarni o'z ichiga olgan muammolarni o'z ichiga oladi. 
6. Parametrik dasturlash. Ushbu bo'limda maqsad funktsiyasidagi noma'lum 
o'zgaruvchilar koeffitsientlari yoki cheklovlar ba'zi parametrlarga bog'liq bo'lgan 
masalalar kiradi. 
Chiziqli dasturlash- bu matematik dasturlashning eng rivojlangan bo'limi bo'lib, 
uning yordamida chiziqli ulanishlar va cheklovlar bilan ekstremal masalalarni 
tahlil qilish va yechish amalga oshiriladi. 
Chiziqli dasturlash modelini yozishning standart shakli chiziqli tenglamalar 
tizimida yozilgan kanonik shaklda, ya'ni chiziqli tenglik shaklida, manfiy 
bo'lmagan sonlarda: 

---

(1) 
Chiziqli dasturlash masalasini echishning standart shakli maqsad funktsiyasini 
minimallashtiradigan manfiy bo'lmagan sonlardagi chiziqli tenglamalar tizimining 
yechimlarini topishdir. Bunday holda, maqsad funktsiyasi quyidagi shaklga ega: 
(3) 
Optimal yechim - bu maqsad funktsiyasini (3) maksimallashtirish (yoki 
minimallashtirish) mumkin bo'lgan yechimdir. 
Butun sonli dasturlash masalasining qo’yilishi va uni yechish usuli
Butun sonli dasturlash masalasining qo’yilishi va uni yechish usuli
Ma’lumki, iqtisodning ko’p masalalarini yechish, butun sonli yechimni toppish 
bilan bog’liq. Bunday masalalarda yechimning butun son bo’lishi talab etiladi. 
Masalan, korxonalar orasida mahsulot ishlab chiqarish topshiriqlari, buyumlar 
bichish, kemalar ishlab chiqarish, samolyotlarni reyslarga taqsimlash va hokazo. 
Bunday misollarni ko’plab keltirish mumkin. Butun sonli dasturlash masalasi 
chiziqli dasturlash masalasidan qo‘shimcha shartlar bilan farq qiladi. Bu 
shartlarning qatnashishi butun sonli dasturlash masalasini yechish jarayonini 
qiyinlashtiradi. Natijada chiziqli dasturlash masalalarini yechish uchun 
qo‘llaniladigan usullarni butun sonli dasturlash masalalariga qo‘llash mumkin 
bo‘lmay qoladi. 
Gomori usuli. Butun sonli dasturlash masalalarini yechish uchun uning 
xususiyatlarini e'tiborga oluvchi usullar yaratilgan bo‘lib, ulardan amerikalik olim 
R.Gomori yaratgan usul optimal yechimni beruvchi eng aniq usul hisoblanadi. Bu 
usulning g‘oyasi quyidagidan iborat. Berilgan butun sonli dasturlash masalasida 
noma'lumlarning butun bo‘lishlik shartiga e'tibor bermasdan, ularni oddiy chiziqli 
dasturlash masalasi sifatida simpleks usuldan foydalanib yechamiz.
Gomori usuli. Butun sonli dasturlash masalalarini yechish uchun uning 
xususiyatlarini e'tiborga oluvchi usullar yaratilgan bo‘lib, ulardan amerikalik olim 
R.Gomori yaratgan usul optimal yechimni beruvchi eng aniq usul hisoblanadi. Bu 
usulning g‘oyasi quyidagidan iborat. Berilgan butun sonli dasturlash masalasida 
noma'lumlarning butun bo‘lishlik shartiga e'tibor bermasdan, ularni oddiy chiziqli 
dasturlash masalasi sifatida simpleks usuldan foydalanib yechamiz.
Agar yechim butun sonlardan iborat bo‘lsa, u butun sonli dasturlash masalasining 
ham yechimi bo‘ladi. Aks holda noma'lumlarning butun bo‘lishlik shartini 
e'tiborga oluvchi va "kesuvchi tenglama" deb ataluvchi qo‘shimcha tenglama 
tuziladi. 
Kesuvchi tenglamani tuzish.

---

Kesuvchi tenglamani tuzish.
1.Aytaylik, masaladagi sonlarning butun bo‘lishlik sharti tashlab yuborishdan hosil 
bo‘ladigan masala yechilgan va uning optimal yechimi mavjud bo‘lsin. Agar 
barcha x lar butun sonlar bo‘lsa, topilgan yechim butun sonli dasturlash 
masalaning yechimi bo‘ladi.
2.Faraz qilaylik, ba'zi x lar kasr sonlardan iborat bo‘lsin, ya'ni simpleks jadvaldagi 
ozod hadlar ustuni qiymatlari ichida kasr sonlar ham mavjud bo‘lsin. Ularning 
butun kismlarini [x] bilan belgilaymiz. U holda bu sonlarning kasr qismlari q lar 
quyidagicha aniqlanadi: