วิธี การเขียนโปรแกรมแบบไดนามิกช่วยให้คุณแก้ไขปัญหาเศรษฐกิจมากมายได้สำเร็จ (ดูตัวอย่าง) ลองพิจารณาปัญหาที่ง่ายที่สุดอย่างหนึ่ง เรามีเงินทุนสำรอง (ทรัพยากร) K บางส่วนซึ่งจะต้องกระจายระหว่างองค์กรต่างๆ เมื่อมีการลงทุนในกองทุนแต่ละองค์กรจะสร้างรายได้ที่ขึ้นอยู่กับ กล่าวคือ เป็นตัวแทนของฟังก์ชันบางประเภท (แน่นอนว่าฟังก์ชันเหล่านี้จะไม่ลดลง)

คำถามคือ กองทุน K ควรกระจายไปยังองค์กรต่างๆ อย่างไรจึงจะสร้างรายได้สูงสุดโดยรวม?

ปัญหานี้แก้ไขได้อย่างง่ายดายโดยใช้วิธีการเขียนโปรแกรมแบบไดนามิก แม้ว่าในการกำหนดจะไม่มีการกล่าวถึงเวลา แต่ก็ยังเป็นไปได้ที่จะเปิดเผยการดำเนินงานของการกระจายเงินทุนในบางลำดับโดยพิจารณาจากขั้นตอนแรกคือการลงทุนในกองทุนในองค์กร ประการที่สอง ฯลฯ

ระบบควบคุม S ใน ในกรณีนี้- เงินทุนหรือทรัพยากรที่มีการกระจาย สถานะของระบบ S ก่อนแต่ละขั้นตอนจะมีหมายเลข S หนึ่งตัว - หุ้นกองทุนที่มีอยู่ที่ยังไม่ได้ลงทุน ในงานนี้ “การจัดการขั้นตอน” คือเงินทุนที่จัดสรรให้กับองค์กร จำเป็นต้องค้นหาการควบคุมที่เหมาะสมที่สุด เช่น ชุดตัวเลขที่รายได้รวมสูงสุด:

ให้เราแก้ปัญหานี้ก่อนในรูปแบบทั่วไปตามสูตร และจากนั้นสำหรับข้อมูลตัวเลขเฉพาะ ให้เราค้นหาแต่ละขั้นตอนเพื่อให้ได้กำไรสูงสุดตามเงื่อนไข (จากขั้นตอนนี้จนจบ) หากเราเข้าใกล้ขั้นตอนนี้ด้วยการสำรองเงินทุน S ให้เราแสดงกำไรที่เหมาะสมที่สุดแบบมีเงื่อนไข และการควบคุมที่เหมาะสมที่สุดตามเงื่อนไขที่สอดคล้องกัน - กองทุนที่ลงทุน องค์กร -

มาเริ่มการเพิ่มประสิทธิภาพจากขั้นตอนสุดท้ายกัน ให้เราเข้าใกล้ขั้นตอนนี้ด้วยยอดเงินคงเหลือ ส. เราควรทำอย่างไร? เห็นได้ชัดว่าลงทุนจำนวนเงิน S ทั้งหมด ในองค์กร ดังนั้น การควบคุมที่เหมาะสมตามเงื่อนไขในขั้นตอนที่ 3: ให้เงินทุนทั้งหมดที่มีอยู่แก่องค์กรสุดท้าย เช่น

และอัตราขยายที่เหมาะสมที่สุดตามเงื่อนไข

เมื่อพิจารณาจากช่วงค่าทั้งหมดของ S (โดยระบุตำแหน่งไว้ค่อนข้างใกล้) เราจะทราบค่าแต่ละค่าของ S ขั้นตอนสุดท้ายได้รับการปรับให้เหมาะสม

มาดูขั้นตอนสุดท้ายกันดีกว่า ให้เราเข้าใกล้มันด้วยการสำรองเงินทุน S ให้เราแสดงกำไรที่เหมาะสมตามเงื่อนไขในสองขั้นตอนสุดท้าย: (ซึ่งได้รับการปรับให้เหมาะสมแล้ว) หากเราจัดสรรเงินทุนให้กับองค์กรในขั้นตอนสุดท้าย เงินรางวัลของเราในสองขั้นตอนสุดท้ายจะเท่ากับ

และคุณจำเป็นต้องค้นหาสิ่งที่ได้รับสูงสุด:

ป้ายหมายความว่าถูกยึดแล้ว ค่าสูงสุดสำหรับทุกสิ่งที่เป็นไปได้ (เราไม่สามารถลงทุนมากกว่า S) จากนิพจน์ใน วงเล็บปีกกา- ค่าสูงสุดนี้คืออัตราขยายที่เหมาะสมที่สุดแบบมีเงื่อนไขสำหรับสองขั้นตอนสุดท้าย และค่าที่ได้รับค่าสูงสุดนี้คือการควบคุมที่เหมาะสมที่สุดแบบมีเงื่อนไขในขั้นตอนนั้น

และการควบคุมที่เหมาะสมตามเงื่อนไขที่สอดคล้องกันคือค่าที่ทำให้บรรลุค่าสูงสุดนี้

ด้วยวิธีนี้เราจะไปถึงองค์กรในที่สุด เรารู้แน่ว่าสต๊อกกองทุนก่อนก้าวแรกจะเท่ากับ K:

ดังนั้นจึงพบกำไร (รายได้) สูงสุดจากทุกองค์กร ตอนนี้สิ่งที่เหลืออยู่คือ "อ่านคำแนะนำ" ค่าที่ถึงค่าสูงสุด (13.4) คือการควบคุมที่เหมาะสมที่สุดในขั้นตอนที่ 1

หลังจากที่เราลงทุนเงินทุนเหล่านี้ในองค์กรแรกแล้ว เราก็จะเหลือมันไว้ “การอ่าน” คำแนะนำสำหรับค่า S นี้เราจัดสรรให้กับองค์กรที่สอง ปริมาณที่เหมาะสมที่สุดแปลว่า ฯลฯ จนจบ

ทีนี้ลองแก้ตัวอย่างเชิงตัวเลขกัน กองทุนเริ่มต้น (หน่วยมาตรฐาน) และจำเป็นต้องกระจายกองทุนอย่างเหมาะสมที่สุดระหว่างห้าองค์กร เพื่อความง่าย เราถือว่าลงทุนเพียงจำนวนเต็มเท่านั้น ฟังก์ชันรายได้แสดงไว้ในตารางที่ 13.1

ตารางที่ 13.1

ในแต่ละคอลัมน์ เริ่มต้นจากการลงทุนจำนวนหนึ่ง รายได้จะหยุดเพิ่มขึ้น (ในความเป็นจริง สิ่งนี้สอดคล้องกับความจริงที่ว่าแต่ละองค์กรสามารถ "เชี่ยวชาญ" เงินทุนได้ในจำนวนที่จำกัดเท่านั้น)

มาดำเนินการปรับให้เหมาะสมตามเงื่อนไขตามที่อธิบายไว้ข้างต้น โดยเริ่มจากขั้นตอนที่ 5 สุดท้าย ทุกครั้งที่เราเข้าใกล้ขั้นตอนต่อไป มีเงินสำรองหรือไม่ เราพยายามจัดสรรเงินทุนจำนวนหนึ่งหรือจำนวนนั้นสำหรับขั้นตอนนี้ เอาเงินรางวัลไปเป็น ขั้นตอนนี้ตามตาราง 13.1 เราบวกกับเงินรางวัลที่ปรับให้เหมาะสมแล้วในขั้นตอนต่อๆ ไปทั้งหมดจนจบ (โดยคำนึงว่าเรามีเงินทุนเหลือน้อยกว่าอยู่แล้ว เพียงสำหรับจำนวนเงินทุนที่เราจัดสรรไว้) และค้นหาการลงทุนตามจำนวนนี้ ถึงจุดสูงสุด การลงทุนนี้เป็นการควบคุมที่เหมาะสมตามเงื่อนไขในขั้นตอนนี้ และค่าสูงสุดนั้นคือกำไรที่ดีที่สุดตามเงื่อนไข

