Bài giảng Toán tài chính - Chương 5b: Quy hoạch tuyến tính hai biến

CHƯƠNG 5B

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

VÍ DỤ 1

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:

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.

VÍ DỤ 1

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. Đ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

Lượng đường sử dụng và điều kiện: 

0,06



500

x 2

x 1

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

0,02



300

x 3

x 1

VÍ DỤ 1





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

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Ụ 2

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 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.

VÍ DỤ 3

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:

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.

VÍ DỤ 4

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:

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

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.

min (max)

  ...





  f x

  1

BÀI TOÁN QHTT TỔNG QUÁT  c x 2 2

c x 1 1



  ...



1, 2,..,

  2



a x 1 1 i

a x 2 2 i

a x in n

 b i i

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



1, 2,...,

  3

tuy y

     

    

(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

DẠNG MA TRẬN CỦA BÀI TOÁN QHTT

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

min (max)





  ...



c x 1 1

c x 2 2

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

  ...





a x 2 2 m

a x mn n

b m

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

a x 1 1 m  0

DẠNG MA TRẬN CỦA BÀI TOÁN QHTT

Đặt:

...

a 1

a 11 a

a 12 a

...



b 1 b 2 ...

x 1 x 2 ...

c 1 c 2 ...

n 22 2 ....................

...

b m

x n

c n

m 1

a m

a mn

     

     

     

     

     

     

      

      

T   c x

Ta có dạng ma trận của bài toán QHTT:   f min max

 Ax b    x 0

BÀI TOÁN DẠNG CHÍNH TẮC:

min (max)





 f x



c x j



j 1 



b (i 1,m) 

a x ij



j 1 

• 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) 

     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 TOÁN DẠNG CHUẨN TẮC

min (max)





 f x



c x j



j 1 

•



b (i 1,m) 

a x ij



j 1 

• Các hệ số tự do bi không âm (bi ≥ 0) Trong ma trận hệ số có đủ m vecto cột đơn vị: e1, e2,…,em

0 (j 1,n) 

     x 



e 1

e 2

e m

...

     

     

     

     

     

     

VÍ DỤ 5

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

260



120

600



max



x 3





500

x 1 

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Í DỤ 6





max

x 1

x 2

x 3

  x 4





x 4 

x 5 



x 6 



x 2 0

x 3 

x 4 1, 2,...,6

x 3  

6 

Xét bài toán QHTT sau:    f x 4  x  1  12 x  1   x  1   x 

Bài toán trên có dạng chính tắc hay chuẩn tắc

VÍ DỤ 6

Ma trận hệ số tự do:

• Ma trận hệ số A: 0

1 0

12 0 1 1

0 1 0 1   1 0 0 1

12 3 6

     

    

     2e

• Ẩn cơ bản thứ nhất là x5. • Ẩn cơ bản thứ 2 là x6. • Ẩn cơ bản thứ 3 là x2.

CÁC LOẠI PHƯƠNG ÁN

Đị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.

Đị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).

VÍ DỤ 7

120



100



max

x 1

x 2



x 2





x 2 x 2

Cho bài toán QHTT:    f x  x 2  1   x 5  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  

PHƯƠNG ÁN CƠ BẢN

,...,



x x , 1 2

Trong bài toán chính tắc. Xét phương án 



x n Hệ vectơ liên kết với phương án





A x | j



 0

Trong đó Aj là vec tơ cột thứ j trong ma trận hệ số Amn Định nghĩa. Phương án cơ bản nếu hệ vecto liên kết với phương án độc lập tuyến tính

Ẩn xj gọi là cơ bản nếu > 0

PACB TRONG BÀI TOÁN CHUẨN TẮC

Cho ẩn cơ bản thứ k bằng hệ số tự do thứ k, còn các ẩn không cơ bản bằng 0, nghĩa là:  6; 0;



x 2

x 4

x 6

x 5

x 1

x 12; 3 Ta được một phương án cơ bản x = (0,6,0,0,12,3) .

Phương án này không suy biến vì có đủ 3 thành phần dương. Đây là phương án cơ bản ban đầu của bài toán.

,0,0,...,0

,...,



Tổng quát, trong bài toán QHTT dạng chuẩn bất kì, khi cho ẩn cơ bản thứ k bằng hệ số tự do thứ k ( k = 1,2,…,m ), còn các ẩn không cơ bản bằng 0, ta được phương án cơ bản ban đầu của bài toán. Nếu sắp xếp lại ta có dạng sau. 



