Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 44

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 c = zeros(n, 1); % create the vector c

20 20 c([x1 x2 x3 x4 x5]) = [-2; -3; 1; 4; 1];

21 21 % call linprog solver

22 22 [x, objVal] = linprog(c, A, b, Aeq, beq, lb, ub);

23 23 for i = 1:n

24 24 fprintf('%s \t %20.4f\n', variables{i}, x(i))

25 25 end

26 26 fprintf(['The value of the objective function is' '%20.4f\n'],

27 27 objVal)

For a color version of this code, see www.iste.co.uk/radi/optimizations.zip

Executing this code produces the following results: