Question:
A certain airline operation
A
、
B
、
C
Three cities, these routes take off and reach the following table every day.
Set aircraft to stay at the airport
loss costs are roughly and stay
The square of the time is proportional.
Each aircraft landing from landing
At least needed to take off from get off work
2
hour preparation time,
Try a decision to stop
cost loss is the smallest
allocate flight scheme.
A
、
B
、
C
Three cities, these routes take off and reach the following table every day.
Set aircraft to stay at the airport
loss costs are roughly and stay
The square of the time is proportional.
Each aircraft landing from landing
At least needed to take off from get off work
2
hour preparation time,
Try a decision to stop
cost loss is the smallest
allocate flight scheme.
|
Flight
15th |
Take off
City
|
Take off
time
|
Arrival
City
|
Arrival time |
| 101 |
A
|
9:00
|
B
|
12:00
|
| 102 |
A
|
10:00
|
B
|
13:00
|
| 103 |
A
|
15:00
|
B
|
18:00
|
| 104 |
A
|
20:00
|
C
|
24:00
|
| 105 |
A
|
22:00
|
C
|
2:00
(the next day) |
| 106 |
B
|
4:00
|
A
|
7:00
|
| 107 |
B
|
11:00
|
A
|
14:00
|
| 108 |
B
|
15:00
|
A
|
18:00
|
| 109 |
C
|
7:00
|
A
|
11:00
|
|
110 |
C
|
15:00
|
A
|
19:00
|
| 111 |
B
|
13:00
|
C
|
18:00
|
| 112 |
B
|
18:00
|
C
|
23:00
|
| 113 |
C
|
15:00
|
B
|
20:00
|
| 114 | C | 7:00 | B | 12:00 |
A city loss fee:
city lling costs:
C city loss fee:
problem solving ideas:
A
、
B
、
C
City takes off as the “task” to be completed,
The aircraft that arrives can be regarded as a pending distribution
“People” to complete the task.
As long as the plane reaches two hours, it can be distributed to complete the take -off task.
can be different in the city
A
、
B
、
C
List the efficiency matrix of the distribution problem,
Among them, the numbers are stopped by the aircraft
Losses.
can be different in the city
A
、
B
、
C
List the efficiency matrix of the distribution problem,
Among them, the numbers are stopped by the aircraft
Losses.
MATLAB code is as follows:
%applicable to any N -order coefficient matrix
Clear all;
C = [4 9 64 169 225
361 400 625 36 64
225 256 441 4 16
484 529 16 81 121
196 225 400 625 9];%efficiency matrix C
n = SIZE (C, 1);%Calculate the number of ran c n
C = c (:);%Calculate the target function coefficient, and arrange the matrix C according to the column into a column vector.
A = []; b = [];%without unlimited constraints
Ae = zeros (2*n, n^2);%Calculating the restricted coefficient matrix A
for i = 1: n
for j = (i-1)*n+1: n*i
Ae (i, j) = 1;
end
for k = i: n: n^2
Ae (n+i, k) = 1;
end
end
Be = Ones (2*n, 1);%equivalent to restrain the right end b
Xm = zeros (n^2,1);%decision variable lower boundary XM
XM = Ones (n^2,1);%decision variable upper boundary XM
[x, z1] = linprog (c, a, b, ae, be, xm, xm);%use linprog to solve
x = reshape (x, n, n);%row the column vector x into a n -order square array by column
DISP ('The optimal solution matrix is:');%output assignment scheme and the best value
Assignment = Round (X)%uses Round for four houses and five
Disp ('The optimal interpretation as:');
Z1
%%
%Suitable for any N -order coefficient matrix
Clear all;
C = [256 529 9 625 36
225 484 4 576 25
100 289 441 361 576
64 225 361 289 484
256 529 9 625 36];%efficiency matrix C
n = SIZE (C, 1);%Calculate the number of ran c n
C = c (:);%Calculate the target function coefficient, and arrange the matrix C according to the column into a column vector.
A = []; b = [];%without unlimited constraints
Ae = zeros (2*n, n^2);%Calculating the constraint coefficient matrix A
for i = 1: n
for j = (i-1)*n+1: n*i
Ae (i, j) = 1;
end
for k = i: n: n^2
Ae (n+i, k) = 1;
end
end
Be = Ones (2*n, 1);%equivalent to restrain the right end b
Xm = zeros (n^2,1);%decision variable lower boundary XM
XM = Ones (n^2,1);%decision variable upper boundary XM
[x, z2] = linprog (c, a, b, ae, be, xm, xm);%use linprog to solve
x = reshape (x, n, n);%row the column vector x into a n -order square array by column
DISP ('The optimal solution matrix is:');%output assignment scheme and the best value
Assignment = Round (X)%uses Round for four houses and five
Disp ('The optimal interpretation as:');
Z2
%%
%Suitable for any N -order coefficient matrix
Clear all;
C = [49 225 225 49
25 169 169 25
169 441 441 169
64 256 256 64];%efficiency matrix C
n = SIZE (C, 1);%Calculate the number of ran c n
C = c (:);%Calculate the target function coefficient, and arrange the matrix C according to the column into a column vector.
A = []; b = [];%without unlimited constraints
Ae = zeros (2*n, n^2);%Calculating the restricted coefficient matrix A
for i = 1: n
for j = (i-1)*n+1: n*i
Ae (i, j) = 1;
end
for k = i: n: n^2
Ae (n+i, k) = 1;
end
end
Be = Ones (2*n, 1);%equivalent to restrain the right end b
Xm = zeros (n^2,1);%decision variable lower boundary XM
XM = Ones (n^2,1);%decision variable upper boundary XM
[x, z3] = linprog (c, a, b, ae, be, xm, xm);%use linprog to solve
x = reshape (x, n, n);%row the column vector x into a n -order square array by column
DISP ('The optimal solution matrix is:');%output assignment scheme and the best value
Assignment = Round (X)%uses Round for four houses and five
Disp ('The optimal interpretation as:');
Z3
%%
Z = Z1+Z2+Z3result is as follows:
OPTImal Solution Found.
The optimal solution matrix is:
Assignment =
0 1 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
The optimal solution is:
Z1 =
273
Optimal solution found.
The optimal solution matrix is:
Assignment =
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 0 1 0
0 0 1 0 0
The optimal solution is:
Z2 =
848
Optimal solution found.
The optimal solution matrix is:
Assignment =
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
The optimal solution is:
Z3 =
627
z =
1748z1 results:
z2 result:
、
z3 Result:
So the solution that minimizes the cost of staying is:
101(A)→110(C) →104(A) →107(B) →103(A) →109(C) →112(B) →101(A)
102(A) →106(B) →102(A)
105(A) →108(B) →114(C) →111(B) →113(C) →105(A)
Losses: 273K+848K+627K = 1748K