इस पेज का अनुवाद Cloud Translation API से किया गया है.

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

नीचे दिए गए सेक्शन में, C++ के साथ OR-टूल का इस्तेमाल किया जा सकता है:

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

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

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

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

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

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

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

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

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

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

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

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

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

यहां दी गई शर्तों के हिसाब से 3x + y का ज़्यादा से ज़्यादा इस्तेमाल करें:

0 ≤ x ≤ 1
0 ≤ y ≤ 2
x + y ≤ 2

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

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

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

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

C++ प्रोग्राम

इस सेक्शन में C++ प्रोग्राम के बारे में बताया गया है. यह प्रोग्राम, सवाल को सेट अप करता है और उसे हल करता है.

इसका तरीका यहां बताया गया है:

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

#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

सॉल्वर का एलान करें.
```
// Create the linear solver with the GLOP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
if (!solver) {
  LOG(WARNING) << "Could not create solver GLOP";
  return;
}
```
MPSolver किसी भी लीनियर प्रोग्रामिंग या मिक्स्ड इंटीजर प्रोग्रामिंग से जुड़ी समस्याओं को हल करने का रैपर होता है.

वैरिएबल बनाएं.

// Create the variables x and y.
MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

LOG(INFO) << "Number of variables = " << solver->NumVariables();

सीमाएं तय करें. पहली दो सीमाएं, 0 &leq; x ≤ 1 और 0 &leq; y ≤ 2, पहले ही वैरिएबल की परिभाषा के हिसाब से सेट होती हैं. यह कोड, कंस्ट्रेंट x + y &leq; 2 के बारे में बताता है:
```
// Create a linear constraint, x + y <= 2.
const double infinity = solver->infinity();
MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
ct->SetCoefficient(x, 1);
ct->SetCoefficient(y, 1);

LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
```
यह तरीका SetCoefficient कंस्ट्रेंट के लिए एक्सप्रेशन में, x और y के गुणांक सेट करता है.

मकसद फ़ंक्शन तय करें.

// Create the objective function, 3 * x + y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 1);
objective->SetMaximization();

SetMaximization तरीका बताता है कि यह बहुत बड़ी समस्या है.

सॉल्वर को शुरू करें और नतीजे दिखाएं.

LOG(INFO) << "Solving with " << solver->SolverVersion();
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
LOG(INFO) << "Status: " << result_status;
if (result_status != MPSolver::OPTIMAL) {
  LOG(INFO) << "The problem does not have an optimal solution!";
  if (result_status == MPSolver::FEASIBLE) {
    LOG(INFO) << "A potentially suboptimal solution was found";
  } else {
    LOG(WARNING) << "The solver could not solve the problem.";
    return;
  }
}

LOG(INFO) << "Solution:";
LOG(INFO) << "Objective value = " << objective->Value();
LOG(INFO) << "x = " << x->solution_value();
LOG(INFO) << "y = " << y->solution_value();

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

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

// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);

  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetFlag(&FLAGS_stderrthreshold, 0);
  operations_research::BasicExample();
  return EXIT_SUCCESS;
}

C++ प्रोग्राम चलाना

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

ऊपर दिए गए कोड को कॉपी करके नई फ़ाइल में चिपकाएं और उसे program.cc के तौर पर सेव करें.
उस डायरेक्ट्री में सबसे ऊपर मौजूद कमांड विंडो खोलें जहां आपने OR-टूल इंस्टॉल किया है. यह डालें:
```
make run SOURCE=relative/path/to/program.cc
```
जहां relative/path/to/, उस डायरेक्ट्री का पाथ है जहां आपने प्रोग्राम को सेव किया है.

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

Solution:
x =  1.0
y =  1.0

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

make build SOURCE=relative/path/to/program.cc

ऑप्ट मोड में कंपाइल किया जा रहा है

O3 मोड में कंपाइल करने के लिए:

make DEBUG='-O3' all

C++ एक्ज़ीक्यूटेबल चलाना

जब OR-टूल C++ प्रोग्राम को make के साथ कंपाइल किया जाता है, तो वह bin डायरेक्ट्री में बन जाता है. उदाहरण प्रोग्राम के लिए एक्ज़ीक्यूटेबल को इस तरह चलाया जा सकता है:

cd bin && ./program

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

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

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

यह पता करना कि आपको किस तरह की समस्या को हल करना है

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Assignment

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

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

पैकिंग

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

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

शेड्यूल करें

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

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

रूटिंग

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

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

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

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

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

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