Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand

Chiziqli dasturlashning asosiy teoremalari. 
Chiziqli dasturiy muammolarni echish usullarini asoslash uchun ularning analitik isbotlarini 
hisobga olmagan holda bir qator muhim teoremalarni tuzamiz. Har bir teoremaning ma'nosini 
tushuntirish oldingi kichik bo'limda berilgan ZLP masalasini geometrik izohlash tushunchasiga 
yordam beradi. 
Ammo, birinchi navbatda, kelgusida muhokama qilish uchun muhim bo'lgan ba'zi tushunchalarni 
eslaymiz. 

---

Agar n o'zgaruvchisi (m agar koeffitsientlar matritsasini aniqlovchi nolga teng bo'lmasa, asosiy deyiladi. Keyin qolgan m-
n o'zgaruvchilar asosiy bo'lmagan (yoki bepul) deb nomlanadi. 
N o'zgaruvchilar (m bo'lmagan o'zgaruvchilar nol qiymatga ega bo'lgan har qanday echimdir. Teorem 1. Chiziqli 
dasturlash muammosini cheklash tizimining barcha ruxsat etilgan echimlari to'plami qavariqdir. 
Maxsus holatda, cheklash tizimiga x1 va x2 ikkita o'zgaruvchilar kiritilgan bo'lsa, ushbu to'plam 
tekislikda ko'rsatilishi mumkin. Mumkin echimlar (x1, x2 ≥ 0) haqida gaplashayotganimiz 
sababli, tegishli to'plam Karteziya koordinatalari tizimining birinchi choragida joylashgan 
bo'ladi. Ushbu to'plam yopiq (ko'pburchak), ochiq (cheksiz ko'pburchak maydon) bo'lishi 
mumkin, bitta nuqtadan iborat va nihoyat, cheklash-tengsizlik tizimi qarama-qarshi bo'lishi 
mumkin. 
Teorema 2. Agar chiziqli dasturlash masalasi eng maqbul echimga ega bo'lsa, u mumkin bo'lgan 
echimlar to'plamining burchak nuqtalarining bittasiga (ikkitasiga) to'g'ri keladi. 2-teoremadan biz 
optimal echimning o'ziga xosligi buzilishi mumkin, degan xulosaga kelishimiz mumkin va agar 
echim noyob bo'lmasa, bunday son-sanoqsiz optimal echimlar (tegishli burchak nuqtalarini 
bog'laydigan segmentning barcha nuqtalari) bo'ladi. 
Teorema 3. Chiziqli dasturlash muammosining har bir qabul qilinadigan asosiy echimi uchun 
qabul qilinadigan echimlar sohasining burchak nuqtasi mos keladi va aksincha. 
2 va 3-teoremalarning natijasi, cheklash tenglamalari yordamida berilgan (yoki qisqartirilgan) 
chiziqli dasturlash masalasining eng maqbul echimi (optimal echimlar) cheklash tizimining 
ruxsat etilgan asosiy echimi (qabul qilinadigan asosiy echimlar) bilan mos tushadi. 
Shunday qilib, ZLPning optimal echimini cheklangan sonli mumkin bo'lgan asosiy echimlar 
orasida izlash kerak. Ishlab chiqarishni rejalashtirishda resurslardan optimal foydalanish 
Ushbu sinf vazifalarining umumiy ma'nosi quyidagicha. 
Kompaniya n turli xil mahsulotlarni ishlab chiqaradi. Ularni ishlab chiqarish uchun har xil 
turdagi resurslar (xom ashyo, materiallar, ish vaqti va boshqalar) talab qilinadi. Resurslar 
cheklangan, rejalashtirish davrida ularning zaxiralari mos ravishda b1, b2, ..., bm shartli 
birliklardir. 
Aij texnologik koeffitsientlari ham ma'lum, ular jth tipidagi mahsulotning birligini ishlab 
chiqarish uchun qancha itr manbadan zarur bo'lganligini ko'rsatadi. 
Kompaniya tomonidan j-chi turdagi mahsulotlarni sotishda olingan foyda cj ga teng. 
Rejalashtirish davrida aij, bi va cj qiymatlari doimiy bo'lib qoladi. Bunday ishlab chiqarish 
rejasini tuzish kerak, uni amalga oshirishda kompaniyaning foydasi katta bo'ladi. Keyingi, biz 
ushbu sinfning vazifasiga oddiy misol keltiramiz. Kompaniya xokkey tayoqchalari va shaxmat 
anjomlari ishlab chiqarishga ixtisoslashgan. Har bir klub kompaniyaga $ 2, har bir shaxmat 
to'plamiga $ 4 foyda keltiradi. Bir tayoqni ishlab chiqarish uchun A bo'limida to'rt soat va B 
bo'limida ikki soat ishlash kerak. Shaxmat to'plami A bo'limida olti soat, B bo'limida olti soat va 
S bo'limida bir soat sarflanadi. A qismning mavjud ishlab chiqarish hajmi 120 n. kuniga soat, B 
sektsiyasi - 72 n-soat va C qismi - 10 n-soat. 
Daromadni ko'paytirish uchun kompaniya har kuni qancha klub va shaxmat to'plamlarini ishlab 
chiqarishi kerak? Ushbu sinfning vazifalari uchun shartlar ko'pincha jadval shaklida keltirilgan 
(1-jadvalga qarang). 
1-jadval 

