คณิตศาสตร์เชิงเส้นเชิงโปรแกรม

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

การเพิ่มประสิทธิภาพ: การเขียนโปรแกรมเชิงเส้น

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

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

ขึ้นอยู่กับชุดของข้อ จำกัด ที่แสดงเป็นอสมการ:

a's, b's และ c's คือค่าคงที่ที่กำหนดโดยความสามารถความต้องการค่าใช้จ่ายผลกำไรและข้อกำหนดและข้อ จำกัด อื่น ๆ ของปัญหา ข้อสมมติฐานพื้นฐานในการประยุกต์ใช้วิธีนี้คือความสัมพันธ์ที่หลากหลายระหว่างอุปสงค์และความพร้อมใช้งานนั้นเป็นแบบเส้นตรง นั่นคือไม่มีของ x _ฉันถูกยกให้เป็นพลังงานอื่นที่ไม่ใช่ 1. เพื่อให้ได้วิธีการแก้ปัญหานี้ก็เป็นสิ่งจำเป็นที่จะหาวิธีการแก้ปัญหาของระบบการทำงานของความไม่เท่าเทียมกันเชิงเส้น (นั่นคือชุดของ n ค่า ตัวแปร x _iที่ตอบสนองความไม่เท่าเทียมกันทั้งหมดได้พร้อมกัน) ฟังก์ชันวัตถุประสงค์จะถูกประเมินโดยการแทนที่ค่าของ x _iในสมการที่กำหนด f

การประยุกต์ใช้วิธีการโปรแกรมเชิงเส้นเป็นความพยายามครั้งแรกอย่างจริงจังในช่วงปลายทศวรรษที่ 1930 โดยนักคณิตศาสตร์โซเวียต Leonid Kantorovich และนักเศรษฐศาสตร์ชาวอเมริกัน Wassily Leontief ในพื้นที่ของตารางการผลิตและเศรษฐศาสตร์ตามลำดับ แต่งานของพวกเขาก็ถูกเพิกเฉยมานานหลายทศวรรษ ในช่วงสงครามโลกครั้งที่สองการเขียนโปรแกรมเชิงเส้นถูกใช้อย่างกว้างขวางเพื่อจัดการกับการขนส่งการกำหนดเวลาและการจัดสรรทรัพยากรภายใต้ข้อ จำกัด บางประการเช่นค่าใช้จ่ายและความพร้อมใช้งาน แอปพลิเคชั่นเหล่านี้สร้างความยอมรับได้ของวิธีนี้มากขึ้นซึ่งได้แรงผลักดันเพิ่มเติมในปี 1947 ด้วยการแนะนำวิธีการทางคณิตศาสตร์ของนักคณิตศาสตร์ชาวอเมริกัน George Dantzig ซึ่งเป็นวิธีแก้ปัญหาการเขียนโปรแกรมเชิงเส้นอย่างง่าย

อย่างไรก็ตามเมื่อมีความพยายามที่ซับซ้อนยิ่งขึ้นเกี่ยวกับตัวแปรมากขึ้นจำนวนของการดำเนินการที่จำเป็นก็เพิ่มขึ้นอย่างทวีคูณและเกินขีดความสามารถในการคำนวณของแม้แต่คอมพิวเตอร์ที่ทรงพลังที่สุด จากนั้นในปี 1979 นักคณิตศาสตร์ชาวรัสเซีย Leonid Khachiyan ค้นพบอัลกอริทึมแบบพหุนาม - ซึ่งจำนวนของขั้นตอนการคำนวณเพิ่มขึ้นเป็นพลังของจำนวนของตัวแปรแทนที่จะอธิบายแทนจึงช่วยให้แก้ปัญหาที่ไม่สามารถเข้าถึงได้จนบัดนี้ อย่างไรก็ตามอัลกอริทึมของ Khachiyan (เรียกว่าวิธี ellipsoid) นั้นช้ากว่าวิธี simplex เมื่อใช้งานจริง ในปี 1984 Narendra Karmarkar นักคณิตศาสตร์ชาวอินเดียค้นพบอัลกอริธึมแบบพหุนามเวลาอีกรูปแบบหนึ่งซึ่งเป็นวิธีการจุดภายในซึ่งพิสูจน์ได้ว่าสามารถแข่งขันกับวิธีซิมเพล็ก