L5 - Integer Solutions

Question 1

Why do we need integer solutions in linear Programming?

Answer 1

• Several real-life applications concern the production of goods that cannot be sold in parts e.g. the number of cars and computers
• We need to account for the fact that the choice variables are integers in MATLAB

Question 2

What is the geometric intuition behind an integer solution?

Answer 2

• imagine the graph now has a square on it
  
  • the feasible region now becomes dots at the integer points e.g. (4,5)
• Using IntLinProg(c,A,b) –> This may give now a different solution to what you would normally get with a non-integer

Question 3

How do profits and costs differ under a integer linear program?

Answer 3

• Profit is lower under an integer solution –> unless it is the same optimal solution as the normal linear program
• Costs are higher under an integer solution –> as you arent fully minimising your costs as you would under a non-integer linear program

Question 4

What is the opposite to a integer program?

Answer 4

• Relax program –> same linear program without the integer constraints

Question 5

Can you use the simplex method with integer solutions?

Answer 5

• The simplex method does not apply anymore to the integer program
  
  • now have to use alternative solution algorithms
  • the most well know is branch and bound

There is also no sensitivity, no dual and no shadow price for integers

Question 6

What is the reduced cost function in the LinProg function?

Answer 6

—Consider that we have n possible products to be produced. In the optimal solution, only some of the corresponding x_i are basic, meaning that some of the products are not inserted in the optimal plan.

—Let x_j be one of the variables which is not in the optimal plan. –> (producing everything else but this variable)

—The managerial question is: what is the value of the corresponding marginal profit that makes it convenient to produce x_j?

—The answer is the “reduced cost”.

—The reduced cost is the least increase in the unit profit of x_j that makes it enter the optimal plan –> how much more profit does it need to generate to become desirable again

• If the reduced costs are different from zero, but the optimal plan contains the variable it means we are being forced my constraints to include it –> profit we reduce by the value equal to the reduced costs