ENGG7302 Computer Programmer

1. [20 points] Mr. Optimal wants to find the values of x 2 [0; 2_] that minimize the functions f(x) = sin(x), g(x) = 5 sin(x), and h(x) = sin (5x) using Generalized Pattern

Search. Please sort the functions (i.e., f, g, and h) based on the difficulty of finding the desired value using Generalized Pattern Search, and as usual, please explain your answer.

Solution

For the functions f(x) = sinx. g (x) = 5sinx and h(x) = sin (5x)

The method to be used will be General pattern search where K = 0, 1…

The first thing is to check for convergence

The second step is to compute f(x)

The third step is to determine a step λ_k using explanatory moves (λ_k, p_k)

If F (x_k) > F (x_k + λ_k) then X_x+1 = X_k + λ_k otherwise X_x+1 = X_k

Update (λ_k, p_k)

For F (x) = sin x

For the convergence f’ (x) = cos x     f^’ (x) = 0

                                                      Or cos x = 0

                                            Therefore for values of x = (2k+1) π/2

For g (x) = 5 sin x  

For h (x) = sin 5x

For the convergence b^’ (x) = 5 cos5x        h^’ (x) = 0

Therefore   cos (5x) = cos (2k+1) π/2

X = (2k+1) π/10

In the close integral [0, 2] the function will minimize its value as illustrated below,

For k = 0    x = π/10

For k = 1      x = 3π/10

For k = 2    x = π/2

Except the above three values, the function cannot minimize its values

2. [10 points] Is the following problem LP? Max x _ cos (a) + y. cos (b) for a particular a, b £ [0; 2_] subject to

 2x + 5y <= 10 x

x>= 0; y >= 0

No, the above is not linear programming problem. This is because only the linear functions can be solved by linear programming method.

3. [20 points] Congratulations, you’ve been appointed to be the new Finance Director of

UQ Humongous Data Training Consulting (UQ-HDTC)! You have three lines of training modules: Company Training (CT), On-line Training (OT), and Academic Training (AT). For each sold CT, UQ-HDTC will receive $1,000 in revenue, while for each sold OT, UQ-HDTC will receive $800 and for each AT, it will receive $700. Each module lasts for one month. To deliver the module CT, UQ-HDTC requires 100 hours of data scientist and computer programmer time. The module OT requires 300 hours of data scientist and 500 hours of computer programmer time, while AT requires 200 hours of data scientist and 100 hours of computer programmer time. Suppose UQ-HDTC has purchased 1,000 hours of data scientists’ time and 800 hours worth of computer programmer time for each month. How many CT, OT, and AT modules you should sell per month, so as to maximize UQ-HDTC revenue, given the constraints on data scientist and computer programmer time? Please form the problem as an LP problem and solve it using Tableau form of Simplex method.

Solution 

The first step is to let: (x CT, y OT and z AT) modules be sold per month where W is the total revenue for each month

The LP problem will therefore become,

Maximize w = 1000x+800y+700z

Subject to 100x+300y+200z<=

100x+500y+100z<=800

Xyzuv<=0

The below is our simplex tableau

The solution is optimal since z_j-c_j >= 0 for all j. Conversely, the optimal solution is unique because for all non-basic vectors z_j-c_j for all the basis vectors. In that case, the below is the required solution.

X = 8

y = 0

z = 0

and hence w_max = 1000*8+800*0+700*0

w_max = 8000

In that case, 8 CT modules has to be sold in each month so as to maximize the total revenue per month and thus the maximum revenue is $ 8000 

4. [20 points] You have 5 $2 coins, 6 $1 coins, 8 $0.5, and no other money. You have to pay a given amount C, where no change is given. Of course, you want to minimize overpay.

Please formulate this problem as a constrained optimization problem. Is this problem linear?

Solution

The total 2 dollar coins = 5

The total 1 dollar coins = 6

The total 0.5 dollar coins = 8

We therefore need to amount = C

The problem constraints becomes

X1 <= 5

X2 <= 6

X3 <= 8

X1+x2+x3 >= C

As an illustration;

X1 = no of coins of 2 dollars

X2 = no of coins of 1 dollars

X3 = no of coins of 0.5 dollars

Therefore, the function to be minimized is z = x1+x2+x3

The non-negative variables are:

X1> 0, x2 >=0, x3> = 0

This shows to be linear relationship and hence it is linear.

