MTRN4030 Week 7- Simplex, Constrained and Optimal Control Methods Solved

Summary
This laboratory exercise is scheduled for three weeks (week 6, 7, 8). The first part of each meeting is a tutorial that tutors will provide a revision on the topic and guidelines to complete the exercises.  

The exercises include the calculation and program-based implementation of constrained optimisation methods, Simplex method, Lagrangian, KKT, as well as the optimal control method. The implementation details of these methods will be investigated and their characteristics and/or limitations are to be identified and discussed. The second objective of the exercises is the development of Matlab codes to solve optimisation problems covered in this exercise. The last part is about the use of Matlab/Simulink to study the optimal control of a simple dynamic system.

An individual written report is required for this exercise, which carries 8%, in addition to the marks for the practical work that is 5%. Submission of the report is to be uploaded to Moodle. Details of the requirements are given in the Assessment section.

 

Simplex Method – Transportation Problem
The problem can be expressed by the formulation of a linear model, and it can be solved using the class of the simplex method. The problem deals with the transportation of some product from 𝑚𝑚 origins, 𝑂𝑂1, ⋯ , 𝑂𝑂𝑚𝑚, to 𝑛𝑛 destinations, 𝐷𝐷1, ⋯ , 𝐷𝐷𝑛𝑛, with the aim of minimizing the total distribution cost, where:

1.       The origin 𝑂𝑂𝑖𝑖 has a supply of 𝑎𝑎𝑖𝑖 units, 𝑖𝑖 = 1, ⋯ , 𝑚𝑚.

2.       The destination 𝐷𝐷𝑗𝑗 has a demand for 𝑏𝑏𝑗𝑗 units to be delivered, 𝑗𝑗 = 1, ⋯ , 𝑛𝑛.

3.       𝑐𝑐𝑖𝑖𝑗𝑗 is the cost per unit distributed from the origin 𝑂𝑂𝑖𝑖 to the destination 𝐷𝐷𝑗𝑗.

The above problem can be expressed as finding a set of 𝑥𝑥𝑖𝑖𝑗𝑗’s, to meet supply and demand requirements at a minimum distribution cost. The corresponding linear model is:

Minimise 𝑧𝑧 = ∑𝑚𝑚𝑖𝑖=1∑𝑛𝑛𝑗𝑗=1𝑐𝑐𝑖𝑖𝑗𝑗𝑥𝑥𝑖𝑖𝑗𝑗

Subject to ∑𝑛𝑛𝑗𝑗=1𝑥𝑥𝑖𝑖𝑗𝑗 ≤ 𝑎𝑎𝑖𝑖, ∑𝑚𝑚𝑖𝑖=1𝑥𝑥𝑖𝑖𝑗𝑗 ≤ 𝑏𝑏𝑗𝑗, 𝑥𝑥𝑖𝑖𝑗𝑗 ≥ 0

Thus, the problem is to determine 𝑥𝑥𝑖𝑖𝑗𝑗, the number of units to be transported from 𝑂𝑂𝑖𝑖 to 𝐷𝐷𝑗𝑗, so that supplies will be consumed and demands satisfied at an overall minimum cost.

The first 𝑚𝑚 constraints correspond to the supply limits, and they express that the supply of commodity units available at each origin must not be exceeded. The next 𝑛𝑛 constraints ensure that the commodity unit requirements at destinations will be satisfied. The decision variables are defined positive since they represent the number of commodity units transported.

Thus, a transportation problem is specified by the number of origins, the number of destinations, the supplies, the demands and the per-unit transportation costs. All this information can be abbreviated in the form of a rectangular array.

The relevant data for any transportation problem can be summarized in a matrix format using a tableau called the transportation costs tableau (see below). The tableau displays the origins with their supply, the destinations with their demand and the transportation per-unit costs.

 
𝐷𝐷1
𝐷𝐷2
⋯
𝐷𝐷𝑛𝑛
supply
𝑂𝑂1
𝑐𝑐11
𝑐𝑐12
 
 
𝑎𝑎1
⋮
 
 
⋱
 
⋮
𝑂𝑂𝑚𝑚
 
 
 
𝑐𝑐𝑚𝑚𝑛𝑛
𝑎𝑎𝑚𝑚
demand
𝑏𝑏1
𝑏𝑏2
⋯
𝑏𝑏𝑛𝑛
 
 

Theorem 1 The necessary and sufficient condition for a transportation problem to have a solution is that the total demand equals the total supply.

Definition 1 (Balanced problem) A transportation problem is said to be balanced if

                                                                             𝑚𝑚                    𝑛𝑛

𝑎𝑎𝑖𝑖 = 𝑏𝑏𝑗𝑗  

                                                                             𝑖𝑖=1                𝑗𝑗=1

If the transportation problem is unbalanced, we have to convert it into a balanced one before solving it. There are two possible cases:

Case 1. The demand exceeds the supply, ∑𝑚𝑚𝑖𝑖=1𝑎𝑎𝑖𝑖 < ∑𝑛𝑛𝑗𝑗=1𝑏𝑏𝑗𝑗   

It is not possible to satisfy the total demand with the existing supply. In this case, a dummy source or origin 𝑂𝑂𝑚𝑚+1 is added to balance the model. Its corresponding supply and unit transportation cost are the following:

𝑎𝑎𝑚𝑚+1 = ∑𝑛𝑛𝑗𝑗=1𝑏𝑏𝑗𝑗 − ∑𝑚𝑚𝑖𝑖=1𝑎𝑎𝑖𝑖, 𝑐𝑐𝑚𝑚+1,𝑗𝑗 = 0

Case 2. The supply exceeds the demand, ∑𝑚𝑚𝑖𝑖=1𝑎𝑎𝑖𝑖 > ∑𝑛𝑛𝑗𝑗=1𝑏𝑏𝑗𝑗   

Being the total supply higher than the total demand, we add a dummy destination 𝐷𝐷𝑛𝑛+1 to the problem, such that its demand and unit transportation costs are:

𝑏𝑏𝑛𝑛+1 = ∑𝑛𝑛𝑖𝑖=1𝑎𝑎𝑖𝑖 − ∑𝑛𝑛𝑗𝑗=1𝑏𝑏𝑗𝑗, 𝑐𝑐𝑖𝑖,𝑛𝑛+1 = 0

The procedure of calculating an initial basic feasible solution is performed in a tableau of the same dimensions as the transportation costs tableau; the transportation solution tableau, where each position (𝑖𝑖, 𝑗𝑗) is associated with the decision variable 𝑥𝑥𝑖𝑖𝑗𝑗, that is, the number of units of product to be transported from origin 𝑂𝑂𝑖𝑖 to destination 𝐷𝐷𝑗𝑗. Such positions (𝑖𝑖, 𝑗𝑗) are called cells, and represent a solution. An empty cell denotes a value of zero.

The Northwest Corner method
Given a balanced transportation problem, and starting at a solution tableau with all the cells (𝑖𝑖, 𝑗𝑗) empty, the following steps lead to an initial basic feasible solution.

Step 1: In the rows and columns under consideration, select the cell (𝑖𝑖, 𝑗𝑗) in the upper lefthand corner (northwest corner) of the solution tableau (to begin, 𝑖𝑖 = 1, 𝑗𝑗 = 1).

Step 2: Assign to the variable 𝑥𝑥𝑖𝑖𝑗𝑗 the feasible amount consistent with the row and the column requirements of that cell, that is, the value:

𝑥𝑥𝑖𝑖𝑗𝑗 = min {𝑎𝑎𝑖𝑖, 𝑏𝑏𝑗𝑗}

At least one of the requirements, the supply or the demand, will then be met. Adjust the supply 𝑎𝑎𝑖𝑖 and the demand 𝑏𝑏𝑗𝑗 as follows:

1.       If 𝑎𝑎𝑖𝑖 happens to be the minimum, then the supply of the origin 𝑂𝑂𝑖𝑖 becomes zero, and the row 𝑖𝑖 is eliminated from further consideration. The demand 𝑏𝑏𝑗𝑗 is replaced by

𝑏𝑏𝑗𝑗 − 𝑎𝑎𝑖𝑖.

2.       If 𝑏𝑏𝑗𝑗 happens to be the minimum, then the demand of the destination 𝐷𝐷𝑗𝑗 becomes zero, and the column 𝑗𝑗 is eliminated from further consideration. The supply 𝑎𝑎𝑖𝑖 is replaced by 𝑎𝑎𝑖𝑖 − 𝑏𝑏𝑗𝑗.

3.       If 𝑎𝑎𝑖𝑖 = 𝑏𝑏𝑗𝑗, then the adjusted values for the supply 𝑎𝑎𝑖𝑖 and the demand 𝑏𝑏𝑗𝑗 become both zero. The row 𝑖𝑖 and the column 𝑗𝑗 are eliminated from further consideration.

Step 3: Two cases may arise:

1.       If only one row or only one column remains under consideration, then any remaining cells (𝑖𝑖, 𝑗𝑗), that is, variables 𝑥𝑥𝑖𝑖𝑗𝑗 associated with these cells, are selected and the remaining supplies are assigned to them. Stop.

2.       Otherwise, go to Step 1.

The above Northwest Corner method is a very simple procedure proposed to find a basic feasible solution for a transportation problem. However, the unit transportation costs play no role in this method, which simply selects the upper left-hand corner variable and assigns a value to it.

 

