Њзбекистон республикаси олий ва њрта махсус

f_i (x_i ) = с_i x_i
Bundan tashqari, n-ta punktda bu mahsulot iste‟mol qilinadi. Har bir iste‟mol

qiluvchi punktning mahsulotga bo„lgan talabi mos ravishda b₁,b₂ ,...,b_n
birliklarni

tashkil qiladi deb faraz qilamiz. Har bir A_i ishlab chiqaruvchi punkt bilan bog„langan va transport xarajatlarining matritsasi C  (c_ij ) dan iborat bo„lsin.
A_i punktdan j punktga yuboriladigan mahsulot miqdorini x_ij bilan belgilaymiz.
U holda masalaning matematik modeli quyidagicha ifodalanadi:

_ x_ij  x_i , (i  1, m)
j1
(7.5)

x_ij  0



_ x_ij  b_j , ( j  1, n)
i1


x_i - бутунсон
(7.6)

(7.7)

n n
y  _ –_i x_i _ –_ij x_ij  min (7.8)
i1 i1
Chiziqli dasturlash masalasidan ana shunday shartlar bilan farq qiladigan masalalarni butun sonli dasturlash masalasi deb ataymiz.
Butun sonli dasturlash masalasini umumiy holda quyidagi ko„rinishda ifodalash mumkin:

_€_ij x _j  b_i , ( j  1, m)
i1
(7.9)

x_ij  0
x_i  бутун
сон,
j 1, n
(7.10)

^ymin		n   –i xi		(7.11)
yoki vektor formada
	AХ=b		(7.12)
	X0 va butun,		(7.13)
	ymin=CX		(7.14)

i1

Butun sonli dasturlash masalalaridagi noma‟lumlarning hammasi uchun butun bo„lishlik sharti qo„yilsa, bunday masalalar to„liq butun sonli dasturlash masalalari, agar ularning ma‟lum bir qismi uchungina bu shartlar qo„yilsa, qisman butun sonli dasturlash masalalari deb ataladi. Agar butun sonli dasturlash masalalaridagi noma‟lumlarda (7.3) ko„rinishdagi shartlar qo„yilgan bo„lsa, bunday masala Bul dasturlash masalasi deb ataladi.
Butun sonli dasturlash masalasi chiziqli dasturlash masalasidan qo„shimcha (7.3) yoki (7.10) ko„rinishdagi shartlar bilan farq qiladi. Bu shartlarning qatnashishi butun sonli dasturlash masalasini yechish jarayonini qiyinlashtiradi. Natijada chiziqli dasturlash masalalarini yechish uchun qo„llaniladigan usullarni butun sonli dasturlash masalalariga qo„llash mumkin bo„lmay qoladi.
Butun sonli dasturlash masalalarini yechish uchun uning xususiyatlarini e‟tiborga oluvchi usullar yaratilgan bo„lib, ulardan amerika olimi R.Gomori yaratgan usul optimal yechimni beruvchi eng aniq usul hisoblanadi.
Bu usulning g„oyasi quyidagidan iborat. Berilgan butun sonli dasturlash masalasida noma‟lumlarning butun bo„lishlik shartiga e‟tibor bermasdan, ularni oddiy chiziqli dasturlash masalasi sifatida simpleks usuldan foydalanib yechamiz.
Agar yechim butun sonlardan iborat bo„lsa, u butun sonli dasturlash masalasining ham yechimi bo„ladi. Aks holda noma‟lumlarning butun bo„lishlik shartini e‟tiborga oluvchi va «kesuvchi tenglama» deb ataluvchi qo„shimcha tenglama tuziladi. Bu tenglama asosiy tenglamalar sistemasiga kiritib yoziladi va bazis yechim almashtiriladi. Buning uchun noma‟lumni kesuvchi tenglamadan ajratiladi va uning qiymatini boshqa tenglamalarga qo„yib chiqiladi. Bunday ishlar masalaning butun sonli yechimi topilguncha yoki uning mavjud emasligi aniqlanguncha takrorlanadi. Har bir siklda tuzilgan qo„shimcha tenglama kesuvchi tenglama deb atalishiga sabab, bu tenglama yordamida berilgan masalaning rejalaridan tashkil topgan K qavariq to„plamning kasr sonli rejalarini o„z ichiga olgan qismini kesib boriladi. Kesish jarayoni K to„plamning faqat butun sonli rejalarni o„z ichiga olgan qismi topilguncha yoki bunday qism mavjud emasligi aniqlanguncha takrorlanadi.