Homework 1: Linear Programming

Description

0. [2 points] Warm-up. Model the following problem in JuMP.

maximize	5x1 x2 + 15x3
x1;x2;x3	2x1 x2 + x3
subject to:
	0 xj 3; j 2 f1; 2; 3g

1. 1. Write Julia code to solve this problem using Clp, ECOS, and SCS solvers. Do all give the same result?

1. 2. Which solver is fastest (use the @time macro in front of the optimize!() statement to check)? Can you say why?

1. 3. Consider changing the rst constraint to 2x₁ x₂ + x₃ + , where is some real number. For all values of larger than a certain threshold value, the problem with become infeasible. (In Julia, the solver will terminate with status INFEASIBLE.) What is this threshold value of ? Can you explain by examining the constraints why this value makes the problem infeasible?

2. [2 points] Standard Form Recall that in class we de ned the \standard form” of a linear program to be

min c^T x subject to Ax b; x 0:

Consider the following linear program which is NOT in standard form:

min 3z1	+ 2z2	z3
subject to 2z1 z2	+ 3z3	= 10;
0 z2 5;		5 z3 20:

1. Transform the given LP into our standard form. How are the components of x related to the components of z = (z₁; z₂; z₃)? Write out explicity the quantities A, b, c.

2. Solve both versions of the LP using JuMP and show that you can recover the optimal z and objective value by solving your transformed version of the LP.

CS/ECE/ISyE 524 Introduction to Optimization Steve Wright, Spring 2021

3. [2 points] Polyhedron modeling. We saw that the set of x such that Ax b where A 2 R^{m n} and b 2 R^m describes a polyhedron. Find A and b such that Ax b describes the diamond-shaped polyhedron in three dimensions (that is, x 2 R³) that is de ned by the following six vertices:

(1; 1; 0); (1; 1; 0); ( 1; 1; 0); ( 1; 1; 0); (0; 0; 1); (0; 0; 1):

(It might help to sketch this gure!)

4. [3 points] Manufacturing transistors. Silicon Valley Corporation (Silvco) manufactures transis-tors. An important aspect of the manufacturing process is the melting of the element germanium in a furnace. Unfortunately, the melting process yields germanium of highly variable quality. The results of the process can be classi ed into ve grades: \grade A”, \grade B”, \grade C”, \grade D”, and \defective”. Two methods can be used for the melting. Method 1 costs $50 per transistor, and Method 2 costs $70 per transistor. The qualities of germanium produced by the melting are shown in the following table (as percentage yields).

	Method 1	Method 2
defective	30	20
grade D	30	20
grade C	20	25
grade B	15	20
grade A	5	15

Silvco can re re melted germanium in an attempt to improve its quality. It costs $25 to re re the melted germanium for one transistor. The results of the re ring process are shown in the table below. For example, if grade B germanium is re red, 50% of the resulting germanium will still be grade B and 50% will be grade A.

	defective	grade D	grade C	grade B	grade A
defective	30	25	15	20	10
grade D		30	30	20	20
grade C			40	30	30
grade B				50	50

Silvco has su cient furnace capacity to melt or re re germanium for at most 20,000 transistors per month. Silvco’s monthly demands are for 1000 grade A transistors, 2000 grade B transistors, 3000 grade C transistors, and 3000 grade D transistors.

Assuming that just one stage of re ring is allowed, model the melting/re ring process and determine the minimum cost of germanium processing required to meet the demands.

Hint: Remember to start by asking: What are the decision variables? Then work through how the decision variables relate to the data in the tables and the text. In particular, you will need to de ne how the objective (total cost) is related to the decision variables.

2 of 2