1. Home
  2. Quy hoạch tuyến tính
  3. Quy hoạch tuyến tính
  4. Bài toán đối ngẫu

0.2 Bài toán đối ngẫu  (Page 4/4)

<< Chapter < Page
  Quy hoạch tuyến tính     Page 4 / 4
Chapter >> Page >

min w ( y ) = b 1 y 1 + b 2 y 2 + b 3 y 3 + 0 . y 4 + 0 . y 5 + 0 . y 6 + 0 . y 7 + 0 . y 8 a 11 y 1 + a 21 y 2 + a 31 y 3 − y 4 = c 1 a 12 y 1 + a 22 y 2 + a 32 y 3 − y 5 = c 2 a 13 y 1 + a 23 y 2 + a 33 y 3 − y 6 = c 3 a 14 y 1 + a 24 y 2 + a 34 y 4 − y 7 = c 4 a 15 y 1 + a 25 y 2 + a 35 y 3 − y 8 = c 5 y 1 , y 2 , y 3 tuy y - y 4 , y 5 , y 6 , y 7 , y 8 ≥ 0 { { { { alignl { stack { size 12{"min"" w" \( y \) =b rSub { size 8{1} } y rSub { size 8{1} } +b rSub { size 8{2} } y rSub { size 8{2} } +b rSub { size 8{3} } y rSub { size 8{3} } +0 "." y rSub { size 8{4} } +0 "." y rSub { size 8{5} } +0 "." y rSub { size 8{6} } +0 "." y rSub { size 8{7} } +0 "." y rSub { size 8{8} } } {} #alignl { stack { left lbrace a rSub { size 8{"11"} } y rSub { size 8{1} } +a rSub { size 8{"21"} } y rSub { size 8{2} } +a rSub { size 8{"31"} } y rSub { size 8{3} } - y rSub { size 8{4} } =c rSub { size 8{1} } {} #right none left lbrace a rSub { size 8{"12"} } y rSub { size 8{1} } +a rSub { size 8{"22"} } y rSub { size 8{2} } +a rSub { size 8{"32"} } y rSub { size 8{3} } - y rSub { size 8{5} } =c rSub { size 8{2} } {} # right none left lbrace a rSub { size 8{"13"} } y rSub { size 8{1} } +a rSub { size 8{"23"} } y rSub { size 8{2} } +a rSub { size 8{"33"} } y rSub { size 8{3} } - y rSub { size 8{6} } =c rSub { size 8{3} } {} #right none left lbrace a rSub { size 8{"14"} } y rSub { size 8{1} } +a rSub { size 8{"24"} } y rSub { size 8{2} } +a rSub { size 8{"34"} } y rSub { size 8{4} } - y rSub { size 8{7} } =c rSub { size 8{4} } {} # right none left lbrace a rSub { size 8{"15"} } y rSub { size 8{1} } +a rSub { size 8{"25"} } y rSub { size 8{2} } +a rSub { size 8{"35"} } y rSub { size 8{3} } - y rSub { size 8{8} } =c rSub { size 8{5} } {} #right no } } lbrace {} # y rSub { size 8{1} } ,y rSub { size 8{2} } ,y rSub { size 8{3} } " tuy y - "y rSub { size 8{4} } ,y rSub { size 8{5} } ,y rSub { size 8{6} } ", "y rSub { size 8{7} } ,y rSub { size 8{8} }>= "0 " {} } } {}

Các dữ liệu của (D) được trình bày trong bảng sau :

y1 y2 y3 y4 y5 y6 y7 y8
b1 b2 b3 0 0 0 0 0
a11 a21 a31 -1 0 0 0 0 c1
a12 a22 a32 0 -1 0 0 0 c2
a13 a23 a33 0 0 -1 0 0 c3
a14 a24 a34 0 0 0 -1 0 c4
a15 a25 a35 0 0 0 0 -1 c5

Giả sử rằng m cột đầu tiên của A là một cơ sở B của (P) thì hai bảng trên được trình bày rút gọn như sau :

x B T size 12{x rSub { size 8{B} } rSup { size 8{T} } } {} x N T size 12{x rSub { size 8{N} } rSup { size 8{T} } } {}
c B T size 12{c rSub { size 8{B} } rSup { size 8{T} } } {} c N T size 12{c rSub { size 8{N} } rSup { size 8{T} } } {}
B N b

Bảng (P)

yT y4....y8
bT 0
BT -Im 0 cB
NT 0 -In-m cN

Bảng (D)

Để đưa bài toán đối ngẫu về dạng chuẩn người ta nhân (bên trái) bảng (D) với bảng sau đây :

B − 1 T size 12{ left ( B rSup { size 8{ - 1} } right ) rSup { size 8{T} } } {} 0
B − 1 N T size 12{ left ( B rSup { size 8{ - 1} } N right ) rSup { size 8{T} } } {} -In-m

Khi đó người ta được bảng kết quả có dạng :

m m n-m
y T size 12{y rSup { size 8{T} } } {} y4y5y6 y7y8
0 b ¯ = B − 1 b size 12{ {overline {b}} =B rSup { size 8{ - 1} } b} {} 0
m Im − B − 1 T size 12{ - left ( B rSup { size 8{ - 1} } right ) rSup { size 8{T} } } {} 0 c B T B − 1 T size 12{ left (c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } right ) rSup { size 8{T} } } {}
n-m 0 − N ¯ T = − B − 1 N T size 12{ - left ( {overline {N}} right ) rSup { size 8{T} } = - left (B rSup { size 8{ - 1} } N right ) rSup { size 8{T} } } {} In-m − c ¯ N = − c N T − c B T B − 1 N T size 12{ - {overline {c}} rSub { size 8{N} } = - left (c rSub { size 8{N} } rSup { size 8{T} } - c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } N right ) rSup { size 8{T} } } {}

Bảng này cho ta một quy hoạch tuyến tính dạng chuẩn với ma trận đơn vị (cơ sở) tương ứng với các cột y1 y2 y3 y7 y8 .

Áp dụng giải thuật đơn hình cơ bản vào kết quả này cho ta quy tắc đổi cơ sở như sau :

Tính : b ¯ = B − 1 b ≥ 0 size 12{ {overline {b}} =B rSup { size 8{ - 1} } b>= 0} {}

a- Nếu b ¯ ≥ 0 size 12{ {overline {b}}>= 0} {} thì giải thuật kết thúc, khi đó :

y = c B T B − 1 size 12{y=c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } } {} là phương án tối ưu của bài toán đối ngẫu .

x B x N righ b ¯ 0 righ x = size 12{x=alignl { stack { left [x rSub { size 8{B} } {} #right ] left [x rSub { size 8{N} } {} #righ]} } \[ \]=alignl { stack { left [ {overline {b}} {} #right ] left [0 {} #righ]} } \[ \]} {} là phương án tối ưu của bài toán gốc .

b- Nếu tồn tại r sao cho b ¯ r ∈ b ¯ , b ¯ r < 0 size 12{ {overline {b}} rSub { size 8{r} } in {overline {b}} , {overline {b}} rSub { size 8{r} }<0} {} thì xảy ra một trong hai trường hợp sau :

- Nếu trong dòng r của N ¯ size 12{ {overline {N}} } {} có thành phần<0 thì người ta tính :

c ¯ s N ¯ rs = min c ¯ j N ¯ rj ∀ j : N ¯ ij < 0 alignl { stack { size 12{ { { {overline {c}} rSub { size 8{s} } } over { {overline {N}} rSub { size 8{ ital "rs"} } } } ="min" left lbrace { { {overline {c}} rSub { size 8{j} } } over { {overline {N}} rSub { size 8{ ital "rj"} } } } right rbrace } {} #" " forall "j : " {overline {N}} rSub { size 8{ ital "ij"} }<0 {} } } {}

Như vậy : đối với bài toán đối ngẫu thì biến yr đi vào cơ sở và biến ys ra khỏi cơ sở, trong khi đó đối với bài toán gốc thì biến xs đi vào cơ sở và biến xr ra khỏi cơ sở.

- Nếu mọi thành phần trong dòng r của N ¯ size 12{ {overline {N}} } {} đều>0 thì phương án tối ưu của bài toán đối ngẫu là không giới nội, điều này (theo định lý đối ngẫu) dẫn đến bài toán gốc không có phương án.

Ví dụ : Xét bài toán

min w ( x ) = x 1 − x 3 x 1 − 2x 2 + x 3 = 1 x 1 + 3x 2 + x 4 = 2 x j ≥ 0 ( j = 1,2,3,4 ) { alignl { stack { size 12{"min"" w" \( x \) =x rSub { size 8{1} } - x rSub { size 8{3} } } {} #alignl { stack { left lbrace x rSub { size 8{1} } - 2x rSub { size 8{2} } +x rSub { size 8{3} } =1 {} #right none left lbrace x rSub { size 8{1} } +3x rSub { size 8{2} } +x rSub { size 8{4} } =2 {} # right no } } lbrace {} #x rSub { size 8{j} }>= 0" " \( j="1,2,3,4" \) {}} } {} (D)

Bài toán đối ngẫu của (D) là :

max z ( y ) = y 1 + 2y 2 y 1 + y 2 ≤ 1 − 2y 1 + 3y 2 ≤ 0 y 1 ≤ − 1 y 2 ≤ 0 { { { alignl { stack { size 12{"max"" z" \( y \) =y rSub { size 8{1} } +2y rSub { size 8{2} } } {} #alignl { stack { left lbrace y rSub { size 8{1} } +y rSub { size 8{2} }<= 1 {} # right none left lbrace - 2y rSub { size 8{1} } +3y rSub { size 8{2} }<= 0 {} # right none left lbrace y rSub { size 8{1} }<= - 1 {} # right none left lbrace y rSub { size 8{2} }<= 0 {} # right no } } lbrace {}} } {} (P)

y1, y2 là tùy ý

Ta có thể chọn bài toán (D) hoặc (P) để giải tìm phương án tối ưu bằng phương pháp đơn hình, từ đó suy ra phương án tối ưu của bài toán còn lại theo kết quả trên. Trong ví dụ này ta chọn bài toán (D) để giải vì có chứa sẵn ma trận đơn vị.

Giải bài toán (D) bằng phương pháp đơn hình cải tiến ta được :

c B 0 size 12{c rSub { size 8{B rSub { size 6{0} } } } } {} i B 0 size 12{i rSub { size 8{B rSub { size 6{0} } } } } {} x 1 size 12{x rSub { size 8{1} } } {} x 2 size 12{x rSub { size 8{2} } } {} x 3 size 12{x rSub { size 8{3} } } {} x 4 size 12{x rSub { size 8{4} } } {} b ¯ 0 size 12{ {overline {b}} rSub { size 8{0} } } {}
-1 3 1 -2 1 0 1
0 4 1 3 0 1 2
c T size 12{c rSup { size 8{T} } } {} 1 0 -1 0 w(x0)
c ¯ 0 T size 12{ {overline {c}} rSub { size 8{0} } rSup { size 8{T} } } {} 2 -2 0 0 -1
c B 1 size 12{c rSub { size 8{B rSub { size 6{1} } } } } {} i B 1 size 12{i rSub { size 8{B rSub { size 6{1} } } } } {} x 1 size 12{x rSub { size 8{1} } } {} x 2 size 12{x rSub { size 8{2} } } {} x 3 size 12{x rSub { size 8{3} } } {} x 4 size 12{x rSub { size 8{4} } } {} b ¯ 1 size 12{ {overline {b}} rSub { size 8{1} } } {}
-1 3 5 3 size 12{ { {5} over {3} } } {} 0 1 2 3 size 12{ { {2} over {3} } } {} 7 3 size 12{ { {7} over {3} } } {}
0 2 1 3 size 12{ { {1} over {3} } } {} 1 0 1 3 size 12{ { {1} over {3} } } {} 2 3 size 12{ { {2} over {3} } } {}
c T size 12{c rSup { size 8{T} } } {} 1 0 -1 0 w(x1)
c ¯ 1 T size 12{ {overline {c}} rSub { size 8{1} } rSup { size 8{T} } } {} 8 3 size 12{ { {8} over {3} } } {} 0 0 2 3 size 12{ { {2} over {3} } } {} − 7 3 size 12{ - { {7} over {3} } } {}

Giải thuật dừng vì thoả dấu hiệu tối ưu của bài toán min.

Phương án tối ưu của bài toán (D) là :

x 1 = 0 x 2 = 2 3 x 3 = 7 3 x 4 = 0 w ( x ) = w ( x 1 ) = − 7 3 { size 12{alignl { stack { left lbrace x rSub { size 8{1} } =0" "x rSub { size 8{2} } = { {2} over {3} } " "x rSub { size 8{3} } = { {7} over {3} } " "x rSub { size 8{4} } =0 {} #right none left lbrace w \( x \) =w \( x rSup { size 8{1} } \) = - { {7} over {3} } {} # right no } } lbrace } {}

Suy ra phương án tối ưu của (P) là :

y T = y 1 y 2 = c B T B − 1 = − 1 0 1 2 3 0 1 3 = − 1 − 2 3 z ( y ) = b T y = 1 2 − 1 − 2 3 = − 7 3 { size 12{alignl { stack { left lbrace y rSup { size 8{T} } = left [ matrix {y rSub { size 8{1} } {} # y rSub { size 8{2} } {} } right ]=c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } = left [ matrix { - 1 {} # 0{}} right ] left [ matrix {1 {} # { {2} over {3} } {} ## 0 {} # { {1} over {3} } {}} right ]= left [ matrix {- 1 {} # - { {2} over {3} } {} } right ]{} # right none left lbrace z \( y \) =b rSup { size 8{T} } y= left [ matrix {1 {} # 2{} } right ]left [ matrix { - 1 {} ##- { {2} over {3} } } right ]= - { {7} over {3} } {} # right no } } lbrace } {}

CÂU HỎI CHƯƠNG 3

1- Bạn hiểu như thế nào về khái niệm đối ngẫu ?

2- Quy hoạch tuyến tính đối ngẫu của một quy hoach tuyến tính chính tắc có dạng như thế nào ?

3- Bạn hãy nêu ra các quy tắc đối ngẫu. Cho ví dụ .

4- Giá trị hàm mục tiêu của hai quy hoạch tuyến tính đối ngẫu thì như thế nào ? . Chứng minh

Bài tập chương 3

1- Xét bài toán quy hoạch tuyến tính

max z = 7x1 + 5x2

2x1 + 3x2  19

(P)2x1 + x2  13

3x2  15

3x1  18

x1 , x2  0

a- Tìm bài toán đối ngẫu (D) từ bài toán (P)

b- Tìm phương án tối ưu cho bài toán (P)

c- Từ bảng đơn hình tối ưu của (P). Hãy tìm phương án tối ưu cho bài toán (D)

2- Xét bài toán quy hoạch tuyến tính

min w= x1 + x2

x1 - 2x3 + x4 = 2

(D)x2 - x3 + 2x4 = 1

x3 - x4 + x5 = 5

xi  0, i = 15

a- Tìm bài toán đối ngẫu của bài toán (D)

b- Tìm phương án tối ưu của bài toán (D)

c- Từ bảng đơn hình tối ưu của bài toán (D). Hãy tìm phương án tối ưu cho bài toán đối ngẫu ở câu a.

3- Xét bài toán quy hoạch tuyến tính

min w = -2x1 - x4

x1 + x2 + 5x3 = 20

(D)x2 + 2x4  5

x1 + x2 - x3  8

xi tùy ý (i=1 4)

Tìm bài toán đối ngẫu (P) của bài toán (D). Từ bài toán (P) hãy chỉ ra rằng (P) không tồn tại phương án tối ưu do đó (D) cũng tồn tại phương án tối ưu.

4- Cho bài toán quy hoạch tuyến tính

(D) max z = 2x 1 + 4x 2 + x 3 + x 4 x 1 + 3x 2 + x 4 ≤ 1 − 5x 2 − 2x 4 ≤ 3 4x 2 + 4x 3 + x 4 ≤ 3 x j ≥ 0 ( j = 1 → 4 ) { { { alignl { stack { size 12{"max"" z"="2x" rSub { size 8{1} } +4x rSub { size 8{2} } +x rSub { size 8{3} } +x rSub { size 8{4} } } {} #alignl { stack { left lbrace x rSub { size 8{1} } +3x rSub { size 8{2} } +x rSub { size 8{4} }<= 1 {} # right none left lbrace - 5x rSub { size 8{2} } - 2x rSub { size 8{4} }<= 3 {} # right none left lbrace 4x rSub { size 8{2} } +4x rSub { size 8{3} } +x rSub { size 8{4} }<= 3 {} # right none left lbrace x rSub { size 8{j} }>= 0" " \( j=1 rightarrow 4 \) {} # right no } } lbrace {}} } {}

1- Tìm bài toán đối ngẫu của bài toán đã cho.

2- Giải bài toán đã cho rồi suy ra kết quả của bài toán đối ngẫu.

5- Cho bài toán quy hoạch tuyến tính

(D) max z = 27x 1 + 50 x 2 + 18 x 3 x 1 + 2x 2 + x 3 ≤ 2 − 2x 1 + x 2 − 2x 3 ≤ 4 x 1 + 2x 2 − 4x 3 ≤ − 2 x 1 , x 2 tuú ý, x 3 ≤ 0ỳ { { { alignl { stack { size 12{"max"" z"="27x" rSub { size 8{1} } +"50"x rSub { size 8{2} } +"18"x rSub { size 8{3} } } {} #alignl { stack { left lbrace x rSub { size 8{1} } +2x rSub { size 8{2} } +x rSub { size 8{3} }<= 2 {} # right none left lbrace - 2x rSub { size 8{1} } +x rSub { size 8{2} } - 2x rSub { size 8{3} }<= 4 {} # right none left lbrace x rSub { size 8{1} } +2x rSub { size 8{2} } - 4x rSub { size 8{3} }<= - 2 {} # right none left lbrace x rSub { size 8{1} } ,x rSub { size 8{2} } "tuú ý, x" rSub { size 8{3} }<= "0ỳ " {} # right no } } lbrace {}} } {}

a- Tìm bài toán đối ngẫu của bài toán đã cho.

b- Giải bài toán đối ngẫu rồi suy ra kết quả của bài toán đã cho.

Questions & Answers

what is phylogeny
Odigie Reply
evolutionary history and relationship of an organism or group of organisms
AI-Robot
ok
Deng
what is biology
Hajah Reply
the study of living organisms and their interactions with one another and their environments
AI-Robot
what is biology
Victoria Reply
HOW CAN MAN ORGAN FUNCTION
Alfred Reply
the diagram of the digestive system
Assiatu Reply
allimentary cannel
Ogenrwot
How does twins formed
William Reply
They formed in two ways first when one sperm and one egg are splited by mitosis or two sperm and two eggs join together
Oluwatobi
what is genetics
Josephine Reply
Genetics is the study of heredity
Misack
how does twins formed?
Misack
What is manual
Hassan Reply
discuss biological phenomenon and provide pieces of evidence to show that it was responsible for the formation of eukaryotic organelles
Joseph Reply
what is biology
Yousuf Reply
the study of living organisms and their interactions with one another and their environment.
Wine
discuss the biological phenomenon and provide pieces of evidence to show that it was responsible for the formation of eukaryotic organelles in an essay form
Joseph Reply
what is the blood cells
Shaker Reply
list any five characteristics of the blood cells
Shaker
lack electricity and its more savely than electronic microscope because its naturally by using of light
Abdullahi Reply
advantage of electronic microscope is easily and clearly while disadvantage is dangerous because its electronic. advantage of light microscope is savely and naturally by sun while disadvantage is not easily,means its not sharp and not clear
Abdullahi
cell theory state that every organisms composed of one or more cell,cell is the basic unit of life
Abdullahi
is like gone fail us
DENG
cells is the basic structure and functions of all living things
Ramadan
What is classification
ISCONT Reply
is organisms that are similar into groups called tara
Yamosa
in what situation (s) would be the use of a scanning electron microscope be ideal and why?
Kenna Reply
A scanning electron microscope (SEM) is ideal for situations requiring high-resolution imaging of surfaces. It is commonly used in materials science, biology, and geology to examine the topography and composition of samples at a nanoscale level. SEM is particularly useful for studying fine details,
Hilary
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply
<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




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