«Kompyuter injiniringi» fakulteti «Kompyuter injiniringi» baǵdarı II kurs 301-20 topar studenti Xojamuratova Umidanıń

ÓZBEKSTAN RESPUBLIKASÍ
INFORMACIYALÍQ TEXNOLOGIYALARÍ HÁM KOMMUNIKACIYALARÍN RAWAJLANDÍRÍW MINISTRLIGI

MUXAMMED AL-XOREZMIY ATINDAǴÍ
TASHKENT INFORMACIYALÍQ TEXNOLOGIYALARÍ UNIVERSITETI NÓKIS FILIALÍ


« Kompyuter injiniringi » fakulteti
«Kompyuter injiniringi» baǵdarı
II kurs 301-20 topar studenti
Xojamuratova Umidanıń

« ALGORITIM PROEKTLESTIRIW »
páninen

ÓZ BETINSHE JUMISI

Tayarlaǵan _________________ U.Xojamuratova
Qabıllaǵan _________________ D.Seytniyazov

Nókis – 2022
Tema: Sızıqlı programmalastırıw máselesi. Máseleniń matematikalıq modeli, ekonomikalıq analizi.
Sızıqlı programmalastırıw matematikada XX ásirdiń birinshi yarımında payda etilgen zárúrli jańa jónelis bolıp, ol ekonomikalıq máselelerdi sheshiwge matematikalıq usıllardıń saldamlı qollanılıwı nátiyjesi bolıp tabıladı. ChD járdeminde standart bolmaǵan máselelerge alıp keletuǵın ekonomikalıq máseleler utıs penen sheshiledi.
Sızıqlı programmalastırıw matematikalıq programmalastırıwdıń bóleginen ibarat. Matematikalıq programmalastırıw sızıqlı hám sızıqsız teńlikler hám de teńsizlikler menen berilgen jıynaqlarda anıqlanǵan funksiyalardıń ekstremumların (jergilikli minimum hám jergilikli maksimumların), ekstremal bahaların (eń kishi hám eń úlken bahaların ) tabıw teoriyası hám usılların úyrenedi.
Matematikalıq programmalastırıwdıń tiykarǵı bólimleri tómendegilerden ibarat :
1. Sızıqlı programmalastırıw (SD).
2. Sızıqsız programmalastırıw (SZD).
3. Qabarıq programmalastırıw (QD).
4. Sanlı usıllar (máselelerdi sheshiwdiń ámeliy usılları ).
Kóplegen ekonomikalıq máseleler sızıqlı programmalastırıw máselelerin sheshiwge alıp keledi. Biz SD máseleleri menen qısqasha tanısamız. Usınıń menen birge Dansig tárepinen usınıs etilgen simpleks-usıl hám bir qatar basqa usıllar menen shuǵıllanamız.
Sızıqlı programmalastırıw sızıqlı munasibetler (sızıqlı teńlik hám sızıqlı teńsizlikler) menen berilgen jıynaqta anıqlanǵan sızıqlı funksiyanıń (maqset funksiyasınıń ) ekstremal (eń kishi hám eń úlken) bahaların tabıw teoriyası hám usılların úyrenedi, bunda erkli ózgeriwshiler tek teris emes bahalar qabıl etedi.
XX ásirdiń 30 -jıllarında orıs matematigi L. V. Kantorovich tábiy resurslardan optimal paydalanıw sıyaqlı ekonomikalıq másele menen saldamlı shuǵıllana basladı hám SD máseleleriniń qollanılıwın anıqladı. 1975-jılda oǵan hám AQSH alımı Kupmansqa “Tábiy resurslardan optimal paydalanıw”ģa tiyisli qatar ilimiy jumısları ushın xalıq aralıq Nobel sıylıqı berilgen. XX ásirdiń 40 -jıllarında AQSH alımı Dj. Dansig SDnıń kanonik máselesi dep júritiletuǵın máselesin sheshiwdiń ájayıp usılı— simpleks-usılın jarattı. Sol usıl jáne onıń túrli máselelerdi sheshiwge maslastırılǵan kórinisleri dúnyaǵa keń tarqaldı.
SDnıń eki máselesi bar.
1. SDnıń kanonik kórinistegi máselesi (kanonik másele).
2. SDnıń normal kórinistegi máselesi (normal másele).
Kanonik másele tómendegishe qoyıladı :
 c_lx_l +c₂x₂ +... + c_n x_n—> max (min),
 a₁₁x₁+a₁₂x₂+... + a_1nx_n=b₁,
 a₂₁x₁ +a₂₂x₂+... + a_2n x_n = b₂,
 -----------------------------------
a_k1x₁+a_k2x₂+... + a_knx_n=b_k,
 x₁ ≥ 0, x₂ ≥ 0,... ,x_n ≥ 0, к < n. (1)

Sol másele vektor -matritsalı kóriniste tómendegishe jazıladı :

(2)
Normal máseleni da vektor -matritsali kóriniste jazamız :
(3)
Joqarıda tómendegi belgilewlerden paydalanıldı:
C= , x= , b= , A= = (4)

Hár bir (K) hám (N) másele k
Maqset funksiyası óziniń optimal ma`nisine sheshimler kόpmúyeshiniń shegara noqatlarında erisedi. Sızıqlı programmalastırıw máselesin grafik usılda tarqatıp alıw tómendegi tártipte atqarıladı :
1) Berilgen máseledegi teńsizliklerge uyqas teńlemelerdi dúzemiz hám olardı uyqas
Túrde:
a₁₁x₁+a₁₂x₂ =a₁ (L₁)
a₂₁x₁ +a₂₂x₂=a₂ (L₂)
…………………….
a_k1x₁+a_k2x₂=a_n (L_n)
x₁=0 (L_m+1)
x₂=0 (L_m+2) (5)
penen belgileymiz.
2) (L₁ ), (L₂ ),  , (L_m+2 ) teńlemeler menen berilgen sızıqlardı X₁OX₂ koordinatalar tegisliginde ańlatpalaymız (1-súwret).

1-súwret
3) (1) de berilgen teńsizliklerge uyqas yarım tegisliklerdi anıqlaymız (2 - súwret).
2-súwret
Suwrettegi hár bir tuwrı sızıq grafigine qoyılǵan strelkalar (1) teńsizliklerge uyqas yarım tegisliklerdi anıqlaydı.
4) Yarım tegisliklerdiń kesilispesin qaraymız. Eger kesilispe kόpmúyeshten ibarat bolsa, máseleniń sheshimi shekli bahaǵa iye boladı. Bul kόpmúyesh sheshimler kόpmúyeshi bolıp, onıń qálegen noqatı berilgen (1) teńsizlikler sistemasın qánaatlantıradı (3-súwret)

3-súwret
Eger kesilispe bos jıynaq bolsa, másele sheshimge iye bolmaydı (4-súwret).


4-súwret
Kesilispe bos jıynaq bolmaǵan halda máseleniń optimal sheshimin tabıw ushın ózgeriwshilerdiń sonday bahaların tabıw kerek, bul bahalarda z maqset funksiyası eń úlken (eń kishi) bahaǵa erissin. Bunday bahalar sheshimler kόpmúyeshiniń shegaralıq noqatlarında boladı. Eger optimal sheshim kόpmúyeshtiń bir ushında bolsa, sheshim birden-bir boladı, keri jaǵdayda másele sheksiz kóp sheshimge iye bolıp, olar kόpmúyeshtiń optimal sheshim qabıl etetuǵın ushlarınıń sızıqlı kombinatsiyalarınan ibarat boladı.