ตัวอย่างปัญหา ของ การหาค่าเหมาะที่สุดแบบเฟ้นสุ่ม

ตัวอย่างปัญหา Newsvendor หลายบริษัทขายสินค้าตามฤดูกาล เช่น บทความแฟชั่น ที่นั่งของสายการบิน ของประดับตกแต่งวันคริสต์มาส นิตยสารและหนังสือพิมพ์ ผลิตภัณฑ์เหล่านี้มีลักษณะการขายที่ค่อนข้างสั้น หลังจากหมดฤดูกาล มูลค่าของผลิตภัณฑ์ก็จะลดลงอย่างมากมาย บ่อยครั้งที่มีการตัดสินใจผลิต หรือซื้อผลิตภัณฑ์ ก่อนที่ฤดูกาลขายจะเริ่มต้น เพราะเมื่อฤดูกาลขายเริ่มต้นแล้ว จะไม่มีเวลามานั่งเปลี่ยนแปลงหรือดำเนินการการตัดสินใจนั้น เนื่องจากจะทำให้ปริมาณของผลิตภัณฑ์ที่จะได้รับไม่ตรงตามเป้าหมาย แต่ในระหว่างฤดูกาล ผู้ที่ตัดสินใจสามารถตัดสินใจแบบอื่นๆที่ทำให้เกิดผลดีมากขึ้นได้ เช่น ปรับเปลี่ยนราคาและยอดขายของผลิตภัณฑ์ที่มีช่วงฤดูกาลยาว พฤติกรรมดังกล่าว เป็นที่คุ้นเคยในหลายๆอุตสาหกรรม ซึ่งสถานการณ์ดังกล่าวก็คือการตัดสินใจทำก่อนสินค้าติดตลาด ดังนั้นการตัดสินใจต้องทำโดยไม่ทราบถึงผลที่จะเกิดขึ้นสมมติว่า ผู้จัดการมีการตัดสินใจผลิตสินค้าตามฤดูกาล ตามการสั่งซื้อสินค้า ดังนั้นการตัดสินใจตัวแปร x คือตัวเลขค่าลบแทนปริมาณการสั่งซื้อ ค่าใช้จ่ายสำหรับผลิตภัณฑ์ของบริษัท c คือต้นทุนต่อหน่วยของผลิตภัณฑ์ ให้ R คือราคาต่อหน่วยของผลิตภัณฑ์ที่สามารถขายในฤดูกาล(รายได้) หลังจากฤดูกาลขาย ผลิตภัณฑ์ที่เหลือสามารถจำหน่ายในราคาค่าซาก คือ s และโดยปกติ s < R ให้ D คือความต้องการใช้ผลิตภัณฑ์ที่ตามการสั่งซื้อ ถ้าค่า D หรือค่าความต้องการสูงกว่าปริมาณการสั่งซื้อ x แล้ว ผลิตภัณฑ์จะถูกขายหมดและไม่มีหลงเหลืออยู่เมื่อหมดฤดูกาล เมื่อรวมรายได้แล้ว จะได้กำไรเท่ากับ R X {\displaystyle RX} และ R X − C X = ( r − C ) x {\displaystyle RX-CX=(r-C)x} ตามลำดับ ถ้า D หรือค่าความต้องการน้อยกว่าปริมาณการสั่งซื้อ x แล้ว ปริมาณของผลิตภัณฑ์ที่มีเหลือเมื่อหมดฤดูกาลคือ x – D ดังนั้น เมื่อรวมรายได้แล้ว จะได้กำไรคือ R D + S ( x − − D ) {\displaystyle RD+S(x--D)} และ R D + S ( x − − D ) − − C X = ( s − − c ) x + ( R − − S ) D {\displaystyle RD+S(x--D)--CX=(s--c)x+(R--S)D} ตามลำดับดังนั้นจะได้กำไร

ไฟล์:Stochastic1.jpgสมการ (1)

