JP5000735B2 - Material assignment system - Google Patents

Description

  The present invention relates to a member assignment system, a member assignment program, a recording medium, a member assignment method, and a member processing apparatus.

  For pre-cutting of house structural materials, raw materials of several lengths (mainly 3m to 6m) are prepared for each specification such as cross-sectional shape, tree type, grade and layer. A member (product) of a predetermined length is cut out from there. In general-sized houses, there are about 20 types of structural materials called horizontal members such as beams, girders, and foundations. From the raw materials of several lengths prepared for each product specification, about 200 products are cut out when the average of these structural materials is 10 for each building. Depending on the product specifications, the product size, and the combination of raw materials to be cut out, the amount of parts that are cut off from the raw materials and wasted differs. Then, the technique which improves a member allocation method was developed (refer patent document 1).

Japanese Patent No. 3565262 JP 2009-98924 A

  The purpose of the calculation of the member allocation method as described above is to cut out the required product with a few raw materials (highest yield) from a raw material group of several lengths prepared for each product specification. Various other technologies have been developed, but it is said that the allocation method at the pre-cut factory using these technologies is approximately 90%. In the case of a building designed and produced according to a certain standard, the yield can be further improved by determining the size of the structural material suitable for the size of the raw material. However, when a structural material is cut out from a raw material based on a variety of designs by order production, development of a calculation method for further improving the yield is required. In fact, a large amount of waste can be reduced simply by improving the yield by 1%.

  In the above-mentioned Patent Document 2, a combination of cutting out a required product from a raw material group of several kinds of lengths prepared for each product specification is optimized using a calculation result of an existing member assignment method. In particular, a technique for narrowing down the search range when searching for an optimal solution for a large number of combinations is introduced. It is another object of the present invention to provide a member assignment system, a member assignment program, a recording medium, a member assignment method, and a member processing apparatus that further reduce the calculation processing time by advancing search efficiently.

The following configurations are means for solving the above-described problems.
<Configuration 1>
The number of each type of raw material required when each of m products of a predetermined length is cut out from k types of raw materials of a predetermined length, and the combination of products assigned to each raw material is optimized. In response to the input of product length data of m required products, an m-th product length vector Lp having the product length as an element and a product request quantity vector b having the product request quantity as an element are obtained. Product length setting means for generating and storing in the storage device, and input of raw material length data of k types of prepared lengths, and generating a kth-order raw material length vector Lm having the raw material length as an element; One or a plurality of products by comparing the raw material length setting means to be stored in the storage device with the required product length data of the m products and the prepared raw material length data of the k kinds of raw materials Economically An allocation pattern vector generating means for enumerating m-th order allocation pattern vectors indicating the relationship between raw materials and products that can be attached, and an allocation pattern matrix A in which the allocation pattern vectors generated by the allocation pattern vector generation means are arranged. Then, an allocation pattern matrix generating means to be stored in the storage device, and a number vector x for which x i is selected from each of the n allocation patterns included in the allocation pattern matrix and for selecting a corresponding raw material is defined. , Generating an objective function indicating the sum of products of the m-th order cost coefficient vector corresponding to the raw material length vector Lm and the used number vector x, and storing the objective function in a storage device; and the allocation pattern matrix A The number of each product cut out with n allocation patterns selected from the above is not more than the quantity of each required product The first constraint condition expression Ax ≧ b that is not to be generated and the relaxed third constraint condition expression that each element xi of the used number vector x is 0 ≦ xi ≦ 1 is generated and stored in the storage device Means, an initial setting means for accepting an input of an initial executable solution obtained by an arbitrary method and storing it in a storage device, an input of the initial executable solution, the objective function, and the constraint expression, Simplex operation means for executing simplex operation processing, and when the solution has a value of xi of 0 or 1 and does not include other than that by the simplex operation processing, the solution is used as an optimal solution. Outputs allocation data. Otherwise, the value of the objective function of the initial executable solution is set to the maximum value, and the value of the objective function obtained as a result of the simplex operation processing is set to the minimum value. , Enumerate combinations of the number of raw materials used that take the value of the objective function in the range, select the one whose objective function is close to the minimum value, and select the length of which to the constraint condition generation means The generation of the second constraint condition Cx = d, which determines the number of raw materials to be selected and used for the allocation, and assumes that the product of the raw material use matrix C and the raw material use number vector x is equal to the raw material use scheduled quantity vector d Requesting the simplex computing means to perform arithmetic processing under the constraint conditions of the first constraint conditional expression, the second constraint conditional expression, and the third constraint conditional expression; If the value is 0 or 1, and the solution does not include anything else, the member assignment data is output with the solution as the optimal solution, otherwise, the listed raw materials Used The next candidate whose objective function is close to the minimum value is selected from the combinations, and the constraint generation unit is requested to generate a new second constraint condition expression Cx = d. Search control means for controlling to repeat the operation of requesting arithmetic processing to the simplex operation means under the condition, and when xi takes a numerical value between 0 and 1 while satisfying the constraint condition expression, the maximum When a function Σf (xi) having a constant value or minimum value is set as an evaluation expression, and a plurality of non-integer solutions are obtained as a result of the pivot operation, the relationship between these non-integer solutions is expressed as the evaluation expression A determination unit configured to apply and compare, and the search control unit continues the pivot calculation process when it is determined that the determination unit satisfies a certain determination criterion, and when it is determined that the determination criterion is not satisfied The pivot performance Member assignment system, characterized in that to resume the pivoting process by changing the initial conditions for starting the process.

<Configuration 2>
In the member allocation system according to Configuration 1, the determination means takes a numerical value between 0 and 1 while the xi satisfies the constraint condition, and the maximum value of the evaluation formula Σf (xi) is a constant value. If the value of the evaluation formula based on the non-integer solution obtained later is larger than the value of the evaluation formula based on the non-integer solution obtained earlier, the determination criterion is satisfied. The member allocation system characterized by determining.

<Configuration 3>
In the member allocation system according to Configuration 1, the determination means takes a numerical value between 0 and 1 while the xi satisfies the constraint condition, and the minimum value of the evaluation formula Σf (xi) is a constant value. If the value of the evaluation formula based on the non-integer solution obtained later is smaller than the value of the evaluation formula based on the non-integer solution obtained earlier, the determination criterion is satisfied. The member allocation system characterized by determining.

<Configuration 4>
The member allocation system according to Configuration 1, wherein the evaluation unit uses a non-integer solution to sequentially determine a value of the evaluation formula based on a criterion for comparison using an annealing method.

<Configuration 5>
In the member allocation system according to Configuration 1, when the non-integer solution has passed the local optimal solution, it is determined that the criterion is satisfied when the value of the evaluation formula once decreases and then starts increasing A member assignment system characterized by:

<Configuration 6>
The member allocation system according to any one of Configurations 1 to 5, wherein the simplex arithmetic processing is executed under the constraint conditions of the first constraint condition expression and the third constraint condition expression, and an executable solution with a non-integer solution Is obtained, and a simplex operation process for obtaining another new non-integer solution is repeated.

<Configuration 7>
Means for optimizing the combination of products assigned to each raw material by obtaining the number of each type of raw material required when each of m products having a predetermined length is cut out from k kinds of raw materials each having a predetermined length; A pre-cut device that accepts optimized member allocation data and cuts out the m products from the k kinds of raw materials that are sequentially supplied, and inputs the product length data of the required m products And a product length setting means for generating an m-th order product length vector Lp having the product length as an element and a product request quantity vector b having the product request quantity as an element and storing them in a storage device. A raw material length setting means for receiving raw material length data of k kinds of lengths, generating a k-th order raw material length vector Lm having the raw material length as an element, and storing it in a storage device Compare the product length data of the m products with the raw material length data of the k kinds of prepared raw materials, and determine the relationship between the raw material and the product that can allocate one or more products economically. An allocation pattern vector generating means for enumerating m-th order allocation pattern vectors and an allocation pattern matrix A in which the allocation pattern vectors generated by the allocation pattern vector generation means are arranged and stored in a storage device. A generation means, each element for selecting a corresponding raw material selected from n allocation patterns included in the allocation pattern matrix defines a used number vector x of xi, and an m-th order corresponding to the raw material length vector Lm Objective function generating means for generating an objective function indicating the sum of products of the cost coefficient vector and the used number vector x and storing the objective function in a storage device; The first constraint condition Ax ≧ b and the number-of-uses vector x that the number of products cut out by the n number of allocation patterns selected from the allocation pattern matrix A must be equal to or greater than the quantity of each product obtained. A constraint condition generating means for generating a relaxed third constraint condition expression that each element x i of 0 ≦ x i ≦ 1 is stored in a storage device, and an input of an initial executable solution obtained by an arbitrary method An initial setting unit that receives and stores the initial executable solution, the objective function, and the input of the constraint condition expression, and a simplex operation unit that executes a simplex operation process, and the simplex operation process. If the value of xi is either 0 or 1, and the solution does not include any other value, the member assignment data is output with the solution as the optimal solution. In the case of the above, use of the raw material that takes the value of the objective function in the range with the objective function value of the initial feasible solution as the maximum value and the objective function value obtained as a result of the simplex operation processing as the minimum value List the combinations of the numbers, select the one whose objective function is close to the minimum value, and select the number of raw materials of which length to select and use for allocation to the constraint generation means A request is made to generate a second constraint condition expression Cx = d in which the product of the raw material use matrix C and the raw material use number vector x is equal to the raw material use scheduled quantity vector d, and the first constraint condition expression and the second Under the constraint conditions of the constraint condition expression and the third constraint condition expression, the simplex calculation means is requested to perform the calculation process, and the value of xi is either 0 or 1 by the simplex calculation process obtained thereafter, Except If the solution does not contain any material, the member allocation data is output with the solution as the optimal solution, otherwise the objective function is set to the minimum value from the listed combinations of the number of used raw materials. The next next candidate is selected, and the constraint condition generation unit is requested to generate a new second constraint condition expression Cx = d, and the simplex calculation unit is requested to perform calculation processing under the new constraint condition. A search control means for controlling to repeat the above operation, and when the xi takes a numerical value between 0 and 1 while satisfying the constraint expression, a function Σf () whose maximum value or minimum value is a constant value xi) is set as an evaluation expression, and when a plurality of non-integer solutions are obtained as a result of the pivot operation processing, a determination means is provided for comparing the relationship between these non-integer solutions by applying the evaluation expression, The control means If it is determined that the means satisfies a certain criterion, the pivot calculation process is continued. If it is determined that the criterion is not satisfied, the pivot calculation process is performed by changing the initial condition when starting the pivot calculation process. The member processing apparatus characterized by restarting.