Lagrange Multiplier Method
Consider the equality constrained problem:  

minimize 𝑓𝑓(𝒙𝒙)

subject to ℎ𝑗𝑗(𝒙𝒙) = 0,  𝑗𝑗 = 1,2, ⋯ , 𝑟𝑟 < 𝑛𝑛.

Transform this constrained problem to an unconstrained problem via the introduction of socalled Lagrange multipliers 𝜆𝜆𝑗𝑗,  𝑗𝑗 = 1,2, ⋯ , 𝑟𝑟, in the formulation of the Lagrangian function: 

𝐿𝐿(𝒙𝒙, 𝝀𝝀) = 𝑓𝑓(𝒙𝒙) + ∑𝑟𝑟𝑗𝑗=1𝜆𝜆𝑗𝑗 ℎ𝑗𝑗(𝒙𝒙) = 𝑓𝑓(𝒙𝒙) + 𝝀𝝀⊤𝒉𝒉(𝒙𝒙).

The necessary conditions for 𝒙𝒙∗ to be a constrained internal local minimum of the equality constrained problem is that 𝒙𝒙∗ corresponds to a stationary point (𝒙𝒙∗, 𝝀𝝀∗) of the Lagrangian function, i.e. that a vector exists such that

𝜕𝜕𝐿𝐿 (𝒙𝒙∗, 𝝀𝝀∗) = 0,  𝑖𝑖 = 1,2, ⋯ , 𝑛𝑛

𝜕𝜕𝑥𝑥𝑖𝑖 𝒙𝒙
 𝜕𝜕𝐿𝐿 ( ∗, 𝝀𝝀∗) = 0,  𝑗𝑗 = 1,2, ⋯ , 𝑟𝑟

𝜕𝜕𝜆𝜆𝑗𝑗
Note that necessary conditions represent 𝑛𝑛 + 𝑟𝑟 equations in the 𝑛𝑛 + 𝑟𝑟 unknowns 𝑥𝑥 . The solutions to these, in general non-linear equations, therefore give candidate solutions 𝒙𝒙∗ to the problem. If 𝑓𝑓(𝒙𝒙) and the ℎ𝑗𝑗(𝒙𝒙) are all convex functions, then these conditions indeed constitute sufficiency conditions. In this case the local constrained minimum is unique and represents the global minimum.

 

 

 

Karush and Kuhn and Tucker (KKT) Conditions Consider the problem:

minimize 𝑓𝑓(𝒙𝒙)

subject to 𝑔𝑔𝑗𝑗(𝒙𝒙) ≤ 0,  𝑗𝑗 = 1,2, ⋯ , 𝑚𝑚 Define the Lagrangian:

𝐿𝐿(𝒙𝒙, 𝝀𝝀) = 𝒇𝒇(𝒙𝒙) + ∑𝑚𝑚𝑗𝑗=1𝜆𝜆𝑗𝑗 𝑔𝑔𝑗𝑗(𝒙𝒙).

At the point 𝒙𝒙∗, corresponding to the solution of the primal problem, the following conditions must be satisfied:

𝑚𝑚

𝜕𝜕𝑓𝑓 (𝒙𝒙∗) + 𝜕𝜕𝑔𝑔𝑗𝑗 (𝒙𝒙∗) = 0,  𝑖𝑖 = 1,2, ⋯ , 𝑛𝑛

                                               𝜕𝜕𝑥𝑥𝑖𝑖                          𝜕𝜕𝑥𝑥𝑖𝑖
𝑗𝑗=1

                                                            𝑔𝑔𝑗𝑗(𝒙𝒙∗) ≤ 0,  𝑗𝑗 = 1,2, ⋯ , 𝑚𝑚          

𝜆𝜆𝑗𝑗∗𝑔𝑔𝑗𝑗(𝒙𝒙∗) = 0,  𝑗𝑗 = 1,2, ⋯ , 𝑚𝑚

𝜆𝜆𝑗𝑗∗ ≥ 0,  𝑗𝑗 = 1,2, ⋯ , 𝑚𝑚

KKT conditions also constitute sufficient conditions for 𝒙𝒙∗ to be a constrained minimum, if

𝑓𝑓(𝒙𝒙) and the 𝑔𝑔𝑗𝑗(𝒙𝒙) are all convex functions.

 

Optimal Control  
Consider the optimal control problem:  

𝑇𝑇

𝑚𝑚𝑖𝑖𝑛𝑛𝑖𝑖𝑚𝑚𝑖𝑖𝑧𝑧𝑚𝑚 𝐿𝐿 (𝑥𝑥, 𝑢𝑢)𝑑𝑑𝑑𝑑 + 𝑉𝑉(𝑥𝑥(𝑇𝑇))𝑑𝑑𝑑𝑑

