Giải phương pháp đơn hình và thực hiện diễn giải bằng đồ thị. Lập trình tuyến tính. Phương pháp đơn giản

Đã thích? Thêm vào dấu trang

Giải quyết vấn đề bằng phương pháp đơn giản: ví dụ trực tuyến

Nhiệm vụ 1. Công ty sản xuất kệ phòng tắm với hai kích cỡ - A và B. Các đại lý bán hàng ước tính có thể bán được tới 550 kệ trên thị trường mỗi tuần. Mỗi kệ loại A yêu cầu 2 m2 vật liệu, mỗi kệ loại B yêu cầu 3 m2 vật liệu. Công ty có thể nhận tới 1200 m2 nguyên liệu mỗi tuần. Để sản xuất một kệ loại A cần thời gian sử dụng máy là 12 phút, để sản xuất một kệ loại B là 30 phút; Máy có thể được sử dụng 160 giờ một tuần. Nếu lợi nhuận từ việc bán kệ loại A là 3 đơn vị tiền tệ và từ kệ loại B - 4 đơn vị tiền tệ. đơn vị thì mỗi tuần nên sản xuất bao nhiêu kệ mỗi loại?

Nhiệm vụ 2. Giải quyết vấn đề lập trình tuyến tính phương pháp đơn giản.

Nhiệm vụ 3. Công ty sản xuất 3 loại sản phẩm: A1, A2, A3, sử dụng 2 loại nguyên liệu thô. Chi phí của từng loại nguyên liệu trên một đơn vị sản phẩm, lượng nguyên liệu dự trữ trong kỳ kế hoạch cũng như lợi nhuận thu được từ một đơn vị sản xuất của từng loại đều được biết.

1. Phải sản xuất bao nhiêu mặt hàng mỗi loại để tối đa hóa lợi nhuận?
2. Xác định trạng thái của từng loại nguyên liệu và giá trị cụ thể của nó.
3. Xác định khoảng thời gian tối đa cho những thay đổi trong tồn kho của từng loại nguyên vật liệu, trong đó xây dựng phương án tối ưu, tức là. Danh pháp sản xuất sẽ không thay đổi.
4. Xác định số lượng sản phẩm sản xuất ra và lợi nhuận từ sản xuất khi tăng lượng dự trữ một trong những loại nguyên liệu thô khan hiếm lên giá trị tối đa có thể (trong phạm vi sản lượng nhất định).
5. Xác định các khoảng thời gian thay đổi lợi nhuận từ một đơn vị sản xuất của từng loại mà tại đó phương án tối ưu đạt được sẽ không thay đổi.

Nhiệm vụ 4. Giải bài toán quy hoạch tuyến tính phương pháp đơn giản:

Nhiệm vụ 5. Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình:

Nhiệm vụ 6. Giải bài toán bằng phương pháp đơn hình, coi phương án đã cho trong điều kiện là phương án tham chiếu ban đầu:

Nhiệm vụ 7. Giải bài toán bằng phương pháp đơn hình đã sửa đổi.
Để sản xuất hai loại sản phẩm A và B, ba loại thiết bị công nghệ được sử dụng. Để sản xuất một đơn vị sản phẩm A, thiết bị loại thứ nhất sử dụng a1=4 giờ, thiết bị loại thứ hai a2=8 giờ và thiết bị loại thứ ba a3=9 giờ. Để sản xuất một đơn vị sản phẩm B, thiết bị loại thứ nhất sử dụng b1=7 giờ, thiết bị loại thứ hai b2=3 giờ và thiết bị loại thứ ba b3=5 giờ.
Thiết bị loại thứ nhất có thể hoạt động để sản xuất các sản phẩm này không quá t1=49 giờ, thiết bị loại thứ hai không quá t2=51 giờ, thiết bị loại thứ ba không quá t3=45 giờ.
Lợi nhuận từ việc bán một đơn vị thành phẩm A là ALPHA = 6 rúp và sản phẩm B là BETTA = 5 rúp.
Lập kế hoạch sản xuất cho sản phẩm A và B, đảm bảo lợi nhuận tối đa từ việc bán chúng.

