Shulou(Shulou.com)06/03 Report--

This article mainly explains "Python mathematical modeling learning simulated annealing algorithm constraint processing implementation method", the explanation content in the article is simple and clear, easy to learn and understand, please follow the small series of ideas slowly in-depth, together to study and learn "Python mathematical modeling learning simulated annealing algorithm constraint processing implementation method"!

Optimization and linear programming

The three elements of optimization problem are decision variables, objective function and constraint conditions.

Linear programming (LP) is an optimization method to study the extremum problem of linear objective function under linear constraint conditions, which is often used to solve the problem of obtaining optimal decision by using existing resources.

Simple linear programming problems can be solved with Lingo software, Matlab, Python also have library functions or solvers to solve linear programming problems, it is easy to learn and use, and do not need to use simulated annealing algorithm. However, integer programming, mixed programming, 0/1 programming, quadratic programming, nonlinear programming and combinatorial optimization problems derived from general linear programming problems cannot be solved by calling a library function. Simulated annealing algorithm has good adaptability in many complex problems, and can be used as a general intelligent algorithm to learn.

In other words, if you are only dealing with linear programming problems, do not use simulated annealing algorithm. However, if it is a complex optimization problem that cannot be handled by existing methods, or you do not know what method to use to deal with a certain type of optimization problem, then simulated annealing algorithm can still be used to solve it.

In this paper, penalty function method is used to analyze simulated annealing algorithm to deal with linear programming problems. The related contents are also applicable to nonlinear programming problems.

2. Simulated annealing algorithm to deal with constraints

Linear programming problems are constrained optimization problems, while simulated annealing algorithm is more suitable for unconstrained optimization problems. For constraints in optimization problems, simulated annealing algorithms have several commonly used methods:

1. Upper and lower bound constraints on the values of decision variables.

This kind of constraint condition is easy to deal with, as long as the initial solution is set, the new solution can be solved between the upper and lower limits of the decision variable. For example:

(1) Set the upper and lower limits of random numbers that generate new solutions to the upper and lower limits of decision variables, i.e.[Xmin, Xmax];

(2) Set the upper and lower limits of the random number that generates the new solution to the upper and lower limits of the current solution and the decision variable, i.e.[Xnow, Xmax];

(3) By conditional judgment, when the new solution exceeds the upper and lower limits of the decision variable, the upper and lower limits are taken, i.e. xNew = max(min(xNew, xMax), xMin). Of course, these processing methods will affect the probability distribution of random numbers, thus affecting the optimization performance of simulated annealing algorithms, which will not be discussed in depth here.

2. The test method deals with inequality constraint problems.

In the iterative process of simulated annealing algorithm, the new solution generated each time is substituted into each inequality constraint function to judge whether the constraint conditions are satisfied; if the new solution does not satisfy the constraint conditions, the new solution is discarded and a new solution is generated again for verification until the new solution satisfies all the constraint conditions. The idea of this method is simple, each iteration is carried out in the feasible region, but for complex problems with many constraints and harsh constraints, the new solutions generated many times cannot satisfy the constraints, which will make the calculation time very long, even stagnant.

3. Elimination method deals with equality constraint problems.

For equality constraints, it is difficult to satisfy the constraint conditions by randomly generated new solutions, and usually cannot be handled by testing methods. Elimination method is to express a decision variable in equality constraint as linear relation of other decision variables by solving equation, and then substitute it into objective function and inequality constraint condition, so as to eliminate the constraint condition. Elimination method not only solves the equality constraint problem, but also reduces the number of decision variables, thus effectively simplifying the complexity of the optimization problem. However, it is very difficult to solve nonlinear equations for nonlinear equality constraints, and the elimination method is not universally applicable.

4. A more general method of dealing with constraints is the penalty function method, described below. YouCans, XUPT

3. Penalty function method

Penalty function method is a kind of commonly used technique to deal with constraint conditions, which is very effective in simulated annealing algorithm. The idea of this method is to transform constraint conditions into penalty functions and add them to the original objective functions to construct new objective functions.

Penalty function method has exterior point method and interior point method. The outside-point method imposes penalty on points outside feasible region (i.e., points that do not satisfy constraints), and does not penalize points inside feasible region, so that iterative points approach feasible region D. The interior point method is to search within the feasible region, and the constraint boundary acts like a wall, so that the objective function cannot pass through, and the search point is limited to the feasible region, so it is only applicable to inequality constraints.

4. Mathematical model case

Although simulated annealing is not recommended for linear programming problems. However, for the sake of understanding, this paper still uses the previous linear programming problem as an example of dealing with constraints. For nonlinear programming problems, as well as nonlinear constraint problems, the treatment is similar and will be described later.

4.1 Problem Description:

A factory produces two kinds of drinks A and B. Each hundred boxes of beverage A requires 6 kilograms of raw materials and 10 workers, earning 100,000 yuan; each hundred boxes of beverage B requires 5 kilograms of raw materials and 20 workers, earning 90,000 yuan.

The factory now has 60 kilograms of raw materials, 150 workers, and due to other conditions, the output of A beverage does not exceed 800 cases.

(1) How to arrange the production plan, that is, how much of each of the two drinks will be produced to maximize profits?

4.2 Problem modeling:

Decision variables:

x1: A Beverage Output (Unit: 100 cases)

x2: B beverage output (unit: 100 cases)

Objective function:

max fx = 10x1 + 9x2

Constraints:

6x1 + 5x2

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.