ตาราง 13.2 แสดงผลลัพธ์ของการเพิ่มประสิทธิภาพแบบมีเงื่อนไขสำหรับทุกขั้นตอน ตารางถูกสร้างขึ้นดังนี้: คอลัมน์แรกให้มูลค่าของหุ้นของกองทุน S ที่เราเข้าใกล้ขั้นตอนนี้ ตารางยังแบ่งออกเป็นคอลัมน์อีกห้าคู่ซึ่งสอดคล้องกับหมายเลขขั้นตอน

ตารางที่ 13.2

คอลัมน์แรกของแต่ละคู่จะให้ค่าของการควบคุมที่เหมาะสมที่สุดตามเงื่อนไข คอลัมน์ที่สอง - อัตราขยายที่เหมาะสมที่สุดตามเงื่อนไข ตารางจะเรียงจากซ้ายไปขวา บนลงล่าง การตัดสินใจในขั้นตอนที่ห้า - ขั้นตอนสุดท้ายถูกบังคับ: เงินทุนทั้งหมดได้รับการจัดสรร ในขั้นตอนอื่นๆ ทั้งหมด โซลูชันจะต้องได้รับการปรับให้เหมาะสม อันเป็นผลมาจากการเพิ่มประสิทธิภาพตามลำดับของขั้นตอนที่ 5, 4, 3, 2 และ 1 ที่เราได้รับ รายการทั้งหมดคำแนะนำทั้งหมดสำหรับการควบคุมที่เหมาะสมที่สุดและอัตราขยาย W ที่เหมาะสมที่สุดแบบไม่มีเงื่อนไขสำหรับการดำเนินการทั้งหมด - ในกรณีนี้จะเท่ากับ 5.6 ในสองคอลัมน์สุดท้ายของตาราง 13.2 มีเพียงแถวเดียวเท่านั้นที่ถูกกรอก เนื่องจากเรารู้สถานะของระบบอย่างแน่ชัดก่อนที่จะเริ่มขั้นตอนแรก: การควบคุมที่เหมาะสมที่สุดในทุกขั้นตอนจะถูกเน้นด้วยกรอบ ดังนั้นเราจึงได้ข้อสรุปสุดท้าย: เราต้องจัดสรรสองหน่วยจากสิบหน่วยให้กับองค์กรแรก, ห้าหน่วยในองค์กรที่สอง, สองในสาม, ไม่มีเลยในสี่ และหนึ่งหน่วยในห้า ด้วยการกระจายนี้รายได้จะสูงสุดและเท่ากับ 5.6

แผนการสอน

วินัยทางวิชาการวิธีการทางคณิตศาสตร์และแบบจำลองทางเศรษฐศาสตร์

หัวข้อบทเรียน การแก้ปัญหา DP เชิงปฏิบัติต่างๆ โดยใช้วิธีทางคณิตศาสตร์

วัตถุประสงค์ของบทเรียน

พัฒนาทักษะในการแก้ปัญหาการเขียนโปรแกรมแบบไดนามิก

การพัฒนาคุณภาพจิตใจ ความสนใจ และทักษะงานวิชาการของนักศึกษา

ปลูกฝังวินัยและความมุ่งมั่นให้กับนักเรียน

อุปกรณ์การเรียนบันทึกการบรรยาย V.P. Agaltsov " วิธีการทางคณิตศาสตร์ในการเขียนโปรแกรม”

ความคืบหน้าของบทเรียน:

จุดขององค์กร:

การตรวจสอบการขาดงานกรอกบันทึก

การอัพเดตความรู้อ้างอิง: คำตอบสำหรับคำถามเพื่อความปลอดภัย

งานใดที่เรียกว่าหลายขั้นตอน?

เครื่องมือทางคณิตศาสตร์ใดที่ใช้แก้ปัญหาหลายขั้นตอน

อะไรคือการควบคุมที่เหมาะสมที่สุด u*?

อัลกอริธึมสำหรับวิธีการประมาณสองวงกลมต่อเนื่องกันคืออะไร?

ยกตัวอย่างงาน การกระจายที่เหมาะสมที่สุดทรัพยากร.

การเรียนรู้เนื้อหาใหม่:

ปัญหาการเขียนโปรแกรมไดนามิกแบบคลาสสิก

• ปัญหาลำดับรองทั่วไปที่ยาวที่สุด: เมื่อพิจารณาสองลำดับ คุณจะต้องค้นหาลำดับรองร่วมที่ยาวที่สุด

• ปัญหาในการหาลำดับที่เพิ่มขึ้นที่ยาวที่สุด: เมื่อพิจารณาจากลำดับแล้ว คุณจะต้องค้นหาลำดับที่เพิ่มขึ้นที่ยาวที่สุด

• ปัญหาระยะทางบรรณาธิการ (ระยะทาง Levenshtein): เมื่อมีสองสตริง คุณจะต้องค้นหาจำนวนขั้นต่ำของการลบ การแทนที่ และการเพิ่มอักขระที่แปลงสตริงหนึ่งเป็นอีกสตริงหนึ่ง

• ปัญหาการคำนวณเลขฟีโบนัชชี

• ปัญหาลำดับของการคูณเมทริกซ์: เมทริกซ์ที่กำหนด ... จำเป็นต้องลดจำนวนการดำเนินการสเกลาร์ให้เหลือน้อยที่สุดสำหรับการคูณ

• ปัญหาการเลือกวิถี

• ปัญหาการตัดสินใจตามลำดับ

• ปัญหาการใช้แรงงาน

• ปัญหาการจัดการสินค้าคงคลัง

• ปัญหากระเป๋าเป้สะพายหลัง: จากชุดวัตถุจำนวนไม่จำกัดที่มีคุณสมบัติ "ต้นทุน" และ "น้ำหนัก" จะต้องเลือกวัตถุจำนวนหนึ่งในลักษณะเพื่อให้ได้ต้นทุนรวมสูงสุดโดยมีน้ำหนักรวมที่จำกัด

• อัลกอริธึม Floyd-Warshall: ค้นหาระยะทางที่สั้นที่สุดระหว่างจุดยอดทั้งหมดของกราฟกำกับแบบถ่วงน้ำหนัก

• อัลกอริธึมของ Bellman-Ford: หาเส้นทางที่สั้นที่สุดในกราฟถ่วงน้ำหนักระหว่างจุดยอดที่กำหนดสองจุด

• ชุดจุดยอดอิสระสูงสุดในต้นไม้: จากต้นไม้ ให้ค้นหาชุดจุดยอดสูงสุดโดยที่ไม่มีจุดสองจุดเชื่อมต่อกันด้วยขอบ

ตัวอย่าง: การจัดสรรทรัพยากรที่เหมาะสมที่สุด

เงินทุน 40 ล้านรูเบิล ผู้ลงทุนจะต้องลงทุนในสี่ โครงการลงทุนเพื่อให้ได้รายได้สูงสุด ตารางแสดงความสามารถในการทำกำไรของโครงการ (การลงทุนทวีคูณของ 8 ล้านรูเบิล)

คุณ

กำไรจากการดำเนินการ

f4(ยู)

f3(ยู)

f2(ยู)

f1(ยู)

55

39

120

115

10 0

120

135

134

14 0

145

158

147

สารละลาย:

นี่เป็นปัญหาการเขียนโปรแกรมแบบไดนามิก การแก้ปัญหาประกอบด้วยสองขั้นตอน ในระยะแรก (ตั้งแต่ต้นจนจบ) เรามองหาวิธีแก้ปัญหาที่ดีที่สุดแบบมีเงื่อนไข ขั้นที่สอง (ตั้งแต่ต้นจนจบ) เรามองหาแนวทางแก้ไขปัญหาที่ดีที่สุด

