تمت ترجمة هذه الصفحة بواسطة Cloud Translation API‏.

استخدام المصفوفات لتحديد نموذج

لقد أوضحنا في القسم السابق كيفية حل MIP باستخدام بضعة متغيرات القيود التي يتم تحديدها بشكل فردي. بالنسبة للمشكلات الأكبر، من المرجح مناسب لتحديد المتغيرات والقيود عن طريق التكرار الحلقي على الصفائف. تشير رسالة الأشكال البيانية يوضح المثال التالي هذا.

مثال

في هذا المثال، سنحل المشكلة التالية.

تكبير 7x₁ + 8x₂ + 2x₃ + 9x₄ + 6x₅ وفقًا للقيود التالية:

5 x₁ + 7 x₂ + 9 x₃ + 2 x₄ + 1 x₅ &leq; 250
18 x₁ أو أكثر 4 ×₂ - 9 x₃ + 10 x₄ + 12 x₅ &leq; 285
4 x₁ + 7 x₂ + 3 x₃ + 8 x₄ + 5 x₅ &leq; 211
5 x₁ + 13 x₂ + 16 x₃ + 3 ×₄ - 7 x₅ &leq; 315

حيث تكون x₁ وx₂ و... وx₅ غير سالبة الأعداد الصحيحة.

تعرض الأقسام التالية البرامج التي تحل هذه المشكلة. البرامج يستخدمون نفس الطرق المستخدمة في مثال MIP السابق، لكن وفي هذه الحالة، نطبقها على قيم الصفيفة في تكرار حلقي.

تضمين أداة الحلّ

تبدأ في أي برنامج من برامج MIP باستيراد برنامج تضمين أداة الحل الخطي تعلن عن أداة حل MIP، كما هو موضح في مثال MIP السابق.

إنشاء البيانات

تُنشئ التعليمة البرمجية التالية صفائف تحتوي على بيانات المثال: المعاملات المتغيرة للقيود والدالة الموضوعية، وحدود القيود.

Python

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["constraint_coeffs"] = [
        [5, 7, 9, 2, 1],
        [18, 4, -9, 10, 12],
        [4, 7, 3, 8, 5],
        [5, 13, 16, 3, -7],
    ]
    data["bounds"] = [250, 285, 211, 315]
    data["obj_coeffs"] = [7, 8, 2, 9, 6]
    data["num_vars"] = 5
    data["num_constraints"] = 4
    return data

C++‎

struct DataModel {
  const std::vector<std::vector<double>> constraint_coeffs{
      {5, 7, 9, 2, 1},
      {18, 4, -9, 10, 12},
      {4, 7, 3, 8, 5},
      {5, 13, 16, 3, -7},
  };
  const std::vector<double> bounds{250, 285, 211, 315};
  const std::vector<double> obj_coeffs{7, 8, 2, 9, 6};
  const int num_vars = 5;
  const int num_constraints = 4;
};

لغة Java

static class DataModel {
  public final double[][] constraintCoeffs = {
      {5, 7, 9, 2, 1},
      {18, 4, -9, 10, 12},
      {4, 7, 3, 8, 5},
      {5, 13, 16, 3, -7},
  };
  public final double[] bounds = {250, 285, 211, 315};
  public final double[] objCoeffs = {7, 8, 2, 9, 6};
  public final int numVars = 5;
  public final int numConstraints = 4;
}

#C

class DataModel
{
    public double[,] ConstraintCoeffs = {
        { 5, 7, 9, 2, 1 },
        { 18, 4, -9, 10, 12 },
        { 4, 7, 3, 8, 5 },
        { 5, 13, 16, 3, -7 },
    };
    public double[] Bounds = { 250, 285, 211, 315 };
    public double[] ObjCoeffs = { 7, 8, 2, 9, 6 };
    public int NumVars = 5;
    public int NumConstraints = 4;
}

إنشاء مثيل للبيانات

تنشئ التعليمة البرمجية التالية مثيلاً لنموذج البيانات.

Python

