Butun sonli dasturlash masalasining qo’yilishi. Shoxlar va chegaralar usuli

Reja:
1. Butun sonli dasturlash masalasining qo’yilishi.Shoxlar va chegaralar usuli.

2.Transport masalasi

3. Chiziqli dasturlashda optimallashtirish masalasi

Butun sonli dasturlash va uni yechish usuli
O‘zgaruvchilarga butun sonli bo‘lishlik sharti qo‘yilgan chiziqli dasturlash masalalariga butun sonli dasturlash masalasi deyiladi. Butun sonli dasturlash masalalariga sayyoh haqidagi masala, optimal jadval tuzish, transport vositalarini marshrutlashni optimallash, optimal joylashtirish masalasi va hokazolarni misol qilish mumkin.
Butun sonli dasturlash masalasi chiziqli dasturlash masalasidan qo‘shimcha 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.
Gomori usuli. Butun sonli dasturlash masalalarini yechish uchun uning xususiyatlarini e'tiborga oluvchi usullar yaratilgan bo‘lib, ulardan amerikalik olim 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.


Kesuvchi tenglamani tuzish.
1.Aytaylik, masaladagi sonlarning butun bo‘lishlik sharti tashlab yuborishdan hosil bo‘ladigan masala yechilgan va uning optimal yechimi mavjud bo‘lsin. Agar barcha x lar butun sonlar bo‘lsa, topilgan yechim butun sonli dasturlash masalaning yechimi bo‘ladi.
2.Faraz qilaylik, ba'zi x lar kasr sonlardan iborat bo‘lsin, ya'ni simpleks jadvaldagi ozod hadlar ustuni qiymatlari ichida kasr sonlar ham mavjud bo‘lsin. Ularning butun kismlarini [x] bilan belgilaymiz. U holda bu sonlarning kasr qismlari q lar quyidagicha aniqlanadi:
q_i=x_i-[x_i], q_ij=a_ij-[a_ij].
Faraz qilaylik, ba'zi q_i≠0 bo‘lsin. U holda, simpleks jadvalning tenglikni qanoatlantiruvchi k qatori uchun kesuvchi tenglama tuziladi. Buning uchun avval
q_k1x₁+ q_k2x₂+ …+ q_knx_n≥q_k
tengsizlik tuziladi, so‘ngra uni (-1) ga ko‘paytirib, x_n+1 qo‘shimcha o‘zgaruvchi kiritiladi.
-q_k1x₁- q_k2x₂- …- q_knx_n + x_n+1=q_k .
Bunday tuzilgan tenglama kesuvchi tenglama deyiladi.
3.Kesuvchi tenglamani simpleks jadvalning m+2 qatoriga joylashtiramiz va simpleks almashtirishlarni bajaramiz.
Agar hosil bo‘lgan yangi simpleks jadvalda barcha x_i lar butun sonli (ya'ni hamma q_i=x_i-[x_i]=0) bo‘lsa, topilgan yechim berilgan butun sonli dasturlash masalasining yechimi bo‘ladi. Aks holda yuqoridagi 2 va 3 punktlar yana takrorlanadi. Umuman bu jarayon masalaning butun sonli yechimi topulguncha yoki masalaning butun sonli yechimi mavjud emasligi aniqlanguncha takrorlanadi.
Misol. quyidagi chiziqli dasturlash masalasining butun sonli yechimini toping.

Masalani normal holga keltiramiz:

Masalani simpleks usulda yechamiz.

1.

BO‘	1	-x1	-x2
x3	6	2	3
x4	3	2	-3
Z	8	3	1

2.

BO‘	1	-x4	-x2		BO‘	1	-x4	-x3
x3	3	-1	6		x2	0.5	-0.17	0.17
x1	1.5	0.5	-1.5		x1	2.25	0.25	0.25
Z	3.5	-1.5	5.5		Z	0.75	-0.58	-0.92

Shunday qilib masalaning optimal plani topildi, lekin bu plan butun sonli emas. Birinchi tenglamaning kasr qismi eng katta bo‘lgani uchun, shu birinchi qatorga nisbatan kesuvchi tenglama tuzamiz:

Bu tengsizlikning ikki tomoniga (-1) ni ko‘paytirib, x₅ qo‘shimcha o‘zgaruvchini kiritamiz. Natijada quyidagiga ega bo‘lamiz:
, ya'ni
Bu oxirgi tenglamada barcha koeffitsientlarning butun qismlari nolga teng bo‘lgani sabab, ular o‘zgarishsiz qoladi. Uni jadvalning oxiriga joylashtiramiz.
4.

BO‘	1	-x4	-x3
x2	0.5	-0.17	0.17
x1	2.25	0.25	0.25
x5	-0.5	0.17	-0.17
Z	0.75	-0.58	-0.92

Simpleks almashtirish qilib quyidagi jadvalga ega bo‘lamiz.

BO‘	1	-x4	-x5
x2	0.0	0.0	1.0
x1	1.5	0.5	1.5
x3	3.0	-1.0	-6.0
Z	3.5	-1.5	-5.5

Endi simpleks jadvalning ikkinchi qatoriga nisbatan kesuvchi tenglamani tuzamiz.
Bu tengsizlikda koeffitsientlar butun qismi noldan katta bo‘lgani sabab q_i=x_i-[x_i], q_ij=a_ij-[a_ij] lardan foydalanib ularning kasr qismini ajratamiz, ya'ni
q₂=1.5-[1.5]=1.5-1=0.5, q₂₄=1.5-[1.5]=1.5-1=0.5.
Tengsizlikning ikki tomoniga (-1) ni ko‘paytirib, x₆ qo‘shimcha o‘zgaruvchini kiritamiz.
Natijada quyidagiga ega bo‘lamiz:
, ya'ni
Uni jadvalning oxiriga joylashtiramiz.
5.

BO‘	1	-x4	-x5
x2	0.0	0.0	1.0
x1	1.5	0.5	1.5
x3	3.0	-1.0	-6.0
x6	-0.5	-0.5	-0.5
Z	3.5	-1.5	-5.5

Simpleks almashtirishlar qilib quyidagi jadvalga ega bo‘lamiz.

BO‘	1	-x6	-x5
x2	0.0	1.0	0.0
x1	1.0	1.0	1.0
x3	4.0	-5.0	-2.0
x4	1.0	1.0	-2.0
Z	5.0	-4.0	-3.0

Hosil bo‘lgan simpleks jadvalda ozod hadlar ustuni elementlari butun sonlardan iborat. Demak, butun sonli dasturlash masalasi yechimi X=(1,0,4,1) bo‘ladi va Z_min=5.


2.Transport masalasi

Transport masalasi chizikli programmalash masalalari ichida nazariy va amaliy nuktai nazaridan eng yahshi uzlashtirilgan masalalardan biri bulib, undan sanoat va kishlok hujalik mahsulotlarini tashishni optimal planlashtirish ishlarida muvaffakiyatli ravishda foydalanilmokda.

Tranport masalasi mahsus chizikli programmalash masalalari sinfiga tegishli bulib, uning chegaralovchi shartlaridagi koefficentlaridan tuzilgan matricaning elementlari 0 va 1 rakamlardan iborat buladi va har bir ustunda fakat ikkita element 0 dan farkli, kolganlari esa 0 ga teng buladi. Transport masalasini echish uchun uning mahsus hususiyatlarini nazarga oluvchi usullar yaratilgan. Transport masalasining matematik modelini kuyidagi kurinishda yozish mumkinligi bizga ma'lum.



Bu erdagi (1) shart har bir ishlab chikaruvchi punktlaridagi mahsulot tula taksimlansin, (2) esa har bir iste'mol kiluvchi punktning talabi tula kanoatlantirilsin degan ma'nolarni bildiradi. Mahsulotni tashish uchun sarf kilinadigan umumiy transport harajatlari (4) chizikli funkciya orkali ifodalanadi.
Masaladagi har bir manfiy bulmagan sonlar. Agar (1) - (4) masalada



tenglik urinli bulsa, ya'ni ishlab chikarilgan mahsulotlar yigindisi unga bulgan talablar yigindisiga teng bulsa, u holda bu masalani yopik modelli transport masalasi deb ataymiz.
1 -teorema. Har kanday yopik modelli transport masalasi echimga ega.
Isbot.
SHartga kura



U holda

Berilgan transport masalasining plani bo’ladi. Haqiqatan ham,

Demak, transport masalasining hamma shartlarini qanoatlantiradi. Shuning uchun bu mikdor masalaning plani buladi.
2 - teorema. Taransport masalasining shartlaridan tuzilgan matrisaning rangi ga teng.
Isbot. Haqiqatan ham, bu matrisa kengaytirilgan holda quyidagi ko’rinishga ega bo’ladi:



Bu matrirsaning ixtiyoriy qatori (masalan 1- qatori) qolgan qatorlarning chiziqli kombinatsiyasidan iborat ekanligini ko'rs’tish mumkin. qatorlarni o’zaro qo’shib, natijasidan qatorlarni ayirsak 1-qatorni hosil qilamiz. Demak, A Matritsaning rangi . Endi - qatorlar o’zaro chiziqli bog’liq bo’lmagan sistemani tashkil qilishini ko’rsatamiz.Buning uchun ixtiyoriy sonlar olib ularga mos ravishda - qatorlarni ko’paytirib o’zaro qo’shamiz va natijasini ga tenglaymiz.Natijada quyidagilarga ega bo’lamiz:
(6)
va
(7)
(6) sistemadan
(8)
Ekani va (7) sistemadan
(9)
kelib chiqadi. Bundan (8) ga asosan bo’ladi. Demak, А matritsaning ta qatori o’zaro chiziqli bog;liq bo’lmagan sistemani tashkil qiladi va demak bo’ladi.
3-teorema. Agar masaladagi barcha va lar butun sonlardan iborat bulsa, transport masalasining echimi butun sonli buladi.
Teoremaning isbotini transport masalasining boshlangich tayanch planlarini topish usullaridan kurish mumkin.
4-teorema. Ihtiyorniy transport masalasining optimal plani mavjuddir.
Isbot. 1-teoremaga asosan masalaning kamida bitta plani mavjuddir. (8.1.1), (8.1.2) shartlardagi koefficientlar va barcha va lar musbat butun son bulganligi sababli ham yukoridan chegaralangan buladi va uning kiymati mos va larning kiymatidan oshmaydi.
Shunday kilib, tarnsport masalasi planlaridan tashkil topgan tuplam bush tuplam bulmaydi, u chegaralangan tuplam buladi. Demak, transport masalasi optimal planga ega.