ENGG7302: Optimization Assignment - Simplex, LP & Pattern Search

This assignment solution covers various optimization problems, including sorting functions based on the difficulty of minimization using Generalized Pattern Search, determining if a problem is a Linear Program (LP), formulating and solving an LP problem using the Simplex method in tableau form to maximize revenue for UQ Humongous Data Training Consulting (UQ-HDTC), formulating a constrained optimization problem to minimize overpayment with a given set of coins, and formulating and solving an LP to maximize revenue for a paper recycling machine using the tableau form of the Simplex method. The solution provides detailed steps and explanations for each problem, including the formulation of constraints and objective functions, tableau iterations, and optimal solutions. It also explores the minimum price a company should pay to buy newspapers from the recycling machine.

MATH ASSIGNMENT 1
Math Assignment
Student’s Name
Institutional Affiliation
Date

MATH ASSIGNMENT 2
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, 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,

MATH ASSIGNMENT 3
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?

MATH ASSIGNMENT 4
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
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.

MATH ASSIGNMENT 5
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
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;

MATH ASSIGNMENT 6
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

MATH ASSIGNMENT 7
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

MATH ASSIGNMENT 8
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

MATH ASSIGNMENT 9
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).

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