Linear Programming 

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

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

การที่เรานำข้อมูลปัญหามาสู่สมการคณิตศาสตร์เพื่อหา Maximize point หรือ Minimize point อย่างนี้ เราเรียกว่า " Program " หรือบางครั้งก็ใช้คำว่า " Mathematical Programming"  ซึ่งประกอบไปด้วยองค์ประกอบสำคัญ 3 ส่วนคือ

1. Decision variable หมายถึงตัวแปลที่ใช้ตัดสินใจ ซึ่งผู้บริหารหรือผู้มีอำนาจตัดสินใจจะเป็นผู้กำหนด

2. Objective function หมายถึงความต้องการสุดท้าย ที่ต้อง Maximize หรือ Minimize แล้วแต่กรณี

3. Constrains หมายถึง ข้อจำกัด หรือ เงื่อนไข ที่จำเป็นต้องทำตามหรือหลีกเลี่ยงไม่ได้

ซึ่ง ที่นิยมใช้มากที่สุดในปัจจุบันนี้ก็คือ Linear Programming Model ซึ่งความหมายก็คือแบบจำลองที่ใช้สำหรับหา Maximize or Minimize ที่ สมการความสัมพันธ์ระหว่าง Objective function และ Constrains เป็นเส้นตรง (Linear relationship)

เพราะเหตุใด Linear programming Model จึงเป็นที่นิยมใช้อย่างกว้างขวาง

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

2. มีวิธีการ หรือเทคนิค ในการวิเคราะห์เป็นที่แพร่หลาย 

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

ข้อกำหนดของ Linear Programming

1. ตัวแปรทุกค่าต้องคงที่แน่นอน  และรู้ค่าจริง

2. สมการที่ได้จะให้ผลลัพธ์ เท่าเดิมถ้าสัมประสิทธิ์ เพิ่มค่าในอัตราส่วนเท่ากัน ( ตัวคูณเท่ากัน)

3. Decision variable แต่ละตัวต้องเป็นอิสระต่อกัน ( ไม่เกิด Interaction )

ตัวอย่าง บริษัทผลิตตุ๊กตาแห่งหนึ่ง ผลิตอยู่ 2 รุ่น คือใหญ่กับเล็ก โดยปริมาณวัตถุดิบที่ใช้ กำไร และเวลาในการผลิตเป็นดังตาราง โดยมีข้อจำกัดคือ มีพลาสติกที่จะใช้ผลิตเหลืออยู่ 1000 กก. ในแต่ละสัปดาห์ มีเวลาผลิตจริงอยู่ 40 ชั่วโมง  และผู้บริหารของบริษัทตกลงว่าในแต่สัปดาห์นั้นจะผลิตตุ๊กตารวมกันทั้ง 2 รุ่นนั้นไม่เกิน 700 โหล และต้องผลิตรุ่นใหญ่ไม่ให้มากกว่ารุ่นเล็กเกิน 350 โหล

จงหารูปแบบการผลิตที่จะทำให้บริษัทได้กำไรสูงที่สุดเท่าที่จะเป็นไปได้ ภายใต้ข้อกำหนดและเงื่อนไขตามที่กล่าวมาข้างต้น

เราสามารถเขียน Objective function ได้ดังนี้

                                                   Maximum Profit  = 800L + 500S

ข้อจำกัดและเงื่อนไข (Constraints)

1. ปริมาณวัตถุดิบ (Plastic) มี 1000 กก.  แต่ต้องใช้ผลิตทั้งรุ่นใหญ่และเล็ก ดังนั้นอสมการจะเป็นดังนี้

                                                2L + 1S <= 1000

    ค่าสัมประสิทธิ์ ของตัวแปรในอสมการนั้น คือปริมาณพลาสติกที่ใช้ต่อหน่วยผลิต

2. เวลาในการผลิตต่อสัปดาห์ 40 * 60 = 2400 นาที

                                               3L + 4S <= 2400

3. ข้อจำกัดในแง่การบริหาร หรือการตลาด (Total production limit) คือทั้งสองรุ่นรวมกันแล้วต้องไม่เกิน 700 โหล ซึ่งอาจจะเป็นเงื่อนไขของฝ่ายการตลาด

                                                L + S <= 700

