Linear-Fractional Programming Theory, Methods, Applications and SoftwareThis is a book on Linear-Fractional Programming (here and in what follows we will refer to it as "LFP"). The field of LFP, largely developed by Hungarian mathematician B. Martos and his associates in the 1960's, is concerned with problems of op timization. LFP problems deal with determining the best possible allo cation of available resources to meet certain specifications. In particular, they may deal with situations where a number of resources, such as people, materials, machines, and land, are available and are to be combined to yield several products. In linear-fractional programming, the goal is to determine a per missible allocation of resources that will maximize or minimize some specific showing, such as profit gained per unit of cost, or cost of unit of product produced, etc. Strictly speaking, linear-fractional programming is a special case of the broader field of Mathematical Programming. LFP deals with that class of mathematical programming problems in which the relations among the variables are linear: the con straint relations (i.e. the restrictions) must be in linear form and the function to be optimized (i.e. the objective function) must be a ratio of two linear functions. |
Contents
INTRODUCTION | 1 |
2 Description of the content | 3 |
3 What is new in this book? | 5 |
5 How to use the book for courses | 6 |
BASIC LINEAR ALGEBRA | 7 |
2 Vectors and their Properties | 14 |
3 Linear Independence and Dependence | 17 |
5 The Inverse of Matrix | 19 |
2 Primal Problems | 206 |
3 Stability | 209 |
4 Dual Problems | 211 |
5 Economic Interpretation | 213 |
6 Numeric Example | 215 |
7 Discussion Questions and Exercises | 218 |
INTEGER LFP | 219 |
1 LFP Models with Integer Variables | 221 |
6 Matrices and Systems of Linear Equations | 22 |
7 The Gaussian Elimination | 24 |
72 Main Steps | 25 |
73 Forward Substitution | 29 |
74 Pivoting | 31 |
8 The GaussJordan Elimination | 32 |
9 Multiple RHSs and Inverses | 37 |
10 Discussion Questions and Exercises | 38 |
INTRODUCTION TO LFP | 41 |
11 Main Definitions | 43 |
13 Main Forms of the LFP Problem | 45 |
2 The Graphical Method | 48 |
22 Multiple Optimal Solutions | 50 |
23 Mixed cases | 51 |
3 Charnes Coopers Transformation | 54 |
4 Dinkelbachs Algorithm | 59 |
5 LFP models | 62 |
52 A Maritime Transportation Problem | 63 |
53 Product Planning | 64 |
54 A Financial Problem | 65 |
55 A Transportation Problem | 66 |
56 A Blending Problem | 68 |
57 A Location Problem | 70 |
6 Discussion Questions and Exercises | 72 |
THE SIMPLEX METHOD | 75 |
1 Main Definitions and Theorems | 76 |
2 Criteria of Optimality | 79 |
3 General Scheme of the Simplex Method | 83 |
4 Simplex Tableau | 86 |
5 Connection Between Iterations | 87 |
52 Pivot Transformation | 89 |
6 Initialization of the Simplex Method | 90 |
61 The Big M Method | 93 |
62 The TwoPhase Simplex Method | 100 |
7 Compact Form of the Simplex Tableau | 104 |
8 Rules of Entering and Dropping Variables | 108 |
81 Entering Rules | 109 |
82 Dropping Rules | 111 |
9 Degeneracy and Cycling | 112 |
10 UnrestrictedInSign Variables | 116 |
11 Bounded Variables | 117 |
12 Discussion Questions and Exercises | 126 |
DUALITY THEORY | 129 |
2 Golsteintype Lagrangian | 133 |
3 Main Theorems | 142 |
4 Computational Relations Between Primal and Dual Problems | 154 |
5 Connection with Linear Programming | 158 |
6 Dual Variables in Stability Analysis | 160 |
7 Comparative Analysis of Dual Variables in LP and LFP | 168 |
8 Discussion Questions and Exercises | 174 |
SENSITIVITY ANALYSIS | 177 |
1 Graphical Introduction to Sensitivity Analysis | 178 |
2Change in RHS Vector b | 180 |
3 Change in Numerator Vector p | 187 |
4 Change in Numerator Constant p₀ | 192 |
5 Change in Denominator Vector d | 194 |
6 Change in Denominator Constant d₀ | 199 |
7 Discussion Questions and Exercises | 201 |
INTERCONNECTION BETWEEN LFP AND LP | 205 |
12 Capital Budgeting Problems | 222 |
13 Set Covering Problems | 223 |
14 The Traveling Salesperson Problem | 225 |
2 The BranchandBound Method | 226 |
3 The Cutting Plane Method | 233 |
4 Formulating discrete LFP Problems | 240 |
42 Practical Situations | 241 |
5 Discussion Questions and Exercises | 243 |
SPECIAL LFP PROBLEMS | 245 |
12 The Transportation Simplex Method | 248 |
13 Determining Initial BFS | 257 |
14 Numerical Example | 267 |
15 Duality Theory for the Transportation Problem | 274 |
2 The Transshipment Problem | 278 |
3 The Assignment Problem | 282 |
4 Discussion Questions and Exercises | 284 |
ADVANCED METHODS AND ALGORITHMS IN LFP | 287 |
2 The CrissCross Method | 293 |
3 The InteriorPoint Methods | 298 |
4 Discussion Questions and Exercises | 301 |
ADVANCED TOPICS IN LFP | 303 |
2 Multiobjective LFP | 307 |
COMPUTATIONAL ASPECTS | 311 |
1 Scaling LFP Problems | 313 |
11 RHS Vector 6 pb | 314 |
12 Column Aⱼ pAⱼ | 317 |
13 Row ai pai | 320 |
14 Numerator Vector p pp | 321 |
15 Denominator Vector d pd | 322 |
16 Scaling Factors | 323 |
17 Numeric examples | 326 |
2 Factorization of Basis Matrix | 330 |
21 LUfactorization | 331 |
22 LUfactorization and Gaussian Elimination | 338 |
23 Updating LU factorization | 343 |
24 Other Types of Factorization | 358 |
3 Reusing Basis | 365 |
4 Iterative Refinement of a Solution | 369 |
5 Sparse matrices | 370 |
51 Sparse Vectors | 371 |
52 Coordinate Scheme | 372 |
53 Collection of Sparse Vectors | 374 |
54 The Linked List | 377 |
6 Discussion Questions and Exercises | 379 |
THE WINGULF PACKAGE | 381 |
1 Program Overview and Background | 382 |
2 The Editor | 385 |
3 Problems with Continuous Variables | 387 |
32 Output | 389 |
33 Interpreting an Optimal Solution | 390 |
34 An LP Example | 394 |
35 An LFP Example | 397 |
4 Problems with Integer Variables | 401 |
42 Output | 402 |
43 An Integer Example | 404 |
5 Future Developments | 405 |
| 409 | |
| 421 | |
Other editions - View all
Linear-Fractional Programming Theory, Methods, Applications and Software E.B. Bajalinov Limited preview - 2003 |
Linear-Fractional Programming Theory, Methods, Applications and Software E.B. Bajalinov Limited preview - 2013 |
Linear-Fractional Programming Theory, Methods, Applications and Software E.B. Bajalinov No preview available - 2013 |
Common terms and phrases
A₁ affect the optimal algorithm b₁ basic feasible solution basic solution basic variables branch-and-bound method calculate Chapter coefficients column column-vector Consider the following corresponding denominator D(x denotes dual problem dual variables elements feasible set Figure formula fractional programming Gauss-Jordan elimination Gaussian elimination hence ILFP initial BFS inverse inverse matrix iteration latter means Let us suppose LFPT linear analogue linear programming linearly independent lower triangular matrix LU-decomposition LU-factorization maximization Method Example multiply Node non-basic nonnegative objective function Q(x obtain the following optimal basis optimal solution optimal value original LFP problem permutation permutation matrix pivot primal LFP problem reduced costs replace RHS vector right-hand side Set covering problem shadow prices simplex method simplex tableau slack variables solvable solve sparse matrix Step subproblems THEOREM transformation transshipment unit unknown variables upper triangular WinGULF zero
Popular passages
Page 414 - Finding the Set of all Efficient Solutions for the Linear Fractional Multiobjective Program with Zero-One Variables.
Page 415 - A Primal Cutting Plane Algorithm for Integer Fractional Programming Problems", Journal of the Operations Research Society of Japan, Vol.19, No.3, 1976, pp.228-244.