b b 2, 1

b m

ĐƯA BÀI TOÁN VỀ DẠNG CHÍNH TẮC

  ...



a x 1 1 i

a x in n

b i

Bước 1. Kiểm tra ràng buộc chính • 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:



  ...



a x 1 1 i

a x 2 2 i

a x in n

b i

• Ta trừ đi ẩn phụ:



  ...





a x 1 1 i

a x 2 2 i

a x in n

x  n k

b i

ĐƯ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 

x i

ix  Nếu có ẩn dạng: ta đổi biến:









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

x i

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Ụ 8

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





min

x 1

x 2

  x 3





x 3



x 2 



  6

x 3



x 3 x 3 2 x 2

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

VÍ DỤ 8

Đáp án:

min







 x 2

 x 3

x 1

    x 3 







x 4

  x 3

  f x  x 4 1







x 5

x 1



6  3



  6



  3   x 3 0,

x 1 



4   x 3   x 3   x 3  x 0, 3

 x 3



x 1 x 4

 x 2  x 3  x 2  x 2 x 5

        

PHƯƠNG PHÁP HÌNH HỌC (ĐỒ THỊ)

Sinh viên tham khảo thêm lý thuyết sách

College Mathematics for Busines – Raymond A. Barnett

Chương 5 phần Linear Programing

Chỉ dùng cho bài toán quy hoạch tuyến tính 2 biến

PHƯƠNG PHÁP ĐỒ THỊ

Xét bài toán quy hoach tuyến tính :





  f x

 min max



c x j



 1



a x ij

b i



 1

PHƯƠNG PHÁP ĐỒ THỊ

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 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.

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

VÍ DỤ 9. BÀI TOÁN KẾ HOẠCH SẢN XUẤT

Một nhà sản xuất lều sử dụng trên các vùng núi có 2 dòng sản phẩm: tiêu chuẩn và thám hiểm.

Mỗi lều tiêu chuẩn yêu cầu 1 giờ công lao động từ bộ phận cắt và 3 giờ công từ bộ phận lắp ráp.

Mỗi lều thám hiểm đòi hỏi 2 giờ công lao động từ bộ phận cắt và 4 giờ làm việc từ bộ phận lắp ráp.

Số giờ lao động tối đa có sẵn mỗi ngày trong các phòng cắt và lắp ráp lần lượt là 32 và 84.

Nếu công ty thu được mức lợi nhuận $50 cho mỗi lều tiêu chuẩn và 80$ cho mỗi lều thám hiểm, thì mỗi ngày nên sản xuất bao nhiêu lều mỗi loại để tối đa hóa tổng lợi nhuận hàng ngày (giả sử rằng tất cả các lều có thể được bán)?

MÔ HÌNH BÀI TOÁN

Gọi x, y lần lượt là số lều tiêu chuẩn và thám hiểm





y P

 

max



 y

 f x y , x



y y

 

84 0

   x 3 4    0, x 

TẬP PHƯƠNG ÁN

 32  y 4 8  y 0

 x y 2    x 3 4    0, x 

•Ta có thể tính toán được lợi nhuận tại từng điểm nằm trong miền khả thi (feasible region) hay tập phương án

•Tại (x,y)=(12,10) ta có P=1400

•Tại (x,y)=(23,2) ta có P=1310

ĐƯỜNG ĐẲNG LỢI

Gán cho P một giá trị cố định và vẽ đồ thị P=50x+80y trên hệ trục tọa độ Oxy ta có được một đường thẳng. Đường này có tên là constant profit line hay đường đẳng lợi.

Mọi điểm thuộc tập phương án và nằm trên đường này đều cho ta một kế hoạch sản xuất và có cùng lợi ích P như nhau.

Với mỗi giá trị khác nhau của P ta có một đường đẳng lợi khác song song với đường đẳng lợi còn lại, vì có chung hệ số góc. Để thuận tiện ta đưa phương trình đường đẳng lợi về dạng:



  



 5 8

P 80

ĐƯỜNG ĐẲNG LỢI





P 80

 5 8 

P max

max

Lợi nhuận lớn nhất sẽ nằm tại điểm mà đường đẳng lợi xa nhất so với gốc tọa độ nhưng vẫn còn nằm trong miền khả năng.

