運籌課件-供學習3introduction to linear programming

3

Introduction

to

Linear

ProgrammingIntroduction3

Introduction

to

Linear

Programming?allocating

limited

resourcesbest

possible

wayin

a?the

simplex

method3

Introduction

to

Linear

Programming3.1

Prototype

exampleThe

Background

:??Product1:

an

8-foot

glass

door

with

aluminum

framingProduct2: A4*6

foot

double-hung

wood-famed

window3

Introduction

to

Linear

ProgrammingplantProduction

time

per

batch,hoursProductiontime

availableper

week,hoursproduct1212310302241218$3,000$5,000Question:ize

their

total

profit

?3.1 Prototype

exampleplantProduction

time

per

batch,

hoursProduction

timeavailable

per

week,hoursproduct

1product

2412Profit

per

batch$3,000$5,000max

z

3x1

5x20x1

2x2

12x1

0x2

43x1

2x2

183.1 Prototype

exampleplantProduction

time

per

batch,

hoursProduction

timeavailable

per

week,hoursproduct

1product

2412Profit

per

batch$3,000$5,0001

2x1,

x2

03x1

2x20x

2x1x1

0x2

4

12

18s.t.max

z

3x1

5x2This

is

a

linearprogramming江西財經3.1 Prototype

exampleRegional

PlanningKibbutzUsable

Land

(Acres)Water

Allocation

(Acre

Feet)1400600260080033003753.1 Prototype

examplecropumquota

(acres)Waterconsumption(acre

feet/acre)Net

return($/acre)Sugar

beets60031,000Cotton5002750s

hum32512503.1 Prototype

exampleThe

question

is:How

many

acres

to

devote

to

each

crop

at

the

respectivekibbutzim

while

satisfying

the

given

restrictions.

The

objective

isto ize

the

total

net

return

to

the

southern

Confederation

ofKibbutzim

as

a

whole.3.1 Prototype

examplegyg

yResearch3.1 Prototype

example運籌學OperationsSo,

the

decision

variables

areCropAllocation

usable

land

to

Kibbutz123Sugarx11x12x13Cottonx21x22x23x31x32x33Shumcropumquota

(acres)Water

consumption(acre

feet/acre)Net

return($/acre)Sugar

beetsCottonS

hum6005003253211,000750250objectiveMaxZ

1000(x11

x12

x13

)

750(x21

x22

x23

)

250(x31

x32

x33

)13

32

3322

3212x

x

x

600

x

x

300xx11

x21

x31

40013

23

333x

2x

x

3753x12

2x22

x32

8003x11

2x21

x31

6003.1 Prototype

example

31323322

2321xx

xx

x

500

325xx11

x12

x13

600300

x13

x23

x33400

x

x

22

x

32600

x11

x21

x31

x12

x22

x32600

x

x

x

x11

x21

x31400x

j

0,

for j

1,2,,9

3.1 Prototype

exampleDecision

variables,

Objective

function,

ConstraintsDetermine

decision

variablesDetermine

the

objective

functionDetermine

the

constraints3.1 Prototype

exampleLP11

1

12

21n

n1am1x1

am2

x221

1x22

2subject

to1

2

x

0,

x

0

,

,xn

0,

amnx

bn

ma2n

xn

b2

aa

x

ba3.2 The

Linear

Programming

ModelThe

standard

formize Z

c1x1

c2

x2

a

xcnxna

x

objective

functionfunctionalconstraintsnonnegativeconstraints3

Introduction

to

Linear

ProgrammingResourceResource

usage

per

unit

of

activityAmount

of

resourceavailableActivity12….n1a11a12a1

nb12a

21a

22a

2

nb2ma

m

1a

m

2a

mnbmContribution

to

Zper

unit

activityc1c

2c

n3.2 The

Linear

Programming

ModelOther

Formslegitimate

formsZ=c1x1+c2x2+…+cnxnai1x1+ai2x2+…+ainxn≥biai1x1+ai2x2+…+ainxn=bixj

unrested

in

signfor

some

values

of

j.3.2 The

Linear

Programming

ModelCertainty

symbols

are

commonly

used

to

denote

the

variouscomponents

of

a

linear

programming

model.These

symbols

arelisted

below:Zxjcjdecision

variablesbiparametersaij3.2 The

Linear

Programming

Model3.3

Solving Linear

Programming

by

