लिनियर प्रोग्रामिंग: वास्तविक दुनिया की अनुकूलन समस्याओं का समाधान

ऑपरेशंस मैनेजर्स एक बार-बार आने वाली चुनौती का सामना करते हैं: बहुत सारे निर्णय, बहुत सी बाधाएँ, और सर्वोत्तम समाधान खोजने का कोई स्पष्ट तरीका नहीं। एक वितरण नेटवर्क को दर्जनों रूट्स में ईंधन लागत को न्यूनतम करना होता है, साथ ही डिलीवरी विंडो, वाहन क्षमता और ड्राइवर शेड्यूल का पालन भी करना होता है।

इन दोनों समस्याओं की गणितीय संरचना समान है। जब आपके उद्देश्य और बाधाएँ रैखिक संबंधों के रूप में व्यक्त किए जा सकते हैं, तो आप लिनियर प्रोग्रामिंग समस्या पर काम कर रहे होते हैं। हम लिनियर प्रोग्रामिंग की परवाह इसलिए करते हैं क्योंकि यह सीमित संसाधनों और प्रतिस्पर्धी आवश्यकताओं के बीच काम करते समय इष्टतम समाधान ढूंढती है।

लिनियर प्रोग्रामिंग की शक्ति उसकी गारंटी में निहित है: यदि कोई व्यवहार्य समाधान मौजूद है, तो एल्गोरिदम इष्टतम वाला ढूंढ लेगा। बेशक, वास्तविक अनुप्रयोग शायद ही पाठ्यपुस्तक उदाहरणों में पूरी तरह फिट बैठते हैं, लेकिन मूल ढाँचे को समझना यह पहचानने में मदद करता है कि कब ऑप्टिमाइज़ेशन अनुमान लगाने की जगह ले सकता है।

यह गाइड आपको नींव से लेकर कार्यात्मक Python इम्प्लीमेंटेशंस तक ले जाती है। हम सरल द्विचर समस्याओं से, जिन्हें आप ज्यामितीय रूप से देख सकते हैं, लेकर उन जटिल परिदृश्यों तक बढ़ेंगे जिनके लिए एल्गोरिथ्मिक समाधान की आवश्यकता होती है। आप यह भी समझेंगे कि ऑप्टिमाइज़ेशन को काम करने योग्य बनाने वाला गणितीय सिद्धांत क्या है और स्वयं समाधान लागू करने के व्यावहारिक कौशल क्या हैं।

लिनियर प्रोग्रामिंग क्या है?

लिनियर प्रोग्रामिंग रैखिक बाधाओं के अधीन एक रैखिक उद्देश्य फलन का अनुकूलन करती है। एक वितरण रूटिंग प्रोजेक्ट पर मैंने काम किया, उसमें लक्ष्य कुल ड्राइविंग दूरी को न्यूनतम करना था, साथ ही वाहन क्षमता और डिलीवरी समय विंडो जैसी बाधाओं का पालन करना था।

मूल संरचना को समझना

हर लिनियर प्रोग्रामिंग समस्या के तीन घटक होते हैं: निर्णय चर, एक उद्देश्य फलन, और बाधाएँ।

निर्णय चर वे विकल्प हैं जो आप चुन रहे हैं। रूटिंग समस्याओं में, बाइनरी चर यह दर्शा सकते हैं कि कौन सा वाहन किस लोकेशन पर जाता है। उत्पादन योजना में, चर निर्माण मात्राओं का प्रतिनिधित्व कर सकते हैं।

उद्देश्य फलन यह परिभाषित करता है कि आप क्या ऑप्टिमाइज़ कर रहे हैं। यह आपके निर्णय चरों का एक रैखिक संयोजन होना चाहिए। बाधाएँ आपकी समस्या के नियम और सीमाएँ परिभाषित करती हैं। ये तीन रूप लेती हैं: समताएँ, कम-या-बराबर या अधिक-या-बराबर असमताएँ।

from scipy.optimize import linprog

c = [10, 15]
A_ub = [[1, 0], [0, 1]]
b_ub = [100, 80]
A_eq = [[1, 1]]
b_eq = [150]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, 
                 bounds=bounds, method='highs')

print(f"Optimal solution: Truck 1 = {result.x[0]:.1f}, Truck 2 = {result.x[1]:.1f}")
print(f"Total cost: ${result.fun:.2f}")संचालित द्वारा

ऊपर दिया गया कोड दो निर्णय चरों के लिए कुल लागत को न्यूनतम करता है, व्यक्तिगत सीमाओं और कुल कवरेज आवश्यकता के अधीन। उद्देश्य गुणांक [10, 15] प्रति इकाई लागत का प्रतिनिधित्व करते हैं, असमता बाधाएँ प्रत्येक चर की सीमा तय करती हैं, और समता बाधा कुल कवरेज सुनिश्चित करती है।

ज्यामितीय व्याख्या