Nhiệm vụ 8. Tìm thấy giải pháp tối ưu phương pháp đơn giản kép

Thuật toán chính để giải ZLP là phương pháp đơn hình. Nó có thể được sử dụng nếu bài toán tối ưu được viết dưới dạng đặc biệt hình thức kinh điển. Trong trường hợp này, tất cả các hạn chế đều có dạng đẳng thức và mỗi biến cơ bản chỉ xảy ra với hệ số 1 trong một phương trình, còn trong các phương trình khác, hệ số của biến cơ bản bằng 0. hàm mục tiêu không nên chứa các biến cơ bản mà chỉ được thể hiện thông qua các biến tự do. Nếu cùng một lúc b Tôi≥ 0 thì chúng ta nói đến một dạng chuẩn mực có thể chấp nhận được.

Bản chất của phương pháp đơn hình là tìm kiếm có hướng các đỉnh của ODD để xác định tọa độ của đỉnh mà tại đó hàm mục tiêu đạt cực trị. Hãy để chúng tôi giới thiệu một số định nghĩa.

Giải pháp tham khảo của hệ thống ràng buộc là một giải pháp khi, đối với một hệ thống ràng buộc ở dạng chính tắc có thể chấp nhận được, tất cả các biến tự do đều bằng 0.

Giải pháp hỗ trợ thoái hóalời giải tham chiếu trong đó một hoặc nhiều biến cơ bản bằng 0.

Giải pháp tham khảo hợp lệLời giải tham chiếu trong đó tất cả các biến cơ bản ≥ 0.

Lời giải tối ưu của ZLP sẽ tương ứng với một trong các lời giải tham chiếu được chấp nhận. Trong phương pháp đơn hình, bắt đầu từ một nghiệm tham chiếu được chấp nhận nằm ở đỉnh của khối đa diện ODR, chúng di chuyển đến đỉnh lân cận, duy trì khả năng được chấp nhận của nghiệm.

Để thuận tiện cho việc xây dựng các quy tắc của phương pháp, chúng tôi viết ra các quy tắc kinh điển được chấp nhận mẫu PAP dưới một dạng khác gọi là dạng chuẩn. Ví dụ:

Để đơn giản hóa việc thực hiện phương pháp đơn giản trên máy tính, nó được trình bày trong dạng bảng. Trong trường hợp này, mỗi giải pháp hỗ trợ tương ứng với một bảng đơn giản mới. Mỗi hàng của bảng tương ứng với một hàng của hàm mục tiêu hoặc một hàng của một trong các ràng buộc. Một bảng ví dụ cho trường hợp bảy biến dùng cho ký hiệu chuẩn được đưa ra dưới đây.

Trong phương pháp đơn công cần có giải pháp hỗ trợ khả thi ban đầu. Đôi khi một giải pháp như vậy rất dễ dàng có được. Ví dụ: nếu có một ràng buộc về dạng với giá trị dương bên phải, thì các biến bổ sung được sử dụng khi viết các ràng buộc dưới dạng đẳng thức sẽ tạo thành một giải pháp tham chiếu được chấp nhận trong đó tất cả các biến thiết kế đều bằng 0 và các biến bổ sung là cơ bản. Tuy nhiên, trong nhiều bài toán có các ràng buộc ở dạng 0 và = 0, do đó lời giải tham chiếu ban đầu có thể không được chấp nhận. Vì vậy, việc áp dụng phương pháp đơn hình trong trường hợp tổng quát phải đi trước giai đoạn tìm kiếm lời giải chấp nhận được. Hãy xem xét một trong các biến thể của thuật toán phương pháp đơn hình, có tính đến giai đoạn tìm kiếm giải pháp có thể chấp nhận được.

Thuật toán phương pháp đơn giản

Giai đoạn 1: tìm một giải pháp tham chiếu có thể chấp nhận được.

Bước 1. Các ràng buộc bất bình đẳng được giảm xuống dưới dạng các ràng buộc bình đẳng. Nhiệm vụ được viết ở dạng tiêu chuẩn.

