Bài toán đơn hình mở rộng giải bài toán m năm 2024

Related documents

• Bài 2 - Đề cương bài giảng
• GIAO Trinh XSTK MỚI NHẤT
• Bài tập môn KTTC 2 - Copy
• Bài tập chia TK - cho sinh viên
• ĐLDL - Bài 3. Đề cương chi tiết bài giảng
• Giải pháp nhằm giảm tình trạng thất nghiệp

Preview text

BÀI TẬP SÁCH GIÁO TRÌNH

BÀI 2. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN

QUY HOẠCH TUYẾN TÍNH

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

Lời giải:

Hệ số Cơ sở

J

Phương

án

-2 5 -4 -1 5 0

x 6

-2 A 1 32 1 6 0 -2 -9 0

-4 A 3 30 0 2 1 [1] 3 0

0 A 6 36 0 3 0 0 1

-184 0 -25 0 1  1 0

-2 A 1 92 1 10 2 0 -3 0

-1 A 4 30 0 2 1 1 3

0 A 6 36 0 3 0 0 1

-214 0 -27 -1 0 -2 0

Đ/S:

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

Lời giải: F[x] = 7x 1 - x 2 - 3x 3 - x 4 - x 5 - 6x 6 → min

Bài toán nhận x 0 = [ 0; 2; 0; 9; 15; 0 ] là phương án cận biên với cơ sở đơn vị

J = [ A

5

; A

4

; A

2

]. Bảng đơn hình xuất phát như sau:

Hệ số

Cj

Cơ số j

Phương

án

7 -1 -3 -1 -1 -

X 1 X 2 X 3 X 4 X 5 X 6

-1 A

5

15 1 0 -1 0 1 -

-1 A 4 9 -2 0 0 1 0 -

-1 A 2 2 -3 1 2 0 0 [4]

-26 -3 0 2 0 0 5↑

1 2 3 4 5 1 2 4 5 2 3 4 5 2 5 6

[ ] 2 5 4 5 min

6 2 9 32

2 3 30

3 36

j 0 , 1, 6

f x x x x x x

x x x x

x x x x

x x x

x j

      

    



    

   



  



c J x 1 x 2 x 3 x 4 x 5

x  [92, 0, 0,30, 0,36] , f min  214

1 2 3 4 5 6 1 3 5 6 1 4 6 1 2 3 6

[ ] 7 3 6 max

15

2 2 9

3 2 4 2

j 0 , 1, 6

f x x x x x x x

x x x x

x x x

x x x x

x j

       

    

    



    



  



-1 A 5 31/2 [1/4] 1/4 -1/2 0 1 0

-1 A 4 10 -7/2 1/2 1 1 0 0

-6 A

6

1/2 -3/4 1/4 1/2 0 0 1

-57/2 3/4↑ -5/4 -1/2 0 0 0

7 A 1 62 1 1 -2 0 4 0

-1 A

4

227 0 4 -6 1 14 0

-6 A

6

47 0 1 -1 0 3 1

-75 0 -2 1 0 -3 0

Ở bảng đơn hình thứ 3, { } nên hàm

mục tiêu không bị chặn.

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

Lời giải:

Hệ số Cơ sở

J

Phương

án

3 2 -3 -15 0

3 A 1 7 1 0 [1] -3 0

2 A 2 1 0 1 -2 -2 0

0 A 5 16 0 0 1 1

23 0 0 2 2 0

-3 A 3 7 1 0 1 -3 0

2 A 2 15 2 1 0 -8 0

0 A 5 9 -1 0 0 [4] 1

9 -1 0 0 8 0

-3 A 3 55/4 1/4 0 1 0 3/

2 A 2 33 0 1 0 0

-15 A 4 9/4 -1/4 0 0 1 1/

-9 0 0 0 0 -

Đ/S: x = [0,33,55/4,9/4,0]. F[x] = -9.

Tập phương án

trong đó x = [0,33,55/4,9/4,0]là phương án tối ưu ở bảng đơn hình

và điều kiện =

z 1  [1;0; 1/ 4;1/ 4;0]  tz 1  [ ;0;t t / 4; / 4;0]t gọi là phương vô hạn tối ưu

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

1 2 3 4

1 3 4

2 3 4

3 4

[ ] 3 2 3 15 min

3 7

2 2 1

16

j 0 , 1, 4

f x x x x x

x x x

x x x

x x

x j

    

   



   

  



  



c J x 1 x 2 x 3 x 4 x 5

*

.

k

x  x t z

0

0 0 min , , 0

j

jk

jk

x

t j J x

x



 

       

 

x *  [ , 33, 55 / 4t  1/ 4 , 9 / 4t 1/ 4 , 0], 0 t  t 55

0

0

-

1

1

1

