Exam (elaborations)
Optimisation Techniques
- Course
- Institution
Exam of 41 pages for the course Optimisation Techniques at University of Greenwich (CW)
[Show more]
Seller
Follow
tskl
Content preview
QUESTION 1Consider the integer linear programming problem,
max 𝑥 + 2𝑦
s.t. 𝑥 + 𝑦 ≤ 10
2𝑥 + 5𝑦 ≤ 25 + 𝑧
𝑥, 𝑦 ≥ 0 𝑎𝑛𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟
Here z = 0 if the last digit of your registration number is odd; otherwise, z = 5
(a) Relax the integrality constraint. Assume that it is known that in the optimal solution of the
obtained LP problem both main constraints hold as equalities. Derive the final simplex tableau using
the transformation matrix technique. Is the obtained optimal solution feasible for the original
integer programming problem?
Since my last digit of the registration number is odd, then z=0.
So,
max 𝑥 + 2𝑦
s.t. 𝑥 + 𝑦 ≤ 10
2𝑥 + 5𝑦 ≤ 25
𝑥, 𝑦 ≥ 0 𝑎𝑛𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟
LP Relaxation
max 𝑥 + 2𝑦
s.t. 𝑥 + 𝑦 ≤ 10
2𝑥 + 5𝑦 ≤ 25
𝑥 ≤1
𝑦 ≤1
𝑥, 𝑦 ≥ 0
Thus,
1 1
[ ]
2 5
Finding the inverse,
1 1 1
A= [ ] = 𝑎𝑑𝑗(𝐴)
2 5 det(𝐴)
1 5 −1
= [ ]
(5×1)−(2×1) −2 1
, 1 5 −1
= [ ]
(5)−(2) −2 1
1 5 −1
= [ ]
3 −2 1
Therefore, the inverse matrix is the following,
5 −1
[3 3]
−2 1
3 3
Order of rows: 𝒙, 𝒚
Af = Tf x A0 =
5 −1 5 −1
[3 3 ] [1 1 1 0
] = [
1 0 3 3]
−2 1 2 5 0 1 0 1 −2 1
3 3 3 3
RHSf = Tf x RHS0 =
25
5 −1
3
10
[3 3 ][ ] =
−2 1 25
5
3 3 [3]
,𝑧 − 𝑟𝑜𝑤:
5 −1
1 0 3 3 1 1
[1 2] [ −2 1 ] = [1 2 ]
0 1 3 3
3 3
𝑍 − 𝑟𝑜𝑤 𝑓𝑖𝑛𝑎𝑙 𝑣𝑎𝑙𝑢𝑒:
𝟐𝟓
𝟑 𝟑𝟓
[𝟏 𝟐] =
𝟓 𝟑
[𝟑]
𝒄 − 𝒛:
1 1 1 1
[1 2 0 0] − [1 2 ] = [0 0 − − ]
3 3 3 3
The obtained optimal solution is NOT feasible for the original integer programming problem.
Since this is the integer linear programming problem, the RHS shows a fraction for the final
25 5
tableau, 𝑥 = 3 𝑎𝑛𝑑 𝑦 = 3 and not an integer, therefore it is not feasible for this ILP.
Hence the final simplex tableau using the transformation matrix technique is given by,
Basis x y s1 s2 RHS
CB 1 2 0 0
x 1 1 0 5/3 - 1/3 25/3
y 2 0 1 - 2/3 1/3 5/3
zj 1 2 1/3 1/3 35/3
cj-zj 0 0 - 1/3 - 1/3
, (b) Starting with the tableau found in (a), apply the Gomory fractional algorithm to obtain
two different optimal integer solution. Clearly explain how the cut equations are derived.
The “Gomory Cut” is a computationally efficient method for deriving an optimal solution to an ILP
by adding (a) constraint(s) to enforce integrality. It ONLY works with ILPs – i.e. all coefficients, RHS
elements and decision variables must be integers.
Let the integer part the “floor” function of the number, formally defined as the largest whole
number no larger than the variable and denote it like this:
𝑓𝑙𝑜𝑜𝑟 (𝑥) = |𝑥|
The fractional part of the variable = 𝑥 − |𝑥| , 𝑑𝑒𝑛𝑜𝑡𝑒𝑑 {𝑥}, {𝑥} ≥ 0
The final simplex tableau from part (a) is the following,
Basis x y s1 s2 RHS
CB 1 2 0 0
x 1 1 0 5/3 - 1/3 25/3
y 2 0 1 - 2/3 1/3 5/3
zj 1 2 1/3 1/3 35/3
cj-zj 0 0 - 1/3 - 1/3
Cut 𝑥 since it has a larger fraction part.
G-row derived from the 𝑥 row;
𝟓 𝟏
𝟏 𝟎 −
𝟑 𝟑
𝟓 𝟏 𝟐𝟓
𝒙 + 𝒔𝟏 − 𝒔𝟐 =
𝟑 𝟑 𝟑
Find the fractional parts,
So Constraint becomes:
𝟐 𝟐 𝟏
𝒙 + (1 + )𝒔𝟏 + (−𝟏 + ) 𝒔𝟐 = 𝟖 +
𝟑 𝟑 𝟑
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller tskl. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $20.81. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78252 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now