JPH05128142A - Quasi-optimum solution searching system - Google Patents

Abstract

(57) [Summary] [Purpose] To obtain a method of searching for a quasi-optimal solution that enables the planner to search for a solution that is satisfactory, that is, a quasi-optimal solution at high speed and process it in a short time. [Structure] The constraint conditions of the linear programming problem are expressed by multi-system simultaneous equations, and many multi-system simultaneous equations obtained by giving appropriate constants to some unknowns of the simultaneous equations are distributed to multiple high-speed arithmetic processors and parallelized. When performing the arithmetic processing and evaluating the obtained solution, the suboptimal solution is searched by advancing the search in the search space from the vicinity of the value considered to be the optimum solution toward the end of the constraint.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for searching a suboptimal solution of a so-called linear programming problem such as Hitchcock type transportation problem or resource combination problem.

[0002]

2. Description of the Related Art Conventionally, as a method for obtaining an optimum solution of a linear programming problem, a numerical calculation method such as a simplex method or, recently, AI technique is used to express a constraint condition or an evaluation function by a rule and follow the rule. However, a method of deriving an optimal solution is being tried.

[0003]

Both the simplex method and the AI method described above are methods for deriving an optimum solution while improving the solution so as to maximize the evaluation function under a certain constraint condition, and the evaluation is low. It is a serial process that starts search from the solution in order and finally tries to reach the optimal solution.
Therefore, especially for a large linear programming problem, it took a long time to process even if a large computer was used. An object of the present invention is to provide a method of searching for a quasi-optimal solution that enables a planner to search a solution that is satisfactory, that is, a quasi-optimal solution at high speed and process the solution in a short time.

[0004]

The method for searching for a sub-optimal solution according to the present invention expresses the constraint condition of a linear programming problem by a multi-dimensional simultaneous equation and gives appropriate constants to some unknowns of this simultaneous equation. Many parallel simultaneous equations obtained by allocating to multiple high-speed arithmetic processors and performing parallel arithmetic processing, and when evaluating the obtained solution, constraints from the neighborhood of the value that seems to be the optimal solution in the search space A quasi-optimal solution is searched by advancing the search toward the end.

[0005]

DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 is a block diagram showing the configuration of an arithmetic unit for carrying out a suboptimal solution search method according to an embodiment of the present invention. In the figure, 1 is a plan making computer, and 2 is a man-machine interface of the plan making computer.
Reference numeral 3 is a governing device, and 4 is a plurality of high-speed arithmetic processors controlled by the governing device 3 and performing parallel arithmetic processing respectively.

For example, in a general linear programming problem, the constraint condition di min ≤Σaij * xj ≤di max i = 1,2, ..., m j = 1,2, ..., n ej min ≤xj ≤ej max evaluation function Z = ΣCj * xj + Co, the constraint conditions are described by the following multi-dimensional simultaneous equations. Σa1j * xj = y1 (1) Σa2j * xj = y2 (2) Σa3j * xj = y3 (3) ... Σamj * xj = ym (m) n ≧ m where ym is a target value dm min ≤ ym ≤ dm max
Is. Further, Σ represents the total sum of 1 to n for j.

In order to solve this simultaneous equation, (nm)
An appropriate constant is given to each xj. This constant is (nm)
The number of simultaneous x-j equations is set for each combination of the constant values of (nm) xj to obtain many m-element simultaneous equations. When this simultaneous equation is solved by parallel arithmetic processing, an initial parameter (*) is given to a plurality of high-speed arithmetic processors 4 in FIG. 1, and xj given as a constant is taken as an optimum solution of ej min ≤xj ≤ej max. Proceed toward the end of the constraint, given near the likely value (eg, center value). Then, the obtained solution is evaluated, and a solution which is equal to or higher than the criterion is adopted as a satisfactory solution, that is, a suboptimal solution.

The initial value includes a parameter commonly given to all processors and a parameter individually given to each processor, and they are as follows. A) Parameters common to all processors: 1) Upper and lower limit values of solution xj ej max, ej min 2) Coefficients of simultaneous equations aij 3) Upper and lower limits of simultaneous simultaneous court dm max, dm min 4) Multiple Target value of simultaneous court ym 5) xj of constant treatment and change range 6) Evaluation standard value B) Parameter given to each processor 1) Search space of each

