[20 points] Mr. Optimal wants to find the values of x ∈ [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. 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 ≥ 0 ; y ≥ 0 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 Tableu form of Simplex method. 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? 1 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. (b) [20 points] Suppose a company asked to buy your newspapers, instead. What should be the minimum price this?
Minimizing Trigonometric Functions Using Generalized Pattern Search
- [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, pk)
If F (xk) > F (xk + λk) then Xx+1 = Xk + λk otherwise Xx+1 = Xk
Update (λk, pk)
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
- [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.
- [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.
Identifying Linear Programming Problems
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
|
|
|
Cj
|
1000
|
800
|
700
|
0
|
0
|
|
CB
|
B
|
b
|
a1
|
a2
|
a3
|
a4
|
a5
|
|
0
|
a4
|
1000
|
100
|
300
|
200
|
1
|
0
|
|
0
|
a5
|
800
|
100
|
500
|
100
|
0
|
1
|
|
|
|
|
-1000
|
-800
|
-700
|
0
|
0
|
|
0
|
a4
|
200
|
0
|
-200
|
100
|
1
|
-1
|
|
100
|
a1
|
8
|
1
|
5
|
1
|
0
|
1/100
|
|
|
|
|
0
|
4200
|
300
|
0
|
10
|
The solution is optimal since zj-cj >= 0 for all j. Conversely, the optimal solution is unique because for all non-basic vectors zj-cj for all the basis vectors. In that case, the below is the required solution.
X = 8
y = 0
z = 0
and hence wmax = 1000*8+800*0+700*0
wmax = 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
- [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.
- [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
Maximizing Revenue for a Training Consulting Company with Constraints on Resources
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.
