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.

001.jpg

: 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]

001.jpg

Opinions etc.

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

Recommended Posts

Solving Mathematical Optimization Model Exercises with Google's OR-Tools (3) Production Optimization Problems
Solve Mathematical Optimization Model Exercises with Google's OR-Tools (4) Solve Number Places
Solving 4-color problems with combinatorial optimization
Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems
Solving nurse scheduling problems with combinatorial optimization
Solving school district organization problems with combinatorial optimization
Optimization learned with OR-Tools [Linear programming: multi-stage model]
Introduction to Python Mathematical Optimization Solving junior high school math problems with pulp
Production Planning Optimization (OR-Tools)
Optimization learned with OR-Tools Part0 [Introduction]
Solving game theory with combinatorial optimization
Explanation of production optimization model by Python
Precautions when solving DP problems with Python