อัลกอริทึมของเบนสันซึ่งตั้งชื่อตามแฮโรลด์ เบนสันเป็นวิธีการแก้ ปัญหา การเขียนโปรแกรมเชิงเส้นแบบหลายวัตถุประสงค์และการเขียนโปรแกรมเชิงเส้นเวกเตอร์ โดยทำงานด้วยการค้นหา "จุดสุดขั้วที่มีประสิทธิภาพในชุดผลลัพธ์" ^{[ 1 ]} แนวคิดหลักในอัลกอริทึมของเบนสันคือการประเมินภาพบนสุดของ ปัญหา การเพิ่มประสิทธิภาพเวกเตอร์โดย การ ตัดระนาบ^{[ 2 ]}

พิจารณาโปรแกรมเชิงเส้นเวกเตอร์

${\displaystyle \min _{C}Px\;{\text{ subject to }}Ax\geq b}$

สำหรับ, , และกรวยเรียงลำดับนูนทรงหลายเหลี่ยมที่มีภายในไม่ว่างเปล่าและไม่มีเส้นตรง เซตที่เป็นไปได้คือโดยเฉพาะอย่างยิ่ง อัลกอริทึมของเบนสันจะค้นหาจุดสุดขั้วของเซตซึ่งเรียกว่าภาพบน^{[ 2 ]}${\displaystyle P\in \mathbb {R} ^{q\times n}}$${\displaystyle A\in \mathbb {R} ^{m\times n}}$${\displaystyle b\in \mathbb {R} ^{m}}$${\displaystyle C}$${\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}}$${\displaystyle P[S]+C}$

ในกรณีนี้จะได้กรณีพิเศษของโปรแกรมเชิงเส้นแบบหลายวัตถุประสงค์ ( การหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์ ) ${\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}}$

มีอัลกอริธึมของเบนสันแบบคู่^{[ 3 ]}ซึ่งอิงตามความเป็นคู่ทางเรขาคณิต^{[ 4 ]}สำหรับโปรแกรมเชิงเส้นหลายวัตถุประสงค์

Bensolve - โปรแกรมแก้สมการ VLP ฟรี

• www.bensolve.org

ภายใน

• ลิงก์ไปยัง GitHub