การเขียนโปรแกรมแบบไม่เชิงเส้น: วิธีการและแบบฝึกหัด - คณิตศาสตร์ - 2026

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

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

รูปที่ 1. ปัญหาการเขียนโปรแกรมแบบไม่เชิงเส้น (NLP) โดยที่ G คือฟังก์ชัน (ไม่ใช่เชิงเส้น) เพื่อปรับให้เหมาะสมในพื้นที่สีเขียวซึ่งพิจารณาจากข้อ จำกัด ที่มา: F. Zapata

ดังนั้นจึงไม่สามารถใช้ขั้นตอนและวิธีการของโปรแกรมเชิงเส้นได้

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

วิธีการเขียนโปรแกรมเชิงเส้น

สำหรับปัญหาการเขียนโปรแกรมเชิงเส้นวิธีการหลักที่จะใช้คือ:

1.- วิธีการกราฟิก

2.- ตัวคูณ Lagrange เพื่อสำรวจขอบเขตของขอบเขตการแก้ปัญหา

3.- การคำนวณการไล่ระดับสีเพื่อสำรวจความสุดขั้วของฟังก์ชันวัตถุประสงค์

4.- วิธีการลดขั้นตอนเพื่อค้นหาจุดไล่ระดับสีว่าง

5.- วิธีการแก้ไขของตัวคูณ Lagrange (ด้วยเงื่อนไข Karush-Kuhn-Tucker)

ตัวอย่างการแก้ปัญหาด้วยวิธีกราฟิก

ตัวอย่างของการแก้ปัญหาด้วยวิธีการแบบกราฟิกคือวิธีที่สามารถเห็นได้ในรูปที่ 2:

รูปที่ 2. ตัวอย่างของปัญหาที่ไม่ใช่เชิงเส้นพร้อมข้อ จำกัด ที่ไม่ใช่เชิงเส้นและวิธีแก้ปัญหาแบบกราฟิก ที่มา: F. Zapata

การออกกำลังกาย

- แบบฝึกหัดที่ 1 (วิธีกราฟิก)

กำไร G ของ บริษัท บางแห่งขึ้นอยู่กับจำนวนที่ขายของผลิตภัณฑ์ X และจำนวนที่ขายผลิตภัณฑ์ Y นอกจากนี้กำไรจะถูกกำหนดโดยสูตรต่อไปนี้:

G = 2 (X - 2) ² + 3 (Y - 3) ²

จำนวน X และ Y เป็นที่ทราบกันดีว่ามีข้อ จำกัด ดังต่อไปนี้:

X≥0; Y≥0และ X + Y ≤ 7

กำหนดค่าของ X และ Y ที่ให้ผลกำไรสูงสุด

รูปที่ 3 กำไรของ บริษัท สามารถสร้างแบบจำลองทางคณิตศาสตร์เพื่อหากำไรสูงสุดโดยใช้การเขียนโปรแกรมแบบไม่เชิงเส้น ที่มา: Pixabay

สารละลาย

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

สำหรับวิธีแก้ปัญหานี้จะเลือกวิธีการแบบกราฟิก

ขั้นแรกจะกำหนดขอบเขตการแก้ปัญหาซึ่งกำหนดโดยข้อ จำกัด

เป็นX≥0; Y≥0วิธีแก้ปัญหาจะต้องพบในควอดแรนท์แรกของระนาบ XY แต่เนื่องจาก X + Y ≤ 7 ต้องเป็นจริงด้วยดังนั้นคำตอบจึงอยู่ในระนาบครึ่งล่างของเส้น X + Y = 7

ขอบเขตการแก้ปัญหาคือจุดตัดของจตุภาคแรกกับระนาบครึ่งล่างของเส้นซึ่งส่งผลให้เกิดพื้นที่สามเหลี่ยมที่พบโซลูชัน เหมือนกับที่ระบุไว้ในรูปที่ 1

ในทางกลับกันกำไร G สามารถแสดงในระนาบคาร์ทีเซียนได้เนื่องจากสมการของมันคือวงรีที่มีจุดศูนย์กลาง (2,3)

วงรีแสดงในรูปที่ 1 สำหรับค่าต่างๆของ G ยิ่งค่า G สูงเท่าไรก็ยิ่งได้รับมากเท่านั้น

มีโซลูชันที่เป็นของภูมิภาค แต่ไม่ให้ค่า G สูงสุดในขณะที่อื่น ๆ เช่น G = 92.4 อยู่นอกโซนสีเขียวนั่นคือโซนโซลูชัน

จากนั้นค่าสูงสุดของ G ทำให้ X และ Y เป็นของภูมิภาคโซลูชันสอดคล้องกับ:

G = 77 (กำไรสูงสุด) ซึ่งกำหนดให้สำหรับ X = 7 และ Y = 0

ที่น่าสนใจคือกำไรสูงสุดเกิดขึ้นเมื่อยอดขายของผลิตภัณฑ์ Y เป็นศูนย์ในขณะที่จำนวนผลิตภัณฑ์ X ถึงมูลค่าสูงสุดที่เป็นไปได้

- แบบฝึกหัดที่ 2 (วิธีวิเคราะห์: ตัวคูณลากรองจ์)

หาคำตอบ (x, y) ที่ทำให้ฟังก์ชัน f (x, y) = x ² + 2y ²สูงสุดในพื้นที่ g (x, y) = x ² + y ² - 1 = 0

สารละลาย

