Sample Solution manual of Introduction to Linear Optimization and Extensions with MATLAB by Roy H. Kwon pdf PDF

Preview

Summary

Authors: Roy H. Kwon
Published: CRC Press 2013
Edition: 1st
Pages: 219
Type: pdf , include slides
Size: 7MB
Download After Payment...

Description

gioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-

FOLFNKHUHWRGRZQORDG

SOLUTIONS MANUAL FOR INTRODUCTION TO LINEAR OPTIMIZATION AND EXTENSIONS WITH MATLAB® by

Roy H. Kwon

gioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-

FOLFNKHUHWRGRZQORDG

gioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-

FOLFNKHUHWRGRZQORDG

SOLUTIONS MANUAL FOR INTRODUCTION TO LINEAR OPTIMIZATION AND EXTENSIONS WITH MATLAB® by

Roy H. Kwon

Boca Raton London New York

CRC Press is an imprint of the Taylor & Francis Group, an informa business

gioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-

FOLFNKHUHWRGRZQORDG

CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2014 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed on acid-free paper Version Date: 20130808 International Standard Book Number-13: 978-1-4822-0121-5 (Ancillary) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com

ioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-s

FOLFNKHUHWRGRZQORDG

Chapter 1 ……………………………………………………………………………………………………………………………….2 Chapter 2 …………………………………………………………………………………………………………………………..…25 Chapter 3 ……………………………………………………………………………………………………………………..………42 Chapter 4 ……………………………………………………………………………………………………………………………102 Chapter 5 ………………………………………………………………………………………………………………………..….125 Chapter 6 ……………………………………………………………………………………………………………………..…….162 Chapter 7 ……………………………………………………………………………………………………………………………185 Chapter 8 ……………………………………………………………………………………………………………………………202

1

ioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-s

FOLFNKHUHWRGRZQORDG

Chapter 1

Exercise 1.1 Solution: Let x3 = x3+ - x3-, x3+ ≥ 0, x3- ≥ 0, then translate into standard form + minimize -2x1 + 4x2 + 3x3 - 3x3 + - x1 - x2 + 2x3 - 2x3 + s1 = -1 x2 + x3+ - x3- + s2 = 1 + x1 + x2 + x3 - x3 + s3 = 4 -x1 - x2 - x3+ + x3- + s4 = -4 + x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x3 ≥ 0, s1 ≥ 0, s2 ≥ 0, s3 ≥ 0, s4 ≥ 0 therefore, c = [-2 4 3 -3 0 0 0 0 ]T, x = [x1, x2, x3+, x3-, s1, s2, s3, s4]T,

subject to

.

Exercise 1.2 Solution: Let z = |x2|, the problem becomes following LP: minimize 2x1 + 3z subject to

x1 + x2 ≥ 6 z ≥ x2 z ≥ -x2

Exercise 1.3 Solution: The problem becomes following LP: minimize 2x1 + 2x3 subject to 5x1 + 3x3 ≤ 5 x1 ≥ 0, x3 ≥ 0

Exercise 1.4 Solution: (a) The problem is equivalent to maximize z i i i = 1, …, n subject to z ≤ c0 + c x Ax1 = b (b) The problem is to maximize worst cast profit.

2

ioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-s

Exercise 1.5

FOLFNKHUHWRGRZQORDG

Sketch each feasible set F below and state whether it is bounded, unbounded, or empty. (a) x1 + x2 ≤ 6 4x1 - 2x2 ≤ 12 x1 ≤2 (b) 2x1 + 6x2 ≤ 22 x1 - x2 ≤ 5 x1 ≥ 0, x2 ≥ 0 (c)

x1 + x2 ≤ 4 x1 + 2x2 ≥ 12 x1 ≥ 0

Solution: (a) F is unbounded

(b) F is bounded

3

ioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-s

FOLFNKHUHWRGRZQORDG

(c) F is empty

Exercise 1.6 Solution: (a) Let P = feasible set of a LP. P bounded means there exists M > 0 such that ||x|| ≤ M for all x∈P. Now ||cTx|| ≤ ||c||*||x|| ≤ ||c||M for all x∈P. 4

ioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-s

FOLFNKHUHWRGRZQORDG (b) Consider minimize x1 + x2 subject to x1 ≥ 0, x2 ≥ 0 Then x = [0 0]T is optimal, but P is unbounded.

Exercise 1.7 Consider the LP minimize 2x1 + x2 subject to

x2 ≥ 2

x1 - 3x2 ≤ 5 Determine if the LP is unbounded or not. If it is, specify a sequence of vectors x(k) such that the objective function → -∞ as k → ∞. Solution: the LP is unbounded since the feasible set F is unbounded as follows:

It is easy to find vectors x(k) = [11 - k , 2]T, the objective value is (24 -2k) → -∞ as k → ∞.

Exercise 1.8 Suppose that there are 4 different projects and 4 workers and each worker must be assigned a project and each project must be assigned a worker. It costs $20 an hour for a worker. The following table gives the time required (in hours) for each worker i to complete a particular project j 5

ioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-s

project 1 project 2 project 3 FOLFNKHUHWRGRZQORDG

project 4

worker 1

7

3

6

10

worker 2

5

4

9

9

worker 3

6

4

7

10

worker 4

5

5

6

8

