Scribd
Upload
43 views

Integer Linear Programming

Integer programming involves optimizing a linear function subject to linear constraints, but with the added restriction that some or all variables must take integer values. It describes problems that can be modeled as linear programs with additional integrality constraints. The graphical method for integer programming involves plotting the feasible region and constraints on a graph to find optimal integer solutions for the objective function.

Uploaded by

arjhay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
43 views

Integer Linear Programming

Integer programming involves optimizing a linear function subject to linear constraints, but with the added restriction that some or all variables must take integer values. It describes problems that can be modeled as linear programs with additional integrality constraints. The graphical method for integer programming involves plotting the feasible region and constraints on a graph to find optimal integer solutions for the objective function.

Uploaded by

arjhay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 13

Integer Linear

Programming:
Graphical Method
WHAT
IS
INTEGER
PROGRAMMING?
INTEGER PROGRAMMING:

• It is the domain of mathematical optimization


in which some or all of the problem variables
are restricted to be integers.
• It expresses the optimization of a linear
function subject to a set of linear constraints
over integer variables.
• Integer programs are substantially smaller in
size than linear programs that can be solved to
prove optimality in a reasonable amount of
time.
New Constraints in ILP:

• Xi Integer means Xi ∈ {….-3,-2,-1,0,1,2,3,….}


• Xi Binary means Xi ∈ {0,1} {0≤Xi≤1 and integer}

Non-negative Integer Value:

• Xi≥0 and integer means Xi ∈ {0,1,2,3,4,..}


Max Z =6X+7Y
st 4X + 5Y ≤ 20
10X + 7Y ≤ 35
3X + 4Y ≥ 6
X, Y ≥ 0
Y
4X + 5Y ≤ 20 Optimal
5
Objective
function
4 Optimal value
Solution Z = 6(1.59) +
3 A (1.59, 2.73) 7(2.73)
Z = 28.65
3X + 4Y ≥ 6 2 Feasible
Area
1
10X + 7Y ≤ 35

X
1 2 3 4 5
Max Z = 6X + 7Y
st 4X + 5Y ≤ 20
10X + 7Y ≤ 35
3X + 4Y ≥ 6
X, Y ≥ 0 and Integer
Y
4X + 5Y ≤ 20
X=Laptops
5
Y = Desktops
4
Feasible
All integer
All Integer
Solution
3 DOTS

3X + 4Y ≥ 6 2

1
10X + 7Y ≤ 35

X
1 2 3 4 5
Max Z = 6X + 7Y
st 4X + 5Y ≤ 20
10X + 7Y ≤ 35
3X + 4Y ≥ 6
X, Y ≥ 0 and Integer
Y
5 Optimal
Solution
4 (0,4)
Z = 6(0) + 7(4)
3
Z = 28
2

X
1 2 3 4 5
Max Z = 6X + 7Y
st 4X + 5Y ≤ 20
10X + 7Y ≤ 35
3X + 4Y ≥ 6
X, Y ≥ 0 and X Integer
Y
5
Optimal
4 Solution
(1,3.6)
(1, 3.2)
Z = 6(1) + 7(3.2)
3
Z = 28.4
2

X
1 2 3 4 5
Max Z = 6X + 7Y
st 4X + 5Y ≤ 20
10X + 7Y ≤ 35
3X + 4Y ≥ 6
X, Y ≥ 0 and Y Integer
Y
5
Optimal
4 Solution
(1.4,3)3)
(1.25, Z = 6(1.25) + 7(3)
3
Z = 28.5
2

X
1 2 3 4 5
Graphical Method: Minimization

Min Z = 5X + 7Y
s.t. X + 3Y ≥ 6
5X + 2Y ≥ 10
Y ≥4
X,Y ≥ 0

4
Y ≥4
FEASIBLE
5X

3
REGION
+
2Y
≥1

2
0

X+3
1
Y ≥6

0
0.5 1 1. 5 2 2. 5 3 3. 5 4 4. 5 5 5. 5
6

A
4
Y ≥4
FEASIBLE
3
REGION
5
X
+
2
Y

2
≥
1
0

B X+3
1
Y ≥6
OPTIMAL
SOLUTION
C
0(1.38, 1.54)
0. 5 1 1.5 2 2. 5 3 3. 5 4 4. 5 5 5. 5

Minimize X Y
5X + 7Y = ?0 5
5X + 7Y = 35
7 0
Equation
X + 3Y ≥ 6 C1
Coordinates POINT B
5X + 2Y ≥ 10 C2 (1.38,1.54)
X = 6 – 3Y
5(6-3Y) + 2Y =10 Z = 5X + 7Y
30-15Y + 2Y =10 Z = 5(1.38) + 7(1.54)
-13Y = -20
Y = 1.54 = 17.7
Minimum Z
X = 6 – 3(1.54) 17.7
X = 1.38
Comment?
Comment?
Suggestion?
Suggestion?
Clarification?
Clarification?
THANK YOU💗
Angelene Arcena
Sophia Marie Beloy
Jerome Dayaon
Zarcylou Geralde
Mickhaella Rosana
Janell Marie Sales
Frank Anthony Utom
Ganella Mae Valencia

You might also like