<< Chapter < Page Chapter >> Page >

Định lý

Tổ hợp lồ có tính chất bắc cầu.

b- Tập hợp lồi

Tập con S của Rn được gọi là tập hợp lồi khi S chứa toàn bộ đoạn thẳng nối hai điểmbất kỳ của S.

x + (1-)y  S x,y,[0,1]

Tập hợp rỗng và tập hợp chỉ có một phần tử được xem là tập hợp lồi.

Định lý

Giao của một số bất kỳ các tập hợp lồi là một tập hợp lồi.

Định lý

Nếu S là một tập hợp lồi thì S chứa mọi tổ hợp lồi của một họ điểm bất kỳ trong S.

c- Ðiểm cực biên của một tập hợp lồi

Ðiểm x trong tập lồi S  Rn được gọi là điểm cực biên nếu không thể biểu diễn được x dưới dạng tổ hợp lồi thật sự của hai điểm phân biệt của S.

x

4- Ða diện lồi và tập lồi đa diện

Đa diện lồi

Tập hợp S tất cả các tổ hợp của các điểm x1, x2,....,xm cho trước được gọi là đa diện lồi sinh ra bởi các điểm đó.

Đa diện lồi là một tập hợp lồi.

Trong đa diện lồi người ta có thể loại bỏ dần các điểm là tổ hợp của các điểm còn lại. Khi đó người ta thu được một hệ các điểm, giả sử là y1, y2,...,yp (pm) . Các điểm này chính là các điểm cực biên của đa diện lồi, chúng sinh ra đa diện lồi đó.

Số điểm cực biên của đa diện lồi là hữu hạn.

Siêu phẳng - Nửa không gian

A=[aij]m.n là ma trận cấp m.n

Ai (i=1,2,...,m) là hàng thứ i của A

Siêu phẳng trong Rn là tập các điểm x=[x1,x2,.....,xn]T thỏa

Ai x = bi

Nửa không gian trong Rn là tập các điểm x=[x1,x2,.....,xn]T thỏa

Ai x  bi

Siêu phẳng và nửa không gian đều là các tập hợp lồi.

Tập lồi đa diện

Giao của một số hữu hạn các nửa không gian trong Rn được gọi là tập lồi đa diện.

Tập lồi đa diện là một tập hợp lồi.

Nếu tập lồi đa diện không rỗng và giới nội thì đó là một đa diện lồi

Đặc điểm của tập hợp các phương án

Ðịnh lý

Tập hợp các phương án của một quy hoạch tuyến tính là một tập lồi đa diện.

Nếu tập hợp lồi đa diện này không rỗng và giới nội thì đó là một đa diện lồi, số điểm cực biên của nó là hữu hạn.

Ðịnh lý

Tập hợp các phương án tối ưu của một quy hoạch tuyến tính là một tập lồi.

Xét quy hoạch tuyến tính chính tắc

min/max z ( x ) = c T x ( I ) Ax = b ( II ) x 0 ( III ) { alignl { stack { size 12{"min/max "z \( x \) =c rSup { size 8{T} } x" " \( I \) } {} #alignl { stack { left lbrace ital "Ax"=b" " \( "II" \) {} #right none left lbrace x>= 0" " \( "III" \) {} # right no } } lbrace {}} } {}

Giả sử A=[aij]m.n có cấp m.n, m  n, rang(A)=m .

Gọi Aj (j=1,2,...,n) cột thứ j của ma trận A, quy hoạch tuyến tính chính tắc trên có thể viết :

min/max z ( x ) = c 1 x 1 + c 2 x 2 + . . . + c n x n x 1 A 1 + x 2 A 2 + . . . + x n A n = b x 0 { alignl { stack { size 12{"min/max"" z" \( x \) =c rSub { size 8{1} } x rSub { size 8{1} } +c rSub { size 8{2} } x rSub { size 8{2} } + "." "." "." +c rSub { size 8{n} } x rSub { size 8{n} } } {} #alignl { stack { left lbrace x rSub { size 8{1} } A rSup { size 8{1} } +x rSub { size 8{2} } A rSup { size 8{2} } + "." "." "." +x rSub { size 8{n} } A rSup { size 8{n} } =b {} #right none left lbrace x>= 0 {} # right no } } lbrace {}} } {}

Gọi S={x=[x1,x2,...,xn]T  0 / x1A1+ x2A2+...+ xnAn=b} là tập các phương án của bài toán.

x 0 = x 1 0 , x 2 0 , . . . , x n 0 T size 12{x rSup { size 8{0} } = left [x rSub { size 8{1} } rSup { size 8{0} } ,x rSub { size 8{2} } rSup { size 8{0} } , "." "." "." ,x rSub { size 8{n} } rSup { size 8{0} } right ]rSup { size 8{T} } } {}  S là một phương án khác 0.

Định lý

Điều kiện cần và đủ để x0 là phương án cực biên ( điểm cực biên của S) là các cột Aj ứng với x j 0 size 12{x rSub { size 8{j} } rSup { size 8{0} } } {} >0 là độc lập tuyến tính.

Hệ quả

Số phương án cực biên của một quy hoạch tuyến tính chính tắc là hữu hạn. Số thành phần>0 của một phương án cực biên tối đa là bằng m.

Khi số thành phần>0 của một phương án cực biên bằng đúng m thì phương án đó được gọi là một phương án cơ sở.

Định lý

Nếu tập các phương án của một quy hoạch tuyến tính chính tắc không rỗng thì quy hoạch tuyến tính đó có ít nhất một phương án cực biên.

Bổ đề

Nếu

x ¯ size 12{ {overline {x}} } {} là một phương án tối ưu của quy hoạch tuyến tính.

x1, x2 là các phương án của quy hoạch tuyến tính.

x ¯ size 12{ {overline {x}} } {} là tổ hợp lồi thực sự của x1, x2

thì x1, x2 cũng là phương án tối ưu của quy hoạch tuyến tính.

Định lý

Nếu quy hoạch tuyến tính chính tắc có phương án tối ưu thì thì sẽ có ít nhất một phương án cực biên là phương án tối ưu.

Questions & Answers

what does nano mean?
Anassong Reply
nano basically means 10^(-9). nanometer is a unit to measure length.
Bharti
do you think it's worthwhile in the long term to study the effects and possibilities of nanotechnology on viral treatment?
Damian Reply
absolutely yes
Daniel
how to know photocatalytic properties of tio2 nanoparticles...what to do now
Akash Reply
it is a goid question and i want to know the answer as well
Maciej
characteristics of micro business
Abigail
for teaching engĺish at school how nano technology help us
Anassong
Do somebody tell me a best nano engineering book for beginners?
s. Reply
what is fullerene does it is used to make bukky balls
Devang Reply
are you nano engineer ?
s.
fullerene is a bucky ball aka Carbon 60 molecule. It was name by the architect Fuller. He design the geodesic dome. it resembles a soccer ball.
Tarell
what is the actual application of fullerenes nowadays?
Damian
That is a great question Damian. best way to answer that question is to Google it. there are hundreds of applications for buck minister fullerenes, from medical to aerospace. you can also find plenty of research papers that will give you great detail on the potential applications of fullerenes.
Tarell
what is the Synthesis, properties,and applications of carbon nano chemistry
Abhijith Reply
Mostly, they use nano carbon for electronics and for materials to be strengthened.
Virgil
is Bucky paper clear?
CYNTHIA
so some one know about replacing silicon atom with phosphorous in semiconductors device?
s. Reply
Yeah, it is a pain to say the least. You basically have to heat the substarte up to around 1000 degrees celcius then pass phosphene gas over top of it, which is explosive and toxic by the way, under very low pressure.
Harper
Do you know which machine is used to that process?
s.
how to fabricate graphene ink ?
SUYASH Reply
for screen printed electrodes ?
SUYASH
What is lattice structure?
s. Reply
of graphene you mean?
Ebrahim
or in general
Ebrahim
in general
s.
Graphene has a hexagonal structure
tahir
On having this app for quite a bit time, Haven't realised there's a chat room in it.
Cied
what is biological synthesis of nanoparticles
Sanket Reply
what's the easiest and fastest way to the synthesize AgNP?
Damian Reply
China
Cied
types of nano material
abeetha Reply
I start with an easy one. carbon nanotubes woven into a long filament like a string
Porter
many many of nanotubes
Porter
what is the k.e before it land
Yasmin
what is the function of carbon nanotubes?
Cesar
I'm interested in nanotube
Uday
what is nanomaterials​ and their applications of sensors.
Ramkumar Reply
what is nano technology
Sravani Reply
what is system testing?
AMJAD
preparation of nanomaterial
Victor Reply
how to synthesize TiO2 nanoparticles by chemical methods
Zubear
what's the program
Jordan
?
Jordan
what chemical
Jordan
how did you get the value of 2000N.What calculations are needed to arrive at it
Smarajit Reply
Privacy Information Security Software Version 1.1a
Good
Berger describes sociologists as concerned with
Mueller Reply
Got questions? Join the online conversation and get instant answers!
QuizOver.com Reply

Get the best Algebra and trigonometry course in your pocket!





Source:  OpenStax, Quy hoạch tuyến tính. OpenStax CNX. Aug 08, 2009 Download for free at http://cnx.org/content/col10903/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Quy hoạch tuyến tính' conversation and receive update notifications?

Ask