(a) Formulate this problem of assigning workers and jobs at minimum cost as a linear program. (b) Solve the model in (a) using MATLAB linprog function. If you get a fraction solution optimal solution then find a feasible integer solution (i.e. all variables are 0 or 1) with same optimal objective value. For this type of model, this will always be possible. Solution: set xij = project j is assigned to worker i, then min

s.t.

(b) Solve the model by following MATLAB code: %% Exercise 1.8 I=4; % number of workers J=4; % number of projects time_req = [7 3 6 10; 5 4 9 9; 6 4 7 10; 5 5 6 8;]; wage = 20; % the wages is $20/hr c = reshape(time_req, [], 1);% cost coefficient c Aeq_j = []; % the constraint coefficient about project j for j = 1:J 6

ioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-s

Aeq_j = blkdiag(Aeq_j, ones(1,J)); FOLFNKHUHWRGRZQORDG end Aeq_i = [];% the constraint coefficient about worker i for i = 1:I Aeq_i = cat(2, Aeq_i, eye(I)); end Aeq = [Aeq_j; Aeq_i]; beq = ones(I+J,1); lb = zeros(I*J,1); [x_assign, f_assign] = linprog(c, [],[], Aeq,beq, lb, []); x_assign = reshape(x_assign, I, J);% coincide with time_req matrix min_cost = wage*f_assign; % note that we want the min cost

Worker 1 Worker 2 Worker 3 Worker 4

Project 1

Project 2

Project 3

Project 4

1.87E-15 1 2.32E-14 7.59E-15

0.558046 3.54E-15 0.441954 1.56E-15

0.441954 7.82E-16 0.558046 2.50E-14

2.15E-15 2.90E-14 3.26E-15 1

Minimum cost

$460

If we using the following plan, we can also get the same objective value: Worker 1 Worker 2 Worker 3 Worker 4

Project 1

Project 2

Project 3

Project 4

0 1 0 0

1 0 0 0

0 0 1 0

0 0 0 1

Minimum cost

$460

Exercise 1.9 The Ontario Steel Company ONASCO needs to produce a new type of steel that will be created from a mixture of various types of iron, alloy, and steel. The new type of steel should have a chrome content of at least 1% but no more than 1.25% and should have a silicon content of at least 3% but no more than 4%. ONASCO has the following materials for creating the new type of steel Amount Available

Cost

Chrome

Silicon

% per lb

% per lb

Iron A

1500 lbs

$.05/lb

0.01

1.75

Iron B

900 lbs

$.07/lb

7.00

17.00

Steel A

150 lbs

$.02/lb

0.00

0.00

Steel B

200 lbs

$.025/lb

0.00

0.00

Alloy A

800 lbs

$.10/lb

0.00

22.00

Alloy B

700 lbs

$.12/lb

0.00

31.00

ONASCO would like to make 1500 tons of the new type of steel at minimum cost. 7

ioumeh.com/product/introduction-to-linear-optimization-and-extensions-with-matlab-s

(a) Formulate this problem as a linear program. FOLFNKHUHWRGRZQORDG (b) Solve the model in (a) using MATLAB Solution: ONASCO needs 1500 tons or 3,000,000 pounds of new steel. Let xA = amount (lbs) of Iron A used in the new steel, xB = amount (lbs) of Iron B used in the new steel, yA = amount (lbs) of Steel A used in the new steel, yB = amount (lbs) of Steel B used in the new steel, zA = amount (lbs) of Alloy A used in the new steel, zB = amount (lbs) of Alloy B in the new steel. The new steel should contain at least 3000000*1% = 30000 pounds of Chrome and at most 3000000*1.25% = 37500 pounds of Chrome, and at least 3000000*3% = 90000 pounds of Silicon and at most 3000000*4% = 120000 pounds of Silicon. Then, we can formulate the LP as: minimize

0.05xA + 0.07xB + 0.02yA + 0.025yB + 0.10zA + 0.12zB

subject to

30000 ≤ 1%xA + 7%xB + 0.00yA + 0.00yB + 0.00zA + 0.00zB ≤ 37500 90000 ≤ 1.75%xA + 17%xB + 0.00yA + 0.00yB + 22%zA + 31%zB ≤ 120000 xA + xB + yA + yB + zA + zB = 3,000,000 xA ≥ 0, xB ≥ 0, yA ≥ 0, yB ≥ 0, zA ≥ 0, zB ≥ 0

(b) We can get the minimum total cost of the 1500 tons of new product by following MATLAB code: %% Exercise 1.9 total_product=3000000;%1500 tons = how many pounds c = [.05; .07; .02; .025; .10; .12;]; cons1 = [0.01 7.00 0.00 0.00 0.00 0.00]; cons2 = [1.75 17.00 0.00 0.00 22.00 31.00]; A = [-cons1; cons1; -cons2; cons2;]; b = total_product/100*... [-1; 1.25; -3; 4;]; Aeq = [1 1 1 1 1 1;]; beq = total_product; lb = [0; 0; 0; 0; 0; 0;]; ub = []; [x_Steel, f_Steel] = linprog(c, A,b, Aeq,beq, lb,ub);

Amount Minimum total cost

xA

xB

yA

yB

zA

zB

4.86E-06

5294.1041

2994705.9

0.0005203

0.0099224

0.0007709

60264.706

8...