Ուսապարկերի աճուրդ

մինի

**Ուսապարկերի աճուրդ**, աճուրդի տեսակ, որտեղ վաճառում են մի քանի նույնական իրեր, և կան մի քանի հայտատուներ՝ տարբեր գնահատականներով, որոնք հետաքրքրված են տարբեր քանակությամբ իրերով: Ուսապարկերի աճուրդ նպատակն է ընտրել ընդհանուր պահանջարկ ունեցող հայտատուների ենթաբազմություն, ոչ ավելի, քան ապրանքների քանակը և, կախված դրանից, առավելագույն ընդհանուր արժեքը: Հայտատուների նման հավաքակազմ գտնելը պահանջում է լուծել ուսապարկերի խնդիրը, որը բացատրում է «Ուսապարկերի աճուրդ» տերմինը:

Ուսապարկերի աճուրդի կիրառման օրինակ է գովազդատուների միջև եթերաժամանակի բաշխումը։ Այստեղ օբյեկտները ժամանակի չափման միավորներն են (օրինակ՝ վայրկյանները): Յուրաքանչյուր գովազդատու ունի գովազդային առաջարկ՝ տարբեր տևողությամբ (վայրկյանների տարբեր քանակ) և գովազդի տարբեր արժեք: Նպատակն է ընտրել գովազդի ենթաբազմություն, որը պետք է ցուցադրվի որոշակի ժամանակահատվածում՝ ընդհանուր արժեքը առավելագույնի հասցնելու համար:

## Նշում
Կան որոշակի նույնական դիրքեր և  տարբեր աճուրդի մասնակիցներ: Աճուրդի յուրաքանչյուր մասնակցի նախասիրությունները նշվում են երկու թվերով՝

* Պահանջ-ամբողջ թիվ, որը որոշում է, թե որքան ապրանք է ցանկանում ձեռք բերել տվյալ հայտատուն: Հայտատուին անհրաժեշտ է ապրանքների Հենց այդ քանակը, և նրան քիչ թե շատ ապրանքներ պետք չեն:
* Աճուրդի արժեքը այն թիվն է, որը որոշում է, թե որքան գումար է հայտատուն ակնկալում ստանալ հենց այդ ապրանքների ստացումից:

Աճուրդի հավանական արդյունքը աճուրդում հաղթած մասնակիցների  ենթաբազմությունն է, ընդ որում նրանց ընդհանուր պահանջարկը ոչ ավելի, քան նշված են։ Հաղթողների բազմության արժեքը հավասար է հաղթողների արժեքների գումարին։

Նպատակն է գտնել հաղթողների ընդունելի հավաքածու՝ առավելագույն ընդհանուր գումարով:

Հեռարձակման ժամանակի օրինակում, եթե գովազդը հատկացվում է 5 րոպե, ապա վայրկյանների քանակը  հավասար է 300), կարևոր է հաշվել պոտենցիալ գովազդատուների քանակը, գովազդի տևողությունը վայրկյաններով և այն գումարը, որը  ակնկալում են ստանալ, եթե դրա գովազդը հեռարձակվի:

## Հիմնական լուծումներ
Եթե բոլոր հայտատուների պահանջներն ու արժեքները հայտնի են հանրությանը, ապա խնդիրը կարող է լուծվել ուսապարկի խնդրի ցանկացած ալգորիթմի միջոցով: Խնդիրը բարդ է, բայց այն ունի արդյունավետ մշտական գործակիցի մոտարկման ալգորիթմներ: Գործնականում, սովորաբար,  պահանջները հայտնի են (օրինակ, յուրաքանչյուր գովազդատուի գովազդի տևողությունը պետք է հայտնի լինի), բայց  գնահատականները հայտատուների անձնական տեղեկատվությունն են: Այսպիսով, աճուրդի մեխանիզմը պետք է խրախուսի հայտատուներին բացահայտել իրենց իրական գնահատականները:

Աճուրդը ճշմարիտ մեխանիզմ է, որը կարող է օգտագործվել արժեքների գումարը առավելագույնի հասցնելու համար՝ միաժամանակ խթանելով գործակալներին բացահայտել իրենց իրական արժեքները: Այնուամենայնիվ, սա գործում է միայն այն դեպքում, եթե արդյունքը առավելագույնի հասցնի արժեքները.Սա չի աշխատում մոտավորությունների հետ (եթե արդյունքը միայն մոտավորապես օպտիմալ է, ապա այն այլևս վավեր չէ): Օպտիմալ արդյունքի որոնումը չի կարող իրականացվել բազմանդամ ժամանակում: Այս առումով հարց է առաջանում՝ կան արդյոք հուսալի մեխանիզմներ, որոնք աշխատում են բազմանդամ ժամանակում և հասնում են մոտավորապես օպտիմալ արդյունքի։

## Հուսալի մոտարկման մեխանիզմներ
Մուալեմը և Նիսսանը տվեցին այս հարցի առաջին դրական պատասխանը, նրանք ցույց տվեցին, որ երկու ագահ ալգորիթմների համատեղումը տալիս է երկգործոն մոտարկման հուսալի մեխանիզմ:

Բրիստը, Քրիստան և Վոկինգը բարելավեցի այս արդյունքը՝ ցույց տալով ճշմարիտ ալգորիթմ:

Դատտինգը, Գկատցելիսը և Ռաֆգարդենը ներկայացրեցին հուսալի աճուրդի ալգորիթմ, որը հասնում է O լոգարիթմական մոտարկմանը և ապացուցեցին, որ ոչ մի հետաձգված ընդունման աճուրդ չի կարող հասնել ավելի լավ մոտարկման: Սա ցույց է տալիս  վստահելի աճուրդների ընդհանուր դասի և հետաձգված ընդունման աճուրդների ենթադասի միջև տարբերությունը:

## Ծանոթագրություններ