4. เงื่อนไขความหลากหลายของการผลิต ( Balance product mix ) หมายความว่า บริษัทจำเป็นต้องวางขายตุ๊กตาทั้งสองรุ่น นี้ในตลาด ด้วยเหตุผลทางการตลาด หรือการกระจายความเสี่ยง ซึ่งผู้บริหารกำหนดว่า ต้องผลิตรุ่นใหญ่มากกว่ารุ่นเล็กได้ไม่เกิน 350 โหล

                                               L - S <= 350

เงื่อนไขอีกข้อหนึ่งซึ่งเป็นข้อกำหนดทางคณิตศาสตร์ คือทั้งสองตัวแปร (รุ่นใหญ่และเล็ก) จะต้องไม่มีค่าเป็นลบ หรือน้อยกว่า 0 นั่นเอง ( Nonnegativity of Decision variables)

                                              L , S >= 0

เมื่อเรานำสมการจากข้อกจำกัดหรือเงื่อนไขต่างๆ มาเขียนเป็น Mathematical Model จะได้ดังนี้

                      Maximize              800L + 500S                           (รายได้สูงสุด ต่อสัปดาห์)

                      Constraint              2L   +  S  <= 1000                (วัตถุดิบ พลาสติก)

                                                    3L  +  4S  <= 2400                (เวลาในการผลิตใน 1 สัปดาห์)

                                                      L   +  S   <= 700                  (ผลิตรวม)

                                                      L   -  S    <= 350                  ( ความหลากหลายของ ผลิตภัณฑ์)

                                                      L  ,  S  >=  0                        ( Nonnegativity)

การวิเคราะห์โดยการใช้กราฟ

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

1. เริ่มต้นเราจะต้องพิจารณา ที่ Nonegativity ก่อน จาก L , S >= 0 นั่นแปลว่าเวลาเราจะทำกราฟ จะมีปรากฏอยู่แต่ใน Quadrant ที่ 1 คือ แกน X , Y มีค่ามากกว่า 0 เสมอ

2. เขียนกราฟเส้น Constraints ที่ 1  จาก  2L  +  S  <=  1000

                       ถ้าเราให้  L = 0  ก็จะได้    S <= 1000

                      และ ถ้าเราให้   S = 0 ก็จะได้    2L <= 1000 นั่นคือ   L <= 500

ในบริเวณระบายสีคือบริเวณที่เป็นไปได้ ตามอสมการ  ( Feasible region )

3. เขียนกราฟเส้น Constraints ที่ 2 เพิ่มเข้าไปในกราฟ จาก 3L  +  4S  <= 2400 

                      ถ้าเราให้    L = 0   ก็จะได้        4S <= 2400          นั่นคือ        S <= 600

                     และถ้าเราให้   S = 0   ก็จะได้    3L <= 2400            นั่นคือ          L <= 800

 ในบริเวณระบายสีคือบริเวณที่เป็นไปได้ ( Feasible region ) ตามอสมการ ทั้งสอง

3. เขียนกราฟ Constraints ที่ 3 เพิ่มเข้าไปในกราฟ คือปริมาณการผลิตรวม  จาก  L+ S <= 700

                                ถ้าให้ L= 0 ก็จะได้ S <= 700  เช่นเดียวกัน ถ้าให้ S = 0 ก็จะได้  L <= 700

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

4. เขียนกราฟ Constraints ที่ 4 เพิ่มเข้าไปในกราฟ คือ Product mix  จาก  L- S <= 350

                                ถ้าให้ L= 0 ก็จะได้ S <= - 350  หรือ  ถ้าให้ L = 700 ก็จะได้  S <= 350

                               เช่นเดียวกัน ถ้าให้ S = 0 ก็จะได้  L <= 350

ในบริเวณระบายสีคือบริเวณที่เป็นไปได้ ( Feasible region ) ตามอสมการ ทั้งหมด จะเห็นได้ว่า นั่นหมายความว่า ค่า S และ  L ที่เป็นไปได้ที่ทำให้เกิด Optimum จะอยู่ภายในบริเวณระบายสีเท่านั้น

5. หาจุดที่เป็นไปได้ ( Feasible point ) ที่จะทำให้เกิด Optimum point  

