การเขียนโปรแกรมเชิงเส้น: มีไว้เพื่ออะไรโมเดลข้อ จำกัด การใช้งาน - คณิตศาสตร์ - 2026

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

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

รูปที่ 1. การเขียนโปรแกรมเชิงเส้นใช้กันอย่างแพร่หลายเพื่อเพิ่มผลกำไร ที่มา: Piqsels

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

Z = k ₁ x + k ₂ y

ด้วยค่าคงที่k ₁และ k ₂ ฟังก์ชันนี้เรียกว่าฟังก์ชันวัตถุประสงค์ แน่นอนว่ามีสถานการณ์ที่มีผลมากกว่าสองตัวแปรสำหรับการศึกษาซึ่งมีความซับซ้อนมากขึ้น:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ + ….

และข้อ จำกัด ยังสร้างแบบจำลองทางคณิตศาสตร์โดยระบบสมการหรืออสมการโดยมีเส้นตรง x และ y เท่ากัน

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

การเขียนโปรแกรมเชิงเส้นได้รับการพัฒนาโดยอิสระโดยนักฟิสิกส์และนักคณิตศาสตร์ชาวอเมริกัน George Dantzig (1914-2005) และ Leonid Kantorovich นักคณิตศาสตร์และนักเศรษฐศาสตร์ชาวรัสเซีย (1912-1986) ไม่นานหลังจากสงครามโลกครั้งที่สอง

วิธีการแก้ปัญหาที่เรียกว่าวิธีซิมเพล็กซ์เป็นผลงานการผลิตของ Dantzig ซึ่งทำงานให้กับกองทัพอากาศสหรัฐมหาวิทยาลัยเบิร์กลีย์และมหาวิทยาลัยสแตนฟอร์ด

รูปที่ 2. นักคณิตศาสตร์ George Dantzig (ซ้าย) และ Leonid Kantorovich (ขวา) ที่มา: F. Zapata

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

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

- ฟังก์ชั่นวัตถุประสงค์

- ตัวแปรการตัดสินใจ

-ข้อ จำกัด

ในฟังก์ชันวัตถุประสงค์คุณกำหนดสิ่งที่คุณต้องการบรรลุ ตัวอย่างเช่นสมมติว่าคุณต้องการเพิ่มผลกำไรสูงสุดจากการผลิตผลิตภัณฑ์บางอย่าง จากนั้นฟังก์ชัน "กำไร" จะถูกสร้างขึ้นตามราคาที่ขายผลิตภัณฑ์

ในแง่ทางคณิตศาสตร์ฟังก์ชันนี้สามารถแสดงโดยย่อโดยใช้สัญกรณ์ผลรวม:

Z = ∑k _ผม x _ผม

ในสมการนี้ k _iคือสัมประสิทธิ์และ x _iคือตัวแปรการตัดสินใจ

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

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

ประเภทของข้อ จำกัด

คุณสามารถมีข้อ จำกัด จำนวน M ได้เริ่มตั้งแต่ j = 1 ถึง j = M ในทางคณิตศาสตร์ข้อ จำกัด มีสามประเภท:

1. _J = Σ IJ x _ผม
2. B _j ≥ ∑ b _ij . x _ผม
3. C _เจ ≤ΣคIJ x _ผม

ข้อ จำกัด ประการแรกคือประเภทสมการเชิงเส้นและหมายความว่าต้องเคารพค่า A _jซึ่งเป็นที่รู้จัก

ข้อ จำกัด ที่เหลืออีกสองข้อคืออสมการเชิงเส้นและหมายความว่าค่าที่รู้จัก B _jและ C _jสามารถเคารพหรือเกินได้เมื่อสัญลักษณ์ที่ปรากฏเป็น≥ (มากกว่าหรือเท่ากับ) หรือเคารพหรือไม่เกินหากสัญลักษณ์นั้นมีค่า≤ (น้อยกว่าหรือเท่ากับ)

ตัวอย่างโมเดล

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

ร้านขนมท้องถิ่นขึ้นชื่อเรื่องอาหารพิเศษ 2 อย่าง ได้แก่ เค้กแบล็กฟอเรสต์และเค้กแซกริแพนทีน

ในการเตรียมต้องใช้ไข่และน้ำตาล สำหรับป่าดำคุณต้องใช้ไข่ 9 ฟองและน้ำตาล 500 กรัมในขณะที่สำหรับแซคริแพนทีนคุณต้องมีไข่ 8 ฟองและน้ำตาล 800 กรัม ราคาขายตามลำดับคือ $ 8 และ $ 10

ปัญหาคือเค้กแต่ละประเภทต้องทำเบเกอรี่กี่ชิ้นจึงจะได้กำไรสูงสุดโดยรู้ว่ามีน้ำตาล 10 กิโลกรัมและไข่ 144 ฟอง?

ตัวแปรการตัดสินใจ

ตัวแปรการตัดสินใจคือ "x" และ "y" ซึ่งรับค่าจริง:

-x: จำนวนเค้กแบล็คฟอเรสต์

-y: เค้กประเภท sacripantine

ข้อ จำกัด

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

ดังนั้นในรูปแบบทางคณิตศาสตร์ข้อ จำกัด เหล่านี้จึงอยู่ในรูปแบบ:

1. x ≥ 0
2. และ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

ข้อ จำกัด ที่ 1 และ 2 เป็นเงื่อนไขของการไม่ปฏิเสธที่เปิดเผยก่อนหน้านี้และอสมการทั้งหมดที่เพิ่มขึ้นเป็นเส้นตรง ในข้อ จำกัด 3 และ 4 คือค่าที่ต้องไม่เกิน: 144 ฟองและน้ำตาล 10 กก.

ฟังก์ชันวัตถุประสงค์

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

G = 8x + 10y

วิธีการแก้ปัญหา

วิธีการแก้ปัญหาต่างๆรวมถึงวิธีการแบบกราฟิกอัลกอริทึมด้านเดียวและวิธีจุดภายในเพื่อตั้งชื่อไม่กี่

- วิธีกราฟิกหรือเรขาคณิต

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

รูปที่ 3. ขอบเขตที่เป็นไปได้ซึ่งพบวิธีแก้ปัญหาการเพิ่มประสิทธิภาพ ที่มา: Wikimedia Commons

พื้นที่นี้สร้างขึ้นโดยใช้เส้นข้อ จำกัด ซึ่งเป็นเส้นที่ได้จากความไม่เท่าเทียมกันของข้อ จำกัด โดยใช้เครื่องหมายความเท่าเทียมกันเท่านั้น

ในกรณีของร้านเบเกอรี่ที่ต้องการเพิ่มผลกำไรบรรทัดข้อ จำกัด คือ:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

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

โชคดีที่สำหรับปัญหาการทำขนมในพื้นที่ที่เป็นไปได้นั้นไม่ว่างเปล่าเรามีข้อมูลดังกล่าวด้านล่าง

รูปที่ 4. ขอบเขตที่เป็นไปได้ของปัญหาขนมอบ บรรทัดที่มี gain 0 ข้ามจุดเริ่มต้น ที่มา: F. Zapata กับ Geogebra

ทางออกที่ดีที่สุดหากมีอยู่จะพบได้ด้วยความช่วยเหลือของฟังก์ชันวัตถุประสงค์ ตัวอย่างเช่นเมื่อพยายามหากำไรสูงสุด G เรามีบรรทัดต่อไปนี้ซึ่งเรียกว่าเส้น iso-profit:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

ด้วยเส้นนี้เราได้คู่ทั้งหมด (x, y) ที่ให้ค่า G ที่กำหนดดังนั้นจึงมีตระกูลของเส้นตามค่าของ G แต่ทั้งหมดมีความชันเท่ากัน -k ₁ / k ₂ดังนั้นพวกมันจึงเป็น เส้นขนาน.

ทางออกที่ดีที่สุด

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

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

สำหรับขนมของเราจุดยอดของผู้สมัครคือ A, B และ C

- วิธีการง่ายๆของ Dantzig

วิธีกราฟิกหรือเรขาคณิตสามารถใช้ได้กับสองตัวแปร อย่างไรก็ตามมีความซับซ้อนมากขึ้นเมื่อมีตัวแปรสามตัวและไม่สามารถใช้กับตัวแปรจำนวนมากได้

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

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

การประยุกต์ใช้งาน

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

นี่คือบางฟิลด์:

- ในการตลาดใช้เพื่อค้นหาส่วนผสมที่ดีที่สุดของสื่อ (โซเชียลเน็ตเวิร์กโทรทัศน์สื่อและอื่น ๆ ) เพื่อโฆษณาผลิตภัณฑ์บางอย่าง