ผู้จัดการต้องการตัดสินใจ x เพื่อเพิ่มกำไร G (x, D) แต่ไม่รู้ว่า D เป็นอย่างไร หรืออาจบอกได้ว่าไม่แน่นอนในตอนนี้สังเกตว่า ถ้า r ≤ c และ s ≤ c แล้ว บริษัทจะไม่ได้กำไรจากการซื้อและขายผลิตภัณฑ์ กำหนดปริมาณการสั่งซื้อที่ดีที่สุดคือ x* = 0 โดยไม่คำนึงถึง D นอกจากนี้ถ้า s ≥ c แล้ว ผลิตภัณฑ์ที่ยังไม่ได้ขายเมื่อหมดฤดูกาล สามารถขายในราคาอย่างน้อยเท่ากับต้นทุนของผลิตภัณฑ์ เพื่อที่จะได้ปริมาณการสั่งซื้อที่เหมาะสมที่สุดโดยไม่คำนึงถึง D นี่เป็นตัวอย่างที่ถูกต้องและชัดเจน ดังนั้นเราจึงสมมติได้ว่าส่วนที่เหลือคือ s < c < r. ภายใต้สมมติฐานนี้ กำหนดให้ D ≥ 0 ฟังก์ชัน G(•,D) เป็นตัวแบบเชิงเส้นเป็นช่วง มีความชันเป็นบวก r - c สำหรับ x < D และความชันเป็นลบ s - c สำหรับ x > D ดังนั้นถ้าทราบความต้องการของ D จะได้การตัดสินใจที่ดีที่สุดในการเลือกปริมาณการสั่งซื้อ x * = Dอย่างไรก็ตาม ถ้าไม่รู้ D แล้ว จะทำให้ปัญหายากขึ้น บางครั้งผู้จัดการอาจต้องการป้องกันผลที่เลวร้ายที่สุด สมมติว่าผู้จัดการคิดว่า D จะอยู่ในช่วง [a, b] โดย a < b นั่นคือ ขอบเขตบนและล่างสำหรับความต้องการที่ผู้จัดการรู้ ในกรณีเพื่อป้องกันสถานการณ์ที่เลวร้ายที่สุด ผู้จัดการอาจกำหนดค่า x ที่ให้ผลกำไรที่ดีที่สุดภายใต้ผลที่เลวร้ายที่สุด นั่นคือค่ามากสุดของซึ่งนำไปสู่ปัญหา max – min ดังนี้

ไฟล์:Stochastic2.jpgสมการ (2)

มันไม่ยากที่จะมองว่า g (x) = G (x, a) และด้วยเหตุนี้ x* = a เป็นค่าที่เหมาะสมที่สุดจากกรณีสถานการณ์ที่เลวร้ายที่สุด เป็นที่ชัดเจนว่า ในหลายกรณีจะมีการตัดสินใจที่ยึดติดแบบเดิมๆเกินไปบางครั้งผู้จัดการอาจยังต้องการเสี่ยงตัดสินใจภายใต้ความเป็นไปได้ที่เลวร้ายที่สุด โดยคิดว่าจะให้ผลลัพธ์ที่ดี และเป็นการตัดสินใจที่ดีที่สุดที่สามารถเป็นไปได้ สำหรับทุกๆผลลัพธ์ของ D ใดๆ กำหนดให้ ไฟล์:Stochastic2-1.jpg แสดงผลกำไรที่ดีที่สุด และถูกเรียกว่าค่าข้อมูลที่เหมาะสมที่สุดด้วย การตัดสินใจที่เหมาะสมกับข้อมูลที่สมบูรณ์แบบ x* = D บางครั้งถูกเรียกว่า รอและดูวิธีการแก้ปัญหา สมมติว่าผู้จัดการฝ่าย เลือกที่จะสั่งซื้อ x เพื่อให้กำไรเป็น G (x, D) จำนวนของกำไรที่บริษัทจะไม่ได้ เพราะตัดสินใจผิดพลาดคือ g ∗ ( D ) − G ( x , D ) {\displaystyle g*(D)-G(x,D)} ผู้จัดการอาจกำหนดค่าของ x ที่ช่วยลดส่วนของกำไรที่เสียไป สำหรับ x ใดๆ เนื่องจากผู้จัดการฝ่ายต้องการที่จะกำหนดค่าของ x ที่ช่วยลดส่วนของกำไรที่เสียไป จึงนำไปสู่ปัญหา min - max ต่อไปนี้

ไฟล์:Stochastic3.jpg