0

subject to the constraint                

𝑥𝑥̇ = 𝑓𝑓(𝑥𝑥, 𝑢𝑢), 𝑥𝑥 ∈ 𝑅𝑅𝑛𝑛, 𝑢𝑢 ∈ 𝑅𝑅𝑚𝑚

Abstractly, this is a constrained optimization problem where we seek a feasible trajectory

(𝑥𝑥(𝑑𝑑), 𝑢𝑢(𝑑𝑑)) that minimizes the cost function  

𝑇𝑇

𝐽𝐽(𝑥𝑥, 𝑢𝑢) =  𝐿𝐿 (𝑥𝑥, 𝑢𝑢)𝑑𝑑𝑑𝑑 + 𝑉𝑉(𝑥𝑥(𝑇𝑇))

0

The term 𝐿𝐿(𝑥𝑥, 𝑢𝑢) is referred to as the integral cost and 𝑉𝑉(𝑥𝑥(𝑇𝑇)) is the final (or terminal) cost. There are many variations and special cases of the optimal control problem.

Infinite horizon optimal control. If we let 𝑇𝑇 = ∞  and set 𝑉𝑉 = 0, then we seek to optimize a cost function over all time. This is called the infinite horizon optimal control problem, versus the finite horizon problem with 𝑇𝑇 < ∞ . Note that if an infinite horizon problem has a solution with finite cost, then the integral cost term 𝐿𝐿(𝑥𝑥, 𝑢𝑢) must approach zero as 𝑑𝑑 → ∞.

Linear quadratic (LQ) optimal control. If the dynamical system is linear and the cost function is quadratic, we obtain the linear quadratic optimal control problem:  

𝑇𝑇

𝑥𝑥̇ = 𝐴𝐴𝑥𝑥 + 𝐵𝐵𝑢𝑢,  𝐽𝐽   

In this formulation, 𝑄𝑄 ≥ 0 penalizes state error, 𝑅𝑅 > 0 penalizes the input and 𝑃𝑃 > 0 penalizes terminal state. This problem can be modified to track a desired trajectory (𝑥𝑥𝑑𝑑, 𝑢𝑢𝑑𝑑) by rewriting the cost function in terms of (𝑥𝑥 − 𝑥𝑥𝑑𝑑) and (𝑢𝑢 − 𝑢𝑢𝑑𝑑).

Terminal constraints. It is often convenient to ask that the final value of the trajectory, denoted 𝑥𝑥𝑓𝑓, be specified. We can do this by requiring that 𝑥𝑥(𝑇𝑇) = 𝑥𝑥𝑓𝑓 or by using a more general form of constraint: 𝜙𝜙(𝑥𝑥(𝑇𝑇)) = 0,  𝑖𝑖 = 1, ⋯ , 𝑞𝑞. The fully constrained case is obtained by setting 𝑞𝑞 = 𝑛𝑛 and defining 𝜙𝜙(𝑥𝑥(𝑇𝑇)) = 𝑥𝑥𝑖𝑖(𝑇𝑇) − 𝑥𝑥𝑖𝑖,𝑓𝑓. For a control problem with a full set of terminal constraints, 𝑉𝑉(𝑥𝑥(𝑇𝑇)) can be omitted since its value is fixed.

Time optimal control. If we constrain the terminal condition to 𝑥𝑥(𝑇𝑇) = 𝑥𝑥𝑓𝑓, let the terminal time 𝑇𝑇 be free (so that we can optimize over it) and choose𝐿𝐿(𝑥𝑥, 𝑢𝑢) = 1, we can find the time-optimal trajectory between an initial and final condition. This problem is usually only well-posed if we additionally constrain the inputs 𝑢𝑢 to be bounded.

A very general set of conditions are available for the optimal control problem that captures most of these special cases in a unifying framework. Consider a nonlinear system

𝑥𝑥̇ = 𝑓𝑓(𝑥𝑥, 𝑢𝑢), 𝑥𝑥 ∈ 𝑅𝑅𝑛𝑛

where 𝑥𝑥(0) given, 𝑢𝑢 ∈ 𝑅𝑅𝑝𝑝, and𝑓𝑓(𝑥𝑥, 𝑢𝑢) = (𝑓𝑓1(𝑥𝑥, 𝑢𝑢), ⋯ , 𝑓𝑓𝑛𝑛(𝑥𝑥, 𝑢𝑢)): 𝑅𝑅𝑛𝑛 × 𝑅𝑅𝑝𝑝 → 𝑅𝑅𝑛𝑛. We wish to minimize a cost function 𝐽𝐽 with terminal constraints:

𝑇𝑇

𝐽𝐽 = ∫0 𝐿𝐿 (𝑥𝑥, 𝑢𝑢)𝑑𝑑𝑑𝑑 + 𝑉𝑉(𝑥𝑥(𝑇𝑇)),  𝜙𝜙(𝑥𝑥(𝑇𝑇)) = 0.

The function 𝜙𝜙: 𝑅𝑅𝑛𝑛 → 𝑅𝑅𝑞𝑞 gives a set of 𝑞𝑞 terminal constraints.  

Analogous to the case of optimizing a function subject to constraints, we construct the Hamiltonian:  

𝐻𝐻 = 𝐿𝐿 + 𝜆𝜆⊤𝑓𝑓 = 𝐿𝐿 + ∑𝑖𝑖 𝜆𝜆𝑖𝑖 𝑓𝑓𝑖𝑖.

The variables 𝜆𝜆𝑖𝑖 are functions of time and are often referred to as the costate variables.

Pontryagin’s Maximum Principle: If (𝑥𝑥∗, 𝑢𝑢∗) is optimal, then there exists 𝜆𝜆∗(𝑑𝑑) ∈ 𝑅𝑅𝑛𝑛 and

𝜈𝜈∗(𝑑𝑑) ∈ 𝑅𝑅𝑛𝑛 such that

𝑥𝑥̇𝑖𝑖 =  𝜕𝜕𝜆𝜆𝜕𝜕𝜕𝜕𝑖𝑖 , 𝜆𝜆̇𝑖𝑖 = − 𝜕𝜕𝑥𝑥𝜕𝜕𝜕𝜕𝑖𝑖,

𝑥𝑥(0) is given, and 𝜙𝜙(𝑥𝑥(𝑇𝑇)) = 0,

                                                                                𝜕𝜕𝜕𝜕                                 ⊤ 𝜕𝜕𝜕𝜕  

𝜆𝜆(𝑇𝑇) =   (𝑥𝑥(𝑇𝑇)) + 𝑣𝑣  𝜕𝜕𝑥𝑥𝑖𝑖        𝜕𝜕𝑥𝑥

and

𝐻𝐻(𝑥𝑥∗(𝑇𝑇), 𝑢𝑢∗(𝑑𝑑), 𝜆𝜆∗(𝑑𝑑)) ≤ 𝐻𝐻(𝑥𝑥∗(𝑑𝑑), 𝑢𝑢, 𝜆𝜆∗(𝑑𝑑)) for all 𝑢𝑢 ∈ 𝛺𝛺.

The form of the optimal solution is given by the solution of a differential equation with boundary conditions. If 𝑢𝑢 = argmin 𝐻𝐻(𝑥𝑥, 𝑢𝑢, 𝜆𝜆) exists, we can use this to choose the control law 𝑢𝑢 and solve for the resulting feasible trajectory that minimizes the cost. The boundary conditions are given by the 𝑛𝑛 initial states 𝑥𝑥(0), the 𝑞𝑞 terminal constraints on the state 𝜙𝜙(𝑥𝑥(𝑇𝑇)) = 0 and the 𝑛𝑛 − 𝑞𝑞 final values for the Lagrange multipliers 𝜕𝜕𝜕𝜕    ⊤ 𝜕𝜕𝜕𝜕.

𝜆𝜆(𝑇𝑇) =   (𝑥𝑥(𝑇𝑇)) + 𝑣𝑣  

                                                                                𝜕𝜕𝑥𝑥                                    𝜕𝜕𝑥𝑥

In this last equation, 𝑣𝑣 is a free variable and so there are 𝑛𝑛 equations in 𝑛𝑛 + 𝑞𝑞 free variables, leaving 𝑛𝑛 − 𝑞𝑞 constraints on 𝜆𝜆(𝑇𝑇). In total, we thus have 2𝑛𝑛 boundary values. If 𝐻𝐻 is

𝜕𝜕𝜕𝜕 differentiable, then a necessary condition for the optimal input is   = 0. We note that even

𝜕𝜕𝜕𝜕

though we are minimizing the cost, this is still usually called the maximum principle.

 

 

 

Exercises
The major objective of the followings tasks is to let you work out the exercises in order to gain a better understanding of the concepts. Although Matlab results (plots/graphs) are required to support your conclusions/discussions in the written report, programming codes are not needed (assessed as the practical work). Hence, a good programming style would be helpful to limit the bugs in your codes and arrive at the correct result.

 

Task 1 - Simplex Method
1.a. Consider the transportation problem described by the following graph:

  

Set up the optimisation problem. That is, express the minimisation cost equation, and the equations of the constraints.  

Write the corresponding equations in vector/matrix form.

Draw the transportation tableau.