<Configuration 8>
A member assignment program that causes a computer to function as each means described in Configuration 1.

<Configuration 9>
A computer-readable recording medium having recorded thereon a member assignment program that causes the computer to function as each means described in Configuration 1.

<Configuration 10>
A method that optimizes the combination of products assigned to each raw material by obtaining the number of each type of raw material required when cutting out m products each having a predetermined length from k kinds of raw materials each having a predetermined length. The product length setting means accepts the input of the product length data of the required m products, and the m-th order product length vector Lp with the product length as the element and the product with the required product quantity as the element A step of generating a requested quantity vector b and storing it in a storage device; and a raw material length setting means accepts input of raw material length data of k kinds of prepared lengths, and k-th order using the raw material length as an element Generating a raw material length vector Lm and storing the raw material length vector Lm in a storage device, and an allocation pattern vector generation means, wherein the product length data of the m products required and the raw material length of the k kinds of raw materials prepared Enumerating an m-th order allocation pattern vector indicating the relationship between raw materials and products that can economically allocate one or more products by comparing the data, and an allocation pattern matrix generating means, Generating an allocation pattern matrix A in which the allocation pattern vectors generated by the allocation pattern vector generation means are arranged and storing the allocation pattern matrix A in a storage device; and an objective function generation means includes n allocations included in the allocation pattern matrix. Each element for selecting a corresponding raw material by selecting a pattern defines a used number vector x of xi, and the sum of products of m-th order cost coefficient vector corresponding to the raw material length vector Lm and the used number vector x A step of generating an objective function to be stored and storing the objective function in a storage device; and the constraint condition generation means includes n allocations selected from the allocation pattern matrix A. Relaxation that the number of products cut out in the pattern must be equal to or greater than the quantity of each required product, and that each element xi of the constraint expression Ax ≧ b and the number vector x used is 0 ≦ xi ≦ 1 Generating the third constraint conditional expression and storing it in the storage device, a step in which the initial setting means receives the input of the initial executable solution obtained by an arbitrary method and stores it in the storage device, and simplex A calculation means that receives the initial executable solution, the objective function, and the constraint condition expression and executes simplex calculation processing; and a search control means that the value of xi is 0 or 0 by the simplex calculation processing. If the solution is one that does not include any other, the member assignment data is output with the solution as the optimal solution, and in other cases, The objective function value of the initial feasible solution is the maximum value, the objective function value obtained as a result of the simplex operation processing is the minimum value, and the combinations of the number of raw materials that take the objective function value in that range are listed. The step of selecting an objective function close to the minimum value from among them, and the search control means select how many raw materials of which length to the constraint condition generation means to use for allocation Requesting the generation of a second constraint condition Cx = d, wherein the product of the raw material use matrix C and the raw material use number vector x is equal to the raw material use scheduled quantity vector d, and the search control means, Under the constraint, the step of requesting the simplex arithmetic means to perform arithmetic processing, and the search control means determines whether the value of xi is 0 or 1 by the simplex arithmetic processing obtained thereafter. However, if the solution does not include any other ones, the member assignment data is output with the solution as the optimal solution, and in other cases, from among the combinations of the number of used raw materials listed above , The next candidate whose objective function is close to the minimum value is selected, and the constraint condition generation means is requested to generate a new second constraint condition expression Cx = d, and the first constraint condition expression and the A step of controlling to repeat the operation of requesting the simplex computing means to perform arithmetic processing under the constraint conditions of the second constraint condition expression and the third constraint condition expression; and a determination means, wherein the xi represents the constraint condition expression When taking a numerical value between 0 and 1 while satisfying, a function Σf (xi) whose maximum value or minimum value is a constant value is set in the evaluation formula, and a plurality of non-integer solutions are obtained as a result of the pivot operation processing. These non-integer solutions Comparing the relationship by applying the evaluation formula; and when the search control unit determines that the determination unit satisfies a certain determination criterion, the pivot calculation process is continued, and it is determined that the determination criterion is not satisfied. In such a case, the member assignment method includes a step of changing the initial condition when starting the pivot calculation process and restarting the pivot calculation process.

  Multiple non-integer solutions obtained by relaxing the constraints are evaluated using specific evaluation formulas.Thus, it is possible to avoid unnecessary repeated computations by hill-climbing, random restart, annealing, etc. It can be shortened.

1 is a block diagram of a member allocation system 10 according to a first embodiment. 2 is a hardware block diagram of a computer constituting the member allocation system 10. FIG. It is explanatory drawing for demonstrating the parameter of a calculation process. It is a first simplex operation processing flowchart. It is a flowchart of the arithmetic processing after the completion of the first simplex operation. It is explanatory drawing of a specific calculation example, (a) is explanatory drawing of the allocation pattern vector, (b) is explanatory drawing of the raw material use vector cj. It is explanatory drawing of the non-integer solution obtained by the simplex method arithmetic processing. It is explanatory drawing of the following non-integer solution obtained by the simplex method arithmetic processing. It is explanatory drawing of the integer solution obtained by the simplex method arithmetic processing. It is explanatory drawing of the meaning of an evaluation type | formula. It is a flowchart of the main operation | movement of this invention. It is explanatory drawing of a product, an allocation pattern vector, and a use number vector. It is a specific example explanatory drawing of a non-integer solution and an integer solution. It is a block diagram of a member processing apparatus.

  In the present invention, based on a practical solution obtained by an existing arbitrary method, it is evaluated by a simplex method to obtain a further improved solution. The simplex method is known as a method for searching for an optimal solution of a linear programming problem. However, if there are several tens of types of product lengths and raw materials required, the number of combinations may exceed several hundred thousand. The optimal value can be obtained by creating a parameter for arithmetic processing as it is based on the condition that any one of m types of products is assigned to n raw materials arbitrarily selected from k types of raw materials. There is a possibility that the simplex operation processing for the search takes too much time. Therefore, in the present invention, a constraint condition for the arithmetic processing by the simplex method is added to efficiently calculate while narrowing down the comparison target range. Then, when an executable solution is obtained in the process of pivot calculation processing by the simplex method, a future evaluation is made using a predetermined evaluation formula. The search condition is changed according to the result to avoid unnecessary calculation processing. Therefore, the calculation processing time for searching can be greatly shortened. Hereinafter, embodiments of the present invention will be described in detail for each example.

FIG. 1 is a block diagram of a member allocation system 10 according to the first embodiment.
The member assignment system 10 shown in the drawing is operated by a computer program installed in the computer 12. This system is used, for example, by a terminal device 16 connected to the computer 12 via the network 14. The terminal device 16 is provided, for example, in a precut factory that precuts building structural materials. The member assignment system 10 receives the condition data for precut from the terminal device 16, executes the calculation process, and returns the result. The terminal device 16 controls the precut device 17 using the returned member allocation data. As the pre-cut device 17, for example, a device as described in Patent Document 1 can be used.

  The computer 12 is provided with an arithmetic processing device 20 and a storage device 40. As shown in the figure, the arithmetic processing unit 20 includes a product length setting means 21, a raw material length setting means 22, an initial setting means 23, an allocation pattern vector generation means 24, an allocation pattern matrix generation means 25, a constraint condition generation means 26, a cost. Computer programs such as coefficient vector generation means 27, objective function generation means 28, simplex operation processing means 29, search control means 30, and determination means 31 are installed. These computer programs cooperate to execute arithmetic processing.

  The storage device 40 includes a product length vector Lp41, a product request quantity vector b42, a raw material length vector Lm43 (or a cost coefficient vector), an initial executable solution 44, a raw material use scheduled quantity vector d45, an allocation pattern matrix 46, as shown in the figure. , Raw material use matrix C47, first constraint condition formula 48, second constraint condition formula 49, third constraint condition formula 50, objective function 51, combination list 52, member allocation data 53, evaluation formula 54, and the like are stored. ing. These data are input from the outside in advance, or are generated by the operation of the computer program and stored in the storage device 40. Subsequently, the computer program and the data stored in the storage device 40 will be specifically described.

FIG. 2 is a hardware block diagram of a computer constituting the member assignment system 10.
Before describing specific functions of the member assignment system 10, the hardware of the member assignment system 10 will be described. As shown in the figure, an internal bus 110 housed in the main body case 3 of the computer 12 includes a CPU (Central Processing Unit) 111, a ROM (Read Only Memory) 112, a RAM (Random Access Memory) 113, and an HDD. A (hard disk) 114, an input / output interface 115, and a network interface 116 are connected. A display 3, a keyboard 4, and a mouse 5 are connected to the input / output interface 115. A terminal device 16 is connected to the network interface 116 via the network 14. The above hardware is the same as that provided in a generally well-known personal computer. The terminal device 16 supplies the member allocation data 53 (FIG. 1) to the member selection supply device 120 of the precut device 17. As a result, the specified raw material is supplied to the member cutting device 121 and cut with the specified allocation pattern. The cut product is conveyed and discharged by the product conveying device 122.

  The storage device 40 shown in FIG. 1 includes the ROM 112, RAM 113, and HDD 114 shown in FIG. The arithmetic processing unit 20 shown in FIG. 1 includes the CPU 111, the ROM 112, the RAM 113, and the like shown in FIG. Various data are mainly stored and stored in the HDD 114. A computer program executed by the CPU 111 is stored in the ROM 112 or loaded into the RAM 113 as appropriate. The terminal device 16 may have the same configuration. The network 14 may be the Internet or an intranet.

FIG. 3 is an explanatory diagram for explaining parameters of the arithmetic processing.
With reference to this figure, the definition of parameters used for arithmetic processing and the function of each computer program will be described.
[Product length vector Lp]
Let m be the quantity of products to be produced. In the illustrated example, m = 7.
The product length is expressed as Lp1, Lp2, ..., Lpm. The unit is, for example, m (meter).
An m-th order product length vector Lp (row vector) is defined as follows.
Lp = (Lp1, Lp2,…, Lpm)
However, (Lp1 ≧ Lp2 ≧… ≧ Lpm)
In the illustrated example, Lp = (Lp1, Lp2, Lp3, Lp4, Lp5, Lp6, Lp7).

[Product request quantity vector b]
When the production of a product of quantity m is requested, a product demand quantity vector b is defined as follows. In this embodiment, in order to simplify the calculation, description will be made assuming that bi = 1. In practice, bi may be any positive integer.
b = (b1, b2,..., bm) ^T
(The superscript T represents transposition. That is, b is a column vector. The same applies hereinafter.)
In the example of FIG. 3A, b = (1,1,1,1,1,1,1) ^T.
The product length setting means 21 accepts the input of the product length data of m required products, and the m-th order product length vector Lp41 having the product length as an element and the product request quantity having the product request quantity as an element. A vector b42 is generated and stored in the storage device 40.

[Raw material data]
The raw materials include k kinds of lengths. In the illustrated example, k = 3.
The raw material length is expressed as Lm1, Lm2, ..., Lmk. The unit is, for example, m (meter).
A kth-order raw material length vector Lm (row vector) is defined as follows.
Lm = (Lm1, Lm2, ..., Lmk)
However, (Lm1>Lm2>...> Lmk)
In the example of FIG. 3B, Lm = (Lm1, Lm2, Lm3).
The raw material length setting means 22 receives input of raw material length data of k types of prepared lengths, generates a k-th raw material length vector Lm43 having the raw material length as an element, and stores it in the storage device 40.

[Raw material use planned quantity vector d]
The raw material use scheduled quantity vector d45 (column vector) indicates how many materials each of k types of length are used for a feasible solution. This is defined as follows.
d = (d1, d2,..., dk) ^T
In the example of FIG. 3, d = (d1, d2, d3) ^T = (1, 2, 1) ^T. The raw material use scheduled quantity vector d45 is used in a third constraint condition expression described later.

[Number of used vectors x]
Any one of m types of products is allocated to n raw materials arbitrarily selected from k types of raw materials. At this time, an nth-order used number vector x representing the number of used n raw materials used is defined as follows. When n raw materials are selected from k types of raw materials, the same raw material may be selected twice or more.
x = (x1, x2,..., xn) ^T
In order to simplify the calculation, since all the elements of the product request quantity vector b are set to bi = 1, each element xi of the m-th order use number vector x becomes 0 ≦ xi ≦ 1, and as a result of the member assignment The case where xi is 0 or 1 is significant.

  Accordingly, when a plurality of the same raw materials are used, a raw material length vector Lm listing the same product lengths as many as necessary is used. For example, in the above specific example, the required products are assigned to the four raw materials listed as Lm1, Lm2, Lm2, and Lm3. At this time, x1 is set for the first Lm1, x2 for the second Lm2, x3 for the third Lm2, and x4 for the fourth Lm3. In the illustrated example, x1 = x2 = x3 = x4 = 1. When enumerating selected raw materials and unselected raw materials, the value of xi set to the selected raw materials is 1. The value of xi set to the raw material not selected is 0. The used number vector x is used in the constraint condition expression. This handling will be described more specifically in Example 3.

[Assignment pattern vector aj]
Data allocated so as to cut out one of the products of quantity m from any one raw material is represented by an m-th order allocation pattern vector aj (column vector). This is defined as follows.
aj = (a1, a2, ..., am) ^T
The allocation pattern vector in the example of FIG.
Allocate one Lp2 and one Lp6 to Lm1 (0,1,0,0,0,1,0) ^T
Allocate one Lp1 to Lm2 (1, 0, 0, 0, 0, 0, 0) ^T
Assign Lp3 and Lp5 to Lm2 (0, 0, 1, 0, 1, 0, 0) ^T
Assign Lp4 and Lp7 to Lm3 (0, 0, 0, 1, 0, 0, 1) ^T

The above allocation pattern vector aj is generated so as to satisfy the following expression.
Lp · aj≤L (j = 1, 2, ..., n)
The product (Lp · aj) on the left side of this equation is the sum of one product length or a plurality of product lengths assigned to the selected raw material. When generating the allocation pattern vector aj, a raw material having the minimum length Lmi that can be allocated this length is selected. L indicates the length Lmi of the selected raw material. In actual machining, the cutting length and blade thickness for taking out the rectangle are considered, but are ignored here.

For example, in the example of the figure, if one Lp3 and one Lp5 are allocated, it can be allocated to either the raw material Lm1 or Lm2. However, since Lm1> Lm2, the raw material is selected so that the assignment target is Lm2. In this way, find a relationship that can be allocated economically.
The example in the figure enumerates a set of allocation pattern vectors corresponding to feasible solutions. As preparation for obtaining an optimal solution by the simplex method, an allocation pattern vector is enumerated based on the result of the simplex operation processing as necessary.

  The allocation pattern vector generation means 24 economically allocates one or a plurality of products by comparing the product length data of m required products with the raw material length data of k kinds of prepared raw materials. An m-th order allocation pattern vector 46 a indicating the relationship between the raw material and the product that can be generated is generated and stored in the storage device 40.

[Assignment pattern matrix]
When allocating any of m types of products to n raw materials arbitrarily selected from k types of raw materials, n allocation pattern vectors are arranged. An m × n-order allocation pattern matrix in which n aj are arranged is defined below. This is shown in FIG.
A = (aij) (i = 1, 2,..., M, j = 1, 2,..., N)
The allocation pattern matrix generation unit 25 generates an m × n-order allocation pattern matrix in which n allocation pattern vectors 46 a generated by the allocation pattern vector generation unit 24 are arranged, and stores them in the storage device 40.

[First constraint]
The product of the allocation pattern matrix A and the used number vector x is the number of products cut out from the selected raw materials with the corresponding allocation pattern. Accordingly, the number of each product cut out from the raw material selected from the allocation pattern matrix A with the corresponding allocation pattern must be equal to or greater than the quantity of each required product. The required quantity of each product corresponds to the product request quantity vector b. Therefore, the required number of products cannot be obtained unless at least the following formula is satisfied.
Σaij · xj ≧ bi

When the inequality sign is established, it is overmade. For convenience of calculation, the above inequality is used as a constraint. This constraint condition expression is expressed as Ax ≧ b.
In the example of FIG. 3, the number of products produced and the number of required products are 7, and the equal sign is established.
The constraint condition generating means 26 generates a first constraint condition expression that the number of each product cut out from the raw material selected from the allocation pattern matrix A with the corresponding allocation pattern is equal to or greater than the number of each required product. Then, it is stored in the storage device 40.

[Raw material use matrix C]
A k-th-order raw material usage vector cj indicating which raw material to be used out of k kinds of raw materials is defined as follows. This is shown in FIG.
cj = (c1j, c2j,..., ckj) ^T
However, c1j, c2j,..., Ckj are all 0 or 1.
As described above, the raw material usage matrix C is used to represent n raw materials selected from k kinds of raw materials. This is defined by a k × n-order matrix in which n cj are arranged.
C = (cij) (i = 1, 2,..., K, j = 1, 2,..., N)

In the illustrated example, cij is as follows.
c1 = (1, 0, 0) ^T
c2 = (0,1,0) ^T
c3 = (0,1,0) ^T
c4 = (0,0,1) ^T
The allocation pattern matrix generation means 25 generates a k × n-order raw material usage matrix C that enumerates raw material usage vectors cj indicating which raw material of k types of raw materials is used in each allocation pattern, Store in a storage device.

[Second constraint]
Since cj is a vector that designates one of k kinds of raw materials, the following equation is satisfied.
Σcij = 1
Only one of the k numbers is 1 and all others are 0.
The length of each raw material is selected to be the minimum length that can be assigned.
ΣLmi · cij = L
This L is a value indicated by an allocation pattern vector generation condition Lp · aj ≦ L.

Further, as already defined, the used number vector x of n raw materials was x = (x1, x2,..., Xn). Further, the raw material use scheduled quantity vector d indicates the number of uses for each raw material length.
Therefore, the condition of the following formula must be satisfied.
.SIGMA.cij.xj = di (i = 1, 2,..., K)
This constraint condition expression is expressed as Cx = d.
This defines how many raw materials of which length are selected and used for actual allocation. The specific relationship between the constraints of Ax ≧ b and Cx = d will be described more clearly in the third embodiment.
The constraint condition generation unit 26 generates a second constraint condition expression that the product of the raw material use matrix C generated by the allocation pattern matrix generation unit 25 and the raw material use number vector x is equal to the raw material use scheduled quantity vector d. And store it in the storage device.