ค่าที่เหมาะสมที่สุดของปัญหานี้คือ x ∗ = [ ( c − s ) a + ( r − c ) b ] / ( r − s ) {\displaystyle x*=[(c-s)a+(r-c)b]/(r-s)} กำหนดให้ x* เป็นการรวมของ a และ b และทำให้ a < x* < b ค่าซากที่มากที่สุดที่สูญเสียไปต่อหน่วย c – s ค่าขอบเขตล่างของ x* คือ a และกำไรที่มากที่สุดต่อหน่วย r - c ค่าขอบเขตบนของ x* คือ b ดูเหมือนว่าการตัดสินใจที่เหมาะสมที่สุดจะเป็น x* = aสิ่งที่แย่ที่สุดของตัวแปรทั้งสองคือ ไม่มีข้อมูลเบื้องต้นเกี่ยวกับความต้องการ D ยกเว้นขอบเขตบนและล่าง ในบางสถานการณ์ เหตุการณ์นี้อาจจะเป็นกรณีที่แย่ที่สุด ที่ต้องกำหนดขนาดความต้องการที่ไม่รู้ โดยต้องไม่ให้ มีขนาดใหญ่เกินไปอีกวิธีหนึ่งในการตัดสินใจภายใต้ความไม่แน่นอน ซึ่งแตกต่างจากวิธีกรณีที่แย่ที่สุดที่ได้อธิบายไว้ข้างต้น เป็นวิธีการหาค่าที่เหมาะสมโดยการสุ่ม ซึ่งเราจะระบุในส่วนที่เหลือของบทความนี้ สมมติว่าความต้องการ D ถูกมองว่าเป็นตัวแปรสุ่ม นั่นหมายความว่าเราจะรู้การแจกแจงความน่าจะเป็นของ D หรืออย่างน้อยสามารถประมาณโดยใช้ข้อมูลเก่าๆ และ / หรือข้อมูลที่เคยปรากฏมาก่อนหน้านี้ F(w) ≡ ℙ(D ≤ w) จากผู้จัดการ ให้ เป็นฟังก์ชันการแจกแจงสะสม (CDF) ของ D จากนั้นสามารถหาค่าที่เหมาะสมจากฟังก์ชันค่าเฉลี่ย นั่นคือ ค่าคาดหวังของกำไรที่มากที่สุด E ⁡ [ G ( x , D ) ] = ∫ 0 ∞ G ( x , w ) d ⁡ F ( w ) . {\displaystyle \operatorname {E} [G(x,D)]=\int _{0}^{\infty }G(x,w)\,\operatorname {d} F(w).} ซึ่งนำไปสู่โปรแกรมการสุ่มไฟล์:Stochastic4.jpg
การแก้ปัญหาค่าที่เหมาะสมไม่ใช่เรื่องยากในปัจจุบัน กำหนดให้ D ≥ 0 ฟังก์ชัน G(•,D) มีลักษณะเว้า (ตัวแบบเชิงเส้นเป็นช่วง) ดังนั้นมูลค่าที่คาดหวัง g (.) ก็ต้องเว้าด้วย สมมติว่าในขณะที่ F (.) ต่อเนื่องที่จุด x > 0 นั่นคือ ไฟล์:Stochastic4-1.jpg เมื่อใช้การอินทิเกรดแยกส่วนจะคำนวณได้ว่า

ไฟล์:Stochastic5.jpg

ฟังก์ชัน g (.) ลักษณะกราฟเว้าอย่างต่อเนื่อง จากสมการ (5) ถ้า F (°) ต่อเนื่องที่ x จะเป็นไปได้ว่า g (.) เป็นอนุพันธ์ที่ x iff F (.) อย่างต่อเนื่องที่ x ซึ่งในกรณีนี้

ไฟล์:Stochastic6.jpg

ในทางกลับกัน เป็นฟังก์ชันการแจกแจงสะสม (CDF) ของ F ซึ่งถูกกำหนดว่าเนื่องจากฟังก์ชัน g(.) มีลักษณะเว้า ซึ่งสอดคล้องกับ x* > 0 เป็นการหาค่าที่ดีที่สุดของสมการที่ (4) นั่นคือ g’ (x*) = 0 โดยมีเงื่อนไขว่า g(.) เป็นอนุพันธ์ที่ x* กำหนดให้ s < c < r จาก 0 < (r − c)/(r − s) < 1 ดังนั้นคำตอบที่ดีที่สุดของสมการ (4) จะได้ว่า

ไฟล์:Stochastic7.jpg

