2022代写研究计划书指导数学essay
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.
Problems where the Simplex Method will not give all Integer Solutions
Example
The problem
has a feasible region with the vertices (given to 2 decimal places):-
the “Integer” feasible region has the vertices
at
A B
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#
Generating constraints
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.