[Third constraint]
Each element xi of the used number vector x is 0 or 1. This is because it has a meaning to determine which one of the many allocation pattern vectors listed is to be selected. Therefore, a constraint condition expression such as the following expression is established.
xi∈ {0,1}
In this embodiment, this constraint condition is relaxed. That is, a constraint condition expression of 0 ≦ xi ≦ 1 is set.
The constraint condition generation means generates a third constraint condition expression indicating that each element xi of the used number vector x is 0 ≦ xi ≦ 1, and stores it in the storage device.

[Cost factor vector]
Not only the price but also the transportation cost, storage cost, processing fee, etc. differ for each raw material of different length. All cost elements to be included in the calculation are included in the nth-order cost coefficient vector f and defined as follows.
f = (f1, f2,..., fn)
Since the cost coefficient vector f is applied only to the selected n kinds of raw materials, it is an n-order vector. For convenience of calculation, f1, f2,..., Fn are converted into expenses, and the unit is a circle. Therefore, as the objective function value is smaller, a product can be obtained at a lower cost.

  If the price of the raw material is proportional to the length, it is agreed that the yield is the highest and the total cost is the lowest. However, if the price per unit length depends on the raw material length, the cost factor is adjusted. The cost coefficient vector generating means 27 generates an nth-order cost coefficient vector f including a price component in each element of the raw material length vector Lm. The element fi of the cost coefficient vector f is data whose unit is a circle. If the cost coefficient coefficient vector generation means 27 replaces the raw material length vector Lm with the cost coefficient vector f, the following processing can be performed without considering the cost coefficient vector f.

[Objective function]
In this calculation, any one of m types of products is assigned to n raw materials arbitrarily selected from k types of raw materials. At this time, a product can be obtained at a lower cost as the objective function value is smaller. Therefore, an objective function indicating the total cost for the n selected raw materials is defined as follows.
Min Σfi ・ xi
The objective function generation means 28 generates an objective function that indicates the total cost for the n selected raw materials, and stores it in the storage device.

[Use integer programming as a continuous relaxation problem]
In order to execute arithmetic processing by the simplex method, an objective function and constraint conditions are defined as follows.
Min Σfi ・ xi
subject to. Ax ≧ b
Cx = d
0≤xi≤1

The first expression is an objective function generated by the objective function generation means.
The second expression is a first constraint condition expression generated by the constraint condition generation means.
The third expression is a second constraint condition expression generated by the constraint condition generation means.
The fourth expression is a third constraint condition expression generated by the constraint condition generation means.
The objective function indicates the total cost of the n selected raw materials.
The first constraint condition expression shows the relationship among the allocation pattern matrix A, the used number vector x, and the product request quantity vector b.
The second constraint condition expression shows the relationship among the raw material use matrix C, the raw material use number vector x, and the raw material use scheduled quantity vector d.
The third constraint condition expression indicates that xi is 0 or more and 1 or less.

  The initial setting means 23 receives an arbitrary initial executable solution 44 acquired by an arbitrary method. Then, parameters for simplex operation processing are generated. Examples of the arbitrary method include a first fit method and a method described in Patent Document 1. The initial feasible solution can be represented by a used number vector x of raw materials that designates an allocation pattern vector selected from the above allocation pattern matrix A46. This will also be described more specifically in the third embodiment. Parameters input for the first simplex operation processing are data constituting the objective function Σfi · xi, the first constraint expression Ax ≧ b, and the third constraint expression 0 ≦ xi ≦ 1.

  The search control means 30 causes the simplex arithmetic processing means to input parameters excluding the constraint condition of Cx = d and execute the first arithmetic processing. The simplex operation processing means changes the basis variable of the simplex table so as to improve the value of the objective function and outputs a solution. The third constraint condition expression 0 ≦ xi ≦ 1 relaxes the constraint condition of xiε {0, 1}. Accordingly, the solution may include something other than an integer such as xi = 0.5. There may be a plurality of solutions having the same objective function value.

  The search control means 30 detects a solution in which the value of xi is either 0 or 1 and does not include anything other than the obtained solutions. When it is detected, the member assignment data 53 is generated with the solution as the optimum solution, and the process is terminated. In other cases, the search control means regenerates parameters for the next simplex operation process. First, the objective function value F0 of the feasible solution that has been initially set is set to the maximum value. This is because the goal is to improve the default solution. Further, the value F1 of the objective function of the solution obtained by the first simplex calculation process is set to the minimum value. Since the solution is obtained by relaxing the conditions, the objective function value at that time is determined as the limit value.

  Next, the search control means 30 enumerates combinations of the number of raw materials whose objective function values are F1 or more and less than F0, and generates a combination list. This corresponds to the raw material scheduled use quantity vector d. From this combination list, the one with the smallest objective function value is selected as the next candidate. Although a specific example will be described in the third embodiment, the constraint condition generation unit 26 generates the second constraint condition expression Cx = d. If there is a change in the parameters such as the objective function and the allocation pattern vector, the first constraint condition expression Ax ≧ b is also generated. Thereafter, the search control means 30 inputs the generated parameters to the simplex arithmetic processing means 29 to execute arithmetic processing. The third constraint condition expression 0 ≦ xi ≦ 1 is not changed.

  As a result, the obtained solution is detected when the value of xi is 0 or 1 and does not include any other value. When detected, the solution is determined as the optimum solution. In order to shorten the calculation time for the search process, control using an evaluation formula as will be described later is executed. When the optimum solution cannot be obtained, if the value of the objective function is the same as the next candidate in the list of combinations of the number of raw materials, it is selected as the next candidate. If not, the next smaller candidate is selected as the next candidate. Then, in the same manner as the previous time, the second constraint condition expression Cx = d is generated, the parameters are changed, and the generated parameters are input to the simplex calculation processing means to execute calculation processing.

  In this way, the simplex operation process is repeated to search for the optimum solution. When a large number of combinations of raw material combinations are generated, an upper limit is set for the number of combinations of raw material combinations, and if an optimal solution is not found even after searching a certain number of times, an initial executable solution is obtained. As an optimal solution, the member allocation data 53 may be output. In the above arithmetic processing, since the constraint condition indicating the relationship between the allocation pattern matrix A, the used number vector x, and the product request quantity vector b is used, the product length is not included in the parameters of the simplex arithmetic processing, and the calculation is complicated. Don't be. In addition, since the parameter is set so that the used number vector x of the raw material in which each element takes a value of only 0 or 1 becomes a basis variable, and simplex operation processing is executed under a relaxed constraint condition of 0 ≦ xi ≦ 1, Even when the optimum solution cannot be obtained, the search function can be limited by obtaining the minimum value of the objective function.

FIG. 4 is a flowchart of the first simplex operation processing operation.
An embodiment of a computer program for controlling the above system will be described with reference to these drawings.
In step S11, the raw material length setting means 22 accepts raw material data. The terminal device 16 receives input of all raw material length data to be used, generates data corresponding to the raw material length vector Lm43, and stores it in the storage device 40. In step S12, the product length setting means 21 accepts input of the product length and quantity. The input of the requested product length data is received from the terminal device 16, data corresponding to the product length vector Lp 41 and the product request quantity vector b 42 is generated and stored in the storage device 40.

  In step S13, the initial setting means 23 receives an input of the initial executable solution 44. The result is stored in the storage device 40. In step S14, the allocation pattern vector generation means 24 compares the product length vector Lp41, the raw material length vector Lm43, etc., and generates an allocation pattern vector. The allocation pattern vector is stored in the storage device 40. Subsequently, in step S <b> 15, the allocation pattern matrix generation unit 25 generates the allocation pattern matrix 46 and stores it in the storage device 40. Next, in step S <b> 16, the constraint condition generation unit 26 generates a first constraint condition expression 48, a second constraint condition expression 49, and a third constraint condition expression 50 and stores them in the storage device 40.

  In step S17, the cost coefficient vector generation means 27 generates a cost coefficient vector, and in step S18, the objective function generation means 28 sets the objective function 51 using the cost coefficient vector. The result is stored in the storage device 40. Next, the search control means 30 inputs the first calculation parameter to the simplex calculation processing means 29 in step S19 as described later. In step S20, a simplex operation using this operation parameter is executed. When the solution is obtained, the search control means 30 determines whether or not it is an integer solution in step S21. If the result of this determination is yes, it is an optimal solution, so that member assignment data is output in step S23 and the process is terminated. If no, the process proceeds to step S22. In step S22, the search control means 30 controls the calculation by the simplex method according to the procedure shown in FIG.

FIG. 5 is a flowchart of the calculation process after the completion of the first simplex calculation.
The operation of this flowchart is controlled by the search control means 30 and executed by the simplex operation processing means 29. First, in step S31, the maximum value of the objective function is set from the initial executable solution. Next, in step S32, the minimum value of the objective function is set from the calculation processing result in step S20 of FIG. In step S33, a raw material combination list is generated within the set objective function range. The results are stored in the storage device 40 by arranging them in ascending order of the objective function. In step S34, the one with the smallest objective function value is selected from the combination list. Further, in step S35, a request is made to the constraint condition generation means 26, and a constraint condition is set as will be described later.

  In step S36, the objective function generation unit 28 is requested to set the objective function. In step S37, a simplex operation is executed. In step S38, the search control means 30 determines whether an integer solution has been obtained. If the result of this determination is yes, this process ends, and the process proceeds to step S23 in FIG. On the other hand, if no, the process proceeds to step S39. In step S39, it is determined whether the pivot calculation process has been repeated W times set in advance. W times is an upper limit value. As a result, if a solution is not obtained even after a long search, the process is stopped. That is, in step S40, the initial executable solution is output as a calculation processing result. If the number of repetitions is less than W times, the process returns to step S34, the combination list having the next largest objective function value is selected, and the simplex operation process is executed again. Through the above processing, the computer program automatically searches for an optimal solution. In the present invention, special control as described later is performed for the search operation in step S37.

