Chiziqli dasturlashning asosiy teoremalari

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 o'zgaruvchisi, 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 barcha asosiy 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.
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.
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.