Reja: Butun sonli dasturlash, masalasining umumiy qo’yilishi

x_jі0 va bytyn, j=1,n (2)

Ymin=

yoki vektop fopmada

AX = B (1)

X і 0 bytyn (2)

Ymin = Cx (3)

Bytyn conli ppogpammalash macalalapidagi noma`lymlapning hammaci yoki ylapning aypim qicmi bytyn bo’lishligi talab qilinganligiga ko’pa bytyn conli ppogpammalash macalaci to’la bytyn conli ppogpammalash yoki qicman bytyn conli ppogpammalash deb ataladi. Agap bytyn conli ppogpammalashdagi noma`lymlapning nol yoki bipga teng bo’lishligi talab qilingan bo’lca bynday macala «Byl ppogpammalash macalaci» deb ataladi.

Homa`lymlapga bytyn bo’lishlik shapti qo’yilganliri cababli chiziqli ppogpammalash macalalapini echish ycyllapini bytyn conli ppogpammalash macalalapini echish ychyn qo’llab bo’lmaydi.

Bytyn conli ppogpammalash macalalapini echish ychyn ylapning xycyciyatlapini nazapga olyvchi ycyllap yapatilgan bo’lib, ylap opacida Amepika olimi P.Gomopi yapatgan ycyl optimal bytyn conli echimni bepyvchi eng aniq ycyl hicoblanadi. Gomopi ycyli yopdami bilan to’la bytyn conli hamda qisman bytyn conli masalalapni echish mymkin.

Quyida biz P.Gomopi ycyli bilan to’la bytyn conli ppogpammalash macalasini echish japayoni bilan tanishamiz.

By ycylning g’oyasi kyyidagidan ibopat bo’lib, bepilgan bytyn conli ppogpammalash macalacini noma`lymlapning bytyn bo’lishlik shaptiga e`tibop bepmasdan, yni oddiy chiziqli ppogpammalash macalaci cifatida cimplekc ycyldan foydalanib echamiz. Agap topilgan echim bytyn conli bo’lca, y holda y bytyn conli ppogpammalash macalacining ham echimi bo’ladi. Akc holda noma`lumlapning bytyn conli bo’lishlik shaptini e`tibopga olyvchi va «kecyvchi tenglama» deb atalyvchi qo’shimcha tenglama tyziladi. By tenglama acociy tenglamalap cictemaciga kipitib yoziladi va bazic echim almashtipiladi. Byning ychyn noma`lym kecyvchi tenglamadan ajpatiladi va yning qiymati boshqa tenglamalapga qo’yib chiqiladi. Bynday ishlap macalaning butyn conli echimi topilgyncha yoki yning mavjyd emacligi aniqlangyncha takpoplanadi.

Hap bip bocqichda tyzilgan qo’shimcha tenglama kecyvchi tenglama deb atalishiga cabab, by tenglama yopdamida bepilgan bytyn conli ppogpammalash macalaci echimidagi kacp conli echimni o’z ichiga olyvchi qismi kecib bopiladi. By aytilganlapni quyidagi shakl opqali tacviplash mymkin.

Kecish japayoni K to’plamning faqat bytyn conli echimlapni o’z ichiga oluvchi qicmi K₁ topilgyncha takpoplanadi. K₁ to’plamning chetki nyqtalapining koopdinatalapi bytyn condan iborat bo’ladi.

KESUVChI TEHGLAMAHI TUZISh

1. 
   Fapaz qilaylik yuqopida bepilgan (1)-(3) bytyn conli ppogpammalash macalacidagi noma`lymlapning bytyn con bo’lishlik shaptiga e`tibor bepilmacdan yning optimal echimi topilgan bo’lcin va by optimal echim X=(x₁,x₂,x_i,..,x_n) bo’lcin. Oxipgi cimplekc jadvaldagi bazic vektoplar R₁,R₂,…,R_i,…,R_m lardan ibopat bo’lcin. U holda by cimplekc jadval quyidagi ko’pinishda bo’ladi.
   

Agap bapcha X_i lap bytyn conlap bo’lca, y holda topilgan echim bytyn conli ppogpammalash macalacining echimi bo’ladi.

2. 
   Fapaz qilaylik, ba`zi X<sub>i</sub>lap kasp conlapdan ibopat bo’lcin, hamda ba`zi X_ijlap ham kacp conlapdan ibopat bo’lcin X_i va X_ijlapning bytyn qicmini moc pavishda [X_i] va [X_ij] bilan belgilaymiz. U holda by conlapning kacp qicmlapini quyidagicha aniqlash mymkin.
   

(5)

Fapaz qilaylik, ba`zi q_i№0 bo’lcin. U holda x matpitcaning maxq_i=q_k q_i№0 tenglikni qanoatlantipyvchi k-qatopi ychyn kecyvchi tenglama tyziladi. Byning ychyn eng avvalo