5. [30 points] A paper recycling machine can produce toilet paper, writing pads, and paper towels, which sell for 18, 29 and 25 cents and consume 0.5, 0.22 and 0.75 kilograms of newspaper and 0.2, 0.4, and 0.22 minutes. Each day 10 hours and 1500 kilograms of newspaper are available, and at least 1000 rolls of toilet paper, 200 writing pads and 400 rolls of paper towels are required.

(a) [10 points] Please formulate an appropriate LP to maximize revenue and solve it using tableau form of simplex method.

Solution

Let:

X1 = number of toilet paper

X2 = number of writing pads

X3 = number of paper towels

Maximize, Z = 18x1+29x2+25x3

The constraints are as follows

0.5x1+0.22x2+0.75x3<= 1500   the new paper constraints

0.2x1+0.4x2+0.22x3<= 600      the time constraints

In that case, it will be

X1>= 1000

X2 >= 200

X3 >= 400

When we solve this by tableau method;

Tableau #1
x1 x2 x3 s1 s2 s3 s4 s5 z
0.5 0.22 0.75 1 0 0 0 0 0 1500
0.2 0.4 0.22 0 1 0 0 0 0 600   
1 0 0 0 0 -1 0 0 0 1000
0 1 0 0 0 0 -1 0 0 200   
0 0 1 0 0 0 0 -1 0 400   
-18 -29 -25 0 0 0 0 0 1 0   

Tableau #2
x1 x2 x3 s1 s2 s3 s4 s5 z
0 0.22 0.75 1 0 0.5 0 0 0 1000
0 0.4 0.22 0 1 0.2 0 0 0 400   
1 0 0 0 0 -1 0 0 0 1000
0 1 0 0 0 0 -1 0 0 200   
0 0 1 0 0 0 0 -1 0 400   
0 -29 -25 0 0 -18 0 0 1 18000  

Tableau #3
x1 x2 x3 s1 s2 s3 s4 s5 z
0 0 0.75 1 0 0.5 0.22 0 0 956   
0 0 0.22 0 1 0.2 0.4 0 0 320   
1 0 0 0 0 -1 0 0 0 1000
0 1 0 0 0 0 -1 0 0 200   
0 0 1 0 0 0 0 -1 0 400   
0 0 -25 0 0 -18 -29 0 1 23800  

Tableau #4
x1 x2 x3 s1 s2 s3 s4 s5 z
0 0 0 1 0 0.5 0.22 0.75 0 656   
0 0 0 0 1 0.2 0.4 0.22 0 232   
1 0 0 0 0 -1 0 0 0 1000
0 1 0 0 0 0 -1 0 0 200   
0 0 1 0 0 0 0 -1 0 400   
0 0 0 0 0 -18 -29 -25 1 33800  

Tableau #5
x1 x2 x3 s1 s2 s3 s4 s5 z
0 0 0 1 -0.55 0.39 0 0.629 0 528.4  
0 0 0 0 2.5 0.5 1 0.55 0 580   
1 0 0 0 0 -1 0 0 0 1000
0 1 0 0 2.5 0.5 0 0.55 0 780   
0 0 1 0 0 0 0 -1 0 400   
0 0 0 0 72.5 -3.5 0 -9.05 1 50620  

Tableau #6
x1 x2 x3 s1 s2 s3 s4 s5 z
0 0 0 1.58983 -0.874404 0.620032 0 1 0 840.064
0 0 0 -0.874404 2.98092 0.158983 1 0 0 117.965
1 0 0 0 0 -1 0 0 0 1000   
0 1 0 -0.874404 2.98092 0.158983 0 0 0 317.965
0 0 1 1.58983 -0.874404 0.620032 0 0 0 1240.06
0 0 0 14.3879 64.5866 2.11129 0 0 1 58222.6

The value of x1=1000, x2=318 and x3=1241

Optimal Solution: z = 1000(18) + 318(29) + 1241(25)

 = 58247 cents

(b) [20 points] suppose a company asked to buy your newspapers, instead. What should be the minimum price this?

Solution

The LP will be therefore to minimize Z=0.5x10.22x2+0.75x3

The minimum price will be = 58247 cents / 1500kg

= $ 0.3883 per Kilogram of newspapers 

References

Chua, L. and Lin, P., 2015. Computer-Aided Analysis of Electronic Circuits: Algorithms and Computational Techniques (Prentice-Hall series in electrical computer engineering).

Fletcher, C.A., 2014. Computational techniques for fluid dynamics 2: Specific techniques for different flow categories. Springer Science & Business Media.