becomes z = 6, 000, 000. Increasing the amount of rubber in stock beyond 600, without also increasing the amount of steel in stock, no longer affects the optimal solution because x is constrained to remain positive.
1.11.3. Dual problem of the competitor
Suppose now that the automobile manufacturer has a competitor who offers to repurchase all raw materials in stock to fulfill a large number of orders. The competitor must offer a certain price (assumed to be constant and denoted u) per unit of rubber and another price (denoted v) per unit of steel. For the offer to be accepted, the price paid by the competitor must at least be equal to the turnover that the manufacturer could achieve by manufacturing automobiles itself. The competitor’s problem can therefore be written as
[1.24]
Graphical analysis finds the optimal solution u = 4, 000 and v = 6, 000, which corresponds to a global price of p = 5, 200, 000. Observe (and we will see later that this is no coincidence) that the optimal solution of the competitor’s problem (the dual problem to the manufacturer’s primal problem) coincides with the marginal prices of the manufacturer’s problem, and the minimum price that the competitor can offer is equal to the manufacturer’s maximum turnover.
1.12. Using Matlab
Matlab offers the linprog solver for optimizing LPs. The linprog solver takes the following input arguments:
– f: the objective function;
– A: the matrix of inequality constraints;
– b: the right-hand side of the inequality constraints;
– Aeq: the matrix of equality constraints;
– beq: the right-hand side of the equality constraints;
– lb: the vector of lower bounds of the decision variables;
– ub: the vector of upper bounds of the decision variables;
– x0: the starting point of x, only used for the active-set algorithm;
– options : options created with “optimoptions”.
All linprog arguments use the following options, defined via the “optimoptions” input:
– Algorithm: the following algorithms can be used:1) “interior-point” (default);2) “dual-simplex”;3) “active-set”;4) “simplex”.
– LargeScale: the “interior-point” algorithm is used when this option is set to “on” (default) and the primal simplex algorithm is used when it is set to “off”.
– TolCon: the feasibility tolerance for constraints. The default value is 1e-4. It takes scalar values from 1e-10 to 1e-3 (only available for the dual simplex algorithm).
The output arguments of the linprog solver are as follows:
– fval: the value of the objective function at the solution x;
– x: the solution found by the solver. If exitflag > 0, then x is a solution; if not, x is the value of the variables when the solver terminated prematurely;
– exitflag: the reason why the algorithm terminated:- 1: the solver converged to the solution x;- 0: the number of iterations exceeded the “MaxIter option”;- 2: no feasible point was found;- 3: the LP problem is not bounded;- 4: a NaN value was encountered when executing the algorithm;- 5: the primal and dual problems are infeasible;- 7: the search direction became too small and no other progress was observed.
The following list specifies the various syntaxes that can be used to call the linprog solver:
– x = linprog(f, A, b): solves min fT x such that Ax ≤ b (used when there are only equality constraints);
– x = linprog(f, A, b, Aeq, beq): solves the problem with the equality constraints Aeqx = beq. Set A=[ ] and b=[ ] if no inequalities exist;
– 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 always in the range lb ≤ x ≤ ub. Set Aeq=[ ] and beq=[ ] if no equalities exist;
– x = linprog(f, A, b, Aeq, beq, lb, ub, x0): defines the starting point at x0 (only used for the active-set algorithm);
– x = linprog(f, A, b, Aeq, beq, lb, ub, x0, options): minimizes with the specified options;
– [x, fval] = linprog(...): returns the value of the objective function at the solution x;
– [x, fval, exitflag] = linprog(...): returns a value exitflag that describes the exit condition;
– [x, fval, exitflag, output] = linprog(...): returns a structure output that contains information about the optimization process;
– [x, fval, exitflag, output, lambda] = linprog(...): returns a structure output whose fields contain the Lagrange multipliers λ at the solution x.
EXAMPLE 1.14.– Consider the linear program:
[1.25]
The following code can be executed to compute this example.
1 1 variables = {'x1', 'x2', 'x3', 'x4', 'x5'}; % construct the vector x
2 2 n = length(variables);
3 3 for i = 1:n % create the indices of x
4 4 eval([variables{i}, ' = ', num2str(i), ';']);
5 5 end
6 6 lb = zeros(1, n);
7 7 lb([x1, x2]) = [5, 1]; % add the bounds of the variables x1,x2
8 8 ub = Inf(1, n);
9 9 A = zeros(3, n); % create the matrix A
10 10 b = zeros(3, 1); % create the vector b
11 11 % define the constraints
12 12 A(1, [x1, x2, x3, x4]) = [1, 4, -2, -1]; b(1) = 8;
13 13 A(2, [x1, x2, x3, x4]) = [1, 3, 2, -1]; b(2) = 10;
14 14 A(3, [x1, x2, x3, x4, x5]) = [2, 1, 2, 3, -1]; b(3) = 20;
15 15 Aeq = zeros(1, n); % create the matrix Aeq
16 16 beq = zeros(1, 1); % create the vector beq
17 17 % define the equality constraints
18 18 Aeq(1, [x1, x2, x3, x4, x5]) = [1, 3, -4, -1, 1]; beq(1) = 7;
19 19
