linprog cannot find solution

Question

Austin Brehm 2019-2-24

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/446752-linprog-cannot-find-solution

评论： John D'Errico 2019-2-27

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 个评论
显示 3更早的评论隐藏 3更早的评论

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.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Steven Lord 2019-2-26

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/446752-linprog-cannot-find-solution#answer_362877

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 个评论
显示 2更早的评论隐藏 2更早的评论

Austin Brehm 2019-2-27

Sorry, I made an error. ub is set to an empty matrix [ ], not a zeros matrix. lb is set to a zeros matrix. In other words, the lower bound is zero and the upper bound does not exist.

Walter Roberson 2019-2-27

在 MATLAB Online 中打开

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)

请先登录，再进行评论。

Answer 2

John D'Errico 2019-2-27

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/446752-linprog-cannot-find-solution#answer_362975

编辑：John D'Errico 2019-2-27

在 MATLAB Online 中打开

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

John D'Errico 2019-2-27

在 MATLAB Online 中打开

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')

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)

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.

请先登录，再进行评论。

Answer 3

Walter Roberson 2019-2-27

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/446752-linprog-cannot-find-solution#answer_362900

在 MATLAB Online 中打开

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 个评论
显示 1更早的评论隐藏 1更早的评论

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

在 MATLAB Online 中打开

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.

请先登录，再进行评论。

linprog cannot find solution

5 个评论
显示 3更早的评论隐藏 3更早的评论

回答（3 个）

4 个评论
显示 2更早的评论隐藏 2更早的评论

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

3 个评论
显示 1更早的评论隐藏 1更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

linprog cannot find solution

5 个评论 显示 3更早的评论隐藏 3更早的评论

回答（3 个）

4 个评论 显示 2更早的评论隐藏 2更早的评论

1 个评论 显示 -1更早的评论隐藏 -1更早的评论

3 个评论 显示 1更早的评论隐藏 1更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

5 个评论
显示 3更早的评论隐藏 3更早的评论

4 个评论
显示 2更早的评论隐藏 2更早的评论

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

3 个评论
显示 1更早的评论隐藏 1更早的评论