1

-

0

1

1

1

0

0

1

0

0

-

-

[1]

0

1

-

0

1

0

0

0

1

0

-1 -1 0 0 0 1 -1 0 0

0

-

-

2

1

1

0

-

0

2

1

1

0

0

1

0

0

-

0

1

0

0

-

0

1

0

0

1

1

0

-2 0 -1 0 0 0 0 0 -

Ở bảng đơn hình thứ 2 ta có , j =̅ ̅̅̅̅ nên bài toán có phương án tối ưu là :

̅ [ ] và giá trị tối ưu : [ ]

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

Lời giải: Bảng đơn hình xuất phát như sau:

Hệ số Cơ sở

J

Phương

án

1 -1 1 1 1 -

x 6

1 A 4 5 1 0 1 1 0

-1 A 2 2 2 1 -2 0 0 1

1 A 5 2 1 0 1 0 1 [2]

7 -1 0 3 0 0 5

1 A 4 2 -1/2 0 -1/2 1 -3/2 0

-1 A 2 1 3/2 1 -5/2 0 -1/2 0

-1 A 6 1 1/2 0 [1/2] 0 1/2 1

0 -7/2 0 1/2 0 -5/2 0

1

-

1

4

A

A 2

3

A

3

6

2

0

4

1

0

1

0

0

0

1

1

0

0

-

2

1

1

5

1

-1 -4 0 0 0 -3 -

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp [M]:

Lời giải:

Hệ số Cơ sở

J

Phương án

2 4 -2 0 M M

x 6

1 2 3 4 5 6 1 3 4 6 1 2 3 6 1 3 5 6

[ ] min3 52 2 22 2j 0 , 1, 6f x x x x x x xx x x xx x x xx x x xx j                    

c J x 1 x 2 x 3 x 4 x 5

f

f

1 2 3 1 2 3 1 2 3 1 2 3

[ ] 2 4 2 min2 272 2 5018j 0 , 1,f x x x xx x xx x xx x xx j              

c J x 1 x 2 x 3 x 4 x 5

M A 5 27 1 -2 1 0 1 0

M A 6 50 2 1 [2] 0 0 1

0 A 4 18 1 -1 -1 1 0 0

77M 3M-2 -M-4 3M+2 0 0 0

M A 5 2 0 -5/2 0 0 1

-2 A 3 25 1 ½ 1 0 0

0 A 4 43 2 -1/2 0 1 0

2M-50 -4 -5/2M-5 0 0

Từ bảng đơn hình thứ 2 có x=[0,0,25,43,2,0], có biến giả x 5  2 >.

Vậy bài toán không có PATU

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp [M]:

Lời giải: F[x] =

Vì bài toán chưa ở dạng chuẩn, ma trận hệ số A mới có một vecto đơn vị. Thêm hai biến

giả [với M là số dương tùy ý] ta có bài toán mở rộng [M] của bài toán đã cho là:

F[x]=

