linprog cannot find solution
9 次查看(过去 30 天)
显示 更早的评论
I am running linprog to solve a problem with only equality constraints. The problem formulation is correctly setup, but the solver returns "no feasible solution found". How do I get linprog to find a solution?
5 个评论
Walter Roberson
2019-2-26
should we just use rand to construct the matrices or will you attach them?
John D'Errico
2019-2-26
编辑:John D'Errico
2019-2-26
Just telling us the shape of those matrices is not sufficient to tell us anything, since it is quite easy to construct such a set of matrices that has NO feasible solution. Would you like me to show you how? Or, you can give us the matrices, and we can show you if a solution can ever exist.
回答(3 个)
Steven Lord
2019-2-26
By the way you described the lb and ub inputs, both your lower and upper bounds are 0. That means the only possible feasible solution is the zero vector. Can that vector possibly satisfy your equality constraints? Since beq is not also the zero vector, it cannot.
So linprog is correct when it states that the problem you specified has no feasible solution. It doesn't matter what f or Aeq contain.
If you change either the lower or upper bounds your problem may have a solution. If you do and linprog still reports no feasible solution we will likely need to see the specific values in Aeq, beq, lb, and ub in order to determine if that's correct.
4 个评论
Walter Roberson
2019-2-27
Setting up for future investigation:
t = readtable('Results.xlsx', 'readvariablenames', false);
f = t{1,2:end};
A = [];
b = [];
Aeq = t{5:end,2:end};
beq = t{3,2:33} .';
lb = zeros(1,256);
ub = [];
sol = linprog(f,A,b,Aeq,beq,lb,ub)
John D'Errico
2019-2-27
编辑:John D'Errico
2019-2-27
I'll answer this a different way than did Walter, using different tools to answer the question at hand.
You have a linear system of equations as equality constraints.
Aeq*x = beq
Linear algebra shows us that Aeq is rank deficient.
size(Aeq)
ans =
32 256
rank(Aeq)
ans =
31
So it has 32 rows, but a numerical rank of only 31. When will a solution to such a problem exist? That is, does there exist a vector x such that Aeq*x== beq, despite the rank deficiency?
That can happen of course. In fact, it is entirely possible. Not here of course. Why not?
If a vector x existed such that this was possibly true, then it must be true that beq could be written as a linear combination of the columns of Aeq. That is, when you multiply Aeq*x, you form a linear combination of those columns. So, the simple test to see if such a solution exists, is to append beq to Aeq,and THEN test the rank again. It that rank is STILL 31, then a solution exists.
rank([Aeq,beq])
ans =
32
So here, the new matrix is now of full rank. That tells us that beq has information content in it that was not in the matrix Aeq. Is the differential a lot? It is not huge, but it is significant. So, was the problem possibly just a typing error?
U,S,V] = svd(Aeq);
U(:,end)'*beq
ans =
35.293
bdelta = U(:,end)'*beq*U(:,end)
bdelta =
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
6.2336
-5.9663
-6.0712
-6.6701
-5.8189
-5.7125
-6.2129
-6.4774
-5.7752
-6.1643
-6.6471
-6.9377
-6.1171
-6.0338
-6.4881
-6.7246
-5.92
So, my best guess at how to change the vector beq, so that a solution COULD exist is to adjust beq by bdelta. As you can see, if we perturb beq by bdelta, then a solution will exist.
rank([Aeq,beq-bdelta])
ans =
31
Again, IF we perturbed the elements of beq by the amounts in the vector bdelta, then the problem would now in theory be feasible. The thing is, bdelta is not that small, not relative to the size of the numbers in beq, nor is bdelta indicative of where you may have made a typing error. It may indicate there was a typo in your construction of the coefficients in Aeq.
In the end, linprog failed because your problem is inconsistent. No solution can ever be found that will satisfy the equality constraint system as you have posed it. My best guess is you made some unknown error in constructing the equations. It may have been when those coefficients were brought into MATLAB. Hmm, I could probably locate the smallest single element perturbation of Aeq or beq that would bring the problem back into feasiblilty. I'm not confident it is worth the effort at this point, since I do not know how those variables were created.
It LOOKS like Aeq was created programmatically. So the first 16 rows indicate weighted sums of each block of 16 unknowns. The second set of 16 rows are just copies of the identity matrix. So I know what your matrix tries to do, but at the same time, I see no obvious mistakes as to how Aeq was created. It seems to be consistent with itself based on all of the checks I can make. (I did make a few of them.)
So, then I looked more carefully at beq.
beq
beq =
1068.95017960331
1123.34967983758
856.792128689677
1714.94424488521
951.991254099641
1034.9504919569
951.991254099641
1481.02639387787
934.311416523505
654.153990317039
440.635951897548
1837.34312041231
1168.22926753084
379.436514134
1521.82601905357
1296.06809308137
1896
1800
1512
1566
1494
1566
1566
1800
736
544
832
624
480
336
408
256
Does anything seem out of kilter? It is not obvious to me. I could check for single element perturbations to beq that would restore feasibility to the problem.
I just did exactly that, and nothing obvious was flagged in my eyes, except that each of the first 16 elements of beq was too large by almost exactly the same amount: 199.816.
So you did something wrong. I'm not sure what it was or where you error came from, but linprog is 100% correct in telling you that no feasible solution exists for the system you have posed.
1 个评论
John D'Errico
2019-2-27
By the way, I see by reading your comments to Walter, that you were wondering how you might find an approximate solution.
The problem is, there are infinitely many possible approximate solutions. Not just a simple infinity either. But a whole boatload of infinities. But, what is the best we can possibly do?
x0 = lsqlin(Aeq,beq,[],[],[],[],zeros(256,1));
Minimum found that satisfies the constraints.
Optimization completed because the objective function is non-decreasing in
feasible directions, to within the default value of the optimality tolerance,
and constraints are satisfied to within the default value of the constraint tolerance.
<stopping criteria details>
LSQLIN does solve that problem, giving ONE possible solution.
plot(x0,'-o')
![untitled.jpg](https://www.mathworks.com/matlabcentral/answers/uploaded_files/206122/untitled.jpeg)
Indeed, some of those elements are very near zero, but all are positive.
The error made in the solution is:
norm(Aeq *x0 - beq)
ans =
35.293
Which, if you appreciate the linear algebra I did to write my answer, it is not a coincidence that this yields the same number.
U(:,end)'*beq
ans =
35.293
However, the solution x0 is not necessarily one that minimizes the linprog problem posed. In order to do that, we need to modify beq.
nullAeq = null(Aeq');
beqhat = beq - beq'*nullAeq*nullAeq
beqhat =
1062.7
1117.1
850.56
1708.7
945.76
1028.7
945.76
1474.8
928.08
647.92
434.4
1831.1
1162
373.2
1515.6
1289.8
1902
1806.1
1518.7
1571.8
1499.7
1572.2
1572.5
1805.8
742.16
550.65
838.94
630.12
486.03
342.49
414.72
261.92
rank([Aeq,beqhat])
ans =
31
But, can we now solve the approximate problem? Yes. But the solution is only one of infinitely many equally valid solutions.
xhat = linprog(f,A,b,Aeq,beqhat,lb,ub);
plot(xhat)
![untitled.jpg](https://www.mathworks.com/matlabcentral/answers/uploaded_files/206123/untitled.jpeg)
Most of the elements are 0, as should be expected. And there are infinitely many ways I could have solved the problem differently, getting a completely different approximate solution for each, that would have been equally well approximately valid.
Walter Roberson
2019-2-27
If you use the symbolic toolbox, you can solve the first 31 (of 32) equalities for variables [1:17 33 48 49 65 81 97 113 129 145 161 177 193 209 225 241 ] .
However when you substitute that into the 32nd equation
x16 + x32 + x48 + x64 + x80 + x96 + x112 + x128 + x144 + x160 + x176 + x192 + x208 + x224 + x240 + x256 == 256
then you get the inconsistency
12772858437668988265496/27386139134060684307 == 256
Your equality equations are not consistent with each other, so the system cannot be solved.
3 个评论
Walter Roberson
2019-2-27
With the constraints you have now, there is no solution. If you want to approximate a solution you will need to describe how you are willing to relax your equalities.
Walter Roberson
2019-2-27
Suppose you approximate the solution by considering each equality equation Aeq(K,:)*x == beq(K) as being Aeq(K,:)*x - beq(K) and asking to minimize the squared sum of residues residue = sum((Aeq*x - beq).^2) . In the case where all of the equalities could be met, the residue would be 0. If not all of the equalities can be met, then you can try to minimize the residue, to minimize the constraint violation in one sense, under the assumption that the equalities are all of equal weight.
If you construct that residue then you can proceed to minimize it by using calculus: differentiate with respect to a variable, solve for zero, substitute back in, go for another variable, and so on. You can proceed in the order x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x33, x49, x65, x81, x97, x113, x129, x145, x161, x177, x193, x209, x225 . After that, you arrive at a residue that has no variables and is non-zero, indicating that the equalities cannot all be solved simultaneously. Back substitute from there to get values those variables must equal in terms of the others in order to get the f with least constraint violation.
x1 = (8772648985220703*x18)/8621075391639826 + (92568112640880017408*x19)/82801118599004708817 + (8407957995560919*x20)/8621075391639826 + (4127107857803151*x21)/4310537695819913 + (8977404239245911*x22)/8621075391639826 + (14193657175611539456*x23)/13073860831421796129 + (80148310768499032064*x24)/82801118599004708817 + (4453553770196300*x25)/4310537695819913 + (4802331290924450*x26)/4310537695819913 + (32093776844548997120*x27)/27600372866334902939 + (84892852975933849600*x28)/82801118599004708817 + (4359264757226295*x29)/4310537695819913 + (90041593249925169152*x30)/82801118599004708817 + (4858336151197661*x31)/4310537695819913 + (4277079358747569*x32)/4310537695819913 + (8772648985220703*x34)/8621075391639826 + (92568112640880017408*x35)/82801118599004708817 + (8407957995560919*x36)/8621075391639826 + (4127107857803151*x37)/4310537695819913 + (8977404239245911*x38)/8621075391639826 + (14193657175611539456*x39)/13073860831421796129 + (80148310768499032064*x40)/82801118599004708817 + (4453553770196300*x41)/4310537695819913 + (4802331290924450*x42)/4310537695819913 + (32093776844548997120*x43)/27600372866334902939 + (84892852975933849600*x44)/82801118599004708817 + (4359264757226295*x45)/4310537695819913 + (90041593249925169152*x46)/82801118599004708817 + (4858336151197661*x47)/4310537695819913 + (4277079358747569*x48)/4310537695819913 + (8772648985220703*x50)/8621075391639826 + (92568112640880017408*x51)/82801118599004708817 + (8407957995560919*x52)/8621075391639826 + (4127107857803151*x53)/4310537695819913 + (8977404239245911*x54)/8621075391639826 + (14193657175611539456*x55)/13073860831421796129 + (80148310768499032064*x56)/82801118599004708817 + (4453553770196300*x57)/4310537695819913 + (4802331290924450*x58)/4310537695819913 + (32093776844548997120*x59)/27600372866334902939 + (84892852975933849600*x60)/82801118599004708817 + (4359264757226295*x61)/4310537695819913 + (90041593249925169152*x62)/82801118599004708817 + (4858336151197661*x63)/4310537695819913 + (4277079358747569*x64)/4310537695819913 + (8772648985220703*x66)/8621075391639826 + (92568112640880017408*x67)/82801118599004708817 + (8407957995560919*x68)/8621075391639826 + (4127107857803151*x69)/4310537695819913 + (8977404239245911*x70)/8621075391639826 + (14193657175611539456*x71)/13073860831421796129 + (80148310768499032064*x72)/82801118599004708817 + (4453553770196300*x73)/4310537695819913 + (4802331290924450*x74)/4310537695819913 + (32093776844548997120*x75)/27600372866334902939 + (84892852975933849600*x76)/82801118599004708817 + (4359264757226295*x77)/4310537695819913 + (90041593249925169152*x78)/82801118599004708817 + (4858336151197661*x79)/4310537695819913 + (4277079358747569*x80)/4310537695819913 + (8772648985220703*x82)/8621075391639826 + (92568112640880017408*x83)/82801118599004708817 + (8407957995560919*x84)/8621075391639826 + (4127107857803151*x85)/4310537695819913 + (8977404239245911*x86)/8621075391639826 + (14193657175611539456*x87)/13073860831421796129 + (80148310768499032064*x88)/82801118599004708817 + (4453553770196300*x89)/4310537695819913 + (4802331290924450*x90)/4310537695819913 + (32093776844548997120*x91)/27600372866334902939 + (84892852975933849600*x92)/82801118599004708817 + (4359264757226295*x93)/4310537695819913 + (90041593249925169152*x94)/82801118599004708817 + (4858336151197661*x95)/4310537695819913 + (4277079358747569*x96)/4310537695819913 + (8772648985220703*x98)/8621075391639826 + (92568112640880017408*x99)/82801118599004708817 + (8407957995560919*x100)/8621075391639826 + (4127107857803151*x101)/4310537695819913 + (8977404239245911*x102)/8621075391639826 + (14193657175611539456*x103)/13073860831421796129 + (80148310768499032064*x104)/82801118599004708817 + (4453553770196300*x105)/4310537695819913 + (4802331290924450*x106)/4310537695819913 + (32093776844548997120*x107)/27600372866334902939 + (84892852975933849600*x108)/82801118599004708817 + (4359264757226295*x109)/4310537695819913 + (90041593249925169152*x110)/82801118599004708817 + (4858336151197661*x111)/4310537695819913 + (4277079358747569*x112)/4310537695819913 + (8772648985220703*x114)/8621075391639826 + (92568112640880017408*x115)/82801118599004708817 + (8407957995560919*x116)/8621075391639826 + (4127107857803151*x117)/4310537695819913 + (8977404239245911*x118)/8621075391639826 + (14193657175611539456*x119)/13073860831421796129 + (80148310768499032064*x120)/82801118599004708817 + (4453553770196300*x121)/4310537695819913 + (4802331290924450*x122)/4310537695819913 + (32093776844548997120*x123)/27600372866334902939 + (84892852975933849600*x124)/82801118599004708817 + (4359264757226295*x125)/4310537695819913 + (90041593249925169152*x126)/82801118599004708817 + (4858336151197661*x127)/4310537695819913 + (4277079358747569*x128)/4310537695819913 + (8772648985220703*x130)/8621075391639826 + (92568112640880017408*x131)/82801118599004708817 + (8407957995560919*x132)/8621075391639826 + (4127107857803151*x133)/4310537695819913 + (8977404239245911*x134)/8621075391639826 + (14193657175611539456*x135)/13073860831421796129 + (80148310768499032064*x136)/82801118599004708817 + (4453553770196300*x137)/4310537695819913 + (4802331290924450*x138)/4310537695819913 + (32093776844548997120*x139)/27600372866334902939 + (84892852975933849600*x140)/82801118599004708817 + (4359264757226295*x141)/4310537695819913 + (90041593249925169152*x142)/82801118599004708817 + (4858336151197661*x143)/4310537695819913 + (4277079358747569*x144)/4310537695819913 + (8772648985220703*x146)/8621075391639826 + (92568112640880017408*x147)/82801118599004708817 + (8407957995560919*x148)/8621075391639826 + (4127107857803151*x149)/4310537695819913 + (8977404239245911*x150)/8621075391639826 + (14193657175611539456*x151)/13073860831421796129 + (80148310768499032064*x152)/82801118599004708817 + (4453553770196300*x153)/4310537695819913 + (4802331290924450*x154)/4310537695819913 + (32093776844548997120*x155)/27600372866334902939 + (84892852975933849600*x156)/82801118599004708817 + (4359264757226295*x157)/4310537695819913 + (90041593249925169152*x158)/82801118599004708817 + (4858336151197661*x159)/4310537695819913 + (4277079358747569*x160)/4310537695819913 + (8772648985220703*x162)/8621075391639826 + (92568112640880017408*x163)/82801118599004708817 + (8407957995560919*x164)/8621075391639826 + (4127107857803151*x165)/4310537695819913 + (8977404239245911*x166)/8621075391639826 + (14193657175611539456*x167)/13073860831421796129 + (80148310768499032064*x168)/82801118599004708817 + (4453553770196300*x169)/4310537695819913 + (4802331290924450*x170)/4310537695819913 + (32093776844548997120*x171)/27600372866334902939 + (84892852975933849600*x172)/82801118599004708817 + (4359264757226295*x173)/4310537695819913 + (90041593249925169152*x174)/82801118599004708817 + (4858336151197661*x175)/4310537695819913 + (4277079358747569*x176)/4310537695819913 + (8772648985220703*x178)/8621075391639826 + (92568112640880017408*x179)/82801118599004708817 + (8407957995560919*x180)/8621075391639826 + (4127107857803151*x181)/4310537695819913 + (8977404239245911*x182)/8621075391639826 + (14193657175611539456*x183)/13073860831421796129 + (80148310768499032064*x184)/82801118599004708817 + (4453553770196300*x185)/4310537695819913 + (4802331290924450*x186)/4310537695819913 + (32093776844548997120*x187)/27600372866334902939 + (84892852975933849600*x188)/82801118599004708817 + (4359264757226295*x189)/4310537695819913 + (90041593249925169152*x190)/82801118599004708817 + (4858336151197661*x191)/4310537695819913 + (4277079358747569*x192)/4310537695819913 + (8772648985220703*x194)/8621075391639826 + (92568112640880017408*x195)/82801118599004708817 + (8407957995560919*x196)/8621075391639826 + (4127107857803151*x197)/4310537695819913 + (8977404239245911*x198)/8621075391639826 + (14193657175611539456*x199)/13073860831421796129 + (80148310768499032064*x200)/82801118599004708817 + (4453553770196300*x201)/4310537695819913 + (4802331290924450*x202)/4310537695819913 + (32093776844548997120*x203)/27600372866334902939 + (84892852975933849600*x204)/82801118599004708817 + (4359264757226295*x205)/4310537695819913 + (90041593249925169152*x206)/82801118599004708817 + (4858336151197661*x207)/4310537695819913 + (4277079358747569*x208)/4310537695819913 + (8772648985220703*x210)/8621075391639826 + (92568112640880017408*x211)/82801118599004708817 + (8407957995560919*x212)/8621075391639826 + (4127107857803151*x213)/4310537695819913 + (8977404239245911*x214)/8621075391639826 + (14193657175611539456*x215)/13073860831421796129 + (80148310768499032064*x216)/82801118599004708817 + (4453553770196300*x217)/4310537695819913 + (4802331290924450*x218)/4310537695819913 + (32093776844548997120*x219)/27600372866334902939 + (84892852975933849600*x220)/82801118599004708817 + (4359264757226295*x221)/4310537695819913 + (90041593249925169152*x222)/82801118599004708817 + (4858336151197661*x223)/4310537695819913 + (4277079358747569*x224)/4310537695819913 + (8772648985220703*x226)/8621075391639826 + (92568112640880017408*x227)/82801118599004708817 + (8407957995560919*x228)/8621075391639826 + (4127107857803151*x229)/4310537695819913 + (8977404239245911*x230)/8621075391639826 + (14193657175611539456*x231)/13073860831421796129 + (80148310768499032064*x232)/82801118599004708817 + (4453553770196300*x233)/4310537695819913 + (4802331290924450*x234)/4310537695819913 + (32093776844548997120*x235)/27600372866334902939 + (84892852975933849600*x236)/82801118599004708817 + (4359264757226295*x237)/4310537695819913 + (90041593249925169152*x238)/82801118599004708817 + (4858336151197661*x239)/4310537695819913 + (4277079358747569*x240)/4310537695819913 + (8772648985220703*x242)/8621075391639826 + (92568112640880017408*x243)/82801118599004708817 + (8407957995560919*x244)/8621075391639826 + (4127107857803151*x245)/4310537695819913 + (8977404239245911*x246)/8621075391639826 + (14193657175611539456*x247)/13073860831421796129 + (80148310768499032064*x248)/82801118599004708817 + (4453553770196300*x249)/4310537695819913 + (4802331290924450*x250)/4310537695819913 + (32093776844548997120*x251)/27600372866334902939 + (84892852975933849600*x252)/82801118599004708817 + (4359264757226295*x253)/4310537695819913 + (90041593249925169152*x254)/82801118599004708817 + (4858336151197661*x255)/4310537695819913 + (4277079358747569*x256)/4310537695819913 - 561364608676283893184584958384761037397048940183932329728433928/37226881503254587069916582681156129322543129006689830182215
x2 = 15597682935217799466258756605032702599588435432/8636250076029926322527764764222395259999055 - x34 - x50 - x66 - x82 - x98 - x114 - x130 - x146 - x162 - x178 - x194 - x210 - x226 - x242 - x18
x3 = 13115614949356682968509103379211779470135397016/8636250076029926322527764764222395259999055 - x35 - x51 - x67 - x83 - x99 - x115 - x131 - x147 - x163 - x179 - x195 - x211 - x227 - x243 - x19
x4 = 13574620714447891615132647752871238623575862066/8636250076029926322527764764222395259999055 - x36 - x52 - x68 - x84 - x100 - x116 - x132 - x148 - x164 - x180 - x196 - x212 - x228 - x244 - x20
x5 = 12951891814580669074145856622866575798530132458/8636250076029926322527764764222395259999055 - x37 - x53 - x69 - x85 - x101 - x117 - x133 - x149 - x165 - x181 - x197 - x213 - x229 - x245 - x21
x6 = 13578024208663211864714834987971697362945233714/8636250076029926322527764764222395259999055 - x38 - x54 - x70 - x86 - x102 - x118 - x134 - x150 - x166 - x182 - x198 - x214 - x230 - x246 - x22
x7 = 13580307840478033900937689107998187955539713346/8636250076029926322527764764222395259999055 - x39 - x55 - x71 - x87 - x103 - x119 - x135 - x151 - x167 - x183 - x199 - x215 - x231 - x247 - x23
x8 = 15595126169080269888312985464803217980591555448/8636250076029926322527764764222395259999055 - x40 - x56 - x72 - x88 - x104 - x120 - x136 - x152 - x168 - x184 - x200 - x216 - x232 - x248 - x24
x9 = 1281903298560746707533536047223546380632735776/1727250015205985264505552952844479051999811 - x41 - x57 - x73 - x89 - x105 - x121 - x137 - x153 - x169 - x185 - x201 - x217 - x233 - x249 - x25
x10 = 951105131872375600099938109975880167958297504/1727250015205985264505552952844479051999811 - x42 - x58 - x74 - x90 - x106 - x122 - x138 - x154 - x170 - x186 - x202 - x218 - x234 - x250 - x26
x11 = 1449055124206575453976842755500027610300766656/1727250015205985264505552952844479051999811 - x43 - x59 - x75 - x91 - x107 - x123 - x139 - x155 - x171 - x187 - x203 - x219 - x235 - x251 - x27
x12 = 1088369718560180210286569895343474443660231504/1727250015205985264505552952844479051999811 - x44 - x60 - x76 - x92 - x108 - x124 - x140 - x156 - x172 - x188 - x204 - x220 - x236 - x252 - x28
x13 = 839501874190650375097096354648154289288195072/1727250015205985264505552952844479051999811 - x45 - x61 - x77 - x93 - x109 - x125 - x141 - x157 - x173 - x189 - x205 - x221 - x237 - x253 - x29
x14 = 2957812615173820363259716254575595575932442544/8636250076029926322527764764222395259999055 - x46 - x62 - x78 - x94 - x110 - x126 - x142 - x158 - x174 - x190 - x206 - x222 - x238 - x254 - x30
x15 = 3581665114208675197288570251078911770109545608/8636250076029926322527764764222395259999055 - x47 - x63 - x79 - x95 - x111 - x127 - x143 - x159 - x175 - x191 - x207 - x223 - x239 - x255 - x31
x16 = 2262006934488200969366163898832214724422917152/8636250076029926322527764764222395259999055 - x48 - x64 - x80 - x96 - x112 - x128 - x144 - x160 - x176 - x192 - x208 - x224 - x240 - x256 - x32
x17 = 43449351499685028368455894812102037540918774327710550310085632/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x19)/82801118599004708817 - (8407957995560919*x20)/8621075391639826 - (4127107857803151*x21)/4310537695819913 - (8977404239245911*x22)/8621075391639826 - (14193657175611539456*x23)/13073860831421796129 - (80148310768499032064*x24)/82801118599004708817 - (4453553770196300*x25)/4310537695819913 - (4802331290924450*x26)/4310537695819913 - (32093776844548997120*x27)/27600372866334902939 - (84892852975933849600*x28)/82801118599004708817 - (4359264757226295*x29)/4310537695819913 - (90041593249925169152*x30)/82801118599004708817 - (4858336151197661*x31)/4310537695819913 - (4277079358747569*x32)/4310537695819913 - (8772648985220703*x18)/8621075391639826
x33 = 33081805428729426625191068532832881486512460775315494745823232/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x35)/82801118599004708817 - (8407957995560919*x36)/8621075391639826 - (4127107857803151*x37)/4310537695819913 - (8977404239245911*x38)/8621075391639826 - (14193657175611539456*x39)/13073860831421796129 - (80148310768499032064*x40)/82801118599004708817 - (4453553770196300*x41)/4310537695819913 - (4802331290924450*x42)/4310537695819913 - (32093776844548997120*x43)/27600372866334902939 - (84892852975933849600*x44)/82801118599004708817 - (4359264757226295*x45)/4310537695819913 - (90041593249925169152*x46)/82801118599004708817 - (4858336151197661*x47)/4310537695819913 - (4277079358747569*x48)/4310537695819913 - (8772648985220703*x34)/8621075391639826
x49 = 66458956300020168725697762409688108951548322660410206436472832/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x51)/82801118599004708817 - (8407957995560919*x52)/8621075391639826 - (4127107857803151*x53)/4310537695819913 - (8977404239245911*x54)/8621075391639826 - (14193657175611539456*x55)/13073860831421796129 - (80148310768499032064*x56)/82801118599004708817 - (4453553770196300*x57)/4310537695819913 - (4802331290924450*x58)/4310537695819913 - (32093776844548997120*x59)/27600372866334902939 - (84892852975933849600*x60)/82801118599004708817 - (4359264757226295*x61)/4310537695819913 - (90041593249925169152*x62)/82801118599004708817 - (4858336151197661*x63)/4310537695819913 - (4277079358747569*x64)/4310537695819913 - (8772648985220703*x50)/8621075391639826
x65 = 36784500454070716120471391437802063744668686531075423961285632/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x67)/82801118599004708817 - (8407957995560919*x68)/8621075391639826 - (4127107857803151*x69)/4310537695819913 - (8977404239245911*x70)/8621075391639826 - (14193657175611539456*x71)/13073860831421796129 - (80148310768499032064*x72)/82801118599004708817 - (4453553770196300*x73)/4310537695819913 - (4802331290924450*x74)/4310537695819913 - (32093776844548997120*x75)/27600372866334902939 - (84892852975933849600*x76)/82801118599004708817 - (4359264757226295*x77)/4310537695819913 - (90041593249925169152*x78)/82801118599004708817 - (4858336151197661*x79)/4310537695819913 - (4277079358747569*x80)/4310537695819913 - (8772648985220703*x66)/8621075391639826
x81 = 40011134690439554740895678387464105017378477444218558437548032/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x83)/82801118599004708817 - (8407957995560919*x84)/8621075391639826 - (4127107857803151*x85)/4310537695819913 - (8977404239245911*x86)/8621075391639826 - (14193657175611539456*x87)/13073860831421796129 - (80148310768499032064*x88)/82801118599004708817 - (4453553770196300*x89)/4310537695819913 - (4802331290924450*x90)/4310537695819913 - (32093776844548997120*x91)/27600372866334902939 - (84892852975933849600*x92)/82801118599004708817 - (4359264757226295*x93)/4310537695819913 - (90041593249925169152*x94)/82801118599004708817 - (4858336151197661*x95)/4310537695819913 - (4277079358747569*x96)/4310537695819913 - (8772648985220703*x82)/8621075391639826
x97 = 36784500454070716120471391437802063744668686531075423961285632/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x99)/82801118599004708817 - (8407957995560919*x100)/8621075391639826 - (4127107857803151*x101)/4310537695819913 - (8977404239245911*x102)/8621075391639826 - (14193657175611539456*x103)/13073860831421796129 - (80148310768499032064*x104)/82801118599004708817 - (4453553770196300*x105)/4310537695819913 - (4802331290924450*x106)/4310537695819913 - (32093776844548997120*x107)/27600372866334902939 - (84892852975933849600*x108)/82801118599004708817 - (4359264757226295*x109)/4310537695819913 - (90041593249925169152*x110)/82801118599004708817 - (4858336151197661*x111)/4310537695819913 - (4277079358747569*x112)/4310537695819913 - (8772648985220703*x98)/8621075391639826
x113 = 57360905666324438929889057962786180281142874876237518923087872/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x115)/82801118599004708817 - (8407957995560919*x116)/8621075391639826 - (4127107857803151*x117)/4310537695819913 - (8977404239245911*x118)/8621075391639826 - (14193657175611539456*x119)/13073860831421796129 - (80148310768499032064*x120)/82801118599004708817 - (4453553770196300*x121)/4310537695819913 - (4802331290924450*x122)/4310537695819913 - (32093776844548997120*x123)/27600372866334902939 - (84892852975933849600*x124)/82801118599004708817 - (4359264757226295*x125)/4310537695819913 - (90041593249925169152*x126)/82801118599004708817 - (4858336151197661*x127)/4310537695819913 - (4277079358747569*x128)/4310537695819913 - (8772648985220703*x114)/8621075391639826
x129 = 36096857092221616973199309225552200105745067872510652467261952/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x131)/82801118599004708817 - (8407957995560919*x132)/8621075391639826 - (4127107857803151*x133)/4310537695819913 - (8977404239245911*x134)/8621075391639826 - (14193657175611539456*x135)/13073860831421796129 - (80148310768499032064*x136)/82801118599004708817 - (4453553770196300*x137)/4310537695819913 - (4802331290924450*x138)/4310537695819913 - (32093776844548997120*x139)/27600372866334902939 - (84892852975933849600*x140)/82801118599004708817 - (4359264757226295*x141)/4310537695819913 - (90041593249925169152*x142)/82801118599004708817 - (4858336151197661*x143)/4310537695819913 - (4277079358747569*x144)/4310537695819913 - (8772648985220703*x130)/8621075391639826
x145 = 25200354589074405603294464622231930253184692984911587814730752/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x147)/82801118599004708817 - (8407957995560919*x148)/8621075391639826 - (4127107857803151*x149)/4310537695819913 - (8977404239245911*x150)/8621075391639826 - (14193657175611539456*x151)/13073860831421796129 - (80148310768499032064*x152)/82801118599004708817 - (4453553770196300*x153)/4310537695819913 - (4802331290924450*x154)/4310537695819913 - (32093776844548997120*x155)/27600372866334902939 - (84892852975933849600*x156)/82801118599004708817 - (4359264757226295*x157)/4310537695819913 - (90041593249925169152*x158)/82801118599004708817 - (4858336151197661*x159)/4310537695819913 - (4277079358747569*x160)/4310537695819913 - (8772648985220703*x146)/8621075391639826
x161 = 16895738603666088036565768197745533712902557562611727373990912/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x163)/82801118599004708817 - (8407957995560919*x164)/8621075391639826 - (4127107857803151*x165)/4310537695819913 - (8977404239245911*x166)/8621075391639826 - (14193657175611539456*x167)/13073860831421796129 - (80148310768499032064*x168)/82801118599004708817 - (4453553770196300*x169)/4310537695819913 - (4802331290924450*x170)/4310537695819913 - (32093776844548997120*x171)/27600372866334902939 - (84892852975933849600*x172)/82801118599004708817 - (4359264757226295*x173)/4310537695819913 - (90041593249925169152*x174)/82801118599004708817 - (4858336151197661*x175)/4310537695819913 - (4277079358747569*x176)/4310537695819913 - (8772648985220703*x162)/8621075391639826
x177 = 71219564189744677474258121962759518806012671086578153828472832/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x179)/82801118599004708817 - (8407957995560919*x180)/8621075391639826 - (4127107857803151*x181)/4310537695819913 - (8977404239245911*x182)/8621075391639826 - (14193657175611539456*x183)/13073860831421796129 - (80148310768499032064*x184)/82801118599004708817 - (4453553770196300*x185)/4310537695819913 - (4802331290924450*x186)/4310537695819913 - (32093776844548997120*x187)/27600372866334902939 - (84892852975933849600*x188)/82801118599004708817 - (4359264757226295*x189)/4310537695819913 - (90041593249925169152*x190)/82801118599004708817 - (4858336151197661*x191)/4310537695819913 - (4277079358747569*x192)/4310537695819913 - (8772648985220703*x178)/8621075391639826
x193 = 45194907725917351190768052599776405910366074938549713100163072/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x195)/82801118599004708817 - (8407957995560919*x196)/8621075391639826 - (4127107857803151*x197)/4310537695819913 - (8977404239245911*x198)/8621075391639826 - (14193657175611539456*x199)/13073860831421796129 - (80148310768499032064*x200)/82801118599004708817 - (4453553770196300*x201)/4310537695819913 - (4802331290924450*x202)/4310537695819913 - (32093776844548997120*x203)/27600372866334902939 - (84892852975933849600*x204)/82801118599004708817 - (4359264757226295*x205)/4310537695819913 - (90041593249925169152*x206)/82801118599004708817 - (4858336151197661*x207)/4310537695819913 - (4277079358747569*x208)/4310537695819913 - (8772648985220703*x194)/8621075391639826
x209 = 14515434658803833662285588421209828785670383349527753677990912/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x211)/82801118599004708817 - (8407957995560919*x212)/8621075391639826 - (4127107857803151*x213)/4310537695819913 - (8977404239245911*x214)/8621075391639826 - (14193657175611539456*x215)/13073860831421796129 - (80148310768499032064*x216)/82801118599004708817 - (4453553770196300*x217)/4310537695819913 - (4802331290924450*x218)/4310537695819913 - (32093776844548997120*x219)/27600372866334902939 - (84892852975933849600*x220)/82801118599004708817 - (4359264757226295*x221)/4310537695819913 - (90041593249925169152*x222)/82801118599004708817 - (4858336151197661*x223)/4310537695819913 - (4277079358747569*x224)/4310537695819913 - (8772648985220703*x210)/8621075391639826
x225 = 58947774962899272231569151862261798809820618163715919307410432/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x227)/82801118599004708817 - (8407957995560919*x228)/8621075391639826 - (4127107857803151*x229)/4310537695819913 - (8977404239245911*x230)/8621075391639826 - (14193657175611539456*x231)/13073860831421796129 - (80148310768499032064*x232)/82801118599004708817 - (4453553770196300*x233)/4310537695819913 - (4802331290924450*x234)/4310537695819913 - (32093776844548997120*x235)/27600372866334902939 - (84892852975933849600*x236)/82801118599004708817 - (4359264757226295*x237)/4310537695819913 - (90041593249925169152*x238)/82801118599004708817 - (4858336151197661*x239)/4310537695819913 - (4277079358747569*x240)/4310537695819913 - (8772648985220703*x226)/8621075391639826
You then substitute these into f*x . The resulting expression is linear, with a mix of positive and negative terms.
Since your lower bound is 0 and your upper bound is positive infinity, you can take any of the negative terms and set its associated variable to infinity, and set the remaining variables involved in the expression to non-negative values, and that will represent an optimization of the system (yielding negative infinity.)
It is tempting to say, "Take all of the variables that have positive coefficients and set the variables to zero, and take all of the variables that have negative coefficients and set the variables to infinity". It does not hurt to do the first part of that, setting the variables with associated positive coefficients to 0. However, before setting the other variables to infinity in bulk, you need to check each of the equalities, in case those equalities might involve addition and subtraction of different infinite variables, which would be undefined. Looking through them all, I find that in each case all of the coefficients involved with variables are the same sign within any one equality. Therefore, it would not be a problem to set all of the variables with negative coefficients in the resolved f*x to infinity. It isn't necessary to do so though.
In all, 153 variables have negative coefficients and 73 have positive coefficients and 30 are defined in terms of the other variables by the constraints.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Linear Least Squares 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!