[SOLVED] ESE 5060 – Introduction to Optimization Final Exam Fall Semester 2023 C/C

ESE 5060 – Introduction to Optimization (Final Exam)

Fall Semester, 2023

Instructions:

You must answer any five (5) of the following six (6) problems. Do not answer more than five (5) problems. If you do, only the first 5 problems answered will be graded. Please indicate on the front of your exam booklet which problems you want graded and please be sure to cross out any problems in your exam booklet that you do not want graded.

Problem #1 (20 points) – The Branch and Bound Method Suppose that an optimal tableau for the LP Problem

max    z = 4x1  + 6x2  + 3x3       (Objective Function)

s.t.    3x1  + 2x2  + 5x3   ≤ 68        (Constraint #1)

4x1 + 6x2  + 3x3  ≤ 83        (Constraint #2)

3x1 + 4x2 + 2x3  ≤ 57       (Constraint #3)

x1 ,x2 ,x3  ≥ 0           (Sign Restrictions)

is

Row	BVs	Values	x1	x2	x3	s1	s2	s3
0	z	83	0	0	0	0	1	0
1	x1	5	[ 1]	0	0	0	−2	3
2	x2	13/2	0	[ 1]	0	−1/8	9/8	−11/8
3	x3	8	0	0	[ 1]	1/4	3/4	−5/4

Using the Branch and Bound Method, determine the solution to this LP if x2  is now restricted to be an integer. You must show your tableaus for full credit. Only a final answer without the tableaus yields very little or no credit. 

Problem #2 (20 points) – Constructing An IP Problem

Consider the following non–linear programming problem

max   z = 5x1 + 3x2  + 7x3        (Linear Objective Function)

s.t.     |x1 + 2x2 + 4x3 | ≥ 20   (Non-Linear Constraint #1)

2x1 + 3x2  + x3  ≤ 30     (Linear Constraint #2)

x1 ,x2 ,x3  ≥ 0                (Sign Restrictions)

that contains: one (1) linear objective function, one (1) non-linear constraint, one (1) linear constraint and three (3) sign restrictions.

a.)  (6 points) Construct a single IP problem that can be used to solve this non-linear

programming problem. Your single IP problem should contain: one (1) linear objective

function, four (4) linear constraints, five (5) variables, three (3) sign restrictions and two

(2) integer restrictions. Be sure to clearly state how any big M’s are computed and note

that when constructing your big M’s, you need only observe that from the linear constraint

2x1 + 3x2  + x3  ≤ 30

and the sign restrictions x1 ,x2 ,x3  ≥ 0, it’s enough to note that

0 ≤ x1  ≤ 15      ,     0  ≤ x2  ≤ 10     and     0 ≤ x3  ≤ 30. Of course, you need not solve the resulting IP problem.

b.)  (14 points) If we now want to require that at least one of the following three (3) additional constraints

|4x1 − x2  + x3 | ≤ 15,    |3x1  − 8x2  + 9x3 | ≥ 72    or    7x1  + 4x2  − 3x3   = 25

are also satisfied, construct a single IP problem that can be used to solve this. Your single IP problem should contain: one (1) linear objective function, nine (9) variables, eleven (11) linear constraints, three (3) sign restrictions and six (6) integer restrictions. Be sure to clearly state how any big M’s are computed. Of course, you need not solve the resulting IP problem. 

Problem #3 (20 points) – A Transportation Problem

Steelco manufactures three types of steel at different plants. The time required to manufacture 1 ton of steel (regardless of type) and the costs to manufacture 1 ton of steel at each plant are shown in the following table.

PlantSteel     One Ton of Steel 1     One Ton of Steel 2     One Ton of Steel 3     Time

Plant 1                     $60                          $40                         $28               20 min

Plant 2                     $50                          $30                         $30               16 min

Plant 3                     $43                          $20                         $20               15 min

Each week, 100 tons of each type of steel (1, 2, and 3) must be produced and each plant is open 40 hours per week.

a.)  (10 points) Formulate a balanced transportation problem to minimize the cost of meeting Steelco’s weekly requirements. Put both your answer in the form of the tableau as shown here.

b.)  (5 points) Use the shipping cost method to determine an initial basic feasible point and

the value of w for this problem. Note that if there is a tie in shipping costs when using the shipping cost method, you must break the tie by choosing the most northwest corner results between the ties.

c.)  (5 points) Suppose the time required to produce 1 ton of steel now depends on the type of steel as well as on the plant at which it is produced, as summarized in the next table.

PlantSteel     Steel 1 (Minutes)     Steel 2 (Minutes)     Steel 3 (Minutes)

Plant 1                   15                           12                          15

Plant 2                   15                           15                          20

Plant 3                   10                           10                          15

Could a transportation problem still be formulated? Explain.

Problem #4 (20 points) – Sensitivity Analysis During a sensitivity analysis on the LP

min   w = cTx   (Objective Function)

s.t.    Ax = b    (Constraints #1-#m)

x ≥ 0       (Sign Restrictions)

in which both b and c were changed, the optimal tableau is found to changed to the following tableau.

Row	BVs	Values	x1	x2	x3	x4	x5	x6
0	−w	100	0	0	0	5	−1	3
1	x1	8	[ 1]	0	0	2	−5	−2
2	x2	16	0	[ 1]	0	−4	3	1
3	x3	−4	0	0	[ 1]	−1	2	0

Continue solving the LP with this tableau to arrive at a new optimal solution. You must show your tableaus for full credit. Only a final answer without the tableaus yields very  little or no credit.

Problem #5 (20 points) – An Interesting Cone

Recall that if

are n × 1 columns, we say that x < y when either x = y or when x ≠ y and the first non-zero component of x − y is negative (reading from top to bottom).

a.)  (10 points) Prove that the set

where both x 1  and x2  are n × 1 columns, is a convex cone in R2n . You may use all

properties about lexicographic ordering that you already know from Exam #2 without proving them again here.

b.)  (10 points) Prove that convex cone S is not pointed for all n =  1,2,3, . . . .

Problem #6 (20 points) – Formulating A 0–1 Integer Programming Problem

To graduate from BasketWeavers (BW) University with a major in operations research (OR), a student must complete at least two math courses, at least two operations research (OR) courses, and at least two computer courses. There are a total of seven (7) courses available and some courses can be used to fulfill more than one requirement as summarized in the following table

Course Number and Name	Math Req.	OR Req.	Computer Req.
1.) Calculus	Yes	−	−
2.) Operations Research	Yes	Yes	−
3.) Data Structures	Yes	−	Yes
4.) Business Statistics	Yes	Yes	−
5.) Computer Simulation	−	Yes	Yes
6.) Computer Programming	−	−	Yes
7.) Forecasting	Yes	Yes	−

In addition, some courses are prerequisites for others as indicted in the next table.

This Course Is A Prerequisite For →                           This Course

1.) Calculus                                                      4.) Business Statistics

6.) Computer Programming                                5.) Computer Simulation

6.) Computer Programming                                3.) Data Structures

4.) Business Statistics                                        7.) Forecasting

Formulate a 0-1 IP problem that minimizes the number of courses needed to satisfy BW’s major requirements in operations research.