Linear Programming, Integer Programming, Dynamic Programming

กรรมวิธี เพื่อใช้แก้ปัญหา Optimization อย่าง Linear Programming, Interger Programming, และ Dynamic Programming เป็นที่คุ้นเคยกันดี แต่ว่าต่างกันอย่างไร

Linear programming

In mathematics, linear programming (LP) is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints. Informally, linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model and given some list of requirements represented as linear equations.

Integer programming is a general term that refers to any mathematical optimization or feasibility program in which some or all of the variables are restricted to be integral. In many settings the term integer program is used as short-hand for integer linear programming.

Integer unknowns

If the unknown variables are all required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) NP-hard. 0-1 integer programming or binary integer programming (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of Karp’s 21 NP-complete problems.

สำหรับ กล่าวว่า

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

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

ตัวอย่าง Linear Progragmming จากวิชากการ >

Dynamic programming

In mathematics and computer science, dynamic programming is a method of solving complex problems by breaking them down into simpler steps. It is applicable to problems that exhibit the properties of overlapping subproblems and optimal substructure (described below). When applicable, the method takes much less time than naive methods.

Bottom-up dynamic programming simply means storing the results of certain calculations, which are then re-used later because the same calculation is a sub-problem in a larger calculation. Top-down dynamic programming involves formulating a complex calculation as a recursive series of simpler calculations.


– อ้างอิง wiki Linear Programming, Dynamic Programming, : , ,



Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s