---

Chiziqli dasturlash usullari. Iqtisodiyotda ko'pincha duch keladigan ko'plab ekstremal 
muammolarni hal qilish uchun chiziqli dasturlash usullaridan foydalaniladi. Bunday 
muammolarni hal qilish ba'zi o'zgaruvchilar funktsiyalarining haddan tashqari qiymatlarini 
(maksimal va minimal) topish uchun kamayadi. 
Chiziqli dasturlash o'rganilayotgan hodisalar o'rtasidagi bog'liqlik mutlaqo funktsional 
bo'lganda, chiziqli tenglamalar tizimini (tenglamalar va tengsizliklarga o'tish bilan) echishga 
asoslangan. U o'zgaruvchilarning matematik ifodasi, ma'lum bir tartib, hisoblar ketma-ketligi 
(algoritm), mantiqiy tahlil bilan tavsiflanadi.
U faqat o'rganilgan o'zgaruvchilar va omillar matematik aniqlik va miqdoriy cheklovga ega 
bo'lgan holatlarda, hisob-kitoblarning ma'lum ketma-ketligi omillarning o'zaro bir-biriga mos 
kelishiga olib kelganda, hisoblardagi mantiq, matematik mantiq o'rganilayotgan hodisaning 
mohiyatini mantiqiy asosli tushunish bilan birlashtirilganda qo'llanila. Ushbu usulni sanoat 
ishlab chiqarishda qo'llash, masalan, mashinalarning, yig'ishmalarning, ishlab chiqarish 
liniyalarining (mahsulotlarning ushbu assortimenti va boshqa belgilangan qiymatlar uchun) 
maqbul jami mahsuldorligi hisoblanadi, materiallarni oqilona kesish muammosi (ish 
qismlarining maqbul rentabelligi bilan) hal qilinadi. 
Chiziqli dasturlash yordamida hal qilingan barcha iqtisodiy muammolar muqobil echimlar va 
ma'lum cheklov shartlari bilan ajralib turadi. Bunday muammoni hal qilish uchun barcha 
mumkin bo'lgan (alternativ) variantlardan eng yaxshisini, optimalini tanlash kerak. Iqtisodiyotda 
chiziqli dasturlash usulidan foydalanishning ahamiyati va ahamiyati shundaki, maqbul variant 
juda ko'p sonli alternativ variantlardan tanlanadi. Bunday muammolarni hal qilish uchun boshqa 
usullardan foydalanish deyarli mumkin emas.