using

EXCEL3

Introduction

to

Linear

Programmingm3.3

Solving Linear

Programming

by

using

EXCELmaxz

3x1

51x1

0x2

x24Wyndlass

Co.

Product-Mix

Proble0x1

2x2

12s.t.3x1

2x2

18x1,x2

0DoorsWindowsUnit

Profit$300$500HoursHours

Used

Per

Unit

ProducedAvailablePlant

1104Plant

20212Plant

33218DoorsWindowsUnits

Produced00DoorsW

indowsUnit

Profit$300$500HoursHours

Us

ed

Per

Unit

P

roducedAvailableP

lant

1104P

lant

202123218P

lant

3DoorsW

indowsTotal

P

rofitUnits

Produc

ed11$800G11Total

Profit12=SUMPRODUCT(UnitProfit,UnitsProduced)3.3

Solving Linear

Programming

by

using

EXCELDoorsW

indowsUnit

P

rofit$300

$500HoursHoursHours

Us

ed

P

er

Unit

P

roduc

edUsedA

vailableP

lant

11

01<=4P

lant

20

22<=12P

lant

33

25<=18DoorsW

indowsTotal

P

rofitUnits

P

roduced1

1$800E5Hours6Used7=SUMPRODUCT(C7:D7,UnitsProduced)8=SUMPRODUCT(C8:D8,UnitsProduced)9=SUMPRODUCT(C9:D9,UnitsProduced)3.3

Solving Linear

Programming

by

using

EXCEL3.3

Solving Linear

Programming

by

using

EXCEL24運籌學Operations

Research(7)

Answer

the

parameters

of

SolverBCDEFG3DoorsWindows4Unit

Profit$300

$5005HoursHours6Hours

Used

Per

Unit

ProducedUsedAvailable7Plant

11

00

23

21<=112188Plant

22<=9Plant

35<=1011DoorsWindowsTotal

Profit12Units

Produced1

1$8003.3

Solving Linear

Programming

by

using

EXCELSchool

of

Information

Technology,

JiangXi

University

of

Finance

&

Economics?2006BCDEFG3DoorsWindows4Unit

Profit$300$5005HoursHours6Hours

Used

Per

Unit

ProducedUsedAvailable7Plant

1101<=102128Plant

22<=9Plant

3325<=181011DoorsWindowsTotal

Profit12Units

Produced11$800of

Information

Technology,

JiangXi

University

of

Finance

&

Economics?20063.3

Solving Linear

Programming

by

using

EXCEL3.3

Solving Linear

Programming

by

using

EXCELDoorsW

indowsUnit

P

rofit$300

$500HoursHoursHours

Us

ed

P

er

Unit

Produc

edUsedA

vailableP

lant

11

02<=1P

lant

20

212<=12P

lant

33

218<=18DoorsW

indowsTotal

P

rofitUnit

s

P

roduced2

6$3,6003.3

Solving Linear

Programming

by

using

EXCELThe

optimal

solution

is:Regional

Planningwater

consumptionAllocation

land

to

KibbtzCrop(Acre

Feet/Acre)123Sugar

beets321133.33100.0025.00258.3333<=600500325Cotton100.00250.00150.00500<=S

hum0<=233.33350.00175.00<=<=<=Usable

Land

(Acres)400.00

600.00

300.00um

Profit633333.33600.00800.00375.00<=<=<=Water

allocation(Acre

Feet)600.00

800.00

375.00Equal

Proportion

of

land

PlantedPlant

of

Rate

of

Kibbutz

1Plant

of

Rate

of

Kibbutz

2Plant

of

Rate

of

Kibbutz

30.58=0.58=0.583.3

Solving Linear

Programming

by

using

EXCEL3.4 Solving

LP

by

Graphic

Method3

Introduction

to

Linear

Programming12x1,

x2

00x

2x.

1

2s.t

x

2xmax

z

3x1

5x21x1

0x2

4

123

18The

optimal

solutionx1=2,

x2=6Z=3600echFeasibleRegionThe

steps

of

Graphic

Method:3.4 Solving

LP

by

Graphic

Method3.4 Solving

LP

by

Graphic

MethodExercise:

To

solving

the

following

LP,

0x

x1

2s.t.3

x1

2x2

262

x1

3

x2

24max

z

4

x1

3

x21(8)()The

optimal

