[PYTHON] Solving Mathematical Optimization Model Exercises with Google's OR-Tools (3) Production Optimization Problems

Introduction

This article is the third article to solve the practice problem of the reference text "Problem solving series by Python: How to make an optimization model using a data analysis library" about mathematical optimization.

The first article is below. Please see here first.

Solving mathematical optimization model exercises with Google's OR-Tools (1) The easiest mass filling problem https://qiita.com/ttlabo/private/7e8c93f387814f99931f

Production optimization problem

This is the third exercise in the reference text. Let's try the following problems at once.

: speech_balloon: Problem

ruby:7.3.problem

I want to maximize profits by producing products with limited raw materials.
The raw material prices and profits for each product and the inventory for each raw material are as follows.

: question: ** Thinking **

This problem is one of the "logistics network design problems" among the mathematical optimization problems called typical problems. Consider constraints and objective functions.

** Constraints ** The problem statement says, "Ingredients are limited." This is a clue to consider the constraints.

** Objective function ** Maximizing the profit is a hint for the objective function.

: a: ** Answer **

Consider the constraints. Let x be the amount that produces product 1 and y be the amount that produces product 2. x and y take positive integer values.

** Constraints ** Ingredient 1 has 40 in stock. The amount of raw material 1 used for product 1 and product 2 is 40 or less. 1 * x + 2 * y <= 40

Next, raw material 2 has 80 in stock. The amount of raw material 2 used for product 1 and product 2 is 80 or less. 4 * x + 4 * y <= 80

Similarly, for raw material 3, the following holds. 3 * x + 1 * y <= 50

** Objective function ** Think about profits. The profit from product 1 is 5.0 and the profit from product 2 is 4.0. The objective function is to maximize the sum of these profits. Profit = x * 5.0 + y * 4.0

Consider the program. The contents of the program basically follow Google's OR-Tools guide. (https://developers.google.com/optimization)

Write a spell at the beginning of the program.

ruby:7.3.renshu.py

from __future__ import print_function
from ortools.linear_solver import pywraplp

Since it is solved by the mixed integer programming solver, it is declared below.

ruby:7.3.renshu.py

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
                             pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

x and y are conditions that do not take negative values. Set the maximum value of x and y to 100.

ruby:7.3.renshu.py

# x,Non-negative condition for y(Must not be negative)
x = solver.IntVar(0.0, 100, 'x')
y = solver.IntVar(0.0, 100, 'y')

Define three constraints.

ruby:7.3.renshu.py

solver.Add(1 * x + 2 * y <= 40)
solver.Add(4 * x + 4 * y <= 80)
solver.Add(3 * x + 1 * y <= 50)

Since this problem is a maximization problem, solver.Maximize is used.

ruby:7.3.renshu.py

#Maximize profits
solver.Maximize(x * 5.0 + y * 4.0)

Execute the solution.

7.3.renshu.py

#Solution execution
status = solver.Solve()

Check the result.

7.3.renshu.py

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    if x.solution_value() > 0.5:
        print('x=',x.solution_value())
        print('y=',y.solution_value())
    print("Time = ", solver.WallTime(), " milliseconds")
else:
    print('The problem does not have an optimal solution.')

The optimization calculation results are as follows.

Solution: ok Objective value = 95.0 x= 15.0 y= 5.0 Time = 369 milliseconds

You can see that you only need to produce 15 products 1 and 5 products 2. The maximized profit is 95.0.

The whole program.

7.3.renshu.py

from __future__ import print_function
from ortools.linear_solver import pywraplp

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

x = solver.IntVar(0.0, 100, 'x')
y = solver.IntVar(0.0, 100, 'y')

#Constraints
solver.Add(1 * x + 2 * y <= 40)
solver.Add(4 * x + 4 * y <= 80)
solver.Add(3 * x + 1 * y <= 50)


#Maximize profits
solver.Maximize(x * 5.0 + y * 4.0)

#Solution execution
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    if x.solution_value() > 0.5:
        print('x=',x.solution_value())
        print('y=',y.solution_value())
    print("Time = ", solver.WallTime(), " milliseconds")
else:
    print('The problem does not have an optimal solution.')

Exhibit

This article is based on the exercises described in the reference text "Problem Solving Series with Python: How to Create an Optimization Model Using a Data Analysis Library" about mathematical optimization.

■ Reference text "Problem-solving series using Python: How to create an optimization model using a data analysis library" Tsutomu Saito [Author] Modern Science Company [Publishing]

Opinions etc.

If you have any opinions or corrections, please let us know.