Write a Matlab program for the Northwest Corner method.

You have to show all intermediate results (the tableaus) in the report. But the Matlab code is not required (assessed as part of the practical work). 

 

1.b. The function linprog is available in Matlab to solve linear programming problems. An extract from the help menu is given below.

X = LINPROG(f,A,b) attempts to solve the linear programming problem:  min f'*x    subject to:   A*x <= b  

X = LINPROG(f,A,b,Aeq,beq) solves the problem above while additionally satisfying the equality constraints Aeq*x = beq.  

X = LINPROG(f,A,b,Aeq,beq,LB,UB) defines a set of lower and upper bounds on the design variables, X, so that the solution is in the range LB<=X<=UB. Use empty matrices for LB and UB, if no bounds exist. Set LB(i)=-Inf if X(i) is unbounded below; set UB(i)=Inf if X(i) is unbounded above. 

Now, you have to convert the problems in Part 1.a to the appropriate function input format. Verify your results using Matlab with regard to the Northwest Corner method. Discuss the cause of discrepancies if any.

Show and discuss the results in the report. 

 

 

Task 2 – Lagrange Multiplier Method
2.a. Given the function  

𝑓𝑓(𝑥𝑥, 𝑦𝑦) = 𝑥𝑥𝑦𝑦(2 + 𝑥𝑥),

 subject to the equality constraint  

𝑔𝑔(𝑥𝑥, 𝑦𝑦) = 𝑥𝑥2 + 𝑦𝑦2 = 2.

Obtain, using a Matlab program, the extreme points of 𝑓𝑓(𝑥𝑥, 𝑦𝑦). Identify the minimum

(𝑥𝑥𝑚𝑚𝑖𝑖𝑛𝑛, 𝑦𝑦𝑚𝑚𝑖𝑖𝑛𝑛) and maximum point (𝑥𝑥𝑚𝑚𝑚𝑚𝑥𝑥, 𝑦𝑦𝑚𝑚𝑚𝑚𝑥𝑥). Illustrate your answer with 3-dimensinal plots of the function, constraint, and extreme points.

(Hint: use symbolics to represent the variables 𝑥𝑥, 𝑦𝑦, define the function 𝑓𝑓 and constraint 𝑔𝑔. Then use the jacbian command to find the solution of the Lagrangian derivatives. Furthermore, solve for the condition that the constraint is satisfied, e.g. S=solve(L(1),L(2),g), where L(1), L(2) are the Lagrangian derivatives and ‘g’ is the constraint equation. Finally, determine the minimum and maximum points using the min and max commands.) Show your resultant pots in the report. 

 

2.b. Given a piece of metal sheet of surface area 𝑆𝑆 = 10𝑚𝑚2, if it is manufactured as a rectangular container of sides 𝑥𝑥1, 𝑥𝑥2, 𝑥𝑥3, what is the maximum volume 𝑉𝑉 that can be enclosed.  

Show your workings and results in the report. 

 

2.c. A factory can produce 3 types of products 𝑥𝑥1, 𝑥𝑥2, 𝑥𝑥3, but the facility can allow only a limited amount  

𝑔𝑔 = 𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 = 100.

The profit that can be obtained is  

𝑃𝑃 = 8𝑥𝑥1𝑥𝑥2𝑥𝑥32 − 200(𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3).

What is the maximum profit that can be obtained and what are the optimum numbers of each item should be produced?  

Show your workings and results in the report. 

 

Task 3 - Karush and Kuhn and Tucker (KKT) Conditions

3.a. Use the KKT condition approach, find the minimum of the function  

𝑓𝑓(𝑥𝑥1, 𝑥𝑥2) = (𝑥𝑥1 − 1)2 + (𝑥𝑥2 − 2)2

such that  

𝑥𝑥1 ≥ 0, 𝑥𝑥2 ≥ 0, 𝑥𝑥1 + 𝑥𝑥2 ≤ 2, 𝑥𝑥2 − 𝑥𝑥1 = 1 What are the optimum values 𝑓𝑓  ?

Show your workings and results in the report. 

 

3.b. Consider the four-bar truss shown below, in which members 1, 2, and 3 have the same cross-sectional area 𝑥𝑥1 and the same length 𝐿𝐿, while member 4 has an area of cross section

 

𝑥𝑥2 and length √3𝐿𝐿.  

  

The weight of the truss per unit value of 𝐿𝐿 can be expressed as  

𝑓𝑓  .

The deflection of point 𝐴𝐴 is constrained by  

 .

Let the cross-sections bee constrained by 𝑥𝑥1 ≥ 5.73, 𝑥𝑥2 ≥ 7.17. Find the minimum weight (per 𝐿𝐿) and the cross-section areas.

