<< Chapter < Page Chapter >> Page >

Gọi xj  0 là số lượng sản phẩm thứ j sẽ sản xuất (j=1,2,...,n)

Tổng lợi nhuận thu được từ việc bán các sản phẩm là :

z = j = 1 n c j x j = c 1 x 1 + c 2 x 2 + . . . . . . + c n x n size 12{z= Sum cSub { size 8{j=1} } cSup { size 8{n} } {c rSub { size 8{j} } x rSub { size 8{j} } } =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} } } {}

Vì yêu cầu lợi nhuận thu được cao nhất nên ta cần có :

max z = j = 1 n c j x j = c 1 x 1 + c 2 x 2 + . . . . . . + c n x n size 12{"max z"= Sum cSub { size 8{j=1} } cSup { size 8{n} } {c rSub { size 8{j} } x rSub { size 8{j} } } =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} } } {}

Lượng nguyên liệu thứ i=1m dùng để sản xuất sản phẩm thứ 1 là ai1x1

Lượng nguyên liệu thứ i=1m dùng để sản xuất sản phẩm thứ 2 là ai2x2

...............................................

Lượng nguyên liệu thứ i=1m dùng để sản xuất sản phẩm thứ n là ainxn

Vậy lượng nguyên liệu thứ i dùng để sản xuất là các sản phẩm là

ai1x1+ai2x2+...+ainxn

Vì lượng nguyên liệu thứ i=1m dùng để sản xuất các loại sản phẩm không thể vượt quá lượng được cung cấp là bi nên :

ai1x1+ai2x2+...+ainxn  bi (i=1,2,...,m)

Vậy theo yêu cầu của bài toán ta có mô hình sau đây :

max z = j = 1 n c j x j = c 1 x 1 + c 2 x 2 + . . . . . . + c n x n size 12{"max z"= Sum cSub { size 8{j=1} } cSup { size 8{n} } {c rSub { size 8{j} } x rSub { size 8{j} } } =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} } } {}

a 11 x 1 + a 12 x 2 + . . . + a 1n x n b 1 a 21 x 1 + a 22 x 2 + . . . + a 2n x n b 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a m1 x 1 + a m2 x 2 + . . . + a mn x n b m x j 0 ( j = 1,2, . . . ,n ) { { { { size 12{alignl { stack { left lbrace a rSub { size 8{"11"} } x rSub { size 8{1} } +a rSub { size 8{"12"} } x rSub { size 8{2} } + "." "." "." +a rSub { size 8{1n} } x rSub { size 8{n} }<= b rSub { size 8{1} } {} # right none left lbrace a rSub { size 8{"21"} } x rSub { size 8{1} } +a rSub { size 8{"22"} } x rSub { size 8{2} } + "." "." "." +a rSub { size 8{2n} } x rSub { size 8{n} }<= b rSub { size 8{2} } {} # right none left lbrace "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." {} #right none left lbrace a rSub { size 8{m1} } x rSub { size 8{1} } +a rSub { size 8{m2} } x rSub { size 8{2} } + "." "." "." +a rSub { size 8{ ital "mn"} } x rSub { size 8{n} }<= b rSub { size 8{m} } {} # right none left lbrace x rSub { size 8{j} }>= 0" " \( j="1,2," "." "." "." ",n" \) {} # right no } } lbrace } {}

Bài toán vận tải

Người ta cần vận chuyển hàng hoá từ m kho đến n cửa hàng bán lẻ. Lượng hàng hoá ở kho i là si (i=1,2,...,m) và nhu cầu hàng hoá của cửa hàng j là dj (j=1,2,...,n). Cước vận chuyển một đơn vị hàng hoá từ kho i đến của hàng j là cij  0 đồng.

Giả sử rằng tổng hàng hoá có ở các kho và tổng nhu cầu hàng hoá ở các cửa hàng là bằng nhau, tức là :

i = 1 m s i = j = 1 n d j size 12{ Sum cSub { size 8{i=1} } cSup { size 8{m} } {s rSub { size 8{i} } } = Sum cSub { size 8{j=1} } cSup { size 8{n} } {d rSub { size 8{j} } } } {}

Bài toán đặt ra là lập kế hoạch vận chuyển để tiền cước là nhỏ nhất, với điều kiện là mỗi cửa hàng đều nhận đủ hàng và mỗi kho đều trao hết hàng.

Gọi xij  0 là lượng hàng hoá phải vận chuyển từ kho i đến cửa hàng j. Cước vận chuyển chuyển hàng hoá i đến tất cả các kho j là :

j = 1 n c ij x ij size 12{ Sum cSub { size 8{j=1} } cSup { size 8{n} } {c rSub { size 8{ ital "ij"} } x rSub { size 8{ ital "ij"} } } } {}

Cước vận chuyển tất cả hàng hoá đến tất cả kho sẽ là :

z = i = 1 m j = 1 n c ij x ij size 12{z= Sum cSub { size 8{i=1} } cSup { size 8{m} } { Sum cSub { size 8{j=1} } cSup { size 8{n} } {c rSub { size 8{ ital "ij"} } x rSub { size 8{ ital "ij"} } } } } {}

Theo yêu cầu của bài toán ta có mô hình toán sau đây :

min z = i = 1 m j = 1 n c ij x ij i = 1 m x ij = d j ( j = 1,2, . . . ,n ) x ij 0 ( i = 1,2, . . . ,m ) ( j = 1,1, . . . ,n ) { alignl { stack { size 12{"min"" "z= Sum cSub { size 8{i=1} } cSup { size 8{m} } { Sum cSub { size 8{j=1} } cSup { size 8{n} } {c rSub { size 8{ ital "ij"} } x rSub { size 8{ ital "ij"} } } } } {} #alignl { stack { left lbrace Sum cSub { size 8{i=1} } cSup { size 8{m} } {x rSub { size 8{ ital "ij"} } =d rSub { size 8{j} } } " " \( j="1,2," "." "." "." ",n" \) {} #right none left lbrace x rSub { size 8{ ital "ij"} }>= 0" " \( i="1,2," "." "." "." ",m" \) " " \( j="1,1," "." "." "." ",n" \) {} # right no } } lbrace {}} } {}

Quy hoạch tuyến tính tổng quát và chính tắc

Quy hoạch tuyến tính tổng quát

Tổng quát những bài toán quy hoạch tuyến tính cụ thể trên, một bài toán quy hoạch tuyến tính là một mô hình toán tìm cực tiểu (min) hoặc cực đại (max) của hàm mục tiêu tuyến tính với các ràng buộc là bất đẳng thức và đẳng thức tuyến tính. Dạng tổng quát của một bài toán quy hoạch tuyến tính là :

min/max z = j = 1 n c j x j ( I ) j = 1 n a ij x j = b i ( i I 1 ) j = 1 n a ij x j b i ( i I 2 ) ( II ) j = 1 n a ij x j b i ( i I 3 ) x j 0 j J 1 x j 0 j J 2 ( III ) x j tùy ý j J 3 no { { { { alignl { stack { size 12{"min/max"" "z= Sum cSub { size 8{j=1} } cSup { size 8{n} } {c rSub { size 8{j} } x rSub { size 8{j} } } " " \( I \) } {} #alignl { stack { left lbrace alignl { stack {left lbrace Sum cSub { size 8{j=1} } cSup { size 8{n} } {a rSub { size 8{ ital "ij"} } x rSub { size 8{j} } } =b rSub { size 8{i} } " " \( i in I rSub { size 8{1} } \) {} # right none left lbrace Sum cSub { size 8{j=1} } cSup { size 8{n} } {a rSub { size 8{ ital "ij"} } x rSub { size 8{j} } }<= b rSub { size 8{i} } " " \( i in I rSub { size 8{2} } \) " " \( "II" \) {} # right none left lbrace Sum cSub { size 8{j=1} } cSup { size 8{n} } {a rSub { size 8{ ital "ij"} } x rSub { size 8{j} } }>= b rSub { size 8{i} } " " \( i in I rSub { size 8{3} } \) {} # right no } } lbrace {} #right none left lbrace alignl { stack { left lbrace x rSub { size 8{j} }>= 0" " left (j in J rSub { size 8{1} } right ) {} # right none left lbrace x rSub { size 8{j} }<= 0" " left (j in J rSub { size 8{2} } right )" " \( "III" \) {} # right none left lbrace x rSub { size 8{j} } " tùy ý " left (j in J rSub { size 8{3} } right ) {} #right no } } lbrace {} # right no } } lbrace {}} } {}

Trong đó :

 (I) Hàm mục tiêu

Là một tổ hợp tuyến tính của các biến số, biểu thị một đại lượng nào đó mà ta cần phải quan tâm của bài toán.

 (II) Các ràng buộc của bài toán

Là các phương trình hoặc bất phương trình tuyến tính n biến số, sinh ra từ điều kiện của bài toán.

 (III) Các các hạn chế về dấu của các biến số

Người ta cũng thường trình bày bài toán quy hoạch tuyến tính dưới dạng ma trận như sau :

a 11 a 12 . . . a 1n a 21 a 22 . . . a 2n . . . . . . . . . . . . . . . . . . . . . . a m1 a m2 . . . a mn righ A = a ij = size 12{A= left [a rSub { size 8{ ital "ij"} } right ]=alignl { stack {left [a rSub { size 8{"11"} } " a" rSub { size 8{"12"} } " " "." "." "." " a" rSub { size 8{"1n"} } {} # right ]left [a rSub { size 8{"21"} } " a" rSub { size 8{"22"} } " " "." "." "." " a" rSub { size 8{"2n"} } {} # right ]left [ "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." {} # right ]left [a rSub { size 8{m1} } " a" rSub { size 8{"m2"} } " " "." "." "." " a" rSub { size 8{"mn"} } {} # righ]} } \[ \] } {} x 1 x 2 . . . x n righ c 1 c 2 . . . c n righ b 1 b 2 . . . b m righ x = size 12{x=alignl { stack { left [x rSub { size 8{1} } {} #right ] left [x rSub { size 8{2} } {} #right ] left [ "." "." "." {} #right ] left [x rSub { size 8{n} } {} #righ]} } \[ \]" c"=alignl { stack { left [c rSub { size 8{1} } {} #right ] left [c rSub { size 8{2} } {} #right ] left [ "." "." "." {} #right ] left [c rSub { size 8{n} } {} #righ]} } \[ \]" b"=alignl { stack { left [b rSub { size 8{1} } {} #right ] left [b rSub { size 8{2} } {} #right ] left [ "." "." "." {} #right ] left [b rSub { size 8{m} } {} #righ]} } \[ \]} {}

Gọi ai (i=1m) là dòng thứ i của ma trận A, ta có :

m in/max z ( x ) = c T x ( I ) a i x = b i ( i I 1 ) a i x b i ( i I 2 ) ( II ) a i x b i ( i I 3 ) x j 0 j J 1 x j 0 j J 2 ( III ) x j tùy ý j J 3 no { { { { alignl { stack { size 12{m"in/max "z \( x \) =c rSup { size 8{T} } x" " \( I \) } {} #alignl { stack { left lbrace alignl { stack {left lbrace a rSub { size 8{i} } x=b rSub { size 8{i} } " " \( i in I rSub { size 8{1} } \) {} # right none left lbrace a rSub { size 8{i} } x<= b rSub { size 8{i} } " " \( i in I rSub { size 8{2} } \) " " \( "II" \) {} # right none left lbrace a rSub { size 8{i} } x>= b rSub { size 8{i} } " " \( i in I rSub { size 8{3} } \) {} # right no } } lbrace {} #right none left lbrace alignl { stack { left lbrace x rSub { size 8{j} }>= 0" " left (j in J rSub { size 8{1} } right ) {} #right none left lbrace x rSub { size 8{j} }<= 0" " left (j in J rSub { size 8{2} } right )" " \( "III" \) {} # right none left lbrace x rSub { size 8{j} } " tùy ý " left (j in J rSub { size 8{3} } right ) {} #right no } } lbrace {} # right no } } lbrace {}} } {}

Người ta gọi :

- A là ma trận hệ số các ràng buộc.

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