solutionx1=6,x2=4Z=363.4 Solving

LP

by

Graphic

MethodSome

other

possible

situations

:(1)

No

Optimal

Solutions.3.4 Solving

LP

by

Graphic

MethodTerminology

for

Solution

of

the

Modelfeasible

solutioninfeasiblesolution?feasibleregionno

feasiblesolutions.An

optimal

solution3.4 Solving

LP

by

Graphic

MethodFeasibleRegionRelationship

between

optimalsolutions

and

CPF

solutions:corner-point

feasible(CPF)solution3.4 Solving

LP

by

Graphic

Method3.5

Assumptions

of

Linear

Programming(1)ProportionalityProportionalityProportionalityassumption:valueis

proportional

to

theof

the

objective

functionlevel

of

the

activity

xj,left-hand

side

of

each

functional

constraint

isproportional

to

the

level

of

the

activity

xj,23x1

2x2

18x1,

x2

02x

12x1

4s.t.max

Z

3x1

2x23

Introduction

to

Linear

Programming運籌學Operations

Research035660371291201234Proportionality

violatedCase

1 Case

2 Case

3ProportionalitysatisfiedTo

illustrate

this

assumption,

consider

the

Wynd

lassCo.

problem.Profit

from

product

1

($000

per

week)x13.5

Assumptions

of

Linear

Programming江西財經大學信息管理學院?2006School

of

Information

Technology,

JiangXi

University

of

Finance

&

Economics?200637Set-up

cSocsoto3.5

Assumptions

of

Linear

ProgrammingCase

1SatisfiesViolatesViolatesCase

1Case

23.5

Assumptions

of

Linear

ProgrammingCase

2:slope

of

the

profit

functionthe3.5

Assumptions

of

Linear

ProgrammingViolatesCase

3:slope

of

the

profit

functionSatisfies3.5

Assumptions

of

Linear

Programming(x1,x2)Value

of

ZAdditivity

satisfiedAdditivity

violatedCase

1Case

2(1,0)(0,1)353535(1,1)8973.5

Assumptions

of

Linear

ProgrammingAdditive

Assumption:the

sum

of

theindividual

contributionsCase

1:if

the

two

products

werecomplementary

in

some

way

that

increases

profit3.5

Assumptions

of

Linear

ProgrammingCase2:arise

if

the

two

products

werecompetitive

in

some

wayback

andforth3.5

Assumptions

of

Linear

Programming運籌學Operations

ResearchCase

3:

the

production

time

used

by

the

two

products

is

givenby

the

function

3x1+2x2+0.5x1x2,which

violates

the

additiveassumption.(x1,x2)Amount

of

resource

usedAdditivity

satisfiedAdditivity

violatedCase

3Case

4(2,0)(0,3)666666(2,3)121510.83.5

Assumptions

of

Linear

Programming江西財經大學信息管理學院?2006School

of

Information

Technology,

JiangXi

University

of

Finance

&

Economics?200645運籌學Operations

ResearchCase

4:

the

function

for

production

time

used

is

3x1+2x2-0.5x1

x2, so

violates

the

additive

assumption.2(x1,x2)Amount

of

resource

usedAdditivity

satisfiedAdditivity

violatedCase

3Case

4(2,0)(0,3)666666(2,3)121510.83.5

Assumptions

of

Linear

Programming江西財經大學信息管理學院?2006School

of

Information

Technology,

JiangXi

University

of

Finance

&

Economics?200646Divisibility

assumptionfractional

levelsinteger

values3.5

Assumptions

of

Linear

ProgrammingCertainty

assumptions:known

constant3.5

Assumptions

of

Linear

Programming3.6

Additional

Examples3

Introduction

to

Linear

ProgrammingDesign

of

Radiation

TherapyRadiationtherapy3.6

Additional

Examples1332Beam13.6

Additional

ExamplesTable

3.7Data

for

the

Design

of

Mary’sRadiation

TherapyFraction

of

Entry

Dose

AbsorbedRestriction

on

TotalAverage

Dosage,Kiloradsby

Area

(Average)AreaBeam1Beam2Healthy

anatomy0.40.5MinimizeCritical

tissues0.30.1<=2.7Tumor

region0.50.5=6Center

of

tumor0.60.4>=6select

the

combination

ofbeams

to

be

used,

and

the

intensity

of

each

one,

togenerate

the

best

possible