Trong ví dụ này thì nó chính là điểm (20,6)

Profit max: P=20.50+6.80=1480

Nhận xét. PATU nằm tại các điểm góc (corner points) của tập phương án

VÍ DỤ 10

Đối với tập phương án như hình vẽ

(A) Cho P = x + y. Vẽ đồ thị các đường đẳng lợi thông qua các điểm (5, 5) và (10, 10). Đặt đường thẳng dọc theo đường có lợi nhuận nhỏ hơn và trượt theo hướng tăng lợi nhuận, mà không làm thay đổi độ dốc của nó. Giá trị tối đa của P là bao nhiêu? Giá trị tối đa này xảy ra ở đâu?

(B) Lặp câu (A) cho P = x + 10y.

CÁC ĐỊNH LÝ

Định lý 1. Nếu bài toán quy hoạch tuyến tính có PATU thì PATU là một trong các PACB của tập phương án.

Định lý 2. (Về sự tồn tại phương án tối ưu)

A) Nếu tập phương án của bài toán QHTT bị chặn thì cả bài toán min và max đều có PATU

B) Nếu tập phương án không bị chặn và các hệ số của hàm mục tiêu đều dương thì bài toán min có PATU nhưng bài toán max không có PATU

C) Nếu tập phương án của bài toán rỗng thì cả bài toán min và max đều không có PATU

TÌM PATU BẰNG PP ĐỒ THỊ

VÍ DỤ 11A

Z max = 28

Z min = 15

VÍ DỤ 11B

Z min = 160

Không có max

VÍ DỤ 12

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

   

x 2

x 1





 x 2

x 1





x 2

x 1



min   1   2   3

x 2 0,



x 2

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

VÍ DỤ 13

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

VÍ DỤ 14

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:

100 mã lực

50 mã lực

150

70 Thợ sắt (3000)

120

50 Thợ rèn (2000)

80

40 Thợ mộc

(1500)

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Ụ 14

Gọi x1, x2 lần lượt là số tàu 100 mã lực và 50 mã lực cần đóng Ta cần tìm x1, x2 sao cho: f(x)=100x1+50x2 max Điều kiện:



x70



3000



x50



2000

1 

x40

1500

2 

1 

2 0

x,0



150   120   x80   

VÍ DỤ 15

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Ụ 16

Một xí nghiệp điện cơ sản xuất quạt điện các loại. Cần cắt từ một tấm tôn các cánh quạt điện theo 3 kiểu A, B, C. Có 6 mẫu cắt khác nhau theo bảng sau:

Mẫu cắt

Kiểu cánh quạt

PHƯƠNG PHÁP ĐƠN HÌNH

Simplex method

Xuất phát từ một PACB đầu tiên, tìm cách đánh giá PACB ấy, nếu nó chưa tối ưu thì tìm cách chuyển sang một PACB mới tốt hơn.

Quá trình được lặp lại vì số PACB là hữu hạn nên sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được vì hàm mục tiêu không bị chặn hoặc sẽ tìm được phương án tối ưu.

Do nhà toán học George Benard Danzig đưa ra năm 1947

PHƯƠNG PHÁP ĐƠN HÌNH

1) Tìm một phương án cực biên (phương án cơ bản)

2) Xét xem PACB này đã là PATU hay chưa. Nếu đã tối ưu

thì kết thúc. Ngược lại chuyển sang bước 3.

3) Tìm phương án cực biên liền kề tốt hơn PACB đang xét

4) Quay về bước 2.

VÍ DỤ 17

Xét bài toán dạng chuẩn tắc 





min

x 1

x 3

x  4







2 

x 3 

  xf x 2 1 

2 0



x 1 jx

    



2 1

3  1

1 0

0 1

4 5

Ta có:   

  

  

  









  xf

VÍ DỤ 17

x 1

x 3

3 



  

  

  

  

Ẩn cơ bản: x3, x4





Phương án cơ bản: x1=x2=0; x3=4; x4=5  2   5,4,0,0

 xf

Ta có:











x 1 

2 

x 3 



5 

x 1 

x 3 x

x 1

x 1 x



2 0



    

VÍ DỤ 17

Ta đánh giá f(x) như sau:



















x 1

x 1 x 1  32

2 

x 3 3   243 x



2 

 52 

  xf   xf   xf

x 1  xf

 

x 1

 x 11

x 22



