指导数学essay-Integer Programming- Algorithm determines the Opti

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.