6 to 11 are explanatory diagrams of specific calculation examples described in Patent Document 2. FIG.
(Raw material data)
For example, there are five kinds of prepared raw materials. The length is as follows. The unit of length is 0.1 mm (millimeter).
Lm1 = 60000
Lm2 = 49000
Lm3 = 45000
Lm4 = 40000
Lm5 = 30000
(Product length data)
Seven products are required, and the length is as follows. The unit of length is 0.1 mm (millimeter).
Lp1 = 53050
Lp2 = 44350
Lp3 = 30700
Lp4 = 26250
Lp5 = 21050
Lp6 = 17840
Lp7 = 17150

(Assignment pattern vector)
FIG. 6A is an explanatory diagram of an allocation pattern vector.
The above seven types of product lengths are listed in one vertical column from the top to the bottom on the left side of the figure. In addition, the raw material lengths are listed in one horizontal row from the left to the right at the top. A vertical line below each raw material length is an assigned pattern vector. For example, one having a product length of 44350 can be assigned to one having a raw material length of 45000. For example, one with a product length of 30700 and 17840 can be assigned to one with a raw material length of 49000. This table compares the product length data of seven products with the raw material length data of five types of raw materials in this way, and the raw materials and products that can economically allocate one or more products. 7th order allocation pattern vectors indicating the relationship with Here, x1 to x5 are allocation pattern vectors obtained from the initial executable solution, and x6 to x18 are allocation pattern vectors additionally generated based on the result of the first simplex operation process.

  x1 to x18 are each element of the used number vector x of the raw material. Whether or not the raw material of the length displayed on the lower side is used in the corresponding allocation pattern is indicated by a numerical value of 0 or 1. When the value of x1 to x18 is 0, the raw material is not used, and when it is 1, it is used. Which of the listed allocation pattern vectors is to be selected is displayed based on the used number vector x of raw materials.

(Objective function)
In order to simplify the explanation, each element of the cost coefficient vector f is matched with the raw material length. That is, the numerical value of length is read as a circle as it is.
The 18 numerical values on the right side of the raw material length in FIG. 6A are elements of the cost coefficient vector f. Therefore, the value of the objective function Σ (fi · xi) of the executable solution that is input as the initial value in the first simplex calculation process is 233000 as the sum of the used raw material lengths of x1 to x5. In the following calculation, a solution that improves this is obtained, so the upper limit value of the objective function is set to 233000.

(Raw material usage matrix C)
FIG. 6B shows raw material use vectors cj corresponding to the respective assigned pattern vectors in FIG. The raw material used when the allocation pattern vector of x1-x18 is selected is shown. Accordingly, the product of the raw material usage vector cj and the raw material usage number vector x indicates a breakdown of the number of raw materials used for each raw material length.

7 and 8 are explanatory diagrams of the non-integer solution obtained by the simplex method arithmetic processing which will be described in detail later.
In the tables of FIG. 7 and FIG. 8, the display of the allocation pattern vector having a solution value of 0 is excluded. That is, FIG. 7 shows a solution that x4 = x1 = x16 = 1, x12 = x9 = x3 = 0.5, and the others are zero. FIG. 8 shows a solution that x4 = x1 = 1, x2 = x9 = x10 = x16 = x3 = 0.5, and the others are zero. For example, in the example of FIG. 7, when one raw material length is 60000, 45000, 49000 each and 0.5 raw material length is 40000, 49000, 45000 each, an objective function value is 221000. Results were obtained. Certainly, the objective function value is smaller than the initial value. However, since the constraint condition of xi ∈ {0, 1} was relaxed so that 0 ≦ xi ≦ 1, an infeasible solution of xi = 0.5 was obtained.

  In the present invention, the objective function value when the above solution is obtained is set to the lower limit value of the optimum value. That is, since the objective is to improve the initial feasible solution, the initial value of the objective function value is set to the maximum value 233000, and the objective function value 221000 obtained by the first simplex operation processing is set to the minimum value. Assuming that there is an optimum value in this range, the search is performed again. Here, the case where the objective function value becomes a value smaller than 221000 or more and 233000 by combining an arbitrary number of raw materials is listed. For example, calculation results to be aggregated while selecting combinations may be sorted in ascending order.

  It is not necessary to enumerate all the combinations. While enumerating in order from the sum of the raw material lengths, that is, from the smallest objective function value, the second and subsequent simplex operations are executed, and an executable solution, that is, an optimal solution is obtained. If it is obtained, the process may be terminated. Therefore, for example, no. 1-No. By enumerating combinations up to the 10th place and performing a simplex operation process with a sufficiently narrow search range, the operation processing time can be shortened. This is illustrated in FIG.

FIG. 9 is an explanatory diagram showing an example of the integer solution finally obtained.
FIG. 1-No. An example of 10 combinations and objective function values is shown. FIG. 9B shows an example of the obtained integer solution.
No. 1, the raw material length 49000 is 3 pieces, 45000 is 1 piece, and 30000 is 1 piece. No. 2, the raw material length 49000 is 2 pieces, 45000 is 1 piece, and 40000 is 2 pieces. No. 3, the raw material length 49000 is one, 45000 is one, 40000 is one, and 30000 is three. No. 4, all the raw material lengths 60000 to 30000 are combined into one. There are 30 or more combinations up to the maximum value. First, the search calculation processing is started by listing up to this point.

  No. 1-3 and No.1. In the combination of 5, since the maximum value of the raw material length to be used is 49000, a product having a product length of 53050 cannot be clearly obtained. These are excluded from the calculation target. The above arithmetic processing is repeated for other combinations. As a result, the No. of the combination of the number of raw materials. 4, an integer solution was obtained in which the base variables xi of the simplex table were all 0 or 1. If one material having a raw material length of 6000.4000.0.4500.0.30.40.49000 is selected, all the products to be cut out can be assigned to each. Thereby, the sum total of raw material length becomes 224000. Since the sum of the raw material lengths of the initial feasible solution was 233,000, it was possible to find an allocation pattern that can save raw materials by 9000. Data indicating the listed combinations is output as member assignment data and transmitted to the terminal device.

(Simplex processing)
Hereinafter, the process of simplex operation processing will be described more specifically.
First, a method for determining the maximum value and the minimum value of the objective function value of the initial feasible solution will be described.
First, an initial executable solution obtained by any known method is set in the simplex arithmetic processing means 29. This is, for example, the following arrangement. The unit is 0.1 mm (millimeter). This is the same as that described in FIG.

The product 44350 is taken from the raw material length 45000.
Take products 30700 and 17840 from raw material length 49000.
Products 26250 and 21050 are taken from the raw material length 49000.
Take product 53050 from raw material length 60000.
Take product 17150 from raw material length 30000.

The simplex arithmetic processing means 29 is set with an initial value as shown in FIG.
fi (f1 to f5) is a raw material length in which five pieces are arranged in the horizontal direction of the uppermost stage.
x1 to x5 are all “1”.
In the left column, seven types of product lengths are arranged in order from the longest.
The numerical value of 7 rows and 5 columns (all 1 or 0) on the right side is the allocation pattern matrix A.

Here, the objective function is Σfi · xi, the constraint conditions are set as (Ax ≧ b) and 0 ≦ xi ≦ 1, and the simplex arithmetic processing means 29 is activated.
The simplex arithmetic processing means 29 operates so as to obtain an executable solution that satisfies the conditions. Since the initial setting is a feasible solution, the initial solution must be output according to the initial setting.
The solution of this arithmetic processing is x = (1,1,1,1,1) ^T
It is.
That is, (x1, x2, x3, x4, x5) ^T
= (1,1,1,1,1) ^T
It is.
The objective function value is 233000. It is a value obtained by tabulating the initial values fi.
This is the maximum value of the objective function. If no other feasible solution is found, the default value is the optimal value.
This calculation process is performed to obtain a simplex multiplier π. This is a preliminary process.

  Based on this simplex multiplier, an allocation pattern vector group that can improve the initial solution can be selected. That is, there are many possible allocation pattern vectors, but in this process, only allocation pattern vectors that can improve the initial solution can be added. The improvement of the initial solution means that the value of the objective function Σfi · xi can be made smaller.

As a result, 13 types of allocation pattern vectors can be added. For example, the tenth allocation pattern vector is the lower vertical column (0000101) ^{T in} FIG. 6 labeled x10 and raw material length 4000.
It is. As a result, a new 7 × 18 allocation pattern matrix A is set in the simplex operation processing means 29.

This time, the objective function is Σfi · xi, the constraint condition is (Ax ≧ b), and xi is relaxed so that 0 ≦ xi ≦ 1, and the simplex arithmetic processing means 29 is activated.
The simplex operation processing means 29 selects one of the allocation patterns from the allocation pattern matrix A by pivot calculation processing, and obtains a solution that satisfies the above-described condition, that is, an executable solution. Since the condition of xi has been relaxed, a feasible solution containing a value of xi of 0.5 is obtained. A solution in which xi is an integer of 0 or 1 is called an integer solution, and a solution in which any xi is neither 0 nor 1 is called a non-integer solution.

The simplex operation processing means 29 performs a pivot operation process so as to reduce the value of the objective function Σfi · xi. Then, an executable solution is obtained and the result is output. If an integer solution is obtained with the output feasible solution, it is an optimal value. Accordingly, the calculation process is terminated without proceeding to the subsequent processes.
On the other hand, when a non-integer solution is obtained with the output executable solution, the value of the objective function Σfi · xi at that time is used for the next calculation process. That is, in the example of FIG. 7, the solution at this time is to use 0.5 raw material lengths of 40000, 49000, and 45000, respectively, and the value of the objective function Σfi · xi is 221000. This is the lower limit. The result is as shown in FIG. Thus, the maximum value and the minimum value of the objective function value can be obtained.