Bài toán min nên với   xf

 1 9 x

Ta chưa đánh giá được giá trị nhỏ nhất của f 



  xf

1 9 x 

VÍ DỤ 17

Thử chọn x1, x4 làm ẩn cơ bản. Cho x2, x3=0 ta có





x 1 



x 1

  

Phương án cơ bản:

0 x

x  1  5 x   3,0,0,2 

Ta có:

2 



x 1

x 3







2 

x 3 

x 1 



3 



x 3

3 2 5 2

1 2 1 2

x 1 x



2 0

 2    



        

VÍ DỤ 17

Ta đánh giá f(x) như sau:









  xf

x 1

 4



  xf

x 3

9 2

x 3 3 2

Dễ thấy:

  4xf Vậy phương án tối ưu:

* x

3,0,0,2 

CHÚ Ý



Tổng quát ta có:

  xf

 xf

k x

   

Ẩn không cơ bản

0kx

Với x0 là phương án cơ bản

+ Nếu bài toán min thì ta cần Delta dương

+ Nếu bài toán max thì ta cần Delta âm

Trong PP đơn hình phía sau thì Delta trong bảng đơn hình ngược dấu với Delta ở đây.

PHƯƠNG PHÁP ĐƠN HÌNH

BẢNG ĐƠN HÌNH





ac i



1 

 Cách tính Delta một cột:  Lấy hệ số cột ngoài cùng bên trái bảng  Nhân với hệ số cột cần tính  Trừ đi giá trị trên đầu cột cần tính

ibc

   x 

 Cách tính giá trị f(x):  Lấy cột hệ số nhân cột P. Án

1 

DẤU HIỆU VỀ PHƯƠNG ÁN TỐI ƯU

1. Nếu ∆k ≤ 0 thì x0 là phương án tối ưu.

2. Nếu tồn tại một ∆k > 0 mà ajk ≤ 0 thì bài toán không có phương án tối ưu.

3. Nếu tất cả ∆k > 0 và tồn tại ajk > 0 thì ta có thể tìm được phương án tốt hơn trong trường hợp bài toán không suy biến.

CÁC BƯỚC THỰC HIỆN

Nhớ phép biến đổi sơ cấp trên dòng đối với ma trận. Tương tự như khi đi tìm hạng của ma trận khi biến đổi về dạng bậc thang.

VÍ DỤ 18



4 3

2 0

3 1

0 0

1 0

0 1

60 36

    

    

    

    

VÍ DỤ 18





  xf

x 1

x 3

x 5

x 6

PA Hệ số Ẩn cơ



4 3

2 0

3 1

0 0

1 0

0 1

60 36

    

    

    

    

X1 5 X2 4 X3 5 X4 2 X5 1 X6 3 bản





  xf

x 1

x 3

x 5

x 6

VÍ DỤ 18

x1 x2 x3 x4 x5 x6 PA Hệ số Ẩn cơ bản 5 4 5 2 1 3

2 x4 52 2 4 3 1 1 0

1 x5 60 4 2 3 0 1 0



2 4

4 2

3 3

1 0

0 1

0 0



52 60

    

    

    

    

3 x6 36 3 0 1 0 0 1

VÍ DỤ 18





  xf

x 1

x 3

x 5

x 6

PA Hệ số Ẩn cơ

X1 5 X4 2 X5 1 X6 3 X2 4 X3 5 bản

X4 52 2 2 1 1 0 4 3

X5 60 1 4 0 1 0 2 3

x6 36 3 3 0 0 1 0 1



272



  0 xf

 2

    

         

    

    

         

    

272 12 0 0 0 6 7

VÍ DỤ 18





  xf

x 1

x 3

x 5

x 6

PA Hệ số Ẩn cơ

X4 2 X5 1 X6 3 X1 5 X2 4 X3 5 bản

1 1 0 2 52 X4 2 4 3

0 1 0 4 60 X5 1 2 3

0 0 1 3 36 x6 3 0 1

 5



 1

         

    

    

         

     0



4 3

1 0

2 0

3 1

0 0

0 1

60 36

         

    

    

    

0 0 0 272 12 6 7

ĐÁNH GIÁ

PA Hệ số Ẩn cơ

X1 5 X2 4 X3 5 X4 2 X5 1 X6 3 bản

X4 52 2 2 4 3 1 1 0

X5 60 1 4 2 3 0 1 0