data = create_data_model()

C++‎

DataModel data;

لغة Java

final DataModel data = new DataModel();

#C

DataModel data = new DataModel();

إنشاء مثيل أداة الحلّ

تنشئ التعليمة البرمجية التالية مثيلاً للحل.

Python

# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
    return

C++‎

// Create the mip solver with the SCIP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
  LOG(WARNING) << "SCIP solver unavailable.";
  return;
}

لغة Java

// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
  System.out.println("Could not create solver SCIP");
  return;
}

#C

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

تحديد المتغيرات

تحدد التعليمة البرمجية التالية متغيرات المثال في حلقة تكرارية. للأحجام الكبيرة فإن ذلك أسهل من تحديد المتغيرات على حدة، كما في المثال السابق.

Python

infinity = solver.infinity()
x = {}
for j in range(data["num_vars"]):
    x[j] = solver.IntVar(0, infinity, "x[%i]" % j)
print("Number of variables =", solver.NumVariables())

C++‎

const double infinity = solver->infinity();
// x[j] is an array of non-negative, integer variables.
std::vector<const MPVariable*> x(data.num_vars);
for (int j = 0; j < data.num_vars; ++j) {
  x[j] = solver->MakeIntVar(0.0, infinity, "");
}
LOG(INFO) << "Number of variables = " << solver->NumVariables();

لغة Java

double infinity = java.lang.Double.POSITIVE_INFINITY;
MPVariable[] x = new MPVariable[data.numVars];
for (int j = 0; j < data.numVars; ++j) {
  x[j] = solver.makeIntVar(0.0, infinity, "");
}
System.out.println("Number of variables = " + solver.numVariables());

#C

Variable[] x = new Variable[data.NumVars];
for (int j = 0; j < data.NumVars; j++)
{
    x[j] = solver.MakeIntVar(0.0, double.PositiveInfinity, $"x_{j}");
}
Console.WriteLine("Number of variables = " + solver.NumVariables());

تحديد القيود

تضع التعليمة البرمجية التالية قيودًا للمثال، باستخدام الطريقة MakeRowConstraint (أو صيغة أخرى، حسب لغة الترميز). تشير رسالة الأشكال البيانية أول وسيطتين إلى الطريقة هما الحدان الأدنى والعلوي . الوسيطة الثالثة، اسم القيد، اختيارية.

لكل قيد، يمكنك تحديد معاملات المتغيرات باستخدام دالة الرسم الطريقة SetCoefficient. تعين الطريقة معامل المتغير x[j] في القيد i ليكون الإدخال [i][j] في الصفيف constraint_coeffs

Python

for i in range(data["num_constraints"]):
    constraint = solver.RowConstraint(0, data["bounds"][i], "")
    for j in range(data["num_vars"]):
        constraint.SetCoefficient(x[j], data["constraint_coeffs"][i][j])
print("Number of constraints =", solver.NumConstraints())
# In Python, you can also set the constraints as follows.
# for i in range(data['num_constraints']):
#  constraint_expr = \
# [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])]
#  solver.Add(sum(constraint_expr) <= data['bounds'][i])

C++‎

// Create the constraints.
for (int i = 0; i < data.num_constraints; ++i) {
  MPConstraint* constraint = solver->MakeRowConstraint(0, data.bounds[i], "");
  for (int j = 0; j < data.num_vars; ++j) {
    constraint->SetCoefficient(x[j], data.constraint_coeffs[i][j]);
  }
}
LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

لغة Java

// Create the constraints.
for (int i = 0; i < data.numConstraints; ++i) {
  MPConstraint constraint = solver.makeConstraint(0, data.bounds[i], "");
  for (int j = 0; j < data.numVars; ++j) {
    constraint.setCoefficient(x[j], data.constraintCoeffs[i][j]);
  }
}
System.out.println("Number of constraints = " + solver.numConstraints());

#C