ถ้าเราลองพิจารณาบริเวณระบายสี (Feasible region) นั้น ถ้าเราลองเลือกจุดตัดใดจุดหนึ่ง ภายในบริเวณ ระบายสีเราจะเรียกว่า จุดเป็นไปได้ภายในเขต ( Interior point) เช่นเดียวกัน ถ้าจุดใดจุดหนึ่งอยู่นอกบริเวณ เราจะเรียกว่าจุดที่เป็นไปไม่ได้เลย ( Infeasible points) ความหมายคือจุดนี้จะไม่ทำให้เกิด Optimum point ได้เลย

หากเราเลือกจุดที่อยู่บนเส้น Constraint ที่เป็นกรอบของบริเวณ ระบายสี เราจะเรียกว่า จุดเขตแบ่งระหว่าง Feasible กับ Infeasible region หรือเรียกว่า Boundary point.

จุดที่อยู่ตรงจุดตัดระหว่าง เส้น Constraints ที่ล้อมกรอบบริเวณระบายสีอยู่ทั้งหมดนั้น เราจะเรียกว่าจุดยอดสุด ( Extreme points )

การหาจุดที่ดีที่สุด โดยวิธีใช้กราฟ ( Solving graphically for an optimal solution)

เมื่อเราได้กราฟ ได้ Feasible region รวมทั้ง Feasible points มา จะทำอย่างไรเราถึงจะรู้ได้ว่า จุดที่ดีที่สุดอยู่ตรงไหน (Optimum point)

วิธีที่ดีที่สุดตอนนี้ลอง พล้อต เส้น Maximize หรือสมการ Objective บนกราฟ ดู โดยเราจะสมมุติค่า Maximize ขึ้นมาค่าหนึ่ง ดังตัวอย่าง

                 สมมติเราให้        800L + 500S = 500000  

                 ถ้าเราให้  L = 0  ก็จะได้  S = 1000  และถ้าให้ S = 0 ก็จะได้ L =  625

จะเห็นว่าเส้นของสมการ Objective ที่เราทดลองนั้น ไม่ได้ผ่าน Feasible region เลย แสดงว่า บริษัทจะไม่สามารถเลือกปริมาณตุ๊กตา L , S size ตามเส้นสมการดังกล่าวได้เลย เพราะจะไม่ได้ตามข้อจำกัด 

เราทดลองเพิ่มเส้นสมการ Objective อีกเส้น โดย สมมติให้

                                     800L + 500S = 200000

                                      ดังนั้น   ถ้าให้ L = 0 ก็จะได้ S = 400  และถ้าให้ S = 0 ก็จะได้ L =  250

จะเห็นว่าเส้นของสมการ Objective ที่เราทดลองนั้น อยู่ภายในเขต Feasible region ทั้งหมด แสดงว่า แม้บริษัทจะสามารถเลือกปริมาณตุ๊กตา L , S size ตามเส้นสมการดังกล่าวในการผลิตได้ เพื่อให้ได้ Profit ตามต้องการ แต่บริษัทก็จะเสียโอกาสที่จะได้ Maximum profit เพราะตามสมการดังกล่าวจะไม่มีจุด Maximize เลย

จากการที่เราได้พล้อต เส้นตามสมการ Objective สองเส้นนั้น ทำให้เราทราบได้ว่า เส้นสมการที่มีจุด Maximize จะขนานกับเส้นที่เกิดจากสมการ Objective ทั้งสองเส้นนี้เสมอ หมายความว่า สมการ Objective จะให้ความชัน (Slope) ของเส้นกราฟ เท่ากันเสมอ 

ถ้าลองเพิ่มเส้น สมการ Objective เข้าไปในกราฟ หลายๆเส้นระหว่าง 2 เส้นที่ได้พล้อตไปแล้วนั้น เราก็จะได้เส้น ที่มี Maximize point แน่นอน โดยเส้นที่เราเลือก คือ

                                800L + 500S = 300000

                                800L + 500S = 400000

                                800L + 500S = 436000

จากกราฟ เราจะพบว่า สมการ Ojective ที่ให้ Profit มากที่สุด และยังสัมผัสกับ Feasible region อยู่ ก็คือ  800L + 500S = 436000 และจุดสุดท้ายที่เส้น Objective ที่ยังสัมผัสกับ Feasible region ก็คือจุด Optimal point นั่นเองและจุดดังกล่าวนี้ก็เป็น Extreme point ด้วย ( หมายความว่า จะมี Optimum point เพียงจุดเดียว )

