Google OR-Tools : 線性優化 - 1. The Glop Linear Solver

線性優化原文連結
在符合下列條件下，求得3x + 4y 最大值

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

如果把上述範例圖像化可得到以下圖片，

我們的目標3x+4y之最大值一定是在這個三角形的端點之一

可以把三個端點的值都代入，也可求得解

但如果不自己畫圖，該怎麼做呢

# Step 1: Import the linear solver, or MIP, or cp_model

from __future__ import print_functionfrom ortools.linear_solver import pywraplp

# Step 2: Add the solution printer
此步驟不需要

# Step 3: Declare the linear solver, or MIP, or cp_model

    solver = pywraplp.Solver('LinearProgrammingExample',
                             pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

宣告使用Glop solver, 叫做'LinearProgrammingExample'

# Step 4: Create a database and requests
此步驟不需要

# Step 5: Create the variables

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

創立x & y 兩個變數，他們的值為0到無限大

# Step 6: Define the constraints

    # Constraint 0: x + 2y <= 14.
    constraint0 = solver.Constraint(-solver.infinity(), 14)
    constraint0.SetCoefficient(x, 1)
    constraint0.SetCoefficient(y, 2)

    # Constraint 1: 3x - y >= 0.
    constraint1 = solver.Constraint(0, solver.infinity())
    constraint1.SetCoefficient(x, 3)
    constraint1.SetCoefficient(y, -1)

    # Constraint 2: x - y <= 2.
    constraint2 = solver.Constraint(-solver.infinity(), 2)
    constraint2.SetCoefficient(x, 1)
    constraint2.SetCoefficient(y, -1)

加入約束範圍的三條線
SetCoefficient是指變數前的係數

# Step 7: Define the objective

    # Objective function: 3x + 4y.
    objective = solver.Objective()
    objective.SetCoefficient(x, 3)
    objective.SetCoefficient(y, 4)
    objective.SetMaximization()

定義目標之參數與係數

# Step 8: Create a solver and invoke solve

    solver.Solve()
    opt_solution = 3 * x.solution_value() + 4 * y.solution_value()

呼叫solver
# Step 9: Call a printer and display the results

    print('Number of variables =', solver.NumVariables())
    print('Number of constraints =', solver.NumConstraints())
    # The value of each variable in the solution.
    print('Solution:')
    print('x = ', x.solution_value())
    print('y = ', y.solution_value())
    # The objective value of the solution.
    print('Optimal objective value =', opt_solution)

上述可得到

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

這個方法看起來很煩，下次介紹簡潔的寫法