ปัญหาการเขียนโปรแกรมเชิงเส้น วิธีแก้ไข และแอปพลิเคชัน [พร้อมตัวอย่าง]

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

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

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

ตอนนี้ ส้มหนึ่งถุงมีราคา 500 รูปีอินเดีย ในขณะที่ถุงแอปเปิ้ลราคา 750 รูปีอินเดีย คุณสามารถสร้าง INR 100 จากการขายส้มหนึ่งถุง และ 200 รูปีอินเดียจากการขายแอปเปิ้ลหนึ่งถุง

ปัญหานี้มีความเป็นไปได้ต่างๆ คุณอาจเลือกซื้อส้มเท่านั้น แต่หลังจากนั้น คุณจะมีที่เก็บของคุณเพียง 10 ถุง และกำไรของคุณจะเท่ากับ 1,000 รูปีอินเดีย ในทำนองเดียวกัน คุณอาจเลือกซื้อเฉพาะแอปเปิ้ลและทำเป็นกำไร 1,500 รูปีอินเดีย คุณยังสามารถซื้อทั้งสองอย่างรวมกันได้

ปัญหาดังกล่าวเรียกว่าปัญหาโปรแกรมเชิงเส้นตรง และเราจะพูดถึงในรายละเอียด มาเริ่มกันเลย:

การเขียนโปรแกรมเชิงเส้นคืออะไร?

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

พื้นฐานของการเขียนโปรแกรมเชิงเส้น

ต่อไปนี้เป็นเงื่อนไขพื้นฐานของการเขียนโปรแกรมเชิงเส้น:

ข้อจำกัด

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

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

ตัวแปรเหล่านี้กำหนดผลลัพธ์ของคุณ ผลลัพธ์ของคุณขึ้นอยู่กับตัวแปรเหล่านี้ เราจึงเรียกมันว่า 'ตัวแปรการตัดสินใจ'

ข้อจำกัดการไม่ปฏิเสธ

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

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

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

การกำหนดปัญหาการเขียนโปรแกรมเชิงเส้น

คุณควรรู้วิธีกำหนดโปรแกรมเชิงเส้นตรงเพื่อนำไปใช้ในชีวิตจริง สมมติว่าคุณเป็นผู้ผลิตของเล่นและคุณผลิตของเล่นเพียงสองชิ้นเท่านั้น: A และ B พูดง่ายๆ ก็คือ ของเล่นของคุณต้องใช้ทรัพยากร X และ Y สองอย่างในการผลิต นี่คือข้อกำหนดของของเล่นของคุณ:

• ของเล่น A หนึ่งหน่วยต้องการให้คุณหนึ่งหน่วยของทรัพยากร X และสามหน่วยของทรัพยากร Y

• ของเล่น B หนึ่งหน่วยต้องการทรัพยากร X หนึ่งหน่วยและทรัพยากรสองหน่วย Y

คุณมีทรัพยากร 5 หน่วย X และ 12 หน่วยของทรัพยากร Y อัตรากำไรจากการขายของเล่นเหล่านี้คือ:

• INR 6 ต่อหน่วยขายของเล่น A
• INR 5 ต่อหน่วยขายของเล่น B

คุณจะผลิตของเล่นแต่ละชิ้นได้กี่หน่วยเพื่อให้ได้กำไรสูงสุด?

การแก้ไขปัญหา

มาแทนปัญหาการโปรแกรมเชิงเส้นในสมการกัน:

Z = 6a + 5b

ในที่นี้ z หมายถึงกำไรทั้งหมด a หมายถึงจำนวนของเล่น A ทั้งหมด และ b หมายถึงจำนวนทั้งหมดถึง B หน่วย เป้าหมายของเราคือการเพิ่มมูลค่าของ Z ให้สูงสุด (กำไร)

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

a + b 5

ตอนนี้ของเล่น A และ B ทุกหน่วยต้องการทรัพยากร 3 และ 2 หน่วยตามลำดับ และเรามีทรัพยากร Y ทั้งหมด 12 หน่วยเท่านั้น ดังนั้นในทางคณิตศาสตร์ มันจะมีลักษณะดังนี้:

3a + 2b 12

จำไว้ว่าค่าของหน่วยของเล่น A ต้องเป็นจำนวนเต็มเท่านั้น ซึ่งหมายความว่าเรายังมีข้อจำกัดของ a->0 และ b<-0

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

อ่าน: แนวคิดและหัวข้อโครงการการเขียนโปรแกรมเชิงเส้น

ขั้นตอนของการกำหนดปัญหาการเขียนโปรแกรมเชิงเส้น

ในการกำหนดปัญหาการเขียนโปรแกรมเชิงเส้น ให้ทำตามขั้นตอนเหล่านี้:

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

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

การแก้ปัญหาการเขียนโปรแกรมเชิงเส้นด้วย R

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

ตัวอย่าง

