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

เมื่อกำหนดระบบที่ลดค่าให้น้อยที่สุดภายใต้เงื่อนไขเวกเตอร์ต้นทุนที่ลดลงสามารถคำนวณได้เป็น โดยที่คือเวกเตอร์ต้นทุนคู่ ${\displaystyle \mathbf {c} ^{T}\mathbf {x} }$${\displaystyle \mathbf {Ax} \leq \mathbf {b} ,\mathbf {x} \geq 0}$${\displaystyle \mathbf {c} -\mathbf {A} ^{T}\mathbf {y} }$${\displaystyle \mathbf {y} }$

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

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

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

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

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

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

ถ้าค่าที่เหมาะสมที่สุดของตัวแปรเป็นบวก (ไม่ใช่ศูนย์) ต้นทุนที่ลดลงจะเป็นศูนย์เสมอ ถ้าค่าที่เหมาะสมที่สุดของตัวแปรเป็นศูนย์และต้นทุนที่ลดลงที่สอดคล้องกับตัวแปรก็เป็นศูนย์ด้วย แสดงว่ามีมุมอื่นอย่างน้อยหนึ่งมุมที่อยู่ในคำตอบที่เหมาะสมที่สุดเช่นกัน ค่าของตัวแปรนี้จะเป็นบวกที่มุมที่เหมาะสมที่สุดมุมใดมุมหนึ่ง" ^{[ 1 ]}

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