{ ⃗⃗⃗⃗⃗⃗

Bài toán [M] là bài toán dạng chuẩn với cơ sở đơn vị { }.Ta có bảng đơn hình:

Hệ số Cơ sở Phương án

-3 -1 3 M M

-3 2 1 2 -1 0 0

M 5 0 -10 [5] 1 0

M 4 0 -3 2 0 1

9M - 6 0 -13M-5 7M 0 0

-3 3 1 0 0 1/

3 1 0 -2 1 1/

M 2 0 [1] 0 -2/

2M -6 0 [M -5] 0

-3 3 1 0 0

3 5 0 0 1

-1 2 0 1 0

F[x] 4 0 0 0

Ở bảng 3 dấu hiệu tối ưu xuất hiện nên bài toán [M] có PATU [ ] và F[x] =

\=>

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp [M]:

1 2 3 1 2 3 2 3 2 3

[ ] 3 3 m ax

2 2

10 5 5

3 2 4

j 0 , 1,

f x x x x

x x x

x x

x x

x j

   

   



   

   



  



J án x 6

0 A 4 6 1 1 1 1 0

M A 5 1 2 [3] -1 0 1 0

M A 6 0 1 2 -1 0 0 1

M 3M 5M -2M 0 0 0

0 A 4 17/3 1/3 0 0 1 0

5 A 2 1/3 2/3 1 -1/3 0 0

M A 6 -2/3 -1/3 0 1/3 0 1

0 0

Đ/s x=[0;1;2;3]; f[x]=

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp [M]:

1 2 3 4 5 6 1 2 3 5 1 2 3 6 1 2 3 4 j

f [x] x x x 0x Mx Mx min

2x x x x 2

4x x 2x x 1

x 2x 4x x 4

x 0 ; j 1, 6; M 0

      

    



    

 

   



   



Hệ số Cơ sở

J

Phươngán

1 1 -1 0 M M

x 6

M A 5 2 2 -1 1 0 1 0

M A 6 1 [4] -1 2 0 0 1

0 A 4 4 1 2 -4 1 0 0

3M 6M -2M 3M 0 0 0

M A 5 3/2 0 -1/2 0 0 1

1 A 1 1/4 1 -1/4 [1/2] 0 0

0 A 4 15/4 0 -1/2 -9/2 1 0

0 -M/2-1/4 1/2 0 0

Đ/s x=[0;0;1/2;6;3/2;0]

1. Giải bài toán quy hoạch tuyến tính sau bằng phương pháp [M]:

Lời giải: F[x] = 7x 1 + x 2 4x 3 + Mx 6 + Mx 7 min

6x 1 4x 2 5x 3 + x 4 = 20

x 1 + 2x 2 + x 3 +x 6 = 8

c J x 1 x 2 x 3 x 4 x 5

1 2 3 1 2 3 1 2 3 1 2 3

[ ] min

2 2

4 2 1

2 4 4

j 0 , 1,

f x x x x

x x x

x x x

x x x

x j

   

   



   



  



  



c J x 1 x 2 x 3 x 4 x 5

1 2 3 1 2 3 1 2 3 1 2 3

[ ] 7 4 min 6 4 5 20 2 8 3 2 8 j 0 , 1, f x x x x x x x x x x x x x x j                        

3x 1 + x 2 + x 3 x 5 +x 7 = 8

xj 0, j =1÷

Bài toán [M] là bài toán dạng chuẩn, với hệ vecto cơ sở là J = {A

4

, A

6

,A

7

}.

Lập bảng đơn hình xuất phát như sau:

Hệ số

Cj

Cơ sở

J

Phương

án x 0

7 1 -4 0 0 M M

x 1 x 2 x 3 x 4 x 5 x 6 x 7

0 A

4

20 6 -4 -5 1 0 0 0

M A 6 8 1 2 [1] 0 0 1 0

M A

7

8 -3 2 3 0 -1 0 1

F[x] 16M M-7 4M-1 2M+4 0 -M 0 0

0 A 4 60 11 6 0 1 0

-4 A

3

8 1 2 1 0 0 0

M A 7 0 -4 0 0 0 -1 1

F[x] -32 -4M-11 -9 0 0 -M 0

Ở bảng đơn hình 2, dấu hiệu tối ưu xuất hiện Δj 0, j= 1÷7 nên bài toán mở rộng [M] có

phương án tối ưu x =[ 0,0,8,60], fmin = -32.

1. Cho bài toán



1 3 4 5 2 3 4 1 3 4 6 1 3 4 7

2 3 12

2 14

4 9 36

3 2 5 23

x x x x

x x x

x x x x

x x x x

    



   



    

    

a] Chứng tỏ là phương án cực biên

b] Giải bài toán bằng phương pháp đơn hình bằng PACB ở ý a].

1 1 3 4 5 1 2 3 4 2 2 3 4 5 6 3 3 1 3 4 5 7 4 4 1

1 3 1

6

2 2 2 2

2 14

3 2 12 4

1 1 3

5 3

2 2 2

d

x x x x d

x x x d d

x x x x d d d

x x x x d d d



     



    



       



       



Hệ số Cơ sở Phương

án

2 -5 -4 2 0 0 0

x 6 x 7

2 A 1 6 1 0 1/2 -3/2 -1/2 0 0

-5 A 2 14 0 1 1 2 0 0

0 A 6 12 0 0 -1 -3 2 1 0

1 2 3 4 1 3 4 2 3 4 1 3 4 1 3 4

[ ] 2 5 4 2 min

2 3 12

2 14

4 9 36

3 2 5 23

j 0 , 1, 4

f x x x x x

x x x

x x x

x x x

x x x

x j

    

   



  



   



   



  

x 0 [1, 4,10, 0]

x 1 x 2 x 3 x 4 x 5

Kết luận: Hàm mục tiêu không bị chặn

1. Cho bài toán

1 2 3 4 5 2 4 5 6 1 2 4 5 2 4 5 7 2 3 5

####### : [ ] [ ] 2 3 4 min

####### 3 4 3 34

####### 4 2 24

####### 7 2 3 12

####### 1 1

####### 5

####### 2 2

####### j 0 1,

####### F x f x x x x x x

####### x x x x

####### x x x x

####### x x x x

####### x x x

####### x j

#######         

#######      

#######     

####### 

#######     

####### 

#######     

####### 

####### 

#######   

a] Giải bài toán bằng phương pháp đơn hình.

Hệ

số

Cơ sở Phương

án

-1 1 -2 -3 4 0 0

x 6 x 7