लिनियर प्रोग्रामिंग को ज्यामितीय रूप से समझने से मेरे ऑप्टिमाइज़ेशन के बारे में सोचने का तरीका बदल गया। प्रत्येक बाधा एक हाफ-स्पेस को परिभाषित करती है, और उनका प्रतिच्छेद व्यवहार्य क्षेत्र बनाता है। यह क्षेत्र हमेशा एक उत्तल पॉलीटोپ होता है, जिसका अर्थ है कि दो आंतरिक बिंदुओं के बीच खींची कोई भी रेखा भीतर ही रहती है।

यहाँ महत्वपूर्ण समझ यह है: इष्टतम समाधान हमेशा व्यवहार्य क्षेत्र के शीर्षों पर होते हैं। किसी किनारे के साथ आगे बढ़ना या तो आपके उद्देश्य में सुधार करता है या नहीं, इसलिए आप तब तक बढ़ते रहते हैं जब तक कि किसी कोने पर नहीं पहुँच जाते। यह गुण लिनियर प्रोग्रामिंग एल्गोरिदम को कुशल बनाता है।

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(0, 8, 400)
y1 = (10 - x) / 2
y2 = 12 - 2*x

plt.figure(figsize=(10, 8))
plt.plot(x, y1, 'r-', label='x + 2y ≤ 10', linewidth=2)
plt.plot(x, y2, 'b-', label='2x + y ≤ 12', linewidth=2)

y_feasible = np.minimum(y1, y2)
y_feasible = np.maximum(y_feasible, 0)
plt.fill_between(x, 0, y_feasible, where=(y_feasible >= 0), 
                 alpha=0.3, color='green', label='Feasible region')

vertices = [(0, 0), (0, 5), (14/3, 8/3), (6, 0)]
for v in vertices:
    plt.plot(v[0], v[1], 'ko', markersize=10)
    obj_value = 3*v[0] + 4*v[1]
    plt.annotate(f'({v[0]:.1f}, {v[1]:.1f})\nObj: {obj_value:.1f}',
                 xy=v, xytext=(v[0]+0.3, v[1]+0.3))

plt.xlim(-0.5, 8)
plt.ylim(-0.5, 8)
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.grid(True, alpha=0.3)
plt.title('Geometric View: Optimal Solution at Vertex (4.7, 2.7)')
plt.show()संचालित द्वारा

यह विज़ुअलाइज़ेशन उस शीर्ष (4.7, 2.7) पर इष्टतम समाधान दिखाता है जहाँ दो बाधाएँ एक-दूसरे को काटती हैं। उत्तल व्यवहार्य क्षेत्र यह सुनिश्चित करता है कि कोई छिपी घाटियाँ नहीं हैं जहाँ एल्गोरिदम अटक जाए, जिससे स्थानीय इष्टतम वैश्विक इष्टतम के बराबर होता है।

वास्तविक समस्याओं का रूपांतरण

सबसे कठिन हिस्सा गणित हल करना नहीं, बल्कि गड़बड़ समस्याओं को साफ-सुथरी फॉर्म्युलेशंस में बदलना है। चर और बाधाएँ परिभाषित करना अक्सर स्वयं ऑप्टिमाइज़ेशन चलाने से अधिक समय लेता है।

निर्णय चर परिभाषित करने के लिए बुनियादी विकल्पों की पहचान करनी होती है। रूटिंग के लिए, आप वाहन-स्थान असाइनमेंट के लिए बाइनरी चर का उपयोग कर सकते हैं, या बाधाओं को सरल बनाने के लिए विज़िट ऑर्डरिंग हेतु सतत चर जोड़ सकते हैं।

बाधाएँ बनाना व्यापारिक नियमों को असमताओं में अनुवादित करना है। यह छिपी मान्यताओं को उजागर करता है। जब कोई मैनेजर कहता है "प्रत्येक स्थान पर एक डिलीवरी चाहिए," क्या उसका मतलब ठीक एक है या कम से कम एक? ये बारीकियाँ फॉर्म्युलेशन को पूरी तरह बदल देती हैं।

यहाँ PuLP का उपयोग करते हुए एक उदाहरण फॉर्म्युलेशन है:

from pulp import *

prob = LpProblem("Food_Bank_Routing", LpMinimize)

trucks = ['Truck_A', 'Truck_B', 'Truck_C']
centers = ['North', 'South', 'East', 'West', 'Central']

x = LpVariable.dicts("route", 
                     [(i, j) for i in trucks for j in centers],
                     cat='Binary')