Bước 2.Đối với mỗi ràng buộc có số hạng tự do âm, dấu của hệ số của các biến tự do sẽ được kiểm tra. Nếu thiếu ít nhất một hệ số âm thì các hạn chế không nhất quán. Nếu các số hạng tự do trong mọi ràng buộc đều không âm thì nghiệm tham chiếu được chấp nhận và cần chuyển sang giai đoạn thứ hai (giai đoạn tìm lời giải tối ưu).

Bước 3.Đối với ràng buộc có số hạng tự do âm, biến tự do có hệ số âm được chọn. Biến này sẽ là biến cơ sở mới. Nếu có nhiều hơn một hệ số âm thì bất kỳ hệ số nào có hệ số âm đều có thể được chọn làm biến cơ sở mới (việc chọn biến trong trường hợp này sẽ ảnh hưởng đến số lần thay đổi cơ sở, nhưng không ảnh hưởng đến kết quả cuối cùng). Hãy để nó là một biến x tôi. Nếu có nhiều hơn một ràng buộc với số hạng tự do âm thì bạn có thể chọn bất kỳ ràng buộc nào để phân tích các hệ số.

Bước 4.Để chọn một biến tự do mới, mối quan hệ được xem xét b j /Một jl cho tất cả các hạn chế, và b j Và Một jl phải có cùng dấu hiệu. Tỷ lệ tối thiểu được tìm thấy. Biến miễn phí mới sẽ là biến cơ bản mà ràng buộc được áp dụng b j /Một jl hóa ra là tối thiểu. Trong trường hợp này phần tử phân giải của bảng sẽ nằm ở giao điểm của cột tương ứng với biến x tôi và một dòng tương ứng với ràng buộc mà tỷ lệ tối thiểu đạt được.

Bước 5. Cơ sở được thay thế. Để tính lại giá trị các phần tử của bảng đơn sau khi thay đổi cơ sở, ta đưa vào bảng ký hiệu sau:

Tại q=r; s=p,số lần lặp (thay đổi cơ sở);

Tại q=r;sp,s=
;

Tại q r; s=p;q=
;

cho các phần tử khác.

Bước 6. Hãy quay lại bước 2.

giai đoạn 2: tìm ra giải pháp tối ưu.

Bước 1. Dấu hiệu tối ưu của giải pháp được kiểm tra.

Dấu hiệu của giải pháp tối ưu:

a) hàm mục tiêu sẽ có giá trị lớn nhất trong trường hợp trong dòng (biểu thức) của hàm mục tiêu ở dạng ký hiệu chuẩn tất cả các hệ số của biến tự do đều dương (không xét đến số hạng tự do);

b) hàm mục tiêu sẽ có giá trị tối thiểu trong trường hợp trong dòng của hàm mục tiêu ở dạng chuẩn, tất cả các hệ số của biến tự do đều âm;

c) nếu trong biểu thức của hàm mục tiêu ở dạng chuẩn, tất cả các hệ số của các biến đều cùng dấu và có ít nhất một hệ số 0, thì nghiệm kết quả là thay thế, nghĩa là sẽ có một tập hợp biến khác cung cấp cùng một giá trị cho hàm mục tiêu.

Nếu tiêu chí tối ưu được thỏa mãn thì giải pháp đã được tìm thấy. Giá trị của các biến tự do bằng 0, giá trị của các biến cơ bản bằng số hạng tự do của ràng buộc tương ứng, giá trị của hàm mục tiêu bằng số hạng tự do của hàm mục tiêu. Nếu tiêu chí tối ưu không được thỏa mãn thì chuyển sang bước 2.

Bước 2. Theo quy tắc chọn biến cơ bản mới, chúng ta chuyển một trong các biến tự do sang biến cơ bản.

Quy tắc chọn biến tự do để chuyển về cơ sở

Khi tìm giá trị lớn nhất (cực tiểu) của hàm viết dưới dạng chuẩn, biến có hệ số âm (dương) trong biểu thức hàm mục tiêu ở dạng chuẩn phải được chuyển về cơ sở. Nếu có nhiều hơn một hệ số âm (dương) c j, sau đó chọn một biến có hệ số âm (dương) giá trị tuyệt đối lớn hơn c j .