Next, an example of this solution will be described.
A three-dimensional simultaneous equation with five unknowns is described as follows. δ11 x1 + δ12 x2 + δ13 x3 + δ14 x4 + δ15 x5 = y1 (1) δ21 x1 + δ22 x2 + δ23 x3 + δ24 x4 + δ25 x5 +5 x3 + δ3 + δ3 + δ3 + δ3 + δ3 + δ3 + δ3 min ≤ x1 ≤ e1 max e2 min ≤ x2 ≤ e2 max e3 min ≤ x3 ≤ e3 max e4 min ≤ x4 ≤ e4 max e5 min ≤ x5 ≤ e5 max d1 min ≤ y1 ≤ d1 max d2 min ≤ y2 ≤ d2 max d3 min ≤y3 ≤d3 max

Although constants are given to x4 and x5 in the above equations (1) to (3), the experience value of the planner is, for example, 10≤X4≤.
When 20, 30 ≤ X5 ≤ 50, the range is divided into, for example, 10 equal parts, the central region is searched, and the range is expanded toward the upper and lower limit values.
In general, effective variables used in operation of the operation are not mathematically rigorously solved, and for example, a rough numerical value up to about one decimal place is sufficient. Therefore, in this embodiment, the quasi-optimal solution is obtained by appropriately setting the change width into 10 equal parts as described above.

In the present embodiment, an intersection (solution) is searched while translating n planes in a polyhedron existing in an n-dimensional Euclidean space, and if the intersection is inside the polyhedron, the solution is adopted. , If it is outside, it is out of scope and is not adopted. That is, the search space can be narrowed by stopping the search (stopping the search in the next region) when the solution becomes outside the polyhedron when the plane is translated.
Further, when the calculation is not completed even by such processing, the search is stopped up to a predetermined area (a fixed distance from the initial value). For example, a fixed distance from the initial value is i, j,
Set k ... Within i0 ± h, j0 ± h, k0 ± h, and search within that range. In the embodiment of FIG. 2 described below,
.. are set to the regions a, b, c ...

FIG. 2 shows an example of processing by two high-speed arithmetic processors. Both processors A and B divide the area within the area of a to solve a multi-dimensional simultaneous equation, and notify the governing device 3 of the combination of the obtained solutions that has the highest evaluation as a suboptimal solution. And select the one with the highest evaluation. If no solution is obtained in the region of a,
The area of b and the search space are sequentially expanded in the order of c → d → e.

A problem in parallel processing by a plurality of high-speed arithmetic processors is that it is not easy to divide a program or allocate data to each processor, and the data communication between the processors is enormous. However, in this embodiment, the linear programming problem is described by a multi-dimensional simultaneous equation, and the range solved by each processor is allocated to each processor. .. Further, simultaneous processing equations to be solved by each processor are first generated by giving initial parameters to each processor, and a suboptimal solution is returned to the governing device 3 to increase the processing speed.

For example, as an example of a resource combination problem, a raw material blending plan is given. In the mid-to-long term plan for the year and the half year, the cost is often taken into consideration as an evaluation function with the highest priority. In the short-term level plan, the quality of blended raw materials and inventory adjustment for each brand at every yard are given top priority. For this reason, the planner determines the blending amount for each brand while changing the constraint conditions so that the quality and the inventory are appropriate as the constraint conditions rather than the cost of the evaluation function. In such a case, the present embodiment, which searches for a suboptimal solution that satisfies the constraint condition at high speed, is particularly useful.

[0015]

As described above, according to the present invention, a linear programming problem is represented by a multi-dimensional simultaneous equation, the parallel processing is performed by a plurality of high-speed arithmetic processors, and the search is performed with a value that is considered to be an optimum solution. Since it is designed to proceed from the neighborhood toward the end of the constraint, it is possible to search the suboptimal solution at high speed.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of an apparatus that implements a suboptimal solution search method according to an embodiment of the present invention.

FIG. 2 is an explanatory diagram showing an example in which processing is performed by two high-speed arithmetic processors.

[Explanation of symbols]

 1 Planning computer 2 Man-machine interface of planning computer 3 Governance device 4 High-speed arithmetic processor

Claims (1)

[Claims] 1. A multi-dimensional simultaneous equation obtained by expressing the constraint condition of a linear programming problem by a simultaneous equation and assigning an appropriate constant to some of the unknowns of this simultaneous equation is distributed to a plurality of arithmetic processors to perform parallel arithmetic processing. When evaluating the solution obtained by this parallel operation processing, a suboptimal solution is obtained by advancing the search from a predetermined value within the range where the optimal solution exists in the search space toward the end of the constraint. A method of searching for a suboptimal solution characterized by the following.