3569:
6073:
5873:
5225:
4478:
7276:
6068:{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\geq \rho \mathbf {p} ^{T}\mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\\\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\mathbf {z} \leq \rho \mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} ){\mathbf {z} }\\\end{matrix}}}
5773:
4978:
6576:
6208:
3066:
49:
states that the objective value of the dual LP at any feasible solution is always a bound on the objective of the primal LP at any feasible solution (upper or lower bound, depending on whether it is a maximization or minimization problem). In fact, this bounding property holds for the optimal values
5230:
The primal problem deals with physical quantities. With all inputs available in limited quantities, and assuming the unit prices of all outputs is known, what quantities of outputs to produce so as to maximize total revenue? The dual problem deals with economic values. With floor guarantees on all
6672:
5238:
The coefficients that bound the inequalities in the primal space are used to compute the objective in the dual space, input quantities in this example. The coefficients used to compute the objective in the primal space bound the inequalities in the dual space, output unit prices in this example.
2938:
5242:
Both the primal and the dual problems make use of the same matrix. In the primal space, this matrix expresses the consumption of physical quantities of inputs necessary to produce set quantities of outputs. In the dual space, it expresses the creation of the economic values associated with the
4264:
2602:
and relies on the proof that, with the suitable pivot rule, it provides a correct solution. The proof establishes that, once the simplex algorithm finishes with a solution to the primal LP, it is possible to read from the final tableau, a solution to the dual LP. So, by running the simplex
2435:. In other words, the objective value in each feasible solution of the dual is an upper-bound on the objective value of the primal, and objective value in each feasible solution of the primal is a lower-bound on the objective value of the dual. Here is a proof for the primal LP "Maximize
7034:
5576:
8555:
Since this is a minimization problem, we would like to obtain a dual program that is a lower bound of the primal. In other words, we would like the sum of all right hand side of the constraints to be the maximal under the condition that for each primal variable the sum of its
5246:
Since each inequality can be replaced by an equality and a slack variable, this means each primal variable corresponds to a dual slack variable, and each dual variable corresponds to a primal slack variable. This relation allows us to speak about complementary slackness.
4487:
unit prices for each of these means of production (inputs) are set by a planning board. The planning board's job is to minimize the total cost of procuring the set amounts of inputs while providing the farmer with a floor on the unit price of each of his crops (outputs),
6363:
6289:
3095:
is minimized to its lower bound under the constraints: the first constraint gives a lower bound of 3/5 while the second constraint gives a stricter lower bound of 4/6, so the actual lower bound is 4/6 and the minimum is 7 ⋅ 4/6 = 14/3.
4971:
4257:
5220:{\displaystyle {\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.}
5681:
5234:
To each variable in the primal space corresponds an inequality to satisfy in the dual space, both indexed by output type. To each inequality to satisfy in the primal space corresponds a variable in the dual space, both indexed by input type.
7024:
8285:
8106:
6476:
6104:
6803:
6874:
2949:
649:
The duality theorem states that the duality gap between the two LP problems is at least zero. Economically, it means that if the first factory is given an offer to buy its entire stock of raw material, at a per-item price of
6582:
2796:
4473:{\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.}
7271:{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)=(10/3,4,14/3)\geq (3,4,14/3)=\mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} =(14/3,7)^{T}\leq (14/3,7)^{T}=\mathbf {B} {\mathbf {z} }\end{matrix}}}
6469:
6416:
5485:
There is a close connection between linear programming problems, eigenequations, and von
Neumann's general equilibrium model. The solution to a linear programming problem can be regarded as a generalized eigenvector.
5494:
8740:
7961:
7419:
2209:
If all constraints have the same sign, it is possible to present the above recipe in a shorter way using matrices and vectors. The following table shows the relation between various kinds of primals and duals.
6723:
1878:
4785:
4678:
1361:
8986:
8846:
7665:
7525:
1973:
1456:
3496:
4096:
4016:
4577:
2954:
2801:
6212:
This form of the structural equilibrium model and linear programming problems can often be converted to each other, that is, the solutions to these two types of problems are often consistent.
3881:
3281:
9142:
Note that we assume in our calculations steps that the program is in standard form. However, any linear program may be transformed to standard form and it is therefore not a limiting factor.
3576:
with the dashed line farthest from the origin gives the optimal combination (its lying on the land and pesticide lines implies that revenue is limited by land and pesticide, not fertilizer)
3399:
3340:
9135:
8548:
8434:
7814:
9082:
8495:
8381:
7761:
6294:
6218:
3558:
4859:
2165:
1795:
1278:
933:
2552:
In particular, if the primal is unbounded (from above) then the dual has no feasible solution, and if the dual is unbounded (from below) then the primal has no feasible solution.
1021:
5422:
4876:
1601:
1143:
5473:
5365:
4150:
3936:
5607:
5768:{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} \geq \rho \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} \mathbf {z} \leq \rho \mathbf {B} {\mathbf {z} }\\\end{matrix}}}
4167:
9021:
8881:
8320:
8141:
7700:
7560:
3146:
6097:
5866:
5844:
5819:
5797:
5651:
5629:
5313:
591:
110:
We would like to construct an upper bound on the solution. So we create a linear combination of the constraints, with positive coefficients, such that the coefficients of
2100:
2037:
1730:
1667:
1243:
1210:
2130:
2067:
1697:
1634:
6884:
6571:{\displaystyle {\begin{bmatrix}\mathbf {y} ^{T}\mathbf {A} &u\\\end{bmatrix}}\geq {\begin{bmatrix}\mathbf {c} ^{T}&\mathbf {y} ^{T}\mathbf {b} \\\end{bmatrix}}}
6203:{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)\geq \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} \leq \mathbf {B} {\mathbf {z} }\end{matrix}}}
8151:
7972:
877:
617:
490:
Now consider another factory that has no raw material, and wishes to purchase the entire stock of raw material from the previous factory. It offers a price vector of
385:
339:
266:
2195:
1760:
1051:
435:
5671:
3809:
3782:
3755:
3728:
3698:
3671:
3644:
3617:
3200:
3173:
2000:
1523:
1503:
1483:
1173:
1078:
788:
697:
555:
313:
220:
6728:
3061:{\displaystyle {\begin{aligned}{\text{minimize }}&7y_{1}\\{\text{subject to }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}}
1886:
constraints. The coefficient of a dual variable in the dual constraint is the coefficient of its primal variable in its primal constraint. So each constraint
1543:
973:
953:
848:
828:
808:
761:
741:
721:
593:, since otherwise the factory could earn more cash by producing a certain product than selling off the raw material used to produce the good. It also should be
528:
508:
455:
405:
359:
286:
240:
193:
6808:
7285:
The max-flow min-cut theorem is a special case of the strong duality theorem: flow-maximization is the primal LP, and cut-minimization is the dual LP. See
5231:
output unit prices, and assuming the available quantity of all inputs is known, what input unit pricing scheme to set so as to minimize total expenditure?
6667:{\displaystyle {\begin{bmatrix}u\\\mathbf {A} \mathbf {x} \\\end{bmatrix}}\leq {\begin{bmatrix}\mathbf {c} ^{T}\mathbf {x} \\\mathbf {b} \\\end{bmatrix}}}
2933:{\displaystyle {\begin{aligned}{\text{maximize }}&3x_{1}+4x_{2}\\{\text{subject to }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}}
2564:
says that if one of the two problems has an optimal solution, so does the other one and that the bounds given by the weak duality theorem are tight, i.e.:
3102:
We use this example to illustrate the proof of the weak duality theorem. Suppose that, in the primal LP, we want to get an upper bound on the objective
2749:
2. The strong duality theorem provides a "good characterization" of the optimal value of an LP in that it allows us to easily prove that some value
7311:
Sometimes, one may find it more intuitive to obtain the dual program without looking at the program matrix. Consider the following linear program:
6421:
6368:
1053:, then the factory would make more money by selling its raw material than producing goods, since the prices are "too high". At equilibrium price
5571:{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} =\rho \mathbf {p} ^{T}\\\mathbf {A} \mathbf {z} =\rho {\mathbf {z} }\\\end{matrix}}}
2626:
feasible solution. Suppose we have an oracle that, given an LP, finds an arbitrary feasible solution (if one exists). Given the LP "Maximize
2746:
must be a minimal solution of the dual LP. If the combined LP has no feasible solution, then the primal LP has no feasible solution either.
8643:
7864:
7322:
6679:
1803:
619:, since the factory would not sell any raw material with negative price. Then, the second factory's optimization problem is the dual LP:
4698:
4591:
1286:
8891:
8751:
7570:
7430:
1893:
1376:
3404:
7286:
9390:
9362:
Kemeny, J. G.; Morgenstern, O.; Thompson, G. L. (1956). "A Generalization of the von
Neumann Model of an Expanding Economy".
9247:
4029:
3949:
3572:
Graphical solution to the farmer example – after shading regions violating the conditions, the vertex of the remaining
9205:
4511:
5821:
are the equilibrium prices of various goods and the equilibrium activity levels of various economic agents, respectively.
1091:
In general, given a primal LP, the following algorithm can be used to construct its dual LP. The primal LP is defined by:
6676:
Let us illustrate the structural equilibrium model with the previously discussed tiny example. In this example, we have
3820:
3205:
9434:
9319:
9279:
9217:
7293:
3085:
is maximized to its upper bound under the constraint (7/6). The maximum is 4 ⋅ 7/6 = 14/3.
9406:
6358:{\displaystyle \mathbf {B} ={\begin{bmatrix}\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {b} \\\end{bmatrix}}}
3345:
3286:
9090:
8503:
8389:
7769:
6284:{\displaystyle \mathbf {A} (u)={\begin{bmatrix}\mathbf {0} &u\\\mathbf {A} &\mathbf {0} \\\end{bmatrix}}}
2595:
The strong duality theorem is harder to prove; the proofs usually use the weak duality theorem as a sub-routine.
669:≥ 0, then it should take the offer. It will make at least as much revenue as it could producing finished goods.
122:
of the dual LP are the coefficients of this linear combination. The dual LP tries to find such coefficients that
9031:
8444:
8330:
7710:
5824:
The von
Neumann's equilibrium model can be further extended to the following structural equilibrium model with
672:
The strong duality theorem further states that the duality gap is zero. With strong duality, the dual solution
3501:
4805:
5676:
The above eigenequations for the square matrix can be extended to von
Neumann's general equilibrium model:
4966:{\displaystyle {\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}}
2135:
1765:
1248:
882:
978:
9461:
5375:
3099:
In accordance with the strong duality theorem, the maximum of the primal equals the minimum of the dual.
1560:
1102:
5432:
57:
states that, moreover, if the primal has an optimal solution then the dual has an optimal solution too,
9171:
5324:
4252:{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}
4109:
3895:
41:
The objective direction is inversed – maximum in the primal becomes minimum in the dual and vice versa.
5583:
5480:
3568:
9166:
8994:
8854:
8293:
8114:
7673:
7533:
3105:
1606:
The sign constraint of each dual variable is "opposite" to the sign of its primal constraint. So "
7019:{\displaystyle \mathbf {p} ^{*}=(1,2/3)^{T},\quad \mathbf {z} ^{*}=(0,7/6,1)^{T},\quad u^{*}=14/3}
6080:
5849:
5827:
5802:
5780:
5634:
5612:
5275:
560:
168:
The duality theorem has an economic interpretation. If we interpret the primal LP as a classical "
8280:{\displaystyle f_{i}x_{i}\cdot s_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\cdot s_{i}\geq h_{i}\cdot s_{i},}
8101:{\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}\cdot y_{j}+e_{j}t_{j}\cdot y_{j}\geq g_{j}\cdot y_{j},}
2072:
2009:
1702:
1639:
1215:
1182:
2105:
2042:
1672:
1609:
9161:
5266:
However, it is possible for both the dual and the primal to be infeasible. Here is an example:
2648:≥ 0", we can construct another LP by combining this LP with its dual. The combined LP has both
65:
2943:
Applying the recipe above gives the following dual LP, with one variable and two constraints:
9156:
7031:
We substitute the above calculation results into the structural equilibrium model, obtaining
856:
596:
364:
318:
245:
9303:
7292:
Other graph-related theorems can be proved using the strong duality theorem, in particular,
6798:{\displaystyle \mathbf {A} (u)={\begin{bmatrix}0&0&u\\5&6&0\\\end{bmatrix}}}
2170:
1735:
1026:
410:
9329:
5656:
3787:
3760:
3733:
3706:
3676:
3649:
3622:
3595:
3560:. Hence, the objective of the dual LP is an upper bound on the objective of the primal LP.
3178:
3151:
1978:
1508:
1488:
1461:
1151:
1056:
766:
675:
533:
291:
198:
3646:
units of pesticide must be used. Similarly, to grow one unit of barley, one unit of land,
8:
6869:{\displaystyle \mathbf {B} ={\begin{bmatrix}3&4&0\\0&0&7\\\end{bmatrix}}}
169:
9307:
1528:
958:
938:
833:
813:
793:
746:
726:
706:
513:
493:
440:
390:
344:
271:
225:
178:
9421:
Detailed documentation on the
General Equilibrium Model and Dual Linear Program in R.
9386:
9383:
General
Equilibrium and Structural Dynamics: Perspectives of New Structural Economics
9315:
9285:
9275:
9243:
9213:
2599:
1080:, the factory cannot increase its profit by purchasing or selling off raw material.
5481:
Viewing the solution to a linear programming problem as a (generalized) eigenvector
118:. This linear combination gives us an upper bound on the objective. The variables
9325:
9235:
7300:
6099:
is the utility levels of various consumers. A special case of the above model is
4581:(minimize the total cost of the means of production as the "objective function")
3573:
975:, since the prices are "too low". Conversely, if the raw material prices satisfy
2201:
From this algorithm, it is easy to see that the dual of the dual is the primal.
9151:
3580:
Consider a farmer who may grow wheat and barley with the set provision of some
2603:
algorithm, we obtain solutions to both the primal and the dual simultaneously.
24:
172:" problem, its dual LP can be interpreted as a "resource valuation" problem.
72:(the gap between the optimum of the primal and the optimum of the dual) is 0.
9455:
9289:
7028:
These are consistent with the solutions to the linear programming problems.
6464:{\displaystyle \mathbf {z} ={\begin{bmatrix}\mathbf {x} \\1\\\end{bmatrix}}}
6411:{\displaystyle \mathbf {p} ={\begin{bmatrix}1\\\mathbf {y} \\\end{bmatrix}}}
955:, then the factory would purchase more raw material to produce more of good
8571: + 1 constraints. If we sum its constraints' coefficients we get
2607:
790:
may not be unique, so the equilibrium price may not be fully determined by
700:
9269:
8557:
743:
would accept for raw material, given the market price for finished goods
69:
5255:
A LP can also be unbounded or infeasible. Duality theory tells us that:
3071:
It is easy to see that the maximum of the primal LP is attained when
341:(it cannot produce negative goods) and raw-material constraints. Let
9274:. Paul A. Samuelson, Robert M. Solow. New York: Dover Publications.
9342:
von
Neumann, J. (1945). "A Model of General Economic Equilibrium".
9236:"Complements on Duality: Economic Interpretation of Dual Variables"
8735:{\displaystyle \sum _{j=1}^{n}g_{j}y_{j}+\sum _{i=1}^{m}h_{i}s_{i}}
8560:
do not exceed its coefficient in the linear function. For example,
7956:{\displaystyle \sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}}
7414:{\displaystyle \sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}}
7303:
for zero-sum games can be proved using the strong-duality theorem.
38:
Each constraint in the primal LP becomes a variable in the dual LP;
35:
Each variable in the primal LP becomes a constraint in the dual LP;
6718:{\displaystyle \mathbf {A} ={\begin{bmatrix}5&6\end{bmatrix}}}
1873:{\displaystyle {\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}}
9385:(in Chinese). Beijing: Economic Science Press. pp. 122–125.
4780:{\displaystyle y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}}
4673:{\displaystyle y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}}
3148:. We can use the constraint multiplied by some coefficient, say
1356:{\displaystyle {\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}}
175:
Consider a factory that is planning its production of goods. Let
8981:{\displaystyle e_{j}y_{j}+\sum _{i=1}^{m}b_{ij}s_{i}\leq d_{j},}
8841:{\displaystyle \sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}\leq c_{i},}
7660:{\displaystyle f_{i}x_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\geq h_{i},}
7520:{\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}\geq g_{j},}
3703:
The primal problem would be the farmer deciding how much wheat (
1968:{\displaystyle a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}}
1451:{\displaystyle a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}}
9314:, Annals of Discrete Mathematics, vol. 29, North-Holland,
7829:
conditions and all variables are non-negative. We shall define
2790:
Consider the primal LP, with two variables and one constraint:
68:. The strong duality theorem is one of the cases in which the
1882:
Each primal variable becomes a dual constraint. So there are
1553:
Each primal constraint becomes a dual variable. So there are
703:) for the raw material that a factory with production matrix
3491:{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}}
2753:
is the optimum of some LP. The proof proceeds in two steps:
557:). For the offer to be accepted, it should be the case that
460:
Then, the constrained revenue maximization is the primal LP:
387:
be the matrix of material costs (producing one unit of good
6471:, then the structural equilibrium model can be written as
27:(LP) is another LP that is derived from the original (the
9361:
5631:
are the left and right eigenvectors of the square matrix
4154:(cannot produce negative quantities of wheat or barley).
5262:
If the dual is unbounded, then the primal is infeasible.
5259:
If the primal is unbounded, then the dual is infeasible;
3592:
pesticide. To grow one unit of wheat, one unit of land,
699:
is, economically speaking, the "equilibrium price" (see
4091:{\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}
4011:{\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}
3885:(maximize the revenue from producing wheat and barley)
3088:
Similarly, the minimum of the dual LP is attained when
1083:
The duality theorem has a physical interpretation too.
126:
the resulting upper bound. This gives the following LP:
7039:
6825:
6754:
6696:
6627:
6591:
6526:
6485:
6438:
6385:
6311:
6244:
6109:
5878:
5686:
5499:
5489:
The eigenequations of a square matrix are as follows:
5162:
5118:
5061:
4987:
4914:
4885:
4572:{\displaystyle L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}}
4429:
4392:
4349:
4273:
4214:
4176:
9242:, New York, NY: Springer New York, pp. 142–155,
9093:
9034:
8997:
8894:
8857:
8754:
8646:
8506:
8447:
8392:
8333:
8296:
8154:
8117:
7975:
7867:
7772:
7713:
7676:
7573:
7536:
7433:
7325:
7037:
6887:
6879:
To solve the structural equilibrium model, we obtain
6811:
6731:
6682:
6585:
6479:
6424:
6371:
6297:
6221:
6107:
6083:
5876:
5852:
5830:
5805:
5783:
5684:
5659:
5637:
5615:
5586:
5497:
5435:
5378:
5327:
5278:
4981:
4879:
4808:
4701:
4594:
4514:
4267:
4170:
4112:
4032:
3952:
3898:
3823:
3790:
3763:
3736:
3709:
3679:
3652:
3625:
3598:
3504:
3407:
3348:
3289:
3208:
3181:
3154:
3108:
2952:
2799:
2757:
Show a feasible solution to the primal LP with value
2173:
2138:
2108:
2075:
2045:
2012:
1981:
1896:
1806:
1768:
1738:
1705:
1675:
1642:
1612:
1563:
1531:
1511:
1491:
1464:
1379:
1289:
1251:
1218:
1185:
1154:
1105:
1059:
1029:
981:
961:
941:
885:
859:
836:
816:
796:
769:
749:
729:
709:
678:
599:
563:
536:
516:
496:
443:
413:
393:
367:
347:
321:
294:
274:
248:
228:
201:
181:
9407:"General Equilibrium Model and Dual Linear Program"
7287:
Max-flow min-cut theorem#Linear program formulation
2768:Show a feasible solution to the dual LP with value
2618:1. The weak duality theorem implies that finding a
9129:
9076:
9015:
8980:
8875:
8840:
8734:
8542:
8489:
8428:
8375:
8314:
8279:
8135:
8100:
7955:
7808:
7755:
7694:
7659:
7554:
7519:
7413:
7270:
7018:
6868:
6797:
6717:
6666:
6570:
6463:
6410:
6357:
6283:
6202:
6091:
6067:
5860:
5838:
5813:
5791:
5767:
5665:
5645:
5623:
5601:
5570:
5467:
5416:
5359:
5307:
5219:
4965:
4853:
4779:
4672:
4571:
4502:for barley. This corresponds to the following LP:
4472:
4251:
4144:
4090:
4010:
3930:
3875:
3803:
3776:
3749:
3722:
3692:
3665:
3638:
3611:
3552:
3490:
3393:
3334:
3275:
3194:
3167:
3140:
3060:
2932:
2189:
2159:
2124:
2094:
2061:
2031:
1994:
1967:
1872:
1789:
1754:
1724:
1691:
1661:
1628:
1595:
1537:
1517:
1497:
1477:
1450:
1355:
1272:
1237:
1204:
1167:
1137:
1072:
1045:
1015:
967:
947:
927:
871:
842:
822:
802:
782:
755:
735:
715:
691:
611:
585:
549:
522:
502:
449:
429:
399:
379:
353:
333:
307:
280:
260:
234:
214:
187:
3876:{\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}
3276:{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}}
9453:
2742:must be a maximal solution of the primal LP and
853:To see why, consider if the raw material prices
9203:
2002:is similar to the sign constraint on variable
361:be the raw material it has available, and let
9302:
268:be the list of market prices (a unit of good
9435:"Lecture 6: linear programming and matching"
9432:
4020:(cannot use more fertilizer than available)
3394:{\displaystyle y_{1}\cdot 6x_{2}\geq 4x_{2}}
3335:{\displaystyle y_{1}\cdot 5x_{1}\geq 3x_{1}}
2716:If the combined LP has a feasible solution (
2327:This is called an "asymmetric" dual problem
9341:
9233:
9130:{\displaystyle 1\leq j\leq n,1\leq i\leq m}
8543:{\displaystyle 1\leq j\leq n,1\leq i\leq m}
8429:{\displaystyle 1\leq i\leq m,1\leq j\leq n}
7809:{\displaystyle 1\leq i\leq m,1\leq j\leq n}
4100:(cannot use more pesticide than available)
2761:; this proves that the optimum is at least
2622:feasible solution is as hard as finding an
2613:
1086:
64:These theorems belong to a larger class of
9210:Understanding and Using Linear Programming
9077:{\displaystyle y_{j}\geq 0,\,s_{i}\geq 0,}
8490:{\displaystyle y_{j}\geq 0,\,s_{i}\geq 0,}
8376:{\displaystyle x_{i}\geq 0,\,t_{j}\geq 0,}
7756:{\displaystyle x_{i}\geq 0,\,t_{j}\geq 0,}
2772:; this proves that the optimum is at most
2394:subject to " and the dual LP is "minimize
2387:Below, suppose the primal LP is "maximize
2277:This is called a "symmetric" dual problem
9054:
8467:
8353:
7733:
5156:
4423:
3050:
2417:of the primal and each feasible solution
2153:
1783:
1266:
9271:Linear programming and economic analysis
9240:Springer Texts in Electrical Engineering
7306:
3567:
3553:{\displaystyle 7y_{1}\geq 3x_{1}+4x_{2}}
3078:is minimized to its lower bound (0) and
9267:
4854:{\displaystyle y_{L},y_{F},y_{P}\geq 0}
2382:
1549:The dual LP is constructed as follows.
9454:
9199:
9197:
9195:
9193:
9191:
9189:
9187:
4789:(the farmer must receive no less than
4682:(the farmer must receive no less than
3940:(cannot use more land than available)
2413:says that, for each feasible solution
2204:
75:
5250:
2160:{\displaystyle x_{i}\in \mathbb {R} }
1790:{\displaystyle y_{j}\in \mathbb {R} }
1273:{\displaystyle x_{i}\in \mathbb {R} }
928:{\displaystyle (A^{T}y)_{i}<c_{i}}
31:) LP in the following schematic way:
5243:outputs from set input unit prices.
1179:– it should be either non-negative (
1016:{\displaystyle A^{T}y\geq c,y\geq 0}
80:Suppose we have the linear program:
9184:
5417:{\displaystyle -x_{1}+x_{2}\leq -2}
3757:) to grow if their sell prices are
1596:{\displaystyle y_{1},\ldots ,y_{m}}
1138:{\displaystyle x_{1},\ldots ,x_{n}}
13:
9380:
5468:{\displaystyle x_{1},x_{2}\geq 0.}
1800:The dual objective function is
14:
9473:
9296:
8634:
7855:
7313:
5360:{\displaystyle x_{1}-x_{2}\leq 1}
4483:For the dual problem assume that
4145:{\displaystyle x_{1},x_{2}\geq 0}
3931:{\displaystyle x_{1}+x_{2}\leq L}
3700:units of pesticide must be used.
3563:
2555:
195:be its production schedule (make
163:
16:Mathematical optimization concept
7259:
7253:
7179:
7165:
7156:
7145:
7055:
7044:
6939:
6890:
6813:
6733:
6684:
6652:
6643:
6632:
6607:
6602:
6556:
6545:
6531:
6501:
6490:
6442:
6426:
6396:
6373:
6343:
6336:
6316:
6299:
6269:
6262:
6248:
6223:
6191:
6185:
6177:
6163:
6154:
6143:
6125:
6114:
6085:
6056:
6047:
6039:
6031:
6023:
6012:
6004:
5996:
5988:
5980:
5968:
5960:
5952:
5944:
5933:
5918:
5910:
5902:
5894:
5883:
5854:
5832:
5807:
5785:
5756:
5750:
5739:
5734:
5725:
5714:
5702:
5691:
5639:
5617:
5602:{\displaystyle \mathbf {p} ^{T}}
5589:
5559:
5547:
5542:
5527:
5515:
5504:
114:in the constraints are at least
66:duality theorems in optimization
7280:
6991:
6936:
5777:where the economic meanings of
2785:
2404:
9426:
9399:
9374:
9355:
9344:The Review of Economic Studies
9335:
9261:
9227:
7240:
7219:
7207:
7186:
7175:
7169:
7137:
7111:
7105:
7071:
7065:
7059:
6979:
6952:
6924:
6903:
6743:
6737:
6233:
6227:
6173:
6167:
6135:
6129:
6077:where the economic meaning of
6051:
6027:
6008:
5984:
5972:
5948:
5922:
5898:
3453:
3421:
3254:
3222:
1975:, where the symbol before the
903:
886:
315:). The constraints it has are
1:
9177:
9016:{\displaystyle 1\leq j\leq n}
8876:{\displaystyle 1\leq i\leq m}
8597: + ... +
8315:{\displaystyle 1\leq i\leq m}
8136:{\displaystyle 1\leq j\leq n}
7695:{\displaystyle 1\leq i\leq m}
7555:{\displaystyle 1\leq j\leq n}
4869:In matrix form this becomes:
4863:(prices cannot be negative).
4160:In matrix form this becomes:
3141:{\displaystyle 3x_{1}+4x_{2}}
1369:constraints. Each constraint
9234:Sakarovitch, Michel (1983),
6092:{\displaystyle \mathbf {u} }
5868:as matrix-valued functions:
5861:{\displaystyle \mathbf {B} }
5839:{\displaystyle \mathbf {A} }
5814:{\displaystyle \mathbf {z} }
5792:{\displaystyle \mathbf {p} }
5646:{\displaystyle \mathbf {A} }
5624:{\displaystyle \mathbf {z} }
5308:{\displaystyle 2x_{1}-x_{2}}
1458:where the symbol before the
586:{\displaystyle A^{T}y\geq c}
59:and the two optima are equal
50:of the dual and primal LPs.
7:
9145:
8625:. This sum must be at most
2780:
2095:{\displaystyle x_{i}\geq 0}
2032:{\displaystyle x_{i}\leq 0}
1725:{\displaystyle y_{j}\geq 0}
1662:{\displaystyle y_{j}\leq 0}
1238:{\displaystyle x_{i}\leq 0}
1205:{\displaystyle x_{i}\geq 0}
10:
9478:
9172:Relaxation (approximation)
2125:{\displaystyle \geq c_{i}}
2062:{\displaystyle \leq c_{i}}
1692:{\displaystyle \leq b_{j}}
1629:{\displaystyle \geq b_{j}}
1283:An objective function:
8640:
7861:
7319:
5271:
4507:
3816:
2724:), then by weak duality,
9268:Dorfman, Robert (1987).
9167:Semidefinite programming
3673:units of fertilizer and
3619:units of fertilizer and
2614:Theoretical implications
1087:Constructing the dual LP
1023:, but does not minimize
510:(a unit of raw material
8632:. As a result, we get:
2606:Another proof uses the
872:{\displaystyle y\geq 0}
723:and raw material stock
612:{\displaystyle y\geq 0}
380:{\displaystyle A\geq 0}
334:{\displaystyle x\geq 0}
261:{\displaystyle c\geq 0}
9162:Duality (optimization)
9131:
9078:
9017:
8982:
8938:
8877:
8842:
8775:
8736:
8711:
8667:
8544:
8491:
8430:
8377:
8316:
8281:
8211:
8137:
8102:
7996:
7957:
7932:
7888:
7810:
7757:
7696:
7661:
7617:
7556:
7521:
7454:
7415:
7390:
7346:
7272:
7020:
6870:
6799:
6719:
6668:
6572:
6465:
6412:
6359:
6285:
6204:
6093:
6069:
5862:
5840:
5815:
5793:
5769:
5667:
5647:
5625:
5603:
5572:
5469:
5418:
5361:
5309:
5221:
4967:
4855:
4781:
4674:
4573:
4474:
4253:
4146:
4092:
4012:
3932:
3877:
3805:
3778:
3751:
3724:
3694:
3667:
3640:
3613:
3577:
3554:
3492:
3395:
3336:
3277:
3196:
3169:
3142:
3062:
2934:
2714:
2665:
2593:
2562:strong duality theorem
2550:
2191:
2190:{\displaystyle =c_{i}}
2161:
2126:
2096:
2063:
2033:
1996:
1969:
1874:
1791:
1756:
1755:{\displaystyle =b_{j}}
1726:
1693:
1663:
1630:
1597:
1539:
1519:
1499:
1479:
1452:
1357:
1274:
1245:), or unconstrained (
1239:
1206:
1169:
1139:
1074:
1047:
1046:{\displaystyle b^{T}y}
1017:
969:
949:
929:
873:
844:
824:
804:
784:
757:
737:
717:
693:
647:
613:
587:
551:
524:
504:
488:
451:
437:units of raw material
431:
430:{\displaystyle A_{ji}}
401:
381:
355:
335:
309:
282:
262:
236:
216:
189:
156:This LP is called the
154:
108:
55:strong duality theorem
9433:A. A. Ahmadi (2016).
9132:
9079:
9018:
8983:
8918:
8878:
8843:
8755:
8737:
8691:
8647:
8545:
8492:
8431:
8378:
8317:
8282:
8191:
8138:
8103:
7976:
7958:
7912:
7868:
7811:
7758:
7697:
7662:
7597:
7557:
7522:
7434:
7416:
7370:
7326:
7307:Alternative algorithm
7273:
7021:
6871:
6800:
6720:
6669:
6573:
6466:
6413:
6360:
6286:
6205:
6094:
6070:
5863:
5841:
5816:
5794:
5770:
5668:
5666:{\displaystyle \rho }
5648:
5626:
5604:
5573:
5470:
5419:
5362:
5310:
5222:
4968:
4856:
4782:
4675:
4574:
4475:
4254:
4147:
4093:
4013:
3933:
3878:
3806:
3804:{\displaystyle S_{2}}
3779:
3777:{\displaystyle S_{1}}
3752:
3750:{\displaystyle x_{2}}
3725:
3723:{\displaystyle x_{1}}
3695:
3693:{\displaystyle P_{2}}
3668:
3666:{\displaystyle F_{2}}
3641:
3639:{\displaystyle P_{1}}
3614:
3612:{\displaystyle F_{1}}
3571:
3555:
3493:
3396:
3337:
3278:
3197:
3195:{\displaystyle y_{1}}
3170:
3168:{\displaystyle y_{1}}
3143:
3063:
2935:
2666:
2658:
2566:
2523:
2521:Weak duality implies:
2192:
2162:
2127:
2097:
2064:
2034:
2006:in the primal LP. So
1997:
1995:{\displaystyle c_{i}}
1970:
1875:
1792:
1757:
1727:
1694:
1664:
1631:
1598:
1540:
1520:
1518:{\displaystyle \leq }
1500:
1498:{\displaystyle \geq }
1480:
1478:{\displaystyle b_{j}}
1453:
1358:
1275:
1240:
1212:), or non-positive (
1207:
1170:
1168:{\displaystyle x_{i}}
1140:
1075:
1073:{\displaystyle y^{*}}
1048:
1018:
970:
950:
930:
874:
845:
825:
805:
785:
783:{\displaystyle y^{*}}
758:
738:
718:
694:
692:{\displaystyle y^{*}}
621:
614:
588:
552:
550:{\displaystyle y_{i}}
525:
505:
462:
452:
432:
402:
382:
356:
336:
310:
308:{\displaystyle c_{i}}
283:
263:
237:
217:
215:{\displaystyle x_{i}}
190:
128:
82:
9442:Princeton University
9212:. Berlin: Springer.
9091:
9032:
8995:
8892:
8855:
8752:
8644:
8504:
8445:
8390:
8331:
8294:
8152:
8115:
7973:
7865:
7770:
7711:
7674:
7571:
7534:
7431:
7323:
7035:
6885:
6809:
6729:
6680:
6583:
6477:
6422:
6369:
6295:
6219:
6105:
6081:
5874:
5850:
5828:
5803:
5781:
5682:
5657:
5653:, respectively, and
5635:
5613:
5584:
5495:
5433:
5376:
5325:
5276:
4979:
4877:
4806:
4699:
4592:
4512:
4265:
4168:
4110:
4030:
3950:
3896:
3821:
3788:
3761:
3734:
3707:
3677:
3650:
3623:
3596:
3502:
3405:
3346:
3287:
3206:
3179:
3152:
3106:
2950:
2797:
2411:weak duality theorem
2383:The duality theorems
2171:
2136:
2106:
2073:
2043:
2010:
1979:
1894:
1804:
1766:
1736:
1703:
1673:
1640:
1610:
1561:
1529:
1509:
1489:
1462:
1377:
1287:
1249:
1216:
1183:
1152:
1103:
1057:
1027:
979:
959:
939:
883:
857:
834:
814:
794:
767:
747:
727:
707:
676:
597:
561:
534:
514:
494:
441:
411:
391:
365:
345:
319:
292:
272:
246:
226:
199:
179:
47:weak duality theorem
5673:is the eigenvalue.
2598:One proof uses the
2205:Vector formulations
170:resource allocation
76:Form of the dual LP
9462:Linear programming
9127:
9074:
9013:
8978:
8873:
8838:
8732:
8540:
8487:
8426:
8373:
8312:
8277:
8133:
8098:
7953:
7806:
7753:
7692:
7657:
7552:
7517:
7411:
7268:
7266:
7016:
6866:
6860:
6795:
6789:
6715:
6709:
6664:
6658:
6613:
6568:
6562:
6512:
6461:
6455:
6408:
6402:
6355:
6349:
6281:
6275:
6200:
6198:
6089:
6065:
6063:
5858:
5836:
5811:
5789:
5765:
5763:
5663:
5643:
5621:
5599:
5568:
5566:
5465:
5414:
5357:
5305:
5251:Infeasible program
5217:
5205:
5147:
5104:
5050:
4963:
4957:
4903:
4851:
4777:
4670:
4569:
4470:
4458:
4414:
4378:
4338:
4249:
4243:
4203:
4142:
4088:
4008:
3928:
3873:
3801:
3774:
3747:
3720:
3690:
3663:
3636:
3609:
3578:
3550:
3488:
3391:
3332:
3273:
3192:
3165:
3138:
3058:
3056:
2930:
2928:
2187:
2157:
2122:
2092:
2059:
2029:
1992:
1965:
1870:
1787:
1752:
1722:
1689:
1659:
1626:
1593:
1535:
1515:
1495:
1475:
1448:
1353:
1270:
1235:
1202:
1165:
1148:For each variable
1135:
1070:
1043:
1013:
965:
945:
925:
869:
840:
820:
800:
780:
753:
733:
713:
689:
609:
583:
547:
520:
500:
447:
427:
397:
377:
351:
331:
305:
278:
258:
232:
212:
185:
9392:978-7-5218-0422-5
9249:978-0-387-90829-8
9140:
9139:
8553:
8552:
7819:
7818:
5478:
5477:
4867:
4866:
4158:
4157:
2984:
2960:
2847:
2807:
2600:simplex algorithm
2380:
2379:
1820:
1817:
1814:
1810:
1538:{\displaystyle =}
1303:
1300:
1297:
1293:
1099:variables:
968:{\displaystyle i}
948:{\displaystyle i}
843:{\displaystyle c}
823:{\displaystyle b}
803:{\displaystyle A}
756:{\displaystyle c}
736:{\displaystyle b}
716:{\displaystyle A}
523:{\displaystyle i}
503:{\displaystyle y}
450:{\displaystyle j}
400:{\displaystyle i}
354:{\displaystyle b}
281:{\displaystyle i}
235:{\displaystyle i}
188:{\displaystyle x}
160:the original LP.
9469:
9446:
9445:
9439:
9430:
9424:
9423:
9418:
9417:
9411:CRAN - R Project
9403:
9397:
9396:
9378:
9372:
9371:
9359:
9353:
9351:
9339:
9333:
9332:
9300:
9294:
9293:
9265:
9259:
9258:
9257:
9256:
9231:
9225:
9223:
9204:Gärtner, Bernd;
9201:
9136:
9134:
9133:
9128:
9083:
9081:
9080:
9075:
9064:
9063:
9044:
9043:
9022:
9020:
9019:
9014:
8987:
8985:
8984:
8979:
8974:
8973:
8961:
8960:
8951:
8950:
8937:
8932:
8914:
8913:
8904:
8903:
8882:
8880:
8879:
8874:
8847:
8845:
8844:
8839:
8834:
8833:
8821:
8820:
8811:
8810:
8798:
8797:
8788:
8787:
8774:
8769:
8741:
8739:
8738:
8733:
8731:
8730:
8721:
8720:
8710:
8705:
8687:
8686:
8677:
8676:
8666:
8661:
8635:
8549:
8547:
8546:
8541:
8496:
8494:
8493:
8488:
8477:
8476:
8457:
8456:
8435:
8433:
8432:
8427:
8382:
8380:
8379:
8374:
8363:
8362:
8343:
8342:
8321:
8319:
8318:
8313:
8286:
8284:
8283:
8278:
8273:
8272:
8260:
8259:
8247:
8246:
8234:
8233:
8224:
8223:
8210:
8205:
8187:
8186:
8174:
8173:
8164:
8163:
8142:
8140:
8139:
8134:
8107:
8105:
8104:
8099:
8094:
8093:
8081:
8080:
8068:
8067:
8055:
8054:
8045:
8044:
8032:
8031:
8019:
8018:
8009:
8008:
7995:
7990:
7962:
7960:
7959:
7954:
7952:
7951:
7942:
7941:
7931:
7926:
7908:
7907:
7898:
7897:
7887:
7882:
7856:
7837:dual variables:
7815:
7813:
7812:
7807:
7762:
7760:
7759:
7754:
7743:
7742:
7723:
7722:
7701:
7699:
7698:
7693:
7666:
7664:
7663:
7658:
7653:
7652:
7640:
7639:
7630:
7629:
7616:
7611:
7593:
7592:
7583:
7582:
7561:
7559:
7558:
7553:
7526:
7524:
7523:
7518:
7513:
7512:
7500:
7499:
7490:
7489:
7477:
7476:
7467:
7466:
7453:
7448:
7420:
7418:
7417:
7412:
7410:
7409:
7400:
7399:
7389:
7384:
7366:
7365:
7356:
7355:
7345:
7340:
7314:
7277:
7275:
7274:
7269:
7267:
7263:
7262:
7256:
7248:
7247:
7229:
7215:
7214:
7196:
7182:
7168:
7159:
7154:
7153:
7148:
7133:
7101:
7081:
7058:
7053:
7052:
7047:
7025:
7023:
7022:
7017:
7012:
7001:
7000:
6987:
6986:
6968:
6948:
6947:
6942:
6932:
6931:
6919:
6899:
6898:
6893:
6875:
6873:
6872:
6867:
6865:
6864:
6816:
6804:
6802:
6801:
6796:
6794:
6793:
6736:
6724:
6722:
6721:
6716:
6714:
6713:
6687:
6673:
6671:
6670:
6665:
6663:
6662:
6655:
6646:
6641:
6640:
6635:
6618:
6617:
6610:
6605:
6577:
6575:
6574:
6569:
6567:
6566:
6559:
6554:
6553:
6548:
6540:
6539:
6534:
6517:
6516:
6504:
6499:
6498:
6493:
6470:
6468:
6467:
6462:
6460:
6459:
6445:
6429:
6417:
6415:
6414:
6409:
6407:
6406:
6399:
6376:
6364:
6362:
6361:
6356:
6354:
6353:
6346:
6339:
6325:
6324:
6319:
6302:
6290:
6288:
6287:
6282:
6280:
6279:
6272:
6265:
6251:
6226:
6209:
6207:
6206:
6201:
6199:
6195:
6194:
6188:
6180:
6166:
6157:
6152:
6151:
6146:
6128:
6123:
6122:
6117:
6098:
6096:
6095:
6090:
6088:
6074:
6072:
6071:
6066:
6064:
6060:
6059:
6050:
6042:
6034:
6026:
6015:
6007:
5999:
5991:
5983:
5971:
5963:
5955:
5947:
5942:
5941:
5936:
5921:
5913:
5905:
5897:
5892:
5891:
5886:
5867:
5865:
5864:
5859:
5857:
5845:
5843:
5842:
5837:
5835:
5820:
5818:
5817:
5812:
5810:
5798:
5796:
5795:
5790:
5788:
5774:
5772:
5771:
5766:
5764:
5760:
5759:
5753:
5742:
5737:
5728:
5723:
5722:
5717:
5705:
5700:
5699:
5694:
5672:
5670:
5669:
5664:
5652:
5650:
5649:
5644:
5642:
5630:
5628:
5627:
5622:
5620:
5608:
5606:
5605:
5600:
5598:
5597:
5592:
5577:
5575:
5574:
5569:
5567:
5563:
5562:
5550:
5545:
5536:
5535:
5530:
5518:
5513:
5512:
5507:
5474:
5472:
5471:
5466:
5458:
5457:
5445:
5444:
5423:
5421:
5420:
5415:
5404:
5403:
5391:
5390:
5366:
5364:
5363:
5358:
5350:
5349:
5337:
5336:
5314:
5312:
5311:
5306:
5304:
5303:
5291:
5290:
5269:
5268:
5226:
5224:
5223:
5218:
5210:
5209:
5202:
5201:
5188:
5187:
5174:
5173:
5152:
5151:
5144:
5143:
5130:
5129:
5109:
5108:
5101:
5100:
5087:
5086:
5073:
5072:
5055:
5054:
5047:
5046:
5035:
5034:
5016:
5015:
5004:
5003:
4972:
4970:
4969:
4964:
4962:
4961:
4954:
4953:
4940:
4939:
4926:
4925:
4908:
4907:
4860:
4858:
4857:
4852:
4844:
4843:
4831:
4830:
4818:
4817:
4796:for his barley)
4786:
4784:
4783:
4778:
4776:
4775:
4763:
4762:
4750:
4749:
4737:
4736:
4724:
4723:
4711:
4710:
4679:
4677:
4676:
4671:
4669:
4668:
4656:
4655:
4643:
4642:
4630:
4629:
4617:
4616:
4604:
4603:
4578:
4576:
4575:
4570:
4568:
4567:
4549:
4548:
4530:
4529:
4505:
4504:
4479:
4477:
4476:
4471:
4463:
4462:
4455:
4454:
4441:
4440:
4419:
4418:
4383:
4382:
4375:
4374:
4361:
4360:
4343:
4342:
4335:
4334:
4323:
4322:
4309:
4308:
4297:
4296:
4258:
4256:
4255:
4250:
4248:
4247:
4240:
4239:
4226:
4225:
4208:
4207:
4200:
4199:
4188:
4187:
4151:
4149:
4148:
4143:
4135:
4134:
4122:
4121:
4097:
4095:
4094:
4089:
4081:
4080:
4068:
4067:
4055:
4054:
4042:
4041:
4017:
4015:
4014:
4009:
4001:
4000:
3988:
3987:
3975:
3974:
3962:
3961:
3937:
3935:
3934:
3929:
3921:
3920:
3908:
3907:
3882:
3880:
3879:
3874:
3872:
3871:
3859:
3858:
3846:
3845:
3833:
3832:
3814:
3813:
3810:
3808:
3807:
3802:
3800:
3799:
3783:
3781:
3780:
3775:
3773:
3772:
3756:
3754:
3753:
3748:
3746:
3745:
3729:
3727:
3726:
3721:
3719:
3718:
3699:
3697:
3696:
3691:
3689:
3688:
3672:
3670:
3669:
3664:
3662:
3661:
3645:
3643:
3642:
3637:
3635:
3634:
3618:
3616:
3615:
3610:
3608:
3607:
3559:
3557:
3556:
3551:
3549:
3548:
3533:
3532:
3517:
3516:
3497:
3495:
3494:
3489:
3487:
3486:
3471:
3470:
3452:
3451:
3436:
3435:
3417:
3416:
3400:
3398:
3397:
3392:
3390:
3389:
3374:
3373:
3358:
3357:
3341:
3339:
3338:
3333:
3331:
3330:
3315:
3314:
3299:
3298:
3282:
3280:
3279:
3274:
3272:
3271:
3253:
3252:
3237:
3236:
3218:
3217:
3201:
3199:
3198:
3193:
3191:
3190:
3174:
3172:
3171:
3166:
3164:
3163:
3147:
3145:
3144:
3139:
3137:
3136:
3121:
3120:
3067:
3065:
3064:
3059:
3057:
3053:
3045:
3044:
3034:
3024:
3023:
3010:
3000:
2999:
2985:
2983:subject to
2982:
2976:
2975:
2961:
2958:
2939:
2937:
2936:
2931:
2929:
2919:
2918:
2900:
2899:
2889:
2879:
2878:
2863:
2862:
2848:
2846:subject to
2845:
2839:
2838:
2823:
2822:
2808:
2805:
2213:
2212:
2196:
2194:
2193:
2188:
2186:
2185:
2166:
2164:
2163:
2158:
2156:
2148:
2147:
2131:
2129:
2128:
2123:
2121:
2120:
2101:
2099:
2098:
2093:
2085:
2084:
2068:
2066:
2065:
2060:
2058:
2057:
2038:
2036:
2035:
2030:
2022:
2021:
2001:
1999:
1998:
1993:
1991:
1990:
1974:
1972:
1971:
1966:
1964:
1963:
1951:
1950:
1941:
1940:
1919:
1918:
1909:
1908:
1879:
1877:
1876:
1871:
1869:
1868:
1859:
1858:
1840:
1839:
1830:
1829:
1818:
1815:
1812:
1811:
1808:
1796:
1794:
1793:
1788:
1786:
1778:
1777:
1761:
1759:
1758:
1753:
1751:
1750:
1731:
1729:
1728:
1723:
1715:
1714:
1698:
1696:
1695:
1690:
1688:
1687:
1668:
1666:
1665:
1660:
1652:
1651:
1635:
1633:
1632:
1627:
1625:
1624:
1602:
1600:
1599:
1594:
1592:
1591:
1573:
1572:
1544:
1542:
1541:
1536:
1524:
1522:
1521:
1516:
1504:
1502:
1501:
1496:
1484:
1482:
1481:
1476:
1474:
1473:
1457:
1455:
1454:
1449:
1447:
1446:
1434:
1433:
1424:
1423:
1402:
1401:
1392:
1391:
1362:
1360:
1359:
1354:
1352:
1351:
1342:
1341:
1323:
1322:
1313:
1312:
1301:
1298:
1295:
1294:
1291:
1279:
1277:
1276:
1271:
1269:
1261:
1260:
1244:
1242:
1241:
1236:
1228:
1227:
1211:
1209:
1208:
1203:
1195:
1194:
1174:
1172:
1171:
1166:
1164:
1163:
1144:
1142:
1141:
1136:
1134:
1133:
1115:
1114:
1079:
1077:
1076:
1071:
1069:
1068:
1052:
1050:
1049:
1044:
1039:
1038:
1022:
1020:
1019:
1014:
991:
990:
974:
972:
971:
966:
954:
952:
951:
946:
934:
932:
931:
926:
924:
923:
911:
910:
898:
897:
878:
876:
875:
870:
849:
847:
846:
841:
829:
827:
826:
821:
809:
807:
806:
801:
789:
787:
786:
781:
779:
778:
762:
760:
759:
754:
742:
740:
739:
734:
722:
720:
719:
714:
698:
696:
695:
690:
688:
687:
618:
616:
615:
610:
592:
590:
589:
584:
573:
572:
556:
554:
553:
548:
546:
545:
529:
527:
526:
521:
509:
507:
506:
501:
456:
454:
453:
448:
436:
434:
433:
428:
426:
425:
406:
404:
403:
398:
386:
384:
383:
378:
360:
358:
357:
352:
340:
338:
337:
332:
314:
312:
311:
306:
304:
303:
287:
285:
284:
279:
267:
265:
264:
259:
241:
239:
238:
233:
221:
219:
218:
213:
211:
210:
194:
192:
191:
186:
9477:
9476:
9472:
9471:
9470:
9468:
9467:
9466:
9452:
9451:
9450:
9449:
9437:
9431:
9427:
9415:
9413:
9405:
9404:
9400:
9393:
9381:Li, Wu (2019).
9379:
9375:
9360:
9356:
9340:
9336:
9322:
9312:Matching Theory
9301:
9297:
9282:
9266:
9262:
9254:
9252:
9250:
9232:
9228:
9220:
9202:
9185:
9180:
9148:
9092:
9089:
9088:
9059:
9055:
9039:
9035:
9033:
9030:
9029:
8996:
8993:
8992:
8969:
8965:
8956:
8952:
8943:
8939:
8933:
8922:
8909:
8905:
8899:
8895:
8893:
8890:
8889:
8856:
8853:
8852:
8829:
8825:
8816:
8812:
8806:
8802:
8793:
8789:
8780:
8776:
8770:
8759:
8753:
8750:
8749:
8726:
8722:
8716:
8712:
8706:
8695:
8682:
8678:
8672:
8668:
8662:
8651:
8645:
8642:
8641:
8631:
8624:
8618:
8611:
8603:
8596:
8590:
8583:
8577:
8566:
8505:
8502:
8501:
8472:
8468:
8452:
8448:
8446:
8443:
8442:
8391:
8388:
8387:
8358:
8354:
8338:
8334:
8332:
8329:
8328:
8295:
8292:
8291:
8268:
8264:
8255:
8251:
8242:
8238:
8229:
8225:
8216:
8212:
8206:
8195:
8182:
8178:
8169:
8165:
8159:
8155:
8153:
8150:
8149:
8116:
8113:
8112:
8089:
8085:
8076:
8072:
8063:
8059:
8050:
8046:
8040:
8036:
8027:
8023:
8014:
8010:
8001:
7997:
7991:
7980:
7974:
7971:
7970:
7947:
7943:
7937:
7933:
7927:
7916:
7903:
7899:
7893:
7889:
7883:
7872:
7866:
7863:
7862:
7852:
7843:
7771:
7768:
7767:
7738:
7734:
7718:
7714:
7712:
7709:
7708:
7675:
7672:
7671:
7648:
7644:
7635:
7631:
7622:
7618:
7612:
7601:
7588:
7584:
7578:
7574:
7572:
7569:
7568:
7535:
7532:
7531:
7508:
7504:
7495:
7491:
7485:
7481:
7472:
7468:
7459:
7455:
7449:
7438:
7432:
7429:
7428:
7405:
7401:
7395:
7391:
7385:
7374:
7361:
7357:
7351:
7347:
7341:
7330:
7324:
7321:
7320:
7309:
7301:Minimax theorem
7294:Konig's theorem
7283:
7265:
7264:
7258:
7257:
7252:
7243:
7239:
7225:
7210:
7206:
7192:
7178:
7164:
7161:
7160:
7155:
7149:
7144:
7143:
7129:
7097:
7077:
7054:
7048:
7043:
7042:
7038:
7036:
7033:
7032:
7008:
6996:
6992:
6982:
6978:
6964:
6943:
6938:
6937:
6927:
6923:
6915:
6894:
6889:
6888:
6886:
6883:
6882:
6859:
6858:
6853:
6848:
6842:
6841:
6836:
6831:
6821:
6820:
6812:
6810:
6807:
6806:
6788:
6787:
6782:
6777:
6771:
6770:
6765:
6760:
6750:
6749:
6732:
6730:
6727:
6726:
6708:
6707:
6702:
6692:
6691:
6683:
6681:
6678:
6677:
6657:
6656:
6651:
6648:
6647:
6642:
6636:
6631:
6630:
6623:
6622:
6612:
6611:
6606:
6601:
6598:
6597:
6587:
6586:
6584:
6581:
6580:
6561:
6560:
6555:
6549:
6544:
6543:
6541:
6535:
6530:
6529:
6522:
6521:
6511:
6510:
6505:
6500:
6494:
6489:
6488:
6481:
6480:
6478:
6475:
6474:
6454:
6453:
6447:
6446:
6441:
6434:
6433:
6425:
6423:
6420:
6419:
6401:
6400:
6395:
6392:
6391:
6381:
6380:
6372:
6370:
6367:
6366:
6348:
6347:
6342:
6340:
6335:
6332:
6331:
6326:
6320:
6315:
6314:
6307:
6306:
6298:
6296:
6293:
6292:
6274:
6273:
6268:
6266:
6261:
6258:
6257:
6252:
6247:
6240:
6239:
6222:
6220:
6217:
6216:
6197:
6196:
6190:
6189:
6184:
6176:
6162:
6159:
6158:
6153:
6147:
6142:
6141:
6124:
6118:
6113:
6112:
6108:
6106:
6103:
6102:
6084:
6082:
6079:
6078:
6062:
6061:
6055:
6054:
6046:
6038:
6030:
6022:
6011:
6003:
5995:
5987:
5979:
5976:
5975:
5967:
5959:
5951:
5943:
5937:
5932:
5931:
5917:
5909:
5901:
5893:
5887:
5882:
5881:
5877:
5875:
5872:
5871:
5853:
5851:
5848:
5847:
5831:
5829:
5826:
5825:
5806:
5804:
5801:
5800:
5784:
5782:
5779:
5778:
5762:
5761:
5755:
5754:
5749:
5738:
5733:
5730:
5729:
5724:
5718:
5713:
5712:
5701:
5695:
5690:
5689:
5685:
5683:
5680:
5679:
5658:
5655:
5654:
5638:
5636:
5633:
5632:
5616:
5614:
5611:
5610:
5593:
5588:
5587:
5585:
5582:
5581:
5565:
5564:
5558:
5557:
5546:
5541:
5538:
5537:
5531:
5526:
5525:
5514:
5508:
5503:
5502:
5498:
5496:
5493:
5492:
5483:
5453:
5449:
5440:
5436:
5434:
5431:
5430:
5399:
5395:
5386:
5382:
5377:
5374:
5373:
5345:
5341:
5332:
5328:
5326:
5323:
5322:
5299:
5295:
5286:
5282:
5277:
5274:
5273:
5253:
5204:
5203:
5197:
5193:
5190:
5189:
5183:
5179:
5176:
5175:
5169:
5165:
5158:
5157:
5146:
5145:
5139:
5135:
5132:
5131:
5125:
5121:
5114:
5113:
5103:
5102:
5096:
5092:
5089:
5088:
5082:
5078:
5075:
5074:
5068:
5064:
5057:
5056:
5049:
5048:
5042:
5038:
5036:
5030:
5026:
5024:
5018:
5017:
5011:
5007:
5005:
4999:
4995:
4993:
4983:
4982:
4980:
4977:
4976:
4956:
4955:
4949:
4945:
4942:
4941:
4935:
4931:
4928:
4927:
4921:
4917:
4910:
4909:
4902:
4901:
4896:
4891:
4881:
4880:
4878:
4875:
4874:
4839:
4835:
4826:
4822:
4813:
4809:
4807:
4804:
4803:
4795:
4771:
4767:
4758:
4754:
4745:
4741:
4732:
4728:
4719:
4715:
4706:
4702:
4700:
4697:
4696:
4689:for his wheat)
4688:
4664:
4660:
4651:
4647:
4638:
4634:
4625:
4621:
4612:
4608:
4599:
4595:
4593:
4590:
4589:
4563:
4559:
4544:
4540:
4525:
4521:
4513:
4510:
4509:
4501:
4494:
4457:
4456:
4450:
4446:
4443:
4442:
4436:
4432:
4425:
4424:
4413:
4412:
4406:
4405:
4399:
4398:
4388:
4387:
4377:
4376:
4370:
4366:
4363:
4362:
4356:
4352:
4345:
4344:
4337:
4336:
4330:
4326:
4324:
4318:
4314:
4311:
4310:
4304:
4300:
4298:
4292:
4288:
4285:
4284:
4279:
4269:
4268:
4266:
4263:
4262:
4242:
4241:
4235:
4231:
4228:
4227:
4221:
4217:
4210:
4209:
4202:
4201:
4195:
4191:
4189:
4183:
4179:
4172:
4171:
4169:
4166:
4165:
4130:
4126:
4117:
4113:
4111:
4108:
4107:
4076:
4072:
4063:
4059:
4050:
4046:
4037:
4033:
4031:
4028:
4027:
3996:
3992:
3983:
3979:
3970:
3966:
3957:
3953:
3951:
3948:
3947:
3916:
3912:
3903:
3899:
3897:
3894:
3893:
3867:
3863:
3854:
3850:
3841:
3837:
3828:
3824:
3822:
3819:
3818:
3795:
3791:
3789:
3786:
3785:
3768:
3764:
3762:
3759:
3758:
3741:
3737:
3735:
3732:
3731:
3714:
3710:
3708:
3705:
3704:
3684:
3680:
3678:
3675:
3674:
3657:
3653:
3651:
3648:
3647:
3630:
3626:
3624:
3621:
3620:
3603:
3599:
3597:
3594:
3593:
3588:fertilizer and
3574:feasible region
3566:
3544:
3540:
3528:
3524:
3512:
3508:
3503:
3500:
3499:
3482:
3478:
3466:
3462:
3447:
3443:
3431:
3427:
3412:
3408:
3406:
3403:
3402:
3385:
3381:
3369:
3365:
3353:
3349:
3347:
3344:
3343:
3326:
3322:
3310:
3306:
3294:
3290:
3288:
3285:
3284:
3267:
3263:
3248:
3244:
3232:
3228:
3213:
3209:
3207:
3204:
3203:
3186:
3182:
3180:
3177:
3176:
3159:
3155:
3153:
3150:
3149:
3132:
3128:
3116:
3112:
3107:
3104:
3103:
3094:
3084:
3077:
3055:
3054:
3049:
3040:
3036:
3032:
3031:
3019:
3015:
3008:
3007:
2995:
2991:
2986:
2981:
2978:
2977:
2971:
2967:
2962:
2957:
2953:
2951:
2948:
2947:
2927:
2926:
2914:
2910:
2895:
2891:
2887:
2886:
2874:
2870:
2858:
2854:
2849:
2844:
2841:
2840:
2834:
2830:
2818:
2814:
2809:
2804:
2800:
2798:
2795:
2794:
2788:
2783:
2616:
2584:
2573:
2558:
2541:
2530:
2407:
2385:
2207:
2181:
2177:
2172:
2169:
2168:
2152:
2143:
2139:
2137:
2134:
2133:
2116:
2112:
2107:
2104:
2103:
2080:
2076:
2074:
2071:
2070:
2053:
2049:
2044:
2041:
2040:
2017:
2013:
2011:
2008:
2007:
1986:
1982:
1980:
1977:
1976:
1959:
1955:
1946:
1942:
1933:
1929:
1914:
1910:
1901:
1897:
1895:
1892:
1891:
1864:
1860:
1854:
1850:
1835:
1831:
1825:
1821:
1807:
1805:
1802:
1801:
1782:
1773:
1769:
1767:
1764:
1763:
1746:
1742:
1737:
1734:
1733:
1710:
1706:
1704:
1701:
1700:
1683:
1679:
1674:
1671:
1670:
1647:
1643:
1641:
1638:
1637:
1620:
1616:
1611:
1608:
1607:
1587:
1583:
1568:
1564:
1562:
1559:
1558:
1530:
1527:
1526:
1510:
1507:
1506:
1490:
1487:
1486:
1469:
1465:
1463:
1460:
1459:
1442:
1438:
1429:
1425:
1416:
1412:
1397:
1393:
1384:
1380:
1378:
1375:
1374:
1347:
1343:
1337:
1333:
1318:
1314:
1308:
1304:
1290:
1288:
1285:
1284:
1265:
1256:
1252:
1250:
1247:
1246:
1223:
1219:
1217:
1214:
1213:
1190:
1186:
1184:
1181:
1180:
1177:sign constraint
1159:
1155:
1153:
1150:
1149:
1129:
1125:
1110:
1106:
1104:
1101:
1100:
1089:
1064:
1060:
1058:
1055:
1054:
1034:
1030:
1028:
1025:
1024:
986:
982:
980:
977:
976:
960:
957:
956:
940:
937:
936:
919:
915:
906:
902:
893:
889:
884:
881:
880:
858:
855:
854:
835:
832:
831:
815:
812:
811:
795:
792:
791:
774:
770:
768:
765:
764:
748:
745:
744:
728:
725:
724:
708:
705:
704:
683:
679:
677:
674:
673:
598:
595:
594:
568:
564:
562:
559:
558:
541:
537:
535:
532:
531:
515:
512:
511:
495:
492:
491:
442:
439:
438:
418:
414:
412:
409:
408:
392:
389:
388:
366:
363:
362:
346:
343:
342:
320:
317:
316:
299:
295:
293:
290:
289:
273:
270:
269:
247:
244:
243:
227:
224:
223:
222:amount of good
206:
202:
200:
197:
196:
180:
177:
176:
166:
78:
17:
12:
11:
5:
9475:
9465:
9464:
9448:
9447:
9425:
9398:
9391:
9373:
9354:
9334:
9320:
9308:Plummer, M. D.
9304:Lovász, László
9295:
9280:
9260:
9248:
9226:
9218:
9206:Matoušek, Jiří
9182:
9181:
9179:
9176:
9175:
9174:
9169:
9164:
9159:
9154:
9152:Convex duality
9147:
9144:
9138:
9137:
9126:
9123:
9120:
9117:
9114:
9111:
9108:
9105:
9102:
9099:
9096:
9086:
9084:
9073:
9070:
9067:
9062:
9058:
9053:
9050:
9047:
9042:
9038:
9027:
9024:
9023:
9012:
9009:
9006:
9003:
9000:
8990:
8988:
8977:
8972:
8968:
8964:
8959:
8955:
8949:
8946:
8942:
8936:
8931:
8928:
8925:
8921:
8917:
8912:
8908:
8902:
8898:
8887:
8884:
8883:
8872:
8869:
8866:
8863:
8860:
8850:
8848:
8837:
8832:
8828:
8824:
8819:
8815:
8809:
8805:
8801:
8796:
8792:
8786:
8783:
8779:
8773:
8768:
8765:
8762:
8758:
8747:
8743:
8742:
8729:
8725:
8719:
8715:
8709:
8704:
8701:
8698:
8694:
8690:
8685:
8681:
8675:
8671:
8665:
8660:
8657:
8654:
8650:
8639:
8629:
8622:
8616:
8607:
8601:
8594:
8588:
8581:
8575:
8564:
8551:
8550:
8539:
8536:
8533:
8530:
8527:
8524:
8521:
8518:
8515:
8512:
8509:
8499:
8497:
8486:
8483:
8480:
8475:
8471:
8466:
8463:
8460:
8455:
8451:
8440:
8437:
8436:
8425:
8422:
8419:
8416:
8413:
8410:
8407:
8404:
8401:
8398:
8395:
8385:
8383:
8372:
8369:
8366:
8361:
8357:
8352:
8349:
8346:
8341:
8337:
8326:
8323:
8322:
8311:
8308:
8305:
8302:
8299:
8289:
8287:
8276:
8271:
8267:
8263:
8258:
8254:
8250:
8245:
8241:
8237:
8232:
8228:
8222:
8219:
8215:
8209:
8204:
8201:
8198:
8194:
8190:
8185:
8181:
8177:
8172:
8168:
8162:
8158:
8147:
8144:
8143:
8132:
8129:
8126:
8123:
8120:
8110:
8108:
8097:
8092:
8088:
8084:
8079:
8075:
8071:
8066:
8062:
8058:
8053:
8049:
8043:
8039:
8035:
8030:
8026:
8022:
8017:
8013:
8007:
8004:
8000:
7994:
7989:
7986:
7983:
7979:
7968:
7964:
7963:
7950:
7946:
7940:
7936:
7930:
7925:
7922:
7919:
7915:
7911:
7906:
7902:
7896:
7892:
7886:
7881:
7878:
7875:
7871:
7860:
7848:
7841:
7817:
7816:
7805:
7802:
7799:
7796:
7793:
7790:
7787:
7784:
7781:
7778:
7775:
7765:
7763:
7752:
7749:
7746:
7741:
7737:
7732:
7729:
7726:
7721:
7717:
7706:
7703:
7702:
7691:
7688:
7685:
7682:
7679:
7669:
7667:
7656:
7651:
7647:
7643:
7638:
7634:
7628:
7625:
7621:
7615:
7610:
7607:
7604:
7600:
7596:
7591:
7587:
7581:
7577:
7566:
7563:
7562:
7551:
7548:
7545:
7542:
7539:
7529:
7527:
7516:
7511:
7507:
7503:
7498:
7494:
7488:
7484:
7480:
7475:
7471:
7465:
7462:
7458:
7452:
7447:
7444:
7441:
7437:
7426:
7422:
7421:
7408:
7404:
7398:
7394:
7388:
7383:
7380:
7377:
7373:
7369:
7364:
7360:
7354:
7350:
7344:
7339:
7336:
7333:
7329:
7318:
7308:
7305:
7282:
7279:
7261:
7255:
7251:
7246:
7242:
7238:
7235:
7232:
7228:
7224:
7221:
7218:
7213:
7209:
7205:
7202:
7199:
7195:
7191:
7188:
7185:
7181:
7177:
7174:
7171:
7167:
7163:
7162:
7158:
7152:
7147:
7142:
7139:
7136:
7132:
7128:
7125:
7122:
7119:
7116:
7113:
7110:
7107:
7104:
7100:
7096:
7093:
7090:
7087:
7084:
7080:
7076:
7073:
7070:
7067:
7064:
7061:
7057:
7051:
7046:
7041:
7040:
7015:
7011:
7007:
7004:
6999:
6995:
6990:
6985:
6981:
6977:
6974:
6971:
6967:
6963:
6960:
6957:
6954:
6951:
6946:
6941:
6935:
6930:
6926:
6922:
6918:
6914:
6911:
6908:
6905:
6902:
6897:
6892:
6863:
6857:
6854:
6852:
6849:
6847:
6844:
6843:
6840:
6837:
6835:
6832:
6830:
6827:
6826:
6824:
6819:
6815:
6792:
6786:
6783:
6781:
6778:
6776:
6773:
6772:
6769:
6766:
6764:
6761:
6759:
6756:
6755:
6753:
6748:
6745:
6742:
6739:
6735:
6712:
6706:
6703:
6701:
6698:
6697:
6695:
6690:
6686:
6661:
6654:
6650:
6649:
6645:
6639:
6634:
6629:
6628:
6626:
6621:
6616:
6609:
6604:
6600:
6599:
6596:
6593:
6592:
6590:
6565:
6558:
6552:
6547:
6542:
6538:
6533:
6528:
6527:
6525:
6520:
6515:
6509:
6506:
6503:
6497:
6492:
6487:
6486:
6484:
6458:
6452:
6449:
6448:
6444:
6440:
6439:
6437:
6432:
6428:
6405:
6398:
6394:
6393:
6390:
6387:
6386:
6384:
6379:
6375:
6352:
6345:
6341:
6338:
6334:
6333:
6330:
6327:
6323:
6318:
6313:
6312:
6310:
6305:
6301:
6278:
6271:
6267:
6264:
6260:
6259:
6256:
6253:
6250:
6246:
6245:
6243:
6238:
6235:
6232:
6229:
6225:
6193:
6187:
6183:
6179:
6175:
6172:
6169:
6165:
6161:
6160:
6156:
6150:
6145:
6140:
6137:
6134:
6131:
6127:
6121:
6116:
6111:
6110:
6087:
6058:
6053:
6049:
6045:
6041:
6037:
6033:
6029:
6025:
6021:
6018:
6014:
6010:
6006:
6002:
5998:
5994:
5990:
5986:
5982:
5978:
5977:
5974:
5970:
5966:
5962:
5958:
5954:
5950:
5946:
5940:
5935:
5930:
5927:
5924:
5920:
5916:
5912:
5908:
5904:
5900:
5896:
5890:
5885:
5880:
5879:
5856:
5834:
5809:
5787:
5758:
5752:
5748:
5745:
5741:
5736:
5732:
5731:
5727:
5721:
5716:
5711:
5708:
5704:
5698:
5693:
5688:
5687:
5662:
5641:
5619:
5596:
5591:
5561:
5556:
5553:
5549:
5544:
5540:
5539:
5534:
5529:
5524:
5521:
5517:
5511:
5506:
5501:
5500:
5482:
5479:
5476:
5475:
5464:
5461:
5456:
5452:
5448:
5443:
5439:
5428:
5425:
5424:
5413:
5410:
5407:
5402:
5398:
5394:
5389:
5385:
5381:
5371:
5368:
5367:
5356:
5353:
5348:
5344:
5340:
5335:
5331:
5320:
5316:
5315:
5302:
5298:
5294:
5289:
5285:
5281:
5264:
5263:
5260:
5252:
5249:
5228:
5227:
5216:
5213:
5208:
5200:
5196:
5192:
5191:
5186:
5182:
5178:
5177:
5172:
5168:
5164:
5163:
5161:
5155:
5150:
5142:
5138:
5134:
5133:
5128:
5124:
5120:
5119:
5117:
5112:
5107:
5099:
5095:
5091:
5090:
5085:
5081:
5077:
5076:
5071:
5067:
5063:
5062:
5060:
5053:
5045:
5041:
5037:
5033:
5029:
5025:
5023:
5020:
5019:
5014:
5010:
5006:
5002:
4998:
4994:
4992:
4989:
4988:
4986:
4973:
4960:
4952:
4948:
4944:
4943:
4938:
4934:
4930:
4929:
4924:
4920:
4916:
4915:
4913:
4906:
4900:
4897:
4895:
4892:
4890:
4887:
4886:
4884:
4865:
4864:
4861:
4850:
4847:
4842:
4838:
4834:
4829:
4825:
4821:
4816:
4812:
4801:
4798:
4797:
4793:
4787:
4774:
4770:
4766:
4761:
4757:
4753:
4748:
4744:
4740:
4735:
4731:
4727:
4722:
4718:
4714:
4709:
4705:
4694:
4691:
4690:
4686:
4680:
4667:
4663:
4659:
4654:
4650:
4646:
4641:
4637:
4633:
4628:
4624:
4620:
4615:
4611:
4607:
4602:
4598:
4587:
4583:
4582:
4579:
4566:
4562:
4558:
4555:
4552:
4547:
4543:
4539:
4536:
4533:
4528:
4524:
4520:
4517:
4499:
4495:for wheat and
4492:
4481:
4480:
4469:
4466:
4461:
4453:
4449:
4445:
4444:
4439:
4435:
4431:
4430:
4428:
4422:
4417:
4411:
4408:
4407:
4404:
4401:
4400:
4397:
4394:
4393:
4391:
4386:
4381:
4373:
4369:
4365:
4364:
4359:
4355:
4351:
4350:
4348:
4341:
4333:
4329:
4325:
4321:
4317:
4313:
4312:
4307:
4303:
4299:
4295:
4291:
4287:
4286:
4283:
4280:
4278:
4275:
4274:
4272:
4259:
4246:
4238:
4234:
4230:
4229:
4224:
4220:
4216:
4215:
4213:
4206:
4198:
4194:
4190:
4186:
4182:
4178:
4177:
4175:
4156:
4155:
4152:
4141:
4138:
4133:
4129:
4125:
4120:
4116:
4105:
4102:
4101:
4098:
4087:
4084:
4079:
4075:
4071:
4066:
4062:
4058:
4053:
4049:
4045:
4040:
4036:
4025:
4022:
4021:
4018:
4007:
4004:
3999:
3995:
3991:
3986:
3982:
3978:
3973:
3969:
3965:
3960:
3956:
3945:
3942:
3941:
3938:
3927:
3924:
3919:
3915:
3911:
3906:
3902:
3891:
3887:
3886:
3883:
3870:
3866:
3862:
3857:
3853:
3849:
3844:
3840:
3836:
3831:
3827:
3798:
3794:
3771:
3767:
3744:
3740:
3730:) and barley (
3717:
3713:
3687:
3683:
3660:
3656:
3633:
3629:
3606:
3602:
3565:
3564:Farmer example
3562:
3547:
3543:
3539:
3536:
3531:
3527:
3523:
3520:
3515:
3511:
3507:
3485:
3481:
3477:
3474:
3469:
3465:
3461:
3458:
3455:
3450:
3446:
3442:
3439:
3434:
3430:
3426:
3423:
3420:
3415:
3411:
3388:
3384:
3380:
3377:
3372:
3368:
3364:
3361:
3356:
3352:
3329:
3325:
3321:
3318:
3313:
3309:
3305:
3302:
3297:
3293:
3270:
3266:
3262:
3259:
3256:
3251:
3247:
3243:
3240:
3235:
3231:
3227:
3224:
3221:
3216:
3212:
3189:
3185:
3162:
3158:
3135:
3131:
3127:
3124:
3119:
3115:
3111:
3092:
3082:
3075:
3069:
3068:
3052:
3048:
3043:
3039:
3035:
3033:
3030:
3027:
3022:
3018:
3014:
3011:
3009:
3006:
3003:
2998:
2994:
2990:
2987:
2980:
2979:
2974:
2970:
2966:
2963:
2959:minimize
2956:
2955:
2941:
2940:
2925:
2922:
2917:
2913:
2909:
2906:
2903:
2898:
2894:
2890:
2888:
2885:
2882:
2877:
2873:
2869:
2866:
2861:
2857:
2853:
2850:
2843:
2842:
2837:
2833:
2829:
2826:
2821:
2817:
2813:
2810:
2806:maximize
2803:
2802:
2787:
2784:
2782:
2779:
2778:
2777:
2766:
2615:
2612:
2582:
2569:
2557:
2556:Strong duality
2554:
2539:
2526:
2519:
2518:
2512:
2502:
2489:
2473:
2467:
2421:of the dual:
2406:
2403:
2401:subject to ".
2384:
2381:
2378:
2377:
2375:
2355:
2329:
2328:
2325:
2300:
2279:
2278:
2275:
2250:
2224:
2223:
2220:
2217:
2206:
2203:
2199:
2198:
2184:
2180:
2176:
2155:
2151:
2146:
2142:
2119:
2115:
2111:
2091:
2088:
2083:
2079:
2056:
2052:
2048:
2028:
2025:
2020:
2016:
1989:
1985:
1962:
1958:
1954:
1949:
1945:
1939:
1936:
1932:
1928:
1925:
1922:
1917:
1913:
1907:
1904:
1900:
1880:
1867:
1863:
1857:
1853:
1849:
1846:
1843:
1838:
1834:
1828:
1824:
1809:minimize
1798:
1785:
1781:
1776:
1772:
1749:
1745:
1741:
1721:
1718:
1713:
1709:
1686:
1682:
1678:
1658:
1655:
1650:
1646:
1623:
1619:
1615:
1604:
1590:
1586:
1582:
1579:
1576:
1571:
1567:
1547:
1546:
1534:
1514:
1494:
1485:can be one of
1472:
1468:
1445:
1441:
1437:
1432:
1428:
1422:
1419:
1415:
1411:
1408:
1405:
1400:
1396:
1390:
1387:
1383:
1363:
1350:
1346:
1340:
1336:
1332:
1329:
1326:
1321:
1317:
1311:
1307:
1281:
1268:
1264:
1259:
1255:
1234:
1231:
1226:
1222:
1201:
1198:
1193:
1189:
1162:
1158:
1146:
1132:
1128:
1124:
1121:
1118:
1113:
1109:
1088:
1085:
1067:
1063:
1042:
1037:
1033:
1012:
1009:
1006:
1003:
1000:
997:
994:
989:
985:
964:
944:
922:
918:
914:
909:
905:
901:
896:
892:
888:
879:are such that
868:
865:
862:
839:
819:
799:
777:
773:
752:
732:
712:
686:
682:
608:
605:
602:
582:
579:
576:
571:
567:
544:
540:
519:
499:
446:
424:
421:
417:
396:
376:
373:
370:
350:
330:
327:
324:
302:
298:
277:
257:
254:
251:
231:
209:
205:
184:
165:
164:Interpretation
162:
77:
74:
43:
42:
39:
36:
25:linear program
15:
9:
6:
4:
3:
2:
9474:
9463:
9460:
9459:
9457:
9443:
9436:
9429:
9422:
9412:
9408:
9402:
9394:
9388:
9384:
9377:
9369:
9365:
9358:
9349:
9345:
9338:
9331:
9327:
9323:
9321:0-444-87916-1
9317:
9313:
9309:
9305:
9299:
9291:
9287:
9283:
9281:0-486-65491-5
9277:
9273:
9272:
9264:
9251:
9245:
9241:
9237:
9230:
9224:Pages 81–104.
9221:
9219:3-540-30697-8
9215:
9211:
9207:
9200:
9198:
9196:
9194:
9192:
9190:
9188:
9183:
9173:
9170:
9168:
9165:
9163:
9160:
9158:
9155:
9153:
9150:
9149:
9143:
9124:
9121:
9118:
9115:
9112:
9109:
9106:
9103:
9100:
9097:
9094:
9087:
9085:
9071:
9068:
9065:
9060:
9056:
9051:
9048:
9045:
9040:
9036:
9028:
9026:
9025:
9010:
9007:
9004:
9001:
8998:
8991:
8989:
8975:
8970:
8966:
8962:
8957:
8953:
8947:
8944:
8940:
8934:
8929:
8926:
8923:
8919:
8915:
8910:
8906:
8900:
8896:
8888:
8886:
8885:
8870:
8867:
8864:
8861:
8858:
8851:
8849:
8835:
8830:
8826:
8822:
8817:
8813:
8807:
8803:
8799:
8794:
8790:
8784:
8781:
8777:
8771:
8766:
8763:
8760:
8756:
8748:
8745:
8744:
8727:
8723:
8717:
8713:
8707:
8702:
8699:
8696:
8692:
8688:
8683:
8679:
8673:
8669:
8663:
8658:
8655:
8652:
8648:
8637:
8636:
8633:
8628:
8621:
8615:
8612: +
8610:
8606:
8600:
8593:
8587:
8584: +
8580:
8574:
8570:
8563:
8559:
8537:
8534:
8531:
8528:
8525:
8522:
8519:
8516:
8513:
8510:
8507:
8500:
8498:
8484:
8481:
8478:
8473:
8469:
8464:
8461:
8458:
8453:
8449:
8441:
8439:
8438:
8423:
8420:
8417:
8414:
8411:
8408:
8405:
8402:
8399:
8396:
8393:
8386:
8384:
8370:
8367:
8364:
8359:
8355:
8350:
8347:
8344:
8339:
8335:
8327:
8325:
8324:
8309:
8306:
8303:
8300:
8297:
8290:
8288:
8274:
8269:
8265:
8261:
8256:
8252:
8248:
8243:
8239:
8235:
8230:
8226:
8220:
8217:
8213:
8207:
8202:
8199:
8196:
8192:
8188:
8183:
8179:
8175:
8170:
8166:
8160:
8156:
8148:
8146:
8145:
8130:
8127:
8124:
8121:
8118:
8111:
8109:
8095:
8090:
8086:
8082:
8077:
8073:
8069:
8064:
8060:
8056:
8051:
8047:
8041:
8037:
8033:
8028:
8024:
8020:
8015:
8011:
8005:
8002:
7998:
7992:
7987:
7984:
7981:
7977:
7969:
7966:
7965:
7948:
7944:
7938:
7934:
7928:
7923:
7920:
7917:
7913:
7909:
7904:
7900:
7894:
7890:
7884:
7879:
7876:
7873:
7869:
7858:
7857:
7854:
7851:
7847:
7840:
7836:
7833: +
7832:
7828:
7825: +
7824:
7803:
7800:
7797:
7794:
7791:
7788:
7785:
7782:
7779:
7776:
7773:
7766:
7764:
7750:
7747:
7744:
7739:
7735:
7730:
7727:
7724:
7719:
7715:
7707:
7705:
7704:
7689:
7686:
7683:
7680:
7677:
7670:
7668:
7654:
7649:
7645:
7641:
7636:
7632:
7626:
7623:
7619:
7613:
7608:
7605:
7602:
7598:
7594:
7589:
7585:
7579:
7575:
7567:
7565:
7564:
7549:
7546:
7543:
7540:
7537:
7530:
7528:
7514:
7509:
7505:
7501:
7496:
7492:
7486:
7482:
7478:
7473:
7469:
7463:
7460:
7456:
7450:
7445:
7442:
7439:
7435:
7427:
7424:
7423:
7406:
7402:
7396:
7392:
7386:
7381:
7378:
7375:
7371:
7367:
7362:
7358:
7352:
7348:
7342:
7337:
7334:
7331:
7327:
7316:
7315:
7312:
7304:
7302:
7297:
7295:
7290:
7288:
7278:
7249:
7244:
7236:
7233:
7230:
7226:
7222:
7216:
7211:
7203:
7200:
7197:
7193:
7189:
7183:
7172:
7150:
7140:
7134:
7130:
7126:
7123:
7120:
7117:
7114:
7108:
7102:
7098:
7094:
7091:
7088:
7085:
7082:
7078:
7074:
7068:
7062:
7049:
7029:
7026:
7013:
7009:
7005:
7002:
6997:
6993:
6988:
6983:
6975:
6972:
6969:
6965:
6961:
6958:
6955:
6949:
6944:
6933:
6928:
6920:
6916:
6912:
6909:
6906:
6900:
6895:
6880:
6877:
6861:
6855:
6850:
6845:
6838:
6833:
6828:
6822:
6817:
6790:
6784:
6779:
6774:
6767:
6762:
6757:
6751:
6746:
6740:
6710:
6704:
6699:
6693:
6688:
6674:
6659:
6637:
6624:
6619:
6614:
6594:
6588:
6578:
6563:
6550:
6536:
6523:
6518:
6513:
6507:
6495:
6482:
6472:
6456:
6450:
6435:
6430:
6403:
6388:
6382:
6377:
6350:
6328:
6321:
6308:
6303:
6276:
6254:
6241:
6236:
6230:
6215:If we define
6213:
6210:
6181:
6170:
6148:
6138:
6132:
6119:
6100:
6075:
6043:
6035:
6019:
6016:
6000:
5992:
5964:
5956:
5938:
5928:
5925:
5914:
5906:
5888:
5869:
5822:
5775:
5746:
5743:
5719:
5709:
5706:
5696:
5677:
5674:
5660:
5594:
5578:
5554:
5551:
5532:
5522:
5519:
5509:
5490:
5487:
5462:
5459:
5454:
5450:
5446:
5441:
5437:
5429:
5427:
5426:
5411:
5408:
5405:
5400:
5396:
5392:
5387:
5383:
5379:
5372:
5370:
5369:
5354:
5351:
5346:
5342:
5338:
5333:
5329:
5321:
5318:
5317:
5300:
5296:
5292:
5287:
5283:
5279:
5270:
5267:
5261:
5258:
5257:
5256:
5248:
5244:
5240:
5236:
5232:
5214:
5211:
5206:
5198:
5194:
5184:
5180:
5170:
5166:
5159:
5153:
5148:
5140:
5136:
5126:
5122:
5115:
5110:
5105:
5097:
5093:
5083:
5079:
5069:
5065:
5058:
5051:
5043:
5039:
5031:
5027:
5021:
5012:
5008:
5000:
4996:
4990:
4984:
4974:
4958:
4950:
4946:
4936:
4932:
4922:
4918:
4911:
4904:
4898:
4893:
4888:
4882:
4872:
4871:
4870:
4862:
4848:
4845:
4840:
4836:
4832:
4827:
4823:
4819:
4814:
4810:
4802:
4800:
4799:
4792:
4788:
4772:
4768:
4764:
4759:
4755:
4751:
4746:
4742:
4738:
4733:
4729:
4725:
4720:
4716:
4712:
4707:
4703:
4695:
4693:
4692:
4685:
4681:
4665:
4661:
4657:
4652:
4648:
4644:
4639:
4635:
4631:
4626:
4622:
4618:
4613:
4609:
4605:
4600:
4596:
4588:
4585:
4584:
4580:
4564:
4560:
4556:
4553:
4550:
4545:
4541:
4537:
4534:
4531:
4526:
4522:
4518:
4515:
4506:
4503:
4498:
4491:
4486:
4467:
4464:
4459:
4451:
4447:
4437:
4433:
4426:
4420:
4415:
4409:
4402:
4395:
4389:
4384:
4379:
4371:
4367:
4357:
4353:
4346:
4339:
4331:
4327:
4319:
4315:
4305:
4301:
4293:
4289:
4281:
4276:
4270:
4260:
4244:
4236:
4232:
4222:
4218:
4211:
4204:
4196:
4192:
4184:
4180:
4173:
4163:
4162:
4161:
4153:
4139:
4136:
4131:
4127:
4123:
4118:
4114:
4106:
4104:
4103:
4099:
4085:
4082:
4077:
4073:
4069:
4064:
4060:
4056:
4051:
4047:
4043:
4038:
4034:
4026:
4024:
4023:
4019:
4005:
4002:
3997:
3993:
3989:
3984:
3980:
3976:
3971:
3967:
3963:
3958:
3954:
3946:
3944:
3943:
3939:
3925:
3922:
3917:
3913:
3909:
3904:
3900:
3892:
3889:
3888:
3884:
3868:
3864:
3860:
3855:
3851:
3847:
3842:
3838:
3834:
3829:
3825:
3815:
3812:
3796:
3792:
3769:
3765:
3742:
3738:
3715:
3711:
3701:
3685:
3681:
3658:
3654:
3631:
3627:
3604:
3600:
3591:
3587:
3583:
3575:
3570:
3561:
3545:
3541:
3537:
3534:
3529:
3525:
3521:
3518:
3513:
3509:
3505:
3483:
3479:
3475:
3472:
3467:
3463:
3459:
3456:
3448:
3444:
3440:
3437:
3432:
3428:
3424:
3418:
3413:
3409:
3386:
3382:
3378:
3375:
3370:
3366:
3362:
3359:
3354:
3350:
3327:
3323:
3319:
3316:
3311:
3307:
3303:
3300:
3295:
3291:
3268:
3264:
3260:
3257:
3249:
3245:
3241:
3238:
3233:
3229:
3225:
3219:
3214:
3210:
3187:
3183:
3160:
3156:
3133:
3129:
3125:
3122:
3117:
3113:
3109:
3100:
3097:
3091:
3086:
3081:
3074:
3046:
3041:
3037:
3028:
3025:
3020:
3016:
3012:
3004:
3001:
2996:
2992:
2988:
2972:
2968:
2964:
2946:
2945:
2944:
2923:
2920:
2915:
2911:
2907:
2904:
2901:
2896:
2892:
2883:
2880:
2875:
2871:
2867:
2864:
2859:
2855:
2851:
2835:
2831:
2827:
2824:
2819:
2815:
2811:
2793:
2792:
2791:
2775:
2771:
2767:
2764:
2760:
2756:
2755:
2754:
2752:
2747:
2745:
2741:
2737:
2734:
2730:
2727:
2723:
2719:
2713:
2711:
2707:
2703:
2700:
2696:
2693:
2689:
2685:
2682:
2678:
2674:
2671:
2664:
2663:
2657:
2656:as variables:
2655:
2651:
2647:
2643:
2639:
2636:
2632:
2629:
2625:
2621:
2611:
2609:
2604:
2601:
2596:
2592:
2591:
2588:
2585:
2579:
2576:
2572:
2565:
2563:
2553:
2549:
2548:
2545:
2542:
2536:
2533:
2529:
2522:
2517:
2513:
2511:
2507:
2503:
2501:
2497:
2496:
2490:
2487:
2484:
2483:
2478:
2474:
2472:
2468:
2466:
2463:
2460:
2459:
2458:
2456:
2452:
2448:
2445:
2441:
2438:
2434:
2431:
2427:
2424:
2420:
2416:
2412:
2402:
2400:
2397:
2393:
2390:
2376:
2374:
2370:
2367:
2363:
2360:
2356:
2353:
2349:
2345:
2342:
2338:
2335:
2331:
2330:
2326:
2323:
2319:
2315:
2312:
2308:
2305:
2301:
2299:
2295:
2292:
2288:
2285:
2281:
2280:
2276:
2273:
2269:
2265:
2262:
2258:
2255:
2251:
2248:
2244:
2240:
2237:
2233:
2230:
2226:
2225:
2221:
2218:
2215:
2214:
2211:
2202:
2182:
2178:
2174:
2149:
2144:
2140:
2117:
2113:
2109:
2089:
2086:
2081:
2077:
2054:
2050:
2046:
2026:
2023:
2018:
2014:
2005:
1987:
1983:
1960:
1956:
1952:
1947:
1943:
1937:
1934:
1930:
1926:
1923:
1920:
1915:
1911:
1905:
1902:
1898:
1889:
1885:
1881:
1865:
1861:
1855:
1851:
1847:
1844:
1841:
1836:
1832:
1826:
1822:
1799:
1779:
1774:
1770:
1747:
1743:
1739:
1719:
1716:
1711:
1707:
1684:
1680:
1676:
1656:
1653:
1648:
1644:
1621:
1617:
1613:
1605:
1588:
1584:
1580:
1577:
1574:
1569:
1565:
1556:
1552:
1551:
1550:
1532:
1512:
1492:
1470:
1466:
1443:
1439:
1435:
1430:
1426:
1420:
1417:
1413:
1409:
1406:
1403:
1398:
1394:
1388:
1385:
1381:
1372:
1368:
1364:
1348:
1344:
1338:
1334:
1330:
1327:
1324:
1319:
1315:
1309:
1305:
1282:
1262:
1257:
1253:
1232:
1229:
1224:
1220:
1199:
1196:
1191:
1187:
1178:
1160:
1156:
1147:
1130:
1126:
1122:
1119:
1116:
1111:
1107:
1098:
1094:
1093:
1092:
1084:
1081:
1065:
1061:
1040:
1035:
1031:
1010:
1007:
1004:
1001:
998:
995:
992:
987:
983:
962:
942:
920:
916:
912:
907:
899:
894:
890:
866:
863:
860:
851:
837:
817:
797:
775:
771:
763:. (Note that
750:
730:
710:
702:
684:
680:
670:
668:
664:
660:
657:
653:
646:
644:
640:
636:
633:
629:
626:
620:
606:
603:
600:
580:
577:
574:
569:
565:
542:
538:
517:
497:
487:
485:
481:
477:
474:
470:
467:
461:
458:
444:
422:
419:
415:
394:
374:
371:
368:
348:
328:
325:
322:
300:
296:
288:can sell for
275:
255:
252:
249:
229:
207:
203:
182:
173:
171:
161:
159:
153:
151:
147:
143:
140:
136:
133:
127:
125:
121:
117:
113:
107:
105:
101:
97:
94:
90:
87:
81:
73:
71:
67:
62:
60:
56:
51:
48:
40:
37:
34:
33:
32:
30:
26:
22:
9441:
9428:
9420:
9414:. Retrieved
9410:
9401:
9382:
9376:
9367:
9364:Econometrica
9363:
9357:
9347:
9343:
9337:
9311:
9298:
9270:
9263:
9253:, retrieved
9239:
9229:
9209:
9141:
8626:
8619:
8613:
8608:
8604:
8598:
8591:
8585:
8578:
8572:
8568:
8561:
8558:coefficients
8554:
7849:
7845:
7838:
7834:
7830:
7826:
7822:
7820:
7310:
7298:
7291:
7284:
7281:Applications
7030:
7027:
6881:
6878:
6675:
6579:
6473:
6214:
6211:
6101:
6076:
5870:
5823:
5776:
5678:
5675:
5579:
5491:
5488:
5484:
5319:Subject to:
5265:
5254:
5245:
5241:
5237:
5233:
5229:
4975:subject to:
4868:
4790:
4683:
4586:subject to:
4496:
4489:
4484:
4482:
4261:subject to:
4159:
3890:subject to:
3702:
3589:
3585:
3581:
3579:
3283:. Now, if
3101:
3098:
3089:
3087:
3079:
3072:
3070:
2942:
2789:
2786:Tiny example
2773:
2769:
2762:
2758:
2750:
2748:
2743:
2739:
2735:
2732:
2728:
2725:
2721:
2717:
2715:
2709:
2705:
2701:
2698:
2694:
2691:
2687:
2683:
2680:
2676:
2672:
2669:
2667:
2661:
2659:
2653:
2649:
2645:
2641:
2637:
2634:
2630:
2627:
2623:
2619:
2617:
2608:Farkas lemma
2605:
2597:
2594:
2589:
2586:
2581:
2577:
2574:
2570:
2567:
2561:
2559:
2551:
2546:
2543:
2538:
2534:
2531:
2527:
2524:
2520:
2515:
2509:
2505:
2499:
2494:
2492:
2485:
2481:
2480:
2476:
2470:
2464:
2461:
2454:
2450:
2446:
2443:
2439:
2436:
2432:
2429:
2425:
2422:
2418:
2414:
2410:
2408:
2405:Weak duality
2398:
2395:
2391:
2388:
2386:
2372:
2368:
2365:
2361:
2358:
2351:
2347:
2343:
2340:
2336:
2333:
2321:
2317:
2313:
2310:
2306:
2303:
2297:
2293:
2290:
2286:
2283:
2271:
2267:
2263:
2260:
2256:
2253:
2246:
2242:
2238:
2235:
2231:
2228:
2208:
2200:
2003:
1887:
1883:
1554:
1548:
1370:
1366:
1176:
1096:
1090:
1082:
852:
701:shadow price
671:
666:
662:
658:
655:
654:, such that
651:
648:
642:
638:
634:
631:
627:
624:
622:
489:
483:
479:
475:
472:
468:
465:
463:
459:
174:
167:
157:
155:
149:
145:
141:
138:
134:
131:
129:
123:
119:
115:
111:
109:
103:
99:
95:
92:
88:
85:
83:
79:
63:
58:
54:
52:
46:
44:
28:
20:
18:
8746:subject to
8567:appears in
7967:subject to
7425:subject to
2668:subject to
2633:subject to
2442:subject to
2364:subject to
2339:subject to
2309:subject to
2289:subject to
2259:subject to
2234:subject to
1699:" becomes
1636:" becomes
1557:variables:
630:subject to
471:subject to
137:subject to
91:subject to
70:duality gap
23:of a given
9416:2023-06-26
9370:: 115–135.
9255:2022-12-23
9178:References
7853:. We get:
5272:Maximize:
4873:Minimize:
4508:Minimize:
4164:Maximize:
3817:Maximize:
3811:per unit.
3202:we get:
3175:. For any
2357:Minimize
2302:Minimize
2252:Minimize
1762:" becomes
1365:A list of
623:Minimize
130:Minimize
9122:≤
9116:≤
9104:≤
9098:≤
9066:≥
9046:≥
9008:≤
9002:≤
8963:≤
8920:∑
8868:≤
8862:≤
8823:≤
8757:∑
8693:∑
8649:∑
8638:Maximize
8535:≤
8529:≤
8517:≤
8511:≤
8479:≥
8459:≥
8421:≤
8415:≤
8403:≤
8397:≤
8365:≥
8345:≥
8307:≤
8301:≤
8262:⋅
8249:≥
8236:⋅
8193:∑
8176:⋅
8128:≤
8122:≤
8083:⋅
8070:≥
8057:⋅
8021:⋅
7978:∑
7914:∑
7870:∑
7859:Minimize
7801:≤
7795:≤
7783:≤
7777:≤
7745:≥
7725:≥
7687:≤
7681:≤
7642:≥
7599:∑
7547:≤
7541:≤
7502:≥
7436:∑
7372:∑
7328:∑
7317:Minimize
7217:≤
7109:≥
6998:∗
6945:∗
6896:∗
6620:≤
6519:≥
6182:≤
6139:≥
6020:ρ
6017:≤
5929:ρ
5926:≥
5747:ρ
5744:≤
5710:ρ
5707:≥
5661:ρ
5555:ρ
5523:ρ
5460:≥
5409:−
5406:≤
5380:−
5352:≤
5339:−
5293:−
5212:≥
5111:≥
4846:≥
4765:≥
4752:⋅
4726:⋅
4658:≥
4645:⋅
4619:⋅
4557:⋅
4538:⋅
4519:⋅
4465:≥
4385:≤
4137:≥
4083:≤
4070:⋅
4044:⋅
4003:≤
3990:⋅
3964:⋅
3923:≤
3861:⋅
3835:⋅
3519:≥
3457:≥
3419:⋅
3376:≥
3360:⋅
3317:≥
3301:⋅
3220:⋅
3047:∈
3026:≥
3002:≥
2921:≥
2902:≥
2660:Maximize
2332:Maximize
2282:Maximize
2227:Maximize
2167:becomes "
2150:∈
2110:≥
2102:becomes "
2087:≥
2047:≤
2039:becomes "
2024:≤
1953:⪋
1924:⋯
1845:⋯
1780:∈
1717:≥
1677:≤
1654:≤
1614:≥
1578:…
1513:≤
1493:≥
1436:⪋
1407:⋯
1328:⋯
1263:∈
1230:≤
1197:≥
1120:…
1095:A set of
1066:∗
1008:≥
996:≥
935:for some
864:≥
776:∗
685:∗
604:≥
578:≥
464:Maximize
407:requires
372:≥
326:≥
253:≥
84:Maximize
9456:Category
9310:(1986),
9290:16577541
9208:(2006).
9146:See also
7821:We have
2781:Examples
1292:maximize
124:minimize
9330:0859549
9157:Duality
8602:1,;;n;;
3401:, then
2708:≥ 0,
2624:optimal
2488:)
2216:Primal
2132:" and
242:), let
158:dual of
9389:
9350:: 1–9.
9328:
9318:
9288:
9278:
9246:
9216:
5580:where
3584:land,
2620:single
2580:= min
2537:≤ min
2457:≥ 0":
2069:" and
1819:
1816:
1813:
1669:and "
1373:is:
1302:
1299:
1296:
830:, and
152:≥ 0
29:primal
9438:(PDF)
6805:and
3498:, so
2738:. So
2704:,
2690:,
2679:,
2222:Note
2219:Dual
1732:and "
9387:ISBN
9316:ISBN
9286:OCLC
9276:ISBN
9244:ISBN
9214:ISBN
7844:and
7299:The
5846:and
5799:and
5609:and
3784:and
3342:and
2652:and
2560:The
2409:The
2354:≥ 0
2324:≥ 0
2274:≥ 0
2249:≥ 0
1890:is:
1175:, a
913:<
530:for
486:≥ 0.
106:≥ 0.
53:The
45:The
21:dual
19:The
8589:1,2
8576:1,1
2712:≥ 0
2568:max
2525:max
2504:= (
2491:= (
1525:or
1505:or
850:.)
645:≥ 0
457:).
9458::
9440:.
9419:.
9409:.
9368:24
9366:.
9348:13
9346:.
9326:MR
9324:,
9306:;
9284:.
9238:,
9186:^
7296:.
7289:.
7223:14
7190:14
7127:14
7095:14
7075:10
7006:14
6876:.
6725:,
6418:,
6365:,
6291:,
5463:0.
5215:0.
4468:0.
2731:=
2697:≥
2686:≥
2675:≤
2644:,
2640:≤
2610:.
2516:by
2514:≤
2506:Ax
2475:≤
2471:xc
2469:=
2453:,
2449:≤
2428:≤
2371:≥
2350:,
2346:=
2320:,
2316:=
2296:≤
2270:,
2266:≥
2245:,
2241:≤
2197:".
1280:).
810:,
665:,
661:≥
641:,
637:≥
482:,
478:≤
148:,
144:≥
102:,
98:≤
61:.
9444:.
9395:.
9352::
9292:.
9222:.
9125:m
9119:i
9113:1
9110:,
9107:n
9101:j
9095:1
9072:,
9069:0
9061:i
9057:s
9052:,
9049:0
9041:j
9037:y
9011:n
9005:j
8999:1
8976:,
8971:j
8967:d
8958:i
8954:s
8948:j
8945:i
8941:b
8935:m
8930:1
8927:=
8924:i
8916:+
8911:j
8907:y
8901:j
8897:e
8871:m
8865:i
8859:1
8836:,
8831:i
8827:c
8818:i
8814:s
8808:i
8804:f
8800:+
8795:j
8791:y
8785:j
8782:i
8778:a
8772:n
8767:1
8764:=
8761:j
8728:i
8724:s
8718:i
8714:h
8708:m
8703:1
8700:=
8697:i
8689:+
8684:j
8680:y
8674:j
8670:g
8664:n
8659:1
8656:=
8653:j
8630:1
8627:c
8623:1
8620:s
8617:1
8614:f
8609:n
8605:y
8599:a
8595:2
8592:y
8586:a
8582:1
8579:y
8573:a
8569:n
8565:1
8562:x
8538:m
8532:i
8526:1
8523:,
8520:n
8514:j
8508:1
8485:,
8482:0
8474:i
8470:s
8465:,
8462:0
8454:j
8450:y
8424:n
8418:j
8412:1
8409:,
8406:m
8400:i
8394:1
8371:,
8368:0
8360:j
8356:t
8351:,
8348:0
8340:i
8336:x
8310:m
8304:i
8298:1
8275:,
8270:i
8266:s
8257:i
8253:h
8244:i
8240:s
8231:j
8227:t
8221:j
8218:i
8214:b
8208:n
8203:1
8200:=
8197:j
8189:+
8184:i
8180:s
8171:i
8167:x
8161:i
8157:f
8131:n
8125:j
8119:1
8096:,
8091:j
8087:y
8078:j
8074:g
8065:j
8061:y
8052:j
8048:t
8042:j
8038:e
8034:+
8029:j
8025:y
8016:i
8012:x
8006:j
8003:i
7999:a
7993:m
7988:1
7985:=
7982:i
7949:j
7945:t
7939:j
7935:d
7929:n
7924:1
7921:=
7918:j
7910:+
7905:i
7901:x
7895:i
7891:c
7885:m
7880:1
7877:=
7874:i
7850:i
7846:s
7842:j
7839:y
7835:n
7831:m
7827:n
7823:m
7804:n
7798:j
7792:1
7789:,
7786:m
7780:i
7774:1
7751:,
7748:0
7740:j
7736:t
7731:,
7728:0
7720:i
7716:x
7690:m
7684:i
7678:1
7655:,
7650:i
7646:h
7637:j
7633:t
7627:j
7624:i
7620:b
7614:n
7609:1
7606:=
7603:j
7595:+
7590:i
7586:x
7580:i
7576:f
7550:n
7544:j
7538:1
7515:,
7510:j
7506:g
7497:j
7493:t
7487:j
7483:e
7479:+
7474:i
7470:x
7464:j
7461:i
7457:a
7451:m
7446:1
7443:=
7440:i
7407:j
7403:t
7397:j
7393:d
7387:n
7382:1
7379:=
7376:j
7368:+
7363:i
7359:x
7353:i
7349:c
7343:m
7338:1
7335:=
7332:i
7260:z
7254:B
7250:=
7245:T
7241:)
7237:7
7234:,
7231:3
7227:/
7220:(
7212:T
7208:)
7204:7
7201:,
7198:3
7194:/
7187:(
7184:=
7180:z
7176:)
7173:u
7170:(
7166:A
7157:B
7151:T
7146:p
7141:=
7138:)
7135:3
7131:/
7124:,
7121:4
7118:,
7115:3
7112:(
7106:)
7103:3
7099:/
7092:,
7089:4
7086:,
7083:3
7079:/
7072:(
7069:=
7066:)
7063:u
7060:(
7056:A
7050:T
7045:p
7014:3
7010:/
7003:=
6994:u
6989:,
6984:T
6980:)
6976:1
6973:,
6970:6
6966:/
6962:7
6959:,
6956:0
6953:(
6950:=
6940:z
6934:,
6929:T
6925:)
6921:3
6917:/
6913:2
6910:,
6907:1
6904:(
6901:=
6891:p
6862:]
6856:7
6851:0
6846:0
6839:0
6834:4
6829:3
6823:[
6818:=
6814:B
6791:]
6785:0
6780:6
6775:5
6768:u
6763:0
6758:0
6752:[
6747:=
6744:)
6741:u
6738:(
6734:A
6711:]
6705:6
6700:5
6694:[
6689:=
6685:A
6660:]
6653:b
6644:x
6638:T
6633:c
6625:[
6615:]
6608:x
6603:A
6595:u
6589:[
6564:]
6557:b
6551:T
6546:y
6537:T
6532:c
6524:[
6514:]
6508:u
6502:A
6496:T
6491:y
6483:[
6457:]
6451:1
6443:x
6436:[
6431:=
6427:z
6404:]
6397:y
6389:1
6383:[
6378:=
6374:p
6351:]
6344:b
6337:0
6329:0
6322:T
6317:c
6309:[
6304:=
6300:B
6277:]
6270:0
6263:A
6255:u
6249:0
6242:[
6237:=
6234:)
6231:u
6228:(
6224:A
6192:z
6186:B
6178:z
6174:)
6171:u
6168:(
6164:A
6155:B
6149:T
6144:p
6136:)
6133:u
6130:(
6126:A
6120:T
6115:p
6086:u
6057:z
6052:)
6048:z
6044:,
6040:u
6036:,
6032:p
6028:(
6024:B
6013:z
6009:)
6005:z
6001:,
5997:u
5993:,
5989:p
5985:(
5981:A
5973:)
5969:z
5965:,
5961:u
5957:,
5953:p
5949:(
5945:B
5939:T
5934:p
5923:)
5919:z
5915:,
5911:u
5907:,
5903:p
5899:(
5895:A
5889:T
5884:p
5855:B
5833:A
5808:z
5786:p
5757:z
5751:B
5740:z
5735:A
5726:B
5720:T
5715:p
5703:A
5697:T
5692:p
5640:A
5618:z
5595:T
5590:p
5560:z
5552:=
5548:z
5543:A
5533:T
5528:p
5520:=
5516:A
5510:T
5505:p
5455:2
5451:x
5447:,
5442:1
5438:x
5412:2
5401:2
5397:x
5393:+
5388:1
5384:x
5355:1
5347:2
5343:x
5334:1
5330:x
5301:2
5297:x
5288:1
5284:x
5280:2
5207:]
5199:P
5195:y
5185:F
5181:y
5171:L
5167:y
5160:[
5154:,
5149:]
5141:2
5137:S
5127:1
5123:S
5116:[
5106:]
5098:P
5094:y
5084:F
5080:y
5070:L
5066:y
5059:[
5052:]
5044:2
5040:P
5032:2
5028:F
5022:1
5013:1
5009:P
5001:1
4997:F
4991:1
4985:[
4959:]
4951:P
4947:y
4937:F
4933:y
4923:L
4919:y
4912:[
4905:]
4899:P
4894:F
4889:L
4883:[
4849:0
4841:P
4837:y
4833:,
4828:F
4824:y
4820:,
4815:L
4811:y
4794:2
4791:S
4773:2
4769:S
4760:P
4756:y
4747:2
4743:P
4739:+
4734:F
4730:y
4721:2
4717:F
4713:+
4708:L
4704:y
4687:1
4684:S
4666:1
4662:S
4653:P
4649:y
4640:1
4636:P
4632:+
4627:F
4623:y
4614:1
4610:F
4606:+
4601:L
4597:y
4565:P
4561:y
4554:P
4551:+
4546:F
4542:y
4535:F
4532:+
4527:L
4523:y
4516:L
4500:2
4497:S
4493:1
4490:S
4485:y
4460:]
4452:2
4448:x
4438:1
4434:x
4427:[
4421:,
4416:]
4410:P
4403:F
4396:L
4390:[
4380:]
4372:2
4368:x
4358:1
4354:x
4347:[
4340:]
4332:2
4328:P
4320:1
4316:P
4306:2
4302:F
4294:1
4290:F
4282:1
4277:1
4271:[
4245:]
4237:2
4233:x
4223:1
4219:x
4212:[
4205:]
4197:2
4193:S
4185:1
4181:S
4174:[
4140:0
4132:2
4128:x
4124:,
4119:1
4115:x
4086:P
4078:2
4074:x
4065:2
4061:P
4057:+
4052:1
4048:x
4039:1
4035:P
4006:F
3998:2
3994:x
3985:2
3981:F
3977:+
3972:1
3968:x
3959:1
3955:F
3926:L
3918:2
3914:x
3910:+
3905:1
3901:x
3869:2
3865:x
3856:2
3852:S
3848:+
3843:1
3839:x
3830:1
3826:S
3797:2
3793:S
3770:1
3766:S
3743:2
3739:x
3716:1
3712:x
3686:2
3682:P
3659:2
3655:F
3632:1
3628:P
3605:1
3601:F
3590:P
3586:F
3582:L
3546:2
3542:x
3538:4
3535:+
3530:1
3526:x
3522:3
3514:1
3510:y
3506:7
3484:2
3480:x
3476:4
3473:+
3468:1
3464:x
3460:3
3454:)
3449:2
3445:x
3441:6
3438:+
3433:1
3429:x
3425:5
3422:(
3414:1
3410:y
3387:2
3383:x
3379:4
3371:2
3367:x
3363:6
3355:1
3351:y
3328:1
3324:x
3320:3
3312:1
3308:x
3304:5
3296:1
3292:y
3269:1
3265:y
3261:7
3258:=
3255:)
3250:2
3246:x
3242:6
3239:+
3234:1
3230:x
3226:5
3223:(
3215:1
3211:y
3188:1
3184:y
3161:1
3157:y
3134:2
3130:x
3126:4
3123:+
3118:1
3114:x
3110:3
3093:1
3090:y
3083:2
3080:x
3076:1
3073:x
3051:R
3042:1
3038:y
3029:4
3021:1
3017:y
3013:6
3005:3
2997:1
2993:y
2989:5
2973:1
2969:y
2965:7
2924:0
2916:2
2912:x
2908:,
2905:0
2897:1
2893:x
2884:7
2881:=
2876:2
2872:x
2868:6
2865:+
2860:1
2856:x
2852:5
2836:2
2832:x
2828:4
2825:+
2820:1
2816:x
2812:3
2776:.
2774:t
2770:t
2765:.
2763:t
2759:t
2751:t
2744:y
2740:x
2736:y
2733:b
2729:x
2726:c
2722:y
2720:,
2718:x
2710:y
2706:x
2702:y
2699:b
2695:x
2692:c
2688:c
2684:y
2681:A
2677:b
2673:x
2670:A
2662:1
2654:y
2650:x
2646:x
2642:b
2638:x
2635:A
2631:x
2628:c
2590:y
2587:b
2583:y
2578:x
2575:c
2571:x
2547:y
2544:b
2540:y
2535:x
2532:c
2528:x
2510:y
2508:)
2500:y
2498:)
2495:A
2493:x
2486:y
2482:A
2479:(
2477:x
2465:x
2462:c
2455:x
2451:b
2447:x
2444:A
2440:x
2437:c
2433:y
2430:b
2426:x
2423:c
2419:y
2415:x
2399:y
2396:b
2392:x
2389:c
2373:c
2369:y
2366:A
2362:y
2359:b
2352:x
2348:b
2344:x
2341:A
2337:x
2334:c
2322:y
2318:c
2314:y
2311:A
2307:y
2304:b
2298:b
2294:x
2291:A
2287:x
2284:c
2272:y
2268:c
2264:y
2261:A
2257:y
2254:b
2247:x
2243:b
2239:x
2236:A
2232:x
2229:c
2183:i
2179:c
2175:=
2154:R
2145:i
2141:x
2118:i
2114:c
2090:0
2082:i
2078:x
2055:i
2051:c
2027:0
2019:i
2015:x
2004:i
1988:i
1984:c
1961:i
1957:c
1948:m
1944:y
1938:i
1935:m
1931:a
1927:+
1921:+
1916:1
1912:y
1906:i
1903:1
1899:a
1888:i
1884:n
1866:m
1862:y
1856:m
1852:b
1848:+
1842:+
1837:1
1833:y
1827:1
1823:b
1797:.
1784:R
1775:j
1771:y
1748:j
1744:b
1740:=
1720:0
1712:j
1708:y
1685:j
1681:b
1657:0
1649:j
1645:y
1622:j
1618:b
1603:.
1589:m
1585:y
1581:,
1575:,
1570:1
1566:y
1555:m
1545:.
1533:=
1471:j
1467:b
1444:j
1440:b
1431:n
1427:x
1421:n
1418:j
1414:a
1410:+
1404:+
1399:1
1395:x
1389:1
1386:j
1382:a
1371:j
1367:m
1349:n
1345:x
1339:n
1335:c
1331:+
1325:+
1320:1
1316:x
1310:1
1306:c
1267:R
1258:i
1254:x
1233:0
1225:i
1221:x
1200:0
1192:i
1188:x
1161:i
1157:x
1145:.
1131:n
1127:x
1123:,
1117:,
1112:1
1108:x
1097:n
1062:y
1041:y
1036:T
1032:b
1011:0
1005:y
1002:,
999:c
993:y
988:T
984:A
963:i
943:i
921:i
917:c
908:i
904:)
900:y
895:T
891:A
887:(
867:0
861:y
838:c
818:b
798:A
772:y
751:c
731:b
711:A
681:y
667:y
663:c
659:y
656:A
652:y
643:y
639:c
635:y
632:A
628:y
625:b
607:0
601:y
581:c
575:y
570:T
566:A
543:i
539:y
518:i
498:y
484:x
480:b
476:x
473:A
469:x
466:c
445:j
423:i
420:j
416:A
395:i
375:0
369:A
349:b
329:0
323:x
301:i
297:c
276:i
256:0
250:c
230:i
208:i
204:x
183:x
150:y
146:c
142:y
139:A
135:y
132:b
120:y
116:c
112:x
104:x
100:b
96:x
93:A
89:x
86:c
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
