Matlab Linear Programming

Содержание

Слайд 2

MATLAB Linear Programming © 2010-2013 Greg Reese. All rights reserved

MATLAB Linear Programming

© 2010-2013 Greg Reese. All rights reserved

Слайд 3

Optimization Optimization - finding value of a parameter that maximizes or

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

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

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

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

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,

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

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

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

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

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

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

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

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

Linear programming

Example - diet problem

Слайд 17

Linear programming Example - diet problem What are unknowns? x1 =

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

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

Linear programming

Example - diet problem
Therefore, need to minimize

Слайд 20

Linear programming Example - diet problem Constraint 1 - calorie intake

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

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

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

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

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

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

Linear programming

Example - diet problem
In matrix notation, want to
where

Слайд 27

Linear programming MATLAB solves linear programming problem where x, b, beq,

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

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:

Linear programming

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

Слайд 30

Linear programming Example - diet problem ISSUE 1 - We have

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

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

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 =

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

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

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

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

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

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

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

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

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

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,

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

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

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

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

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

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:

Linear programming

Try It
Put it together
Constraints:
Objective function:

Слайд 50

Linear programming Try It Rename x to x1 and y to

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

Linear programming

Try It
Write in matrix form
Maximize
Maximize

Слайд 52

Linear programming Try It Find solution that maximizes profit. Display both

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

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

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

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

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

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

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

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

Слайд 60

Linear programming Try It - blending problem Put it together Constraints:

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

Linear programming

Try It - blending problem
Write in matrix form
Minimize

Слайд 62

Linear programming Try It - blending problem >> A = [-6500

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] =

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
Слайд 64

MATLAB Linear Programming Questions?

MATLAB Linear Programming

Questions?

- Предыдущая
Проблема гендерного равенства в развитии рынка труда
Следующая -
Проблематика рассказа М. Горького Челкаш

Похожие презентации

Множественные сравнения
Решение логарифмических уравнений
Представьте в виде неправильной дроби
Умножение десятичной дроби на натуральное число
Декартовая система координат
Презентация по математике "Определение квадратного уравнения. Неполные квадратные уравнения" - скачать бесплатно
Формирование начальных математических знаний
Початкові відомості зі стереометрії. Конус
Тренажер «Считаем с Колобком»
Интегративные процессы математического образования и профессиональная подготовка учащихся
Взаимное расположение прямых и плоскостей
Подобие треугольников. Решение практических задач
Векторы. Понятие вектора. Равенство векторов
Геометрические тела в окружающем мире
Шагая по стране Знаний. Сказки Пушкина в цифрах
Готовимся к ЕГЭ
Презентация на тему Римские цифры
Проверка умножения
Системы эконометрических уравнений
Математический каламбур. Анаграммы в стихах
Общий приём вычитания с переходом через десяток
Математическая игра
Второй признак равенства треугольников. Решение задач
Геометрический смысл производной. Определение
Векторні величини. Метод координат
Статистические характеристики
Сложение и вычитание алгебраических дробей с одинаковыми знаменателями
Доли и дроби
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть