Java के लिए OR-टूल के साथ शुरू करें

नीचे दिए गए सेक्शन से, Java के लिए OR-टूल का इस्तेमाल शुरू किया जा सकेगा:

• ऑप्टिमाइज़ेशन से जुड़ी समस्या क्या होती है?
• Java में ऑप्टिमाइज़ेशन से जुड़ी समस्या हल करना
• Java के और उदाहरण
• यह पता करना कि आपको किस तरह की समस्या को हल करना है

ऑप्टिमाइज़ेशन समस्या क्या है?

ऑप्टिमाइज़ेशन का मकसद, कई संभावित समाधानों में से किसी समस्या का सबसे अच्छा समाधान ढूंढना होता है. (कभी-कभी आप कोई संभव समाधान ढूंढ लेंगे; OR-टूल ऐसा भी कर सकते हैं.)

यह रही ऑप्टिमाइज़ेशन से जुड़ी एक आम समस्या. मान लीजिए कि एक शिपिंग कंपनी अपने ग्राहकों को ट्रकों के बेड़े का इस्तेमाल करके पैकेज डिलीवर करती है. कंपनी को हर दिन, ट्रक के लिए पैकेज असाइन करने चाहिए. इसके बाद, हर ट्रक के लिए अपना पैकेज डिलीवर करने के लिए, एक रास्ता चुनना चाहिए. पैकेज और रूट के हर संभावित असाइनमेंट का शुल्क लगता है. यह शुल्क, ट्रक तक पहुंचने के लिए तय की गई कुल दूरी और अन्य चीज़ों पर निर्भर करता है. सबसे कम कीमत वाले पैकेज और रूट के असाइनमेंट चुनने में समस्या आती है.

सभी ऑप्टिमाइज़ेशन समस्याओं की तरह, इस समस्या में भी ये एलिमेंट होते हैं:

• मकसद—वह संख्या जिसे आपको ऑप्टिमाइज़ करना है. ऊपर दिए गए उदाहरण में, मकसद कीमत को कम करना है. ऑप्टिमाइज़ेशन की कोई समस्या सेट अप करने के लिए, आपको एक ऐसा फ़ंक्शन सेट करना होगा जो किसी भी संभावित हल के लिए, मकसद की वैल्यू का पता लगाता हो. इसे मकसद फ़ंक्शन कहा जाता है. पिछले उदाहरण में, मकसद फ़ंक्शन, पैकेज और रूट के किसी भी असाइनमेंट की कुल लागत की गणना करेगा.

  सबसे अच्छा समाधान वह होता है जिसके लिए मकसद फ़ंक्शन की वैल्यू सबसे अच्छी हो. ("सबसे अच्छा" ज़्यादा से ज़्यादा या कम से कम हो सकता है.)

• सीमाएं—समस्या की खास ज़रूरतों के आधार पर, संभावित समाधानों के सेट पर लगने वाली पाबंदियां. उदाहरण के लिए, अगर शिपिंग कंपनी ट्रक के लिए दिए गए वज़न से ज़्यादा के पैकेज असाइन नहीं कर सकती, तो समाधानों पर रोक लग जाएगी.

  सही हल वह होता है जो समस्या के लिए दी गई सभी सीमाओं को पूरा करता है. हालांकि, यह ज़रूरी नहीं है कि वह सबसे बेहतर हो.

ऑप्टिमाइज़ेशन से जुड़ी समस्या को हल करने का पहला कदम होता है मकसद और सीमाओं को पहचानना.

Java में ऑप्टिमाइज़ेशन से जुड़ी समस्या हल करना

इसके बाद, हम ऑप्टिमाइज़ेशन समस्या का उदाहरण देंगे. साथ ही, बताएंगे कि Java में इसे कैसे सेट अप किया जाता और हल कैसे किया जाता है.

लीनियर ऑप्टिमाइज़ेशन का उदाहरण

लीनियर ऑप्टिमाइज़ेशन (या लीनियर प्रोग्रामिंग), ऑप्टिमाइज़ेशन के सबसे पुराने और सबसे ज़्यादा इस्तेमाल किए जाने वाले एरिया में से एक है. इसमें मकसद फ़ंक्शन और कंस्ट्रेंट को लीनियर एक्सप्रेशन के तौर पर लिखा जा सकता है. इस तरह की समस्या का एक आसान उदाहरण यह है.

3x + y को इन शर्तों के आधार पर बढ़ाएं:

1. 0 ≤ x ≤ 1
2. 0 ≤ y ≤ 2
3. x + y ≤ 2

इस उदाहरण में, मकसद फ़ंक्शन 3x + y है. मकसद फ़ंक्शन और कंस्ट्रेंट, दोनों लीनियर एक्सप्रेशन से तय किए जाते हैं. इससे यह एक लीनियर सवाल बन जाता है.

समस्या को हल करने के मुख्य चरण

हर भाषा के लिए, समस्या को सेट अप करने और उसे हल करने के बुनियादी चरण एक ही हैं:

1. ज़रूरी लाइब्रेरी इंपोर्ट करें,
2. सॉल्वर घोषित करें,
3. वैरिएबल बनाएं,
4. सीमाओं को परिभाषित करें.
5. मकसद फ़ंक्शन तय करें,
6. सॉल्वर को प्रोत्साहित करें और
7. नतीजे दिखाएं.

Java प्रोग्राम<

यह सेक्शन एक ऐसे Java प्रोग्राम के बारे में बताता है जो समस्या को सेट अप करता है और उसका समाधान करता है.

ध्यान दें: पूरे Java प्रोग्राम और इसे चलाने के चरण, सेक्शन के आखिर में दिखाए गए हैं.

निम्न चरणों का अनुसरण करें:

• ज़रूरी लाइब्रेरी इंपोर्ट करें.

  import com.google.ortools.Loader;
  import com.google.ortools.linearsolver.MPConstraint;
  import com.google.ortools.linearsolver.MPObjective;
  import com.google.ortools.linearsolver.MPSolver;
  import com.google.ortools.linearsolver.MPVariable;

• सॉल्वर का एलान करें.

  // Create the linear solver with the GLOP backend.
  MPSolver solver = MPSolver.createSolver("GLOP");

  MPSolver, लीनियर प्रोग्रामिंग या मिक्स्ड इंटीजर प्रोग्रामिंग से जुड़े किसी भी सवाल को हल करने का रैपर होता है.
• वैरिएबल बनाएं.

  // Create the variables x and y.
  MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
  MPVariable y = solver.makeNumVar(0.0, 2.0, "y");
  
  System.out.println("Number of variables = " + solver.numVariables());

• सीमा तय करें. पहले दो कंस्ट्रेंट, 0 &leq; x ≤ 1 और 0 &leq; y ≤ 2, पहले ही वैरिएबल की परिभाषाओं के हिसाब से सेट होते हैं. यह कोड, कंस्ट्रेंट x + y &leq; 2 के बारे में बताता है:

  // Create a linear constraint, 0 <= x + y <= 2.
  MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
  ct.setCoefficient(x, 1);
  ct.setCoefficient(y, 1);
  
  System.out.println("Number of constraints = " + solver.numConstraints());

  तरीका setCoefficient, कंस्ट्रेंट के लिए एक्सप्रेशन में x और y के कोएफ़िशिएंट सेट करता है.
• मकसद फ़ंक्शन तय करें.

  // Create the objective function, 3 * x + y.
  MPObjective objective = solver.objective();
  objective.setCoefficient(x, 3);
  objective.setCoefficient(y, 1);
  objective.setMaximization();

  setMaximization तरीका बताता है कि यह समस्या बड़ी है.
• सॉल्वर को शुरू करें और नतीजे दिखाएं.

  solver.solve();
  System.out.println("Solution:");
  System.out.println("Objective value = " + objective.value());
  System.out.println("x = " + x.solutionValue());
  System.out.println("y = " + y.solutionValue());

प्रोग्राम पूरा करें

पूरा प्रोग्राम नीचे दिखाया गया है.

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

    // Create the variables x and y.
    MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
    MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    solver.solve();

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());
  }

  private BasicExample() {}
}

Java प्रोग्राम चलाना

ऊपर दिए गए प्रोग्राम को इस तरह चलाया जा सकता है:

1. ऊपर दिए गए कोड को कॉपी करके नई फ़ाइल में चिपकाएं. इसके बाद, उसे my_program.java के तौर पर सेव करें.
2. जिस डायरेक्ट्री में आपने 'OR-टूल' इंस्टॉल किया है उसके टॉप लेवल पर मौजूद कमांड विंडो खोलें. इसके बाद, यह डालें:

   make run SOURCE=relative/path/to/my_program.java

   जहां relative/path/to/, उस डायरेक्ट्री का पाथ है जहां आपने प्रोग्राम को सेव किया है.