เริ่มจากปัญหาพื้นฐานกันก่อน องค์กรมีผลิตภัณฑ์สองรายการที่มีราคาขาย 25 รูปีอินเดียและ 20 รูปีอินเดียและเรียกว่าผลิตภัณฑ์ A และ B ตามลำดับ ทุกวัน พวกเขามีทรัพยากร 1800 หน่วยในการผลิตผลิตภัณฑ์เหล่านี้ ผลิตภัณฑ์ A ต้องการ 20 หน่วยทรัพยากร และ B ต้องการ 12 หน่วยทรัพยากร เวลาในการผลิตสำหรับผลิตภัณฑ์ทั้งสองนี้คือสี่นาที และองค์กรได้รับทั้งหมดแปดชั่วโมงทำงานทุกวัน ปัญหาคือ ปริมาณการผลิตของแต่ละผลิตภัณฑ์ควรเป็นเท่าไหร่ เพื่อเพิ่มผลกำไรของบริษัท

สารละลาย:

เราจะเริ่มแก้ปัญหานี้โดยกำหนดฟังก์ชันวัตถุประสงค์:

สูงสุด (ยอดขาย) = สูงสุด ( 25 ปี 1 + 20 ปี 2 )

ในที่นี้ 25 และ 20 คือราคาของผลิตภัณฑ์ A และ B ตามลำดับ y1 คือหน่วยทั้งหมดของผลิตภัณฑ์ A ที่ผลิต และ y2 คือหน่วยทั้งหมดของผลิตภัณฑ์ B ที่ผลิต ตัวแปรการตัดสินใจของเราคือ y1 และ y2

ตอนนี้เราจะกำหนดข้อจำกัดสำหรับปัญหาของเรา:

ข้อจำกัดด้านทรัพยากร:

20 ปี 1 + 12 ปี 2 1800

จำกัดเวลา:

4 ปี 1 + 4 ปี 2 8*60

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

ใช้ R เพื่อแก้ปัญหา:

เราจะใช้ lpsolve เพื่อแก้ปัญหา LP นี้และเริ่มต้นด้วยการตั้งค่าฟังก์ชันวัตถุประสงค์:

> ต้องการ (lpSolve)

กำลังโหลดแพ็คเกจที่ต้องการ: lpSolve

> วัตถุประสงค์ใน <- c(25, 20)

> วัตถุประสงค์.in

[1] 25 20

จากนั้นเราจะสร้างเมทริกซ์สำหรับข้อจำกัด:

> const <- matrix(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> คอนสต

[,1] [,2]

[1,] 20 12

[2,] 4 4

> time_constraints <- (8*60)

> ข้อจำกัดทรัพยากร <- 1800

> เวลา_ข้อ จำกัด

[1] 480

> ทรัพยากร_ข้อ จำกัด

[1] 1800

มาสร้างสมการที่กำหนดไว้แล้วกัน:

> rhs <- c(resource_constraints, time_constraints)

> rhs

[1] 1800 480

> ทิศทาง <- c(“<=”, “<=”)

> ทิศทาง

[1] “<=” “<=”

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

lp( ทิศทาง, วัตถุประสงค์, const.mat, const.dir, const.rhs )

> ที่เหมาะสมที่สุด <- lp(direction=”max”, object.in, const, ทิศทาง, rhs)

> เหมาะสมที่สุด

สำเร็จ: ฟังก์ชันวัตถุประสงค์คือ2625

> สรุป (เหมาะสมที่สุด)

โหมดคลาสความยาว

ทิศทางที่ 1 -ไม่มี- ตัวเลข

x.count 1 -none- ตัวเลข

วัตถุประสงค์ 2 -ไม่มี- ตัวเลข

const.count 1 -none- ตัวเลข

ข้อ จำกัด 8 -ไม่มี- ตัวเลข

int.count 1 -none- ตัวเลข

int.vec 1 -none- ตัวเลข

bin.count 1 -ไม่มี- ตัวเลข

binary.vec 1 -none- ตัวเลข

num.bin.solns 1 -ไม่มี- ตัวเลข

objval 1 -ไม่มี- ตัวเลข

โซลูชัน 2 -ไม่มี- ตัวเลข

แก้คำนำหน้า 1 -ไม่มี- ตัวเลข

compute.sens 1 -ไม่มี- ตัวเลข

sens.coef.from 1 -none- ตัวเลข

sens.coef.to 1 -ไม่มี- ตัวเลข

คู่ 1 -ไม่มี- ตัวเลข

duals.from 1 -none- ตัวเลข

duals.to 1 -ไม่มี- ตัวเลข

มาตราส่วน 1 -ไม่มี- ตัวเลข

use.dense 1 -none- ตัวเลข

thick.col 1 -none- ตัวเลข

หนาแน่น.val 1 -ไม่มี- ตัวเลข

หนาแน่น.const.nrow 1 -ไม่มี- ตัวเลข

หนาแน่น.ctr 1 -ไม่มี- ตัวเลข

use.rw 1 -none- ตัวเลข

tmp 1 -ไม่มี- ตัวอักษร

สถานะ 1 -ไม่มี- ตัวเลข

หลังจากรันโค้ดด้านบนแล้ว คุณจะได้รับวิธีแก้ไขปัญหาที่ต้องการ

ค่าที่เหมาะสมที่สุดสำหรับ y1 และ y2:

จำไว้ว่า y1 และ y2 เป็นหน่วยของผลิตภัณฑ์ A และผลิตภัณฑ์ B ที่เราต้องผลิต:

> โซลูชัน$ที่เหมาะสมที่สุด

[1] 45 75

ตัวเลขยอดขายที่ดีที่สุด:

กำไรสูงสุดที่เราสามารถสร้างได้ด้วยค่าที่ได้รับของ y1 และ y2 คือ:

> ที่เหมาะสม$objval

[1] 2625

อ่านเพิ่มเติม: พีชคณิตเชิงเส้นสำหรับการเรียนรู้ของเครื่อง

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

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

• ด้วยความนิยมที่เพิ่มขึ้นของบริการจัดส่ง การโปรแกรมเชิงเส้นจึงกลายเป็นหนึ่งในวิธีที่ได้รับความนิยมมากที่สุดในการค้นหาเส้นทางที่เหมาะสมที่สุด เมื่อคุณโดยสาร Ola หรือ Uber ซอฟต์แวร์จะใช้โปรแกรมเชิงเส้นตรงเพื่อค้นหาเส้นทางที่ดีที่สุด บริษัทจัดส่งเช่น Amazon และ FedEx ยังใช้เพื่อกำหนดเส้นทางที่ดีที่สุดสำหรับคนส่งของ พวกเขามุ่งเน้นที่การลดเวลาและค่าใช้จ่ายในการจัดส่ง
• การเรียนรู้ภายใต้การดูแลของแมชชีนเลิร์นนิงทำงานบนแนวคิดพื้นฐานของการเขียนโปรแกรมเชิงเส้น ในการเรียนรู้ภายใต้การดูแล คุณต้องค้นหาแบบจำลองทางคณิตศาสตร์ที่เหมาะสมที่สุดเพื่อทำนายผลลัพธ์ตามข้อมูลอินพุตที่ให้มา
• ภาคการค้าปลีกใช้โปรแกรมเชิงเส้นเพื่อเพิ่มประสิทธิภาพพื้นที่ชั้นวาง ด้วยแบรนด์และสินค้าที่มีอยู่มากมาย การพิจารณาว่าจะวางสินค้าไว้ที่ใดในร้านจึงเป็นงานที่เข้มงวดมาก การวางสินค้าในร้านค้าอาจส่งผลต่อยอดขายอย่างมาก เครือข่ายค้าปลีกรายใหญ่ เช่น Big Bazaar, Reliance, Walmart เป็นต้น ใช้โปรแกรมเชิงเส้นเพื่อกำหนดการจัดวางผลิตภัณฑ์ พวกเขาต้องคำนึงถึงความสนใจของผู้บริโภคในขณะเดียวกันก็รับประกันการจัดวางผลิตภัณฑ์ที่ดีที่สุดเพื่อให้เกิดผลกำไรสูงสุด
• บริษัทต่างๆ ใช้โปรแกรมเชิงเส้นเพื่อปรับปรุงห่วงโซ่อุปทานของตน ประสิทธิภาพของห่วงโซ่อุปทานขึ้นอยู่กับปัจจัยหลายอย่าง เช่น เส้นทางที่เลือก เวลา ฯลฯ โดยใช้โปรแกรมเชิงเส้นตรง พวกเขาสามารถค้นหาเส้นทางที่ดีที่สุด เวลา และการจัดสรรทรัพยากรอื่นๆ เพื่อเพิ่มประสิทธิภาพสูงสุด

เรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมเชิงเส้นและวิทยาศาสตร์ข้อมูล

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

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

• เหตุผลหลักในการเป็นนักวิทยาศาสตร์ข้อมูล
• อัลกอริทึมที่นักวิทยาศาสตร์ข้อมูลทุกคนควรรู้
• วิธีการเป็นนักวิทยาศาสตร์ข้อมูล

ในทางกลับกัน คุณสามารถเรียนหลักสูตรวิทยาศาสตร์ข้อมูลเพื่อเรียนรู้จากผู้เชี่ยวชาญในอุตสาหกรรม คุณจะได้เรียนรู้แบบโต้ตอบผ่านวิดีโอ แบบทดสอบ และโครงการต่างๆ การเรียนหลักสูตรจะช่วยให้คุณเรียนรู้ทักษะที่จำเป็นในการเป็นนักวิทยาศาสตร์ข้อมูลมืออาชีพ ตรวจสอบ IIIT-B & upGrad's PG Diploma in Data Science ซึ่งสร้างขึ้นสำหรับมืออาชีพด้านการทำงานและเสนอกรณีศึกษาและโครงการมากกว่า 10 รายการ, การประชุมเชิงปฏิบัติการเชิงปฏิบัติ, การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม, ตัวต่อตัวกับที่ปรึกษาอุตสาหกรรม, 400 ชั่วโมง ของการเรียนรู้และการช่วยเหลืองานกับบริษัทชั้นนำ