این صفحه به‌وسیله ‏Cloud Translation API‏ ترجمه شده است.

حل مشکل LP

بخش‌های زیر نمونه‌ای از یک مشکل LP را ارائه می‌کنند و نحوه حل آن را نشان می‌دهند. مشکل اینجاست:

3x + 4y با توجه به محدودیت‌های زیر به حداکثر برسانید:

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

هر دو تابع هدف، 3x + 4y ، و محدودیت ها با عبارات خطی داده می شوند، که این مسئله را به صورت خطی تبدیل می کند.

محدودیت‌ها ناحیه‌ی امکان‌پذیر را که مثلثی است که در زیر نشان داده شده است، شامل داخل آن تعریف می‌کنند.

مراحل اساسی برای حل یک مشکل LP

برای حل مشکل LP، برنامه شما باید شامل مراحل زیر باشد:

وارد کردن لفاف حل خطی،
حل کننده LP را اعلام کنید،
متغیرها را تعریف کنید،
محدودیت ها را تعریف کنید،
هدف را تعریف کنید،
با حل کننده LP تماس بگیرید. و
راه حل را نمایش دهید

راه حل با استفاده از MPSolver

بخش زیر برنامه ای را ارائه می دهد که با استفاده از Wrapper MPSolver و یک حل کننده LP مشکل را حل می کند.

توجه داشته باشید. برای اجرای برنامه زیر، باید OR-Tools را نصب کنید .

حل‌کننده اصلی بهینه‌سازی خطی OR-Tools، Glop ، حل‌کننده برنامه‌نویسی خطی داخلی Google است. سریع، کارآمد حافظه و از نظر عددی پایدار است.

لفاف حل خطی را وارد کنید

همانطور که در زیر نشان داده شده است، بسته‌بندی حل‌کننده خطی OR-Tools، رابطی برای حل‌کننده‌های MIP و حل‌کننده‌های خطی، وارد کنید (یا شامل کنید).

پایتون

from ortools.linear_solver import pywraplp

C++

#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;

حل کننده LP را اعلام کنید

MPsolver یک پوشش برای چندین حل کننده مختلف از جمله Glop است. کد زیر حل کننده GLOP را اعلام می کند.

پایتون

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

C++

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 جایگزین، PDLP جایگزین GLOP کنید. برای جزئیات بیشتر در مورد انتخاب حل کننده ها، به حل پیشرفته LP و برای نصب حل کننده های شخص ثالث، به راهنمای نصب مراجعه کنید.

متغیرها را ایجاد کنید

ابتدا متغیرهای x و y را ایجاد کنید که مقادیر آنها در محدوده 0 تا بی نهایت باشد.

پایتون

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

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

C++

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())

C++

// 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)

C++

// 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()

C++

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.")

C++

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()

C++

#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 است که خط برای آن خط منطقه امکان پذیر را قطع می کند.

برای کسب اطلاعات بیشتر در مورد حل مسائل بهینه سازی خطی، به حل پیشرفته LP مراجعه کنید.