dose

distribution.3.6

Additional

Exampless.t

0.5x1

0.5x

2

6.0.6x1

0.4x2

6x1,

x2

63.6

Additional

ExamplesFORMULATION

:Minimize Z

0.4x1

0.5x20.3x1

0.1x2

2.7Controlling

Air

Pollution3.6

Additional

Examples運籌學Operations

Research江西財經大學信息管理學院?2006School

of

Information

Technology,

JiangXi

University

of

Finance

&

Economics?200655The

three

main

types

of

pollutants

in

this

airsideare

particulate

matter,

sulfur

oxides,

andhydrocarbons.

The

new

standards

require

that

thecompany

reduce

its

annual

emission

of

thesepollutants

bytheamounts

shown

inTable3.12.PollutionRequired

reduction

in

annual

emission

rate(million

pounds)Particulates60Sulfur

oxides150Hydrocarbons1253.6

Additional

ExamplesIncreasing

the

height

of

the

smokestacks;Using

filter

devices

(including

gas

traps)

in

the

smokestacks;(3)Including

cleaner,

high-grade

materials

among

the

fuels

forthe

furnaces.3.6

Additional

ExamplesPollutantTaller

SmokestacksFiltersBetter

fuelsBlastfurnacesOpen-hearthfurnacesBlastfurnacesOpen-hearthfurnacesBlastfurnacesOpen-hearthfurnacesParticulates12925201713Sulfur

oxides354218315649hydrocarbons3753282429203.6

Additional

Examples運籌學Operations

Research江西財經大學信息管理學院?2006School

of

Information

Technology,

JiangXi

University

of

Finance

&

Economics?200658A

method’s

annual

cost

includes

increased

operating

andmaintenance

expense

as

well

as

reduced

revenue

due

to

anyloss

in

the

efficiency

of

the

production

process

caused

by

usingthe

method.The

other

major

cost

is

the

start-up

cost

required

to

installthe

method.The

total

annual

cost

estimates

(in

million

of

dollars)

aregiven

in

Table

3.14

for

using

the

methods

at

their

fullabatement

capacities.Abatement

methodBlast

furnacesOpen-hearth

furnacesTaller

smokestacks810Filters76Better

fules1193.6

Additional

ExamplesQuestion:3.6

Additional

ExamplesFORMULATION:3.6

Additional

ExamplesReclaiming

Solid

Wastes3.6

Additional

Examples運籌學Operations

ResearchProductDataforSave-it

Co.GradeSpecificationAmalgamationCost

perpound($)Selling

price

perpound

($)ABCMaterial

1:Not

more

than

30%

of

totalMaterial

2:Not

less

than

40%

of

totalMaterial

3:Not

more

than

50%

of

totalMaterial4:Exactly

20%oftotalMaterial

1:Not

more

than

50%

of

totalMaterial

2:Not

less

than

10%

of

totalMaterial4:Exactly

10%oftotal3.002.508.507.00Material

1:not

more

than

70%

of

total2.005.50江西財經大學信息管理學院?2006School

of

Information

Technology,

JiangXi

University

of

Finance

&

Economics?2006623.6

Additional

Examples運籌學Operations

Researchfor

ea aterial,

at

leasthalf

of

the

pounds

perweekavailable

should

be

collectedand

treated

.$30,000

per

week

shouldbe

used

to

treat

thesematerials.30060040050030002000400010001234The

reclamationcenter

collects

its

solid

waste

materials

fromregular

sources

and

so

is

normally

able

to

maintain

a

steady

ratefor

treating

them.Solid

waste

material

data

for

the

save-it

Co.Material Pounds

perweek

availableTreatment

cost

Additional

restrictionsper

pound($)江西財經大學信息管理學院?2006School

of

Information

Technology,

JiangXi

University

of

Finance

&

Economics?2006633.6

Additional

Examplesat

least

half

of

the

amountQuestion:3.6

Additional

ExamplesLet

xij

=

Pounds

of

material

j

allocated

to

product

i

per

week

(i

=

A,

B,

C;

j

=

1,

2,

3,4).ize

Profit

=

5.5(xA1

+

xA2

+

xA3

+

xA4)

+

4.5(xB1

+

xB2

+

xB3

+

xB4)

+

3.5(xC1

+

xC2+

xC3

+

xC4)subject

to MixtureSpecifications:Availability

of