I-bob bo’yicha qisqacha xulosa qilib shuni aytish mumkinki

II – BOB. SIMPLEKS USULI VA UNING DASTURIY TA’MINOTI

1. 
   Chiziqli programmalash va simpleks usuli.
   

Matematik programmalash chiziqli programmalash, chiziqli bo’lmagan programmalash va dinamik programmalash deb ataluvchi qismlarni o’z ichiga oladi. Birinchi bo’lib A.N. Tolstoy 1930 yilda mahsulot tashishni optimal planlashtirish masalasini chiziqli programmalash masalasi sifatida ifodalagan. Venger olimi B. Egerveri 1931 yilda «tanlash problemasi» deb atalmish masalani qo’yib, uni yechish usullarini kashf qildi. Bu usul keyinroq «venger usuli» deb atala boshlandi.

Chiziqli programmalash masalalarini sistemalashtirish va ularni yechish uchun umumiy, universal bo’lgan usul yaratish ustida A.V.Kantorovich 1939 yildan boshlab shug’ullana boshlagan. A.V.Kantorovich kashf qilgan usul «hal qiluvchi ko’paytuvchilar usuli» deb ataladi.

A.V.Kantorovich, M.K.Gavurin bilan hamkorlikda 1943 yilda transport masalasi deb ataluvchi chiziqli programmalash masalasini yechish uchun «potenstiallar usuli»ni kashf qildi.

Ko’pgina olimlar o’z faoliyatlarini chiziqli va chiziqli bo’lmagan programmalashning matematik nazariyasini taraqqiy ettirish va matematik usullarni iqtisodiy muammolarni hal qilishga qo’llanishga bag’ishladilar.

Chiziqli programmalash usullarini taraqqiy ettirish muamosi bilan ko’pgina olimlar shuullanganlar. Masalan, amerikalik olim Xichkok 1941 yilda transport masalasining matematik modelini tuzdi, Danstig 1949 yilda chiziqli programmalash masalasini yechish uchun universal usul—simpleks usulni kashf etdi. Chiziqli va chiziqli bo’lmagan programmalash usullari Ford, Falkerson, Kun, Lemke, Gass, Charnes, Bil va boshqa olimlarning ishlarida o’z rivojini topdi.

Hozirgi davrda chiziqli va chiziqli bo’lmagan programmalash usullarini konkret iqtisodiy masalalarni yechishga qo’llash hamda ularni EhM da yechish uchun eng qulay algoritmlar yaratish muammosi bo’yicha ish olib borilmoqda. Shu bilan bir qatorda ko’p olimlarning e’tibori chiziqli bo’lmagan programmalash usullarini taraqqiy ettirishga bag’ishlangan. Bu sohada birinchi marta Kun va Takker 1951 yilda isbotlagan teorema birinchi yutuq bo’lib, unda chiziqli bo’lmagan programmalash masalasining optimal yechimga ega bo’lishining zarur va etarlilik sharti keltirilgan.

Bu ishning amalga oshishi chiziqli bo’lmagan programmalashga oid ko’pgina ilmiy tadqiqotlar uchun turtki bo’ldi. Charnes va Lemke 1954 yilda maqsad funkstiyasi separabel formada va chegaralovchi shartlari chiziqli bo’lgan masala uchun taqribiy yechish yo’lini ko’rsatdilar.

Ayrim chiziqli bo’lmagan programmalash masalalari uchun chiziqli approksimastiya topilib ularni chiziqli programmalash usullarini qo’llab yechish mumkin.

Bazi iqtisodiy jarayonlar vaqtga boliq bo’ladi. Bunday masalalarning turli bosqichlaridagi yechimini aniqlash uchun dinamik programmalash usullari qo’llaniladi. Masalan, planlashtirilayotgan davrning har bir yilida korxonalararo vositalarni optimal taqsimlash masalasi dinamik programmalash masalasiga misol bo’la oladi.

Har qanday iqtisodiy masalani matematik dasturlash usullarini qo’llab yechishdan avval, ularning matematik modelini tuzish kerak; boshqacha aytganda berilgan iqtisodiy masalaning chegaralovchi shartlarini va maqsadini matematik formulalar orqali ifodalab olish kerak. Har qanday masalaning matematik modelini tuzish uchun:

-masalaning iqtisodiy ma`nosini o’rganib, undagi asosiy shart va maqsadni aniqlash;

-masaladagi noma`lumlarni belgilash;

-masalaning shartlarini algebraik tenglamalar yoki tengsizliklar orqali ifodalash;

-masalaning maqsadini funksiya orqali ifodalash kerak.

Misol uchun bir nechta eng sodda iqtisodiy masalalarning matematik modelini tuzish jarayoni bilan tanishamiz.

Faraz qilaylik, korxonada m xil mahsulot ishlab chiqarilsin; ulardan ixtiyoriy birini i (i=1,…,m) bilan belgilaymiz. Bu mahsulotlarni ishlab chiqarish uchun n xil ishlab chiqarish faktorlari zarur bo’lsin. Ulardan ixtiyoriy birini j (j=1,…,n) bilan belgilaymiz.

Har bir ishlab chiqarish faktorining umumiy miqdori va bir birlik mahsulotni ishlab chiqarish uchun sarf qilinadigan normasi quyidagi jadvalda berilgan:

2.1.1-jadval

Masalaning iqtisodiy ma`nosi: korxonaning ishini shunday rejalashtirish kerakki: a) hamma mahsulotlarni ishlab chiqarish uchun sarf qilinadigan har bir ishlab chiqarish faktorining miqdori ularning umumiy miqdoridan oshmasin; b) mahsulotlarni realizatciya qilishdan korxonaning oladigan daromadi maksimal bo’lsin.

Masaladagi b) shart uning maqsadini aniqlaydi. Demak masalaning maqsadi mahsulotlarni realizatciya qilishdan korxonaning oladigan umumiy daromadini maksimallashtirishdan iborat va uni

y = c₁x₁ +c₂x₂+ … + c_mx_m (2.1.3)

chiziqli funksiya orqali ifodalash mumkin. Shartga ko’ra y®max. Bu shartni Y_max ko’rinishda belgilaymiz.

Chiziqli dasturlash masalasi umumiy holda 2.1.1-1.1.3 kabi ifodalanadi.

2.1.1-1.1.2 shartlarni qanoatlantiruvchi noma`lumlarning shunday qiymatlarini topish kerakki, ular (2.1.3) chiziqli funksiyaga minimal (maksimal) qiymat bersin. Masalaning (2.1.1) va (2.1.2) shartlari uning chegaraviy shartlari deb, (2.1.3) chiziqli funksiya esa masalaning maqsadi yoki maqsad funksiyasi deb ataladi.

Masaladagi barcha chegaralovchi shartlar va maqsad funksiya chiziqli ekanligi ko’rinib turibdi. Shuning uchun ham (2.1.1)–(2.1.3) masala chiziqli dasturlash masalasi deb ataladi.

Konkret masalalarda (2.1.1) shart tenglamalar sistemasidan, «і» yoki «Ј» ko’rinishdagi tengsizliklar sistemasidan yoki aralash sistemadan iborat bo’lishi

x_{1 і} 0, x_{2 і} 0, …, x_{n і} 0, (2.1.5)

(2.1.4)-(2.1.6) ko’rinish chiziqli dasturlash masalasining kanonik ko’rinishi deb ataladi. (2.1.4)–(2.1.6) masala vektorlar yordamida quyidagicha ifodalash mumkin:

P₁x₁ + P₂x₂+ … + P_nx_n = P₀ (2.1.7)

X і 0 (2.1.8)

S = (C₁, C₂, …, C_n) – vektor–qator.

X = (X₁, X₂, …, X_n) – vektor–ustun.

(2.1.4)-(2.1.6) masalaning matritca ko’rinishdagi ifodasi quyidagicha yoziladi:

AX = P₀, (2.1.10)

X і 0, (2.1.11)

Y_min = CX, (2.1.12)

bu erda S = (C₁, C₂, …, C_n) – qator vektor, A = (a_ij) – (4) sistema koeffitcientlaridan tashkil topgan matritca; X = (X₁, X₂, …, X_n) va P₀ = (b₁, b₂, …, b_n) – ustun vektorlar.

(2.1.13)

Chiziqli dasturlash masalalarini yechishni simpleks usuli bir tayanch rejasidan boshqa tayanch rejasiga o’tishga asoslangan bo’lib, qaysikim bu yerda maqsad funksiyasini qiymati oshib boradi. Simpleks usulining mohiyati shundan iboratki, dastavval CHDMdagi barcha shartlarni qanoatlantiruvchi mumkin bo’lgan tayanch reja topiladi.

Boshlang’ich tayanch reja chekli sondagi etap (simpleks)dan keyin optimal rejani hosil qilish yo’lini ko’rsatadi va har bir navbatdagi simpleks oldingisiga nisbatan optimal rejaga yaqinroq rejani beradi. Masalani yechish jarayoni optimal yechim topilguncha yoki masalaning maqsad funksiyasi chekli maksimum (minimum)ga ega emasligi aniqlanguncha davom ettiriladi.

Demak, CHDM simpleks usuli bilan yechilganda, berilgan masalaning barcha shartlarini qanoatlantiruvchi boshlang’ich tayanch reja topiladi. Bu boshlang’ich tayanch rejaga asoslanib chekli sondagi simplekslar (bir simpleks jadvalidan, navbatdagi simpleks jadvaliga o’tish) bilan navbatdagi yangi tayanch rejlarni topish va ularning optimalligini tekshirib borish, masalaning optimal yechimga ega ekanligi aniqlanguncha davom ettiriladi.

Simpleks usuli CHDMning quyidagi xossalariga asoslangan:

-agar masala ekstremumga ega bo’lsa u yagona bo’ladi, ya’ni maksimum yoki minimumlardan biri bo’ladi.