ขั้นที่ 1

เรากระจายเงินทุนระหว่างสี่โครงการและคำนวณกำไรที่ได้รับ ล (ฉัน ), ฉัน = 8,16,24,32,40.

1 ขั้นตอน: เงินสดกำลังลงทุนในโครงการที่สี่

แอล(8)= 55

ลิตร(16)=58

ลิตร(24)=90

ลิตร(32)=100

ลิตร(40)=140

ขั้นตอนที่ 2: กองทุนมีการลงทุนในโครงการที่สี่และสาม

คุณ

กำไรจากการดำเนินการ

1 ขั้นตอน

f3(ยู)

55

39

10 0

120

14 0

145

ขั้นตอนที่ 3: กองทุนมีการลงทุนในโครงการที่สี่ สาม (ขั้นตอนที่ 2) และโครงการที่สอง

คุณ

กำไรจากการดำเนินการ

ขั้นตอนที่ 2

ฉ 2(ยู)

94

108

120

135

135

175

158

175

134

214

147

ขั้นที่ 2:

ในขั้นตอนที่สี่ เราเลือกมูลค่ากำไรสูงสุดที่ได้รับ L (40) = 214

และการส่งคืนในลำดับย้อนกลับจากตารางหนึ่งไปอีกตารางหนึ่ง (จาก 4 ขั้นตอนถึง 1) เราเลือกมูลค่ารายได้ที่ได้รับค่า 214

รายได้สูงสุด 214 ล้านรูเบิล จากเงินลงทุนสามารถรับได้โดยมีการกระจายเงินทุนดังนี้

1 โครงการ – 0 ล้านรูเบิล

2 โครงการ – 24 ล้านรูเบิล

โครงการที่ 3 – 8 ล้านรูเบิล

4 โครงการ – 8 ล้านรูเบิล

การรวมวัสดุใหม่:

5. สรุปบทเรียน: ข้อสรุป, การประเมิน, การบ้าน:

(2) ข้อ 5.1

Ср12: การก่อตัวและการดูดซึมเนื้อหาของเนื้อหาทางทฤษฎี

ลายเซ็นของอาจารย์

วิธีการโปรแกรมแบบไดนามิกใช้เพื่อแก้ปัญหาการหาค่าเหมาะที่สุด ซึ่งฟังก์ชันวัตถุประสงค์หรือข้อจำกัด หรือทั้งข้อแรกและข้อที่สอง มีลักษณะการพึ่งพาแบบไม่เชิงเส้นไปพร้อมๆ กัน

ส่วนนี้แสดงด้วยเครื่องคิดเลขต่อไปนี้:

1. - การกระจายการลงทุนระหว่างวิสาหกิจ P 1, P 2,..., P n. จำนวนเงินลงทุน E Conv. ถ้ำ หน่วย
2. ปัญหาการจัดสรรทรัพยากร การดำเนินงานของสององค์กรมีการวางแผนไว้เป็นเวลา n ปี ทรัพยากรเบื้องต้นเท่ากับ s 0
3. งานคลังสินค้า: เขียน โปรแกรมที่เหมาะสมที่สุดผลลัพธ์ของผลิตภัณฑ์ X ซึ่งช่วยลดต้นทุนรวมขององค์กรให้เหลือน้อยที่สุด
4. ปัญหากระเป๋าเป้สะพายหลัง (แก้ปัญหาการบรรทุกยานพาหนะ)

ปัญหาการจัดสรรการลงทุน

ในงาน ประเภทนี้มีการระบุจำนวนเงินลงทุน (หรือจำนวนเงินเพื่อการกระจาย) และตารางกำไรที่วางแผนไว้ หากไม่ได้ระบุจำนวนเงินสำหรับการแจกแจงอย่างชัดเจน คุณสามารถดูได้จากตาราง - เท่ากับค่าสูงสุด x i (บรรทัดสุดท้ายของตาราง)

ตารางสามารถมีรูปลักษณ์ที่แตกต่างกันได้
ตารางที่ 1 - เวอร์ชันแรกของตารางข้อมูลต้นฉบับ

x	ฉ 1 (x)	ฉ 2 (x)	ฉ 3 (x)
5 *

* - โดยที่ค่า 5 คือค่าสูงสุด (จำนวนเงินสำหรับการแจกแจง)

ตารางที่ 2 - ตารางข้อมูลต้นฉบับเวอร์ชันที่สอง

x
ฉ 1 (x)
ฉ 2 (x)
ฉ 3 (x)

งานตัวอย่าง.
มีการจัดสรรหน่วยกองทุนสำหรับสององค์กร วิธีกระจายกองทุนทั้งหมดในช่วง 4 ปีเพื่อให้รายได้มากที่สุดหากทราบว่ารายได้จาก x หน่วยของกองทุนที่ลงทุนในองค์กรแรกเท่ากับ f 1 (x) และรายได้จากหน่วย y ของกองทุนที่ลงทุน ในองค์กรที่สองเท่ากับ f 2(y) ยอดคงเหลือของกองทุน ณ สิ้นปีคือ g 1 (x) สำหรับองค์กรแรกและ g 2 (y) สำหรับองค์กรที่สอง แก้ไขปัญหาโดยใช้วิธีการเขียนโปรแกรมแบบไดนามิก

เมื่อป้อนข้อมูล สามารถเว้นบรรทัดศูนย์แรกให้ว่างได้

บริการปัญหาการจัดสรรการลงทุนใช้วิธีการกวาดย้อนหลัง

วิธีการผ่าน

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

ในบริการ Sweep Method คุณต้องเลือกวิธีการแก้ปัญหาด้วย: ขั้นตอนการกวาดไปข้างหน้าหรือย้อนกลับ

ปัญหาการเปลี่ยนอุปกรณ์

วัตถุประสงค์ของการแก้ปัญหาคือเพื่อกำหนดขั้นตอนของอัลกอริทึม (ในปีใด) ที่ต้องเปลี่ยนอุปกรณ์ เพื่อจุดประสงค์นี้เราจึงแนะนำ ระยะเวลาการดำเนินงาน(เป็นปี) และ ต้นทุนของอุปกรณ์ใหม่- หลังจากนี้คุณจะต้องกรอกตารางรายได้ r(t) และ มูลค่าคงเหลือส(ท)
ปัญหาการเปลี่ยนอุปกรณ์

การวางแผนสายการผลิต

งาน การประมวลผลตามลำดับบนเครื่องสองเครื่อง N ชิ้นส่วนที่แตกต่างกัน หากทราบเวลาการประมวลผล A i และ B i ของส่วนที่ i บนเครื่องที่เกี่ยวข้อง จำเป็นต้องค้นหาลำดับการประมวลผลที่ช่วยลดเวลาหยุดทำงานของเครื่องที่สองให้เหลือน้อยที่สุดและด้วยเหตุนี้จึงลดลง เวลาทั้งหมดการประมวลผลชิ้นส่วน

มีทรัพยากรจำนวนหนึ่ง 0 ที่ต้องแจกจ่ายให้กับองค์กรธุรกิจ n แห่งสำหรับกิจกรรมปัจจุบันในระหว่างช่วงเวลาที่อยู่ระหว่างการตรวจสอบ (เดือน ไตรมาส ครึ่งปี ปี ฯลฯ) เพื่อให้ได้ยอดรวม กำไรสูงสุด- ขนาดของการลงทุนทรัพยากร x i (;) ในกิจกรรมของแต่ละองค์กรทางเศรษฐกิจคือผลคูณของมูลค่าที่แน่นอน h เป็นที่ทราบกันดีว่าองค์กรทางเศรษฐกิจแต่ละแห่ง ขึ้นอยู่กับปริมาณเงินทุนที่ใช้ x i สำหรับช่วงเวลาที่อยู่ระหว่างการตรวจสอบ นำมาซึ่งผลกำไรในจำนวน f i (x i) (ไม่ขึ้นอยู่กับการลงทุนทรัพยากรในหน่วยงานทางเศรษฐกิจอื่น ๆ)

ลองจินตนาการถึงกระบวนการกระจายทรัพยากรระหว่างองค์กรธุรกิจเป็นกระบวนการจัดการแบบ n ขั้นตอน (หมายเลขขั้นตอนเกิดขึ้นพร้อมกับหมายเลขตามเงื่อนไขขององค์กรธุรกิจ) ให้ sk () เป็นพารามิเตอร์สถานะเช่น จำนวนเงินที่มีอยู่หลังจากขั้นตอนที่ k เพื่อแจกจ่ายให้กับองค์กรธุรกิจที่เหลือ (n - k) จากนั้นจึงสามารถเขียนสมการสถานะได้ แบบฟอร์มต่อไปนี้:

ให้เราแนะนำการพิจารณาฟังก์ชัน - กำไรรวมที่ดีที่สุดตามเงื่อนไขที่ได้รับจาก k-th, (k+1) - th, ..., หน่วยงานทางเศรษฐกิจลำดับที่ n หากทรัพยากรมีจำนวน s k-1 () มีการกระจายอย่างเหมาะสมระหว่างกัน เป็นไปได้หลายอย่าง การตัดสินใจของฝ่ายบริหารสัมพันธ์กับขนาดของทรัพยากรที่กระจายในขั้นตอนที่ k สามารถแสดงได้ดังนี้:

จากนั้นสมการที่เกิดซ้ำของ R.E. Bellman (แผนภาพย้อนกลับ) จะมีลักษณะดังนี้:

ตัวอย่าง.มีทรัพยากรจำนวนหนึ่ง s 0 =100 ซึ่งจะต้องกระจายระหว่าง n=4 องค์กรธุรกิจสำหรับกิจกรรมปัจจุบันในช่วงระยะเวลาที่อยู่ระหว่างการตรวจสอบ (เดือน) เพื่อให้ได้กำไรสูงสุดทั้งหมด ขนาดของการลงทุนทรัพยากร x i (;) ในกิจกรรมของแต่ละเอนทิตีทางเศรษฐกิจคือผลคูณของค่า h = 20 และระบุโดยเวกเตอร์ Q เป็นที่ทราบกันว่าแต่ละเอนทิตีทางเศรษฐกิจขึ้นอยู่กับปริมาณเงินทุนที่ใช้ x i สำหรับช่วงเวลาที่อยู่ระหว่างการตรวจสอบ นำมาซึ่งกำไรจำนวน f i (x i) () (ไม่ขึ้นอยู่กับการลงทุนทรัพยากรในหน่วยงานทางเศรษฐกิจอื่น ๆ ):

มีความจำเป็นต้องกำหนดจำนวนทรัพยากรที่ควรจัดสรรให้กับแต่ละองค์กรเพื่อให้กำไรรวมสูงสุด

สารละลาย.มาสร้างสมการที่เกิดซ้ำของ Bellman กัน (รูปแบบผกผัน):

ให้เรากำหนดค่าสูงสุดตามเงื่อนไขตาม (13) ผลการคำนวณแสดงไว้ในตารางที่ 1

ตารางที่ 1. การคำนวณ Optima แบบมีเงื่อนไข

		22+20=42
		22+33=55		17+42=59
		22+46=68		17+55=72		14+59=73
		67+20=87

จากผลลัพธ์ของการเพิ่มประสิทธิภาพตามเงื่อนไข เราจะกำหนดการจัดสรรทรัพยากรที่เหมาะสมที่สุด:

ดังนั้นการจัดสรรทรัพยากรที่เหมาะสมที่สุดคือ:

ซึ่งจะให้ผลกำไรสูงสุดในจำนวน 87 หน่วยธรรมดา ถ้ำ หน่วย

คำตอบ:การจัดสรรทรัพยากรอย่างเหมาะสม: ซึ่งให้ผลกำไรสูงสุดจาก 87 หน่วยทั่วไป ถ้ำ หน่วย

บทสรุป

การเขียนโปรแกรมแบบไดนามิกเป็นขอบเขตของการเขียนโปรแกรมทางคณิตศาสตร์ที่มีชุดเทคนิคและเครื่องมือในการค้นหา ทางออกที่ดีที่สุดตลอดจนการเพิ่มประสิทธิภาพแต่ละขั้นตอนในระบบและพัฒนากลยุทธ์การจัดการ กล่าวคือ กระบวนการจัดการสามารถแสดงเป็นกระบวนการหลายขั้นตอนได้ การเขียนโปรแกรมแบบไดนามิกโดยใช้การวางแผนทีละขั้นตอนช่วยให้ไม่เพียงทำให้การแก้ปัญหาง่ายขึ้นเท่านั้น แต่ยังช่วยแก้ปัญหาที่ไม่สามารถใช้วิธีการต่างๆ ได้อีกด้วย การวิเคราะห์ทางคณิตศาสตร์- การลดความซับซ้อนของการแก้ปัญหาทำได้โดยการลดจำนวนตัวเลือกที่กำลังศึกษาอยู่อย่างมาก เนื่องจากแทนที่จะแก้ไขปัญหาหลายตัวแปรที่ซับซ้อนเพียงครั้งเดียว วิธีการวางแผนทีละขั้นตอนเกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างง่ายหลายครั้ง เมื่อวางแผนกระบวนการทีละขั้นตอน เราดำเนินการจากผลประโยชน์ของกระบวนการทั้งหมดโดยรวม เช่น เมื่อทำการตัดสินใจในขั้นตอนใดขั้นตอนหนึ่ง จำเป็นอย่างยิ่งที่จะต้องคำนึงถึงเป้าหมายสุดท้ายเสมอ อย่างไรก็ตาม การเขียนโปรแกรมแบบไดนามิกก็มีข้อเสียเช่นกัน ต่างจากการเขียนโปรแกรมเชิงเส้นตรงที่ วิธีเริมเป็นสากล ไม่มีวิธีการดังกล่าวในการเขียนโปรแกรมแบบไดนามิก แต่ละงานมีความยากในตัวเอง และในแต่ละกรณีจำเป็นต้องหาวิธีแก้ไขที่เหมาะสมที่สุด ข้อเสียของการเขียนโปรแกรมแบบไดนามิกคือความซับซ้อนในการแก้ปัญหาหลายมิติ ปัญหาการเขียนโปรแกรมแบบไดนามิกต้องเป็นไปตามเงื่อนไขสองประการ เงื่อนไขแรกมักเรียกว่าเงื่อนไขที่ไม่มีผลกระทบ และเงื่อนไขที่สองคือเงื่อนไขเพิ่มเติม ฟังก์ชั่นวัตถุประสงค์งาน ในทางปฏิบัติ มีปัญหาในการวางแผนซึ่งปัจจัยสุ่มมีบทบาทสำคัญ ซึ่งมีอิทธิพลต่อทั้งสถานะของระบบและผลที่ได้ มีความแตกต่างระหว่างปัญหาการเขียนโปรแกรมไดนามิกที่กำหนดและแบบสุ่ม ในปัญหาที่กำหนด การควบคุมที่เหมาะสมที่สุดจะไม่ซ้ำกันและระบุไว้ล่วงหน้าเป็น โปรแกรมที่ยากลำบากการกระทำ ในปัญหาสุ่ม การควบคุมที่เหมาะสมที่สุดจะเป็นแบบสุ่ม และเลือกในระหว่างกระบวนการ ขึ้นอยู่กับสถานการณ์สุ่ม ในรูปแบบที่กำหนดขึ้น จะต้องผ่านกระบวนการเป็นขั้นตอนตั้งแต่ต้นจนจบ นอกจากนี้ยังมีเงื่อนไขแบบมีเงื่อนไขทั้งหมดในแต่ละขั้นตอน การควบคุมที่เหมาะสมที่สุดแต่จากการควบคุมทั้งหมดนี้ มีเพียงการควบคุมเดียวเท่านั้นที่ถูกดำเนินการในท้ายที่สุด นี่ไม่ใช่กรณีในรูปแบบสุ่ม การควบคุมที่เหมาะสมตามเงื่อนไขแต่ละรายการสามารถนำไปใช้ได้จริง หากกระบวนการสุ่มก่อนหน้านี้นำระบบไปสู่สถานะที่สอดคล้องกัน หลักการของการเพิ่มประสิทธิภาพเป็นพื้นฐานสำหรับการแก้ปัญหาการเขียนโปรแกรมแบบไดนามิกทีละขั้นตอน ตัวแทนทั่วไป งานทางเศรษฐกิจการเขียนโปรแกรมแบบไดนามิกคือสิ่งที่เรียกว่าปัญหาการผลิตและการจัดเก็บ ปัญหาการกระจายการลงทุน ปัญหาการจัดตารางการผลิต และอื่นๆ ปัญหาการเขียนโปรแกรมแบบไดนามิกใช้ในการวางแผนกิจกรรมขององค์กรโดยคำนึงถึงการเปลี่ยนแปลงความต้องการผลิตภัณฑ์เมื่อเวลาผ่านไป ในการกระจายทรัพยากรอย่างเหมาะสมระหว่างองค์กรในทิศทางหรือเวลา คำอธิบายของลักษณะของการเขียนโปรแกรมแบบไดนามิกและประเภทของปัญหาที่สามารถกำหนดได้ภายในกรอบงานจะต้องมีความทั่วไปและค่อนข้างคลุมเครือเนื่องจากมีความหลากหลายมากมาย งานต่างๆเหมาะสมกับรูปแบบการเขียนโปรแกรมแบบไดนามิก ศึกษาเท่านั้น จำนวนมากตัวอย่างให้ความเข้าใจที่ชัดเจนเกี่ยวกับโครงสร้างของการเขียนโปรแกรมแบบไดนามิก

เชิงนามธรรม

การแนะนำ

การเขียนโปรแกรมแบบไดนามิก- วิธีการปรับให้เหมาะสมที่สุดที่ปรับให้เข้ากับการปฏิบัติงานซึ่งกระบวนการตัดสินใจสามารถแบ่งออกเป็นขั้นตอน (ขั้นตอน) การดำเนินการดังกล่าวเรียกว่าหลายขั้นตอน

จุดเริ่มต้นของการพัฒนาการเขียนโปรแกรมแบบไดนามิกมีอายุย้อนกลับไปในยุค 50 ของศตวรรษที่ยี่สิบ และมีความเกี่ยวข้องกับชื่อของริชาร์ด เออร์เนสต์ เบลล์แมน

หากโมเดลการเขียนโปรแกรมเชิงเส้นสามารถนำมาใช้ในทางเศรษฐศาสตร์เพื่อตัดสินใจในการวางแผนขนาดใหญ่ในสถานการณ์ที่ซับซ้อน โมเดลการเขียนโปรแกรมแบบไดนามิกจะถูกใช้เพื่อแก้ปัญหาที่มีขนาดเล็กกว่ามาก:

ü เมื่อพัฒนากฎการจัดการสินค้าคงคลัง

ü เมื่อกระจายทรัพยากรการลงทุนระหว่างโครงการทางเลือก

ü เมื่อจัดทำแผนปฏิทินสำหรับปัจจุบันและ ยกเครื่องอุปกรณ์ที่ซับซ้อนและการเปลี่ยนทดแทน ฯลฯ

1. การกำหนดทั่วไปของปัญหาการเขียนโปรแกรมแบบไดนามิก

การเขียนโปรแกรมสมการเบลล์แมนแบบไดนามิก

กระบวนการควบคุมถือเป็นกระบวนการต่างๆ เช่น กระบวนการกระจายเงินทุนระหว่างองค์กร การใช้ทรัพยากรเป็นเวลาหลายปี การเปลี่ยนอุปกรณ์ เป็นต้น จากผลของการควบคุม ระบบ (วัตถุควบคุม) S จะถูกถ่ายโอนจากสถานะเริ่มต้น s 0เพื่อระบุ n - ให้แบ่งการควบคุมออกเป็น n ขั้นตอน กล่าวคือ การตัดสินใจจะทำตามลำดับในแต่ละขั้นตอน และการควบคุมที่ถ่ายโอนระบบ S จากสถานะเริ่มต้นไปยังสถานะสุดท้ายคือชุดของการตัดสินใจด้านการจัดการทีละขั้นตอน

ให้เราแสดงด้วย X เค การตัดสินใจของฝ่ายบริหาร ขั้นตอนที่ 1(k=1, 2, …, น) ตัวแปร X เค ปฏิบัติตามข้อ จำกัด บางประการและในแง่นี้เรียกว่ายอมรับได้ (X เค อาจเป็นตัวเลข จุดในปริภูมิ n มิติ หรือคุณลักษณะเชิงคุณภาพก็ได้)

ให้ X=(X 1, เอ็กซ์ 2, …, เอ็กซ์ n ) - ควบคุมที่ถ่ายโอนระบบ S จากสถานะ s 0เพื่อระบุ n - ให้เราแสดงด้วย s เค สถานะของระบบ (แสดงคุณลักษณะโดยชุดพารามิเตอร์บางชุดและค่าเฉพาะ) หลังจากขั้นตอนการควบคุม k นอกจากนี้สถานะของระบบ เค ในตอนท้ายของขั้นตอนที่ k ขึ้นอยู่กับสถานะก่อนหน้าเท่านั้น เค-1 และการตัดสินใจของฝ่ายบริหารในขั้นตอนที่ k-th X เค (เช่นไม่ได้ขึ้นอยู่กับเงื่อนไขก่อนหน้าและการตัดสินใจของฝ่ายบริหารโดยตรง) ข้อกำหนดนี้เรียกว่า "ไม่มีผล" และสามารถแสดงได้ด้วยสมการสถานะต่อไปนี้:

ดังนั้นเราจึงได้ลำดับของสถานะ s0, s1, …, sk-1, sk, …, sn-1, sn จากนั้นกระบวนการจัดการแบบ n ขั้นตอนสามารถอธิบายได้เป็นแผนผังดังนี้:

ให้ตัวบ่งชี้ประสิทธิภาพของขั้นตอนที่ k แสดงโดยฟังก์ชันบางอย่าง:

และประสิทธิภาพของกระบวนการหลายขั้นตอนทั้งหมดที่อยู่ระหว่างการพิจารณาคือฟังก์ชันเสริมต่อไปนี้:

จากนั้น ปัญหาการหาค่าเหมาะที่สุดทีละขั้นตอน (ปัญหาการโปรแกรมแบบไดนามิก) มีสูตรดังนี้: กำหนดตัวควบคุม X ที่ยอมรับได้ ซึ่งจะถ่ายโอนระบบ S จากสถานะ s0 ไปยังสถานะ sn โดยที่ฟังก์ชันวัตถุประสงค์ Z รับค่าที่ใหญ่ที่สุด (น้อยที่สุด)

มีปัญหาการเขียนโปรแกรมแบบไดนามิก คุณสมบัติดังต่อไปนี้:

ปัญหาการปรับให้เหมาะสมถูกตีความว่าเป็นกระบวนการควบคุมแบบ n ขั้นตอน

ฟังก์ชันวัตถุประสงค์จะเท่ากับผลรวมของฟังก์ชันวัตถุประสงค์ของแต่ละขั้นตอน

การเลือกการควบคุมในขั้นตอนที่ k ขึ้นอยู่กับสถานะของระบบในขั้นตอนนี้เท่านั้น และไม่ส่งผลกระทบต่อขั้นตอนก่อนหน้า (ไม่มี ข้อเสนอแนะ).

สถานะ sk หลังขั้นตอนการควบคุม k-th ขึ้นอยู่กับสถานะก่อนหน้า sk-1 และการควบคุม Xk (“ไม่มีผลตามมา”) เท่านั้น