Show your workings and results in the report. 

 

Task 4 – Optimal Control
4.a. Given a dynamical system  

𝑥𝑥̇ = 𝑎𝑎𝑥𝑥 + 𝑏𝑏𝑢𝑢, 𝑎𝑎 > 0, 𝑏𝑏 > 0,

and 𝑥𝑥(0) = 𝑥𝑥0. Find the optimal trajectory (𝑥𝑥(𝑑𝑑),  𝑢𝑢(𝑑𝑑)) such that the following cost is minimized  

𝐽𝐽  .

Hint: find 𝜆𝜆 = 𝑥𝑥(𝑇𝑇)𝑚𝑚𝑚𝑚(𝑇𝑇−𝑡𝑡), then 𝑑𝑑𝜆𝜆  = 𝑥𝑥(𝑇𝑇) 𝑑𝑑𝑒𝑒 𝑎𝑎(𝑇𝑇−𝑡𝑡) 𝑑𝑑(𝑇𝑇−𝑡𝑡) = −𝑥𝑥(𝑇𝑇)𝑎𝑎𝑚𝑚(𝑇𝑇−𝑡𝑡) = −𝑎𝑎𝜆𝜆

                                                                 𝑑𝑑𝑡𝑡                      𝑑𝑑(𝑇𝑇−𝑡𝑡)    𝑑𝑑𝑡𝑡

Show your workings and results in the report. 

 

4.b. Suppose we wish to drive a car from a stationary position on a driveway into a stationary position in a garage, having moved some distance 𝐴𝐴. The available controls for the driver are the accelerator and the brake (for simplicity, we assume no gear changes), and we take the equation of motion of the car as

𝑑𝑑2𝑥𝑥

 2 = 𝑢𝑢

𝑑𝑑𝑑𝑑

where 𝑢𝑢 = 𝑢𝑢(𝑑𝑑) represents the applied acceleration or deceleration (braking) and 𝑥𝑥 the distance travelled. The control 𝑢𝑢 is subject to both a lower bound (maximum braking) and upper bound (maximum acceleration), that is,

−𝛼𝛼 ≤ 𝑢𝑢 ≤ 𝛽𝛽

where 𝛼𝛼, 𝛽𝛽 are positive constants. The problem can now be stated: minimise the time taken, 𝑇𝑇, that is, 

𝑇𝑇

𝑇𝑇 =  𝑑𝑑𝑑𝑑

0

and boundary conditions

𝑥𝑥(0) = 0, 𝑥𝑥̇(0) = 0, 𝑥𝑥(𝑇𝑇) = 𝑎𝑎, 𝑥𝑥̇(𝑇𝑇) = 0

We can change the control constraint into an equality constraint by introducing another control variable, say 𝑣𝑣, where

𝑣𝑣2 = (𝑢𝑢 + 𝛼𝛼)(𝛽𝛽 − 𝑢𝑢)

Since 𝑣𝑣2 is positive, 𝑢𝑢 must satisfy the constraint. Further introduce the usual state variable notation 𝑥𝑥1 =𝑥𝑥 so that 

𝑥𝑥̇1 = 𝑥𝑥2,  𝑥𝑥̇2 = 𝑢𝑢

with boundary conditions 

𝑥𝑥1(0) = x2(0) = 0, 𝑥𝑥1(𝑇𝑇 ) = 𝐴𝐴, 𝑥𝑥2(𝑇𝑇) = 0

Now, formulate the augmented functional (containing three multipliers 𝜆𝜆1, 𝜆𝜆2, 𝜆𝜆3, for the two states 𝑥𝑥̇1 and 𝑥𝑥̇2 and control 𝑣𝑣2). Then use the Euler equations to determine the conditions for optimality. One of the conditions obtained is

                                                            𝜕𝜕𝜕𝜕 𝑑𝑑 𝜕𝜕𝜕𝜕
 𝜕𝜕𝑣𝑣 − 𝑑𝑑𝑑𝑑𝑑𝑑𝑣𝑣̇ = 0 ⇒ 2𝑣𝑣𝜆𝜆3 = 0  

Since 𝜆𝜆3 cannot be zero, then set 𝑣𝑣 = 0. Hence, initially 𝑢𝑢 = 𝛽𝛽 (driving forward) and then 𝑢𝑢 = −𝛼𝛼 (stopping). Let the switching time of the control be 𝜏𝜏, give an expression for the control 𝑢𝑢.

From, 𝑥𝑥̇1 = 𝑥𝑥2,  𝑥𝑥̇2 = 𝑢𝑢, perform integrations to obtain 𝑥𝑥1 and 𝑥𝑥2.

Furthermore, 𝑥𝑥1 and 𝑥𝑥2 must be continuous at the switching time (where the control changes from 𝛽𝛽 to −𝛼𝛼), find the switching time 𝜏𝜏 and the final time 𝑇𝑇.

Show your workings and results in the report. 

 

4.c. This problem is concerned with the design of a linear quadratic regulator. Consider a system   

𝑥𝑥̇ = 𝐴𝐴𝑥𝑥 + 𝐵𝐵𝑢𝑢,  𝑥𝑥(0) = 𝑥𝑥0,

 the cost function is  

                                           𝐽𝐽  1 𝑇𝑇(𝑥𝑥⊤𝑄𝑄𝑥𝑥𝑥𝑥   

The Hamiltonian is  

                                                 𝐻𝐻 =  𝑥𝑥 𝑄𝑄𝑥𝑥𝑥𝑥 +  𝑢𝑢 𝑄𝑄𝜕𝜕𝑢𝑢 + 𝜆𝜆⊤(𝐴𝐴𝑥𝑥 + 𝐵𝐵𝑢𝑢)

                                                            2                     2

The optimal conditions based on Pontryagin’s maximum principle are

                 

𝜕𝜕𝐻𝐻

𝑥𝑥̇ =   = 𝐴𝐴𝑥𝑥 + 𝐵𝐵𝑢𝑢

𝜕𝜕𝜆𝜆

                                                                               𝜕𝜕𝐻𝐻                    ⊤𝜆𝜆

−𝜆𝜆̇ == 𝑄𝑄𝑥𝑥𝑥𝑥 + 𝐴𝐴

𝜕𝜕𝑥𝑥

                                                                    0 = 𝜕𝜕𝐻𝐻                   ⊤𝐵𝐵

= 𝑄𝑄𝜕𝜕𝑢𝑢 + 𝜆𝜆

𝜕𝜕𝑢𝑢

 

From the last equation, we have 𝑢𝑢 = −𝑄𝑄𝜕𝜕−1𝐵𝐵⊤𝜆𝜆. Put 𝜆𝜆 = 𝑃𝑃𝑥𝑥, and set 𝑃𝑃̇ = 0, show that the algebraic Riccati equation can be given by  

𝑃𝑃𝐴𝐴 + 𝐴𝐴𝑇𝑇𝑃𝑃 − 𝑃𝑃𝐵𝐵𝑄𝑄𝜕𝜕−1𝐵𝐵𝑇𝑇𝑃𝑃 + 𝑄𝑄𝑥𝑥 = 0.

Now, consider another system that is controlled only by the acceleration/deceleration, the system is given by  

𝑥𝑥̇

                                                                 𝑥𝑥̇12 = 00 10𝑥𝑥𝑥𝑥12 + 01𝑢𝑢 
Choose arbitrary 𝑞𝑞 (e.g., 1, 2, 5) for 𝑄𝑄𝑥𝑥 = 𝑞𝑞2            0 , 𝑄𝑄𝜕𝜕 = 1. Show that the control gain is

                                                                                         0      0



𝐾𝐾 = 𝑞𝑞 2𝑞𝑞. Select different combinations between 𝑄𝑄𝑥𝑥 and 𝑄𝑄𝜕𝜕, comment on how they affect the system response. Verify your result with the Matlab lqr command and inspect the system response using Simulink.  

The Matlab command lqr provides the regulator gain factor 𝐾𝐾 = −𝑄𝑄𝜕𝜕−1𝐵𝐵⊤𝑃𝑃, 𝑢𝑢 = −𝐾𝐾𝑥𝑥. The command lqr can be called using:

[K,S,E] = LQR(SYS,Qx,Qu) to calculate the optimal gain matrix 𝐾𝐾, such that: for a continuous-time state-space model SYS=ss(A,B,C,D), the state-feedback law

𝑢𝑢 = −𝐾𝐾𝑥𝑥 minimizes the cost function 𝐽𝐽 = ∫(𝑥𝑥⊤𝑄𝑄𝑥𝑥𝑥𝑥 + 𝑢𝑢⊤𝑄𝑄𝜕𝜕𝑢𝑢) 𝑑𝑑𝑑𝑑, subject to the system dynamics 𝑥𝑥̇ = 𝐴𝐴𝑥𝑥 + 𝐵𝐵𝑢𝑢.

You have to define the system matrices A, B, C, D. Then construct a system structure using the command ss(A,B,C,D) before calling the lqr command. The gain 𝐾𝐾 will be stored in the workspace. Furthermore, build a Simulink model and run, say, for 10 time-units (set the stop time parameter in the ‘Simulation’ menu). In the state-space model, you have to assign the appropriate system matrix values.  

 

  

                 Simulink Model                                          Control                                          Response

 

Show your workings and results in the report.