for (int i = 0; i < data.NumConstraints; ++i)
{
    Constraint constraint = solver.MakeConstraint(0, data.Bounds[i], "");
    for (int j = 0; j < data.NumVars; ++j)
    {
        constraint.SetCoefficient(x[j], data.ConstraintCoeffs[i, j]);
    }
}
Console.WriteLine("Number of constraints = " + solver.NumConstraints());

تحديد الهدف

تحدد التعليمة البرمجية التالية الدالة الهدف للمثال. تشير رسالة الأشكال البيانية تخصص طريقة SetCoefficient معاملات الهدف، بينما الدالة SetMaximization بوصفها مسألة تكبير.

Python

objective = solver.Objective()
for j in range(data["num_vars"]):
    objective.SetCoefficient(x[j], data["obj_coeffs"][j])
objective.SetMaximization()
# In Python, you can also set the objective as follows.
# obj_expr = [data['obj_coeffs'][j] * x[j] for j in range(data['num_vars'])]
# solver.Maximize(solver.Sum(obj_expr))

C++‎

// Create the objective function.
MPObjective* const objective = solver->MutableObjective();
for (int j = 0; j < data.num_vars; ++j) {
  objective->SetCoefficient(x[j], data.obj_coeffs[j]);
}
objective->SetMaximization();

لغة Java

MPObjective objective = solver.objective();
for (int j = 0; j < data.numVars; ++j) {
  objective.setCoefficient(x[j], data.objCoeffs[j]);
}
objective.setMaximization();

#C

Objective objective = solver.Objective();
for (int j = 0; j < data.NumVars; ++j)
{
    objective.SetCoefficient(x[j], data.ObjCoeffs[j]);
}
objective.SetMaximization();

طلب أداة حلّ المشكلة

تستدعي التعليمة البرمجية التالية أداة الحل.

Python

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

C++‎

const MPSolver::ResultStatus result_status = solver->Solve();

لغة Java

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

#C

Solver.ResultStatus resultStatus = solver.Solve();

عرض الحلّ

يعرض الكود التالي الحل.

Python

if status == pywraplp.Solver.OPTIMAL:
    print("Objective value =", solver.Objective().Value())
    for j in range(data["num_vars"]):
        print(x[j].name(), " = ", x[j].solution_value())
    print()
    print(f"Problem solved in {solver.wall_time():d} milliseconds")
    print(f"Problem solved in {solver.iterations():d} iterations")
    print(f"Problem solved in {solver.nodes():d} branch-and-bound nodes")
else:
    print("The problem does not have an optimal solution.")

C++‎

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

for (int j = 0; j < data.num_vars; ++j) {
  LOG(INFO) << "x[" << j << "] = " << x[j]->solution_value();
}

لغة Java

// Check that the problem has an optimal solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("Objective value = " + objective.value());
  for (int j = 0; j < data.numVars; ++j) {
    System.out.println("x[" + j + "] = " + x[j].solutionValue());
  }
  System.out.println();
  System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
  System.out.println("Problem solved in " + solver.iterations() + " iterations");
  System.out.println("Problem solved in " + solver.nodes() + " branch-and-bound nodes");
} else {
  System.err.println("The problem does not have an optimal solution.");
}

#C

// 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("Optimal objective value = " + solver.Objective().Value());

for (int j = 0; j < data.NumVars; ++j)
{
    Console.WriteLine("x[" + j + "] = " + x[j].SolutionValue());
}

إليك حل المشكلة.

Number of variables = 5
Number of constraints = 4
Objective value = 260.0
x[0]  =  10.0
x[1]  =  16.0
x[2]  =  4.0
x[3]  =  4.0
x[4]  =  3.0

Problem solved in 29.000000 milliseconds
Problem solved in 315 iterations
Problem solved in 13 branch-and-bound nodes

إكمال البرامج

إليك البرامج الكاملة

Python

from ortools.linear_solver import pywraplp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["constraint_coeffs"] = [
        [5, 7, 9, 2, 1],
        [18, 4, -9, 10, 12],
        [4, 7, 3, 8, 5],
        [5, 13, 16, 3, -7],
    ]
    data["bounds"] = [250, 285, 211, 315]
    data["obj_coeffs"] = [7, 8, 2, 9, 6]
    data["num_vars"] = 5
    data["num_constraints"] = 4
    return data



