Canonical form

Error

There was an error loading the page.

Contributors

Julien Ugon

Feedback

From users who are members of SIT316 :

Julien Ugon

said

Needs to be tested

8 months, 2 weeks ago

History

○

Julien Ugon 8 months, 2 weeks ago

Published this.

○

Julien Ugon 8 months, 2 weeks ago

Gave some feedback: Needs to be tested

○

Julien Ugon 9 months, 1 week ago

Created this.

Name	Status	Author	Last Modified
Canonical form	Needs to be tested	Julien Ugon	06/08/2024 00:32
Duality	Needs to be tested	Julien Ugon	06/09/2024 00:38

There are 9 other versions that do you not have access to.

Question statement

Convert the following linear programming problem to canonical form:

$\begin{gathered} \var{{optimise}}\text{ } \var{objective} \text{ subject to }\\ \var{system} \end{gathered}$

$x_i≥0, \forall\in \var{Jp}$

$x_j≤0, \forall j\in \var{Jn}$

Give any introductory information the student needs.

			Name	Type	Generated Value

nvar	integer	3
positivity	list	[ 1, -1, 0 ]
ncons	integer	4
A	list	Nested 4×3 list
b	list	[ 4, 5, -5, 1 ]
direction	list	[ "=", "=", "≥", "=" ]
C	list	[ -5, 1, 1 ]
optimise	string	maximise

			Name	Type	Generated Value

x	list	[ "x1", "x2", "x3" ]
L	list	List of 4 items
Cp	list	List of 4 items
Constraints	list	List of 4 items
system	string	\begin{gathered}x_{1} + x_{2}
objective_string	string	-5x1+1x2+1*x3
objective	expression	x2 - 5x1 + x3
Jp	set	set(1)
Jn	set	set(2)

			Name	Type	Generated Value

y	list	[ "y1", "y2", "y3", "y4" ]
Mv	list	Nested 4×3 list
Av	list	Nested 4×4 list
cv	list	[ [ -5 ], [ -1 ], [ 1, -1 ] ]
cc	list	[ -5, -1, 1, -1 ]
objectivev_string	string	-5y1+-1y2+1y3+-1y4
objectivev	expression	-5y1 - y2 + y3 - y4
Lv	list	List of 4 items
Cpv	list	List of 4 items
Constraintsv	list	List of 4 items
Systemv	string	\begin{gathered}y_{1} - y_{2}
nvarcanonical	number	4
nconscanonical	number	7

			Name	Type	Generated Value

Mc	list	List of 4 items
Ac	list	Nested 7×4 list
bv	list	List of 4 items
bc	list	[ 4, -4, 5, -5, 5, 1, -1 ]
AA	matrix	Matrix of size 7×5
Lc	list	List of 7 items
Cpc	list	List of 7 items
Constraintsc	list	List of 7 items
systemc	string	\begin{gathered}y_{1} - y_{2}

			Name	Type	Generated Value

cstudent

list

[ -5, -1, 1, -1 ]

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
random(2..3)

JME function reference

Description

Number of variables in the system.

Describe what this variable represents, and list any assumptions made about its value.

Can an exam override the value of this variable?

Generated value: `integer`

→ Used by:

A
C
positivity
x

This variable doesn't seem to be used anywhere.

Parts

Information only
Canonical form Gap-fill
1. Gap c Matrix entry
  Add
2. Gap System Matrix entry
  Add

Information only

Ask the student a question, and give any hints about how they should answer this part.

In this quiz you will be asked to convert linear programs to canonical or standard forms. The variables in the solution will be $y_1,\ldots,y_n$ .

After you convert the linear program in your notes, your own solution may have different variable names, for example, your constraints may look like:

$\begin{alignat}{4} x_1&+3x_2^+&-3x_2^-&&+s_1 &&&= 2\\ -2x_1 &-5x_2^+&+5x_2^-&-2x_3 &&+ s_2 &&=3\\ 3x_1 &&&-x_3 &&&&=5. \end{alignat}$

Each of your variables should be assigned to one of the $y_i$ variables in the quiz, for example:

$\begin{align} y_1 &= x_1 & y_2 &= x_2^+ & y_3 &= x_2^-\\ y_4 &= x_3 & y_3 &= s_1 & y_4 &= s_2 \end{align}$

In the quiz the constraints then should become

$\begin{alignat}{4} y_1&+3y_2&-3y_3&+0y_4&+y_5&+0y_6 &&= 2\\ -2y_1 &-5y_2&+5y_3&-2y_4&+0y_5&+ y_6 &&=3\\ 3y_1 &+0y_2&+0y_3&-1y_4&+0y_5&+ 0y_6 &&=5 \end{alignat}$

In order to enter your solution in the boxes, select the appropriate number of rows (number of constraints, here, for example, 3) and of columns (number of variables, plus the right hand side, here 7) and enter the coefficients. For example:

Advice

In order to convert a problem to canonical form, we need to perform the following changes

The objective should be maximised.
All variables should be positive.
All constraints should be in the form ≤

Maximised objective

The objective is already being maximised, there is nothing to do here.

The objective is being minimised, so we just multiply it by -1, and the new objective becomes $\simplify{-{objective}}$ .

Changing the variables

We change the variables as follows:

The variables $x_i, i∈\var{Jp}$ are already in the desired format, so we set variables $y_j=x_i$ for each of them.
The variables $x_i, i∈\var{Jn}$ are nonpositive, so we set variables $y_j=x_i$ for each of them.
The variables $x_i, \notin \var{union(Jp,Jn)}$ are free so we set two variables $y_j$ and $y_{j+1}$ so that $x_i = y_j-y_{j+1}$ . The coefficients for $y_j$ are the same as those of $x_i$ , and the coefficients for $y_{j+1}$ are the negative of those of $x_i$ .

The objective function becomes $\var{objectivev}$ and the constraints become

$\var{systemv}$

The constraints

The constraints should be changed as follows:

Any constraint of the form "≥" is multiplied by -1 (both the right and left hand sides).
Any equality constraint is replaced with two "≤" constraints, one of which has the same coefficients and the other one multiplied by -1.

The canonical form of the problem is:

$\begin{gathered} \text{maximise } \var{objectivev} \text{ subject to }\\ \var{systemc}\\ y_j\geq 0, \forall j=1…\var{nvarcanonical} \end{gathered}$

Give a worked solution to the whole question.

Use this tab to check that this question works as expected.

There was an error which means the tests can't run:

Part	Test	Passed?
Information only
Gap-fill
Gap-fill		Hasn't run yet
Matrix entry
Matrix entry		Hasn't run yet
Matrix entry
Matrix entry		Hasn't run yet

This question is used in the following exam:

Canonical and Standard forms by Julien Ugon in SIT316.

Loading...

Error

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Julien Ugon 8 months, 2 weeks ago

Julien Ugon 8 months, 2 weeks ago

Julien Ugon 9 months, 1 week ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Information only

Maximised objective

Changing the variables

The constraints

Loading...

Error

Canonical form

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Julien Ugon 8 months, 2 weeks ago

Julien Ugon 8 months, 2 weeks ago

Julien Ugon 9 months, 1 week ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Information only

Maximised objective

Changing the variables

The constraints

Generated value: `integer`