---

CS323 - Linear and Integer Programming Homework

---

• Question 1 (25 pts)
  • Solve the following linear program with the Simplex method

    Show every Simplex Tableau (just the answer will get you only 5 pts --- you can easily get the answer by running a program like lp_solve)

    max: 3x1 + 4x2 s.t.: x1 + 2x2 ≤ 8 3x1 + 2x2 ≤ 12

  ---

  ---

• Question 2 (25 pts)
  • Solve the following linear program with the 2-phased Simplex method

    Show every Simplex Tableau (just the answer will get you only 5 pts --- you can easily get the answer by running a program like lp_solve)

    max: 4x1 + 5x2 s.t.: x1 + 2x2 ≤ 8 3x1 + 2x2 ≤ 12 x1 + x2 ≥ 5

  ---

  ---

• Solving linear programs using "lp_solve"
  • In the next 2 questions, you will use the lp_solve utility (available on the MathCS systems) to solve linear programs

  • Sample Linear program:

    Max: 4*x1 + 5*x2 + 3*x3; s.t: 5*x1 + 6*x2 + 4*x3 <= 30; 2*x1 + 3*x2 + 2*x3 <= 9; x1, x2 >= 0;

    This can be solved using the following input file:

    max: 4*x1 + 5*x2 + 3*x3; 5*x1 + 6*x2 + 4*x3 <= 30; 2*x1 + 3*x2 + 2*x3 <= 9;

    You can obtain a copy of the input file here: click here

    ---

  • To solve the LP using lp_solve, execute the following command:

    lp_solve inp1

  ---

  ---

• Question 3 (25 pts)
  • Solve the following Integer program using the Branch and Bound method:

    Max: 4*x1 + 5*x2 + 3*x3; s.t.: 5*x1 + 6*x2 + 4*x3 <= 30; 2*x1 + 3*x2 + 2*x3 <= 9; x1, x2, x3 integer !

    Show the following for each iteration: (like in the class notes)

    The set of LP that you still need to solve. Then, solve the first LP in the list (using lp_solve). Show the optimum objective value of the LP Show the solution (i.e., the value of the variables x1, x2, ...) And finally, the action taken by the Branch and Bound method

  ---

  ---

• Question 4 (25 pts)
  • Solve the following Integer program using the Branch and Bound method:

    Max: 100*x1 + 150*x2; s.t.: 8000*x1 + 4000*x2 <= 40000; 15*x1 + 30*x2 <= 200; x1, x2 integer !

    Show the following for each iteration: (like in the class notes)

    The set of LP that you still need to solve. Then, solve the first LP in the list (using lp_solve). Show the optimum objective value of the LP Show the solution (i.e., the value of the variables x1, x2, ...) And finally, the action taken by the Branch and Bound method