def main():
    data = create_data_model()
    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver("SCIP")
    if not solver:
        return

    infinity = solver.infinity()
    x = {}
    for j in range(data["num_vars"]):
        x[j] = solver.IntVar(0, infinity, "x[%i]" % j)
    print("Number of variables =", solver.NumVariables())

    for i in range(data["num_constraints"]):
        constraint = solver.RowConstraint(0, data["bounds"][i], "")
        for j in range(data["num_vars"]):
            constraint.SetCoefficient(x[j], data["constraint_coeffs"][i][j])
    print("Number of constraints =", solver.NumConstraints())
    # In Python, you can also set the constraints as follows.
    # for i in range(data['num_constraints']):
    #  constraint_expr = \
    # [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])]
    #  solver.Add(sum(constraint_expr) <= data['bounds'][i])

    objective = solver.Objective()
    for j in range(data["num_vars"]):
        objective.SetCoefficient(x[j], data["obj_coeffs"][j])
    objective.SetMaximization()
    # In Python, you can also set the objective as follows.
    # obj_expr = [data['obj_coeffs'][j] * x[j] for j in range(data['num_vars'])]
    # solver.Maximize(solver.Sum(obj_expr))

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

    if status == pywraplp.Solver.OPTIMAL:
        print("Objective value =", solver.Objective().Value())
        for j in range(data["num_vars"]):
            print(x[j].name(), " = ", x[j].solution_value())
        print()
        print(f"Problem solved in {solver.wall_time():d} milliseconds")
        print(f"Problem solved in {solver.iterations():d} iterations")
        print(f"Problem solved in {solver.nodes():d} branch-and-bound nodes")
    else:
        print("The problem does not have an optimal solution.")


if __name__ == "__main__":
    main()

C++‎

#include <memory>
#include <vector>

#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
struct DataModel {
  const std::vector<std::vector<double>> constraint_coeffs{
      {5, 7, 9, 2, 1},
      {18, 4, -9, 10, 12},
      {4, 7, 3, 8, 5},
      {5, 13, 16, 3, -7},
  };
  const std::vector<double> bounds{250, 285, 211, 315};
  const std::vector<double> obj_coeffs{7, 8, 2, 9, 6};
  const int num_vars = 5;
  const int num_constraints = 4;
};

void MipVarArray() {
  DataModel data;

  // Create the mip solver with the SCIP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
  if (!solver) {
    LOG(WARNING) << "SCIP solver unavailable.";
    return;
  }

  const double infinity = solver->infinity();
  // x[j] is an array of non-negative, integer variables.
  std::vector<const MPVariable*> x(data.num_vars);
  for (int j = 0; j < data.num_vars; ++j) {
    x[j] = solver->MakeIntVar(0.0, infinity, "");
  }
  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // Create the constraints.
  for (int i = 0; i < data.num_constraints; ++i) {
    MPConstraint* constraint = solver->MakeRowConstraint(0, data.bounds[i], "");
    for (int j = 0; j < data.num_vars; ++j) {
      constraint->SetCoefficient(x[j], data.constraint_coeffs[i][j]);
    }
  }
  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Create the objective function.
  MPObjective* const objective = solver->MutableObjective();
  for (int j = 0; j < data.num_vars; ++j) {
    objective->SetCoefficient(x[j], data.obj_coeffs[j]);
  }
  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();

  for (int j = 0; j < data.num_vars; ++j) {
    LOG(INFO) << "x[" << j << "] = " << x[j]->solution_value();
  }
}
}  // namespace operations_research

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

لغة Java

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;