distances = {
    ('Truck_A', 'North'): 15, ('Truck_A', 'South'): 20,
    ('Truck_A', 'East'): 10, ('Truck_A', 'West'): 25,
    ('Truck_A', 'Central'): 5,
    ('Truck_B', 'North'): 18, ('Truck_B', 'South'): 15,
    ('Truck_B', 'East'): 12, ('Truck_B', 'West'): 22,
    ('Truck_B', 'Central'): 8,
    ('Truck_C', 'North'): 20, ('Truck_C', 'South'): 25,
    ('Truck_C', 'East'): 15, ('Truck_C', 'West'): 18,
    ('Truck_C', 'Central'): 10,
}

prob += lpSum([distances[i, j] * x[i, j] 
               for i in trucks for j in centers])

for j in centers:
    prob += lpSum([x[i, j] for i in trucks]) == 1

max_stops = {'Truck_A': 3, 'Truck_B': 2, 'Truck_C': 3}
for i in trucks:
    prob += lpSum([x[i, j] for j in centers]) <= max_stops[i]

prob.solve()

print(f"Status: {LpStatus[prob.status]}")
print(f"Total distance: {value(prob.objective)} miles")
for i in trucks:
    route = [j for j in centers if value(x[i, j]) == 1]
    print(f"{i} visits: {', '.join(route)}")संचालित द्वारा

ऊपर की फॉर्म्युलेशन ट्रक-सेन्टर असाइनमेंट के लिए बाइनरी चर का उपयोग करती है, कुल दूरी को न्यूनतम करती है, सुनिश्चित करती है कि प्रत्येक सेंटर को ठीक एक डिलीवरी मिले, और ट्रक क्षमता सीमाओं का सम्मान करती है।

क्लासिक समस्या पैटर्न टेम्पलेट्स प्रदान करते हैं। डाइट समस्या पोषण आवश्यकताओं को पूरा करते हुए लागत को न्यूनतम करती है। ट्रांसपोर्टेशन समस्याएँ शिपिंग लागत को कम करती हैं। यह वाला सीधे मेरी अपनी रूटिंग चुनौती पर लागू हुआ। इन पैटर्न्स को पहचानना फॉर्म्युलेशन को तेज करता है क्योंकि आप शायद ही कभी बिल्कुल नई समस्या हल कर रहे होते हैं।

लिनियर प्रोग्रामिंग बाधाओं द्वारा परिभाषित व्यवहार्य क्षेत्रों के शीर्षों पर इष्टतम समाधान ढूंढती है। छवि: लेखक द्वारा

समाधान विधियाँ और एल्गोरिथ्मिक तरीके

एल्गोरिदम कैसे काम करते हैं, यह समझने से linprog() को कॉल करने के प्रति मेरा नजरिया बदल गया। ये ब्लैक बॉक्स नहीं, बल्कि सुरुचिपूर्ण गणितीय प्रक्रियाएँ हैं।

सिंप्लेक्स एल्गोरिदम

The सिंप्लेक्स एल्गोरिदम, जिसे 1947 में जॉर्ज डैन्टज़िग ने विकसित किया, शुरुआती बिंदु है। इसका अंतर्दृष्टि: शीर्ष से सटे शीर्ष तक व्यवस्थित रूप से आगे बढ़ना, हर बार उद्देश्य में सुधार करना, जब तक कि इष्टतम तक न पहुँच जाए।

एल्गोरिदम एक टैब्लो बनाए रखता है और शीर्षों के बीच जाने के लिए पिवट ऑपरेशंस करता है। प्रत्येक इटरेशन एक पिवट तत्व का चयन कर और पंक्ति ऑपरेशंस के माध्यम से अपडेट करके या तो उद्देश्य में सुधार करता है या इष्टतमता निर्धारित करता है।

from scipy.optimize import linprog
import numpy as np

c = [-3, -2]
A_ub = [[2, 1], [2, 3], [3, 1]]
b_ub = [18, 42, 24]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Optimal solution: x1 = {result.x[0]:.2f}, x2 = {result.x[1]:.2f}")
print(f"Maximum value: {-result.fun:.2f}")
print(f"Iterations: {result.nit}")संचालित द्वारा

ऊपर का कोड उद्देश्य गुणांकों को नकारात्मक बनाकर सिंप्लेक्स विधि से एक अधिकतमकरण समस्या हल करने का प्रदर्शन करता है। सॉल्वर बाधाओं द्वारा परिभाषित व्यवहार्य क्षेत्र के शीर्षों के बीच व्यवस्थित रूप से चलता है और कुछ ही इटरेशंस में इष्टतम समाधान तक पहुँच जाता है। बड़े समस्याओं में, सिंप्लेक्स विधि अक्सर व्यवहार्य शीर्षों की संख्या से कहीं कम कदमों में इष्टतम ढूंढ लेती है—हज़ारों संभावनाओं के बावजूद अक्सर 20 से कम इटरेशंस।

इंटीरियर-पॉइंट विधियाँ