Bước 3. Theo quy tắc chọn biến được chuyển từ cơ bản sang miễn phí, chúng tôi xác định một biến miễn phí mới.

Hãy xây dựng quy tắc chọn một biến để chuyển đổi từ cơ bản sang miễn phí.

Để chọn một biến miễn phí mới x Tôi thái độ cần được xem xét b j /Một ij cho tất cả các hạn chế (
), (
), từ các mối quan hệ này, hãy chọn mức tối thiểu và dưới dạng một biến tự do mới, hãy chọn biến cơ bản mà mối quan hệ tối thiểu thu được để giới hạn b j /Một ij. Thái độ b j /Một ij chỉ nên được xem xét tích cực Một ij. Nếu đạt đến mức tối thiểu cho nhiều hơn một chỉ mục j, thì bất kỳ biến nào tương ứng với j-thứ hạn chế.

Nếu không có Một ij không tích cực thì không thể đạt được một giải pháp khả thi mới, tức là khi tìm cực tiểu, hàm mục tiêu không bị giới hạn từ bên dưới và khi tìm cực đại, nó không bị giới hạn từ phía trên ( dấu hiệu vô biên của hàm mục tiêu).

Bước 4. Cơ sở được thay thế tương tự như bước 5 của giai đoạn đầu tiên.

Bước 5. Hãy chuyển sang bước 1.

Ví dụ 2. Tìm theo hạn chế

Hãy viết bài toán ở dạng chuẩn và trình bày dưới dạng bảng đơn:

Dấu hiệu không nhất quán của các giới hạn không được thỏa mãn. Không tìm thấy lời giải có thể chấp nhận được vì thuật ngữ tự do cho ràng buộc x 5 bằng -5. Để có được một giải pháp chấp nhận được, chúng tôi thay đổi cơ sở. Hãy chọn làm cột giải quyết x 1 ; dòng quyền - x 6 (kể từ ngày 1/2<5/2). Разрешающий элемент подчеркнут. Строим новую симплекс-таблицу.

Một trong những phương pháp giải bài toán tối ưu ( thường liên quan đến việc tìm giá trị tối thiểu hoặc tối đa) quy hoạch tuyến tính được gọi là . Phương pháp đơn giản bao gồm cả một nhóm các thuật toán và phương pháp để giải các bài toán quy hoạch tuyến tính. Một trong những phương pháp này bao gồm việc ghi lại dữ liệu nguồn và tính toán lại chúng trong một bảng đặc biệt, được gọi là phương pháp đơn giản dạng bảng.

Hãy xem xét thuật toán của phương pháp đơn giản dạng bảng bằng ví dụ về giải pháp nhiệm vụ sản xuất, cốt lõi là tìm ra một kế hoạch sản xuất đảm bảo lợi nhuận tối đa.

Dữ liệu đầu vào cho bài toán phương pháp đơn hình

Công ty sản xuất 4 loại sản phẩm, gia công trên 3 máy.

Tiêu chuẩn thời gian (phút/cái) để gia công sản phẩm trên máy được xác định theo ma trận A:

Quỹ thời gian vận hành máy (min.) được xác định trong ma trận B:

Lợi nhuận từ việc bán từng đơn vị sản phẩm (RUB/cái) được tính theo ma trận C:

Mục đích của nhiệm vụ sản xuất

Lập kế hoạch sản xuất để tối đa hóa lợi nhuận của doanh nghiệp.

Giải bài toán bằng phương pháp đơn giản dạng bảng

(1) Ta ký hiệu X1, X2, X3, X4 số lượng sản phẩm dự kiến ​​của từng loại. Sau đó là kế hoạch mong muốn: ( X1, X2, X3, X4)

(2) Hãy viết các ràng buộc của kế hoạch dưới dạng hệ phương trình:

(3) Khi đó lợi nhuận mục tiêu là:

Tức là lợi nhuận từ việc hoàn thành kế hoạch sản xuất phải đạt mức tối đa.