In the above arithmetic processing, it was possible to search between the maximum value 233000 and the minimum value 221000 of the value of the objective function and obtain the optimum value. Therefore, a combination of raw materials included in this range is obtained. The condition of the following formula should be satisfied.
221000 ≦ Σfi · xi <233000
Since the smaller Σfi · xi is, the better. Therefore, the order of the total sum of the lengths of the combined raw materials is given. Then, the next arithmetic processing is executed in this order. Japanese Patent Application Laid-Open No. 2004-228561 has shown a technique for reducing the calculation processing time by narrowing the search range in this way.

Next, the objective function is Σfi · xi, the constraint condition is (Ax ≧ b), xi is 0 ≦ xi ≦ 1, and the constraint condition that the combination of raw materials is constant (Cx = d) is added, The simplex operation processing means 29 is activated. The allocation pattern matrix C has 7 rows and 18 columns as in the previous case. For example, the calculation process starts when the total length of the raw materials is 222000 at first. The combination of raw materials at this time is 0 for 60000, 3 for 49000, 1 for 45000, 0 for 40000, and 1 for 30000.
d is (0, 3, 1, 0, 1) ^T in 5 rows and 1 column.
It becomes the contents.

  In this example, since there is no combination of raw materials that is equal to the minimum value 221000 of the objective function, the calculation process starts when the total length of the raw materials is 222000. The simplex operation processing means 29 obtains an executable solution satisfying the constraint condition from 18 types of allocation pattern vectors.

(Evaluation formula)
Actually, for example, when there are 38 types of products, one for each type and three types of raw material lengths, the number of allocation pattern vectors is 526. Even if there is only one kind of raw material length, if there are 200 kinds of products, the number of allocation pattern vectors is 4247. In such a case, when the arithmetic processing by the simplex arithmetic processing means 29 is executed under the above-mentioned conditions, processing for obtaining an executable solution is performed by repeating the pivot operation several thousand times or several hundred thousand times.

  In order to cut out one product, the most economical raw material length is uniquely determined. The most economical raw material length is uniquely determined to cut out a plurality of products in combination. What is necessary is just to obtain | require the most economical raw material length which satisfy | fills the formula of Lp * aj <= L already demonstrated. That is, if the raw material length and the product length are determined, the allocation pattern vector in all cases can be automatically generated. There is no overlap in the combination of raw material length and allocation pattern vector. The simplex operation processing means 29 searches the combination pattern of the allocation pattern vectors satisfying the constraint conditions in a brute force manner while avoiding duplication. Therefore, if the number of allocation pattern vectors can be reduced to the minimum, the calculation processing time can be shortened. On the other hand, for example, as will be described later, the number of allocation pattern vectors may be narrowed based on a simplex multiplier.

  The simplex operation processing means 29 searches for combinations of allocation pattern vectors that satisfy the constraint conditions by a pivot operation using a known simplex tableau. Given the constraint that the combination of raw materials to be used is constant, the simplex operation processing means 29 finds an executable solution in which the value of x satisfies the constraint condition while gradually changing the combination of the allocation pattern vectors. There is no regularity in the order of appearance of non-integer solutions obtained in the process of this pivot operation. If the initial conditions at the start of the pivot operation are different, the pivot operation is executed in a completely different process, and the appearance order of the non-integer solutions also changes. There is no way to find the optimal initial condition to reach an integer solution in the shortest time. If you are unlucky, you may not be able to get an integer solution by repeating the pivot operation tens of thousands of times.

  A plurality of non-integer solutions may be obtained before an integer solution is obtained. Even if a large number of non-integer solutions are obtained, an integer solution may not be obtained until the end. If an integer solution is not obtained until the end, it means that there is no optimal solution for the combination of raw materials for which conditions are set. In Example 2, the search was terminated when the number of repetitions of the pivot operation reached W times, and another combination of raw materials was selected. However, the search strategy can be determined by monitoring the relative cost factor obtained from the simplex tableau when the non-integer solution is output. When the relative cost coefficients are all positive, it may be determined that there are no more feasible solutions. Further, if at least one relative cost coefficient includes 0 (zero), it can be determined that there are other feasible solutions. Therefore, the search should continue. When the above-described executable solution is output, it may be determined that the arithmetic processing has been completed in all cases.

  However, if the number of allocation pattern vectors is large or the number of combinations of raw materials is large, the computation processing time by the simplex computation processing means 29 may become enormous. Therefore, in the present invention, when a plurality of non-integer solutions are obtained, the result of the subsequent arithmetic processing is predicted using an evaluation formula defined below. That is, when a plurality of non-integer solutions are obtained as a result of the pivot operation processing, these non-integer solutions are compared by applying a specific evaluation formula, and if a certain criterion is satisfied, the pivot operation processing is continued. To do. If the determination criterion is not satisfied, the initial condition when starting the pivot calculation process is changed and the pivot calculation process is restarted. Alternatively, the arithmetic processing under the same constraint condition is stopped, and another raw material combination is set as the constraint condition.

  The evaluation formula 54 shown in FIG. 1 is data defined as Σf (xi). Σf (xi) is a function that has a constant maximum value when xi takes a numerical value between 0 and 1 while satisfying the constraint condition. For example, f (xi) can be defined as xi to the nth power (n> 1). Alternatively, Σf (xi) is a function whose minimum value is a constant value when xi takes a numerical value between 0 and 1 while satisfying the constraint condition. For example, f (xi) can be defined as sin πxi, or f (xi) can be defined as xi to the nth power (0 <n <1).

FIG. 10 is an explanatory diagram of the meaning of the evaluation formula.
The meaning of the evaluation expression will be described by defining f (xi) as the square of xi. This evaluation formula is for observing a change in the value of the element xi of the used number vector x of raw materials when a plurality of non-integer solutions are obtained. That is, it can be determined whether the pivot calculation is proceeding in a direction in which all xi included in each solution approach an integer. In general, the theory is as follows.

  For example, the number used is x = (x1, x2). Also, the raw material combination C is (1, 1). The former is a column vector and the latter is a row vector. Since (Cx = d), x1 + x2 = 1. In this case, as shown in FIG. 10A, on the orthogonal coordinates of the x1 axis and the x2 axis, the feasible solution is on a straight line where the coordinate of the x1 axis cut edge is 1 and the coordinate of the x2 axis cut edge is 1. It can be said that there is. The white circles at both ends of the line are integer solutions, and the central black circle is a non-integer solution. In (b), the value of the evaluation formula is shown on the vertical axis, and the values of x1 and x2 are shown on the horizontal axis.

  FIG. 10B shows a solution space when the elements of the number vector x used are x1 and x2. The maximum value of the evaluation formula is 1, and the minimum value is 0.5. As the number of elements of the vector x increases, the solution space becomes more complicated than this figure. In addition, the output order of non-integer solutions and integer solutions obtained by pivot calculation is also complicated. Therefore, the value of the evaluation formula of the integer solution or the non-integer solution obtained by the executable solution that is sequentially output after starting the pivot operation under a certain condition changes as shown in FIG. Black circles are based on non-integer solutions, and white circles are based on integer solutions.

  Here, for example, it is assumed that the arithmetic processing by the simplex arithmetic processing means 29 is started and the executable solution R1 is obtained at a predetermined timing. After that, it is assumed that an executable solution R2 is obtained. Both are non-integer solutions. Comparing the values of both evaluation formulas, the value of the non-integer solution obtained later decreases. Even if the pivot calculation is further continued here, the value of the evaluation formula decreases, and it is determined that the integer solution is not immediately approached. Therefore, the initial condition is changed at this timing. That is, the starting point of the pivot calculation is changed.

  In this calculation processing, the objective function is Σfi · xi, the constraint condition is (Ax ≧ b), xi is 0 ≦ xi ≦ 1, and the constraint condition that the combination of raw materials is constant (Cx = d) is added. Then, the simplex operation processing means 29 was activated. Allocation pattern vectors and constraints cannot be changed. On the other hand, in the method of the present invention, the cost factor value is not included in the constraint condition (Cx = d), and the number vector x is used for the basis variable, so the value of the cost factor fi is changed. There is no direct effect on the solution. In addition, if the value of the cost coefficient fi included in the objective function is changed, the starting point and order of the pivot calculation can be changed. For example, even if the calculation process is started with all the values of the cost coefficient fi set to 0, or the calculation process is started with all the values of the cost coefficient fi set to 1, the same result is finally obtained. . However, the pivoting process is different. That is, by changing the changeable setting conditions for the simplex calculation processing means 29, the pivot calculation is stopped when the executable solution R2 of FIG. 10C is obtained, and this time from the timing t1. It may be possible to resume the pivot operation. Of course, it suffices if the initial condition for starting the pivot calculation can be changed by any other method.

  When the pivot calculation is resumed from the timing t1, an executable solution R3 is obtained thereafter. After that, it is assumed that an executable solution R4 is obtained. Both are non-integer solutions. Here, when the value of both evaluation formulas is compared, the value increases. At this time, if the pivot calculation is further continued, the value of the evaluation formula increases and it is determined that there is a high possibility of approaching the integer solution. Such a determination is performed by the determination unit 31 shown in FIG. In the example of FIG. 10C, the integer solution indicated by the white circle can be safely reached thereafter.

  However, in practice, even if the arithmetic processing is continued under the same setting conditions, an integer solution is not always obtained. Therefore, for example, if the value of the evaluation formula increases and then begins to decrease without obtaining an integer solution, it is determined that the maximum value has been passed, and another setting curve is obtained to change the setting condition. For example, the pivot calculation may be repeated by sequentially switching the value of the cost coefficient fi from the state of all 0 to the state of all 1.

  When multiple non-integer solutions are obtained by the above processing, if it is determined that it is not possible to continue the pivot operation after that, the state is avoided and the pivot operation is started from another condition. In this way, the calculation processing time can be shortened. Further, for example, when the tendency of the value of the evaluation formula does not increase even when the initial condition is changed, it is determined that there is no integer solution under this constraint condition, and the constraint condition (Cx = It is preferable to change d) and restart the arithmetic processing.

  Continuing the pivot calculation only when the value of the evaluation formula increases can be called a hill-climbing method in the known local search method. And changing the initial condition at random can be called a random restart method. Furthermore, an integer solution can be searched by a known annealing method using the above evaluation formula. It is also effective to continue the pivot operation when the value of the evaluation formula once decreases and then increases when it is a non-integer solution and passes the local optimal solution. With the determination criteria as described above, the determination means 31 shown in FIG. 1 determines whether or not to continue the pivot calculation. The search control means 30 shown in FIG. 1 controls the search according to the determination by the determination means.

