Matlab Linear Programming - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Matlab Linear Programming. Доклад-сообщение содержит 65 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

MATLAB Linear Programming

Слайд 2

Описание слайда:

MATLAB Linear Programming

Слайд 3

Описание слайда:

Optimization Optimization - finding value of a parameter that maximizes or minimizes a function with that parameter Talking about mathematical optimization, not optimization of computer code! "function" is mathematical function, not MATLAB language function

Слайд 4

Описание слайда:

Optimization Optimization Can have multiple parameters Can have multiple functions Parameters can appear linearly or nonlinearly

Слайд 5

Описание слайда:

Linear programming Linear programming Most often used kind of optimization Tremendous number of practical applications "Programming" means determining feasible programs (plans, schedules, allocations) that are optimal with respect to a certain criterion and that obey certain constraints

Слайд 6

Описание слайда:

Linear programming A feasible program is a solution to a linear programming problem and that satisfies certain constraints In linear programming Constraints are linear inequalities Criterion is a linear expression Expression called the objective function In practice, objective function is often the cost of or profit from some activity

Слайд 7

Описание слайда:

Linear programming Many important problems in economics and management can be solved by linear programming Some problems are so common that they're given special names

Слайд 8

Описание слайда:

Linear programming DIET PROBLEM You are given a group of foods, their nutritional values and costs. You know how much nutrition a person needs. What combination of foods can you serve that meets the nutritional needs of a person but costs the least?

Слайд 9

Описание слайда:

Linear programming BLENDING PROBLEM Closely relate to diet problem Given quantities and qualities of available oils, what is cheapest way to blend them into needed assortment of fuels?

Слайд 10

Описание слайда:

Linear programming TRANSPORTATION PROBLEM You are given a group of ports or supply centers of a certain commodity and another group of destinations or markets to which commodity must be shipped. You know how much commodity at each port, how much each market must receive, cost to ship between any port and market. How much should you ship from each port to each market so as to minimize the total shipping cost?

Слайд 11

Описание слайда:

Linear programming WAREHOUSE PROBLEM You are given a warehouse of known capacity and initial stock size. Know purchase and selling price of stock. Interested in transactions over a certain time, e.g., year. Divide time into smaller periods, e.g., months. How much should you buy and sell each period to maximize your profit, subject to restrictions that Amount of stock at any time can't exceed warehouse capacity You can't sell more stock than you have

Слайд 12

Описание слайда:

Linear programming Mathematical formulation The variables x1, x2, ... xn satisfy the inequalities and x1 ≥0, x2 ≥0, ... xn ≥0 . Find the set of values of x1, x2, ... xn that minimizes (maximizes) Note that apq and fi are known

Слайд 13

Описание слайда:

Linear programming Mathematical matrix formulation Find the value of x that minimizes (maximizes) fTx given that x ≥ 0 and Ax ≤ b, where

Слайд 14

Описание слайда:

Linear programming General procedure Restate problem in terms of equations and inequalities Rewrite in matrix and vector notation Call MATLAB function linprog to solve

Слайд 15

Описание слайда:

Linear programming Example - diet problem My son's diet comes from the four basic food groups - chocolate dessert, ice cream, soda, and cheesecake. He checks in a store and finds one of each kind of food, namely, a brownie, chocolate ice cream, Pepsi, and one slice of pineapple cheesecake. Each day he needs at least 500 calories, 6 oz of chocolate, 10 oz of sugar, and 8 oz of fat. Using the table on the next slide that gives the cost and nutrition of each item, figure out how much he should buy and eat of each of the four items he found in the store so that he gets enough nutrition but spends as little (of my money...) as possible.

Слайд 16

Описание слайда:

Linear programming Example - diet problem

Слайд 17

Описание слайда:

Linear programming Example - diet problem What are unknowns? x1 = number of brownies to eat each day x2 = number of scoops of chocolate ice cream to eat each day x3 = number of bottles of Coke to drink each day x4 = number of pineapple cheesecake slices to eat each day In linear programming "unknowns" are called decision variables

Слайд 18

Описание слайда:

Linear programming Example - diet problem Objective is to minimize cost of food. Total daily cost is Cost = (Cost of brownies) + (Cost of ice cream) + (Cost of Coke) + (Cost of cheesecake) Cost of brownies = (Cost/brownie) × (brownies/day) = 2.5x1 Cost of ice cream = x2 Cost of Coke = 1.5x3 Cost of cheesecake = 4x4