जहाँ सिंप्लेक्स सीमाओं के साथ चलता है, वहीं इंटीरियर-पॉइंट विधियाँ व्यवहार्य क्षेत्र के अंदरूनी हिस्से से नेविगेट करती हैं। सैकड़ों एसेट्स वाले बड़े पोर्टफोलियो ऑप्टिमाइज़ेशन में, सिंप्लेक्स सुस्त हो सकता है जबकि इंटीरियर-पॉइंट विधियाँ सेकंडों में हल कर देती हैं।

मुख्य लाभ बहुपद-समय जटिलता है। कर्माकर का एल्गोरिदम (1984) ने इंटीरियर-पॉइंट विधियों को व्यावहारिक बनाया, उद्देश्य सुधार और बाधा सीमाओं से दूर रहने के बीच संतुलन बनाते हुए। Gurobi जैसे आधुनिक सॉल्वर समस्या की विशेषताओं के आधार पर स्वतः सिंप्लेक्स और इंटीरियर-पॉइंट में से चुनते हैं।

दो-चर के लिए ग्राफिकल विधि

दो-चर समस्याओं के लिए, मैं हमेशा पहले उन्हें ग्राफिक रूप से हल करता हूँ। यह वह अंतर्दृष्टि बनाती है जो उच्च आयामों में भी स्थानांतरित होती है। बाधाएँ प्लॉट करें, व्यवहार्य क्षेत्र पहचानें, और देखें कौन सा कोना उद्देश्य को ऑप्टिमाइज़ करता है।

from scipy.optimize import linprog

c = [-30, -40]
A_ub = [[2, 1], [1, 2]]
b_ub = [100, 80]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Bread loaves: {result.x[0]:.0f}")
print(f"Cakes: {result.x[1]:.0f}")
print(f"Maximum profit: ${-result.fun:.0f}")संचालित द्वारा

यह बेकरी उत्पादन समस्या ओवन और सजावट घंटों की सीमाओं के अधीन ब्रेड और केक से लाभ को अधिकतम करती है। समाधान यह उजागर करता है कि ज्यामितीय रूप से कौन सा कोना इष्टतम है, जिससे एल्गोरिदम के शीर्ष-से-शीर्ष जाने के व्यवहार को ठोस बनाया जा सके।

उद्योगों में अनुप्रयोग

लिनियर प्रोग्रामिंग एक ही गणितीय ढांचे को लागू करके एक-दूसरे से बहुत भिन्न डोमेन्स में समस्याएँ हल करती है।

मैन्युफैक्चरिंग और उत्पादन

उत्पादन योजना मेरा पहला गंभीर अनुप्रयोग था। प्रोडक्शन मिक्स समस्या निर्माण मात्राएँ निर्धारित करती है, जहाँ चर उत्पादन का प्रतिनिधित्व करते हैं, उद्देश्य लाभ को अधिकतम करना होता है, और बाधाएँ संसाधन सीमाएँ दर्शाती हैं।

from pulp import *

products = ['Phone', 'Tablet', 'Laptop']

profits = {'Phone': 120, 'Tablet': 200, 'Laptop': 350}
assembly_time = {'Phone': 2, 'Tablet': 3, 'Laptop': 5}
testing_time = {'Phone': 1, 'Tablet': 1.5, 'Laptop': 2}

assembly_available = 500
testing_available = 200
min_production = {'Phone': 50, 'Tablet': 30, 'Laptop': 20}

model = LpProblem("Production_Planning", LpMaximize)
production = LpVariable.dicts("produce", products, lowBound=0, cat='Integer')

model += lpSum([profits[p] * production[p] for p in products])
model += lpSum([assembly_time[p] * production[p] for p in products]) <= assembly_available
model += lpSum([testing_time[p] * production[p] for p in products]) <= testing_available

for p in products:
    model += production[p] >= min_production[p]

model.solve()

print(f"Status: {LpStatus[model.status]}")
for p in products:
    print(f"{p}: {production[p].varValue:.0f} units")
print(f"Total profit: ${value(model.objective):,.0f}")संचालित द्वारा

ऊपर का मॉडल तीन प्रोडक्ट लाइनों में इलेक्ट्रॉनिक्स उत्पादन का अनुकूलन करता है, असेंबली और टेस्टिंग क्षमता को न्यूनतम उत्पादन आवश्यकताओं के साथ संतुलित करते हुए।

ब्लेंडिंग समस्याएँ उन मिश्रणों का अनुकूलन करती हैं जो विनिर्देशों को न्यूनतम लागत पर पूरा करें, जैसे पोषण आवश्यकताओं को पूरा करने के लिए खाद्य पदार्थों का मिश्रण बनाना और लागत घटाना।

ट्रांसपोर्टेशन और लॉजिस्टिक्स

ट्रांसपोर्टेशन समस्या एक और अध्ययनित उदाहरण है। पारंपरिक संरचना में आपूर्ति वाले स्रोत और माँग वाले गंतव्य होते हैं, जिनका लक्ष्य कुल शिपिंग लागत को न्यूनतम करना है।