ในแต่ละขั้นตอน การควบคุม Xk ขึ้นอยู่กับจำนวนตัวแปรควบคุมที่มีจำกัด และสถานะ sk ขึ้นอยู่กับพารามิเตอร์จำนวนจำกัด

2. หลักการออปติคัลลิตี้และสมการเบลล์แมน

หลักการเพิ่มประสิทธิภาพได้รับการคิดค้นครั้งแรกโดย Richard Ernest Bellman ในปี 1953 (ตามที่ E.S. Wentzel ตีความ):

ไม่ว่าสถานะของระบบจะเป็นผลจากขั้นตอนจำนวนเท่าใดก็ตาม ในขั้นตอนถัดไปจำเป็นต้องเลือกการควบคุมในลักษณะที่เมื่อรวมกับการควบคุมที่เหมาะสมที่สุดในขั้นตอนต่อๆ ไปทั้งหมด จะนำไปสู่การได้รับที่เหมาะสมที่สุดในขั้นตอนที่เหลือทั้งหมด รวมถึงอันนี้ด้วย

อีกครั้ง. เบลล์แมนยังได้กำหนดเงื่อนไขที่หลักการเป็นจริงด้วย ข้อกำหนดหลักคือกระบวนการควบคุมจะต้องไม่มีผลป้อนกลับ เช่น การควบคุมในขั้นตอนนี้ไม่ควรส่งผลต่อขั้นตอนก่อนหน้า

พิจารณาปัญหาการเขียนโปรแกรมไดนามิกทั่วไปที่ให้ไว้ข้างต้น ในแต่ละขั้นตอน ยกเว้นขั้นตอนสุดท้ายสำหรับสถานะใดๆ ของระบบ เค-1 การตัดสินใจของฝ่ายบริหาร X เค จำเป็นต้องเลือก "ด้วยความระมัดระวัง" เนื่องจากตัวเลือกนี้ส่งผลต่อสถานะที่ตามมาของระบบ sk .

ในขั้นตอนสุดท้ายขึ้นอยู่กับสถานะของระบบ n-1 การตัดสินใจของฝ่ายบริหาร X n สามารถวางแผนได้อย่างเหมาะสมในพื้นที่ เช่น ขึ้นอยู่กับการพิจารณาของขั้นตอนนี้เท่านั้น

ลองพิจารณาดู ครั้งสุดท้ายขั้นตอน:

ส n-1 - สถานะของระบบเมื่อเริ่มต้นขั้นตอนที่ n

ส n - สถานะสุดท้ายของระบบ

เอ็กซ์ n - การควบคุมในขั้นตอนที่ n;

ฉ n (ส n-1 , เอ็กซ์ n ) คือฟังก์ชันวัตถุประสงค์ (ผลตอบแทน) ของขั้นตอนที่ n

ตามหลักการหาค่าเหมาะที่สุด X n จะต้องเลือกในลักษณะที่สำหรับสถานะใด ๆ ของระบบ n-1 รับฟังก์ชันวัตถุประสงค์ที่เหมาะสมที่สุดในขั้นตอนนี้

ให้เราแสดงด้วยค่าที่เหมาะสม (เพื่อความแน่นอนเราจะรับค่าสูงสุด) ของฟังก์ชันวัตถุประสงค์ - ตัวบ่งชี้ประสิทธิภาพของขั้นตอนที่ n โดยมีเงื่อนไขว่าที่จุดเริ่มต้นของขั้นตอนสุดท้ายระบบ S อยู่ในสถานะที่กำหนดเอง sn-1 และในขั้นตอนสุดท้าย การควบคุมก็เหมาะสมที่สุด

เรียกว่าค่าสูงสุดแบบมีเงื่อนไขของฟังก์ชันวัตถุประสงค์ในขั้นตอนที่ n และถูกกำหนดโดยสูตรต่อไปนี้:

การขยายใหญ่สุดจะดำเนินการกับส่วนควบคุมที่ยอมรับได้ทั้งหมด Xn

คำตอบ Xn ที่จะบรรลุผลสำเร็จนั้นขึ้นอยู่กับ sn-1 และเรียกว่าคำตอบที่เหมาะสมที่สุดแบบมีเงื่อนไขในขั้นตอนที่ n ลองแสดงมันด้วย

การแก้ปัญหามิติเดียว การเพิ่มประสิทธิภาพในท้องถิ่นตามสมการ (5) เรากำหนดสำหรับทุกคน รัฐที่เป็นไปได้ sn-1 สองฟังก์ชัน และ

ลองพิจารณาปัญหาสองขั้นตอน: เพิ่ม (n-1) -th ในขั้นตอนที่ n

สำหรับสถานะ sn-2 ใดๆ การตัดสินใจด้านการจัดการตามอำเภอใจ Xn-1 และการควบคุมที่เหมาะสมที่สุดในขั้นตอนที่ n ค่าของฟังก์ชันวัตถุประสงค์ในสองขั้นตอนสุดท้ายจะถูกคำนวณโดยสูตร:

ตามหลักการหาค่าเหมาะที่สุดของ Bellman สำหรับค่าใดๆ n-2 ต้องเลือกวิธีแก้ปัญหาเพื่อที่เมื่อรวมกับการควบคุมที่เหมาะสมที่สุดในขั้นตอนสุดท้าย (ที่ n) จะนำไปสู่ฟังก์ชันวัตถุประสงค์ที่เหมาะสมที่สุดในสองขั้นตอนสุดท้าย ดังนั้นจึงจำเป็นต้องค้นหานิพจน์ที่เหมาะสมที่สุด (6) สำหรับการตัดสินใจด้านการจัดการที่ยอมรับได้ทั้งหมด Xn-1 :

เรียกว่าค่าสูงสุดแบบมีเงื่อนไขของฟังก์ชันวัตถุประสงค์ภายใต้การควบคุมที่เหมาะสมที่สุดในสองขั้นตอนสุดท้าย ควรสังเกตว่านิพจน์ในวงเล็บปีกกาในสูตร (6) ขึ้นอยู่กับ sn-2 และ Xn-1 เท่านั้น เนื่องจากสามารถหา sn-1 ได้จากสมการสถานะ (1) ด้วย:

การควบคุมที่สอดคล้องกัน Xn-1 ที่ขั้นตอนที่ (n-1) แสดงโดยและเรียกว่าการควบคุมที่เหมาะสมตามเงื่อนไขที่ขั้นตอนที่ (n-1)

ออพติมาแบบมีเงื่อนไขของฟังก์ชันวัตถุประสงค์ถูกกำหนดในทำนองเดียวกันสำหรับการควบคุมที่เหมาะสมที่สุดที่ขั้นตอน (n-k+1) โดยเริ่มจากจุดที่ k ถึงจุดสิ้นสุด โดยมีเงื่อนไขว่าที่จุดเริ่มต้นของขั้นตอนที่ k ระบบจะอยู่ในสถานะ sk -1:

การควบคุม Xk ที่ขั้นตอนที่ k ซึ่งบรรลุถึงค่าสูงสุดใน (8) จะถูกแสดงและเรียกว่าการควบคุมที่เหมาะสมที่สุดแบบมีเงื่อนไขที่ขั้นตอนที่ k

สมการ (5) และ (8) เรียกว่าสมการเบลล์แมนที่เกิดซ้ำ (รูปแบบย้อนกลับ) กระบวนการแก้สมการเหล่านี้เรียกว่าการปรับให้เหมาะสมที่มีข้อจำกัด

จากผลของการปรับให้เหมาะสมตามเงื่อนไข จะได้ลำดับสองลำดับ:

, …, - จุดสูงสุดแบบมีเงื่อนไขของฟังก์ชันวัตถุประสงค์ที่จุดสุดท้าย, สองจุดสุดท้าย, …, ที่ n ขั้นตอน;