- สำหรับการมอบหมายงานที่เพียงพอให้กับบุคลากรของ บริษัท หรือโรงงานหรือกำหนดเวลาให้กับพวกเขา

- ในการเลือกอาหารที่มีคุณค่าทางโภชนาการสูงสุดและต้นทุนต่ำที่สุดในอุตสาหกรรมปศุสัตว์และสัตว์ปีก

แบบฝึกหัดที่แก้ไข

- แบบฝึกหัด 1

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

สารละลาย

จำเป็นต้องสร้างกราฟชุดค่าที่กำหนดโดยระบบข้อ จำกัด ที่ระบุในปัญหา:

1. x ≥ 0
2. และ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

พื้นที่ที่กำหนดโดยอสมการ 1 และ 2 สอดคล้องกับกำลังสองแรกของระนาบคาร์ทีเซียน เกี่ยวกับความไม่เท่าเทียมกัน 3 และ 4 เราเริ่มต้นด้วยการค้นหาบรรทัดข้อ จำกัด :

9x + 8y = 144

0.5 x + 0.8y = 10 → 5x + 8y = 100

พื้นที่ที่เป็นไปได้คือรูปสี่เหลี่ยมด้านข้างซึ่งมีจุดยอดคือจุด A, B, C และ D

กำไรขั้นต่ำคือ 0 ดังนั้นเส้น 8x + 10y = 0 คือขีด จำกัด ล่างและเส้นกำไรขั้นต่ำมีความชัน -8/10 = - 0.8

ค่านี้แตกต่างจากความลาดชันของเส้นข้อ จำกัด อื่น ๆ และเนื่องจากขอบเขตที่เป็นไปได้ถูก จำกัด ไว้จึงมีการแก้ปัญหาเฉพาะ

รูปที่ 5. วิธีแก้ปัญหาแบบกราฟิกของแบบฝึกหัด 1 แสดงพื้นที่ที่เป็นไปได้และจุดแก้ปัญหา C ที่จุดยอดใดจุดหนึ่งของพื้นที่ดังกล่าว ที่มา: F. Zapata

คำตอบนี้สอดคล้องกับเส้นความชัน -0.8 ที่ผ่านจุด A, B หรือ C ซึ่งมีพิกัดคือ:

ก (11; 5.625)

ข (0; 12.5)

ค (16, 0)

ทางออกที่ดีที่สุด

เราคำนวณค่า G สำหรับแต่ละจุดเหล่านี้:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144.25

- (0; 12.5): G _B = 8 x 0 + 10 x 12.5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

ผลกำไรสูงสุดคือการผลิตเค้กแบล็คฟอเรสต์ 11 ชิ้นและเค้กแซคริแพนทีน 5,625 ชิ้น โซลูชันนี้สอดคล้องกับโซลูชันที่พบผ่านซอฟต์แวร์

- แบบฝึกหัด 2

ตรวจสอบผลลัพธ์ของแบบฝึกหัดก่อนหน้านี้โดยใช้ฟังก์ชัน Solver ที่มีอยู่ในสเปรดชีตส่วนใหญ่เช่น Excel หรือ LibreOffice Calc ซึ่งรวมอัลกอริทึม Simplex สำหรับการเพิ่มประสิทธิภาพในการเขียนโปรแกรมเชิงเส้น

สารละลาย

รูปที่ 6. รายละเอียดของโซลูชันจากแบบฝึกหัดที่ 1 ผ่านสเปรดชีต Libre Office Calc ที่มา: F. Zapata

รูปที่ 7. รายละเอียดของโซลูชันจากแบบฝึกหัดที่ 1 ผ่านสเปรดชีต Libre Office Calc ที่มา: F. Zapata

อ้างอิง

1. สุกใส การเขียนโปรแกรมเชิงเส้น ดึงมาจาก: bright.org.
2. Eppen, G. 2000. การวิจัยปฏิบัติการในศาสตร์การบริหาร. วันที่ 5. ฉบับ ศิษย์ฮอลล์.
3. Haeussler, E. 1992. คณิตศาสตร์เพื่อการจัดการและเศรษฐศาสตร์. ครั้งที่ 2 ฉบับ Grupo Editorial Iberoamericana
4. Hiru.eus. การเขียนโปรแกรมเชิงเส้น กู้คืนจาก: hiru.eus.
5. Wikipedia การเขียนโปรแกรมเชิงเส้น กู้คืนจาก: es. wikipedia.org.