warehouses = ['Warehouse_A', 'Warehouse_B', 'Warehouse_C']
supply = {'Warehouse_A': 300, 'Warehouse_B': 400, 'Warehouse_C': 200}

customers = ['Customer_1', 'Customer_2', 'Customer_3', 'Customer_4']
demand = {'Customer_1': 200, 'Customer_2': 150, 'Customer_3': 250, 'Customer_4': 200}

costs = {
    ('Warehouse_A', 'Customer_1'): 8,  ('Warehouse_A', 'Customer_2'): 6,
    ('Warehouse_A', 'Customer_3'): 10, ('Warehouse_A', 'Customer_4'): 7,
    ('Warehouse_B', 'Customer_1'): 9,  ('Warehouse_B', 'Customer_2'): 12,
    ('Warehouse_B', 'Customer_3'): 8,  ('Warehouse_B', 'Customer_4'): 11,
    ('Warehouse_C', 'Customer_1'): 14, ('Warehouse_C', 'Customer_2'): 7,
    ('Warehouse_C', 'Customer_3'): 10, ('Warehouse_C', 'Customer_4'): 12,
}

model = LpProblem("Transportation", LpMinimize)

routes = [(w, c) for w in warehouses for c in customers]
shipments = LpVariable.dicts("ship", routes, lowBound=0)

model += lpSum([costs[i, j] * shipments[i, j] for (i, j) in routes])

for w in warehouses:
    model += lpSum([shipments[w, c] for c in customers]) <= supply[w]

for c in customers:
    model += lpSum([shipments[w, c] for w in warehouses]) >= demand[c]

model.solve()संचालित द्वारा

नेटवर्क फ्लो समस्याएँ ट्रांसपोर्टेशन को ट्रांसशिपमेंट नोड्स वाले ग्राफ तक सामान्यीकृत करती हैं। मैंने पढ़ा है कि एयरलाइंस इसे क्रू शेड्यूलिंग और एयरक्राफ्ट रूटिंग के लिए व्यापक रूप से इस्तेमाल करती हैं।

वित्तीय सेवाएँ और स्वास्थ्य सेवा

वित्तीय अनुप्रयोगों में, कैपिटल बजटिंग बजट सीमाओं के अधीन रिटर्न को अधिकतम करने वाले प्रोजेक्ट्स का चयन करती है:

projects = {
    'Project_A': {'return': 25000, 'cost': 100000, 'staff': 5},
    'Project_B': {'return': 30000, 'cost': 150000, 'staff': 7},
    'Project_C': {'return': 20000, 'cost': 80000, 'staff': 4},
}

budget = 300000
staff_available = 15

model = LpProblem("Capital_Budgeting", LpMaximize)
select = LpVariable.dicts("select", projects.keys(), cat='Binary')

model += lpSum([projects[p]['return'] * select[p] for p in projects])
model += lpSum([projects[p]['cost'] * select[p] for p in projects]) <= budget
model += lpSum([projects[p]['staff'] * select[p] for p in projects]) <= staff_available

model.solve()संचालित द्वारा

हेल्थकेयर सिस्टम्स अंतहीन ऑप्टिमाइज़ेशन चुनौतियों का सामना करते हैं। मैंने एक क्लिनिक शेड्यूलिंग समस्या पर परामर्श किया जिसने कौशल आवश्यकताओं और कार्यभार संतुलन का सम्मान करते हुए नर्सों को शिफ्ट्स में असाइन किया।

आधुनिक टेक्नोलॉजी अनुप्रयोग

लिनियर प्रोग्रामिंग मशीन लर्निंग के भीतर भी अप्रत्याशित रूप से दिखाई देती है। फ़ीचर चयन को विरलता बाधाओं के अधीन भविष्यवाणी त्रुटि को न्यूनतम करने के रूप में तैयार किया जा सकता है। क्लाउड कंप्यूटिंग वितरित प्रणालियों में संसाधन आवंटन के लिए इसका उपयोग करती है।

कंप्यूटेशनल जटिलता और प्रदर्शन

जब समस्याएँ खिलौना उदाहरणों से प्रोडक्शन सिस्टम्स तक स्केल होती हैं, तो जटिलता मायने रखती है।

सिंप्लेक्स एल्गोरिदम की जटिलता

सिंप्लेक्स की जटिलता आकर्षक है। इसका वर्स्ट-केस एक्सपोनेंशियल है, पर औसतन प्रदर्शन उत्कृष्ट होता है। Klee-Minty क्यूब जैसे असाधारण मामलों में इसे हर शीर्ष देखना पड़ता है, पर सामान्य समस्याएँ केवल एक छोटे हिस्से की जाँच करती हैं और मोटे तौर पर वर्गात्मक रूप से स्केल करती हैं।

मैंने यह बढ़ते आकार की रैंडमली जनरेटेड समस्याएँ हल करके परखा:

import time
import numpy as np
from scipy.optimize import linprog

def benchmark_simplex(num_vars, num_constraints):
    c = np.random.randn(num_vars)
    A_ub = np.random.randn(num_constraints, num_vars)
    b_ub = np.random.rand(num_constraints) * 10
    
    start = time.time()
    result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='simplex')
    elapsed = time.time() - start
    
    return elapsed, result.nit

problem_sizes = [(10, 20), (50, 100), (100, 200), (200, 400)]

for n_vars, n_const in problem_sizes:
    times, iterations = [], []
    for _ in range(10):
        t, it = benchmark_simplex(n_vars, n_const)
        times.append(t)
        iterations.append(it)
    print(f"{n_vars}x{n_const}: {np.mean(times):.4f}s, {np.mean(iterations):.1f} iterations")संचालित द्वारा

मेरे बेंचमार्क्स ने दिखाया कि समस्या का आकार दोगुना करने से समय में 4x से कम वृद्धि हुई, जो सामान्य वितरणों के लिए लगभग-बहुपदीय व्यवहार की पुष्टि करता है।

प्रदर्शन सुधार

आधुनिक सॉल्वर प्रीप्रोसेसिंग, पैरेलल प्रोसेसिंग, और स्वतः एल्गोरिदम चयन के माध्यम से उल्लेखनीय प्रदर्शन प्राप्त करते हैं। प्रीप्रोसेसिंग हल करने से पहले स्वतः ही समस्या का आकार 30% या अधिक तक घटा सकती है।

डिजनरेसी तब होती है जब इष्टतम पर कई बाधाएँ एक साथ टाइट होती हैं, जो चक्रण का कारण बन सकती है। मुझे यह तब मिला जब दो रूट्स की लागत समान थी। सॉल्वर साइकलिंग से बचने के लिए पर्टर्बेशन तकनीकें उपयोग करते हैं, हालांकि डिजनरेट समस्याएँ धीमी हल होती हैं।

न्यूमेरिकल अस्थिरता खराब स्केलिंग वाली समस्याओं में उत्पन्न होती है। मौद्रिक राशियों (हजारों डॉलर) को मात्राओं (एकल इकाइयों) के साथ मिलाने से सॉल्वर चेतावनियाँ आईं। रिस्केलिंग ने इसे तुरंत ठीक किया।

सॉल्वर प्रदर्शन तुलना: बड़े पैमाने की समस्याओं पर वाणिज्यिक समाधान उत्कृष्ट रहते हैं। छवि: लेखक द्वारा

सॉफ्टवेयर टूल्स और इम्प्लीमेंटेशन

टूल का चुनाव उत्पादकता पर गहरा असर डालता है। मैं हाथ से सिंप्लेक्स लिखने से पेशेवर सॉल्वर्स तक पहुँचा जो कहीं बड़े समस्याओं को संभालते हैं।

वाणिज्यिक सॉल्वर और मॉडलिंग भाषाएँ

CPLEX और Gurobi औद्योगिक ऑप्टिमाइज़ेशन पर हावी हैं, बड़े समस्याओं के लिए ओपन-सोर्स विकल्पों की तुलना में कई गुणा बेहतर प्रदर्शन देते हुए। मैंने सप्लाई चेन कार्य के लिए Gurobi का अकादमिक लाइसेंस उपयोग किया। SciPy के साथ मिनटों में हल होने वाली समस्याएँ सेकंडों में सुलझ गईं।

PuLP मेरा Python में पसंदीदा है। यह विभिन्न बैकएंड्स द्वारा हल किए जाने वाले मॉडलों को फॉर्म्युलेट करने के लिए साफ-सुथरा API देता है:

from pulp import *

model = LpProblem("my_problem", LpMaximize)

x = LpVariable("x", lowBound=0)
y = LpVariable("y", lowBound=0)

model += 3*x + 2*y
model += x + y <= 100
model += 2*x + y <= 150

model.solve()

print(f"Used solver: {model.solver}")
print(f"Status: {LpStatus[model.status]}")संचालित द्वारा

यह एब्स्ट्रैक्शन लेयर सॉल्वर-अज्ञेय कोड देती है जो अलग-अलग प्रणालियों पर चलता है। Pyomo जटिल ऑप्टिमाइज़ेशन के लिए अधिक उन्नत विशेषताएँ देता है, जिनमें नॉनलाइनियर और स्टोकेस्टिक प्रोग्रामिंग शामिल हैं।

क्लाउड और ओपन-सोर्स विकल्प

क्लाउड प्लेटफ़ॉर्म अनियमित बड़े पैमाने की समस्याओं के लिए ऑप्टिमाइज़ेशन-एज़-ए-सर्विस प्रदान करते हैं। आप समस्या डेटा अपलोड करते हैं और API के माध्यम से समाधान प्राप्त करते हैं। सर्वरलेस आर्किटेक्चर सुरुचिपूर्ण है, हालाँकि छोटी समस्याओं के लिए स्थानीय सॉल्वर्स की तुलना में धीमा होता है।