ध्यान दें: आपको ऊपर दिए गए निर्देश को उस डायरेक्ट्री के टॉप लेवल से चलाना होगा जहां आपने OR-टूल इंस्टॉल किए हैं (जहां Makefile मौजूद है).

यह प्रोग्राम x और y की वैल्यू दिखाता है, जो मकसद फ़ंक्शन को बेहतर बनाते हैं:

Solution:
x =  1.0
y =  1.0

प्रोग्राम को चलाए बिना उसे कंपाइल करने के लिए, यह डालें:

make build SOURCE=relative/path/to/my_program.java

Java के ज़्यादा उदाहरण

Java के ऐसे और उदाहरण देखने के लिए जिनमें यह बताया गया है कि ऑप्टिमाइज़ेशन से जुड़ी अलग-अलग तरह की समस्याओं को कैसे हल किया जाए. उदाहरण देखें.

उस समस्या की पहचान करना जिसे आपको हल करना है

दुनिया में ऑप्टिमाइज़ेशन की कई तरह की समस्याएं हैं. हर तरह की समस्या का सबसे सही समाधान ढूंढने के लिए, अलग-अलग तरीके और एल्गोरिदम होते हैं.

ऑप्टिमाइज़ेशन की किसी समस्या को हल करने के लिए, प्रोग्राम लिखना शुरू करने से पहले, आपको यह पता लगाना होगा कि किस तरह की समस्या से निपटना है और फिर एक सही सॉल्वर चुनना होगा. यह एल्गोरिदम, सबसे बेहतर समाधान खोजने वाला होता है.

नीचे आपको OR-टूल ज़रिए हल की जाने वाली समस्याओं के बारे में खास जानकारी मिलेगी. साथ ही, इस गाइड में दिए गए सेक्शन के लिंक मिलेंगे, जिनमें समस्या को हल करने का तरीका बताया गया है.

• लीनियर ऑप्टिमाइज़ेशन
• कंस्ट्रेंट ऑप्टिमाइज़ेशन
• मिक्स्ड-इंटीजर ऑप्टिमाइज़ेशन
• असाइनमेंट
• शेड्यूल बनाना
• पैकिंग
• रूटिंग
• नेटवर्क फ़्लो

लीनियर ऑप्टिमाइज़ेशन

जैसा कि आपने पिछले सेक्शन में सीखा है, लीनियर ऑप्टिमाइज़ेशन समस्या एक है जिसमें मकसद फ़ंक्शन और कंस्ट्रेंट, वैरिएबल में लीनियर एक्सप्रेशन होते हैं.

इस तरह की समस्या के लिए, OR-टूल में प्राइमरी सॉल्वर लीनियर ऑप्टिमाइज़ेशन सॉल्वर है. यह असल में, लीनियर और मिक्स्ड-इंटीजर ऑप्टिमाइज़ेशन के लिए, कई अलग-अलग लाइब्रेरी के लिए रैपर होता है. इनमें, तीसरे पक्ष की लाइब्रेरी भी शामिल हैं.

लीनियर ऑप्टिमाइज़ेशन के बारे में ज़्यादा जानें

मिश्रित-पूर्णांक ऑप्टिमाइज़ेशन

मिले-जुले पूर्णांक ऑप्टिमाइज़ेशन की समस्या एक ऐसी समस्या है जिसमें कुछ या सभी वैरिएबल का पूर्णांक होना ज़रूरी है. इसका एक उदाहरण असाइनमेंट से जुड़ी समस्या है. इसमें, वर्कर के एक ग्रुप को टास्क के सेट को असाइन किया जाना ज़रूरी होता है. हर वर्कर और टास्क के लिए, आपने एक वैरिएबल तय किया है, जिसका मान 1 है, अगर उस वर्कर को कोई टास्क असाइन किया गया है, नहीं तो 0 होगा. इस मामले में, वैरिएबल सिर्फ़ 0 या 1 वैल्यू पर ही काम कर सकते हैं.

मिले-जुले पूर्णांक ऑप्टिमाइज़ेशन के बारे में ज़्यादा जानें

कंस्ट्रेंट ऑप्टिमाइज़ेशन

कंस्ट्रेंट ऑप्टिमाइज़ेशन या कंस्ट्रेंट प्रोग्रामिंग (सीपी), उम्मीदवारों के एक बहुत बड़े सेट में से ऐसे समाधानों की पहचान करता है जो आसानी से काम कर सकते हैं. यहां समस्या को आर्बिट्रेरी कंस्ट्रेंट के हिसाब से तय किया जा सकता है. सीपी, ऑप्टिमाइज़ेशन (सबसे बेहतर समाधान ढूंढने) के बजाय संभावना (सही समाधान खोजना) पर आधारित है और मकसद फ़ंक्शन के बजाय कंस्ट्रेंट और वैरिएबल पर फ़ोकस करता है. हालांकि, सीपी का इस्तेमाल ऑप्टिमाइज़ेशन से जुड़ी समस्याओं को हल करने के लिए किया जा सकता है. इसके लिए, सिर्फ़ मकसद फ़ंक्शन के वैल्यू की तुलना सभी संभावित समाधानों के लिए करनी होगी.

कंस्ट्रेंट ऑप्टिमाइज़ेशन के बारे में ज़्यादा जानें

Assignment

असाइनमेंट से जुड़ी समस्याओं में, टास्क के सेट को एजेंटों (जैसे कि कर्मचारी या मशीन) के एक ग्रुप को असाइन करना शामिल होता है, जहां हर एजेंट को किसी खास टास्क को असाइन करने की एक तय कीमत होती है. सबसे कम कुल कीमत वाला असाइनमेंट ढूंढना है. असाइनमेंट से जुड़ी समस्याएं, असल में नेटवर्क फ़्लो से जुड़ी समस्याओं का खास मामला है.

असाइनमेंट के बारे में ज़्यादा जानें

पैकिंग

बिन पैकिंग में अलग-अलग साइज़ के ऑब्जेक्ट को अलग-अलग क्षमता वाले कंटेनर में पैक किया जाता है. इसका मकसद कंटेनर की कपैसिटी पर निर्भर करते हुए, ज़्यादा से ज़्यादा ऑब्जेक्ट को पैक करना है. इसका एक खास मामला KSnapsack की समस्या है, जिसमें सिर्फ़ एक कंटेनर होता है.

बिन पैकिंग के बारे में ज़्यादा जानें

शेड्यूल करें

शेड्यूल करने में होने वाली समस्याओं में, तय समय पर टास्क पूरे करने के लिए संसाधन असाइन किए जाते हैं. इसका एक अहम उदाहरण नौकरी की दुकान की समस्या है, जिसमें कई कामों को कई मशीनों पर प्रोसेस किया जाता है. हर काम में एक क्रम में टास्क होते हैं जिन्हें एक तय क्रम में किया जाना चाहिए. साथ ही, हर टास्क को एक खास मशीन पर प्रोसेस किया जाना चाहिए. समस्या तो एक शेड्यूल असाइन करने की है, ताकि सभी काम कम से कम समय अंतराल में पूरा हो सके.

शेड्यूल करने के बारे में ज़्यादा जानें

रूटिंग

रूटिंग से जुड़ी समस्याओं में, नेटवर्क को पार करने के लिए वाहनों के ग्रुप के लिए, सबसे सही रास्ते ढूंढना शामिल है. इन रास्तों के बारे में निर्देश दिए गए ग्राफ़ से तय किया गया है. डिलीवरी ट्रक को पैकेज असाइन करने में होने वाली समस्या, रूटिंग से जुड़ी समस्या का एक उदाहरण है. इस समस्या के बारे में ऑप्टिमाइज़ेशन से जुड़ी समस्या क्या है? में बताया गया है. दूसरी समस्या है, यात्रा करने वाले विक्रेता की समस्या.

रूटिंग के बारे में ज़्यादा जानें

नेटवर्क फ़्लो

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

बोलने की ज़्यादा से ज़्यादा समस्या में, हर चाप की ज़्यादा से ज़्यादा क्षमता होती है, जिसे एक जगह से दूसरी जगह ले जाया जा सकता है. समस्या यह है कि हर ऑर्डर पर शिप किए जाने वाले सामान की संख्या असाइन की जाए, ताकि ढोए जा रहे कुल सामान की संख्या ज़्यादा से ज़्यादा हो.

नेटवर्क फ़्लो के बारे में ज़्यादा जानें