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

การปรับประสิทธิภาพใน sql server 2008 ทีละขั้นตอน

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

อัลกอริทึมการวิจัยปฏิบัติการ

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

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

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

Maximize a + b (objetive) Subject a: a <= 2 (restriction 1) b <= 3 (restriction 2)

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

ตัวอย่างที่ดีอาจเป็นปัญหาพอร์ตการลงทุนที่คุณอาจต้องจบลงด้วยสิ่งต่อไปนี้ในรหัสหลอก:

Maximize Subject to: Etc. ...

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

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

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

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

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

วัตถุ	มูลค่า (หน่วย $ 10)	ขนาด (หน่วยทั่วไป)
กล้อง	5	2
ตุ๊กตาลึกลับ	7	4
แอปเปิ้ลไซเดอร์ขวดใหญ่	2	7
แตรฝรั่งเศส	10	10

และแบบจำลอง 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 ของกะในโรงงานนี้ได้

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

ตัวอย่างปัญหา: การเขียนโปรแกรม

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

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

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

กะ 1	กะ 2	กะ 3	กะ 4	กะ 5
1 คน	4 คน	3 คน	5 คน	2 คน

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

ชื่อ	ความพร้อมใช้งาน	ราคาต่อกะ ($)
Melisandre	1, 2, 5	ยี่สิบ
รำข้าว	2. 3. 4. 5	สิบห้า
Cersei	3. 4	35
Daenerys	สี่ห้า	35
ธีออน	2, 4, 5	10
จอน	1, 3, 5	25
Tyrion	2, 4, 5	30
เจมส์	2, 3, 5	ยี่สิบ
อารี	1, 2, 4	ยี่สิบ

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

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

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

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

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

import pulp as pl # declarar algunas variables # cada variable es una variable binaria que es 0 o 1 # 1 significa que el artículo irá a la mochila 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 el problema prob = pl.LpProblem('knapsack', pl.LpMaximize) # función objetivo - maximizar el valor de los objetos en la mochila prob += 5 * a + 7 * b + 2 * c + 10 * d # restricción: el peso de los objetos no puede exceder 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 estado = prob.solve() # resuelve usando el solucionador predeterminado, que es cbc print(pl.LpStatus[status]) # imprime el estado legible por humanos # imprime los valores 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

ถึงปัญหาการเขียนโปรแกรมของเราแล้ว!

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

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

โครงการเรียนรู้ c++

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 el modelo: queremos minimizar el costo prob = pl.LpProblem('scheduling', pl.LpMinimize) # algunos modelos de variable 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']) # establece el objetivo para que sea la suma del costo prob += sum(cost) # establece los requerimientos de cambio 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

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

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

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

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

นอกจากนี้สมมติว่าเนื่องจากปัญหาความขัดแย้งระหว่างบุคคลภายนอกโรงงานของเรา Cersei และ Jaime ไม่สามารถทำงานกะกับ Daenerys หรือ Jon ได้ นอกจากนี้ Jaime และ Cersei ไม่สามารถทำงานกะใด ๆ ร่วมกันได้ ในที่สุดอารีผู้ซึ่งมีความสัมพันธ์ระหว่างบุคคลที่ซับซ้อนเป็นพิเศษก็ไม่สามารถทำงานร่วมกับ 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

กรอกตัวแปรเพื่อใช้การห้ามและข้อ จำกัด การเปลี่ยนแปลงสูงสุด:

กวดวิชา powerpivot ทีละขั้นตอน

for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable('%s_%d' % (worker, shift), 0, 1, pl.LpInteger) # almacena algunos datos variables para que podamos implementar la restricción de prohibición var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # almacena vars por variable para que podamos implementar la restricción de cambio máximo 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

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

# establece los requerimientos de cambio for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # establece los requerimientos de prohibición 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 # establece los estándares de trabajo: 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']))

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

Resultado: Óptimo Shift: 0 trabajadores: Arya dothrakis contratados: 0 Shift: 1 trabajador: Melisandre, Theon, Tyrion, Jaime dothrakis contratados: 0 Shift: 2 trabajadores: Bran, Jon dothrakis contratados: 1 Shift: 3 trabajadores: Bran, Daenerys, Theon, Tyrion, Arya dothrakis contratados: 0 Shift: 4 trabajadores: Melisandre, Jaime dothrakis contratados: 0

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

ข้อสรุป

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

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

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