Optimization Problem with Excel Solver

Optimization เป็นแขนงหนึ่งของ Data science แต่กลับไม่ค่อยเป็นที่รู้จักเท่าไหร่นักและหากพูดถึง Optimization ในสาย Deep learning คงจะนึกถึง Algorithm ที่ใช้ปรับปรุงค่า error และ loss เช่น SGD หรือ Adam

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

ความเป็นมาแบบคร่าวๆ
Optimization อยู่ในวิชา Operations Research วิชาที่ว่าด้วยการศึกษาวิธีการตัดสินใจอย่างประสิทธิภาพโดยใช้ คณิตศาสตร์ และสถิติ โดยในปี 1827 Jean-Baptiste Joseph Fourier ได้เสนอ Linear Programming เพื่อใช้แก้ปัญหา System of linear inequalities จนมาถึงช่วงสงครามโลกครั้งที่สอง จึงได้ถูกใช้เพื่อช่วยในการวางแผนการจัดส่งกำลังและการใช้งานทรัพยากรอย่างมีประสิทธิภาพ และในช่วงเวลาเดียวกันในปี 1947 Dr. George Dantzing ได้นำเสนอ Simplex medthod ทำให้ Optimization ถูกนำไปใช้งานแพร่หลายมากขึ้น

โดยสรุปสั้นๆ Optimization คือการหาคำตอบที่ดีที่สุด (max, min) ภายใต้ข้อจำกัด (Constraints) โดยการแปลงปัญหานั้นให้อยู่ในรูปสมการคณิตศาสตร์ และเพื่อความรวดเร็วในบทความนี้เราใช้ Excel คำนวณกัน

ส่วนประกอบของสมการ Optimization

• Objective Function (สมการเป้าหมาย)
  คือฟังก์ชันที่เราต้องการหาค่าตำ่สุด หรือสูงสุด โดยเราจะกำหนดฟังก์ชันนี้ให้อยู่ในรูปของสมการทางคณิตศาสตร์ที่ติดอยู่ในรูปของ Decision variables
• Decision variables (ตัวแปรตัดสินใจ)
  คือตัวแปรที่เป็นคำตอบของการแก้สมการที่เหมาะสมที่สุด
• Constraints (สมการข้อจำกัด)
  เป็นเงื่อนไขหรือข้อจำกัดต่างๆของ objective function

“ความยากอยู่ตรงที่เราจะต้องคิดสมการออกมาให้ได้ก่อน แล้วจึงจะโยนให้คอมพิวเตอร์คำนวณ โดยในบทความนี้จะยกตัวอย่างโจทย์เพื่อความเข้าใจนะครับ”

โจทย์จัดพนักงานโดยมีวันหยุด

ห้างสรรพสินค้า MDK ต้องการพนักงานทำความสะอาดสถานที่ทุกวัน ปริมาณดังแสดงในตารางที่ 1

เวลาทำงานและค่าจ้างตามที่แสดงในตารางที่ 2 เช่น พนักงานที่ทำงานวันจันทร์ถึงศุกร์ได้ค่าจ้างวันละ 350 บาท (หยุดเสาร์อาทิตย์)

พนักงานที่ทำงานวันจันทร์ หยุดวันอังคาร แล้วทำงานต่อในวันพุธถึงวันอาทิตย์ได้ค่าจ้างวันละ 375 บาท เป็นต้น

ห้าง MDK มีนโยบายว่า อย่างน้อย 75% ของพนักงานจะต้องมีวันหยุดติดต่อกันสองวัน และอย่างน้อย 50% ของพนักงานจะต้องได้หยุดในวันหยุดสุดสัปดาห์

ต้องการทราบว่าจำนวนพนักงานท่ีต้องใช้น้อยท่ีสุดเป็นเท่าใด

Decision variables (ตัวแปรตัดสินใจ)
ตัวแปรการตัดสินใจจะนำประเภทของวันหยุดต่างๆที่ต้องนำไปคิดจ้างมาเป็นตัวแปร

S1, S2, S3, S4, S5, S6, S7, S8

Objective Function (สมการเป้าหมาย)
จากโจทย์ตีความได้ว่าห้าง MDK ต้องการจ่ายค่าจ้างให้น้อยที่สุดภายใต้เงื่อนไขการหยุดในวันต่างๆ ดังนั้นการคิดค่าจ้างจึงเป็นไปตามสมการ

MIN[(S1*350)+(S2*375)+(S3*400)+(S4*425)+(S5*425)+(S6*400)+(S7*375)+(S*375)]

Constraints (สมการข้อจำกัด)
จะพิจารณาจากเงื่อนไขในตารางที่ 1 เช่นวันจันทร์ต้องมีพนักงานมาทำงานอย่างน้อย 22 คน และมาพิจารณาตารางที่ 2 ไม่มีตัวแปรตัวไหนเลยที่หยุดวันจันทร์ และเราพิจารณาเช่นเดียวกันในเงื่อนไขถัดๆไปในตารางที่ 2

S1+S2+S3+S4+S5+S6+S7+S8 ≥ 22
S1+S4+S6+S7+S8 ≥ 13
S1+S2+S4+S5+S6+S7 ≥ 15
S1+S2+S3+S5+S8 ≥ 20
S1+S2+S3+S4+S7+S8 ≥ 18
S3+S4+S5+S6+S7+S8 ≥ 23
S2+S3+S4+S5+S6 ≥ 27

ต้องมีวันหยุดติดต่อกันสองวัน 75% ตัวแปรที่หยุดติดกัน 2 วันคือ S1, S3,S6

S1+S3+S6 ≥ (S1+S2+S3+S4+S5+S6+S7+S8)*0.75

ต้องได้หยุดในวันหยุดสุดสัปดาห์ 50% ตัวแปรที่หยุดสุดสัปดาห์คือ S1,S2,S7,S8

S1+S2+S7+S8 ≥ (S1+S2+S3+S4+S5+S6+S7+S8)*0.5

เมื่อได้สมการครบแล้วเราก็จะมายัดมันใส่ใน Excel กัน

ขั้นตอนการเรียกใช้ Solver

สำหรับ Macbook เข้า Excel > Data > Analysis Tools > เลือก Solver Add-in

สำหรับ Windows เข้า Excel > File > Options > Add-ins >
เลือก Solver Add-in> ในช่อง Manage ให้เลือก Excel Add-ins > Go

การใช้ Excel solver เพื่อแก้ปัญหา Optimizatoin

1. เขียน Decision variables ลงในตารางดังรูป โดยที่ช่องสีเหลืองจะเว้นไว้ให้เป็นค่าของตัวแปรที่เราที่จะคำนวณออกมา

2. เขียน Objective Function ลงในช่องสีฟ้าโดยเขียนเป็นสูตร ดังรูป

3. เขียนสมการ Constraints โดยที่ช่องสีเขียวแต่ละช่องอ้างอิงตามสมการที่เราได้คิดไว้ข้างต้น

4. เปิดตัว Solver และทำการใส่ค่า Parameters และผูกสมการเข้าด้วยกัน

โดยที่ในโจทย์นี้เป็นโจทย์ที่ต้องการค่าใช้จ่ายต่ำที่สุด ดังนั้นเราจะเลือก Min
เลือก Method เป็นแบบ Simplex LP

• Simplex LP : ความสัมพันธ์ระหว่าง Input กับ Output, Input และ Constrain นั้นทุกตัวมีความต่อเนื่องกันเป็นเส้นตรง (LP=Linear Programming)
• GRG Non Linear : ความสัมพันธ์ระหว่าง Input กับ Output อย่างน้อยตัวใดตัวหนึ่งมีความต่อเนื่องกันแต่ไม่ได้เป็นเส้นตรง (เช่น เส้นโค้ง)
• Evolutionary : ความสัมพันธ์ระหว่าง Input กับ Output อย่างน้อยตัวใดตัวหนึ่งไม่ได้มีความต่อเนื่องกัน ค่าผลลัพธ์หรือ Constrain เวลาคำนวณจาก Variable กระโดดไปมาได้

เมื่อใส่ Parameters ครบหมดแล้วก็กด Solve ได้เลย

โดยการทำงานของ Solver จะพยายามเปลี่ยนค่า Decision variables input ไปเรื่อยๆ ภายใต้ Constraints เพื่อหาคำตอบว่าค่าใดทำให้ Objective output มีค่าในแบบที่เราต้องการมากที่สุด

5. เมื่อโปรแกรมคำนวณให้เสร็จแล้ว เราจะได้ค่าของ Decision variables ในช่องสีเหลือง โดยที่ค่าของ Decision variables ทำให้ค่าใช้จ่ายรวมมีค่าน้อยที่สุดภายใต้เงื่อนไขที่เรากำหนดเป็นอันเสร็จพิธี