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

नीचे दिए गए सेक्शन से आपको .Net के लिए OR-टूल इस्तेमाल करने में मदद मिलेगी:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.Net प्रोग्राम

इस सेक्शन में, .Net प्रोग्राम के बारे में जानकारी दी गई है. यह प्रोग्राम, समस्या को सेट अप करता है और उसे हल करता है.

ध्यान दें: .Net प्रोग्राम और इसे चलाने के तरीके की जानकारी, सेक्शन के आखिर में दिखाई जाती है.

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

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

  using System;
  using Google.OrTools.LinearSolver;

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

  // Create the linear solver with the GLOP backend.
  Solver solver = Solver.CreateSolver("GLOP");
  if (solver is null)
  {
      return;
  }

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

  // Create the variables x and y.
  Variable x = solver.MakeNumVar(0.0, 1.0, "x");
  Variable y = solver.MakeNumVar(0.0, 2.0, "y");
  
  Console.WriteLine("Number of variables = " + solver.NumVariables());

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

  // Create a linear constraint, 0 <= x + y <= 2.
  Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
  ct.SetCoefficient(x, 1);
  ct.SetCoefficient(y, 1);
  
  Console.WriteLine("Number of constraints = " + solver.NumConstraints());

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

  // Create the objective function, 3 * x + y.
  Objective objective = solver.Objective();
  objective.SetCoefficient(x, 3);
  objective.SetCoefficient(y, 1);
  objective.SetMaximization();

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

  solver.Solve();
  Console.WriteLine("Solution:");
  Console.WriteLine("Objective value = " + solver.Objective().Value());
  Console.WriteLine("x = " + x.SolutionValue());
  Console.WriteLine("y = " + y.SolutionValue());

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

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

using System;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            return;
        }

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

        Console.WriteLine("Number of variables = " + solver.NumVariables());

        // Create a linear constraint, 0 <= x + y <= 2.
        Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
        ct.SetCoefficient(x, 1);
        ct.SetCoefficient(y, 1);

        Console.WriteLine("Number of constraints = " + solver.NumConstraints());

        // Create the objective function, 3 * x + y.
        Objective objective = solver.Objective();
        objective.SetCoefficient(x, 3);
        objective.SetCoefficient(y, 1);
        objective.SetMaximization();

        solver.Solve();

        Console.WriteLine("Solution:");
        Console.WriteLine("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());
    }
}

.Net प्रोग्राम चलाना

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

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

   <Project Sdk="Microsoft.NET.Sdk">
     <PropertyGroup>
       <OutputType>Exe</OutputType>
       <LangVersion>7.3</LangVersion>
       <TargetFramework>netcoreapp3.1</TargetFramework>
       <EnableDefaultItems>false</EnableDefaultItems>
       <!-- see https://github.com/dotnet/docs/issues/12237 -->
       <RollForward>LatestMajor</RollForward>
       <RestoreSources>../../../temp_dotnet/packages;$(RestoreSources);https://api.nuget.org/v3/index.json</RestoreSources>
       <AssemblyName>Google.OrTools.BasicExample</AssemblyName>
       <IsPackable>true</IsPackable>
     </PropertyGroup>
   
     <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
       <DebugType>full</DebugType>
       <Optimize>true</Optimize>
       <GenerateTailCalls>true</GenerateTailCalls>
     </PropertyGroup>
   
     <ItemGroup>
       <Compile Include="BasicExample.cs" />
       <PackageReference Include="Google.OrTools" Version="9.1.*" />
     </ItemGroup>
   </Project>
   

3. जिस डायरेक्ट्री में आपने OR-टूल इंस्टॉल किया है उसमें सबसे ऊपर के लेवल पर, कमांड विंडो खोलें और यह डालें:

   make run SOURCE=examples/dotnet/BasicExample.cs

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

.Net प्रोग्राम को examples/dotnet/ के अलावा किसी दूसरी डायरेक्ट्री में सेव और चलाया जा सकता है. हालांकि, यह थोड़ा मुश्किल है: ऊपर दिखाई गई csproj फ़ाइल की इस लाइन में बदलाव करना ज़रूरी है:

../../../packages;$(RestoreSources);https://api.nuget.org/v3/index.json

packages डायरेक्ट्री में सही पाथ पाने के लिए.

अपने .Net प्रोग्राम को examples/dotnet/ डायरेक्ट्री में रखना सबसे आसान तरीका है.

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

Solution:
x =  1.0
y =  1.0

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

make build SOURCE=relative/path/to/SimpleProgram.cs

अगर प्रोग्राम में बदलाव किए जाते हैं, तो आपको इसे ऊपर दिखाए गए तरीके से फिर से कंपाइल करना होगा.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Assignment

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

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

पैकिंग

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

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

शेड्यूल करें

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

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

रूटिंग

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

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

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

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

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

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