Слайд 19

Описание слайда:

Linear programming Example - diet problem Therefore, need to minimize

Слайд 20

Описание слайда:

Linear programming Example - diet problem Constraint 1 - calorie intake at least 500 Calories from brownies = (calories/brownie)(brownies/day) = 400x1 Calories from ice cream = 200x2 Calories from Coke = 150x3 Calories from cheesecake = 500x4 So constraint 1 is

Слайд 21

Описание слайда:

Linear programming Example - diet problem Constraint 2 - chocolate intake at least 6 oz Chocolate from brownies = (Chocolate/brownie)(brownies/day) = 3x1 Chocolate from ice cream = 2x2 Chocolate from Coke = 0x3 = 0 Chocolate from cheesecake = 0x4 = 0 So constraint 2 is

Слайд 22

Описание слайда:

Linear programming Example - diet problem Constraint 3 - sugar intake at least 10 oz Sugar from brownies = (sugar/brownie)(brownies/day) = 2x1 Sugar from ice cream = 2x2 Sugar from Coke = 4x3 Sugar from cheesecake = 4x4 So constraint 3 is

Слайд 23

Описание слайда:

Linear programming Example - diet problem Constraint 4 - fat intake at least 8 oz Fat from brownies = (fat/brownie)(brownies/day) = 2x1 Fat from ice cream = 4x2 Fat from Coke = 1x3 Fat from cheesecake = 5x4 So constraint 4 is

Слайд 24

Описание слайда:

Linear programming Example - diet problem Finally, we assume that the amounts eaten are non-negative, i.e., we ignore throwing up. This means that we have x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, and x4 ≥ 0

Слайд 25

Описание слайда:

Linear programming Example - diet problem Putting it all together, we have to minimize subject to the constraints and

Слайд 26

Описание слайда:

Linear programming Example - diet problem In matrix notation, want to where

Слайд 27

Описание слайда:

Linear programming MATLAB solves linear programming problem where x, b, beq, lb, and ub are vectors and A and Aeq are matrices. Can use one or more of the constraints "lb" means "lower bound", "ub" means "upper bound" Often have lb = 0 and ub = ∞, i.e., no upper bound

Слайд 28

Описание слайда:

Linear programming MATLAB linear programming solver is linprog(), which you can call various ways: x = linprog(f,A,b) x = linprog(f,A,b,Aeq,beq) x = linprog(f,A,b,Aeq,beq,lb,ub) x = linprog(f,A,b,Aeq,beq,lb,ub,x0) x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) x = linprog(problem) [x,fval] = linprog(...) [x,fval,exitflag] = linprog(...) [x,fval,exitflag,output] = linprog(...) [x,fval,exitflag,output,lambda] = linprog(...)

Слайд 29

Описание слайда:

Linear programming Example - diet problem Us: MATLAB: Note two differences:

Слайд 30

Описание слайда:

Linear programming Example - diet problem ISSUE 1 - We have Ax ≥ b but need Ax ≤ b One way to handle is to note that if Ax ≥ b then -Ax ≤ -b, so can have MATLAB use constraint (-A)x ≤ (-b) ISSUE 2 - We have 0 ≤ x but MATLAB wants lb ≤ x ≤ ub . Handle by omitting ub in call of linprog(). If omitted, MATLAB assumes no upper bound

Слайд 31

Описание слайда:

Linear programming Example - diet problem x = linprog(f,A,b,Aeq,beq,lb,ub) We'll actually call x = linprog(f,A,b,Aeq,beq,lb) If don't have equality constraints, pass [] for Aeq and beq

Слайд 32

Описание слайда:

Linear programming Example - diet problem Follow along now >> A = -[ 400 200 150 500; 3 2 0 0; 2 2 4 4;... 2 4 1 5 ]; >> b = -[ 500 6 10 8 ]'; >> f = [ 2.5 1 1.5 4]'; >> lb = [ 0 0 0 0 ]'; >> x = linprog( f, A, b, [], [], lb ) Optimization terminated. x = 0.0000 % brownies 3.0000 % chocolate ice cream 1.0000 % Coke 0.0000 % cheesecake

Слайд 33

Описание слайда:

Linear programming Example - diet problem Optimal solution is x = [ 0 3 1 0 ]T . In words, my son should eat 3 scoops of ice cream and drink 1 Coke each day.

Слайд 34

Описание слайда:

Linear programming Example - diet problem A constraint is binding if both sides of the constraint inequality are equal when the optimal solution is substituted. For x = [ 0 3 1 0 ]T the set becomes , so the chocolate and sugar constraints are binding. The other two are nonbinding

Слайд 35

Описание слайда:

Linear programming Example - diet problem How many calories, and how much chocolate, sugar and fat will he get each day? >> -A*x ans = 750.0000 % calories 6.0000 % chocolate 10.0000 % sugar 13.0000 % fat How much money will this cost? >> f'*x ans = 4.5000 % dollars

Слайд 36

Описание слайда:

Linear programming Example - diet problem Because it's common to want to know the value of the objective function at the optimum, linprog() can return that to you [x fval] = linprog(f,A,b,Aeq,beq,lb,ub) where fval = fTx >> [x fval] = linprog( f, A, b, [], [], lb ) x = 0.0000 3.0000 1.0000 0.0000 fval = 4.5000

Слайд 37

Описание слайда:

Linear programming Special kinds of solutions Usually a linear programming problem has a unique (single) optimal solution. However, there can also be: No feasible solutions An unbounded solution. There are solutions that make the objective function arbitrarily large (max problem) or arbitrarily small (min problem) An infinite number of optimal solutions. The technique of goal programming is often used to choose among alternative optimal solutions. (Won't consider this case more)

Слайд 38

Описание слайда:

Linear programming Can tell about the solution MATLAB finds by using third output variable: [x fval exitflag] =... linprog(f,A,b,Aeq,beq,lb,ub) exitflag - integer identifying the reason the algorithm terminated. Values are 1 Function converged to a solution x. 0 Number of iterations exceeded options. -2 No feasible point was found. -3 Problem is unbounded. -4 NaN value was encountered during execution of the algorithm. -5 Both primal and dual problems are infeasible. -7 Search direction became too small. No further progress could be made.

Слайд 39

Описание слайда:

Linear programming Try It Solve the following problem and display the optimal solution, the value of the objective value there, and the exit flag from linprog() Maximize z = 2x1 - x2 subject to

Слайд 40

Описание слайда:

Linear programming Try It First multiply second equation by -1 to get Then, with objective function z = 2x1 - x2 rewrite in matrix form:

Слайд 41

Описание слайда:

Linear programming Try It >> A = [ 1 -1; -2 -1 ]; >> b = [ 1 -6 ]'; >> f = [ 2 -1 ]'; >> lb = [ 0 0 ]';

Слайд 42

Описание слайда:

Linear programming Try It IMPORTANT - linprog() tries to minimize the objective function. If you want to maximize the objective function, pass -f and use -fval as the maximum value of the objective function

Слайд 43

Описание слайда:

Linear programming Try It >> [x fval exitflag] = linprog( -f, A, b, [],[], lb ) Exiting: One or more of the residuals, duality gap, or total relative error has grown 100000 times greater than its minimum value so far: the dual appears to be infeasible (and the primal unbounded). (The primal residual < TolFun=1.00e-008.) x = 1.0e+061 * 4.4649 4.4649 fval = -4.4649e+061 (-fval = 4.4649e+061 !!!) exitflag = -3 (Problem is unbounded)

Слайд 44

Описание слайда:

Linear programming Try It A farmer has 10 acres to plant in wheat and rye. He has to plant at least 7 acres. However, he has only $1200 to spend and each acre of wheat costs $200 to plant and each acre of rye costs $100 to plant. Moreover, the farmer has to get the planting done in 12 hours and it takes an hour to plant an acre of wheat and 2 hours to plant an acre of rye. If the profit is $500 per acre of wheat and $300 per acre of rye how many acres of each should be planted to maximize profits?

Слайд 45

Описание слайда:

Linear programming Try It Decision variables x is number of acres of wheat to plant y is number of acres of rye to plant Constraints "has 10 acres to plant in wheat and rye" In math this is " has to plant at least 7 acres" In math this is

Слайд 46

Описание слайда:

Linear programming Try It Constraints "he has only $1200 to spend and each acre of wheat costs $200 to plant and each acre of rye costs $100 to plant" In math this is

Слайд 47

Описание слайда:

Linear programming Try It Constraints "the farmer has to get the planting done in 12 hours and it takes an hour to plant an acre of wheat and 2 hours to plant an acre of rye " In math this is

Слайд 48

Описание слайда:

Linear programming Try It Objective function "... the profit is $500 per acre of wheat and $300 per acre of rye" In math this is

Слайд 49

Описание слайда:

Linear programming Try It Put it together Constraints: Objective function:

Слайд 50

Описание слайда:

Linear programming Try It Rename x to x1 and y to x2 Change x + y ≥ 7 to -x - y ≤ -7 and then to -x1 - x2 ≤ -7

Слайд 51

Описание слайда:

Linear programming Try It Write in matrix form Maximize Maximize

Слайд 52

Описание слайда:

Linear programming Try It Find solution that maximizes profit. Display both >> A = [ 1 1; -1 -1; 100 200; 2 1]; >> b = [ 10 -7 1200 12 ]'; >> f = [ 300 500 ]'; >> lb = [ 0 0 ]'; >> [x fval] = linprog( -f, A, b, [], [], lb ); >> x' ans = 4.0000 4.0000 >> maxProfit = -fval maxProfit = 3.2000e+003

Слайд 53

Описание слайда:

Linear programming Try It - blending problem Alloy Mixture Optimization (minimize expenses) There are four metals with the following properties: We want to make an alloy with properties in the following range: What mixture of metals should we use to minimize the cost of the alloy?

Слайд 54

$Linear programming Try It - blending problem Decision variables x1 is fraction of total alloy that is metal A x2 is fraction of total alloy that is metal B x3 is fraction of total alloy that is metal C x4 is fraction of total alloy that is metal D$

Описание слайда:

Linear programming Try It - blending problem Decision variables x1 is fraction of total alloy that is metal A x2 is fraction of total alloy that is metal B x3 is fraction of total alloy that is metal C x4 is fraction of total alloy that is metal D

Слайд 55

Описание слайда:

Linear programming Try It - blending problem Density constraints Alloy density must be at least 5950 In math this is Alloy density must be at most 6050 In math this is

Слайд 56

Описание слайда:

Linear programming Try It - blending problem Carbon constraints Carbon concentration must be at least 0.1 In math this is Carbon concentration must be at most 0.3 In math this is

Слайд 57

Описание слайда:

Linear programming Try It - blending problem Phosphor constraints Phosphor concentration must be at least 0.1 In math this is Phosphor concentration must be at most 0.3 In math this is

Слайд 58

$Linear programming Try It - blending problem Constraints Since only the four metals will make up the alloy, the sum of the fractional amounts must be one: Fractional parts must be non-negative: (Each part must also be ≤ 1, but that's handled by first equation.)$

Описание слайда:

Linear programming Try It - blending problem Constraints Since only the four metals will make up the alloy, the sum of the fractional amounts must be one: Fractional parts must be non-negative: (Each part must also be ≤ 1, but that's handled by first equation.)

Слайд 59

Описание слайда:

Linear programming Try It - blending problem Objective function Cost per kg

Слайд 60

Описание слайда:

Linear programming Try It - blending problem Put it together Constraints: (Convert ≥ to ≤) Objective function:

Слайд 61

Описание слайда:

Linear programming Try It - blending problem Write in matrix form Minimize

Слайд 62

Описание слайда:

Linear programming Try It - blending problem >> A = [-6500 -5800 -6200 -5900; 6500 5800 6200 5900;... -0.2 -0.35 -0.15 -0.11; 0.2 0.35 0.15 0.11;... -0.05 -0.015 -0.065 -0.1; 0.05 0.015 0.065 0.1 ]; >> b = [ -5950 6050 -0.1 0.3 -0.045 0.055 ]'; >> f = [ 2 2.5 1.5 2 ]'; >> Aeq = [ 1 1 1 1 ]; >> beq = 1; >> lb = [ 0 0 0 0 ]';

Слайд 63

Описание слайда:

Linear programming Try It - blending problem >> [x fval] = linprog( f, A, b, Aeq, beq, lb ) Optimization terminated. x = 0.0000 <- Metal A 0.2845 <- Metal B 0.5948 <- Metal C 0.1207 <- Metal D fval = 1.8448 <- Profit in $/kg