การเขียนโปรแกรมจำนวนเต็มผสม: คู่มือการตัดสินใจด้วยคอมพิวเตอร์

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

วันนี้เราจะมาสำรวจพลังของการวิจัยการดำเนินงานโดยเดินผ่านปัญหาสมมุติฐาน โดยเฉพาะอย่างยิ่ง เราจะใช้การเขียนโปรแกรมแบบผสมจำนวนเต็ม (MIP) เพื่อกำหนดรูปแบบการจัดพนักงานที่เหมาะสมที่สุดสำหรับโรงงานสมมติ

อัลกอริทึมการวิจัยการดำเนินงาน

ก่อนที่เราจะลงลึกในปัญหาตัวอย่าง เราควรอ่านแนวคิดพื้นฐานในการวิจัยการดำเนินงานและทำความเข้าใจเครื่องมือเล็กน้อยที่เราจะใช้ในวันนี้ก่อน

อัลกอริธึมการเขียนโปรแกรมเชิงเส้น

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

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

ในตัวอย่างง่ายๆ ของเรา เราจะเห็นได้ว่าผลลัพธ์ที่ดีที่สุดคือ 5 โดยมี a = 2 และ b = 3 แม้ว่านี่จะเป็นเพียงตัวอย่างเล็กน้อย แต่คุณอาจจินตนาการถึงโมเดลโปรแกรมเชิงเส้นตรงที่ใช้ตัวแปรนับพันและข้อจำกัดหลายร้อยรายการ .

ตัวอย่างที่ดีอาจเป็นปัญหาพอร์ตการลงทุน ซึ่งคุณอาจลงเอยด้วยโค้ดหลอกด้านล่าง:

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

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

อัลกอริธึมการเขียนโปรแกรมจำนวนเต็ม

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

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

ตัวอย่างปัญหาเป้อาจมีพารามิเตอร์ต่อไปนี้:

และโมเดล MIP จะมีลักษณะดังนี้:

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

ทางออกที่ดีที่สุด ในกรณีนี้ คือ a=0, b=1, c=0, d=1 โดยมีค่าของรายการทั้งหมดเท่ากับ 17

ปัญหาที่เราจะแก้ไขในวันนี้ยังต้องเขียนโปรแกรมจำนวนเต็ม เนื่องจากพนักงานในโรงงานสามารถกำหนดเวลากะสำหรับกะงานได้หรือไม่—เพื่อความง่าย คุณไม่สามารถกำหนดเวลาให้พนักงานเป็นกะ 2/3 ของกะที่โรงงานนี้ได้

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

ตัวอย่างปัญหา: การจัดตารางเวลา

คำอธิบายปัญหา

วันนี้เราจะมาสำรวจปัญหาของการรับพนักงานในโรงงาน ในฐานะผู้บริหารโรงงาน เราจะต้องการลดต้นทุนค่าแรง แต่เราต้องการให้แน่ใจว่าครอบคลุมเพียงพอสำหรับทุกกะเพื่อตอบสนองความต้องการในการผลิต

สมมติว่าเรามีห้ากะโดยมีความต้องการพนักงานดังต่อไปนี้:

และสมมติว่าเรามีคนงานดังต่อไปนี้:

เพื่อให้ปัญหาง่ายขึ้น ให้เราสมมติในขณะที่ข้อกังวลเพียงอย่างเดียวคือความพร้อมใช้งานและค่าใช้จ่าย

เครื่องมือของเรา

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

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

เพื่อแสดงให้เห็นถึงความเรียบง่ายและความสง่างามของ PuLP ต่อไปนี้คือปัญหาของเป้จากก่อนหน้านี้และแก้ไขได้ใน PuLP:

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

เรียกใช้สิ่งนี้และคุณควรได้ผลลัพธ์:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

ตอนนี้เข้าสู่ปัญหาการจัดตารางเวลาของเรา!

การเข้ารหัสโซลูชันของเรา

การเข้ารหัสของโซลูชันของเราค่อนข้างตรงไปตรงมา ขั้นแรก เราจะต้องกำหนดข้อมูลของเรา:

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

ต่อไปเราจะต้องการกำหนดรูปแบบ:

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

และตอนนี้เราแค่ขอให้มันแก้ปัญหาและพิมพ์ผลลัพธ์ออกมา!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

เมื่อคุณรันโค้ด คุณจะเห็นผลลัพธ์ต่อไปนี้:

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

เพิ่มระดับความยากเล็กน้อย: ข้อจำกัดเพิ่มเติม

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

ข้อจำกัดเพิ่มเติม

สมมุติว่าเนื่องจากข้อบังคับด้านแรงงานใหม่ไม่สามารถมอบหมายงานให้มากกว่า 2 กะได้ เพื่อรองรับการทำงานที่เพิ่มขึ้น เราได้คัดเลือกความช่วยเหลือจาก Dothraki Staffing Group ซึ่งจะจัดหาคนงาน Dothraki มากถึง 10 คนสำหรับแต่ละกะในอัตรา 40 ดอลลาร์ต่อกะ

นอกจากนี้ สมมติว่าเนื่องจากความขัดแย้งระหว่างบุคคลภายนอกโรงงานของเรา Cersei และ Jaime ไม่สามารถทำงานกะร่วมกับ Daenerys หรือ Jon ได้ นอกจากนี้ Jaime และ Cersei ไม่สามารถทำงานร่วมกันได้ ในที่สุด Arya ซึ่งมีความสัมพันธ์ระหว่างบุคคลที่ซับซ้อนเป็นพิเศษ ไม่สามารถทำงานกะเดียวกันกับ Jaime, Cersei หรือ Melisandre ได้

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

สารละลาย

อย่างไรก็ตาม ด้วยการเขียนโปรแกรมจำนวนเต็มผสม มันง่ายกว่ามาก เราเพียงแค่ต้องแก้ไขรหัสของเราดังนี้:

กำหนดรายการแบนและข้อจำกัดบางประการ:

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

เติมค่าตัวแปรสำหรับการนำข้อจำกัดการแบนและกะสูงสุดไปใช้:

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

เพิ่มตัวแปร Dothraki:

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

เรายังจำเป็นต้องมีการวนรอบที่ปรับเปลี่ยนเล็กน้อยสำหรับความต้องการกะและแบนในการคำนวณ:

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

และสุดท้ายเพื่อพิมพ์ผลลัพธ์:

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

และเราควรจะไปได้ดี เรียกใช้รหัสและคุณจะเห็นผลลัพธ์ดังนี้:

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

และเราก็ได้ผลลัพธ์ที่เคารพต่อรายชื่อคนงานที่ถูกสั่งห้าม ปฏิบัติตามกฎระเบียบด้านแรงงาน และใช้คนงาน Dothraki อย่างรอบคอบ

บทสรุป

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

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

คุณสามารถค้นหารหัสทั้งหมดที่เกี่ยวข้องกับบทความนี้ได้ที่ GitHub หากคุณต้องการพูดคุยเพิ่มเติม แบ่งปันความคิดเห็นของคุณด้านล่าง!