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
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.')
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]
If you have any opinions or corrections, please let us know.
Recommended Posts