Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment #2

Problem 1

a)   Show that the number of nodes in a tree where we represent all possible combinations of m 0-1 binary variables is

2m+1 - 1

b)  If a complete enumeration of all the nodes in the tree were required, by what factor would

this enumeration increase with respect to the direct enumeration of all 0-1 combinations.

Problem 2

Given is the integer programming problem

max y1 + 1.2y2

s.t. y1 + y2  ≤ 1

0.8y1 + 1.1y2  ≤ 1

y1, y2 ∈ {0, 1}

a)  Plot the contours ofthe objective and the feasible region for the case when the binary variables are relaxed as continuous variables y1, y2  ∈ [0, 1].

b)  Determine from inspection the solution of the relaxed problem (i.e. finding the solution by inspecting each feasible solution in the plot).

c)  Enumerate the four 0-1 combinations in your plot (for all possible values of y1, y2) to find the optimal solution.

d)  Solve the above problem with the branch and bound method by enumerating the nodes in the tree and solving the LP subproblems with GAMS.

Problem 3

A company is considering to produce a chemical C which can be manufactured with either process II or process III, both of which use as raw material chemical B.  B can be purchased from another company or else manufactured with process I which uses A as a raw material.  Given the specifications below, formulate an MILP model and solve it with GAMS to determine:

a)    Which process to build (II and III are exclusive)?

b)    How to obtain chemical B?

c)    How much should be produced of product C?

The objective is to maximize profit.

Maximum supply of A:  16 tons/hr

NOTE:   You may want to scale your cost coefficients (e.g. divide them by  100). Please avoid using any nonlinear term in the model formulation, because the model should an MILP. Please make sure to add ‘option optcr = 0’ in your GAMS code. Please submit your source code file as well.