เห็นได้ชัดว่าเป็นปัญหาการเขียนโปรแกรมที่ไม่ใช่เชิงเส้นเนื่องจากทั้งฟังก์ชันวัตถุประสงค์ f (x, y) และข้อ จำกัด g (x, y) = 0 ไม่ใช่ชุดค่าผสมเชิงเส้นของตัวแปร x และ y

จะใช้วิธีตัวคูณ Lagrange ซึ่งก่อนอื่นต้องกำหนดฟังก์ชัน Lagrange L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 1)

โดยที่λคือพารามิเตอร์ที่เรียกว่าตัวคูณ Lagrange

ในการกำหนดค่ามากของฟังก์ชันวัตถุประสงค์ f ในขอบเขตการแก้ปัญหาที่กำหนดโดยข้อ จำกัด g (x, y) = 0 ให้ทำตามขั้นตอนเหล่านี้:

- ค้นหาอนุพันธ์บางส่วนของฟังก์ชัน Lagrange L เทียบกับ x, y, λ

- ปรับสมดุลของอนุพันธ์ให้เป็นศูนย์

ลำดับของการดำเนินการเหล่านี้มีดังนี้:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

โซลูชันระบบที่เป็นไปได้

คำตอบที่เป็นไปได้ของระบบนี้คือλ = 1 เพื่อให้สมการแรกเป็นที่พอใจในกรณีนี้ y = 0 เพื่อให้สมการที่สองเป็นที่พอใจ

คำตอบนี้หมายความว่า x = 1 หรือ x = -1 เพื่อให้สมการที่สามเป็นที่พอใจ ด้วยวิธีนี้ได้รับสองโซลูชัน S1 และ S2:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0)

อีกทางเลือกหนึ่งคือλ = 2 เพื่อให้สมการที่สองเป็นที่พอใจโดยไม่คำนึงถึงค่า y

ในกรณีนี้วิธีเดียวที่จะทำให้สมการแรกเป็นที่พอใจคือ x = 0 เมื่อพิจารณาจากสมการที่สามมีเพียงสองคำตอบที่เป็นไปได้ซึ่งเราจะเรียกว่า S3 และ S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

หากต้องการทราบว่าโซลูชันใดหรือข้อใดในการเพิ่มฟังก์ชันวัตถุประสงค์ให้สูงสุดเราจะทำการแทนที่ด้วย f (x, y):

S1: f (1, 0) = 1 ² + 2.0 ² = 1

S2: f (-1, 0) = (-1) ² + 2.0 ² = 1

S3: f (0, 1) = 0 ² + 2.1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

เราสรุปได้ว่าคำตอบที่เพิ่ม f สูงสุดเมื่อ x และ y เป็นของเส้นรอบวง g (x, y) = 0 คือ S3 และ S4

คู่ของค่า (x = 0, y = 1) และ (x = 0, y = -1) เพิ่ม f (x, y) ในพื้นที่โซลูชัน g (x, y) = 0

- แบบฝึกหัดที่ 3 (การไล่ระดับสี Null)

ค้นหาคำตอบ (x, y) สำหรับฟังก์ชันวัตถุประสงค์:

f (x, y) = x ² + 2 y ²

ให้เป็นค่าสูงสุดในพื้นที่ g (x, y) = x ² + y ² - 1 ≤ 0

สารละลาย

แบบฝึกหัดนี้คล้ายกับแบบฝึกหัดที่ 2 แต่ขอบเขตวิธีแก้ปัญหา (หรือข้อ จำกัด ) ขยายไปถึงพื้นที่ด้านในของเส้นรอบวง g (x, y) = 0 กล่าวคือกับวงกลม g (x, y) ≤ 0 ซึ่งรวมถึง ไปยังเส้นรอบวงและภูมิภาคด้านใน

การแก้ปัญหาที่เส้นขอบได้รับการพิจารณาแล้วในแบบฝึกหัดที่ 2 แต่ยังคงต้องสำรวจพื้นที่ภายใน

ในการทำเช่นนี้ต้องคำนวณการไล่ระดับสีของฟังก์ชัน f (x, y) และตั้งค่าให้เท่ากับศูนย์เพื่อหาค่ามากในขอบเขตของโซลูชัน สิ่งนี้เทียบเท่ากับการคำนวณอนุพันธ์บางส่วนของ f เทียบกับ x และ y ตามลำดับและตั้งค่าให้เท่ากับศูนย์:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

ระบบสมการนี้มีทางออกเดียว (x = 0, y = 0) ที่เป็นของวงกลม g (x, y) ≤ 0

การแทนที่ค่านี้ในผลลัพธ์ของฟังก์ชัน f:

ฉ (0, 0) = 0

สรุปได้ว่าค่าสูงสุดที่ฟังก์ชันใช้ในขอบเขตโซลูชันคือ 2 และเกิดขึ้นที่ขอบเขตของขอบเขตการแก้ปัญหาสำหรับค่า (x = 0, y = 1) และ (x = 0, y = -1) .

อ้างอิง

1. Avriel, M. 2003. Nonlinear Programing. สำนักพิมพ์โดเวอร์.
2. บาซาร่า. 2522. การเขียนโปรแกรมแบบไม่เชิงเส้น. John Wiley & Sons
3. Bertsekas, D. 1999. Nonlinear Programing: 2nd edition. Athena Scientific
4. Nocedal, J. 1999. การเพิ่มประสิทธิภาพเชิงตัวเลข. สปริงเกอร์ - เวอร์
5. วิกิพีเดีย การเขียนโปรแกรมแบบไม่เชิงเส้น สืบค้นจาก: es.wikipedia.com