Lesson 8 - FOAM LP Standard Form and Simplex PDF

FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT FINASS Lecture 8 – LP Standard Form Federica Ricca Equivalent transformations of LP models  Reference forms for LP (Lect. 3) Special LP max cTx min cTx forms A...

FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT FINASS Lecture 8 – LP Standard Form Federica Ricca Equivalent transformations of LP models  Reference forms for LP (Lect. 3) Special LP max cTx min cTx forms Ax ≤ b Ax ≥ b x≥0 x≥0 max cTx Maximizing the output (performance) which can (1) Ax ≤ b be obtained by a prefixed (limited) quantity of input (resources). x≥0 min cTx Minimizing the input (resources) to obtain a (2) Ax ≥ b prefixed minimum (required) level of output (performance). x≥0 NOTE Forms (1) and (2) can be considered as “Reference forms”, since, after the two above propositions, a LP in arbitrary form can be always equivalently rewritten in one of the two forms. 3 FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  General LP and reference forms max / min c1x1 + c 2 x 2 +... + c j x j +... + c n x n Given a decision problem, one typically provides a x1,x 2 ,...,x j ,..., x n natural formulation of the problem as a LP.   b1  a11x1 + a12 x 2 +... + a1 j x j +... + a1n x n  = b1 This formulation may have constraints and o.f. of   b1 any type (arbitrary form).   b2  a21x1 + a22 x 2 +... + a2 j x j +... + a2n x n  = b2 On the contrary, we have introduced Reference forms   b2 which are formulations with a special structure:    bm  am1x1 + am 2 x 2 +... + amj x j +... + amn x n  = bm   bm x1, x 2 ,..., x n  0 Any LP model in arbitrary form can be equivalently re-written in one of the two reference forms (1), (2). Definition Given a LP denoted by M, another LP model M’ is equivalent to M if M and M’ have the same feasible set and the same optimal solutions. To transform a model M into an equivalent one, specific trasformation rules for the o.f. and to the constraints must be applied. 4 FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA Equivalent trasformations of linear constraints  LP in arbitrary form (Lect. 3) LP IN min cTx Proposition ARBITRARY Dk,nx = dk,1 Given a LP model in arbitrary min cTx min FORM Em,nx ≥ em,1 min form, it can be always Ax ≥ b Hh,n x ≤ hh,1 rewritten in the special form (2): x≥0 xn,1 ≥ 0 LP IN max cTx ARBITRARY Proposition Dk,nx = dk,1 max cTx max FORM Given a LP model in arbitrary Em,nx ≥ em,1 max form, it can be always Ax ≤ b Hh,n x ≤ hh,1 rewritten in the special form (1): x≥0 xn,1 ≥ 0 FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Equivalent transformations of constraints Example LP in arbitrary form Equivalent model in Reference form (1) max x1 + x 2 max x1 + x 2 − x1 + 0.5 x 2  3 − x1 + 0.5 x 2  3 x1 + x 2 = 6 − x1 − x 2  − 6 x1 + x 2  6 2 x1 + x 2  14 − 2 x1 − x 2  − 14 x1  0 x1  0 x2  0 x2  0 The first constraint is already an inequality in the required form. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Equivalent transformations of constraints Example LP in arbitrary form Equivalent model in Reference form (1) max x1 + x 2 max x1 + x 2 − x1 + 0.5 x 2  3 − x1 + 0.5 x 2  3 x1 + x 2 = 6 − x1 − x 2  − 6 x1 + x 2  6 2 x1 + x 2  14 − 2 x1 − x 2  − 14 x1  0 x1  0 x2  0 x2  0 The second constraint is an equality which can be transformed as follows. x1 + x2 ≤ 6 x1 + x2 ≤ 6 x1 + x2 = 6 x1 + x2 ≥ 6 -x1 + -x2 ≤ -6 An equality can be always replaced by an equivalent The second inequality can be e pair of inequalities having the same LHS and RHS equivalently rewritten as ≤. but opposite directions, one ≥, the other ≤. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Equivalent transformations of constraints Example LP in arbitrary form Equivalent model in Reference form (1) max x1 + x 2 max x1 + x 2 − x1 + 0.5 x 2  3 − x1 + 0.5 x 2  3 x1 + x 2 = 6 − x1 − x 2  − 6 x1 + x 2  6 2 x1 + x 2  14 − 2 x1 − x 2  − 14 x1  0 x1  0 x2  0 x2  0 The third constraint is an inequality, but it has the opposite direction w.r.t. the one required by reference form (1) To change the inequality direction from ≥ to ≤ it suffices to multiply both LHS and RHS by -1. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA LP Standard Form  Standard Form (SF) Reference max cTx min cTx Forms Ax ≤ b Ax ≥ b x≥0 x≥0 Linear System in Ax = b Standard Form S= x≥0 Definition A linear system is in standard form (SF) if: 1. all variables are subject to non negativity constraints; 2. all the other constraints are equations. A LP is in Standard Form if its system of constraints is in Standard Form. The objective function of the LP is not affected by the transformation into the equivalent SF. 11 FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Standard Form (SF) Example Consider the following LP in arbitrary form (here all variables are already non negative): In the SF the objective function has no role. min 2x1 – 5x2 The second x1 + 2x2 ≤ 5 constraint is an 4x1 – 3x2 = - 6 equality, therefore it remains the x1 – x2 ≥ 1 same x1 ≥ 0, x2 ≥ 0 FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Standard Form (SF) Example Consider the following LP in arbitrary form (here all variables are already non negative): min 2x1 – 5x2 x1 + 2x2 ≤ 5 4x1 – 3x2 = - 6 The third constraint is x1 – x2 ≥ 1 an inequality LHS ≥ RHS x1 ≥ 0, x2 ≥ 0 of type ≥ x1 – x2 > 1 difference LHS-RHS is positive Two cases are possible: x1 – x2 = 1 difference LHS-RHS is null constraint 3: s3 =(x1 – x2) – 1 ≥ 0 LHS – RHS We measure the absolute difference between LHS and RHS with a slack variable s3 ≥ 0: x1 – x2 – s3 = 1 By subtracting s3 ≥ 0 from the x1 – x2 ≥ 1 LHS of constraint 3, we get an s3 ≥ 0 equivalent equality FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Standard Form (SF) Example Consider the following LP in arbitrary form (here all variables are already non negative): min 2x1 – 5x2 The first x1 + 2x2 ≤ 5 constraint is an 4x1 – 3x2 = - 6 inequality of type ≤ x1 – x2 ≥ 1 LHS ≤ RHS x1 ≥ 0, x2 ≥ 0 x1 + 2x2 < 5 difference RHS-LHS is positive Two cases are possible: x1 + 2x2 = 5 difference RHS-LHS is null constraint 1: s1 = 5 – (x1 + 2x2) ≥ 0 RHS – LHS We measure the absolute difference between LHS and RHS with a slack variable s1 ≥ 0: x1 + 2x2 + s1 = 5 By adding s1 ≥ 0 to the LHS x1 + 2x2 ≤ 5 of constraint 1, we get an s1 ≥ 0 equivalent equality FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Standard Form (SF) Definition Given LP, a constraint is active (or Example binding) at x if, replacing x in the system, the Consider the following LP in arbitrary form LHS of the constraint is equal to its RHS. (here all variables are already non negative): min 2x1 – 5x2 x1 + 2x2 ≤ 5 4x1 – 3x2 = - 6 x1 – x2 ≥ 1 x1 ≥ 0, x2 ≥ 0 The equivalent LP in SF is: min 2x1 – 5x2 NOTE The slacks introduced to obtain equalities x1 + 2x2 + s1 = 5 are additional (non negative) variables of the model. 4x1 – 3x2 =-6 In fact, at the beginning they are unknown, since their x1 – x2 – s3 = 1 value in the optimal solution depends on the value of x1 ≥ 0, x2 ≥ 0 the decision variables x, and on which constraints are s1 ≥ 0, s3 ≥ 0 satisfied as equalities or as strict inequalities at the optimal solution. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA Active constraints in the Standard Form  Active constraints in the Standard Form Definition Given LP, a constraint is active at x if, replacing x in the system, the LHS of the constraint is equal to its RHS. PROPERTY If the LP is in SF, active constraints at a given x can be detected by looking directly at the sign of the corresponding slack. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Active constraints in the Standard Form Example 2x1 + 3x2 – x3 – s = 10 2x1 + 3x2 – x3 ≥ 10 s≥0 1 constraint in the 2 constraints in the original LP corresponding SF (one is the non negativity For a given x, one has: constr. of the slack s) 2 x1 + 3 x2 – x3 – s = 10 2 x1 + 3 x2 – x3 = 10 s=0 either the original the corresponding slack is null, i.e.: constraint is active at x non negativity constraints of s active at (x, s) 2 x1 + 3 x2 – x3 – s = 10 2 x1 + 3 x2 – x3 > 10 s>0 or the original constraint the corresponding slack is positive, i.e.: is not active at x non negativity constraints of s not active at (x, s) PROPERTY If the LP is in SF, active constraints at a given x can be detected by looking directly at the sign of the corresponding slack. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Active constraints in the Standard Form Definition Given LP, a constraint is active at x if, replacing x in the system, the LHS of the constraint is equal to its RHS. For the generic i-th constraint aiTx ≥ bi : aiTx = bi si = aiTx – bi = 0 aiTx – si = bi Original constr. Corresponding slack SF constr. (always) active in x active in x (si null) Slack non-negativity constr. active si = 0 aiTx > bi si = aiTx – bi > 0 aiTx – si = bi Original constr. Corresponding slack SF constr. (always) active in x not active in x (si positive) Slack non-negativity constr. non active si > 0 PROPERTY If the LP is in SF, active constraints at a given x can be detected by looking directly at the sign of the corresponding slack. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Active constraints in the Standard Form Definition Given LP, a constraint is active at x if, replacing x in the system, the LHS of the constraint is equal to its RHS. For the generic i-th constraint aiTx ≥ bi : aiTx = bi aiTx – si = bi Original constr. SF constr. (always) active in x active in x Slack non-negativity constr. active si = 0 aiTx > bi aiTx – si = bi Original constr. SF constr. (always) active in x not active in x Slack non-negativity constr. non active si > 0 PROPERTY If the LP is in SF, active constraints at a given x can be detected by looking directly at the sign of the corresponding slack. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Advantages of SF ADVANTAGE When a LP is trasformed in SF no inequality is eliminated, rather: S each inequality (structural constraint) is converted into an equivalent equality (with s ≥ 0). information contained in the i-th constraint (active/not active in x) is transferred into the non negativty constraint of the i-th slack si (null/positive in (x,s)). non negativity of the i-th i-th structural constraint SF TRANSFERS slack (si=0/si>0) INFORMATION active/non active in x active/non active non negativity constraint in (x,s) FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA Standard Form (General Case)  Standard Form (SF) Recall that the SF involves only the linear system of constraints: it does not affect the objective function. In a LP in SF the o.f. maintains its original form (max/min). In fact, each new added slack variable has a null coefficinet in the o.f. NOTE the number of structural constraints is the same (m), while the number of non-negativity constraints increases (n+m). LP: Reference form and Standard Form min Σj cj xj min Σj cj xj Σj aij xj ≥ bi i=1,2,...,m Σj aij xj – si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m max Σj cj xj max Σj cj xj Σj aij xj ≤ bi i=1,2,...,m Σj aij xj + si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Standard Form (SF) Transforming the LP in SF “simpifies the model” since one has: inequalities only for non negativity constraints and all model variables are non negative; equalities for all structural constraints (always active constraints) and we know whether the i-th constraint of the original LP was active or not at (x,s) directly from the sign of si in (x,s). LP: Reference form and Standard Form min Σj cj xj min Σj cj xj Σj aij xj ≥ bi i=1,2,...,m Σj aij xj – si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m max Σj cj xj max Σj cj xj Σj aij xj ≤ bi i=1,2,...,m Σj aij xj + si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Example Colorants Production Problem max 7 x1 + 10 x 2 max cx When the LP is in this particular form, x1 + x 2  750 with positive RHS, it is ‘easy’ to find a x1 + 2 x 2  1000 feasible solution. Ax ≤ b x 2  400 x1 , x 2  0 x≥0 The SF is obtained by adding a non negative slack to the LHS of each structural constraint (each inequality ≤ of the original model becomes an equality =). max Σj cj xj max Σj cj xj Σj aij xj ≤ bi i=1,2,...,m Σj aij xj + si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Example Colorants Production Problem Standard Form max 7 x1 + 10 x 2 max 7 x1 + 10 x 2 x1 + x 2  750 x1 + x 2 + s1 = 750 x1 + 2 x 2  1000 x1 + 2 x 2 + s2 = 1000 x 2  400 x 2 + s3 = 400 x1 , x 2  0 x1 , x 2  0 s1 , s2 , s3  0 The SF is obtained by adding a non negative slack to the LHS of each structural constraint (each inequality ≤ of the original model becomes an equality =). max Σj cj xj max Σj cj xj Σj aij xj ≤ bi i=1,2,...,m Σj aij xj + si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Example Colorants Production Problem Standard Form max 7 x1 + 10 x 2 max 7 x1 + 10 x 2 x1 + x 2  750 x1 + x 2 + s1 = 750 x1 + 2 x 2  1000 x1 + 2 x 2 + s2 = 1000 x 2  400 x 2 + s3 = 400 x1 , x 2  0 x1 , x 2  0 s1 , s2 , s3  0 We can easily find a feasible solution by setting x=0, so that the slacks’ values s ≥ 0 are automatically given by the RHS of the system. We obtain the solution s1=750, s2=1000, s3= 400 x1= x2= 0 easy to find is feasible (it satisfies all the constraints) feasible not optimal but ‘trivial’, since all decision variables are set to 0 NOTE: slack variables are technically introduced to obtain equalities for the SF, but they have also an precise meaning in the decision context. In the production problem, they measure the excess of resource (which was not used in the production process). FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Standard Form (SF) Transforming the LP in SF “simplyfies the model” since one has: inequalities only for non negativity constraints and all model variables are non negative; equalities for all structural constraints (always active constraints) and we know whether the i-th constraint of the original LP was active or not at (x,s) directly from the sign of si in (x,s). LP: Reference form and Standard Form min Σj cj xj min Σj cj xj Σj aij xj ≥ bi i=1,2,...,m Σj aij xj – si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m max Σj cj xj max Σj cj xj Σj aij xj ≤ bi i=1,2,...,m Σj aij xj + si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Examples Blending Model (juice) min 400 x1 + 600 x 2 min cx 140 x1  70 20 x1 + 10 x 2  30 Ax ≥ b 25 x1 + 50 x 2  75 x1 , x 2  0 x≥0 The SF is obtained by subtracting a non negative slack to the LHS of each structural constraint (each inequality ≥ of the original model becomes an equality =). min Σj cj xj min Σj cj xj Σj aij xj ≥ bi i=1,2,...,m Σj aij xj – si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Examples Blending Model (juice) Standard Form min 400 x1 + 600 x 2 min 400 x1 + 600 x 2 140 x1 − s1 = 70 140 x1  70 20 x1 + 10 x 2 − s2 = 30 20 x1 + 10 x 2  30 25 x1 + 50 x 2 − s3 = 75 25 x1 + 50 x 2  75 x1 , x 2  0 x1 , x 2  0 s1 , s2 , s3  0 The SF is obtained by subtracting a non negative slack to the LHS of each structural constraint (each inequality ≥ of the original model becomes an equality =). min Σj cj xj min Σj cj xj Σj aij xj ≥ bi i=1,2,...,m Σj aij xj – si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Examples Blending Model (juice) Standard Form min 400 x1 + 600 x 2 min 400 x1 + 600 x 2 140 x1 − s1 = 70 140 x1  70 20 x1 + 10 x 2 − s2 = 30 20 x1 + 10 x 2  30 25 x1 + 50 x 2 − s3 = 75 25 x1 + 50 x 2  75 x1 , x 2  0 x1 , x 2  0 s1 , s2 , s3  0 The slack variables have a specific meaning related to the blending model, since they measure the excess of each element in the blend w.r.t. the minimum required need. What happens in this model if we fix to 0 the decision variables? We have non feasible values for s1= -70, s2= -30, s3= -75 x 1= x 2= 0 the slack variables (negative) When the problem is in the Reference form (2), we cannot find a feasible solution by fixing to 0 the decision variables. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA Matrix Standard Form  Matrix Standard Form: min For a minimization problem: min Σj cj xj min Σj cj xj Σj aij xj ≥ bi i=1,2,...,m Σj aij xj – si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m Matrix form Identity matrix of order m min cnTxn min cnTxn Amxnxn ≥ bm Amxnxn – Imxm sm = bm xn ≥ 0 xn ≥ 0 sm ≥ 0 Every inequality i has its dedicated slack variable si, therefore, in every constraint of the SF system, we have only the slack of that contraint (the others have coefficient 0). Identity Matrix We have only s1 in the 1-st constraint, only s2 in the 2-nd constraint,…, only sm in the m-th constraint. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Matrix Standard Form: max For a maximization problem: max Σj cj xj max Σj cj xj Σj aij xj ≤ bi i=1,2,...,m Σj aij xj + si = bi i=1,2,...,m xj ≥ 0 j=1,2,...,n xj ≥ 0 j=1,2,...,n si ≥ 0 i=1,2,...,m Matrix form Identity matrix of order m max cnTxn max cnTxn Amxnxn ≤ bm Amxnxn + Imxm sm = bm xn ≥ 0 xn ≥ 0 sm ≥ 0 Every inequality i has its dedicated slack variable si, therefore, in every constraint of the SF system, we have only the slack of that contraint (the others have coefficient 0). Identity Matrix We have s1 in the 1-st constraint only, s2 in the 2-nd constraint only,…, sm in the m-th constraint only. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA Sign-free variables and SF  Sign-free variables In a LP in arbitrary form some variables may be sign-free, i.e., they can assume any real value, positive, negative, or null. Definition We define free variable a variable not subjected to a non negativity constraint. PROPOSITION In a LP a free variable can be always replaced by a pair of non negative variables. If variable xj is free, then we can represent all its possible values by the pair of non negative variabes yj, zj related to xj as follows: xj = yj - zj In fact, we have: xj > 0 yj > zj xj < 0 yj < zj xj = 0 yj = zj FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Sign-free variables Example min 2x1 – 5x2 Consider the LP in arbitrary form x1 + 2x2 ≤ 5 where variable x2 is free: 4x1 – 3x2 = – 6 x1 – x2 ≥ 1 x1 ≥ 0 x2 free The equivalent model in SF is: min 2x1 – 5y2 + 5z2 x1 + 2y2 – 2z2 + s1 = 5 x2 = y2 – z2 4x1 – 3y2 + 3z2 =–6 x1 – y2 + z2 – s3 = 1 1 variable 2 variables x1 ≥ 0, y2 ≥ 0, z2 ≥ 0, s1 ≥ 0, s3 ≥ 0 This is a change of variables, x2 = y2 – z2, aimed at obtaining an equivalent LP where all variables are non negative, as required by the Standard Form. The transformation is equivalent, but it can be done at the ‘cost’ of introducing one more variable in the model. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  Sign-free variables NOTE The SF refers only to the form of the linear system of constraints: it does not affect the objective function. In fact, in a LP in SF the objective function mantains its original form: replacing a free variable xj by the difference yj - zj does not alter the o.f. each slack variable has null coefficient in the o.f. Proposition Arbitrary LP Every LP can be re-written as an equivalent LP in Standard Form. Equivalent FS NOTE The ‘cost’ of this operation is that the number of variables in the model increases, as well as the number of non negativity constraints. FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA Exercises  EXERCISES Transform into SF the system of constraints of the following models. For each model count the total number of variables (decision and slack) of the model in SF. Exercise VIII - 1 Exercise VIII - 2 max x1 - 4x2 max x1 + x2 - 2x3 x1 + 3x3 ≤ 10 x1 ≤ 2x2 2x1 – x2 ≥ 7 x1 + x2 ≥ 2 x2 + x3 ≤ 5 x1, x2 ≥ 0 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Exercise VIII - 3 Exercise VIII - 4 max 2x1 + x2 min x1 + x2 4x1 – 5x2 ≤ 2 2x1 + 3x2 ≥ -2 x1 – x2 + x3 – x4 ≤ 0 x1 – 2x2 + 4x3 = 0 x1, x2, x3, ≥ 0 x4 sign-free x1, x2, x3 ≥ 0 FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA  EXERCISES Exercise VIII - 5 Transform into SF the system of constraints of the GTC production problem (Lect. 4). FINANCIAL OPTIMIZATION AND ASSET MANAGEMENT – FEDERICA RICCA