x6 36 3 3 0 1 0 0 1

272 12 6 7 0 0 0

Giá trị lớn nhất nằm ở cột x1

2:52 4:60 3:36

  

16 15 12

Giá trị nhỏ nhất nằm ở hàng x6

Vậy đưa biến x1 vào thay cho biến x6

BẢNG MỚI

PA Hệ số Ẩn cơ

X1 5 X2 4 X4 2 X5 1 X3 5 X6 3 bản

X4 2 52 2 4 3 1 0 0

X5 1 60 4 2 3 0 0 1

x6 3 36 3 0 1 0 1 0

272 12 6 7 0 0 0

X4 2 28 0 4 7/3 1 -2/3 0

X5 1 12 0 2 5/3 0 -4/3 1

x1 5 12 1 0 1/3 0 1/3 0

128 0 6 3 0 -4 0

Chia hàng mới để có hệ số 1 tại vị trí xoay Biến đổi trên dòng để các hàng còn lại là 0 Tính lại các giá trị Delta và giá trị f(x0)

BẢNG MỚI

Đưa biến x2 vào thay biến x5

PA Hệ số Ẩn cơ

X1 5 X2 4 X3 5 X4 2 X5 1 X6 3 bản

X4 2 28 0 4 7/3 1 0 -2/3

X5 1 12 0 2 5/3 0 1 -4/3

x1 5 12 1 0 1/3 0 0 1/3

128 0 6 3 0 0 -4

X4 2 4 0 0 -1 1 -2 2

X2 4 6 0 1 5/6 0 1/2 -2/3

x1 5 12 1 0 1/3 0 0 1/3

PATU: x0=(12,6,0,4,0,0) f min = 92

92 0 0 -2 0 -3 0

PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý

1) Đối với bài toán có hàm f(x)  max thì có thể chuyển về giải bài toán với hàm g(x) = −f(x)  min (Chú ý là fmax = −gmin) hoặc cũng có thể giải trực tiếp với dấu hiệu tối ưu là k ≥ 0, dấu hiệu để điều chỉnh phương án là k < 0, còn các yếu tố khác của thuật toán không đổi.

là với hy vọng làm

2) Chọn vectơ đưa vào cơ sở ứng với max

trị số hàm mục tiêu giảm nhiều nhất sau mỗi bước biến đổi, tuy nhiên vectơ đưa vào cơ sở thực sự làm trị số hàm mục tiêu . nhưng trên nguyên giảm nhiều nhất phải ứng với max tắc thì đưa bất kỳ vectơ nào ứng với k > 0 vào cơ sở cũng cải tiến được phương án.

PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý

3) Trường hợp bài toán suy biến thì θ0 có thể bằng 0, khi θ0 = 0 vẫn thực hiện thuật toán một cách bình thường, nghĩa là vectơ ứng với θ0 vẫn bị loại khỏi cơ sở.

Dấu hiệu xuất hiện phương án cực biên suy biến là θ0

đạt tại nhiều chỉ số, khi đó vectơ loại khỏi cơ sở được chọn trong số những vectơ ứng với θ0 theo quy tắc ngẫu nhiên.

PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý

Khi áp dụng thuật toán cần lưu ý hai trường hợp:

Phương án cực biên x0 có cơ sở J0 là cơ sở đơn vị, lúc đó ma trận hệ số phân tích của [ A | b] theo cơ sở đơn vị là chính nó nên ta có thể lập ngay được bảng đơn hình. Bài toán dạng chuẩn là bài toán cho ngay một phương án cực biên với cơ sở là đơn vị, nên từ bài toán ta có thể lập được bảng đơn hình ứng với phương án cực biên ấy.

Nếu J0 không phải là cơ sở đơn vị thì để lập bảng đơn hình trước hết cần phải tìm ma trận hệ số phân tích theo J0. Để làm điều này ta viết ma trận mở rộng [A | b] sau đó thực hiện các phép biến đổi sơ cấp trên các hàng của ma trận, biến đổi sao cho các vectơ cơ sở trở thành các vectơ đơn vị khác nhau. Khi đó ma trận mở rộng sẽ trở thành ma trận hệ số phân tích.

min

  2





x 3

  x 4 8



x 1  2

x 2  3



x 2















x 4 x 4 x 4

x 1 x 1 x 1 0



x 2 x 2 

x 3 x 3 x 3 1, 2,3, 4

 7 