(Operation flow)
FIG. 11 is a flowchart of the main operation of the present invention.
A specific procedure of arithmetic processing using the evaluation formula will be described with reference to FIG. First, in step S51 in the figure, a combination of the number of raw materials is selected. Next, in step S52, a constraint condition is set using the above constraint equation. In step S53, initial conditions are set. This initial condition is a condition at the start of the pivot calculation. For example, all the cost coefficients are set to zero. In step S54, simplex operation processing is started. In step S55, a pivot calculation is executed. The pivot calculation is repeated, and an executable solution is output in step S56. In step S57, it is determined whether it is an integer solution. If the result of this determination is yes, the process ends because it is the optimal solution. If no, the process proceeds to step S58.

  In step S58, it is determined whether or not the pivot calculation is finished. This is a case where it is determined that there is no feasible solution as already described. If the result of this determination is yes, the process proceeds to the first step S51, and the constraint conditions are reset. If no, the process proceeds to step S59. In step S59, arithmetic processing for applying the non-integer solution to the evaluation formula is performed. The determination means 31 (FIG. 1) performs the calculation of steps S59-61. In step S60, determination is made by comparing the history of the values of the evaluation formula. That is, for example, for the previous non-integer solution, the value of the calculated evaluation formula is stored in the storage device and compared with the current one. Also, for the non-integer solution obtained several times in succession, the value of the calculated evaluation formula is stored in the storage device and compared with the current one. In step S61, it is determined whether or not to continue the pivot calculation using the determination criterion as described above. If the result of this determination is yes, the process proceeds to step S56, and steps S56 to 61 are repeated. On the other hand, when the answer is no, the process proceeds to step S62, and the cost coefficient is changed. Then, the process returns to step S54. That is, the pivot calculation is resumed under new initial conditions.

FIG. 12 is an explanatory diagram showing the relationship between the allocation pattern vector and the used number vector when the pivot calculation is repeated 155 times. FIG. 13 is an explanatory diagram of specific examples of non-integer solutions and integer solutions in the process.
The pivot operation by the simplex arithmetic processing means 29 was repeated 155 times from the beginning to obtain the first feasible solution in the figure.
The non-integer solution is such that the material of the allocation pattern of x27 is one, the material of the allocation pattern of x17 is 0.5, the material of the allocation pattern of x88 is 0.5, and so on.
Here, Σf (xi) is calculated. The number vector used includes 16 for 1 and 12 for 0.5. Therefore, Σf (xi) is 19.
Further, when the pivot operation by the simplex arithmetic processing means 29 was repeated, a new executable solution was obtained for the 157th time counting from the beginning. Non-integer solutions were obtained both in the 155th and 156th times, but the value according to the evaluation formula continued to increase. Therefore, the pivot calculation is continued according to the determination by the determination means.

  On the other hand, when the type of raw material is one and the type of product is 200, 4247 types of allocation pattern vectors are generated. Similarly, when simplex operation processing was executed, 1783 pivot operations were performed until the first executable solution was obtained. When the pivot calculation was continued without using the evaluation formula, an integer solution could not be obtained even if the pivot calculation was performed up to 443183 times. On the other hand, when a search was executed using the above evaluation formula, an integer solution could be obtained by performing a pivot operation up to 94808 times. That is, it has been found that the processing time can be sufficiently shortened by the method of the present invention.

FIG. 14 is a block diagram of the member processing apparatus.
The member assignment data 53 was obtained by the above processing. This is supplied to the precut device 17 at the precut factory. The raw materials are selected in the order shown in FIG. 14 and cut according to the corresponding assignment pattern to obtain a product. In this example, the yield in the case of the initial feasible solution was 0.903, but became 0.939 after the improvement. In a pre-cut factory that allocates a large amount of product to a large amount of raw materials and cuts it, a cost reduction can be achieved by simply improving the yield by about 1%. In addition, if the amount of waste can be reduced by 1%, facilities and costs for waste disposal can be saved. In the above example, the types of raw materials and the types and quantities of products required are simplified. However, if a wide variety of raw materials and products are handled, it is expected that the yield will be significantly improved to a level that could not be achieved by the conventional method. be able to.

  In order to obtain the minimum value of the total sum of the raw material lengths used, first, simplex operation processing was executed under the constraints of the first constraint equation and the third constraint equation. At this time, if a feasible solution with a non-integer solution was obtained, the objective function value at that time was set to the minimum value of the total sum of the raw material lengths used. However, as described above, a non-integer solution may be obtained multiple times under the same constraints. Therefore, there is a possibility that another new non-integer solution may be obtained, and it is preferable to repeat the simplex operation processing under the constraint conditions as long as there is a combination that equals the objective function value by combining the number of raw materials. .

  The computer program executed by the above arithmetic processing unit may be modularized in units shown in functional blocks, or may be integrated by combining a plurality of functional blocks. Further, the above computer program may be used by being incorporated into an existing application program. The computer program for realizing the present invention can be recorded on a computer-readable recording medium such as a CD-ROM and installed in any information processing apparatus for use.

DESCRIPTION OF SYMBOLS 10 Member allocation system 12 Computer 14 Network 16 Terminal apparatus 20 Processing unit 21 Product length setting means 22 Raw material length setting means 23 Initial setting means 24 Allocation pattern vector generation means 25 Allocation pattern matrix generation means 26 Constraint condition generation means 27 Cost counting coefficient Vector generation means 28 Objective function generation means 29 Simplex operation processing means 30 Search control means 31 Determination means 40 Storage device 41 Product length vector Lp
42 Product requirement quantity vector b
43 Raw material length vector Lm
44 Initial feasible solution 45 Raw material use planned quantity vector d
46 Allocation pattern matrix 46a Allocation pattern vector 47 Raw material use matrix C
48 First constraint equation 49 Second constraint equation 50 Third constraint equation 51 Objective function 52 Combination list 53 Member assignment data 54 Evaluation equation

Claims (10)

