<Student’s name>
Integer Programming
The problem of integer programming (IP) refers to a problem in which some or all variables must take integer values. In the case when the constraints and the objective function are linear dependence problem is called an integer linear programming problem. Otherwise, if at least one non-linear dependence will be, it will be the integer nonlinear programming problem.
Of particular interest to the problems of the IP due to the fact that in many practical problems, we need to find an integer solution due to a discrete series of values of the variables. In the field of forestry complex, these include the following tasks:
- cutting optimization problem ;
- optimal design of forest machinery and equipment;
- optimization of the system service and maintenance of machines and tractors ;
- etc.
As already mentioned, the problem is often solved without IP integer variable conditions, and then rounded the resulting solution with an excess or deficiency. It does not guarantee an optimal integer solution. Therefore, to find the optimal solution integer problems use special methods that take into account that the number of possible solutions to any integer problem is finite. Therefore, we can consider all possible combinations of integer variables and check whether they satisfy the constraints, and the number of satisfying the constraints, choose the best from the point of view of the objective function. This method is called by the exhaustive search. Its complexity with increasing number of variables and extending the scope of boundary conditions is greatly increased. Therefore, it does not apply real-world problems.
In practice, to solve real-world problems should use methods in which all possible alternatives are not considered. The most common is the branch and bound method.
The essence of branch and bound method is sequential search options, considering only those who in some sense are promising and unpromising discarding options. When using the branch and bound region of feasible solutions of the original problem in a certain way is partitioned into disjoint subsets, and subtasks are solved, ie tasks on these subsets with the same objective function and without integrality conditions (as a linear programming problem). If the obtained optimal solution is not an integer, the range of admissible solutions subtasks again broken into parts and this process continues until, until you find the optimal integer solution of the original problem.
If in the maximization in solving subproblems obtained optimal integer solution, then remembered those which correspond to the increasing value of the objective function. If the received "continuous" solution subtasks is no better stored integer solutions, such subtask is excluded from the list of tasks. The name of this method due to the fact that in the process of solving the problem of succession "branches", breaking into simpler subtasks.
Pruning methods are numerical methods for solving discrete optimization problems (discrete programming methods). They are designed to solve problems of integer linear programming (LP).
The idea of clipping methods is as follows. Originally decided ordinary (" continuous ") LP problem derived from the original problem by dropping the integrality requirements. If the resulting solution is an integer, it is also a solution of the original problem. If not, then to the restrictions of the original problem adds a new linear constraint, which has two properties:
- the resulting non-integer solution does not satisfy it ;
- all integer points of the feasible set of the original problem satisfy it.
- This restriction is called proper pruning.
Then solved extended continuous LP problem, ie continuous task with the added constraint. If the resulting solution is not an integer, added new correct pruning, etc. The process is repeated until a decision until the next extended continuous LP problem would not integer. Thus, the solution of the integer LP problem is reduced to solving a sequence of conventional LP problems.
Geometrically adding each such linear constraint means holding hyperplane cutoff on the polyhedron of feasible solutions regular continuous LP problem with nonintegral optimal point coordinates, but not affecting any of the lattice points of the polyhedron. Therefore, methods based on this idea, called the method of truncation.
Linear Programming
Linear programming is a mathematical discipline devoted to the theory and methods for solving extremal problems on sets of n- dimensional vector space defined by systems of linear equations and inequalities.
Linear programming is a special case of convex programming, which in turn is a special case of mathematical programming. At the same time it is - the basis of several methods of solving integer and nonlinear programming. One of the generalizations of linear programming is a fractional - linear programming.
Many of the properties of linear programming problems can also be interpreted as properties of polyhedra and thus geometrically to formulate and prove them.
The mathematical linear programming problems include studies of specific industrial and economic situations in which one form or another are interpreted as the problem of the optimal use of limited resources.
Range of problems that can be solved using linear programming methods is wide enough. This, for example :
problem of optimal use of resources in production planning ;
problem of mixtures (planning of production);
problem of finding the optimal combination of various kinds of products for storage in warehouses (control inventory or " knapsack problem ");
transportation problems (analysis of plant location, the movement of goods).
Linear programming is the most developed and widely used mathematical programming section (other than here include: integer, dynamic, nonlinear, parametric programming). This is explained as follows :
Mathematical models of a large number of economic problems are linear in the unknown variables;
This type of task is currently the most studied. For him special methods by which these problems are solved, and related programs.
many linear programming problem being solved, are widely used ;
some of the tasks in the original formulation are not linear, after a series of additional restrictions and assumptions may be linear or can be reduced to such a form that they can be solved by linear programming.
Economic and mathematical model of any linear programming problem includes an objective function, which optimum value (maximum or minimum) is required to find ; restrictions in the form of a system of linear equations or inequalities ; requirement of non-negativity of variables.
In general, the model is written as follows:
Objective function:
= c1x1 + c2x2 + + cnxn → max(min);
Constraints:
xj ≥ 0,
Where aij, bi, cj ( ) are constants.
The following are examples of some typical problems solved by using linear programming methods. Such problems have real economic content.
1. Problem of the optimal use of resources in production planning.
The general sense of problems in this class is as follows.
The company produces a variety of products n. For their production requires different types of resources m (raw materials, time and the like). Resources are limited, their reserves in the planning period are, respectively, b1, b2,, bm conventional units.
There are also technological coefficients aij, which show how many units of the i-th resource required to produce one unit of product j- th species ().
Profits derived by an enterprise in the implementation of product j- th species, is cj.
In the planning period values of aij, bi and cj remain constant.
Requires such a plan output, the implementation of which is profit -procurement would be greatest.
Here is a simple example of a problem in this class.
The company specializes in the production of hockey sticks and chess sets. Each putter brings the company a profit of $ 2, and each chess set - $ 4. Make one putter requires four hours of work on the site A and two hours of work at the site B. chess set is made to the cost of six hours in the area A, six hours at the site B and one hour on the site C. Accessible capacity section A is 120 hours per day, size B - 72 hours and the section C - 10 hours.
How many clubs and chess sets should produce company every day to get the maximum profit?
Under this condition we formulate a linear programming problem.
Denote: x1 - the amount produced daily hockey sticks, x2 - the amount produced daily chess sets.
We emphasize that each inequality in the system functional limitations in this case corresponds to a particular production site, namely: first - section A, the second - in the area, and the third - section C.
2. Problem of mixtures (planning of production).
The group tasks on mixtures tasks include finding the cheapest set of certain raw materials, ensuring production of a mixture with the desired properties. In other words, the obtained mixture should be composed of m different components in the specified amounts, as the components themselves are integral parts of n starting materials.
On the chicken farm used two types of feed - I and II. In unit mass of feed material I found the unit A, unit B and unit substance substance C. unit mass of feed II contains four units of material A, two units in substance and does not contain a substance C. In each bird daily diet should include not less than one substance A minimum of four units of matter in not less than one substance S. Price per unit mass of feed is $ 3 I feed II - $ 2.
Make a daily diet of poultry feeding so as to provide the cheapest diet.
Let us formulate a linear programming problem.
Denote: x1 - the amount of feed in the daily ration I birds, x2 - the amount of feed in the daily ration II birds.
3. Transport problem.
Under the transportation problem understand a number of problems with certain specific structure. The most simple transport tasks are tasks for the transport of a certain product from origin to destinations at minimal cost for transportation.
Three suppliers of the same product in a planned period following its reserves : first - 120 conventional units, the second - 100 conventional units, the third - 80 conventional units. This product must be transported to the three users, which needs are 90, 90 and 120 arbitrary units, respectively.
Typically, the initial conditions of the transportation problem is recorded in the so-called transport table (see table). Table cells in the upper left corner of the record of costs (shipping costs per unit product between corresponding points) below the diagonal of each cell is placed value delivery xij (ie xij - the number of units of cargo that will be transported from the i-th j- provider mu consumer).
Necessary to determine the cheapest option transport, each provider must send the goods as much as he has in store, and every consumer should get the right amount of his products.
We formulate the LPP:
Geometric solution of LPP
If the system of constraints linear programming problem is presented in the form of a system of linear inequalities in two variables, then this problem can be solved geometrically. Thus, this method of solving LPP has a very narrow scope of application.
However, the method is of great interest in terms of developing visual representations of the essence of linear programming problems.
Geometric (or graphical) method requires consistent implementation of a number of steps. Below is a procedure for solving the linear programming based on its geometric interpretation.
1. Formulate LPP.
2. Construct the plane { x1, x2 } lines whose equations are obtained by replacing the constraint inequalities signs on signs equality.
3. Find the half-plane defined by each of the constraints of the problem.
4. Find the area of feasible solutions.
5. Built right c1x1 + c2x2 = h, where h - any positive number is desirable to hold direct pass through the polygon solutions.
6. Move found a direct parallel to itself in the direction of increasing (when searching for the maximum) or decrease (when searching for a minimum) of the objective function. As a result, will be found, or the point at which the objective function takes the maximum (minimum) value, or will be installed unbounded function on the set of solutions.
7. Determine the coordinates of the point of maximum (minimum) of the function to calculate the value of the function at this point.
Next, consider the example of solving LPP by graphical methods. For this we use the above problem of hockey sticks and chess sets.
- It was already been cited formulation of the problem, here, we can only repeat it :
2.Now we construct the straight lines corresponding to each of the functional limitations of the problem (see figure). These lines are indicated in figure (1), (2) and (3).
3. Dashes indicate direct on the half-plane defined by the constraints of the problem.
4. Area admissible solutions includes point, for which all the constraints of the problem. In our case, the region is a pentagon (Figure designated ABCDO and painted blue).
5. Direct corresponding objective function, the figure shown by the dotted line.
6. Direct we move parallel to itself upward (direction indicated by the arrow), as it is when moving in this direction of the objective function increases. The last point of the polygon solutions which touches Moves the line before leaving it, is the point C. This is the point corresponding to the optimal solution.
7. Remains to calculate the coordinates of the point C. It is a point of intersection of the lines (1) and (2). Deciding together the equations of these lines, we find,. Substituting these values into the objective function, we find that its value at the optimal point .
Thus, to maximize the company's profits should produce daily 24 clubs and 4 sets. Implementation of this plan will provide a daily profit of $ 64.
Sources
L.V. Kantorovich: A new method of solving some classes of extremal problems, Doklady Akad Sci USSR, 28, 1940, 211-214.
G.B Dantzig: Maximization of a linear function of variables subject to linear inequalities, 1947. Published pp. 339–347 in T.C. Koopmans (ed.):Activity Analysis of Production and Allocation, New York-London 1951 (Wiley & Chapman-Hall)
J. E. Beasley, editor. Advances in Linear and Integer Programming. Oxford Science, 1996. (Collection of surveys)