, …, - การควบคุมที่เหมาะสมที่สุดตามเงื่อนไขที่ n, (n-1) - th, …, ในขั้นตอนที่ 1

เมื่อใช้ลำดับเหล่านี้ เราจะพบวิธีแก้ไขปัญหาการเขียนโปรแกรมไดนามิกที่กำหนด n และ s0:

ด้วยเหตุนี้ เราจึงได้รับแนวทางแก้ไขที่เหมาะสมที่สุดสำหรับปัญหาการเขียนโปรแกรมแบบไดนามิก:

การใช้เหตุผลที่คล้ายกัน เราสามารถสร้างแผนการปรับให้เหมาะสมตามเงื่อนไขโดยตรงได้:

แนวทางแก้ไขปัญหาที่ดีที่สุดในกรณีนี้พบได้ตามรูปแบบต่อไปนี้:

ดังนั้นการสร้างแบบจำลองการเขียนโปรแกรมแบบไดนามิกและการแก้ปัญหาตามนั้น มุมมองทั่วไปสามารถแสดงได้เป็นขั้นตอนดังนี้

เลือกวิธีการแบ่งกระบวนการจัดการออกเป็นขั้นตอน

กำหนดพารามิเตอร์ของรัฐ เค และ ตัวแปรควบคุมเอ็กซ์ เค ในแต่ละขั้นตอนจะมีการเขียนสมการสถานะ

3. ป้อนฟังก์ชันวัตถุประสงค์ของขั้นตอนที่ k และฟังก์ชันวัตถุประสงค์ทั้งหมด เช่นเดียวกับการปรับให้เหมาะสมแบบมีเงื่อนไขและการควบคุมที่เหมาะสมที่สุดแบบมีเงื่อนไขที่ขั้นตอนที่ k ()

สมการที่เกิดซ้ำของ Bellman ถูกเขียนตามแผนผกผันหรือแผนโดยตรง และหลังจากดำเนินการปรับให้เหมาะสมตามเงื่อนไขแล้ว จะได้ลำดับสองลำดับ: () และ ()

กำหนด ค่าที่เหมาะสมที่สุดฟังก์ชันวัตถุประสงค์และแนวทางแก้ไขที่เหมาะสมที่สุด

3. ปัญหาการจัดสรรทรัพยากร

มีทรัพยากรจำนวนหนึ่ง s0 ที่ต้องแจกจ่ายให้กับองค์กรธุรกิจ n แห่งสำหรับกิจกรรมปัจจุบันในระหว่างช่วงเวลาที่อยู่ระหว่างการตรวจสอบ (เดือน ไตรมาส ครึ่งปี ปี ฯลฯ) เพื่อให้ได้กำไรสูงสุดทั้งหมด ขนาดของการลงทุนทรัพยากร xi (;) ในกิจกรรมของแต่ละองค์กรทางเศรษฐกิจคือผลคูณของมูลค่าที่แน่นอน h เป็นที่ทราบกันว่าองค์กรทางเศรษฐกิจแต่ละแห่ง ขึ้นอยู่กับปริมาณเงินทุนที่ใช้ xi ในช่วงที่อยู่ระหว่างการตรวจสอบ นำมาซึ่งผลกำไรในจำนวน fi(xi) (ไม่ได้ขึ้นอยู่กับการลงทุนทรัพยากรในหน่วยงานทางเศรษฐกิจอื่น ๆ)

ลองจินตนาการถึงกระบวนการกระจายทรัพยากรระหว่างองค์กรธุรกิจเป็นกระบวนการจัดการแบบ n ขั้นตอน (หมายเลขขั้นตอนเกิดขึ้นพร้อมกับหมายเลขตามเงื่อนไขขององค์กรธุรกิจ) ให้ sk() เป็นพารามิเตอร์สถานะ เช่น จำนวนเงินที่มีอยู่หลังจากขั้นตอนที่ k เพื่อแจกจ่ายให้กับองค์กรธุรกิจที่เหลือ (n - k) จากนั้นสมการสถานะสามารถเขียนได้ในรูปแบบต่อไปนี้:

ให้เราแนะนำการพิจารณาฟังก์ชัน - กำไรรวมที่เหมาะสมที่สุดตามเงื่อนไขที่ได้รับจาก k-th, (k+1) - th, ..., n-th หน่วยงานทางเศรษฐกิจหากทรัพยากรในปริมาณ sk-1 () กระจายระหว่างกันอย่างเหมาะสมที่สุด ชุดของการตัดสินใจด้านการจัดการที่เป็นไปได้เกี่ยวกับขนาดของทรัพยากรที่จัดสรรในขั้นตอนที่ k สามารถแสดงได้ดังนี้:

จากนั้นสมการที่เกิดซ้ำของ R.E. Bellman (แผนภาพย้อนกลับ) จะมีลักษณะดังนี้:

ตัวอย่าง.มีทรัพยากรจำนวนหนึ่ง s0=100 ซึ่งจะต้องกระจายให้กับองค์กรธุรกิจ n=4 แห่งสำหรับกิจกรรมปัจจุบันในช่วงระยะเวลาที่อยู่ระหว่างการตรวจสอบ (เดือน) เพื่อให้ได้กำไรสูงสุดทั้งหมด ขนาดของการลงทุนทรัพยากร xi (;) ในกิจกรรมของแต่ละเอนทิตีทางเศรษฐกิจคือผลคูณของค่า h=20 และระบุโดยเวกเตอร์ Q เป็นที่ทราบกันว่าแต่ละเอนทิตีทางเศรษฐกิจ ขึ้นอยู่กับปริมาณเงินทุนที่ใช้ xi สำหรับช่วงเวลาที่อยู่ระหว่างการพิจารณา นำมาซึ่งกำไรเป็นจำนวน fi(xi) () (ไม่ขึ้นอยู่กับการลงทุนทรัพยากรในหน่วยงานทางเศรษฐกิจอื่น ๆ ):

มีความจำเป็นต้องกำหนดจำนวนทรัพยากรที่ควรจัดสรรให้กับแต่ละองค์กรเพื่อให้กำไรรวมสูงสุด

สารละลาย.มาสร้างสมการที่เกิดซ้ำของ Bellman กัน (รูปแบบผกผัน):

ให้เรากำหนดค่าสูงสุดตามเงื่อนไขตาม (13) ผลการคำนวณแสดงไว้ในตารางที่ 1

ตารางที่ 1. การคำนวณ Optima แบบมีเงื่อนไข

ส เค-1 x เค ส เค k=3k=2k=1 123456789101112000000000000200200+20=20 22 200+22=22 2200+22=22 22020022+0=22 17+0=1714+0=14400400+33=33 42 200+42=42 4200+42=42 420202022+20=42 17+22=3914+22=3640021+0=2120+0=2026+0=26600600+46=46 55 200+55=55 59 20 0+59=59 590204022+33=5517+42=59 14+42=56402021+20=4120+22=4226+22=4860037+0=3732+0=3235+0=35800800+30=30 68 200+68=68 72 200+72=72 73 20206022+46=6817+55=7214+59=73 404021+33=5420+42=6426+42=68602037+20=5732+22=5435+22=5780067+0=6761+0=6152+0=5210001000+42=42 87 800+87=87 8700+87=87 870208022+30=5217+68=8514+72=86406021+46=6720+55=7526+59=85604037+33=7032+42=7435+42=77802067+20=87 61+22=8352+22=74100058+0=5872+0=7261+0=61จากผลลัพธ์ของการเพิ่มประสิทธิภาพตามเงื่อนไข เราจะกำหนดการจัดสรรทรัพยากรที่เหมาะสมที่สุด:

ดังนั้นการจัดสรรทรัพยากรที่เหมาะสมที่สุดคือ:

ซึ่งจะให้ผลกำไรสูงสุดในจำนวน 87 หน่วยธรรมดา ถ้ำ หน่วย

