Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2003 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Linear-Fractional Programming Theory, Methods, Applications and Software

verfasst von: Erik B. Bajalinov

Verlag: Springer US

Buchreihe : Applied Optimization

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This 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.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
This book deals with linear-fractional programming (LFP). The object of LFP is to find the optimal (maximal or minimal) value of a ear-fractional objective functionsubject to linear constraintson the given variables. If all unknown variables are real valued then we say that the problem is real or continuous. In the case of one or more integer-valued variables we usually say that the problem is integer or IP. The IP problem may be pure, if all the variables must have in optimal solution an integer value, ormixed in the other case.
Erik B. Bajalinov
Chapter 2. Basic Linear Algebra
Abstract
In this chapter, we begin by giving some familiar definitions for the sake of completeness and to refresh readers’ memory. We survey the topics of linear algebra that will be needed in the rest of the book. First, we discuss the building blocks of linear algebra: vectors, matrices, linear dependence and independence, determinants, etc. We continue the chapter with an introduction to inverse of matrix, then we use our knowledge of matrices and vectors to develop a systematic procedure (Gaussian elimination method) for solving linear equations, which we then use to invert matrices. Finally, we close the chapter with a short description of the Gauss-Jordan method for solving systems of linear equations. The material covered in this chapter will be used in our study of linearfractional programming.
Erik B. Bajalinov
Chapter 3. Introduction to LFP
Abstract
This is an introduction to the theory of linear-fractional programming. Here we define the common problem of LFP, give its main economic interpretation, formulate and prove the main lemmas and theorems of LFP and describe some important real-world applications where the use of LFP may prove to be quite useful.
Problems of LFP arise when there appears a necessity to optimize the efficiency of some activity: profit gained by company per unit of expenditure of labor, cost of production per unit of produced goods, nutritiousness of ration per unit of cost, etc. Nowadays because of a deficit of natural resources the use of specific criteria becomes more and more topical. So an application of LFP to solving real-world problems connected with optimizing efficiency could be as useful as in the case of LP.
Erik B. Bajalinov
Chapter 4. The Simplex Method
Abstract
In 1947, George Dantzig [51] developed an efficient method, the simplex algorithm, for solving linear programming problems. Since the development of the simplex method, LP has been used to solve optimization problems any where where there appears a necessity of optimizing some absolute criteria. It might be, for example, cost of trucking, profit gained by some company, number of full-time employees, cost of nutrition rations, etc.
Erik B. Bajalinov
Chapter 5. Duality Theory
Abstract
In accordance with the duality theory of mathematical programming every mathematical programming problem has an associated dual problem. The relationship between these two problems is very useful when investigating properties of optimal solutions of both problems. Principles of duality appear in various branches of mathematics, physics and statistics. These principles are valid in linear-fractional programming too — for any LFP problem (primal problem) we can formulate (construct) some other problem (dual problem), which is very closely connected with the original problem. These connections between primal and dual problems turn out to be of great practical use. Also, duality in LFP admits an elegant and useful economic interpretation.
Erik B. Bajalinov
Chapter 6. Sensitivity Analysis
Abstract
In this chapter, we discuss how changes in the coefficients (including RHS vector b and the coefficients of objective function Q(x)) of LFP problems affect the optimal solution. This is called sensitivity analysis. First, in Section 1, we illustrate the concept of sensitivity analysis through a graphical example. Then in Sections 2-6 we consider separate cases when changes occur in different parts of an LFP problem.
Erik B. Bajalinov
Chapter 7. Interconnection Between LFP and LP
Abstract
As we have seen in Chapter 5, dual variables of LFP indicate if a small change in RHS vector 6 alters the optimal value of numerator P(x) of objective function Q(x) and hence, affects the optimal value of Q(x). It means that the economic interpretation of dual variables in LFP and in LP may be very much alike. However, as is shown by formulas (5.98) and (5.113), dual variables of LFP act more selectively than dual variables of LP. Moreover, if the latest may be interpreted as a total change in profit P(x) when changing resource vector 6, then variables y i , i = 1,2,…, m indicate only the intensive part of a total change in profit. In this chapter we deal with the interconnection between problems of LFP and LP, and their dual variables. We will show how this close connection may be used in real-world applications.
Erik B. Bajalinov
Chapter 8. Integer LFP
Abstract
In some practical applications the unknown variables of a linear-fractional problem are constrained to a discrete set. Such a discrete set may consist of enumerated arbitrary (integer or real) values. If this set of feasible values for unknown variables consists of integer values, such a class of LFP problems is usually called integer linear-fractional programming or ILFP. Examples of applications of integer LFP are mostly in the field of economics and engineering, where it is very important to find such solution that provides the biggest value of a ratio expressed as an objective function — it may be a ratio of revenues and allocations subject to restriction on the availability of the goods involved in the location problem, or a maximal density of integrated elements of an electronic chip designed, etc. If the set of enumerated feasible values for unknown variables contains not only integers but real values too, we usually refer to such of LFP problems as discrete LFP. For example, the following LFP problem is a discrete LFP problem.
Erik B. Bajalinov
Chapter 9. Special LFP Problems
Abstract
In this chapter, we discuss the following special classes of linear-fractional programming problems: transportation problems, assignment problems, and transshipment problems. While each of these problems can be solved by the simplex method, there are specialized algorithms for each type of problems that are much more efficient than the simplex algorithm.
Erik B. Bajalinov
Chapter 10. Advanced Methods and Algorithms in LFP
Abstract
In this chapter, we describe the state of the art in LFP methods. We start by presenting some special variants of the simplex method (including the so-called Dual Simplex Method and the Criss-Cross Method), and then we go on to discuss one of the so-called Interior-Point Methods (IPM)of linear-fractional programming, namely the Method of Analytic Centersproposed by A.S.Nemirovskii [139], [140].
Erik B. Bajalinov
Chapter 11. Advanced Topics in LFP
Abstract
In this chapter, we briefly indicate several new directions of investigations in fractional programming made in the last decades. We discuss here the following extensions of linear-fractional programming: generalized LFP and LFP problems with multiple objective functions.
Erik B. Bajalinov
Chapter 12. Computational Aspects
Abstract
Let us consider the following LFP problem in a canonical form:
Erik B. Bajalinov
Chapter 13. The Wingulf Package
Abstract
WinGULF — is a General, User-friendly Linear and linear-Fractional programming package for Windows.
Erik B. Bajalinov
Backmatter
Metadaten
Titel
Linear-Fractional Programming Theory, Methods, Applications and Software
verfasst von
Erik B. Bajalinov
Copyright-Jahr
2003
Verlag
Springer US
Electronic ISBN
978-1-4419-9174-4
Print ISBN
978-1-4613-4822-1
DOI
https://doi.org/10.1007/978-1-4419-9174-4