Transcript M7L3

Integer Programming
Examples
1
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Objectives

To illustrate Gomory Cutting Plane Method for
solving
2

All Integer linear Programming (AILP)

Mixed Integer Linear Programming (MILP)
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (AILP)
Z  3x1  x 2
Consider the problem Maximize
subject to
2 x1  x 2  6
3x1  9 x 2  45
x1 , x 2  0
x1, x2 are integers
Standard form of the problem can be written as
Maximize
Z  3x1  x2
subject to
2 x1  x2  y1  6
3 x1  9 x2  y2  45
x1 , x2 , y1, y2  0
x1, x2, y1 and y2 are integers
3
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (AILP) …contd.
Solve the problem as an ordinary LP (neglecting integer requirements)
The final tableau of LP problem is shown below
Optimum value of Z is 123 and the values of basic variables are
33
x1 
45 ;
7
7
4
24 7 3
x2 
3
7
7
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (AILP) …contd.
Since the values of basic variables are not integers, generate Gomory
constraint for x1 which has a high fractional value. For this, write the
equation for x1 from the table above
x1  33  6 y1  1 y2
7 14
21
Here, b1  33 7 , bi  4,  i  5 7 ,
c11  6
, c11  0, 11  6
,
14
14
c12  1 , c12  0 and 12  1
21
21
Thus, Gomory constraint can be written as
s1  11 y1  12 y 2   1
5
i.e., s1  6
14
y1  1
21
y2   1
D Nagesh Kumar, IISc
21
Optimization Methods: M7L3
Example Problem (AILP) …contd.
Insert this constraint as a new row in the previous table
Solve this using Dual Simplex method
6
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (AILP) …contd.
47
and the values of basic variables are
3
11
x2  ; and y1   7
3
3
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Optimum value of Z is
7
x1  4;
Example Problem (AILP) …contd.
Since the values of basic variable x2 from this table is not an integer,
generate Gomory constraint for x2. For this, write the equation for x2 from
the table above
x2  11  1 y 2  1 s1
3
9
3
Thus, Gomory constraint can be written as
s2  1 y2  1 s1   2
9
3
3
Insert this constraint as a new row in the last table and solve using dual
simplex method
8
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (AILP) …contd.
Optimum value of Z is 15 and the values of basic variables are
x1 = 4, x2 = 3, y1 = 1, s2 = 6 and y2 = s1 = 0.
These are satisfying the constraints and hence the desired solution.
9
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (MILP)
Consider the previous problem with integer constraint only on x2
Maximize
Z  3x1  x 2
subject to
2 x1  x 2  6
3x1  9 x 2  45
x1 , x 2  0 ; x2 is an integer
Standard form of the problem can be written as
Maximize
Z  3x1  x2
subject to
2 x1  x2  y1  6
3 x1  9 x2  y2  45
x1 , x2 , y1 , y2  0 ; x2 should be an integer
10
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (MILP) …contd.
Solve the problem as an ordinary LP (neglecting integer requirements)
The final tableau of LP problem is shown below
Optimum value of Z is 123 and the values of basic variables are
33
x1 
45 ;
7
7
11
247
x2 
 33
7
7
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (MILP) …contd.
Since the value of x2 is not an integer, generate Gomory constraint for x2. For
this, write the equation for x2 from the table above
x2  24  1 y 2  2 y1
7
7
21
Here,
b2  24 , c21  1 , c22   2
7
7
21
Thus, the value of b2  3 and  2  3 7




Since, c21  c21
and c22  c22  c22,
 c21


c21
 0, c21
  1 since c21 is negative
7


c22
 2 , c22
 0 since c22 is positive
21
12
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (MILP) …contd.
Thus, Gomory constraint can be written as
m
si  
j 1
cij y j
i.e., s2  2

21
i
i
m
cij y j    i

1
y2  3
j 1
28
y1   3
7
Insert this constraint as a new row to the previous table and solve it using
Dual Simplex method
13
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Example Problem (MILP) …contd.
33 and the values of basic variables are
2
x1  4.5; x2  3; y2  4.5 and that of non-basic variables are zero.
This solution is satisfying all the constraints an hence the desired.
Optimum value of Z is
14
D Nagesh Kumar, IISc
Optimization Methods: M7L3
Thank You
15
D Nagesh Kumar, IISc
Optimization Methods: M7L3