|
Integer Programming 指导essay A general Integer Programming problem will take the form:- where c is the cost vector, A the coefficient matrix, and b the resource restriction and the variables x are constrained to have an all integer form. Solution of a Linear Programming Problem The problem where x is not constrained to have integer values is (normally) solved using the Simplex Algorithm. This Algorithm determines the Optimal Solution by searching through the vertices of the boundary of the feasible region (it can be shown that the Optimal Solution will be located at one of these points). However in an Integer Programming problem the boundary of the feasible region is not known and hence the solution technique has to find this boundary before it can search for the Optimal Solution. Defining the LP feasible region Defining the Integer feasible region Therefore, in general, Integer Programming problems are harder and more time consuming than their Linear Programming equivalents. Although on occasion an application of the standard Simplex Method will produce an all integer solution. Problems where the Simplex Method will give an all Integer Solution The solution to the set of simultaneous equations
is given by
now if AR, and b are integer valued then x can be guaranteed to have an all integer form if . Example If and Then AR can have four forms
and
thus the Simplex Method will produce all Integer Solutions for this problem.
Example The problem
has a feasible region with the vertices (given to 2 decimal places):-
the “Integer” feasible region has the vertices at
C
Determination of All Integer Solutions The following examples are used to illustrate two approaches to the determination of the optimal all integer solution to the Linear Programming problem Branch and Bound This method determines the optimal solution by solving a set of Linear Programming problems until it generates the optimal integer solution. For example the LP solution for Base Problem (P) is given by now were x to have an integer value then from this solution it would seem as if either x would be less than or equal to 2 or greater than or equal to 3. Therefore look at the two possible problems
with the solutions
continuing until the optimal integer solution has been determined, this can be a long process!. #p#分页标题#e#
This uses a single Linear Programming problem but at each iteration can add an extra constraint to preserve the integer nature of the current solution vertex. Given the problem
then assuming that the Simplex pivot element would be the x coefficient 2 then divide through by two to give and truncate the coefficients to give and the augmented problem
指导essay which does give the optimal integer solution note that: both these methods can be (very) lengthy.
|
 |
|||
| 网站地图 |