/** MIP example with a variable array. */
public class MipVarArray {
  static class DataModel {
    public final double[][] constraintCoeffs = {
        {5, 7, 9, 2, 1},
        {18, 4, -9, 10, 12},
        {4, 7, 3, 8, 5},
        {5, 13, 16, 3, -7},
    };
    public final double[] bounds = {250, 285, 211, 315};
    public final double[] objCoeffs = {7, 8, 2, 9, 6};
    public final int numVars = 5;
    public final int numConstraints = 4;
  }

  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    final DataModel data = new DataModel();

    // Create the linear solver with the SCIP backend.
    MPSolver solver = MPSolver.createSolver("SCIP");
    if (solver == null) {
      System.out.println("Could not create solver SCIP");
      return;
    }

    double infinity = java.lang.Double.POSITIVE_INFINITY;
    MPVariable[] x = new MPVariable[data.numVars];
    for (int j = 0; j < data.numVars; ++j) {
      x[j] = solver.makeIntVar(0.0, infinity, "");
    }
    System.out.println("Number of variables = " + solver.numVariables());

    // Create the constraints.
    for (int i = 0; i < data.numConstraints; ++i) {
      MPConstraint constraint = solver.makeConstraint(0, data.bounds[i], "");
      for (int j = 0; j < data.numVars; ++j) {
        constraint.setCoefficient(x[j], data.constraintCoeffs[i][j]);
      }
    }
    System.out.println("Number of constraints = " + solver.numConstraints());

    MPObjective objective = solver.objective();
    for (int j = 0; j < data.numVars; ++j) {
      objective.setCoefficient(x[j], data.objCoeffs[j]);
    }
    objective.setMaximization();

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

    // Check that the problem has an optimal solution.
    if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
      System.out.println("Objective value = " + objective.value());
      for (int j = 0; j < data.numVars; ++j) {
        System.out.println("x[" + j + "] = " + x[j].solutionValue());
      }
      System.out.println();
      System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
      System.out.println("Problem solved in " + solver.iterations() + " iterations");
      System.out.println("Problem solved in " + solver.nodes() + " branch-and-bound nodes");
    } else {
      System.err.println("The problem does not have an optimal solution.");
    }
  }

  private MipVarArray() {}
}

#C

using System;
using Google.OrTools.LinearSolver;

public class MipVarArray
{
    class DataModel
    {
        public double[,] ConstraintCoeffs = {
            { 5, 7, 9, 2, 1 },
            { 18, 4, -9, 10, 12 },
            { 4, 7, 3, 8, 5 },
            { 5, 13, 16, 3, -7 },
        };
        public double[] Bounds = { 250, 285, 211, 315 };
        public double[] ObjCoeffs = { 7, 8, 2, 9, 6 };
        public int NumVars = 5;
        public int NumConstraints = 4;
    }
    public static void Main()
    {
        DataModel data = new DataModel();

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

        Variable[] x = new Variable[data.NumVars];
        for (int j = 0; j < data.NumVars; j++)
        {
            x[j] = solver.MakeIntVar(0.0, double.PositiveInfinity, $"x_{j}");
        }
        Console.WriteLine("Number of variables = " + solver.NumVariables());

        for (int i = 0; i < data.NumConstraints; ++i)
        {
            Constraint constraint = solver.MakeConstraint(0, data.Bounds[i], "");
            for (int j = 0; j < data.NumVars; ++j)
            {
                constraint.SetCoefficient(x[j], data.ConstraintCoeffs[i, j]);
            }
        }
        Console.WriteLine("Number of constraints = " + solver.NumConstraints());

        Objective objective = solver.Objective();
        for (int j = 0; j < data.NumVars; ++j)
        {
            objective.SetCoefficient(x[j], data.ObjCoeffs[j]);
        }
        objective.SetMaximization();

        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("Optimal objective value = " + solver.Objective().Value());

        for (int j = 0; j < data.NumVars; ++j)
        {
            Console.WriteLine("x[" + j + "] = " + x[j].SolutionValue());
        }

        Console.WriteLine("\nAdvanced usage:");
        Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
        Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
        Console.WriteLine("Problem solved in " + solver.Nodes() + " branch-and-bound nodes");
    }
}