The number of each type of raw material required when each of m products of a predetermined length is cut out from k types of raw materials of a predetermined length, and the combination of products assigned to each raw material is optimized. There,
Accepting the input of product length data of m required products, and generating an m-th order product length vector Lp having the product length as an element and a product request quantity vector b having the product request quantity as an element Product length setting means for storing in the storage device;
A raw material length setting means that receives input of raw material length data of k types of prepared lengths, generates a k-th order raw material length vector Lm having the raw material length as an element, and stores it in a storage device;
The raw material and product which can economically allocate one or a plurality of products by comparing the product length data of the required m products with the raw material length data of the k kinds of raw materials prepared An allocation pattern vector generation means for enumerating m-th order allocation pattern vectors,
An allocation pattern matrix generation unit that generates an allocation pattern matrix A in which the allocation pattern vectors generated by the allocation pattern vector generation unit are arranged and stores the allocation pattern matrix A in a storage device;
An m-th order cost coefficient vector corresponding to the raw material length vector Lm, wherein each element for selecting a corresponding raw material by selecting from the n allocation patterns included in the allocation pattern matrix defines a number vector x of x i And an objective function generating means for generating an objective function indicating a sum of products of the used number vectors x and storing the objective function in a storage device;
The first constraint condition expression Ax ≧ b and the number-of-uses vector in which the number of each product cut out with the n number of allocation patterns selected from the allocation pattern matrix A must be equal to or greater than the quantity of each required product. a constraint condition generating means for generating a relaxed third constraint condition expression that each element x i of x is 0 ≦ xi ≦ 1, and storing it in the storage device;
Initial setting means for receiving an input of an initial executable solution obtained by an arbitrary method and storing it in a storage device;
Simplex operation means for receiving input of the initial executable solution, the objective function, and the constraint condition expression, and executing simplex operation processing;
If the simplex operation process results in a solution where the value of xi is either 0 or 1 and does not include any other value, the member assignment data is output with the solution as the optimal solution, otherwise Is a combination of the number of raw materials used that takes the objective function value of the initial feasible solution as a maximum value, the objective function value obtained as a result of the simplex operation processing as a minimum value, and takes the objective function value in that range. Are selected from among them, and the number of raw materials of which length is selected and used for allocation is selected for the constraint condition generation means. A request is made to generate a second constraint condition expression Cx = d, where the product of the use matrix C and the raw material use number vector x is equal to the raw material use scheduled quantity vector d, and the first constraint condition expression and the second constraint condition expression are requested. And the third Under the constraint condition of the constraint condition expression, the simplex operation means is requested to perform the arithmetic processing, and the simplex arithmetic processing obtained thereafter results in a solution where the value of xi is either 0 or 1 and does not include any other In this case, the member allocation data is output with the solution as an optimal solution, and in other cases, the next candidate whose objective function is close to the minimum value is selected from the listed combinations of the number of raw materials used. Select and request the constraint condition generation means to generate a new second constraint condition expression Cx = d, and repeat the operation of requesting the simplex operation means to perform arithmetic processing under this new constraint condition. Search control means for controlling,
When the xi takes a numerical value between 0 and 1 while satisfying the constraint expression, a function Σf (xi) whose maximum value or minimum value is a constant value is set as an evaluation expression, and the pivot calculation process When a plurality of non-integer solutions are obtained as a result, a determination unit that compares the relationship between these non-integer solutions by applying the evaluation formula is provided,
The search control means continues the pivot calculation process when it is determined that the determination means satisfies a certain determination criterion, and the initial time when the pivot calculation process is started when it is determined that the determination criterion is not satisfied. A member assignment system characterized by changing the conditions and restarting the pivot calculation process. In the member allocation system according to claim 1,
The determination means is a function in which the xi takes a numerical value between 0 and 1 while satisfying the constraint condition, and the maximum value of the evaluation formula Σf (xi) is a constant value.
If the value of the evaluation formula based on the non-integer solution obtained later is larger than the value of the evaluation formula based on the non-integer solution obtained earlier, it is determined that the criterion is satisfied. Member allocation system. In the member allocation system according to claim 1,
The determination means is a function in which the xi takes a numerical value between 0 and 1 while satisfying the constraint condition, and the minimum value of the evaluation formula Σf (xi) is a constant value.
If the value of the evaluation formula based on the non-integer solution obtained later is smaller than the value of the evaluation formula based on the non-integer solution obtained earlier, it is determined that the criterion is satisfied. Member allocation system. In the member allocation system according to claim 1,
A member assignment system, characterized in that the evaluation formula values obtained by successively obtained non-integer solutions are determined according to a criterion for comparison using an annealing method. In the member allocation system according to claim 1,
A member allocation system characterized in that, when a non-integer solution passes a local optimal solution, it is determined that the criterion is satisfied when the value of the evaluation formula once decreases and then increases. In the member allocation system in any one of Claims 1 thru | or 5,
When the simplex operation process is executed under the constraint conditions of the first constraint condition expression and the third constraint condition expression and an executable solution with a non-integer solution is obtained, another new non-integer number A member assignment system characterized by repeating simplex calculation processing for obtaining a solution. Means for optimizing the combination of products assigned to each raw material by obtaining the number of each type of raw material required when each of m products having a predetermined length is cut out from k kinds of raw materials each having a predetermined length; A pre-cut device that accepts optimized member allocation data and cuts the m products from the k kinds of raw materials that are sequentially supplied;
Accepting the input of product length data of m required products, and generating an m-th order product length vector Lp having the product length as an element and a product request quantity vector b having the product request quantity as an element Product length setting means for storing in the storage device;
A raw material length setting means that receives input of raw material length data of k types of prepared lengths, generates a k-th order raw material length vector Lm having the raw material length as an element, and stores it in a storage device;
The raw material and product which can economically allocate one or a plurality of products by comparing the product length data of the required m products with the raw material length data of the k kinds of raw materials prepared An allocation pattern vector generation means for enumerating m-th order allocation pattern vectors,
An allocation pattern matrix generation unit that generates an allocation pattern matrix A in which the allocation pattern vectors generated by the allocation pattern vector generation unit are arranged and stores the allocation pattern matrix A in a storage device;
An m-th order cost coefficient vector corresponding to the raw material length vector Lm, wherein each element for selecting a corresponding raw material by selecting from the n allocation patterns included in the allocation pattern matrix defines a number vector x of x i And an objective function generating means for generating an objective function indicating a sum of products of the used number vectors x and storing the objective function in a storage device;
The first constraint condition expression Ax ≧ b and the number-of-uses vector in which the number of each product cut out with the n number of allocation patterns selected from the allocation pattern matrix A must be equal to or greater than the quantity of each required product. a constraint condition generating means for generating a relaxed third constraint condition expression that each element x i of x is 0 ≦ xi ≦ 1, and storing it in the storage device;
Initial setting means for receiving an input of an initial executable solution obtained by an arbitrary method and storing it in a storage device;
Simplex operation means for receiving input of the initial executable solution, the objective function, and the constraint condition expression, and executing simplex operation processing;
If the simplex operation process results in a solution where the value of xi is either 0 or 1 and does not include any other value, the member assignment data is output with the solution as the optimal solution, otherwise Is a combination of the number of raw materials used that takes the objective function value of the initial feasible solution as a maximum value, the objective function value obtained as a result of the simplex operation processing as a minimum value, and takes the objective function value in that range. Are selected from among them, and the number of raw materials of which length is selected and used for allocation is selected for the constraint condition generation means. A request is made to generate a second constraint condition expression Cx = d, where the product of the use matrix C and the raw material use number vector x is equal to the raw material use scheduled quantity vector d, and the first constraint condition expression and the second constraint condition expression are requested. And the third Under the constraint condition of the constraint condition expression, the simplex operation means is requested to perform the arithmetic processing, and the simplex arithmetic processing obtained thereafter results in a solution where the value of xi is either 0 or 1 and does not include any other In this case, the member allocation data is output with the solution as an optimal solution, and in other cases, the next candidate whose objective function is close to the minimum value is selected from the listed combinations of the number of raw materials used. Select and request the constraint condition generation means to generate a new second constraint condition expression Cx = d, and repeat the operation of requesting the simplex operation means to perform arithmetic processing under this new constraint condition. Search control means for controlling,
When the xi takes a numerical value between 0 and 1 while satisfying the constraint expression, a function Σf (xi) whose maximum value or minimum value is a constant value is set as an evaluation expression, and the pivot calculation process When a plurality of non-integer solutions are obtained as a result, a determination unit that compares the relationship between these non-integer solutions by applying the evaluation formula is provided,
The search control means continues the pivot calculation process when it is determined that the determination means satisfies a certain determination criterion, and the initial time when the pivot calculation process is started when it is determined that the determination criterion is not satisfied. A member processing apparatus characterized by changing a condition and restarting a pivot calculation process.   The member allocation program which makes a computer function as each means of Claim 1.   A computer-readable recording medium having recorded thereon a member assignment program that causes the computer to function as each means according to claim 1. A method that optimizes the combination of products assigned to each raw material by obtaining the number of each type of raw material required when cutting out m products each having a predetermined length from k kinds of raw materials each having a predetermined length. There,
The product length setting means accepts the input of the product length data of m required products, and the m-th order product length vector Lp with the product length as an element and the product request quantity vector with the product request quantity as an element generating b and storing it in a storage device;
A step in which raw material length setting means receives input of raw material length data of k types of prepared lengths, generates a k-th raw material length vector Lm having the raw material length as an element, and stores it in a storage device;
The allocation pattern vector generation means compares the required product length data of the m products and the prepared raw material length data of the k kinds of raw materials, and economically determines one or more products. Enumerating m-th order allocation pattern vectors indicating the relationship between raw materials and products that can be allocated;
An allocation pattern matrix generation unit that generates an allocation pattern matrix A in which the allocation pattern vectors generated by the allocation pattern vector generation unit are arranged and stores the allocation pattern matrix A in a storage device;
The objective function generating means selects n allocation patterns included in the allocation pattern matrix and selects the corresponding raw material, each element defines the number vector x of x i and corresponds to the raw material length vector Lm Generating an objective function indicating the sum of products of the m-th order cost coefficient vector and the used number vector x and storing the objective function in a storage device;
Constraint condition expression Ax ≧ b, where the number of products cut out by the constraint condition generation means with the n number of allocation patterns selected from the allocation pattern matrix A must be equal to or greater than the quantity of each product obtained. And generating a relaxed third constraint expression that each element xi of the used number vector x is 0 ≦ xi ≦ 1, and storing it in the storage device;
An initial setting means for receiving an input of an initial executable solution obtained by an arbitrary method and storing it in a storage device;
A simplex computing means for receiving input of the initial executable solution, the objective function, and the constraint expression, and executing a simplex computing process;
The search control means outputs a member allocation data with the solution as the optimal solution when the value of xi is either 0 or 1 and does not include any other by the simplex operation processing, In other cases, the raw material which takes the value of the objective function in the range with the value of the objective function of the initial feasible solution as the maximum value and the value of the objective function obtained as a result of the simplex operation processing as the minimum value. Enumerating the combinations of the number of used and selecting the one whose objective function is close to the minimum value from among the combinations,
The search control means determines how many raw materials of which length to select and use for allocation to the constraint generation means. The product of the raw material use matrix C and the raw material use number vector x is the raw material use. Requesting generation of a second constraint condition expression Cx = d that is equal to the planned quantity vector d;
The search control means requesting an arithmetic process to the simplex arithmetic means under the constraint;
When the search control means obtains a simplex operation process, and the solution is a solution that does not include any other value when the value of xi is 0 or 1, member assignment data is determined with that solution as the optimum solution. Otherwise, select the next candidate whose objective function is close to the minimum value from the listed combinations of the number of used raw materials, and Requests the generation of a new second constraint condition expression Cx = d, and requests calculation processing to the simplex operation means under the constraint conditions of the first constraint condition expression, the second constraint condition expression, and the third constraint condition expression A step of controlling to repeat the operation of
When the determination means takes a numerical value between 0 and 1 while the xi satisfies the constraint expression, a function Σf (xi) whose maximum value or minimum value is a constant value is set as an evaluation expression, When a plurality of non-integer solutions are obtained as a result of the pivot operation, comparing the relationship of these non-integer solutions by applying the evaluation formula;
When the search control unit determines that the determination unit satisfies a certain determination criterion, the pivot calculation processing is continued, and when it is determined that the determination criterion is not satisfied, an initial time when the pivot calculation processing is started A member allocating method comprising a step of changing a condition and restarting a pivot calculation process.

Images