ถ้าดูจากกราฟ จุด Extreme point ที่เป็นจุด Optimal point เกิดจากจุดตัดของเส้น Constraints 2 เส้น คือ

                                                    2L   +  S  = 1000                (วัตถุดิบ พลาสติก)

                                                    3L  +  4S = 2400                (เวลาในการผลิตใน 1 สัปดาห์)

ถ้าเราเอา 4 คูณสมการวัตถุดิบ  จะได้

                                                    8L + 4S = 4000

นำสมการ เวลาในการผลิต ไปลบสมการ ที่ได้ใหม่จะได้ผลลัพธ์ดังนี้

                      8L + 4S - 3L - 4S = 4000-2400

                      5L  = 1600

ดังนั้น   L = 320 

นำค่า L = 320 ไปแทนค่าในสมการวัตถุดิบ จะได้ 

                         2(320) + S = 1000

 ดังนั้น               S = 360 

เพราะฉะนั้น จุด Optimal คือ  จุด  L = 320 , S = 360

นั่นคือโรงงานนี้ จะต้องผลิต ตุ๊กตา ขนาดใหญ่ ( L ) = 320 โหล และขนาดเล็ก (S) = 360 โหล ต่อสัปดาห์ ถึงจะได้ผลตอบแทนสูงที่สุดภายใต้ข้อจำกัดและเงื่อนไขตามที่กำหนดไว้

คำศัพท์ที่พบใน Linear programming

1. Extreme point คือจุดภายในบริเวณ Feasible region ที่เกิดจากจุดตัดของสมการ Constraints 2 เส้น

2. Binding constraints คือข้อจำกัดที่ไม่มีข้อยืดหยุ่นเลย หรือหลีกเลี่ยงไม่ได้ และจุดตัดของเส้นกราฟที่เกิดจาก สมการ Binding constraint จะเป็น Optimal point จากโจทย์ข้อนี้ วัตถุดิบ(Plastic) และเวลาในการผลิต (Production time) คือ Constraint ที่สำคัญ ที่ผู้บริหารจะต้องดูแล (Focus) เป็นพิเศษ

3. Slack  หมายถึงส่วนที่เหลือ หรือส่วนที่ยังสามารถยืดหยุ่นได้

                จากตัวอย่างข้อนี้ Plastic และเวลา (Production time) ถือว่าไม่มี Slack เพราะถูกใช้จนหมด นั่นเอง

                 แต่ถ้าเป็นจำนวนที่ผลิตรวม (Total production) จะมี Slack เพราะ   L=320) +S=360 = 680 ยังเหลือ 20 ถึงจะถึงจุดจำกัด ลักษณะนี้เราเรียกว่าเกิด Slack = 20  ในบางครั้งเราอาจจะเห็นศัพท์คำว่า  Surplus แทน

4 Shadow prices คือราคาหรือผลประโยชน์ที่หายไป หากเราไม่สามารถผลิตได้ตามที่ผลการวิเคราะห์นี้กำหนดให้ เช่น

                   จากตัวอย่าง หากโรงงานนี้ ตัดสินใจผลิตตุ๊กตาขนาด L = 321 และ S = 359 โหล จะพบว่า  Optimal point จะเปลี่ยนไป

                                       800(321) + 500(359) = 436300  

                    นั่นคือ ได้เงินเพิ่มขึ้น 300 บาทจากจุดที่ได้จากการวิเคราะห์        

เมื่อมาดู จากสมการข้อจำกัด Constraints  มีการใช้ Plastic เพิ่มขึ้นรวมแล้ว 1 กก.  ( L ใช้เพิ่ม = 2 กก ขณะที่  S  ใช้น้อยลงเพียง 1 กก ) นั่นแสดงว่า หากมีการเปลี่ยนแปลงปริมาณ Plastic 1 หน่วยมี Profit เปลี่ยนไป 300 บาท

 ดังนั้น จำนวนเงินที่เปลี่ยนไป เมื่อ Optimal point เปลี่ยนไป 1 หน่วย เรียกว่า Shadow price