Linear Discrete Programming And Its Applications

Linear discrete programming is a collection of procedures for maximizing or minimizing discrete functions subject to given linear constraints. Many of the problems normally encountered in the modem industry and agriculture, such as economy and environment, industry and pollution, protecting and utilizing finite resources, etc., are concerned with the linear discrete programming. This thesis will establish the theory of linear discrete programming so as to satisfy the needs of sustained economic growth. This thesis is organized in four parts.In Chapter 1, the mathematical model of the linear discrete programming, some definitions and theorems are given; quasi-goal programming and direct algorithms are presented. We also present the dual simplex algorithm for solving linear discrete programming and post optimality analysis based on the quasi-goal programming algorithm. The: transportation problems for rushing to deal with an emergency and the assignment problems for rushing to repair are special examples of linear discrete programming; hence, we develop much more efficient algorithms to handle these problems.In Chapter 2, we present the applications of linear discrete programming to some special mathematical programming problems. These special problems deal with the environment and resources mainly. Linear B-programming deals with the programming problems for maximizing benefit on the premise of protecting the environment against pollution or making full use of the finite resources. B-transportation problem is to minimize total transportation cost subject to that all of the goods should be transported from each source to each destination as quickly as possible. B-assignment problem is to optimize total efficiency subject to that all of the jobs should be completed as quickly as possible. A C-transportation problem is a transportation problem in which the amount transported from all the sources to all the destinations is subject to a given number. A C-assignment problem is an assignment problem in which the jobs will be assigned is less than or equal to the total persons and total jobs. Linear discrete programming may be applied to solve these problems.Chapter 3 concentrates on an application of linear discrete programming to the matrix games. Facing a game problem that deals with the gain and loss, an overwhelming majority of decision-makers have an expectation of minimum winnings, his game cost. Applying traditional game theory to a game problem occasionally encountered in the real world, the player would not assure that his real winnings is in excess of the game cost even if he chooses his optimal strategy strictly, also would not assure that his real winnings is larger than a very small payoff. A game problem, in which each player tries for maximal profits on the premise of avoiding his real winnings may be less than his game cost as far as possible, is said to be a B-game problem. A matrix B-game problem may be transformed into a linear discrete programming problem. It is similar to that a traditional matrix game problem may be transformed into a linear programming problem.Chapter 4 is two particular problems of linear discrete programming.