2 

VÍ DỤ 19 Cho bài toán:   f x       

Chứng tỏ rằng vecto x0 = (8, 0, 0, 0) là phương án cực biên. Dùng vectơ trên giải bài toán theo phương pháp đơn hình

VÍ DỤ 19

Dễ thấy rằng x0 thỏa mãn mọi ràng buộc của bài toán, các ràng buộc là độc lập tuyến tính, vậy x0 là phương án cực biên không suy biến.

  2

min





Trước hết phải đưa bài toán về dạng chính tắc. x 2

  x 4

x 3

x 1









x 2









x 5









x 6

  f x x 1 x 1 x 1 0



x 2 x 2 

x x 3 4 x x 3 4 x x 4 3 1, 2,3, 4,5,6

 7 



       

VÍ DỤ 19

Từ x0 suy ra phương án cực biên không suy biến của bài toán dạng chính tắc: x= (8, 0, 0, 0, 18, 12) với cơ sở là J0 = {A1, A5, A6} không phải là cơ sở đơn vị. Vì vậy để lập được bảng đơn hình ứng với phương án cực biên x ta phải tìm ma trận hệ số phân tích của ma trận điều kiện của bài toán dạng chính tắc qua cơ sở J0 . Chú ý rằng vế phải của ma trận hệ số phân tích phải trùng với các thành phần cơ sở của phương án cực biên.

VÍ DỤ 19

Quá trình biến đổi trên ma trận như sau:



1 2  12 7 4

3  1  8

1 0  15 2 0

0 0  1

8 8 20

21 50 10

  

3 5 4

1 00  013 2 10

8 18 12

    

    

    

    

Dựa trên ma trận hệ số phân tích ta lập bảng đơn hình.

  2





min

  f x

x 1

x 2

x 3

  x 4

PA Hệ số Ẩn cơ

X1 -2 X2 -6 X3 8 X4 -5 X5 0 X6 0 bản

X1 8 1 2 -3 1 0 0 -2

X5 18 0 5 -5 -3 1 0 0

x6 12 0 1 -4 2 0 1 0

-16 0 2 -2 3 0 0

X1 2 1 3/2 -1 0 0 -1/2 -2

X5 36 0 13/2 -11 0 1 3/2 0

x4 6 0 1/2 -2 1 0 1/2 -5

Ta có 3 = 4 > 0, nhưng aj3 < 0 (j  J), bài toán không có phương án tối ưu.

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

VÍ DỤ 20. BÀI TOÁN ĐẶT ẨN PHỤ

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









min

  f x

x 1

x 2

x 3

x 4

1 2

Với hệ ràng buộc:









x 1

x 2

x 3

x 4









x 2 x 2 0





1 2 x x 8 3 4 x x 4 3 1, 2,3, 4

 

 

       

VÍ DỤ 20. BÀI TOÁN ĐẶT ẨN PHỤ

Trước hết đưa bài toán về dạng chính tắc bằng cách cộng vào ràng buộc (2) và (3) hai biến phụ x5 và x6. Ta có:







min

  f x

x 1

x 2

x 3

x 4

1 2

 2 Với hệ ràng buộc mới:







x 1

x 2

x 3

x 4







x 5





x 6

x 2 x 2 0





1 2 x 8 x 4 3 x x 4 3 1, 2,3, 4,5,6

 

 

       

Phương án tương ứng là tối ưu: x0 = (0, 0, 16, 4, 40, 0) Giá trị tối ưu của hàm mục tiêu là: f = –18.

VÍ DỤ 21. BÀI TOÁN ĐẶT ẨN PHỤ

Đây là bài toán dạng chuẩn tắc  phương pháp đơn hình

BÀI TOÁN ẨN GIẢ

QUAN HỆ HAI BÀI TOÁN

 Nếu bài toán M vô nghiệm thì bài toán ban đầu vô nghiệm.  Nếu bài toán M có nghiệm (x1,x2,…,xn,0,…,0) thì (x1,x2,…,xn) là nghiệm bài toán ban đầu  Nếu bài toán M có nghiệm (x1,x2,…,xn,xn+1,…,xn+m) và có ít nhất 1 trong các ẩn giả >0 thì bài toán ban đầu vô nghiệm

 Thuận lợi: có thể xây dựng ngay phương án cơ bản ban đầu thông qua đặt các ẩn giả.