คำตอบ:การจัดสรรทรัพยากรอย่างเหมาะสม: ซึ่งให้ผลกำไรสูงสุดจาก 87 หน่วยทั่วไป ถ้ำ หน่วย

บทสรุป

การเขียนโปรแกรมแบบไดนามิกเป็นขอบเขตของการเขียนโปรแกรมทางคณิตศาสตร์ที่ประกอบด้วยชุดเทคนิคและเครื่องมือสำหรับการค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุดตลอดจนการปรับแต่ละขั้นตอนในระบบให้เหมาะสมและพัฒนากลยุทธ์การควบคุม กล่าวคือ กระบวนการควบคุมสามารถแสดงเป็น กระบวนการหลายขั้นตอน การเขียนโปรแกรมแบบไดนามิกโดยใช้การวางแผนทีละขั้นตอนช่วยให้ไม่เพียง แต่ทำให้การแก้ปัญหาง่ายขึ้นเท่านั้น แต่ยังช่วยแก้ปัญหาที่ไม่สามารถนำมาใช้โดยใช้วิธีการวิเคราะห์ทางคณิตศาสตร์ได้อีกด้วย การลดความซับซ้อนของการแก้ปัญหาทำได้โดยการลดจำนวนตัวเลือกที่กำลังศึกษาอยู่อย่างมาก เนื่องจากแทนที่จะแก้ไขปัญหาหลายตัวแปรที่ซับซ้อนเพียงครั้งเดียว วิธีการวางแผนทีละขั้นตอนเกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างง่ายหลายครั้ง เมื่อวางแผนกระบวนการทีละขั้นตอน เราดำเนินการจากผลประโยชน์ของกระบวนการทั้งหมดโดยรวม เช่น เมื่อทำการตัดสินใจในขั้นตอนใดขั้นตอนหนึ่ง จำเป็นอย่างยิ่งที่จะต้องคำนึงถึงเป้าหมายสุดท้ายเสมอ อย่างไรก็ตาม การเขียนโปรแกรมแบบไดนามิกก็มีข้อเสียเช่นกัน ต่างจากการเขียนโปรแกรมเชิงเส้นซึ่งวิธี simplex เป็นแบบสากล ไม่มีวิธีการดังกล่าวในการเขียนโปรแกรมแบบไดนามิก แต่ละงานมีความยากในตัวเอง และในแต่ละกรณีจำเป็นต้องหาวิธีแก้ไขที่เหมาะสมที่สุด ข้อเสียของการเขียนโปรแกรมแบบไดนามิกคือความซับซ้อนในการแก้ปัญหาหลายมิติ ปัญหาการเขียนโปรแกรมแบบไดนามิกต้องเป็นไปตามเงื่อนไขสองประการ เงื่อนไขแรกมักเรียกว่าเงื่อนไขของการไม่มีผลที่ตามมา และเงื่อนไขที่สองคือเงื่อนไขของการบวกของฟังก์ชันวัตถุประสงค์ของปัญหา ในทางปฏิบัติ มีปัญหาในการวางแผนซึ่งปัจจัยสุ่มมีบทบาทสำคัญ ซึ่งมีอิทธิพลต่อทั้งสถานะของระบบและผลที่ได้ มีความแตกต่างระหว่างปัญหาการเขียนโปรแกรมไดนามิกที่กำหนดและแบบสุ่ม ในปัญหาเชิงกำหนด การควบคุมที่เหมาะสมที่สุดนั้นมีลักษณะเฉพาะและได้รับการระบุไว้ล่วงหน้าว่าเป็นแผนการดำเนินการที่เข้มงวด ในปัญหาสุ่ม การควบคุมที่เหมาะสมที่สุดจะเป็นแบบสุ่ม และเลือกในระหว่างกระบวนการ ขึ้นอยู่กับสถานการณ์สุ่ม ในรูปแบบที่กำหนดขึ้น จะต้องผ่านกระบวนการเป็นขั้นตอนตั้งแต่ต้นจนจบ นอกจากนี้ยังมีชุดการควบคุมที่เหมาะสมที่สุดตามเงื่อนไขทั้งหมดในแต่ละขั้นตอน แต่จากการควบคุมทั้งหมดเหล่านี้ มีเพียงการควบคุมเดียวเท่านั้นที่ถูกดำเนินการในท้ายที่สุด นี่ไม่ใช่กรณีในรูปแบบสุ่ม การควบคุมที่เหมาะสมตามเงื่อนไขแต่ละรายการสามารถนำไปใช้ได้จริง หากกระบวนการสุ่มก่อนหน้านี้นำระบบไปสู่สถานะที่สอดคล้องกัน หลักการของการเพิ่มประสิทธิภาพเป็นพื้นฐานสำหรับการแก้ปัญหาการเขียนโปรแกรมแบบไดนามิกทีละขั้นตอน ตัวแทนทั่วไปของปัญหาทางเศรษฐกิจของโปรแกรมไดนามิกคือปัญหาที่เรียกว่าปัญหาการผลิตและการจัดเก็บ ปัญหาการกระจายการลงทุนด้านทุน ปัญหาเกี่ยวกับกำหนดเวลาการผลิต และอื่นๆ ปัญหาการเขียนโปรแกรมแบบไดนามิกใช้ในการวางแผนกิจกรรมขององค์กรโดยคำนึงถึงการเปลี่ยนแปลงความต้องการผลิตภัณฑ์เมื่อเวลาผ่านไป ในการกระจายทรัพยากรอย่างเหมาะสมระหว่างองค์กรในทิศทางหรือเวลา คำอธิบายคุณลักษณะของการเขียนโปรแกรมแบบไดนามิกและประเภทของปัญหาที่สามารถกำหนดได้ภายในกรอบงานจะต้องมีความทั่วไปและค่อนข้างคลุมเครือ เนื่องจากมีปัญหาที่แตกต่างกันมากมายที่เหมาะกับรูปแบบการเขียนโปรแกรมแบบไดนามิก การศึกษาตัวอย่างจำนวนมากเท่านั้นที่ให้ความเข้าใจที่ชัดเจนเกี่ยวกับโครงสร้างของการเขียนโปรแกรมแบบไดนามิก

อ้างอิง

1. แบบจำลองและวิธีการทางเศรษฐศาสตร์และคณิตศาสตร์ การเขียนโปรแกรมเชิงเส้น: บทช่วยสอนสำหรับนักศึกษาสาขาวิชาเศรษฐศาสตร์ / เรียบเรียงโดย: Smirnov Yu.N., Shibanova E.V., Naberezhnye Chelny: KamPI Publishing House, 2004, 81 p.
2. การวิจัยปฏิบัติการทางเศรษฐศาสตร์: หนังสือเรียน. คู่มือสำหรับมหาวิทยาลัย / N.Sh. เครเมอร์ ปริญญาตรี ปุตโก, ไอ.เอ็ม. Trishin, M.N. ฟรีดแมน; เอ็ด ศาสตราจารย์ น.ช. เครเมอร์. - อ.: เอกภาพ, 2543. - 407 น.
3. คุซเนตซอฟ เอ.วี. และอื่น ๆ คณิตศาสตร์ขั้นสูง: เสื่อ การเขียนโปรแกรม: หนังสือเรียน/A.V. คุซเนตซอฟ, วี.เอ. ซาโควิช, N.I. เย็น; ภายใต้ทั่วไป เอ็ด เอ.วี. คุซเนตโซวา - ชื่อ: สูงกว่า. โรงเรียน พ.ศ. 2537 - 286 หน้า: ป่วย

กวดวิชา

ต้องการความช่วยเหลือในการศึกษาหัวข้อหรือไม่?

ผู้เชี่ยวชาญของเราจะแนะนำหรือให้บริการสอนพิเศษในหัวข้อที่คุณสนใจ
ส่งใบสมัครของคุณระบุหัวข้อในขณะนี้เพื่อค้นหาความเป็นไปได้ในการรับคำปรึกษา