এই পৃষ্ঠাটি Cloud Translation API অনুবাদ করেছে।

একটি এলপি সমস্যা সমাধান করা

নিম্নলিখিত বিভাগগুলি একটি LP সমস্যার উদাহরণ উপস্থাপন করে এবং কীভাবে এটি সমাধান করা যায় তা দেখায়। এখানে সমস্যা:

নিম্নলিখিত সীমাবদ্ধতা সাপেক্ষে সর্বাধিক 3x + 4y করুন:

x + 2y ≤ 14
3x - y ≥ 0
x - y ≤ 2

উদ্দেশ্য ফাংশন, 3x + 4y এবং সীমাবদ্ধতা উভয়ই রৈখিক অভিব্যক্তি দ্বারা দেওয়া হয়, যা এটিকে একটি রৈখিক সমস্যা করে তোলে।

সীমাবদ্ধতাগুলি সম্ভাব্য অঞ্চলকে সংজ্ঞায়িত করে, যা নীচে দেখানো ত্রিভুজ, এর অভ্যন্তর সহ।

একটি LP সমস্যা সমাধানের জন্য প্রাথমিক পদক্ষেপ

একটি LP সমস্যা সমাধানের জন্য, আপনার প্রোগ্রামে নিম্নলিখিত পদক্ষেপগুলি অন্তর্ভুক্ত করা উচিত:

রৈখিক সমাধানকারী মোড়ক আমদানি করুন,
এলপি সলভার ঘোষণা করুন,
ভেরিয়েবলের সংজ্ঞা দাও,
সীমাবদ্ধতা সংজ্ঞায়িত করুন,
উদ্দেশ্য সংজ্ঞায়িত করুন,
এলপি সমাধানকারীকে কল করুন; এবং
সমাধান প্রদর্শন

MPSolver ব্যবহার করে সমাধান

নিম্নলিখিত বিভাগটি একটি প্রোগ্রাম উপস্থাপন করে যা MPSolver র্যাপার এবং একটি LP সমাধানকারী ব্যবহার করে সমস্যার সমাধান করে।

দ্রষ্টব্য। নীচের প্রোগ্রামটি চালানোর জন্য, আপনাকে OR-Tools ইনস্টল করতে হবে।

প্রাথমিক OR-Tools লিনিয়ার অপ্টিমাইজেশান সলভার হল Glop , গুগলের ইন-হাউস লিনিয়ার প্রোগ্রামিং সল্ভার। এটি দ্রুত, মেমরি দক্ষ এবং সংখ্যাগতভাবে স্থিতিশীল।

রৈখিক সমাধানকারী মোড়ক আমদানি করুন

OR-Tools লিনিয়ার সলভার র্যাপার আমদানি করুন (বা অন্তর্ভুক্ত করুন), এমআইপি সলভার এবং লিনিয়ার সলভারগুলির জন্য একটি ইন্টারফেস, নীচে দেখানো হয়েছে৷

পাইথন

from ortools.linear_solver import pywraplp

সি++

#include <iostream>
#include <memory>

#include "ortools/linear_solver/linear_solver.h"

জাভা

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;

সি#

using System;
using Google.OrTools.LinearSolver;

এলপি সলভার ঘোষণা করুন

MPsolver হল Glop সহ বিভিন্ন সমাধানকারীর জন্য একটি মোড়ক। নীচের কোডটি GLOP সমাধানকারী ঘোষণা করে।

পাইথন

solver = pywraplp.Solver.CreateSolver("GLOP")
if not solver:
    return

সি++

std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
  LOG(WARNING) << "SCIP solver unavailable.";
  return;
}

জাভা

MPSolver solver = MPSolver.createSolver("GLOP");

সি#

Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    return;
}

দ্রষ্টব্য: একটি বিকল্প LP সল্ভার ব্যবহার করার জন্য GLOP এর জন্য PDLP প্রতিস্থাপন করুন। সমাধানকারী নির্বাচন করার বিষয়ে আরও বিশদ বিবরণের জন্য, উন্নত এলপি সমাধান দেখুন এবং তৃতীয় পক্ষের সমাধানকারীদের ইনস্টলেশনের জন্য ইনস্টলেশন গাইড দেখুন।