จากสมการ ถ้า F (°) เป็นฟังก์ชันต่อเนื่องที่ x *เห็นได้ชัดว่าหากมีความรู้ด้านการกระจายความน่าจะเป็นของความต้องการ D แล้วจะได้รูปสมการที่ง่ายขึ้น ซึ่งคล้ายกับ CDF ของ F (°) จะไม่สามารถประมาณค่าที่ดีที่สุดได้ แต่จะเป็นการแก้ปัญหาที่ดีที่สุดค่าอื่นๆที่ได้จากการแก้ปัญหาสมการที่ (4) ผู้จัดการฝ่ายพยายามที่จะหากำไรที่ดีที่สุดจากค่าเฉลี่ย อย่างไรก็ตามเมื่อคิดถึงผลกำไร G (x *, D) อาจจะแตกต่างจาก g (x *) ขึ้นอยู่กับส่วนที่เราสนใจของความต้องการ D กรณีนี้อาจเกิดขึ้นถ้า G (x *, D) ถูกมองว่าเป็นตัวแปรสุ่ม จะมีความแปรปรวนขนาดใหญ่ซึ่งอาจจะวัดได้จาก Var [G (x *, D)] ดังนั้นหากผู้จัดการต้องการที่จะควบคุมความแปรปรวน เขาจะต้องพิจารณาปัญหาการเพิ่มประสิทธิภาพดังต่อไปนี้ไฟล์:Stochastic8.jpg
ค่าสัมประสิทธิ์ β ≥ 0 หมายถึงค่าน้ำหนักที่ให้กับการตัดสินใจ ถ้า β มีขนาดใหญ่ ปัญหาดังกล่าวข้างต้นจะมีความแปรปรวนของกำไรน้อยที่สุด ในขณะที่ β = 0 นั่นคือสมการ (8) เกิดขึ้นพร้อมกับสมการ (4) เนื่องจากมีการกำหนดค่าความแปรปรวนเป็น Var [G (x, D)] ≡ IE [(g (x, D) - IE [G (x, D)]) 2] ซึ่งเท่ากับค่าคาดหวังของมัน ค่าที่ได้จาก (8) จะคล้ายกับ ค่าที่คาดหวังที่ได้จาก (4) ดังนั้นการหาค่าคาดหวังที่ดีที่สุดคือ G (x, D) ซึ่งใช้ได้กับ การหาค่าเฉลี่ย ค่าความแปรปรวน ตำแหน่งของข้อมูล และเกือบทุกๆด้านของตัวแปรสุ่มที่น่าสนใจจากตัวอย่างการหาค่าที่ดีที่สุดนี้ สามารถนำไปใช้ได้กับการตัดสินใจภายใต้สภาวะการที่ไม่แน่นอนได้ ตัวแปรสุ่ม D ใช้แทนความหมายของค่าเฉลี่ย μ = IE [D] แล้วทำการกำหนดปัญหาดังนี้

ไฟล์:Stochastic9.jpg

ใกล้เคียง

การหายใจระดับเซลล์ การหายตัวไปของสึซึมิยะ ฮารุฮิ การหารด้วยศูนย์ การหาอายุจากคาร์บอนกัมมันตรังสี การหารสังเคราะห์พหุนาม การหาค่าเหมาะที่สุดแบบเฟ้นสุ่ม การหาค่าเหมาะสุดอย่างตอบสนอง การหาร การหาลำดับนิวคลีโอไทด์ด้วยวิธีอิลลูมินา การหารยาว

แหล่งที่มา

WikiPedia: การหาค่าเหมาะที่สุดแบบเฟ้นสุ่ม http://www.math.uwaterloo.ca/~cswamy/talks/stochop... http://www2.isye.gatech.edu/~anton/stochoptiebook.... http://www.jhuapl.edu/spsa/PDF-SPSA/Handbook04_Sto... http://citeseer.ist.psu.edu/kirkpatrick83optimizat... http://www-illigal.ge.uiuc.edu http://www.ima.umn.edu/talks/workshops/9-9-13.2002... //pubmed.ncbi.nlm.nih.gov/17813860 http://rtm.science.unitn.it/~battiti/archive/TheRe... //doi.org/10.1103%2FPhysRevLett.82.3003 //doi.org/10.1126%2Fscience.220.4598.671