Quy hoạch tuyến tính - Phương pháp đơn hình

Chia sẻ: Le Van Dai | Ngày: | Loại File: PPT | Số trang:149

Thêm vào BST

Báo xấu

281
lượt xem 58
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Để sản xuất những sản phẩm đó doanh nghiệp sử dụng m loại nguyên liệu , ta cũng đánh số từ 1 đến m :1,2, . . .,m.Việc ra quyết định trong việc điều hành những phương tiện đó nói chung là phức tạp, nó sẽ thay đổ tùy theo thị trường .

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Quy hoạch tuyến tính - Phương pháp đơn hình

Quy hoạch tuyến tính CHƯƠNG I. QUY HOẠCH TUYẾN TÍNH – PHƯƠNG PHÁP ĐƠN HÌNH
• I. Mộ số ví dụ dẫn đến bài toán QHTT. • Phương tiện sản xuất của một doanh nghiệp . • Ta xét một doanh nghiệp sản xuất có khả năng sản xuất nhiều sản phẩm . Đơn giản ta đánh số thứ tự cho những sản phẩm đó từ 1 đến n : 1,2, . . ,n. Để sản xuất những sản phẩm đó doanh nghiệp sử dụng m loại nguyên liệu , ta cũng đánh số từ 1 đến m :1,2, . . .,m.Việc ra quyết định trong việc điều hành những phương tiện đó nói chung là phức tạp, nó sẽ thay đổ tùy theo thị trường . Để đơn giả ta xét tại một khoảng thời gian thị trường ổn định và tìm cách điều hành tốt nhất – tối ưu.
• Trong khoảng thời gian đó , khối lượng loại nguyên liệu thứ i mà doanh nghiệp có ta gọi là bi . Trong khoảng thời gian đang xét giá thị trường một đơn vị nguyên liệu thứ i là ρi • Để sản xuất mỗi đơn vị sản phẩm thứ j đòi hỏi một lượng nhất định loại nguyên liệu thứ i , ta ký hiệu là aij .Mỗi đơn vị sản phẩm thứ j trên thị trường có giá bán là σ j . Ta luôn giả thiết : Khả năng của doang nghiệp so với toàn bô thị trường là nhỏ , không tác động đến giá nguyên liệu cũng như giá sản phẩm.
• 1 .Người điều hành sản xuất chủ động. • Bây giờ ta xét bài toán mà Angười điều hành sẽ gặp :Sử dụng những nguyên liệu doanh nghiệp hiện có để sản xuất sao cho mang lại nhiều lợi ích cho doanh nghiệp. • Giả sử doanh nghiệp sẽ sản xuất xj đơn vị sản phẩm thứ j .Doanh thu biên để sản xuất σj sản phẩm thứ j là . Nhưng ta cũng cần phải tính đến chi phí. Chi phí biên cho sản xuất m sản phẩm thứ j ∑ ρi aij . Vậy nên lợi nhuận là i =1 biên của sản phẩm thứ j : m σ ∑i c j = j− ρ aij i=1
• Vậy nên lợi nhuận sản xuất xj đơn sản phẩm thứ j mang lại là :cjxj và tổng lợi nhuận của doanh nghiệp : n • (1.1) f = ∑ c jx j j =1 • Mục đích của kế hoạch là làm cực đại giá trị trên. Tuy nhiên còn một số những ràng buộc mà các mức sản lượng cần phải thỏa. Thứ nhất mức sản lượng không thể âm . Vậy nên : x ≥ 0 ; j = 1,2,  , n j • (1.2)
• Thứ hai doanh nghiệp không thể dùng quá mức nguyên liệu từng loại mà nó có :lượng n nguyên liệu thứ i tiêu thụ theo kế ho∑ch x j ạ aij là j= • Do đó những điều kiện sau cần được1thỏa : n ∑ aij x j ≤ bi ; i =1,2,  , m. • (1.3) j =1 • Tổng kết lại công việc của người điều hành là xác định những mức sản lượng xj , j =1,2, . . .,n để làm cực đại (1.1) , đồng thời phải thỏa các ràng buộc (1.2) và (1.3). • 2. Người điều khiển thụ động. Nhiệm vụ của người điều khiển là ấn định một giá trị cho nguyên liệu hiện có.Những giá trị đó cần thiết cho mục đích tính toán và lên kế hoạch xác định chi phí tồn kho.
• Có một số quy tắc để xác định những giá trị trên.Một quy tắc quan trọng nhất ( và đó là quy tắc duy nhất thích hợp để ta bàn tới ) là : • Công ty sãn sàng bán nguyên liệu thô, n ếu như có một doanh nghiệp bên ngoài mua v ới giá tương thích với giá trị đó. • Giả sử wi là giá trị ấn định cho một đơn vị nguyên liệu thứ i , i=1,2, . . ,m- đó là những số mà người điều khiển phải xác định . Chi phí mất cơ hội của bi đơn vị nguyên liệu thứ i , hiện có là biwi và tổng chi phí cơ hội là : m • (1.4) ∑bi wi i=1
Mục tiêu của người điều khiển là làm nhỏ nhất chi phí cơ hội bị mất (để bản báo cáo tài chính tốt nhất có thể). Ở đây cũng có một số điều kiện. Trước hết giá được gán không thể nhỏ hơn giá phổ biến trên thị trường ( nếu nhỏ hơn thì công ty khác sẽ mua với giá đó ) vậy nên (1.5) wi ≥ ρ i ∀i = 1, , m Tương tự : m (1.6) ∑ wi aij ≥ σ j ∀j = 1, , n i =1 Ta sẽ giải thích tại sao lại như vậy. Vì rằng nếu vế trái nhỏ hơn thực sự vế phải , doanh nghiệp ngoài sẽ mua và sản xuất sản phẩm thứ j và sẽ bán với giá thấp hơn σj σj , trái với giả thiết là giá phổ dụng .
• Làm cực tiểu (1.4) thỏa các ràng buộc (1.5) và (1.6) là bài toán QHTT. • Ta thay đổi đôi chút bằng cách đặt : yi = wi −ρ i , i = 1, , m Thì bài toán của nhà điều hành bi quan sẽ là làm cực tiểu : m ∑bi yi i=1 m thỏa : ∑ yi aij ≥ c j ∀j = 1, , n i =1 ≥ 0 cho mọi i=1, . . , m. và yi
• VD3.Một xí nghiệp may mặc cần may 2000 quần và ít nhất 1000 áo từ cùng một loại vải , từ những tấm vải có cùng kích thước. Công ty cắt mỗi tấm vải theo một trong sáu cách sau : • Tìm phương án cắt sao s. quần cách s. Áo cho số tấm vải phải đem 1 90 35 2 80 55 cắt là ít nhất. 3 70 70 4 60 90 VD.4. 5 120 0 Để một loại gia súc phát 6 0 100 triển tốt thức ăn mỗi ngày cần cung cấp ít nhất 90,130 và 10 gram các chất protit,glucit và khoáng chất tương ứng. Người ta chế biến
Thức ăn từ ba loại thực Thức Chất dinh dưỡng phẩm A,B,C . Tỷ lệ các ăn Protit gluxit khoáng A 10 30 2 chất ( tính theo %) có B 20 40 1 trong các loại thực phẩm C 30 20 3 cho ở bảng bên . Ngoài ra biết giá 1kg thức ăn A,B,C là 30.00 0, 40.000, 50.000 VNĐ. Hãy lập cách chế biến thức ăn sao cho khẩu phần thức ăn rẻ nhất.
• 2. Bài toán QHTT. • A. Dạng tổng quát. • Qua hai ví dụ trên ta thấy , ở đây có những biến mà giá trị của chúng được xác định để làm tối ưu một hàm nào đó .Những biến đó được gọi là những biến quyết định (decision variable) và thường được ký hiệu là : xj , j = 1, . . ,n . Trong QHTT , mục tiêu luôn làm cực đại hoặc cực tiểu một hàm tuyến tính của những biến quyết định đó. f = c1x1 + c2x2 + · · · + cnxn. Hàm trên được gọi là hàm mục tiêu.
• Trong tự nhiên ta hay gặp những bài toán cực tiểu hơn. Nhưng trong toán học người ta thấy làm cực đại có vẻ đẹp hơn, cho nên người ta thương trình bày như tìm cực đại của hàm mục tiêu ( mặc dù tìm cực đại của f tương đương với tìm cực tiểu của –f). • Thêm vào đó là một số ràng buộc. Một số ràng buộc thực sự đơn giản, nó chỉ đòi hỏi tính không âm của vài biến quyết định. Một số ràng buộc khác phức tạp hơn, nhưng tất cả các ràng buộc đều là những phương trình hoặc bất phương trình bậc nhất của các biến quyết định.
• ≤  a1x1 + a2 x2 +  + an xn =b ≥  Dễ dàng chuyển đổi từ dạng ràng buộc này sang dạng ràng buộc khác . Ví dụ , ràng buộc bất phương trình a1x1 + a2 x2 +  + an xn ≤ b ta có thể chuyển về phương trình bằng cách thêm vào một biến , ta gọi là biến phụ (biến giảm nhẹ - slack variable): a1x1 + a2 x2 +  + an xn + w = b , w ≥ 0 Tương tự ràng buộc bất phương trình a1x1 + a2 x2 +  + an xn ≥ b
• Ta chuyển về phương trình : a1x1 + a2 x2 +  + an xn − w = b , w ≥ 0 • Còn phương tình : a1x1 + a2 x2 +  + an xn = b Ta thay bằng hai bất phương trình : a1x1 + a2 x2 +  + an xn ≥ b a1x1 + a2 x2 +  + an xn ≤ b Tiếp theo ta đưa ra một số thuật ngữ và khái niệm trong bài toán QHTT. - Phương án của bài toán QHTT có n biến quyết định x1,. . .,xn là bộ n- số thực (s1,s2, . . . ,sn) ( một véc tơ trong Rn) , sao cho (s1,s2, . . . ,sn) là một nghiệm của hệ ràng buộc , tức khi thay xj=sj vào các ràng buộc thì các ràng buộc đều thỏa
• - Tập phương án : là tập tất cả các phương án của bài toán.Ta thường ký hiệu tập phương án là D.D là một tập con của Rn. - Nếu D là tập rỗng ( tức bài toán không có phương án ) ta nói hệ ràng buộc không tương thích hoặc BT không tương thích - Nếu D không rỗng ( tức bài toán có ít nhất một phương án ) ta nói hệ ràng buộc của bài toán là tương thích hay BT tương thích. - Người ta chứng minh được rằng , nếu tập D không rỗng thì D là một tập lồi , tức là : nếu s =(s1,s2, . . ,sn ) và r= (r1,r2, . . . ,rn) là hai phương án và t là một số thực thuộc [0,1]
thì thì ts+(1-t)r = [ts1+(1-t)r1,ts2+(1-t)r2, . . . ,tsn +(1-t)rn] cũng là phương án. Phương án s được gọi là phương án cực biên nếu s =(p+q)/2 với p và q là phương án thì p=q=s. Khi bài toán QHTT tìm p.á. Cực biên giá trị lớn nhất của hàm mục tiệu f , p.á. X0 được s D gọi là phương án tối ưu r nếu : f ( X 0 ) ≥ f ( X ) ∀ X ∈ D Khi BTQHTT là tìm giá trị nhỏ nhất của hàm mục tiêu f , p.á X0 được gọi là p.á . Tối ưu nếu f ( X ) ≤ f ( X ) ∀X ∈ D 0
• Tập tất cả các phương án tối ưu ta ký hiệu là DOP . DOP của BTQHTT là một tập lồi. b. Dạng chính tắc. Bài toán QHTT được gọi là ở dạng chính tắc nếu các biến quyết định chỉ nhận những giá trị không âm và các ràng buộc còn lại đều là những phương trình tuyến tính.Tức có dạng : f = c1x1 + c2 x 2 + + cn xn → min(hoaëc ax)m a11x1 + a12 x2 + + a1n xn = b1 a21x1 + a22 x2 + + a2n xn = b2 ................. am1x + am 2 x2 + + amn xn = bm x j ≥ 0 ∀j = 1, , n
• Nếu ta đưa ra ký hiệu :cT = (c1,c2, . . ,cn) ;  a11 a12  a1n   x1   b1       x2   b2   a21 a22  a2n  X =   ;B =   ; A =          x  b  a am 2  amn   n  m  m1  • Thì BTQHTT trên có thể viết vắn tắt như sau : f = cT X → min(max) • AX = B X ≥0
• Trong khuôn khổ khóa học này ta chỉ trình bày cách giải chi tiết BTQHTT ở dạng chính tắc. Khi gặp bài toán QHTT chưa ở dạng chính tắc ta thì trước hết ta phải đưa về dạng chính tắc . • + Nếu BTQHTT có cả biến chỉ lấy giá tri không dương hoặc không có ràng buộc gì về dấu . Ta sẽ tiến hành đổi biến như sau : x j = y j neáu x j ≥ 0 x j = − y j neáu x j ≤ 0 x j = y + − y − neáux j ∈ R j j y+ ≥ 0 y − ≥ 0 . Ở đây xj là các biến trong bài trong đó và j j toán gốc.Thay các biến gốc bằng các biến mới ta đuộc bài toán có tất cả các biến nhận giá trị không âm.