Author: Gu Jian
Today, the teacher selected all our works in C1-305, and our works have got a little bit of the teacher, saying that the method is new! Hey! Finally, we have been busy a 4-day work to get the teacher's affirmation, we are of course happy, so our team decided to continue our cooperation, do more brilliant results. However, our works still have some details of the question. We are ready to complete this evening. Now put our first work here encourage yourself. I also hope that more people can discuss discussions together.
School Name: Shenyang Building University
Participants: Liu Jingcheng, Lu Xiaosu, Deng Shangjun
mentor:
Optimization problem of interview
Summary
This article studies the question on B. According to the company's requirements, once the order of the four job seekers determined, the order in the interview in the following stages will no longer change, because each job seeker, the time of the interview (and fixed) in three phases, so two Name Job Searner A, B, press A, in the previous, b, in the order of interviews, may exist: i, when A is completed, B has not completed the previous stage J-1 The interview, so the judge of the J stage must wait for the J-1 interview before the J-1 phase can be performed to the J phase interview, which will appear, the examiner is waiting for job seekers. II, when b Completes J-1 interview, A has not completed the J phase interview, so B must wait for a completion of the J-stage interview, so that the Journal of the J-Dynasty, this appears, the job seeker waiting for job seekers Case. The above two cases inevitably extend the entire interview process. To make four job seekers to leave the company, that is, the interview time they use, as long as it is the time and the shortest time of the examiner waiting for job seekers waiting for job seekers, so that the job seeker and the examiner The utilization rate has reached the highest. They can leave the company together with the shortest time.
First we analyze the interview schedule of the interview schedule, with the computer programming, the two job seekers will participate in the interview in different orders, the time of job seekers, the job seekers, etc., then the time of the job seekers, and then use the picture The method is modeled, and the calculated time expresses the weight of the empowerment map, and the problem conversion has the shortest problem with the four vertices in the empower map (Fig. 1). We use MATLAB programming, in order from small to large order, we will find the minimum side of the top weight of N-1 (n to participate in the interview), and then use the manual participation in the way, the Optimal is discharged. order. Finally, the order of Ding, A, B, and C is the optimal solution, and shares for 84 minutes. That is: Three people can leave the company at 9:24.
Thinking of this problem involves time related to the number of people, if you want to save time, it is worth promoting. So we promoted the model and gave several ways to ask for the optimal solution.
First, the question is proposed
Four job seekers participate in the interview, each job seeker is different in each stage interview time, how to arrange the interview order make the shortest time used, become the key issue we have to solve, and the following work is to complete:
1. ??????? By modeling, the four job seekers have shortlined the shortest time required to complete the interview;
2. ??????? Combine the actual situation to find out the promotion plan of the model.
Second, the problem analysis
• To solve the optimization problem of time, you must meet the following conditions:
1. The time between the time between the two job seekers, the examiner waiting for job seekers and the time of job seekers waiting for job seekers;
2. Select a path that has no repetition through all vertices, and the sum of the weight is minimized.
Use the chart theory to build the shortest path.
figure 1
Third, the model is assumed 1. ??????? The interview will participate in the interview by a stage to the next stage, there must be time interval, we assume that the time interval is 0;
2. ??????? We assume that the job seeker who participates in the interview is equal and independent, that is, the order of their interview is not related to the examiner;
3. ??????? Judicial job seeker who participated in the interview did not agree to the order of their interview;
4. ??????? Assume that any classmate can pass the interview, enter the next stage of the interview. That is: there is no time to exit the interview;
5. ??????? The interviewer can reach the interview place on time at 8:00.
Fourth, noun and symbolic agreement
1. ??????? Aij (i = 1, 2, 3 ...; j = 1, 2, 3 ...) for the job seeker i at the J phase to participate in the interview time, the granular propylene proprrops is corresponding to the sequence number i = 1, 2, 3, 4;
2. ??????? TDK indicates that two D and K are all in the job seeker, pressing D in the order in the previous K, in the specified order, the time to wait D at the time to wait for K The sum of the time, the TDK assigns the weight xdk of the vector from D to K in the empowerment map;
3. ??????? CDK indicates two D and K in the job seeker, press D to participate in the interview in the order in the first K, in the specified order, D complete the interview to K to complete the interview interval;
4. ?????? S is the total time of the optimal path.
V. Establishment and analysis of models
1. The data given by the question constitutes the original time matrix. Aij =
a
11
???????? a12
??????? a13
A21 ??????? a22 ??????? a23
A31 ??????? a32 ??????? a33
A14 ??????? a43 ??????? a43
????????????? is:
12 ?????????? 15 ????????? 20
10 ????????? 20 ????????? 18
20 ????????? 16 ????????? 10
8 ??????????? 10 ????????? 15
2. ??????? Ask the weight to the empowerment map, and construct the matrix.
From the meaning of the title, the weight value TDK can be divided into three cases;
1. ????? When A22-A11> = 0, A23-A12> = 0, indicating that if you sequentially 2-> 1 (B-> A), 1 (A) wants to enter the second stage to participate in the interview, Waiting 2 (B) time is (A22-A11), wanting to enter the third stage interview need to wait 2 (B) time is (A23-A12). Then: t21 = (A22-A11) (A23-A12)
At this time, the time difference C21 = A13, because 1 (A) job seeker is to wait 2 (B) job seeker to complete the third stage of the interview to enter the third stage, and 1 (A) job seeker in the third stage interview A total of time A13, that is, they both completed their respective interviews;
2. ??????? When A22-A11> 0, A23-A12 <0, explaining the interview according to the order 2-> 1 (B-> A), 1 (A) wants to enter the second stage to participate in the interview, The time required to wait 2 (B) is (A22-A11), wanting to enter the third phase of the interview, the third stage of the primary examiner needs to wait 1 (A) job seeker for (A23-A12), then: t21 = A22-A11) | A23-A12 | This time difference C21 = | A23-A12 | A13, because the primary examiner in the third stage has waited for 1 (A), it has been waiting for the time | A23-A12 | And 1 (A) interview time in the third stage is A13, so it is two times;
3. ??????? When A22-A11 <0, in order 2-> 1 (B-> A) interview, the second phase of the main examination official needs to wait 1 (A) job seeker for | A22- A11 |, this time delay, resulting in the third stage of the examiner waiting for 1 (A) time for | A22-A11 |, regardless of A23-A12> 0, or A23-A12 <0, ie, Is the primary examiner waiting, or a student waiting, the total time T21 = | 2 * (A22-A11) | | A23 - A12 | Time difference C21 = 2 * | A12-A11 | | A23 - A12 | a13
Algorithm summary:
?????? Through the above assumptions, we summarize the method of calculating the weight TDK and time difference CDK:
1. ??????? When AD2-AK1> = 0
1) ??????? TDK = | AD2-AK1 | | AD3-AK2 |
2) ??????? When AD3-AK2> = 0, CDK = AK3
3) ??????? When AD3-AK3 <0, CDK = | AD3-AK2 | AK3
2. ??? When AD2-AK1 <0
??????????????????????????????????????????????? TDK = | 2 * (AD2-AK1) (AD3-AK2 ) |
??????????????????????????????????????????????? CDK = | 2 * (AD2-AK1) (AD3-AK2 ) ak3
???????????????????? The above algorithm can be implemented by the MATLAB (the program source code is shown in Appendix 1). During the implementation, I can get TDK =
0 ??? 5 ?? 6 ?? 17
10 ?? 0 ?? 2?? 20
8 ?? 16 ?? 0 ?? 8
6 ?? 5 ?? 21 ?? 0
3. Look for the optimal path: We find the shortest path in the TDK with MATLAB (the program source code is detailed in Appendix 2), the smallest edge of the programs run is: T41, T12, T23. That is, it is Ding A, A-B, and Ets. The optimal order is: Duan Methylene.
4. Calculation total time S: s = Total total time C41 C12 C23 = 84min
6. The promotion of the model:
?? This mode is the optimized model, which has the value of promotion. For example: the pipeline operation produced by the workshop, how many components are produced in different workshops according to the order in order. ?
Seven, appendix:
Appendix 1 (program source code):
Function RST = CRTPOWER (a) ????????% Find The Power of the Matrix.
% ******************************************************** **********
%? This is help information about power () function.
% ?????????? Find the min number in the matrix.
% ???????? Verison: 1.0.0? Finish date: 27/08/2004
%? USAGE:
% ?????? Power (a) ?????% a is Matrix.
% ?????? Return A RST.
% ******************************************************** **********
?
Rows = Length (A (:, 1)); ??????% Get The Rows of the Matrix.
COL1 = a (:, 1);
COL2 = a (:, 2);
COL3 = a (:, 3);
RST = Zeros (ROWS);
For count1 = 1: rows;
??? for count2 = 1: ROWS;
??????? if col2 (count1) -col1 (count2)> = 0;
??????????? RST (count1, count2) = ABS (col2 (count1) -col1 (count2)) ABS (COL3 (count1) -col2 (count2));
??????? ELSE
RST (count1, count2) = 2 * ABS (col2 (count1) -col1 (count2) ABS (col3 (count1) -col2 (count2));
??????? end;
??????? if count1 == count2
??????????? rst (count1, count2) = INF;
??????? end;
???
END;
?
A = [13, 15, 20; 10, 20, 18; 20, 16, 10; 8, 10, 15;];
Crtpower (a)
?
Function RST = FINDMINPARAM (A, ICOUNT, DIFF)
% ******************************************************** **********
%? This is help information about findminparam () function.
%? Find the min number in defferent rows and cols the matrix.
% ?????????? Verison: 1.1.2? Finish date: 28/08/2004 ????
%? USAGE:
% ?????? Findminparam (A, ICOUNT, DIFF)
%? a is matrix.
%? Icount is counter.
% ?? Diff is the parame to find the mininum in diffreent rot. ???????
% ******************************************************** **********
?
IF Nargout> 1
??? Error ('Too Many Output Arguments!'); ELSE
????? ife (Nargin == 0 | Nargin> 3)
??????? Error ('Too Many Input Arguments!');
????? ELSE
??????? cols = length (a (1, :));
???????????? rows = length (a (:, 1));
??????? if Nargin == 1
??????????? iCount = rows * cols;
??????????? DIFF = 0;
??????? end;
??????? if Nargin == 2 | Nargin == 3
??? ???????? if Icount> rows * cols
??????????????? Error ('the search number is too big!');
??????????????? Icount = rows * cols;
??????????? Elseif iCount <1
??????????????? Error ('the mininum is 1');
??????????????? Icount = 1;
??????????? ELSE
??????????????? Icount = icunt;
??????????? end;
??????????? if Nargin == 3
??????????????? IF DIFF == 1
??????????????????? DIFF = 1;
??????????????? ELSE
??????????????????? DIFF = 0;
??????????????? End;
??????????? ELSE
??????????????? DIFF = 0;
??????????? end;
??????? end;
???????
??????? rst = zeros (ICOUNT, 3);
???????????? for count = 1: ICOUNT
??????????? SUCC = 0;
??????????? for rowcount = 1: ROWS;
??????????????? for colcount = 1: cols;
??????????????????????????? f (min (min (a)) == a (Rowcount, Colcount));???
??????????????????????? tmpmin = min (MIN (a)); ??????????????? ?? ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????? TMPROW = ROWCOUNT; ???????????? ??????????
???????????????????????? tmpcol = colcount;
??????????????????????? IF DIFF == 1
??????????????????????????? a (rowcount,:) = inf; ?????????????? ??????
??????????????????????????????????????? a (:, colcount) = INF;
??????????????????????? ELSE
??????????????????????????? a (rowcount, colcount) = INF;
??????????????????????? end; ???????????????????????????????????????????????????? succ = 1;????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? ????????
??????????????????? End;
??????????????? End ????% end for
??????????????? IF SUCC == 1 ????????????????????????????????????????? ???????
??????????????????? breaf;
??????????????? End;
??????????? end;
??????????? if SUCC == 1 ????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? ???????
??????????????? RST (count, 1) = tmpmin
?????????? ?????? RST (count, 2) = TmpRow;
??????????????? RST (count, 3) = tmpcol;
??????????? end;
???????????? end;
???????????? DISP (RST);
????? end;
END;
?
A = [13, 15, 20; 10, 20, 18; 20, 16, 10; 8, 10, 15;];
Findminparam (Crtpower (A), 3, 1);
?
?
Eight, the main reference
Author
Book name
publisher place
Publishing house
Year of publication
Zhao Jingqi
Mathematical modeling and mathematical experiment
Beijing
Higher Education Press
year 2002
?
?
The problem that currently exists:
1. No keywords in the paper;
2. The promotion of the model has not been described in detail in the paper;
3. Although the method in this article can be solved for this topic, if it is promoted, I don't know if I can achieve it! (Know that the crtpower () function does not take into account the promotion problem.)
4. Format issues. The paper did not "English Summary" and need to be added.
?
PS: Appendix this topic:
Shenyang University of Architecture Mathematics Construction Mode Potoring:
There are four students to participate in the three-stage interview. The company requires every classmate must first find the company secretary, and then go to the departmental executive office, and finally participate in the interview, and do not allow the interview (ie: in any The order of 4 classmates in a stage is the same.), Due to the different professional backgrounds of the four students, no one has different interviews in three phases, as shown in the following table:
These four classmates agreed that they left the company after all the interviews, assume that now time 8:00 in the morning, ask them when can they leave the company in the earliest?
(Unit: Minute)
Secretary test supervisor retest manager interview
A 13 15 20
B 10 20 18
C 20 16 10
Ding 8 10 15
?
?
