Bài giảng Toán cao cấp 1: Chương 5b

16/04/2017

Ví dụ 1

CHƯƠNG 5b





2,5



max

  f x



• Vậy ta có mô hình bài toán:  f x x x , 1 3

x 1

x 2

x 3

0,04



0,06



0,05



500

x 3

0,07



0,02

300

QUY HOẠCH TUYẾN TÍNH HAI BIẾN

x 1 x 1 0

x 2 x 3 1, 2,3







 

    

• Đây là bài toán quy hoạch tuyến tính 3 biến, tìm

giá trị lớn nhất của hàm mục tiêu.

Ví dụ 1

Ví dụ 2

• Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh, bánh thập cẩm và bánh dẻo. Lượng nguyên liệu đường, đậu cho một bánh mỗi loại, lượng dự trữ nguyên liệu, tiền lãi cho một bánh mỗi loại được cho trong bảng sau:

• Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡng đạm, đường, khoáng cho một loại gia súc tương ứng là 90g, 130g, 10g. Cho biết hàm lượng các chất dinh dưỡng trên có trong 1g thức ăn A, B, C và giá mua 1kg thức ăn mỗi loại được cho trong bảng sau:

• Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần sản xuất sao cho không bị động về nguyên liệu mà lãi đạt được cao nhất.

• Hãy lập mô hình toán học của bài toán xác định khối lượng thức ăn mỗi loại phải mua để tổng số tiền chi cho mua thức ăn ít nhất nhưng đáp ứng được nhu cầu dinh dưỡng mỗi ngày.

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

Ví dụ 1

Ví dụ 3

• Gọi x1,x2,x3 lần lượt là số bánh đậu xanh, bánh thập

cẩm, bánh dẻo cần phải sản xuất.

• Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm là bàn, ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và giá bán mỗi sản phẩm mỗi loại ước tính trong bảng sau:

• Điều kiện: xj ≥ 0 = 1,2,3 • Tiền lãi thu được (ngàn đồng)





2,5

  f x



 f x x x , 1 3

x 1

x 2

x 3

0,04

0,06



500

• Hãy lập mô hình toán học của bài toán xác định số sản phẩm mỗi loại cần phải sản xuất sao cho không bị động trong sản xuất và tổng doanh thu đạt được cao nhất, biết rằng cơ sở có số lao động tương đương với 500 ngày công, số tiền dành cho chi phí sản xuất là 40 triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6.

• Lượng đường sử dụng và điều kiện:   x x 0,05 1 3 • Lượng đậu sử dụng và điều kiện:  0,07

0,02



300

x 3

x 1

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

16/04/2017

Ví dụ 4

• Bài toán sau có dạng chính tắc:

260



120

600



max



x 3

• Bài toán lập kế hoạch sản xuất • Một trại cưa các khúc gỗ thành các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng trong xây dựng. Giả sử, đối với:





500

x 1 

• Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m

ván

x 2 x 3 

250



40000

x 2 

x 2

x 3

x 1 



x x 1 2 x x x , 1 2 3

x  1  100     

• Ván xây dựng cần 3 giờ để cưa và 3 giờ để bào 10m ván • Máy cưa làm việc tối đa 8 giờ trong ngày và máy bào làm việc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m ván thành phẩm là 120 (ngàn đồng) và lợi nhuận của 10m ván xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất.

Dạng ma trận của bài toán QHTT







Bài toán QHTT tổng quát     ... 1 min (max)

  f x

c x 2 2

c x 1 1

• Xét bài toán QHTT dạng:





  ...



min (max)

c x 1 1

c x 2 2

c x n n



  ...



1, 2,..,

  2



a x 1 1 i

a x 2 2 i

a x in n

 b i i





  ...

c x n n          



  ...



  f x a x 11 1 a x 21 1

b 1 b 2

a x 12 2 a x 22 2

a x 1 n n a x 2 n n



1, 2,...,

  3

  ...





a x 2 2 m

a x mn n

b m

tuy y

     

    

    ..........................................    x

a x 1 1 m  0

(1) Hàm f(x) gọi là hàm mục tiêu (2) là hệ ràng buộc chính (3) là hệ ràng buộc dấu (2) Và (3) gọi chung là hệ ràng buộc của bài toán

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

Dạng ma trận của bài toán QHTT

Bài toán dạng chính tắc





min (max)

 f x



c x j



...

a 1

 j 1

...



a 12 a a 2 22 n ....................

b 1 b 2 ...

x 1 x 2 ...

c 1 c 2 ...



 b (i 1,m)

a x ij



 j 1

...

a m 1

a m

a mn

b m

x n

c n

     

     

     

     

     

     

• Đặt: a  11  a  21    

      

• Các ràng buộc chính đều là phương trình • Các ẩn đều không âm

 0 (j 1,n)

• Ta có dạng ma trận của bài toán QHTT:

     x 

T   c x

 min max



Ax b     x

Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài toán dạng chính tắc tương đương theo nghĩa trị tối ưu của hàm mục tiêu trong hai bài toán là trùng nhau và từ phương án tối ưu của bài toán này suy ra phương án tối ưu của bài toán kia

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

16/04/2017

Các loại phương án

Đưa bài toán về dạng chính tắc

• Bước 2. Kiểm tra điều kiện dấu các ẩn số

 

x 

• Nếu có ẩn dạng:

ta đổi biến:

x i

ix 

• Định nghĩa. Vec tơ ∈ thỏa tất cả các ràng buộc của bài toán quy hoạch tuyến tính được gọi là phương án chấp nhận được.





• Nếu ẩn xi có dấu tùy ý ta đổi biến:





x i

• Định nghĩa. Phương án chấp nhận được làm cho hàm mục tiêu có giá trị lớn nhất (nếu là bài toán max) hay nhỏ nhất (nếu là bài toán min) thì được gọi là phương án tối ưu (PATU).

• Chú ý: • Các ẩn mới và các ẩn phụ đều không âm. • Hệ số của các ẩn phụ trong hàm mục tiêu là 0. • Khi tìm được PATU của bài toán dạng chính tắc ta chỉ cần tính giá trị của các ẩn ban đầu và bỏ đi các ẩn phụ thì sẽ được PATU của bài toán dạng tổng quát đã cho.

Ví dụ

• Cho bài toán QHTT:

• Đưa bài toán sau về dạng chính tắc:





min



120



100



max

x 1

x 2

  x 3

x 1

x 2





x 3

x 2



x 2 





  6



x 3

x 2 x 2

  f x  x 2  1  5  x  1   x  1



x 3 x 3 2 x 2

  f x  x 4  1  x  1  2  x  1   x  1

• Trong các phương án sau phương án nào là

phương án chấp nhận được.



u 1

1     2  

2     2  

1     3  

2     1  

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

Đưa bài toán về dạng chính tắc

Tính chất của tập phương án • Định nghĩa. Đoạn thẳng nối hai điểm x1 và x2 được

• Bước 1. Kiểm tra ràng buộc chính

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến



x R x



, 0

  

   1

 

 x 1

x 2



  ...



định nghĩa: 

 1

a x 1 1 i

a x in n

b i

• Ràng buộc dạng nhỏ hơn: a x • 2 2 i • Ta cộng thêm ẩn phụ:



  ...





a x 1 1 i

a x in n

x  n k

b i

a x 2 2 i • Ràng buộc dạng lớn hơn:

• Nhận xét • Nếu = 0 chúng ta có x2, = 1 chúng ta có x1. • Những điểm thuộc đoạn thẳng với 0 < < 1 gọi là



  ...



các điểm trong của đoạn thẳng

a x 1 1 i

a x 2 2 i

a x in n

b i

• Ta trừ đi ẩn phụ:

• x1, x2 gọi là các điểm biên của đoạn thẳng.



  ...





a x 1 1 i

a x 2 2 i

a x in n

x  n k

b i

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

16/04/2017

Tính chất của tập phương án

Tập lồi và tính chất

• Định lý. Cho x1 và x2 là hai phương án chấp nhận được của bài toán QHTT. Điểm = 1 + 1 − 2 với 0 ≤ ≤ 1 thuộc đoạn thẳng nối hai điểm x1 và x2 .

• Tập S gọi là tập lồi nếu với hai điểm phân biệt bất kỳ x1 và x2 thuộc S thì đoạn nối hai điểm x1 và x2 cũng nằm trong tập S.

Tập lồi

• Khi đó: • i) x cũng là phương án chấp nhận được • ii) Nếu các f(x1)=f(x2) thì f(x)=f(x1)=f(x2) • iii) Nếu f(x1)

Không phải Tập lồi

Ví dụ

Định lý



  y

max

• Xét bài toán QHTT    y

 f x y , x

• Tập S tất cả các phương án chấp nhận được của bài toán quy hoạch tuyến tính dạng chính tắc là một tập lồi.







 x Ax b x





 0

x y ,



    

• Có tập phương án được biểu

diễn như hình bên

• Ta thấy x1=(0,5; 2) và x2=(2;0,5) là các phương án chấp

nhận được.

• Điểm = 1 + 1 − 2 với =2/3 cũng là phương

án chấp nhận được.

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

Ví dụ

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

7/3)

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

• Hai phương án chấp nhận được và x1=(0,5; x2=(2;1/3) có cùng giá trị hàm mục tiêu là 9.

• Khi đó phương án x định

bởi:



   1

 

 x 1

x 2

2 3

   

   • Cũng có giá trị hàm mục tiêu

là 9.

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

16/04/2017

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

Phương pháp đồ thị

• Định lý. Điểm x của tập lồi S được gọi là điểm cực biên của S nếu x không là tổ hợp lồi của hai điểm của S khác x.

• Dùng cho bài toán quy hoạch tuyến tính 2 biến • Xét bài toán quy hoach tuyến tính : 2





  f x

 min max



c x j



• Nhận xét: • Nếu có x1, x2 thuộc S sao cho

 1





   1



 x 1

  x , 2



a x ij

b i



• Thì:



 1 j x



x 1

x 2

    

A, B, C, D, E là các điểm cực biên

Tính chất tập phương án

Phương pháp đồ thị

• Tập hợp các phương án của một bài toán quy

• Biểu diễn các ràng buộc lên đồ thị Oxy. • Xác định phần được giới hạn bởi các ràng buộc là tập

hoạch tuyến tính là một tập lồi đa diện.

phương án.

• Xác định các điểm cực biên (đỉnh) của tập phương án

thỏa mãn các ràng buộc.

• Nếu tập hợp lồi đa diện này không rỗng và bị chặn thì đó là một đa diện lồi. Số điểm cực biên của nó là hữu hạn.

• Xác định giá trị của hàm mục tiêu tại các điểm cực

biên.

• So sánh và suy ra phương án tối ưu

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

Phương án cực biên

Ví dụ 1

• Giải bài toán QHTT sau:

   

x 2

x 1

• Định nghĩa. Điểm cực biên của tập các phương án S trong bài toán QHTT gọi là phương án cực biên.





 x 2

x 1





x 2

x 1

• Tính chất. • Số phương án cực biên của tập phương án S



min   1   2   3

trong bài toán QHTT là hữu hạn

x 2 0,



x 2

 f x x 1 2  2    x   1   x  1

• Nếu bài toán QHTT dạng chính tắc có phương án tối ưu thì nó sẽ có một phương án cực biên là phương án tối ưu.

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

16/04/2017

Ví dụ 1

Ví dụ 3

• Biểu diễn đồ thị các bất đẳng thức lên hệ trục tọa độ ta được miền các phương án là hình ngũ giác ABCDE. Các điểm có tọa độ như sau A(0,0); B(0,2); C(1,4); D(4,1); E(2,0) là các điểm cực biên. lần lượt thay các cực biên vào hàm mục tiêu ta có f(A) = 0; f(B) = 2; f(C) = 3; f(D) = -3; f(E) = -2.

• Vậy phương án tối ưu x*=(4,1) tại đó hàm mục tiêu đạt giá trị Min

• Một xí nghiệp có thể sử dụng tối đa 510 giờ máy cán, 360 giờ máy tiện, 150 giờ máy mài để chế tạo 3 loại sản phẩm A, B, C. Để chế tạo một đơn vị sản phẩm A cần 9 giờ máy cán, 5 giờ máy tiện, 3 giờ máy mài; 1 đơn vị sản phẩm B cần 3 giờ máy cán, 4 giờ máy tiện; 1 đơn vị sản phẩm C cần 5 giờ máy cán. 3 giờ máy tiện, 2 giờ máy mài. Mỗi sản phẩm A trị giá 48 ngàn đồng, mỗi sản phẩm B trị giá 16 ngàn đồng, mỗi sản phẩm C trị giá 27 ngàn đồng. • Vấn đề đặt ra là xí nghiệp cần chế tạo bao nhiêu đơn vị sản phẩm mỗi loại để tổng giá trị sản phẩm xí nghiệp thu được là lớn nhất, với điều kiện không dùng quá số giờ hiện có của mỗi loại máy.

Ví dụ 2

Tìm PACB bằng pp Đại số

• Xét bài toán QHTT dạng chính tắc:

Tc  

x min (max)



• Một xí nghiệp đóng tàu đánh cá cần đóng 2 loại tàu 100 mã lực và 50 mã lực. Trong xí nghiệp có 3 loại thợ chính quyết định sản lượng kế hoạch. Thợ rèn có 2000 công, thợ sắt có 3000 công, thợ mộc có 1500 công. Định mức lao động của mỗi loại tàu được cho trong bản:

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

100 mã lực

50 mã lực

  f x A . x    x 0

Thợ sắt (3000)

150

70 Thợ rèn (2000)

120

50

• A là ma trận cấp m.n (giả sử m≤n) • Ma trận A có hạng là m (có m dòng độc lập

Thợ mộc (1500)

80

40

tuyến tính)

• Hỏi xí nghiệp nên đóng tàu mỗi loại bao nhiêu để đạt

tổng số mã lực cao nhất?

Ví dụ 2

Nghiệm cơ bản

• Phương trình A.x=b được viết lại dạng:

• Gọi x1, x2 lần lượt là số tàu 100 mã lực và 50 mã

lực cần đóng

  ...



 x A x A 1 1 2

x A n n

• Ta cần tìm x1, x2 sao cho: f(x)=100x1+50x2

max



x70



3000



x50



2000

• Chọn m cột của ma trận A độc lập tuyến tính • Giả sử ta có các cột A1, A2, …, Am • Cho các biến tương ứng với các cột còn lại bằng 0 • Giải phương trình ràng buộc với các biến còn lại • Nghiệm tìm được kết hợp với các biến đã cho bằng 0

1 

x40

1500

2 

tạo thành nghiệm cơ bản của bài toán.

1 

2 0

x,0



• Điều kiện: 150   120   x80   

Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến

16/04/2017

Ví dụ

Phương án cực biên

• Cho hệ phương trình tuyến tính 4 ẩn như sau:





x 2

• Nghiệm cơ bản thỏa mãn điều kiện các thành phần đều không âm gọi là phương án cực biên của bài toán. • PACB có đúng m thành phần dương gọi là PACB không

suy biến



x 3 



x 1 x 1

x 2

x 4

  5 

• PACB có ít hơn m thành phần dương gọi là PACB suy

biến.

• Tìm tất cả các nghiệm cơ bản

• Định lý. Nếu x=(x1,x2,…,xn) là PACB của tập các phương án S= {A.x=b, x≥0} thì các cột của A tương ứng với xj>0 là độc lập tuyến tính.