(4) Để giải bài toán cực trị có điều kiện, chúng ta thay thế hệ bất đẳng thức bằng hệ phương trình tuyến tính bằng cách đưa thêm các biến không âm vào đó ( X5, X6, X7).

(5) Hãy chấp nhận những điều sau đây kế hoạch tham khảo:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Hãy nhập dữ liệu vào bảng đơn:

Ở dòng cuối cùng, chúng ta nhập các hệ số của hàm mục tiêu và giá trị của nó với dấu ngược lại;

(7) Chọn ở dòng cuối cùng vĩ đại nhất (modulo) một số âm.

Hãy tính toán b = N/Item_of_the_selected_column

Trong số các giá trị tính được của b ta chọn ít nhất.

Giao điểm của cột và hàng đã chọn sẽ cho chúng ta phần tử phân giải. Chúng ta thay đổi cơ sở thành một biến tương ứng với phần tử phân giải ( X5 đến X1).

• Bản thân phần tử phân giải chuyển thành 1.
• Đối với các phần tử của đường phân giải – a ij (*) = a ij / RE ( nghĩa là chúng ta chia từng phần tử cho giá trị của phần tử phân giải và thu được dữ liệu mới).
• Đối với các phần tử của cột độ phân giải, chúng chỉ được đặt lại về 0.
• Chúng tôi tính toán lại các phần tử còn lại của bảng bằng quy tắc hình chữ nhật.

a ij (*) = a ij – (A * B / RE)

Như bạn có thể thấy, chúng ta lấy ô hiện tại đang được tính toán lại và ô có phần tử phân giải. Chúng tạo thành các góc đối diện của hình chữ nhật. Tiếp theo, chúng ta nhân các giá trị từ các ô của 2 góc còn lại của hình chữ nhật này. Công việc này ( MỘT * B) chia cho phần tử phân giải ( NỐT RÊ). Và trừ đi ô hiện tại đang được tính toán lại ( một ij) chuyện gì đã xảy ra thế. Chúng tôi nhận được một giá trị mới - à ij (*).

(9) Kiểm tra lại dòng cuối cùng ( c) TRÊN sự hiện diện của số âm. Nếu chúng không có ở đó, phương án tối ưu đã được tìm ra; chúng ta chuyển sang giai đoạn cuối cùng để giải quyết vấn đề. Nếu có thì phương án chưa tối ưu, bảng đơn cần phải tính toán lại.

Vì chúng ta lại có số âm ở dòng cuối cùng nên chúng ta bắt đầu một phép tính lặp lại mới.

(10) Vì không có yếu tố tiêu cực nào ở dòng cuối cùng, điều này có nghĩa là chúng tôi đã tìm ra phương án sản xuất tối ưu! Cụ thể: chúng tôi sẽ sản xuất những sản phẩm đã chuyển sang cột “Cơ sở” - X1 và X2. Chúng ta biết lợi nhuận từ việc sản xuất mỗi đơn vị sản phẩm ( ma trận C). Vẫn còn nhân khối lượng sản xuất tìm được của sản phẩm 1 và 2 với lợi nhuận trên 1 sản phẩm, chúng ta sẽ có được kết quả cuối cùng ( tối đa! ) lợi nhuận cho một kế hoạch sản xuất nhất định.

TRẢ LỜI:

X1 = 32 chiếc, X2 = 20 chiếc, X3 = 0 chiếc, X4 = 0 chiếc.

P = 48 * 32 + 33 * 20 = 2.196 chà.

Galyautdinov R.R.

© Việc sao chép tài liệu chỉ được phép nếu có siêu liên kết trực tiếp đến

Hãy xem xét phương pháp đơn giảnđể giải các bài toán quy hoạch tuyến tính (LP). Nó dựa trên sự chuyển đổi từ kế hoạch tham chiếu này sang kế hoạch tham chiếu khác, trong đó giá trị của hàm mục tiêu tăng lên.

Thuật toán của phương pháp đơn giản như sau:

1. Chúng tôi chuyển đổi vấn đề ban đầu thành dạng chính tắc bằng cách đưa vào các biến bổ sung. Đối với các bất đẳng thức có dạng ≤, các biến bổ sung được đưa vào với dấu (+), nhưng nếu có dạng ≥ thì thêm vào dấu (-). Các biến bổ sung được đưa vào hàm mục tiêu có dấu tương ứng với hệ số bằng 0 , bởi vì hàm mục tiêu không được thay đổi ý nghĩa kinh tế của nó.
2. Các vectơ được viết ra Số Pi từ các hệ số của các biến và cột các số hạng tự do. Hành động này xác định số lượng vectơ đơn vị. Quy tắc là số lượng vectơ đơn vị phải bằng số lượng bất đẳng thức trong hệ ràng buộc.
3. Sau đó, dữ liệu nguồn được nhập vào một bảng đơn giản. Các vectơ đơn vị được đưa vào cơ sở và bằng cách loại trừ chúng khỏi cơ sở, giải pháp tối ưu sẽ được tìm thấy. Các hệ số của hàm mục tiêu được viết với dấu ngược lại.
4. Dấu hiệu tối ưu cho bài toán LP là giải pháp tối ưu nếu trong f– trong hàng tất cả các hệ số đều dương. Quy tắc tìm cột kích hoạt - đã xem f– một chuỗi và trong số các phần tử âm của nó, phần tử nhỏ nhất được chọn. Vectơ Số Pi việc chứa đựng nó trở nên dễ dãi. Quy tắc chọn phần tử phân giải - tỷ lệ giữa các phần tử dương của cột phân giải với các phần tử của vectơ được biên soạn P 0 và số cho tỷ lệ nhỏ nhất sẽ trở thành phần tử phân giải mà bảng đơn sẽ được tính toán lại. Dòng chứa phần tử này được gọi là dòng kích hoạt. Nếu không có phần tử tích cực nào trong cột độ phân giải thì bài toán không có lời giải. Sau khi xác định được phần tử phân giải, họ tiến hành tính toán lại bảng đơn giản mới.
5. Quy tắc điền vào một bảng đơn giản mới. Đơn vị được đặt thay cho phần tử phân giải và các phần tử khác được coi là bằng nhau 0 . Vectơ phân giải được thêm vào cơ sở, từ đó vectơ 0 tương ứng bị loại trừ và các vectơ cơ sở còn lại được viết mà không thay đổi. Các phần tử của chuỗi độ phân giải được chia cho phần tử độ phân giải và các phần tử còn lại được tính toán lại theo quy tắc hình chữ nhật.
6. Việc này được thực hiện cho đến khi f– tất cả các phần tử của chuỗi sẽ không trở thành số dương.

Hãy xem xét việc giải quyết vấn đề bằng thuật toán được thảo luận ở trên.
Được cho:

Chúng tôi đưa vấn đề về dạng chính tắc:

Chúng tôi soạn các vectơ:

Điền vào bảng đơn:

:
Hãy tính lại phần tử đầu tiên của vectơ P 0, mà chúng ta tạo một hình chữ nhật gồm các số: và chúng ta nhận được: .

Chúng tôi thực hiện các phép tính tương tự cho tất cả các phần tử khác của bảng đơn:

Trong kế hoạch nhận được f– dòng chứa một phần tử âm – ​​(-5/3), vector P 1. Nó chứa trong cột của nó một phần tử tích cực duy nhất, phần tử này sẽ là phần tử kích hoạt. Hãy tính toán lại bảng liên quan đến yếu tố này:

Không có yếu tố tiêu cực trong f– dòng có nghĩa là tìm thấy phương án tối ưu:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Lập trình tuyến tính, M: Nauka, 1998,
• Ventzel E.S. Nghiên cứu Hoạt động, M: Đài phát thanh Liên Xô, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Lập trình toán học, M: Higher School, 1986.

Giải pháp lập trình tuyến tính tùy chỉnh

Bạn có thể đặt bất kỳ bài tập nào trong chuyên ngành này trên trang web của chúng tôi. Bạn có thể đính kèm tập tin và chỉ định thời hạn tại