ভেরিয়েবল তৈরি করুন

প্রথমে, x এবং y ভেরিয়েবল তৈরি করুন যার মান 0 থেকে অসীম পর্যন্ত।

পাইথন

x = solver.NumVar(0, solver.infinity(), "x")
y = solver.NumVar(0, solver.infinity(), "y")

print("Number of variables =", solver.NumVariables())

সি++

const double infinity = solver->infinity();
// x and y are non-negative variables.
MPVariable* const x = solver->MakeNumVar(0.0, infinity, "x");
MPVariable* const y = solver->MakeNumVar(0.0, infinity, "y");
LOG(INFO) << "Number of variables = " << solver->NumVariables();

জাভা

double infinity = java.lang.Double.POSITIVE_INFINITY;
// x and y are continuous non-negative variables.
MPVariable x = solver.makeNumVar(0.0, infinity, "x");
MPVariable y = solver.makeNumVar(0.0, infinity, "y");
System.out.println("Number of variables = " + solver.numVariables());

সি#

Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");

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

সীমাবদ্ধতা সংজ্ঞায়িত করুন

এর পরে, ভেরিয়েবলের সীমাবদ্ধতাগুলি সংজ্ঞায়িত করুন। প্রতিটি সীমাবদ্ধতাকে একটি অনন্য নাম দিন (যেমন constraint0 ), এবং তারপর সীমাবদ্ধতার জন্য সহগ সংজ্ঞায়িত করুন।

পাইথন

# Constraint 0: x + 2y <= 14.
solver.Add(x + 2 * y <= 14.0)

# Constraint 1: 3x - y >= 0.
solver.Add(3 * x - y >= 0.0)

# Constraint 2: x - y <= 2.
solver.Add(x - y <= 2.0)

print("Number of constraints =", solver.NumConstraints())

সি++

// x + 2*y <= 14.
MPConstraint* const c0 = solver->MakeRowConstraint(-infinity, 14.0);
c0->SetCoefficient(x, 1);
c0->SetCoefficient(y, 2);

// 3*x - y >= 0.
MPConstraint* const c1 = solver->MakeRowConstraint(0.0, infinity);
c1->SetCoefficient(x, 3);
c1->SetCoefficient(y, -1);

// x - y <= 2.
MPConstraint* const c2 = solver->MakeRowConstraint(-infinity, 2.0);
c2->SetCoefficient(x, 1);
c2->SetCoefficient(y, -1);
LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

জাভা

// x + 2*y <= 14.
MPConstraint c0 = solver.makeConstraint(-infinity, 14.0, "c0");
c0.setCoefficient(x, 1);
c0.setCoefficient(y, 2);

// 3*x - y >= 0.
MPConstraint c1 = solver.makeConstraint(0.0, infinity, "c1");
c1.setCoefficient(x, 3);
c1.setCoefficient(y, -1);

// x - y <= 2.
MPConstraint c2 = solver.makeConstraint(-infinity, 2.0, "c2");
c2.setCoefficient(x, 1);
c2.setCoefficient(y, -1);
System.out.println("Number of constraints = " + solver.numConstraints());

সি#

// x + 2y <= 14.
solver.Add(x + 2 * y <= 14.0);

// 3x - y >= 0.
solver.Add(3 * x - y >= 0.0);

// x - y <= 2.
solver.Add(x - y <= 2.0);

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

উদ্দেশ্য ফাংশন সংজ্ঞায়িত করুন

নিম্নলিখিত কোড উদ্দেশ্য ফাংশন সংজ্ঞায়িত করে, 3x + 4y , এবং নির্দিষ্ট করে যে এটি একটি সর্বাধিকীকরণ সমস্যা।

পাইথন

# Objective function: 3x + 4y.
solver.Maximize(3 * x + 4 * y)

সি++

// Objective function: 3x + 4y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 4);
objective->SetMaximization();

জাভা

// Maximize 3 * x + 4 * y.
MPObjective objective = solver.objective();
objective.setCoefficient(x, 3);
objective.setCoefficient(y, 4);
objective.setMaximization();

সি#

// Objective function: 3x + 4y.
solver.Maximize(3 * x + 4 * y);

সমাধানকারীকে আহ্বান করুন

নিম্নলিখিত কোডটি সমাধানকারীকে আহ্বান করে।

পাইথন

print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()

সি++

const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
if (result_status != MPSolver::OPTIMAL) {
  LOG(FATAL) << "The problem does not have an optimal solution!";
}

জাভা

final MPSolver.ResultStatus resultStatus = solver.solve();

সি#

Solver.ResultStatus resultStatus = solver.Solve();

সমাধান প্রদর্শন করুন

নিম্নলিখিত কোড সমাধান প্রদর্শন করে.

পাইথন

if status == pywraplp.Solver.OPTIMAL:
    print("Solution:")
    print(f"Objective value = {solver.Objective().Value():0.1f}")
    print(f"x = {x.solution_value():0.1f}")
    print(f"y = {y.solution_value():0.1f}")
else:
    print("The problem does not have an optimal solution.")

সি++

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

জাভা

if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("Solution:");
  System.out.println("Objective value = " + objective.value());
  System.out.println("x = " + x.solutionValue());
  System.out.println("y = " + y.solutionValue());
} else {
  System.err.println("The problem does not have an optimal solution!");
}

সি#

// Check that the problem has an optimal solution.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
    Console.WriteLine("The problem does not have an optimal solution!");
    return;
}
Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());

সম্পূর্ণ প্রোগ্রাম

সম্পূর্ণ প্রোগ্রাম নীচে দেখানো হয়.

পাইথন

from ortools.linear_solver import pywraplp


def LinearProgrammingExample():
    """Linear programming sample."""
    # Instantiate a Glop solver, naming it LinearExample.
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if not solver:
        return

    # Create the two variables and let them take on any non-negative value.
    x = solver.NumVar(0, solver.infinity(), "x")
    y = solver.NumVar(0, solver.infinity(), "y")

    print("Number of variables =", solver.NumVariables())

    # Constraint 0: x + 2y <= 14.
    solver.Add(x + 2 * y <= 14.0)

    # Constraint 1: 3x - y >= 0.
    solver.Add(3 * x - y >= 0.0)

    # Constraint 2: x - y <= 2.
    solver.Add(x - y <= 2.0)

    print("Number of constraints =", solver.NumConstraints())

    # Objective function: 3x + 4y.
    solver.Maximize(3 * x + 4 * y)

    # Solve the system.
    print(f"Solving with {solver.SolverVersion()}")
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print("Solution:")
        print(f"Objective value = {solver.Objective().Value():0.1f}")
        print(f"x = {x.solution_value():0.1f}")
        print(f"y = {y.solution_value():0.1f}")
    else:
        print("The problem does not have an optimal solution.")

    print("\nAdvanced usage:")
    print(f"Problem solved in {solver.wall_time():d} milliseconds")
    print(f"Problem solved in {solver.iterations():d} iterations")


LinearProgrammingExample()

সি++

#include <iostream>
#include <memory>

#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void LinearProgrammingExample() {
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
  if (!solver) {
    LOG(WARNING) << "SCIP solver unavailable.";
    return;
  }

  const double infinity = solver->infinity();
  // x and y are non-negative variables.
  MPVariable* const x = solver->MakeNumVar(0.0, infinity, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, infinity, "y");
  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // x + 2*y <= 14.
  MPConstraint* const c0 = solver->MakeRowConstraint(-infinity, 14.0);
  c0->SetCoefficient(x, 1);
  c0->SetCoefficient(y, 2);

  // 3*x - y >= 0.
  MPConstraint* const c1 = solver->MakeRowConstraint(0.0, infinity);
  c1->SetCoefficient(x, 3);
  c1->SetCoefficient(y, -1);

  // x - y <= 2.
  MPConstraint* const c2 = solver->MakeRowConstraint(-infinity, 2.0);
  c2->SetCoefficient(x, 1);
  c2->SetCoefficient(y, -1);
  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Objective function: 3x + 4y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 4);
  objective->SetMaximization();

  const MPSolver::ResultStatus result_status = solver->Solve();
  // Check that the problem has an optimal solution.
  if (result_status != MPSolver::OPTIMAL) {
    LOG(FATAL) << "The problem does not have an optimal solution!";
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Optimal objective value = " << objective->Value();
  LOG(INFO) << x->name() << " = " << x->solution_value();
  LOG(INFO) << y->name() << " = " << y->solution_value();
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::LinearProgrammingExample();
  return EXIT_SUCCESS;
}

জাভা

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;

/** Simple linear programming example. */
public final class LinearProgrammingExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    MPSolver solver = MPSolver.createSolver("GLOP");

    double infinity = java.lang.Double.POSITIVE_INFINITY;
    // x and y are continuous non-negative variables.
    MPVariable x = solver.makeNumVar(0.0, infinity, "x");
    MPVariable y = solver.makeNumVar(0.0, infinity, "y");
    System.out.println("Number of variables = " + solver.numVariables());

    // x + 2*y <= 14.
    MPConstraint c0 = solver.makeConstraint(-infinity, 14.0, "c0");
    c0.setCoefficient(x, 1);
    c0.setCoefficient(y, 2);

    // 3*x - y >= 0.
    MPConstraint c1 = solver.makeConstraint(0.0, infinity, "c1");
    c1.setCoefficient(x, 3);
    c1.setCoefficient(y, -1);

    // x - y <= 2.
    MPConstraint c2 = solver.makeConstraint(-infinity, 2.0, "c2");
    c2.setCoefficient(x, 1);
    c2.setCoefficient(y, -1);
    System.out.println("Number of constraints = " + solver.numConstraints());

    // Maximize 3 * x + 4 * y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 4);
    objective.setMaximization();

    final MPSolver.ResultStatus resultStatus = solver.solve();

    if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
      System.out.println("Solution:");
      System.out.println("Objective value = " + objective.value());
      System.out.println("x = " + x.solutionValue());
      System.out.println("y = " + y.solutionValue());
    } else {
      System.err.println("The problem does not have an optimal solution!");
    }

    System.out.println("\nAdvanced usage:");
    System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
    System.out.println("Problem solved in " + solver.iterations() + " iterations");
  }

  private LinearProgrammingExample() {}
}

সি#

using System;
using Google.OrTools.LinearSolver;

public class LinearProgrammingExample
{
    static void Main()
    {
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            return;
        }
        // x and y are continuous non-negative variables.
        Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
        Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");

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

        // x + 2y <= 14.
        solver.Add(x + 2 * y <= 14.0);

        // 3x - y >= 0.
        solver.Add(3 * x - y >= 0.0);

        // x - y <= 2.
        solver.Add(x - y <= 2.0);

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

        // Objective function: 3x + 4y.
        solver.Maximize(3 * x + 4 * y);

        Solver.ResultStatus resultStatus = solver.Solve();

        // Check that the problem has an optimal solution.
        if (resultStatus != Solver.ResultStatus.OPTIMAL)
        {
            Console.WriteLine("The problem does not have an optimal solution!");
            return;
        }
        Console.WriteLine("Solution:");
        Console.WriteLine("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());

        Console.WriteLine("\nAdvanced usage:");
        Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
        Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
    }
}

সর্বোত্তম সমাধান

প্রোগ্রামটি সমস্যার সর্বোত্তম সমাধান প্রদান করে, যেমনটি নীচে দেখানো হয়েছে।

Number of variables = 2
Number of constraints = 3
Solution:
x = 6.0
y = 4.0
Optimal objective value = 34.0

এখানে সমাধান দেখানো একটি গ্রাফ আছে:

ড্যাশ করা সবুজ রেখাটি তার সর্বোত্তম মানের 34 এর সমান অবজেক্টিভ ফাংশন সেট করে সংজ্ঞায়িত করা হয়। যে কোন লাইনের সমীকরণের ফর্ম 3x + 4y = c আছে ড্যাশড লাইনের সমান্তরাল, এবং 34 হল c এর বৃহত্তম মান যার জন্য লাইনটি সম্ভাব্য অঞ্চলকে ছেদ করে।

রৈখিক অপ্টিমাইজেশান সমস্যার সমাধান সম্পর্কে আরও জানতে, উন্নত এলপি সমাধান দেখুন।