T. I. Umarov s. I. Xudoyberdiyev iqtisodiy matematik usullar va

J =1

^XJ ^ ^ ⁽J = ^v.^ⁿ⁾ shartlarni qanoatlantiruvchi

minimal yechimini topish kerak bo’ladi.

Chiziqli dasturlash masalasi yechimlar ko’pburchagiga ega (2- chizma) bo’lsin.

Masalaga, butun sonli yechimni topish talabini qo’ysak, yechimlar to’plami, yakkalangan butun sonlar majmuidan iborat bo’lib qavariq to’plam bo’lmaydi.


x.
lar butun,



Chetki butun sonli nuqtalarni tutashtirib, hamda koordinat-lar o’qi yordamida yangi kontur hosil qilamiz.

2-chizma.

Bu holda ushbu xossalarga ega chiziqli programmalash masalasini hosil qilamiz:

1. 
   
   yangi yechimlar ko’pburchagi butun sonli nuqtalarga ega bo’lib, boshlang’ich masala yechimlar ko’pburchagi bilan chegaralangan; yangi ko’pburchakning hamma burchak nuqtalari butun sonli;
   
2. 
   
   chiziqli funksiya yechimlar ko’pburchagining burchak nuqtalarida optimumga erishganligi uchun, bunday yechimlar ko’pburchagini yasash bilan butun sonli programmalash masalasi yechilgan bo’ladi.
   

Bunday yechish usuli Gomori tomonidan taklif qilingan bo’lib simpleks- metodga (usulga) asoslangan. Bunda, butun sonli talabga e’tibor bermasdan masala simpleks-usul bilan yechiladi. Olingan optimal yechim butun sonli bo’lsa, masala yechilgan bo’ladi. Optimal yechim ichida hech bo’lmaganda xi bitta kasr sonli komponentga ega bo’lsa, bu komponet butun sonli bo’lishini hisobga olingan qo’shimcha talab qo’yiladi va masalani yechish simpleks usul bilan yangi optimal yechimni topishgacha davom ettiriladi. Keyingi optimal yechim ham butun sonli bo’lmasa, navbatdagi qo’shimcha shart qo’yiladi va jarayon butun sonli yechimni olgungacha davom ettiriladi yoki butun sonli yechimga ega emasligi isbotlanadi. Bu х_г kasr son bo’lib x_v satrdagi hamma

sonlar butun bo’lib qolsa o’rinli bo’ladi.

Endi qo’shimcha shartlarni tuzishga o’tamiz. X = (x₁, x₂,...,x_i,..., x_m,...,x_n) optimal yechim A₁, A₂,..., A_i,..., A_m bazisda olingan bo’lsin. Bu holda oxirgi simpleks jadval quyidagicha bo’ladi:

x.

x

1n

x₂ 0 1 ... 0 ... 0 x

x

x

2 j

2n

x 1 0 ... 0 ... 0 ^xi,m+1

2, m+1

X =