GLPK (GNU Linear Programming Kit) विश्वसनीय ओपन-सोर्स वर्कहॉर्स है। मैं इसे शिक्षण और व्यक्तिगत प्रोजेक्ट्स के लिए उपयोग करता हूँ। HiGHS नया सॉल्वर है जो प्रभावशाली प्रदर्शन दिखा रहा है। SciPy ने हाल ही में HiGHS को अपना डिफ़ॉल्ट बैकएंड अपनाया है, और मेरे बेंचमार्क्स ने दिखाया कि यह कई समस्याओं पर Gurobi की बराबरी करता है।

लिनियर प्रोग्रामिंग उदाहरण

पूर्ण उदाहरणों पर काम करना केवल सिद्धांत की तुलना में समझ को बेहतर बनाता है।

उदाहरण 1: डाइट समस्या

क्लासिक डाइट समस्या पोषण आवश्यकताओं को पूरा करते हुए लागत को न्यूनतम करती है:

from pulp import *

foods = {
    'Oatmeal': {'cost': 0.50, 'calories': 110, 'protein': 4, 'vitamin': 2},
    'Chicken': {'cost': 2.50, 'calories': 250, 'protein': 30, 'vitamin': 0},
    'Eggs':    {'cost': 0.80, 'calories': 155, 'protein': 13, 'vitamin': 1},
    'Milk':    {'cost': 1.20, 'calories': 150, 'protein': 8, 'vitamin': 4},
    'Bread':   {'cost': 0.30, 'calories': 80, 'protein': 3, 'vitamin': 0}
}

min_calories, min_protein, min_vitamin = 2000, 50, 10

model = LpProblem("Diet_Optimization", LpMinimize)
servings = LpVariable.dicts("servings", foods.keys(), lowBound=0)

model += lpSum([foods[f]['cost'] * servings[f] for f in foods])
model += lpSum([foods[f]['calories'] * servings[f] for f in foods]) >= min_calories
model += lpSum([foods[f]['protein'] * servings[f] for f in foods]) >= min_protein
model += lpSum([foods[f]['vitamin'] * servings[f] for f in foods]) >= min_vitamin

model.solve()

print(f"Total cost: ${value(model.objective):.2f}")
for food in foods:
    if servings[food].varValue > 0.01:
        print(f"{food}: {servings[food].varValue:.2f} servings")संचालित द्वारा

ऊपर की फॉर्म्युलेशन दैनिक पोषण आवश्यकताओं को पूरा करने वाले खाद्य पदार्थों के सबसे सस्ते संयोजन को ढूंढती है। यह दर्शाता है कि अतिरिक्त विविधता, स्वाद, या आहार वरीयताओं जैसी बाधाओं के बिना इष्टतम LP समाधान हमेशा व्यावहारिक नहीं होते।

यही ढाँचा उत्पादन शेड्यूल का अनुकूलन करने या मार्केटिंग बजट आवंटित करने जैसे व्यावसायिक निर्णयों की नींव भी बन सकता है।

उदाहरण 2: मल्टीपीरियड प्लानिंग

मल्टीपीरियड प्लानिंग कई समय अवधियों में इन्वेंटरी स्तरों का भविष्य की जरूरतों पर प्रभाव देखती है:

days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday']

centers = {
    'North': {'daily_demand': [100, 80, 90, 110, 85], 'capacity': 250},
    'South': {'daily_demand': [120, 100, 95, 105, 130], 'capacity': 300},
}

delivery_cost = {'Monday': 50, 'Tuesday': 50, 'Wednesday': 50,
                 'Thursday': 50, 'Friday': 70}

model = LpProblem("Multiperiod_Routing", LpMinimize)

deliveries = LpVariable.dicts("deliver",
                              [(c, d) for c in centers for d in days],
                              lowBound=0)
inventory = LpVariable.dicts("inventory",
                            [(c, d) for c in centers for d in days],
                            lowBound=0)

model += lpSum([delivery_cost[d] * deliveries[c, d] 
                for c in centers for d in days])

for c in centers:
    for i, day in enumerate(days):
        if i == 0:
            model += inventory[c, day] == deliveries[c, day] - centers[c]['daily_demand'][i]
        else:
            prev_day = days[i-1]
            model += (inventory[c, day] == inventory[c, prev_day] + 
                     deliveries[c, day] - centers[c]['daily_demand'][i])
        model += inventory[c, day] <= centers[c]['capacity']

model.solve()संचालित द्वारा

मल्टीपीरियड मॉडल समस्या का आकार बढ़ाते हैं, लेकिन परिष्कृत ऑप्टिमाइज़ेशन खोलते हैं। मॉडल सस्ती दिनों में डिलीवरी को समेकित करता है, भंडारण क्षमता का उपयोग करके कुल लागत घटाता है।

मिक्स्ड-इंटीजर प्रोग्रामिंग

कई समस्याओं में असतत निर्णय शामिल होते हैं: सुविधा बनानी है या नहीं, किसी कार्यकर्ता को असाइन करना है या नहीं। इसके लिए मिक्स्ड-इंटीजर प्रोग्रामिंग (MIP) की आवश्यकता होती है, जो लिनियर प्रोग्रामिंग को पूर्णांक और बाइनरी चरों के साथ विस्तारित करती है।

परिचय और ब्रांच-एंड-बाउंड

रूटिंग समस्याओं को पूर्णांक निर्णयों की आवश्यकता होती है। बाइनरी चर x[i][j] संकेत करता है कि वाहन i स्थान j पर जाता है या नहीं। वाहन आंशिक विज़िट नहीं कर सकते।

ब्रांच-एंड-बाउंड असतत समाधान स्पेस को व्यवस्थित रूप से खोजता है, इसके लिए सतत LP रिलैक्सेशंस हल करता है:

from pulp import *

model_continuous = LpProblem("Continuous", LpMaximize)
x_cont = LpVariable("x", lowBound=0)
y_cont = LpVariable("y", lowBound=0)

model_continuous += 3*x_cont + 4*y_cont
model_continuous += x_cont + 2*y_cont <= 10
model_continuous += 2*x_cont + y_cont <= 12

model_continuous.solve()
print(f"Continuous: x={x_cont.varValue:.2f}, y={y_cont.varValue:.2f}")

model_integer = LpProblem("Integer", LpMaximize)
x_int = LpVariable("x", lowBound=0, cat='Integer')
y_int = LpVariable("y", lowBound=0, cat='Integer')

model_integer += 3*x_int + 4*y_int
model_integer += x_int + 2*y_int <= 10
model_integer += 2*x_int + y_int <= 12

model_integer.solve()
print(f"Integer: x={x_int.varValue:.0f}, y={y_int.varValue:.0f}")संचालित द्वारा

पूर्णांक समाधान सतत समाधान को राउंड करने से भिन्न हो सकता है। ब्रांच-एंड-बाउंड इष्टतम पूर्णांक समाधान ढूंढता है, लेकिन कहीं अधिक कंप्यूटेशनल लागत पर।

इंटीजर प्रोग्रामिंग कब उपयोग करें

इंटीजर चर का उपयोग तब करें जब निर्णय स्वभावतः असतत हों: सुविधाएँ खोलना, कार्यकर्ताओं को असाइन करना, ऐसे रूटिंग जहाँ आप स्थानों पर जाते हैं या नहीं जाते। बॉन्ड मार्केट में ऑप्टिमाइज़ेशन अक्सर मिक्स्ड इंटीजर समाधानों की मांग करता है। सतत चर निरर्थक भिन्नात्मक असाइनमेंट दे सकते हैं, जबकि बाइनरी चर लागू किए जा सकने वाले समाधान देते हैं।

हालाँकि, इंटीजर प्रोग्रामिंग बहुत महँगी होती है। सैकड़ों इंटीजर चरों वाली समस्याओं को सेकंड्स की बजाय घंटों लग सकते हैं, जबकि सतत LPs जल्दी हल हो जाते हैं। यदि उत्पादन मात्राएँ बड़ी हैं, तो इंटीग्रैलिटी का महत्व कम होता है क्योंकि राउंडिंग से समाधान पर थोड़ा असर पड़ता है। पूरी इंटीजर प्रोग्रामिंग से पहले हमेशा सतत रिलैक्सेशन हल करके बाउंड्स जाँचें।

निष्कर्ष

लिनियर प्रोग्रामिंग यह बदल देती है कि आप ऑप्टिमाइज़ेशन समस्याओं से कैसे निपटते हैं। वही गणितीय ढाँचा रूटिंग से लेकर प्रोडक्शन प्लानिंग और पोर्टफोलियो मैनेजमेंट तक, बेहद अलग डोमेन्स में लागू होता है।

ज्यामितीय रूप से देखे जा सकने वाले सरल द्विचर समस्याओं से शुरू करें। बुनियादी सिंप्लेक्स लागू करें ताकि समझ सकें कि वाणिज्यिक सॉल्वर पर्दे के पीछे क्या करते हैं। वास्तविक फॉर्म्युलेशंस पर काम करें, व्यापार आवश्यकताओं को गणितीय बाधाओं में अनुवादित करते हुए।

अपनी विशेषज्ञता गहरी करने के लिए, हमारे Introduction to Optimization in Python और Linear Algebra for Data Science कोर्सेज़ देखें ताकि अपनी गणितीय नींव मज़बूत करें। हमारा Machine Learning Scientist इन Python करियर ट्रैक भी एक बेहतरीन विकल्प है।