Mavzu: chiziqsiz programmalashtirish. Reja

Boshlang‘ich tayanch yechimni qurish.

Ma'lumki, ixtiyoriy chiziqli programmalash masalasining optimal yechimini topish jarayoni boshlang‘ich tayanch yechimini kurishdan boshlanadi.
Masalaning (1) va (2) sistemalari birgalikda mn – ta noma'lumli m+n – ta tenglamalarda iborat. Agar (1) sistemaning tenglamalarini hadma-had qo‘shsak, va aloxida (2) sistemaning tenglamalarini hadma-had qo‘shsak, ikkita bir xil tenglama hosil bo‘ladi. Bu esa (1) va (2) dan iborat sistemada bitta chiziqli bog‘lik tenglama borligini ko‘rsatadi. Bu tenglama umumiy sistemadan chiqarib tashlansa, masala m+n-1 ta chiziqli bog‘liq bo‘lmagan tenglamalar sistemasidan iborat bo‘lib qoladi. Demak, masalaning buzilmaydigan tayanch yechimi m+n-1 ta musbat komponentalardan iborat bo‘ladi.
Shunday qilib, transport masalasining boshlang‘ich tayanch yechimi biror usul bilan topilgan bo‘lsa, (x_ij) – matritsaning m+n-1ta komponentalari musbat bo‘lib, qolganlari nolga teng bo‘ladi. Agar transport masalasining shartlari va uning tayanch yechimi yuqoridagi jadval ko‘rinishda berilgan bo‘lsa, noldan farqli x_ij – lar joylashgan kataklar «band kataklar», qolganlari «bo‘sh kataklar» deyiladi.
Agar band kataklarni vertikal yoki gorizontal kesmalar bilan tutashtirilganda yopiq ko‘pburchak xosil bo‘lsa, bunday xol sikllanish deyiladi va yechim tayanch yechim bo‘lmaydi. Demak, birorta yechim tayanch yechim bo‘lishi uchun band kataklar soni m+n-1 ta bo‘lib sikllanish ro‘y bermasligi kerak.
Shimoliy-g‘arb usuli.
Transport masalasi jadval ko‘rinishida berilgan bo‘lsin. Yo‘l harajatlarini xisobga olmay B₁ iste'molchining talabini A₁ ta'minotchi xisobiga qondirishga kirishamiz. Buning uchun a₁ va b₁ yuk birliklaridan kichigini A₁B₁ katakning chap pastki burchagiga yozamiz. Agar a₁< b₁ bo‘lsa, B₁ ning extiyojini to‘la qondirish uchun A₂B₁ katakka yetishmaydigan yuk birligini A₂ dan olib yozamiz va h.q. Bu jarayonni A_mB_n katakka yetguncha davom etdiramiz. Agar (5) shart o‘rinli bo‘lsa, bu usulda tuzilgan yechim albatta tayanch yechim bo‘ladi.

1-misol. Transport masalasining boshlang‘ich yechimini toping.

Ta'minotchilar	Iste'molchilar						Zaxira xajmi
	B1	B2	B3	B4	B5
A1	10 100	7	4	1	4	100
A2	2 100	7 150	10	6	11	250
A3	8	5 50	3 100	2 50	2	200
A4	11	8	12	16 50	13 250	300
Talab xajmi	200	200	100	100	250

Minimal qiymat usuli.
Bu usulda boshlang‘ich yechim qurish uchun avval yo‘l harajati eng kichik bo‘lgan katakka a_i va b_j lardan kichigi yoziladi va keyingi eng kichik qiymatli katakka o‘tiladi va h.q. Bu usulda tuzilgan boshlang‘ich yechimni buzilmaslik va sikllanishga tekshirish shart.
2-Misol. Minimal qiymat usuli bilan boshlang‘ich yechimini toping.

Ta'minotchilar	Iste'molchilar						Zaxira xajmi
	B1	B2	B3	B4	B5
A1	10	7	4	1 100	4	100
A2	2 200	7 50	10	6	11	250
A3	8	5	3	2	2 200	200
A4	11	8 150	12 100	16	13 50	300
Talab xajmi	200	200	100	100	250

2. 
   Optimal yechim qurishning potensiallar usuli
   

Teorema: Agar transport masalasining X^*=(x^*_ij) yechimi optimal bo‘lsa, unga quyidagi shartlarni qanoatlantiruvchi m+n-ta sonlar sistemasi mos keladi:
X^*_ij > 0 lar uchun U^*_i + V^*_j = C_ij
X^*_ij = 0 lar uchun U^*_i + V^*_j ? C_ij
i=1,2,…,m; j=1,2,…,n.
U^*_i va V^*_j sonlar mos ravishda «ta'minotchi va iste'molchilarning potensiallari» deyiladi.
Bu teoremaga ko‘ra boshlang‘ich tayanch yechim optimal bo‘lishi uchun quyidagi ikki shart bajarilishi kerak:
a) har bir band katak uchun mos potensiallar yig‘indisi shu katakdagi yo‘l harajati qiymatiga teng bo‘lishi kerak:
U^*_i + V^*_j = C_ij (6)
b) har bir bo‘sh katak uchun mos potensiallar yig‘indisi shu katakdagi yo‘l harajati qiymatidan katta bo‘lmasligi kerak:
U^*_i + V^*_j ? C_ij (7)
Agar kamida bitta bo‘sh katak uchun (7) shart bajarilmasa, ko‘rilayotgan yechim optimal bo‘lmaydi va bu yechimni bazisga (7) shart buzilgan katakdagi noma'lumni kiritish bilan yaxshilash mumkin.
Shunday qilib navbatdagi tayanch yechimni optimallikka tekshirish uchun avval (6) shart yordamida potensiallar sistemasi quriladi va so‘ngra (7) shartning bajarilishi tekshiriladi.


Foydalanilgan adabiyotlar ro’yxati

1. 
   Laura Tomson i LyeokVelling. razrabotka web -prilojeniy na php i mysql. DiaSoft. Sankt-Peterburg – 2003.
   
2. 
   N. N. Kussul, A.Yu. Shelestov. samouchitel ispolzovanie php. Dialektika Moskva-Sankt-Peterburg-Kiev-2005.
   

3. 
   http://www.inetwork.realsofts.com/ . zarabotok v internete.
   

Sopyright(c) 2002-2005 Real-Soft.

4. 
   L.Argerix, D.Koggsxo, KEgervari, M.Geysler. professionalnoe php programmirovanie. Vtoroe izdanie. Sankt-Peterburg-2003.
   
5. 
   Mesheryakov E., xomonenko a. publikatsiya baz dannix v internete. Uchebnoe posobie dlya Vuzov. «Piter» 2001.
   
6. 
   monitoring razvitiya ikt v uzbekistane (Podg. proon
   

pri uchastii kM RUz, UzASI, Goskomstata, mvsso, mno, 2003 g.)

7. 
   Kurs leksiy «Informatsionnie texnologii v kommercheskoy deyatelnosti». Kultishev E.I., 2003.
   
8. 
   «Network Magazine», №10, 1999.
   

10. «PC WEEK», №6, 1998.

11. 
    Informatsiya s veb-sayta «Elektronnie platejnie sistemi» http://www.emoney.ru
    
12. 
    Informatsiya s veb-sayta «Reksoft.Elektronnaya kommersiya», http://www.reksoft.ru