دسترسی نامحدود
برای کاربرانی که ثبت نام کرده اند
برای ارتباط با ما می توانید از طریق شماره موبایل زیر از طریق تماس و پیامک با ما در ارتباط باشید
در صورت عدم پاسخ گویی از طریق پیامک با پشتیبان در ارتباط باشید
برای کاربرانی که ثبت نام کرده اند
درصورت عدم همخوانی توضیحات با کتاب
از ساعت 7 صبح تا 10 شب
دسته بندی: برنامه نويسي ویرایش: نویسندگان: Alexander Schrijver سری: ISBN (شابک) : 0471982326, 9780585302317 ناشر: Wiley سال نشر: 1998 تعداد صفحات: 483 زبان: English فرمت فایل : DJVU (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) حجم فایل: 4 مگابایت
در صورت تبدیل فایل کتاب Theory of linear and integer programming به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.
توجه داشته باشید کتاب نظریه برنامه نویسی خطی و عدد صحیح نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.
تئوری برنامه نویسی خطی و صحیح Alexander Schrijver Centrum voor Wiskunde en Informatica، آمستردام، هلند این کتاب تئوری برنامه ریزی خطی و صحیح را توصیف می کند و الگوریتم های مسائل برنامه ریزی خطی و صحیح را بررسی می کند، با تمرکز بر تجزیه و تحلیل پیچیدگی. هدف آن تکمیل کتاب های کاربردی تر در این زمینه است. یک ویژگی خاص، پوشش نویسنده از تحولات مهم اخیر در برنامه ریزی خطی و عدد صحیح است. برنامه های کاربردی برای بهینه سازی ترکیبی ارائه شده است، و نویسنده همچنین شامل بررسی های تاریخی و کتابشناسی گسترده است. این کتاب برای دانشجویان تحصیلات تکمیلی و محققین در تحقیقات عملیات، ریاضیات و علوم کامپیوتر در نظر گرفته شده است. همچنین برای مورخان ریاضی جالب خواهد بود. مطالب 1 مقدمه و مقدمات; 2 مشکلات، الگوریتم ها و پیچیدگی. 3 جبر خطی و پیچیدگی. 4 نظریه شبکه ها و معادلات دیوفانتین خطی. 5 الگوریتم برای معادلات دیوفانتین خطی. 6 تقریب دیوفانتین و کاهش پایه. 7 مفاهیم اساسی و نتایج در چندوجهی، نابرابری های خطی، و برنامه ریزی خطی. 8 ساختار چند وجهی; 9 قطبیت و چند وجهی مسدود کننده و ضد انسداد. 10 اندازه ها و پیچیدگی نظری نابرابری های خطی و برنامه ریزی خطی. 11 روش سیمپلکس; 12 روش اولیه-دوگانه، حذف و آرام سازی. 13 روش خاچیان برای برنامه ریزی خطی. 14 روش بیضی برای چند وجهی به طور کلی تر. 15 چند جمله ای بیشتر منجر به برنامه ریزی خطی می شود. 16 مقدمه ای بر برنامه ریزی خطی اعداد صحیح. 17 برآورد در برنامه ریزی خطی اعداد صحیح. 18 پیچیدگی برنامه ریزی خطی عدد صحیح. 19 ماتریس های کاملاً تک مدولار: ویژگی ها و مثال های اساسی. 20 تشخیص یکنواختی کامل. 21 تئوری بیشتر مربوط به یکپارچگی کل. 22 چندوجهی انتگرال و یکپارچگی دوگانه کل. 23 هواپیما برش; 24 روش های بیشتر در برنامه ریزی خطی اعداد صحیح. یادداشت های تاریخی و بیشتر در مورد برنامه ریزی خطی عدد صحیح؛ منابع؛ شاخص نشانه گذاری; فهرست نویسنده; نمایه موضوعی
Theory of Linear and Integer Programming Alexander Schrijver Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands This book describes the theory of linear and integer programming and surveys the algorithms for linear and integer programming problems, focusing on complexity analysis. It aims at complementing the more practically oriented books in this field. A special feature is the author's coverage of important recent developments in linear and integer programming. Applications to combinatorial optimization are given, and the author also includes extensive historical surveys and bibliographies. The book is intended for graduate students and researchers in operations research, mathematics and computer science. It will also be of interest to mathematical historians. Contents 1 Introduction and preliminaries; 2 Problems, algorithms, and complexity; 3 Linear algebra and complexity; 4 Theory of lattices and linear diophantine equations; 5 Algorithms for linear diophantine equations; 6 Diophantine approximation and basis reduction; 7 Fundamental concepts and results on polyhedra, linear inequalities, and linear programming; 8 The structure of polyhedra; 9 Polarity, and blocking and anti-blocking polyhedra; 10 Sizes and the theoretical complexity of linear inequalities and linear programming; 11 The simplex method; 12 Primal-dual, elimination, and relaxation methods; 13 Khachiyan's method for linear programming; 14 The ellipsoid method for polyhedra more generally; 15 Further polynomiality results in linear programming; 16 Introduction to integer linear programming; 17 Estimates in integer linear programming; 18 The complexity of integer linear programming; 19 Totally unimodular matrices: fundamental properties and examples; 20 Recognizing total unimodularity; 21 Further theory related to total unimodularity; 22 Integral polyhedra and total dual integrality; 23 Cutting planes; 24 Further methods in integer linear programming; Historical and further notes on integer linear programming; References; Notation index; Author index; Subject index
Cover......Page 1
Title Page......Page 4
Copyright Page......Page 5
Preface......Page 6
Contents\0......Page 8
1.1 Introduction,\0......Page 14
1.2 General preliminaries,\0......Page 16
1.3 Preliminaries from linear algebra, matrix theory, and Euclidean geometry,\0......Page 17
1.4 Some graph theory,\0......Page 21
2 Problems, algorithms, and complexity\0......Page 27
2.2 Problems,\0......Page 28
2.3 Algorithms and running time,\0......Page 29
2.4 Polynomial algorithms,\0......Page 30
2.5 The classes 9, .K9, and co-.N\'9,\0......Page 31
2.6 .K9-complete problems,\0......Page 33
Some historical notes,\0......Page 34
PART I: LINEAR ALGEBRA\0......Page 38
3.1 Some theory,\0......Page 40
3.2 Sizes and good characterizations,\0......Page 42
3.3 The Gaussian elimination method,\0......Page 44
3.4 Iterative methods,\0......Page 49
Historical notes,\0......Page 51
Further notes on linear algebra,\0......Page 53
PART II: LATTICES AND LINEAR DIOPHANTINE EQUATIONS\0......Page 56
4.1 The Hermite normal form,\0......Page 58
4.3 Unimodular matrices,\0......Page 61
4.4 Further remarks,\0......Page 63
5.1 The Euclidean algorithm,\0......Page 65
5.2 Sizes and good characterizations,\0......Page 67
5.3 Polynomial algorithms for Hermite normal forms and systems of linear diophantine equations,\0......Page 69
6.1 The continued fraction method,\0......Page 73
6.2 Basis reduction in lattices,\0......Page 80
6.3 Applications of the basis reduction method,\0......Page 84
Historical notes,\0......Page 89
Further notes on lattices and linear diophantine equations,\0......Page 95
PART III: POLYHEDRA, LINEAR INEQUALITIES, AND LINEAR PROGRAMMING\0......Page 96
7.1 The Fundamental theorem of linear inequalities,\0......Page 98
7.2 Cones, polyhedra, and polytopes,\0......Page 100
7.3 Farkas\' lemma and variants,\0......Page 102
7.4 Linear programming,\0......Page 103
7.5 LP-duality geometrically,\0......Page 105
7.6 Affine form of Farkas\' lemma,\0......Page 106
7.8 Strict inequalities,\0......Page 107
7.9 Complementary slackness,\0......Page 108
7.10 Application: max-flow min-cut,\0......Page 109
8.1 Implicit equalities and redundant constraints,\0......Page 112
8.2 Characteristic cone, lineality space, affine hull, dimension,\0......Page 113
8.4 Facets,\0......Page 114
8.6 The face-lattice,\0......Page 117
8.8 Extremal rays of cones,\0......Page 118
8.9 Decomposition of polyhedra,\0......Page 119
8.10 Application: doubly stochastic matrices,\0......Page 120
8.11 Application: the matching polytope,\0......Page 122
9.1 Polarity,\0......Page 125
9.2 Blocking polyhedra,\0......Page 126
9.3 Anti-blocking polyhedra,\0......Page 129
10.1 Sizes and good characterizations,\0......Page 133
10.2 Vertex and facet complexity,\0......Page 134
10.3 Polynomial equivalence of linear inequalities and linear programming,\0......Page 137
10.4 Sensitivity analysis,\0......Page 138
11.1 The simplex method,\0......Page 142
11.2 The simplex method in tableau form,\0......Page 145
11.3 Pivot selection, cycling, and complexity,\0......Page 150
11.4 The worst-case behaviour of the simplex method,\0......Page 152
11.5 The average running time of the simplex method,\0......Page 155
11.6 The revised simplex method,\0......Page 160
11.7 The dual simplex method,\0......Page 161
12.1 The primal-dual method,\0......Page 164
12.2 The Fourier-Motzkin elimination method,\0......Page 168
12.3 The relaxation method,\0......Page 170
13.1 Ellipsoids,\0......Page 176
13.2 Khachiyan\'s method: outline,\0......Page 178
13.3 Two approximation lemmas,\0......Page 179
13.4 Khachiyan\'s method more precisely,\0......Page 181
13.5 The practical complexity of Khachiyan\'s method,\0......Page 183
13.6 Further remarks,\0......Page 184
14.1 Finding a solution with a separation algorithm,\0......Page 185
14.2 Equivalence of separation and optimization,\0......Page 190
14.3 Further implications,\0......Page 196
15.1 Karmarkar\'s polynomial-time algorithm for linear programming,\0......Page 203
15.2 Strongly polynomial algorithms,\0......Page 207
15.3 Megiddo\'s linear-time LP-algorithm in fixed dimension,\0......Page 212
15.4 Shallow cuts and rounding of polytopes,\0......Page 218
Historical notes,\0......Page 222
Further notes on polyhedra, linear inequalities, and linear programming,\0......Page 236
PART IV: INTEGER LINEAR PROGRAMMING\0......Page 240
16.1 Introduction,\0......Page 242
16.2 The integer hull of a polyhedron,\0......Page 243
16.3 Integral polyhedra,\0......Page 244
16.4 Hilbert bases,\0......Page 245
16.5 A theorem of Bell and Scarf,\0......Page 247
16.6 The knapsack problem and aggregation,\0......Page 248
16.7 Mixed integer linear programming,\0......Page 249
17.1 Sizes of solutions,\0......Page 250
17.2 Distances of optimum solutions,\0......Page 252
17.3 Finite test sets for integer linear programming,\0......Page 255
17.4 The facets of P,,\0......Page 256
18.1 ILP is .N\'9-complete,\0......Page 258
18.2 X61-completeness of related problems,\0......Page 261
18.3 Complexity of facets, vertices, and adjacency on the integer hull,\0......Page 264
18.4 Lenstra\'s algorithm for integer linear programming,\0......Page 269
18.5 Dynamic programming applied to the knapsack problem,\0......Page 274
18.6 Dynamic programming applied to integer linear programming,\0......Page 277
19.1 Total unimodularity and optimization,\0......Page 279
19.2 More characterizations of total unimodularity,\0......Page 282
19.3 The basic examples: network matrices,\0......Page 285
19.4 Decomposition of totally unimodular matrices,\0......Page 292
20.1 Recognizing network matrices,\0......Page 295
20.2 Decomposition test,\0......Page 300
20.3 Total unimodularity test,\0......Page 303
21.1 Regular matroids and signing of {0,1}-matrices,\0......Page 307
21.2 Chain groups,\0......Page 310
21.3 An upper bound of Heller,\0......Page 312
21.4 Unimodular matrices more generally,\0......Page 314
21.5 Balanced matrices,\0......Page 316
22 Integral polyhedra and total dual integrality\0......Page 322
22.1 Integral polyhedra and total dual integrality,\0......Page 323
22.2 Two combinatorial applications,\0......Page 325
22.3 Hilbert bases and minimal TDI-systems,\0......Page 328
22.4 Box-total dual integrality,\0......Page 330
22.5 Behaviour of total dual integrality under operations,\0......Page 334
22.6 An integer analogue of Caratheodory\'s theorem,\0......Page 339
22.7 Another characterization of total dual integrality,\0......Page 340
22.8 Optimization over integral polyhedra and TDI-systems algorithmically,\0......Page 343
22.9 Recognizing integral polyhedra and total dual integrality,\0......Page 345
22.10 Integer rounding and decomposition,\0......Page 349
23.1 Finding the integer hull with cutting planes,\0......Page 352
23.2 Cutting plane proofs,\0......Page 356
23.3 The number of cutting planes and the length of cutting plane proofs,\0......Page 357
23.4 The Chvatal rank,\0......Page 360
23.5 Two combinatorial illustrations,\0......Page 361
23.6 Cutting planes and .N\'9-theory,\0......Page 364
23.7 Chvatal functions and duality,\0......Page 366
23.8 Gomory\'s cutting plane method,\0......Page 367
24.1 Branch-and-bound methods for integer linear progamming,\0......Page 373
24.2 The group problem and corner polyhedra,\0......Page 376
24.3 Lagrangean relaxation,\0......Page 380
24.4 Application: the traveling salesman problem,\0......Page 383
24.5 Benders\' decomposition,\0......Page 384
24.6 Some notes on integer linear programming in practice,\0......Page 385
Historical notes,\0......Page 388
Further notes on integer linear programming,\0......Page 391
References\0......Page 394
Notation index\0......Page 465
Author index\0......Page 467
Subject index\0......Page 478