0 A 6 34 0 3 0 -4 3 1 0

-1 A 1 24 1 4 0 1 -2 0

0

-

A 7

3

A

12

5

0

0

7

1/

0

1

2

0

-

-1/

0

0

1

0

-29 0 -6 0 2 -1 0

0 A 6 58 0 17 0 0 -3 1

-1 A 1 18 1 ½ 0 0 -1/2 0 -1/

-3 A 4 6 0 7/2 0 1 -3/2 0 1/

-2 A 3 5 0 ½ 1 0 -1/2 0 0

-46 0 -11 0 0 2 0 -

 5  2, aj 5  0 vậy hàm mục tiêu không bị chặn

b] Giải bài toán khi có thêm điều kiện .Từ bảng 2, ta xác định phương

giảm trị số hàm mục tiêu z 5  [1/2;0,1/2;3/2;1;3] và phương án cực biên

x = [18;0;5;6;0;58]. Xét các phương án dạng:

x t [ ]  x  tz 5 

[18+t/2;0;5+t/2;6+3t/2;t;58+3t ] [*]

Khi đó f [ [ ]]x t  f [ ]x  t 5 , t 0 hay -50=-46-2t suy ra t=2 thay vào [*] ta được

phương án x t[ ] =[19;0;6;9;2].

Vậy trị số hàm mục tiêu sẽ đạt tại phương án x=[19;0;6;7;2].

1. Giải bài toán bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

1 2 3 4 1 3 4 5 1 2 3 5 2 3 5

[ ] 4 2 3 min

3 16

2 3 2 2 52

2 24

j 0 , 1,

f x x x x x

x x x x

x x x x

x x x

x j

    

    

    



   



  



1 3 4 5 1 2 3 5 6 2 3 5 7

3 16

2 3 2 2 52

2 24

j 0 , 1, 7

x x x x

x x x x x

x x x x

x j

    

     



    



  



Hệ số Cơ sở

J

Phương

án

4 -2 -1 -3 0 0 0

x 6 x 7

x 1 x 2 x 3 x 4 x 5

f [ ]x  50

x t [ ]

f [ ]x   50

c J x 1 x 2 x 3 x 4 x 5

-3 A 4 16 1 0 1 1 3 0

0 A 6 52 2 -3 -2 0 2 1 0

0 A 7 24 0 [1] 1 0 -2 0 1

-48 -7 2 -2 0 -9 0 0

-3 A 4 16 1 0 1 1 3 0

0 A 6 124 2 0 1 0 -4 1 3

-2 A 2 24 0 1 1 0 -2 0 1

-96 -7 0 -4 0 -5 0 -

Đ/s: PATU X

####### 0

[0;24;0;16;0;124;0], fmin =-

1. Giải bài toán bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

1 2 3 1 2 3 1 2 3 1 2 3 j

f [x] 6x 3x x min

2x 5x x 10

4x 3x 2x 16

2x 4x x 8

x 0 ; j 1,

   

   



   



  



  



1 2 3 6 5 1 2 3 4 1 2 3 5 1 2 3 6 j

f [x] 6x 3x x M[x x ] min

2x 5x x x 10

4x 3x 2x x 16

2x 4x x x 8

x 0 ; j 1, 6, M 0

     

    



    

 

   



   



Hệ số Cơ sở J Phương án

6 3 1 0 M M

x 6

0 A 4 10 2 5 1 1 0

M A 5 16 4 -3 2 0 1 0

M A 6 8 2 4 1 0 0

24M 6M-6 M-3 3M-1 0 0 0

0 A 4 2 0 -1 0 1 0

M A 5 0 0 -11 0 0 1

6 A 1 4 1 2 1/2 0 0

24 0 -11M+9 2 0 0

0 A 4 2 0 -1 0 1 0

M A 5 0 0 -11 0 0 1

1 A 3 8 2 4 1 0

8 -4 -11M+1 0 0 0

Đ/s: PATU X 0 [0;0;0;8;], fmin =

1. Giải bài toán bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

1 2 3 1 2 3 1 2 3 1 2 3 j

f [x] 2x x x max 4x x 2x 12 2x 2x x 10 x 2x x / 2 10 x 0 ; j 1,                       

1 2 3 6 7 1 2 3 4 6 1 2 3 5 1 2 3 7 j

F[x] 2x x x M[x x ] min 4x x 2x x x 12 2x 2x x x 10 x 2x x / 2 x 10 x 0 ; j 1, 7                            

Hệ số

Cơ

sở

J

Phương

án

2 1 -1 0 0 M M

x 6 x 7

M A 6 12 -4 -1 2 -1 0 1 0

c J x 1 x 2 x 3 x 4 x 5

c J x 1 x 2 x 3 x 4 x 5