2078:
25:
1772:
1910:
2763:
larger. If it is possible to do so without violating other constraints, then the increased variable becomes basic (it "enters the basis"), while some basic variable is decreased to 0 to keep the equality constraints and thus becomes non-basic (it "exits the basis").
1539:
2925:. In general, a primal-optimal basis is not necessarily dual-optimal, and a dual-optimal basis is not necessarily primal-optimal (in fact, the solution of a primal-optimal basis may even be unfeasible for the dual, and vice versa).
2459:
1441:: the objective of a linear program is convex; the set of feasible solutions is convex (it is an intersection of hyperspaces); therefore the objective attains its maximum in an extreme point of the set of feasible solutions.
1989:
3051:
2889:
2319:
2986:
2166:
1785:
1389:
1326:
130:
of feasible solutions. If there exists an optimal solution, then there exists an optimal BFS. Hence, to find an optimal solution, it is sufficient to consider the BFS-s. This fact is used by the
2361:
1544:
2250:
3092:
the primal LP (or only the dual LP) and returns an optimal basis, then there exists a strongly-polynomial time algorithm for solving any linear program (the latter is a famous open problem).
1437:
5. If a linear program has an optimal solution (i.e., it has a feasible solution, and the set of feasible solutions is bounded), then it has an optimal BFS. This is a consequence of the
601:
552:
447:
222:
2923:
2208:
187:
1236:
1424:
2067:
971:
2353:
variables), a "current BFS", and a "current tableau". The tableau is a representation of the linear program where the basic variables are expressed in terms of the non-basic ones:
519:
399:
250:
2356:
1191:
1158:
285:
1520:
1481:
878:
1118:
1065:
1021:
912:
335:
307:
2671:
1767:{\displaystyle {\begin{aligned}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}&=14\\x_{2}+3x_{3}+5x_{4}+6x_{5}&=7\\\forall i\in \{1,\ldots ,5\}:x_{i}&\geq 0\end{aligned}}}
2721:
2638:
2588:
2517:
2486:
1263:
1092:
746:
683:
2785:
2761:
2741:
2694:
2611:
2561:
2541:
999:
835:
811:
782:
715:
474:
361:
1918:=2 and there are 10 subsets of 2 indices, however, not all of them are bases: the set {3,5} is not a basis since columns 3 and 5 are linearly dependent.
35:
3134:
1928:
93:
2795:
In the worst case, the simplex algorithm may require exponentially many steps to complete. There are algorithms for solving an LP in
3146:
65:
2796:
1042:
non-zero variables; in that case, it can have many different bases, all of which contain the indices of its non-zero variables.
2640:
is an optimal solution, since all variables (including all non-basic variables) must be at least 0, so the second line implies
72:
2991:
2829:
2259:
1905:{\displaystyle A={\begin{pmatrix}1&5&3&4&6\\0&1&3&5&6\end{pmatrix}}~~~~~\mathbf {b} =(14~~7)}
50:
2931:
2111:
1334:
1271:
79:
2215:
3220:
61:
126:) is a solution with a minimal set of non-zero variables. Geometrically, each BFS corresponds to a vertex of the
573:
524:
419:
194:
3085:
3074:
127:
2894:
2179:
2077:
158:
1483:, an optimal solution to any LP can be found in finite time by just evaluating the objective function in all
1196:
2806:
However, Given any optimal solution to the LP, it is easy to find an optimal feasible solution that is also
1438:
1394:
1997:
925:
3178:
757:
496:
376:
227:
1167:
1134:
261:
1486:
1447:
844:
86:
2169:
449:
has at least one solution (otherwise the whole LP has no solution and there is nothing more to do);
3183:
1101:
1048:
1004:
895:
318:
290:
2643:
1331:
The opposite is not true: each BFS can come from many different bases. If the unique solution of
115:
3196:
3142:
3062:
2338:
1523:
620:
131:
3166:
3188:
2800:
2089:
2699:
2696:
are positive, then it may be possible to increase the maximization target. For example, if
2616:
2566:
2495:
2464:
1241:
1070:
724:
661:
2454:{\displaystyle {\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}}
2093:
749:
134:, which essentially travels from one BFS to another until an optimal solution is found.
42:
3096:
Megiddo's algorithms can be executed using a tableau, just like the simplex algorithm.
3066:
2770:
2746:
2726:
2679:
2596:
2546:
2526:
984:
820:
796:
767:
700:
459:
406:
346:
2543:
is the maximization objective. Since non-basic variables equal 0, the current BFS is
3214:
646:
is used not for the submatrix itself, but for the set of indices of its columns. Let
3106:
How to move from an optimal feasible solution to an optimal basic feasible solution
3061:. Every LP with an optimal solution has a PD-optimal basis, and it is found by the
761:
147:
For the definitions below, we first present the linear program in the so-called
24:
3200:
2085:
3105:
2891:
is an optimal solution to the dual linear program, that is, it minimizes
2767:
If this process is done carefully, then it is possible to guarantee that
3192:
480:(otherwise we can just delete redundant rows without changing the LP).
405:
Any linear program can be converted into an equational form by adding
2803:; however, they usually return optimal solutions that are not basic.
981:
1. A BFS is determined only by the constraints of the LP (the matrix
1984:{\displaystyle A_{B}={\begin{pmatrix}5&4\\1&5\end{pmatrix}}}
2337:
In practice, the easiest way to find an optimal BFS is to use the
2329:
There are several methods for finding a BFS that is also optimal.
3081:
an optimal solution to the dual LP, and returns an optimal basis.
2341:. It keeps, at each point of its execution, a "current basis"
1522:
BFS-s. This is not the most efficient way to solve an LP; the
18:
554:. We assume that there is at least one feasible solution. If
143:
Preliminaries: equational form with linearly-independent rows
2814:
Finding a basis that is both primal-optimal and dual-optimal
3077:
algorithm that inputs an optimal solution to the primal LP
3065:. However, its run-time is exponential in the worst case.
2168:. In a similar way, each basis defines a solution to the
1534:
Consider a linear program with the following constraints:
1265:
is non-singular, so the constraint has a unique solution:
3046:{\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}
2884:{\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}
2314:{\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}
2084:
The set of all feasible solutions is an intersection of
46:
2897:
2182:
1950:
1800:
1123:
4. Each basis determines a unique BFS: for each basis
562:, then there is only one feasible solution. Typically
161:
2994:
2934:
2832:
2773:
2749:
2729:
2702:
2682:
2646:
2619:
2599:
2569:
2549:
2529:
2498:
2467:
2359:
2262:
2218:
2114:
2096:. Each BFS corresponds to a vertex of this polytope.
2000:
1931:
1788:
1542:
1489:
1450:
1397:
1337:
1274:
1244:
1199:
1170:
1137:
1104:
1073:
1051:
1023:); it does not depend on the optimization objective.
1007:
987:
928:
898:
847:
823:
799:
770:
727:
703:
664:
576:
527:
499:
462:
422:
379:
349:
321:
293:
264:
230:
197:
2981:{\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}
2161:{\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}
1384:{\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}
1321:{\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}
1444:Since the number of BFS-s is finite and bounded by
603:has many solutions; each such solution is called a
3045:
2980:
2917:
2883:
2779:
2755:
2735:
2715:
2688:
2665:
2632:
2605:
2582:
2555:
2535:
2511:
2480:
2453:
2313:
2245:{\displaystyle A^{T}\mathbf {y} \geq \mathbf {c} }
2244:
2202:
2160:
2061:
1983:
1904:
1766:
1514:
1475:
1418:
1383:
1320:
1257:
1230:
1185:
1152:
1112:
1098:is the set of indices of the non-zero elements of
1086:
1067:is basic if-and-only-if the columns of the matrix
1059:
1015:
993:
965:
906:
872:
829:
805:
776:
740:
709:
677:
595:
546:
513:
468:
441:
393:
355:
329:
301:
279:
244:
216:
181:
3108:. Paul Robin, Operations Research Stack Exchange.
3053:is an optimal BFS of the dual LP, then the basis
2791:Converting any optimal solution to an optimal BFS
2743:is positive, then increasing it above 0 may make
1526:examines the BFS-s in a much more efficient way.
1506:
1493:
1467:
1454:
864:
851:
412:As a preliminary clean-up step, we verify that:
1994:The unique BFS corresponding to this basis is
3088:algorithm that inputs an optimal solution to
2100:Basic feasible solutions for the dual problem
918:if all its non-zero variables are indexed by
8:
2563:, and the current maximization objective is
1734:
1716:
476:are linearly independent, i.e., its rank is
51:introducing citations to additional sources
3167:"On Finding Primal- and Dual-Optimal Bases"
2787:increases until it reaches an optimal BFS.
3139:Understanding and Using Linear Programming
596:{\displaystyle A\mathbf {x} =\mathbf {b} }
547:{\displaystyle A\mathbf {x} =\mathbf {b} }
442:{\displaystyle A\mathbf {x} =\mathbf {b} }
401:means that all variables are non-negative.
217:{\displaystyle A\mathbf {x} =\mathbf {b} }
3182:
3028:
3021:
3016:
3011:
3000:
2995:
2993:
2963:
2956:
2951:
2940:
2935:
2933:
2918:{\textstyle \mathbf {b^{T}} \mathbf {y} }
2910:
2903:
2898:
2896:
2866:
2859:
2854:
2849:
2838:
2833:
2831:
2772:
2748:
2728:
2707:
2701:
2681:
2657:
2645:
2624:
2618:
2598:
2574:
2568:
2548:
2528:
2503:
2497:
2472:
2466:
2441:
2431:
2418:
2394:
2368:
2360:
2358:
2296:
2289:
2284:
2279:
2268:
2263:
2261:
2237:
2229:
2223:
2217:
2203:{\textstyle \mathbf {b^{T}} \mathbf {y} }
2195:
2188:
2183:
2181:
2143:
2136:
2131:
2120:
2115:
2113:
2108:defines a unique basic feasible solution
2005:
1999:
1945:
1936:
1930:
1876:
1795:
1787:
1744:
1687:
1671:
1655:
1639:
1615:
1599:
1583:
1567:
1551:
1543:
1541:
1505:
1492:
1490:
1488:
1466:
1453:
1451:
1449:
1403:
1398:
1396:
1391:satisfies the non-negativity constraints
1366:
1359:
1354:
1343:
1338:
1336:
1303:
1296:
1291:
1280:
1275:
1273:
1249:
1243:
1215:
1210:
1204:
1198:
1176:
1171:
1169:
1143:
1138:
1136:
1105:
1103:
1078:
1072:
1052:
1050:
1038:zero variables. A BFS can have less than
1008:
1006:
986:
951:
927:
899:
897:
863:
850:
848:
846:
822:
798:
769:
732:
726:
702:
669:
663:
588:
580:
575:
539:
531:
526:
500:
498:
461:
434:
426:
421:
380:
378:
348:
322:
320:
294:
292:
270:
265:
263:
231:
229:
209:
201:
196:
182:{\textstyle \mathbf {c^{T}} \mathbf {x} }
174:
167:
162:
160:
2988:is an optimal BFS of the primal LP, and
2076:
1238:, and by definition of basis the matrix
41:Relevant discussion may be found on the
3118:
1231:{\displaystyle A_{B}\mathbf {x_{B}} =b}
3128:
3126:
3124:
3122:
1419:{\displaystyle \mathbf {x_{B}} \geq 0}
2723:is non-basic and its coefficient in
2062:{\displaystyle x_{B}=(0~~2~~0~~1~~0)}
1925:={2,4} is a basis, since the matrix
966:{\displaystyle j\not \in B:~~x_{j}=0}
7:
3160:
3158:
1026:2. By definition, a BFS has at most
916:basic feasible solution with basis B
1131:indices, there is at most one BFS
817:, it has at least one basis; since
3069:proved the following theorems:
1707:
1497:
1458:
892:, we say that a feasible solution
855:
514:{\displaystyle \mathbf {x} \geq 0}
394:{\displaystyle \mathbf {x} \geq 0}
245:{\displaystyle \mathbf {x} \geq 0}
14:
2092:. If it is bounded, then it is a
3001:
2997:
2941:
2937:
2911:
2904:
2900:
2839:
2835:
2269:
2265:
2238:
2230:
2196:
2189:
2185:
2121:
2117:
2104:As mentioned above, every basis
1877:
1404:
1400:
1344:
1340:
1281:
1277:
1216:
1212:
1186:{\displaystyle \mathbf {x_{B}} }
1177:
1173:
1153:{\displaystyle \mathbf {x_{B}} }
1144:
1140:
1106:
1094:are linearly independent, where
1053:
1030:non-zero variables and at least
1009:
900:
589:
581:
540:
532:
501:
435:
427:
381:
323:
295:
280:{\displaystyle \mathbf {c^{T}} }
271:
267:
232:
210:
202:
175:
168:
164:
34:relies largely or entirely on a
23:
1515:{\displaystyle {\binom {n}{m}}}
1476:{\displaystyle {\binom {n}{m}}}
873:{\displaystyle {\binom {n}{m}}}
16:Concept from linear programming
3165:Megiddo, Nimrod (1991-02-01).
2056:
2014:
1899:
1884:
1:
1193:must satisfy the constraint
1113:{\displaystyle \mathbf {x} }
1060:{\displaystyle \mathbf {x} }
1016:{\displaystyle \mathbf {b} }
907:{\displaystyle \mathbf {x} }
341:(the number of constraints);
330:{\displaystyle \mathbf {b} }
302:{\displaystyle \mathbf {x} }
2666:{\displaystyle z\leq z_{0}}
2333:Using the simplex algorithm
3237:
313:(the number of variables);
3171:ORSA Journal on Computing
2523:non-basic variables, and
752:, the columns indexed by
62:"Basic feasible solution"
3086:strongly polynomial time
3075:strongly polynomial time
2676:If some coefficients in
2073:Geometric interpretation
841:columns, it has at most
784:. In this case, we call
493:of the LP is any vector
2593:If all coefficients in
1439:Bauer maximum principle
1045:3. A feasible solution
884:Basic feasible solution
120:basic feasible solution
3047:
2982:
2919:
2885:
2797:weakly-polynomial time
2781:
2757:
2737:
2717:
2690:
2667:
2634:
2607:
2584:
2557:
2537:
2513:
2482:
2455:
2325:Finding an optimal BFS
2315:
2246:
2204:
2162:
2081:
2063:
1985:
1906:
1768:
1516:
1477:
1420:
1385:
1329:
1322:
1259:
1232:
1187:
1154:
1114:
1088:
1061:
1017:
995:
967:
908:
874:
831:
807:
778:
742:
711:
679:
597:
548:
515:
470:
443:
395:
357:
331:
303:
281:
246:
218:
183:
3048:
2983:
2920:
2886:
2782:
2758:
2738:
2718:
2716:{\displaystyle x_{5}}
2691:
2668:
2635:
2633:{\displaystyle z_{0}}
2608:
2585:
2583:{\displaystyle z_{0}}
2558:
2538:
2514:
2512:{\displaystyle x_{N}}
2483:
2481:{\displaystyle x_{B}}
2456:
2316:
2247:
2205:
2163:
2088:. Therefore, it is a
2080:
2064:
1986:
1907:
1769:
1517:
1478:
1421:
1386:
1323:
1267:
1260:
1258:{\displaystyle A_{B}}
1233:
1188:
1155:
1115:
1089:
1087:{\displaystyle A_{K}}
1062:
1018:
996:
968:
909:
875:
832:
808:
779:
743:
741:{\displaystyle A_{B}}
712:
680:
678:{\displaystyle A_{B}}
598:
549:
516:
471:
444:
396:
358:
332:
304:
282:
247:
219:
184:
3141:. Berlin: Springer.
2992:
2932:
2895:
2830:
2822:of the LP is called
2771:
2747:
2727:
2700:
2680:
2644:
2617:
2597:
2567:
2547:
2527:
2496:
2465:
2357:
2260:
2216:
2180:
2112:
1998:
1929:
1786:
1540:
1487:
1448:
1395:
1335:
1272:
1242:
1197:
1168:
1135:
1102:
1071:
1049:
1005:
985:
926:
896:
845:
821:
797:
768:
725:
701:
662:
654:indices from {1,...,
642:Sometimes, the term
574:
525:
497:
460:
420:
377:
347:
337:is a vector of size
319:
309:are vectors of size
291:
262:
228:
195:
159:
47:improve this article
3193:10.1287/ijoc.3.1.63
3026:
2864:
2613:are negative, then
2294:
2170:dual linear program
922:, that is, for all
693:matrix made of the
456:rows of the matrix
3221:Linear programming
3084:If there exists a
3043:
3012:
2978:
2915:
2881:
2850:
2777:
2753:
2733:
2713:
2686:
2663:
2630:
2603:
2580:
2553:
2533:
2509:
2478:
2451:
2449:
2311:
2280:
2242:
2200:
2158:
2082:
2059:
1981:
1975:
1902:
1855:
1764:
1762:
1512:
1473:
1416:
1381:
1318:
1255:
1228:
1183:
1164:. This is because
1150:
1110:
1084:
1057:
1013:
991:
963:
904:
870:
827:
803:
793:Since the rank of
789:a basis of the LP.
774:
738:
707:
675:
593:
544:
511:
466:
439:
391:
353:
327:
299:
277:
242:
214:
179:
116:linear programming
3063:Simplex algorithm
2780:{\displaystyle z}
2756:{\displaystyle z}
2736:{\displaystyle r}
2689:{\displaystyle r}
2606:{\displaystyle r}
2556:{\displaystyle p}
2536:{\displaystyle z}
2519:is the vector of
2492:basic variables,
2488:is the vector of
2339:simplex algorithm
2090:convex polyhedron
2052:
2049:
2043:
2040:
2034:
2031:
2025:
2022:
1991:is non-singular.
1895:
1892:
1875:
1872:
1869:
1866:
1863:
1524:simplex algorithm
1504:
1465:
994:{\displaystyle A}
946:
943:
862:
830:{\displaystyle A}
806:{\displaystyle A}
777:{\displaystyle A}
710:{\displaystyle A}
605:feasible solution
491:feasible solution
485:Feasible solution
469:{\displaystyle A}
356:{\displaystyle A}
132:simplex algorithm
114:In the theory of
112:
111:
97:
3228:
3205:
3204:
3186:
3162:
3153:
3152:
3133:Gärtner, Bernd;
3130:
3052:
3050:
3049:
3044:
3036:
3035:
3027:
3025:
3020:
3006:
3005:
3004:
2987:
2985:
2984:
2979:
2971:
2970:
2962:
2961:
2960:
2946:
2945:
2944:
2924:
2922:
2921:
2916:
2914:
2909:
2908:
2907:
2890:
2888:
2887:
2882:
2874:
2873:
2865:
2863:
2858:
2844:
2843:
2842:
2826:if the solution
2801:ellipsoid method
2786:
2784:
2783:
2778:
2762:
2760:
2759:
2754:
2742:
2740:
2739:
2734:
2722:
2720:
2719:
2714:
2712:
2711:
2695:
2693:
2692:
2687:
2672:
2670:
2669:
2664:
2662:
2661:
2639:
2637:
2636:
2631:
2629:
2628:
2612:
2610:
2609:
2604:
2589:
2587:
2586:
2581:
2579:
2578:
2562:
2560:
2559:
2554:
2542:
2540:
2539:
2534:
2518:
2516:
2515:
2510:
2508:
2507:
2487:
2485:
2484:
2479:
2477:
2476:
2460:
2458:
2457:
2452:
2450:
2446:
2445:
2436:
2435:
2423:
2422:
2399:
2398:
2373:
2372:
2320:
2318:
2317:
2312:
2304:
2303:
2295:
2293:
2288:
2274:
2273:
2272:
2256:The solution is
2251:
2249:
2248:
2243:
2241:
2233:
2228:
2227:
2209:
2207:
2206:
2201:
2199:
2194:
2193:
2192:
2167:
2165:
2164:
2159:
2151:
2150:
2142:
2141:
2140:
2126:
2125:
2124:
2068:
2066:
2065:
2060:
2050:
2047:
2041:
2038:
2032:
2029:
2023:
2020:
2010:
2009:
1990:
1988:
1987:
1982:
1980:
1979:
1941:
1940:
1911:
1909:
1908:
1903:
1893:
1890:
1880:
1873:
1870:
1867:
1864:
1861:
1860:
1859:
1773:
1771:
1770:
1765:
1763:
1749:
1748:
1692:
1691:
1676:
1675:
1660:
1659:
1644:
1643:
1620:
1619:
1604:
1603:
1588:
1587:
1572:
1571:
1556:
1555:
1521:
1519:
1518:
1513:
1511:
1510:
1509:
1496:
1482:
1480:
1479:
1474:
1472:
1471:
1470:
1457:
1425:
1423:
1422:
1417:
1409:
1408:
1407:
1390:
1388:
1387:
1382:
1374:
1373:
1365:
1364:
1363:
1349:
1348:
1347:
1327:
1325:
1324:
1319:
1311:
1310:
1302:
1301:
1300:
1286:
1285:
1284:
1264:
1262:
1261:
1256:
1254:
1253:
1237:
1235:
1234:
1229:
1221:
1220:
1219:
1209:
1208:
1192:
1190:
1189:
1184:
1182:
1181:
1180:
1159:
1157:
1156:
1151:
1149:
1148:
1147:
1119:
1117:
1116:
1111:
1109:
1093:
1091:
1090:
1085:
1083:
1082:
1066:
1064:
1063:
1058:
1056:
1022:
1020:
1019:
1014:
1012:
1000:
998:
997:
992:
972:
970:
969:
964:
956:
955:
944:
941:
913:
911:
910:
905:
903:
879:
877:
876:
871:
869:
868:
867:
854:
836:
834:
833:
828:
812:
810:
809:
804:
783:
781:
780:
775:
747:
745:
744:
739:
737:
736:
716:
714:
713:
708:
684:
682:
681:
676:
674:
673:
602:
600:
599:
594:
592:
584:
570:, so the system
553:
551:
550:
545:
543:
535:
520:
518:
517:
512:
504:
475:
473:
472:
467:
448:
446:
445:
440:
438:
430:
400:
398:
397:
392:
384:
362:
360:
359:
354:
336:
334:
333:
328:
326:
308:
306:
305:
300:
298:
286:
284:
283:
278:
276:
275:
274:
251:
249:
248:
243:
235:
223:
221:
220:
215:
213:
205:
188:
186:
185:
180:
178:
173:
172:
171:
107:
104:
98:
96:
55:
27:
19:
3236:
3235:
3231:
3230:
3229:
3227:
3226:
3225:
3211:
3210:
3209:
3208:
3164:
3163:
3156:
3149:
3132:
3131:
3120:
3115:
3102:
3073:There exists a
3010:
2996:
2990:
2989:
2952:
2950:
2936:
2930:
2929:
2899:
2893:
2892:
2848:
2834:
2828:
2827:
2816:
2793:
2769:
2768:
2745:
2744:
2725:
2724:
2703:
2698:
2697:
2678:
2677:
2653:
2642:
2641:
2620:
2615:
2614:
2595:
2594:
2570:
2565:
2564:
2545:
2544:
2525:
2524:
2499:
2494:
2493:
2468:
2463:
2462:
2448:
2447:
2437:
2427:
2414:
2407:
2401:
2400:
2390:
2374:
2364:
2355:
2354:
2335:
2327:
2278:
2264:
2258:
2257:
2219:
2214:
2213:
2184:
2178:
2177:
2132:
2130:
2116:
2110:
2109:
2102:
2094:convex polytope
2075:
2001:
1996:
1995:
1974:
1973:
1968:
1962:
1961:
1956:
1946:
1932:
1927:
1926:
1854:
1853:
1848:
1843:
1838:
1833:
1827:
1826:
1821:
1816:
1811:
1806:
1796:
1784:
1783:
1761:
1760:
1750:
1740:
1704:
1703:
1693:
1683:
1667:
1651:
1635:
1632:
1631:
1621:
1611:
1595:
1579:
1563:
1547:
1538:
1537:
1532:
1491:
1485:
1484:
1452:
1446:
1445:
1399:
1393:
1392:
1355:
1353:
1339:
1333:
1332:
1292:
1290:
1276:
1270:
1269:
1245:
1240:
1239:
1211:
1200:
1195:
1194:
1172:
1166:
1165:
1139:
1133:
1132:
1100:
1099:
1074:
1069:
1068:
1047:
1046:
1003:
1002:
1001:and the vector
983:
982:
979:
947:
924:
923:
894:
893:
886:
849:
843:
842:
819:
818:
795:
794:
766:
765:
728:
723:
722:
699:
698:
665:
660:
659:
650:be a subset of
619:of the LP is a
613:
572:
571:
523:
522:
495:
494:
487:
458:
457:
418:
417:
407:slack variables
375:
374:
345:
344:
317:
316:
289:
288:
266:
260:
259:
226:
225:
193:
192:
163:
157:
156:
149:equational form
145:
140:
108:
102:
99:
56:
54:
40:
28:
17:
12:
11:
5:
3234:
3232:
3224:
3223:
3213:
3212:
3207:
3206:
3154:
3147:
3135:Matoušek, Jiří
3117:
3116:
3114:
3111:
3110:
3109:
3101:
3100:External links
3098:
3094:
3093:
3082:
3067:Nimrod Megiddo
3042:
3039:
3034:
3031:
3024:
3019:
3015:
3009:
3003:
2999:
2977:
2974:
2969:
2966:
2959:
2955:
2949:
2943:
2939:
2913:
2906:
2902:
2880:
2877:
2872:
2869:
2862:
2857:
2853:
2847:
2841:
2837:
2815:
2812:
2799:, such as the
2792:
2789:
2776:
2752:
2732:
2710:
2706:
2685:
2660:
2656:
2652:
2649:
2627:
2623:
2602:
2577:
2573:
2552:
2532:
2506:
2502:
2475:
2471:
2444:
2440:
2434:
2430:
2426:
2421:
2417:
2413:
2410:
2408:
2406:
2403:
2402:
2397:
2393:
2389:
2386:
2383:
2380:
2377:
2375:
2371:
2367:
2363:
2362:
2334:
2331:
2326:
2323:
2310:
2307:
2302:
2299:
2292:
2287:
2283:
2277:
2271:
2267:
2254:
2253:
2240:
2236:
2232:
2226:
2222:
2210:
2198:
2191:
2187:
2157:
2154:
2149:
2146:
2139:
2135:
2129:
2123:
2119:
2101:
2098:
2074:
2071:
2058:
2055:
2046:
2037:
2028:
2019:
2016:
2013:
2008:
2004:
1978:
1972:
1969:
1967:
1964:
1963:
1960:
1957:
1955:
1952:
1951:
1949:
1944:
1939:
1935:
1901:
1898:
1889:
1886:
1883:
1879:
1858:
1852:
1849:
1847:
1844:
1842:
1839:
1837:
1834:
1832:
1829:
1828:
1825:
1822:
1820:
1817:
1815:
1812:
1810:
1807:
1805:
1802:
1801:
1799:
1794:
1791:
1759:
1756:
1753:
1751:
1747:
1743:
1739:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1709:
1706:
1705:
1702:
1699:
1696:
1694:
1690:
1686:
1682:
1679:
1674:
1670:
1666:
1663:
1658:
1654:
1650:
1647:
1642:
1638:
1634:
1633:
1630:
1627:
1624:
1622:
1618:
1614:
1610:
1607:
1602:
1598:
1594:
1591:
1586:
1582:
1578:
1575:
1570:
1566:
1562:
1559:
1554:
1550:
1546:
1545:
1531:
1528:
1508:
1503:
1500:
1495:
1469:
1464:
1461:
1456:
1432:feasible basis
1415:
1412:
1406:
1402:
1380:
1377:
1372:
1369:
1362:
1358:
1352:
1346:
1342:
1317:
1314:
1309:
1306:
1299:
1295:
1289:
1283:
1279:
1252:
1248:
1227:
1224:
1218:
1214:
1207:
1203:
1179:
1175:
1146:
1142:
1108:
1081:
1077:
1055:
1011:
990:
978:
975:
962:
959:
954:
950:
940:
937:
934:
931:
902:
888:Given a basis
885:
882:
866:
861:
858:
853:
826:
802:
773:
735:
731:
706:
672:
668:
631:rows and only
612:
609:
591:
587:
583:
579:
542:
538:
534:
530:
510:
507:
503:
486:
483:
482:
481:
465:
450:
437:
433:
429:
425:
403:
402:
390:
387:
383:
372:
352:
342:
325:
314:
297:
273:
269:
253:
252:
241:
238:
234:
212:
208:
204:
200:
189:
177:
170:
166:
144:
141:
139:
136:
110:
109:
45:. Please help
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
3233:
3222:
3219:
3218:
3216:
3202:
3198:
3194:
3190:
3185:
3184:10.1.1.11.427
3180:
3176:
3172:
3168:
3161:
3159:
3155:
3150:
3148:3-540-30697-8
3144:
3140:
3136:
3129:
3127:
3125:
3123:
3119:
3112:
3107:
3104:
3103:
3099:
3097:
3091:
3087:
3083:
3080:
3076:
3072:
3071:
3070:
3068:
3064:
3060:
3056:
3040:
3037:
3032:
3029:
3022:
3017:
3013:
3007:
2975:
2972:
2967:
2964:
2957:
2953:
2947:
2926:
2878:
2875:
2870:
2867:
2860:
2855:
2851:
2845:
2825:
2821:
2813:
2811:
2809:
2804:
2802:
2798:
2790:
2788:
2774:
2765:
2750:
2730:
2708:
2704:
2683:
2674:
2658:
2654:
2650:
2647:
2625:
2621:
2600:
2591:
2575:
2571:
2550:
2530:
2522:
2504:
2500:
2491:
2473:
2469:
2442:
2438:
2432:
2428:
2424:
2419:
2415:
2411:
2409:
2404:
2395:
2391:
2387:
2384:
2381:
2378:
2376:
2369:
2365:
2352:
2348:
2345:(a subset of
2344:
2340:
2332:
2330:
2324:
2322:
2308:
2305:
2300:
2297:
2290:
2285:
2281:
2275:
2234:
2224:
2220:
2211:
2175:
2174:
2173:
2171:
2155:
2152:
2147:
2144:
2137:
2133:
2127:
2107:
2099:
2097:
2095:
2091:
2087:
2079:
2072:
2070:
2053:
2044:
2035:
2026:
2017:
2011:
2006:
2002:
1992:
1976:
1970:
1965:
1958:
1953:
1947:
1942:
1937:
1933:
1924:
1919:
1917:
1912:
1896:
1887:
1881:
1856:
1850:
1845:
1840:
1835:
1830:
1823:
1818:
1813:
1808:
1803:
1797:
1792:
1789:
1781:
1779:
1774:
1757:
1754:
1752:
1745:
1741:
1737:
1731:
1728:
1725:
1722:
1719:
1713:
1710:
1700:
1697:
1695:
1688:
1684:
1680:
1677:
1672:
1668:
1664:
1661:
1656:
1652:
1648:
1645:
1640:
1636:
1628:
1625:
1623:
1616:
1612:
1608:
1605:
1600:
1596:
1592:
1589:
1584:
1580:
1576:
1573:
1568:
1564:
1560:
1557:
1552:
1548:
1535:
1529:
1527:
1525:
1501:
1498:
1462:
1459:
1442:
1440:
1435:
1433:
1429:
1413:
1410:
1378:
1375:
1370:
1367:
1360:
1356:
1350:
1328:
1315:
1312:
1307:
1304:
1297:
1293:
1287:
1266:
1250:
1246:
1225:
1222:
1205:
1201:
1163:
1130:
1126:
1121:
1097:
1079:
1075:
1043:
1041:
1037:
1033:
1029:
1024:
988:
976:
974:
960:
957:
952:
948:
938:
935:
932:
929:
921:
917:
891:
883:
881:
859:
856:
840:
824:
816:
800:
791:
790:
787:
771:
763:
759:
755:
751:
733:
729:
720:
704:
696:
692:
688:
670:
666:
658:}. Denote by
657:
653:
649:
645:
640:
638:
634:
630:
626:
623:submatrix of
622:
618:
610:
608:
606:
585:
577:
569:
565:
561:
557:
536:
528:
508:
505:
492:
484:
479:
463:
455:
451:
431:
423:
415:
414:
413:
410:
408:
388:
385:
373:
370:
366:
350:
343:
340:
315:
312:
258:
257:
256:
239:
236:
206:
198:
190:
154:
153:
152:
150:
142:
137:
135:
133:
129:
125:
121:
117:
106:
103:December 2018
95:
92:
88:
85:
81:
78:
74:
71:
67:
64: –
63:
59:
58:Find sources:
52:
48:
44:
38:
37:
36:single source
32:This article
30:
26:
21:
20:
3177:(1): 63–65.
3174:
3170:
3138:
3095:
3089:
3078:
3058:
3054:
2927:
2824:dual-optimal
2823:
2819:
2817:
2807:
2805:
2794:
2766:
2675:
2592:
2520:
2489:
2350:
2346:
2342:
2336:
2328:
2255:
2105:
2103:
2083:
1993:
1922:
1920:
1915:
1913:
1782:
1777:
1775:
1536:
1533:
1443:
1436:
1431:
1430:is called a
1427:
1330:
1268:
1161:
1128:
1124:
1122:
1095:
1044:
1039:
1035:
1031:
1027:
1025:
980:
919:
915:
889:
887:
838:
814:
792:
788:
785:
762:column space
753:
718:
694:
690:
686:
655:
651:
647:
643:
641:
636:
632:
628:
624:
616:
614:
604:
567:
563:
559:
555:
490:
488:
477:
453:
411:
404:
368:
364:
338:
310:
254:
148:
146:
123:
119:
113:
100:
90:
83:
76:
69:
57:
33:
2212:subject to
2086:hyperspaces
1776:The matrix
1160:with basis
750:nonsingular
717:indexed by
697:columns of
685:the square
621:nonsingular
607:of the LP.
416:The system
191:subject to
138:Definitions
3113:References
3059:PD-optimal
3057:is called
977:Properties
521:such that
128:polyhedron
73:newspapers
3201:0899-1499
3179:CiteSeerX
3038:⋅
3030:−
2973:⋅
2965:−
2876:⋅
2868:−
2651:≤
2306:⋅
2298:−
2235:≥
2176:minimize
2153:⋅
2145:−
1755:≥
1726:…
1714:∈
1708:∀
1411:≥
1376:⋅
1368:−
1313:⋅
1305:−
639:columns.
627:with all
506:≥
386:≥
237:≥
155:maximize
43:talk page
3215:Category
3137:(2006).
2928:If both
2818:A basis
1921:The set
1530:Examples
933:∉
2349:out of
1426:, then
880:bases.
760:of the
371:matrix;
255:where:
87:scholar
3199:
3181:
3145:
2461:where
2051:
2048:
2042:
2039:
2033:
2030:
2024:
2021:
1914:Here,
1894:
1891:
1874:
1871:
1868:
1865:
1862:
945:
942:
756:are a
363:is an
89:
82:
75:
68:
60:
2808:basic
914:is a
758:basis
721:. If
644:basis
617:basis
611:Basis
566:<
94:JSTOR
80:books
3197:ISSN
3143:ISBN
3090:only
1780:is:
837:has
689:-by-
635:<
452:All
367:-by-
287:and
224:and
118:, a
66:news
3189:doi
3079:and
2172::
1127:of
813:is
764:of
748:is
124:BFS
49:by
3217::
3195:.
3187:.
3173:.
3169:.
3157:^
3121:^
2810:.
2673:.
2590:.
2321:.
2069:.
1888:14
1629:14
1434:.
1120:.
973:.
625:A,
615:A
558:=
489:A
409:.
151::
3203:.
3191::
3175:3
3151:.
3055:B
3041:c
3033:1
3023:T
3018:B
3014:A
3008:=
3002:B
2998:y
2976:b
2968:1
2958:B
2954:A
2948:=
2942:B
2938:x
2912:y
2905:T
2901:b
2879:c
2871:1
2861:T
2856:B
2852:A
2846:=
2840:B
2836:y
2820:B
2775:z
2751:z
2731:r
2709:5
2705:x
2684:r
2659:0
2655:z
2648:z
2626:0
2622:z
2601:r
2576:0
2572:z
2551:p
2531:z
2521:n
2505:N
2501:x
2490:m
2474:B
2470:x
2443:N
2439:x
2433:T
2429:r
2425:+
2420:0
2416:z
2412:=
2405:z
2396:N
2392:x
2388:Q
2385:+
2382:p
2379:=
2370:B
2366:x
2351:n
2347:m
2343:B
2309:c
2301:1
2291:T
2286:B
2282:A
2276:=
2270:B
2266:y
2252:.
2239:c
2231:y
2225:T
2221:A
2197:y
2190:T
2186:b
2156:b
2148:1
2138:B
2134:A
2128:=
2122:B
2118:x
2106:B
2057:)
2054:0
2045:1
2036:0
2027:2
2018:0
2015:(
2012:=
2007:B
2003:x
1977:)
1971:5
1966:1
1959:4
1954:5
1948:(
1943:=
1938:B
1934:A
1923:B
1916:m
1900:)
1897:7
1885:(
1882:=
1878:b
1857:)
1851:6
1846:5
1841:3
1836:1
1831:0
1824:6
1819:4
1814:3
1809:5
1804:1
1798:(
1793:=
1790:A
1778:A
1758:0
1746:i
1742:x
1738::
1735:}
1732:5
1729:,
1723:,
1720:1
1717:{
1711:i
1701:7
1698:=
1689:5
1685:x
1681:6
1678:+
1673:4
1669:x
1665:5
1662:+
1657:3
1653:x
1649:3
1646:+
1641:2
1637:x
1626:=
1617:5
1613:x
1609:6
1606:+
1601:4
1597:x
1593:4
1590:+
1585:3
1581:x
1577:3
1574:+
1569:2
1565:x
1561:5
1558:+
1553:1
1549:x
1507:)
1502:m
1499:n
1494:(
1468:)
1463:m
1460:n
1455:(
1428:B
1414:0
1405:B
1401:x
1379:b
1371:1
1361:B
1357:A
1351:=
1345:B
1341:x
1316:b
1308:1
1298:B
1294:A
1288:=
1282:B
1278:x
1251:B
1247:A
1226:b
1223:=
1217:B
1213:x
1206:B
1202:A
1178:B
1174:x
1162:B
1145:B
1141:x
1129:m
1125:B
1107:x
1096:K
1080:K
1076:A
1054:x
1040:m
1036:m
1034:-
1032:n
1028:m
1010:b
989:A
961:0
958:=
953:j
949:x
939::
936:B
930:j
920:B
901:x
890:B
865:)
860:m
857:n
852:(
839:n
825:A
815:m
801:A
786:B
772:A
754:B
734:B
730:A
719:B
705:A
695:m
691:m
687:m
671:B
667:A
656:n
652:m
648:B
637:n
633:m
629:m
590:b
586:=
582:x
578:A
568:n
564:m
560:n
556:m
541:b
537:=
533:x
529:A
509:0
502:x
478:m
464:A
454:m
436:b
432:=
428:x
424:A
389:0
382:x
369:n
365:m
351:A
339:m
324:b
311:n
296:x
272:T
268:c
240:0
233:x
211:b
207:=
203:x
199:A
176:x
169:T
165:c
122:(
105:)
101:(
91:·
84:·
77:·
70:·
53:.
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
