Viết hệ thống dưới dạng chính tắc. Bài toán quy hoạch tuyến tính (LPP)

Bất kỳ nhiệm vụ lập trình tuyến tính có thể được rút gọn thành bài toán quy hoạch tuyến tính ở dạng chính tắc. Với mục đích này trong trường hợp chung bạn cần có khả năng quy bài toán cực đại hóa thành bài toán cực tiểu hóa; chuyển từ ràng buộc bất đẳng thức sang ràng buộc đẳng thức và thay thế các biến không tuân theo điều kiện không âm. Tối đa hóa một hàm nhất định tương đương với việc giảm thiểu hàm tương tự được lấy với dấu ngược lại và ngược lại.

Quy tắc rút gọn bài toán quy hoạch tuyến tính thành hình thức kinh điển là như sau:

nếu bài toán ban đầu yêu cầu xác định giá trị lớn nhất hàm tuyến tính, thì bạn nên đổi dấu và tìm giá trị nhỏ nhất của hàm này;
nếu có những hạn chế phần bên phải là âm thì giới hạn này phải được nhân với -1;
nếu có sự bất bình đẳng giữa các hạn chế, thì bằng cách đưa vào các biến không âm bổ sung, chúng sẽ được chuyển thành các đẳng thức;
nếu một số biến x j không có hạn chế về dấu thì nó được thay thế (trong hàm mục tiêu và trong tất cả các hạn chế) bằng hiệu giữa hai biến không âm mới:
x 3 = x 3 + - x 3 - , Ở đâu x 3 + , x 3 - ≥ 0 .

ví dụ 1. Rút gọn bài toán quy hoạch tuyến tính về dạng chính tắc:

phút L = 2x 1 + x 2 - x 3 ;
2x2 - x3 5;
x 1 + x 2 - x 3 ≥ -1;
2x1 - x2 ≤ -3;
x 1 0; x 2 ≥ 0; x 3 ≥ 0.

Hãy đưa các biến san bằng vào từng phương trình của hệ ràng buộc x 4 , x 5 , x 6. Hệ sẽ được viết dưới dạng đẳng thức, còn phương trình thứ nhất và thứ ba của hệ ràng buộc các biến x 4 , x 6được nhập vào bên trái với dấu "+" và trong phương trình thứ hai, biến x 5được nhập bằng dấu "-".

2x2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Các số hạng tự do ở dạng chính tắc phải dương; để làm điều này, nhân hai phương trình cuối với -1:

2x2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

Trong dạng chính tắc của việc viết các bài toán quy hoạch tuyến tính, tất cả các biến có trong hệ thống ràng buộc phải âm. Hãy giả sử rằng x 1 = x 1" - x 7 , Ở đâu x 1" ≥ 0, x 7 ≥ 0 .

Thay biểu thức này vào hệ ràng buộc và hàm mục tiêu rồi viết các biến theo thứ tự chỉ số tăng dần, chúng ta thu được bài toán quy hoạch tuyến tính được trình bày dưới dạng chính tắc:

L min = 2x 1 " + x 2 - x 3 - 2x 7 ;
2x2 - x 3 + x 4 = 5;
-x 1" - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1" + x 2 - x 6 + 2x 7 = 3;
x 1” ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Điều kiện tối ưu cho phương án cơ bản của bài toán LP chính tắc. Phương pháp đơn giản và sự hội tụ của nó.

Phương pháp đơn giản là phổ quát, vì nó cho phép bạn giải quyết hầu hết mọi vấn đề quy hoạch tuyến tính được viết bằng hình thức kinh điển.

Ý tưởng của phương pháp đơn giản cải tiến nhất quán kế hoạch,đó là, bắt đầu từ một giải pháp tham chiếu ban đầu nào đó, chuyển động có hướng tuần tự từ lời giải tham khảo của bài toán đến lời giải tối ưu.

Giá trị của hàm mục tiêu không giảm trong quá trình di chuyển các bài toán đến mức tối đa.

Vì số lượng giải pháp hỗ trợ là hữu hạn nên sau hữu hạn bước chúng ta thu được giải pháp hỗ trợ tối ưu.

Nghiệm tham chiếu là nghiệm cơ bản không âm.

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

1. Mô hình toán của bài toán phải kinh điển. Nếu nó không chính tắc thì nó phải được đưa về dạng kinh điển.

2. Tìm giải pháp tham chiếu ban đầu và kiểm tra tính tối ưu của nó.
Để làm điều này, hãy điền vào bảng đơn 1.
Chúng ta điền vào tất cả các hàng của bảng bước 1 theo dữ liệu của hệ hạn chế và hàm mục tiêu.

Khả thi trường hợp sau khi giải quyết các vấn đề trên tối đa:

1. Nếu mọi hệ số dòng cuối cùng bảng đơn giản Dj³ 0, sau đó tìm thấy

giải pháp tối ưu.

2 Nếu có ít nhất một hệ số DJ £ 0, nhưng đối với biến tương ứng không có một mối quan hệ đánh giá tích cực duy nhất, thì nghiệm chúng tôi dừng nhiệm vụ, vì F(X) ® ¥ , tức là hàm mục tiêu không bị giới hạn trong phạm vi các giải pháp khả thi.

Nếu ít nhất một hệ số của hàng cuối cùng âm và đối với biến tương ứng thì có ít nhất một thái độ đánh giá tích cực thì bạn cần phải chuyển sang sang giải pháp tham khảo khác.

4. E nếu như có một số hệ số âm ở hàng cuối cùng, sau đó vào cột biến cơ bản(BP) giới thiệu rằng Biến đổi, tương ứng với lớn nhất ở giá trị tuyệt đối hệ số âm.

5. Nếu có ít nhất một hệ số Dk< 0 ,Cái đó k - thứ cột chấp nhận cho người dẫn chương trình.

6. Đối với đường dẫn đầu chúng tôi chấp nhận cái tương ứng tối thiểu tỷ lệ thành viên miễn phí biđến hệ số dương dẫn đầu, k – cái đó cột.

7. Phần tử nằm ở giao điểm của hàng và cột đầu tiên được gọi là yếu tố hàng đầu.

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

· điền vào cột cơ sở bằng số không và số một

· viết lại dòng đầu bằng cách chia nó cho phần tử đầu

· nếu hàng đầu có số 0 thì các cột tương ứng có thể được chuyển sang bảng đơn tiếp theo

· chúng ta tìm các hệ số còn lại bằng quy tắc “hình chữ nhật”

Chúng tôi thu được một giải pháp tham chiếu mới mà chúng tôi kiểm tra cho sự tối ưu:

Nếu tất cả các hệ số của hàng cuối cùng Dj³ 0 thì đã tìm ra giải pháp tối đa.

Nếu không, hãy điền vào bảng đơn giản của bước thứ 8, v.v.

Nếu hàm mục tiêu F(X)đòi hỏi phải tìm giá trị tối thiểu, thì tiêu chí sự tối ưu của vấn đề là hệ số không dương D j với mọi j = 1,2,...n.

Sự hội tụ của phương pháp đơn hình. Sự thoái hóa trong các vấn đề LP. Tài sản quan trọng nhất Bất kỳ thuật toán tính toán nào cũng có tính hội tụ, tức là khả năng thu được kết quả mong muốn trong quá trình áp dụng (với độ chính xác nhất định) trong một số bước hữu hạn (lần lặp).

Dễ dàng nhận thấy các vấn đề về sự hội tụ của phương pháp đơn hình có thể nảy sinh ở khâu chọn giá trị r (phần 2”) trong trường hợp giống nhau. giá trị tối thiểu mối quan hệ

sẽ đạt được đồng thời cho nhiều hàng của bảng T (q). Sau đó, ở lần lặp tiếp theo, cột b(β(q+1)) sẽ không chứa phần tử nào.

Trong trường hợp tổng quát, một bài toán quy hoạch tuyến tính được viết theo cách mà các ràng buộc vừa là phương trình vừa là bất đẳng thức, và các biến có thể không âm hoặc thay đổi tùy ý. Trong trường hợp tất cả các ràng buộc đều là phương trình và tất cả các biến đều thỏa mãn điều kiện không âm thì bài toán quy hoạch tuyến tính được gọi là bài toán quy hoạch chính tắc. Nó có thể được biểu diễn dưới dạng tọa độ, vectơ hoặc ký hiệu ma trận.

1. Bài toán quy hoạch tuyến tính chính tắc trong ký hiệu tọa độ có dạng

Ở dạng nhỏ gọn hơn nhiệm vụ này có thể được viết bằng dấu tổng,

(1.7)

2. Bài toán quy hoạch tuyến tính chính tắc trong ký hiệu vectơ có dạng

(1.8)

Ở đâu ,

3. Bài toán quy hoạch tuyến tính chính tắc trong ký hiệu ma trận có dạng

(1.9)

, .

Đây MỘT– ma trận các hệ số của hệ phương trình, X– cột ma trận biến vấn đề, – cột ma trận các phần bên phải của hệ giới hạn.

Các bài toán quy hoạch tuyến tính thường được sử dụng, gọi là đối xứng, trong ký hiệu ma trận có dạng

(1.10)

(1.11)

1.4. Đưa nhiệm vụ chung lập trình tuyến tính
sang dạng kinh điển

Trong hầu hết các phương pháp giải các bài toán quy hoạch tuyến tính, người ta giả định rằng hệ ràng buộc bao gồm các phương trình và điều kiện tự nhiên cho tính không âm của các biến. Tuy nhiên, khi biên soạn các mô hình toán học nhiệm vụ kinh tế các ràng buộc chủ yếu được hình thành thành các hệ bất đẳng thức nên cần chuyển được từ hệ bất đẳng thức sang hệ phương trình. Để đạt được mục đích này, chúng ta chứng minh định lý sau.

Định lý 1.1. Về việc thay thế bất đẳng thức bằng một phương trình. Mọi quyết định sự bất bình đẳng

tương ứng với một nghiệm duy nhất của phương trình

và sự bất bình đẳng

, (1.14)

và ngược lại, mỗi nghiệm của phương trình (1.13) và bất đẳng thức (1.14) tương ứng với một nghiệm duy nhất của bất đẳng thức (1.12).

Bằng chứng. Cho phép là nghiệm của bất đẳng thức (1.12), thì . Chúng ta hãy biểu thị sự khác biệt giữa vế phải và vế trái của bất đẳng thức này bằng , tức là

Rõ ràng . Thay vào đó chúng ta thay vào phương trình (1.13) giá trị biến , chúng tôi nhận được

Như vậy, thỏa mãn phương trình (1.13) và bất đẳng thức (1.14). Điều này có nghĩa là phần đầu tiên của định lý đã được chứng minh.

Bây giờ hãy thỏa mãn phương trình (1.13) và bất đẳng thức (1.14), tức là ta có

VÀ

Loại bỏ giá trị không âm ở vế trái của đẳng thức cuối cùng, ta thu được

I E. thỏa mãn bất đẳng thức (1.12). Định lý đã được chứng minh.

Nếu bất đẳng thức là , thì một biến không âm bổ sung phải được đưa vào vế trái của nó bằng dấu trừ, tức là.

Các biến không âm được đưa vào các ràng buộc bất đẳng thức để biến chúng thành các phương trình được gọi là biến bổ sung. Các biến bổ sung được đưa vào hàm mục tiêu với hệ số bằng 0 và do đó không ảnh hưởng đến giá trị của nó.

Trong trường hợp bài toán có các biến thay đổi tùy ý thì bất kỳ biến nào như vậy sẽ được thay thế bằng hiệu của hai biến không âm, tức là. , Ở đâu Và .

Đôi khi cần phải chuyển một bài toán từ tìm cực tiểu sang tìm cực đại hoặc ngược lại. Để làm được điều này, chỉ cần thay đổi dấu của tất cả các hệ số của hàm mục tiêu thành các hệ số ngược lại, còn không thì giữ nguyên bài toán. Các nghiệm tối ưu của các bài toán cực đại và cực tiểu thu được theo cách này trùng khớp nhau và giá trị của các hàm mục tiêu đối với các nghiệm tối ưu chỉ khác nhau về dấu hiệu.

Ví dụ 1.1.Đưa bài toán quy hoạch tuyến tính về dạng chính tắc.

Giải pháp. Chúng ta chuyển sang bài toán tìm cực đại của hàm mục tiêu. Để làm điều này, chúng ta thay đổi dấu của các hệ số của hàm mục tiêu. Để chuyển bất đẳng thức thứ hai và thứ ba của hệ ràng buộc thành phương trình, chúng tôi đưa vào các biến bổ sung không âm (trên mô hình toán học thao tác này được đánh dấu bằng chữ D). Biến được đưa vào vế trái của bất đẳng thức thứ hai với dấu “+”, vì bất đẳng thức có dạng . Biến được đưa vào vế trái của bất đẳng thức thứ ba với dấu “-”, vì bất đẳng thức có dạng . Các biến được nhập vào hàm mục tiêu với hệ số bằng 0. Biến không áp đặt điều kiện âm được thay thế bằng hiệu , . Chúng tôi viết vấn đề ở dạng chính tắc

Trong một số trường hợp, cần phải giảm vấn đề kinh điển xuống bài toán đối xứng. Hãy xem một ví dụ.

Ví dụ 1.2.Đưa bài toán quy hoạch tuyến tính về dạng đối xứng

Trang 1

Dạng chính tắc của bài toán được đặc trưng bởi ba đặc điểm sau: 1) hệ thống các ràng buộc đồng nhất ở dạng hệ phương trình; 2) các điều kiện không âm đồng nhất áp dụng cho tất cả các biến liên quan đến bài toán và 3) cực đại hóa hàm tuyến tính. Trong vấn đề này, cả ba tính năng này đều bị vi phạm.

Dạng chính tắc của bài toán quy hoạch tuyến tính thuận tiện ở chỗ dễ dàng tìm được đỉnh ban đầu của vùng khả thi.

Chúng ta hãy xem xét dạng chính tắc của bài toán quy hoạch tuyến tính và phương pháp loại bỏ Jordan-Gauss.

Dạng chính tắc của một bài toán quy hoạch tuyến tính thường thuận tiện.

Khi chuyển đổi một hệ thống các ràng buộc sang dạng chính tắc của một bài toán quy hoạch tuyến tính, các bất đẳng thức (12) và (13) phải được thay thế bằng các đẳng thức. Để làm điều này, các biến không âm bổ sung được đưa vào.

Chứng minh rằng các ma trận thực giao hoán theo cặp đồng thời được rút gọn về dạng chính tắc của Bài toán 1128 bằng phép biến đổi tương tự sử dụng ma trận trực giao.

Về cơ bản (4) - (5) có thể được coi là dạng chuẩn của bài toán quy hoạch phi tuyến, vì các phương pháp được nêu trong Chương. Thông thường trong các bài toán lập trình phi tuyến không yêu cầu các biến phải là số nguyên.

Các loại hạn chế và phương pháp chuyển đổi chúng.

Dạng chính tắc của bài toán có đặc điểm là tính đồng nhất của hệ ràng buộc dưới dạng hệ phương trình; tối đa hóa hàm mục tiêu; điều kiện không âm của tất cả các biến liên quan đến bài toán.

Không có Tính năng bổ sung dạng chính tắc của các bài toán không bổ sung vào sơ đồ tính toán đang được xem xét.

Đầu tiên chúng ta xét dạng chính tắc thứ hai của bài toán cực tiểu.

Thuật toán đơn giản-mete có thể được chia thành hai giai đoạn. Ở giai đoạn đầu tiên, một giải pháp cơ bản được tìm ra bằng cách loại bỏ các biến số. Nếu nó được tìm thấy thì chúng ta có dạng chính tắc của bài toán để chuyển sang giai đoạn thứ hai. Bước thứ hai là kiểm tra xem có tối ưu bị chặn hay không. Nếu tồn tại thì xác định các giải pháp cơ bản có thể chấp nhận được và từ đó lựa chọn giải pháp tối ưu.

Nếu vấn đề được giải quyết ở dạng chính tắc thì chỉ một phần của các phép toán được giới thiệu trong đoạn thứ hai được sử dụng. Như vậy, đối với bài toán tối thiểu chính tắc, chỉ thực hiện được trường hợp đoạn 3.4.1 và chỉ cần thực hiện các thao tác sắp xếp lại các cột theo chu kỳ, đưa cột đi qua vùng viền dọc, sửa chữa các vi phạm về kết cấu và một phần thao tác cắt bớt. Một cách đối xứng, khi giải bài toán cực đại kinh điển, chỉ có trường hợp của đoạn 3.4.2 được thực hiện và các hoạt động sắp xếp lại các chuỗi theo chu kỳ, chuyển một chuỗi qua vùng biên ngang, sửa các vi phạm cấu trúc và một phần khác của hoạt động cắt ngắn là cần thiết. Nếu không thì không có gì chi tiết cụ thể bổ sung hình thức kinh điển của nhiệm vụ không thêm vào.

Đoạn đầu tiên của phần giới thiệu cho thấy làm thế nào một bài toán quy hoạch tuyến tính tổng quát có thể được rút gọn thành một trong các dạng chính tắc. Đối với các bài toán kinh điển, việc mô tả phương pháp cải tiến tuần tự được đơn giản hóa về mặt hình thức, vì không cần phải xem xét hai phương án vi phạm điều kiện tối ưu và hai phương án để đạt đến đỉnh tiếp theo. Tuy nhiên, điều này làm tăng kích thước của ma trận cơ sở A [ / , J ], chủ yếu xác định độ phức tạp. Tuy nhiên, trong nhiều trường hợp, việc áp dụng phương pháp này vào các dạng chính tắc của bài toán lại tỏ ra thích hợp hơn và trong phần này chúng ta sẽ tập trung vào các biến thể của phương pháp thu được cho các dạng tuyến tính cụ thể. các vấn đề về lập trình.

Trang: 1

Một phương pháp giải tích để giải bài toán quy hoạch tuyến tính là phương pháp đơn giản.Để áp dụng nó, các vấn đề LP được trình bày theo nhiều cách khác nhau, phải được rút gọn về dạng kinh điển. Bài toán quy hoạch tuyến tính viết dưới dạng (2.1.1)-(2.1.3) là dạng mở rộng của bài toán quy hoạch tuyến tính tổng quát (GLP).

Chúng ta sẽ gọi bài toán sau là bài toán quy hoạch tuyến tính chuẩn (CLPT):

dưới những hạn chế có dạng đẳng thức,

Nếu bài toán dạng (2.3.1)-(2.3.4) thỏa mãn điều kiện t = n, thì nghiệm của nó quy về giải hệ phương trình

(2.3.2) . Trong trường hợp này, bài toán sẽ không có lời giải nếu điều kiện
(2.3.3) không thỏa mãn hoặc hệ phương trình vô nghiệm.

tình trạng T

1. Đi từ vấn đề tối đa hóa hàm mục tiêu (2.3.1) để vấn đề giảm thiểuđủ lấy mọi hệ số Cj hàm mục tiêu có dấu hiệu ngược lại và giải quyết vấn đề đạt được ở mức tối đa. Sau khi tìm được giá trị cực đại, giá trị của hàm mục tiêu phải lấy dấu ngược lại. Giải pháp tối ưu sẽ vẫn như cũ.
2. Đi từ nhỏ hơn hoặc bằng ràng buộc đẳng thức nó là cần thiết bằng dấu cộng:

3. Đi từ ràng buộc “lớn hơn hoặc bằng” đến sự bình đẳng nó là cần thiết giới thiệu thêm một biến không âm bằng dấu trừ:

Trong trường hợp này, mỗi bất đẳng thức giới thiệu riêng của nó (n +/)-biến bổ sung thứ.

4. Mọi thứ đẳng thức có số hạng tự do âm được chia thành-1, để thỏa mãn điều kiện (2.3.4).
5. Nếu trên một số biến Xj điều kiện không âm không được áp đặt, Cái đó thực hiện thay đổi các biến Xj=x".- X" x"j > 0, x"> 0. Trong bài toán đã chuyển đổi tất cả các biến đều không âm.

Có một tuyên bố rằng bất kỳ ZLP nào cũng có thể được rút gọn thành dạng chuẩn.

Ví dụ 2.3.1. Hãy chuyển bài toán ở Ví dụ 2.2.2 sang dạng chính tắc. Hàm mục tiêu và hệ thống ràng buộc có dạng như sau:

Chúng ta hãy giới thiệu một biến bổ sung jc 3 > 0 với dấu cộng vào bất đẳng thức thứ nhất và vào bất đẳng thức thứ hai x 4> 0 với dấu trừ và ở phần thứ ba x 5> 0 cũng có dấu cộng. Kết quả là chúng ta thu được một hệ thống ràng buộc bài toán ở dạng chính tắc:

Với những hạn chế này, bạn cần tìm giá trị lớn nhất của hàm:

Hãy xem xét ý nghĩa kinh tế của các biến bổ sung trong vấn đề kinh điển sử dụng tối ưu các nguồn lực.

Ví dụ 2.3.2. Bài toán sử dụng tài nguyên tối ưu (bài toán thảm)[17J.

Nhà máy có sẵn một lượng tài nguyên nhất định thuộc ba loại: lao động (80 ngày công), nguyên liệu thô (480 kg) và thiết bị (130 giờ máy). Nhà máy có thể sản xuất bốn loại thảm. Thông tin về số lượng đơn vị của từng nguồn lực cần thiết để sản xuất một tấm thảm thuộc từng loại và thu nhập mà doanh nghiệp nhận được từ một đơn vị của từng loại sản phẩm được nêu trong Bảng. 2.3.1.

Cần phải tìm ra phương án sản xuất sao cho tổng chi phí đạt lớn nhất.

Mô hình kinh tế và toán học của bài toán Biến: x x, x 2, x 3, x 4 - số lượng thảm mỗi loại. Hàm mục tiêu - Tổng chi phí sản xuất cần tối đa hóa là:

Giới hạn tài nguyên:

Chúng ta hãy đưa vấn đề về dạng chính tắc bằng cách đưa thêm các biến x 5, x 6 Và x7:

Dưới đây sẽ chỉ ra rằng kế hoạch sản xuất tối ưu là vectơ X* =(0; 30; 10; 0), giá trị của hàm mục tiêu là 150, tức là Để tối đa hóa tổng chi phí sản xuất, cần sản xuất 30 tấm thảm loại thứ hai và 10 tấm thảm loại thứ ba. Hãy thay thế giá trị tối ưu vectơ X trong các hạn chế của KZLP:

Ta thấy nguồn lực “lao động” và “thiết bị” được sử dụng triệt để, nguồn “nguyên liệu” dồi dào:

Trong trường hợp này x vào cho thấy còn lại 200 kg nguyên liệu.

Vì vậy các biến chính x v x 2, x 3, x l có nghĩa là số lượng thảm của từng loại và các biến bổ sung x 5, x 6 họ 7 - khối lượng tài nguyên chưa được sử dụng đúng mức.

Trả lời. Kế hoạch sản xuất tối ưu X* = (0; 30;

10; 0).

Kế hoạch, hoặc giải pháp chấp nhận được, KZLP được gọi là vectơ X =(jc p X 2 ,..., x n), thỏa mãn điều kiện (2.3.2)-(2.3.4).

Nếu tất cả các thành phần của nghiệm cơ bản của hệ ràng buộc CLLP đều không âm thì nghiệm đó được gọi là giải pháp tham khảo hoặc kế hoạch tham khảo Số lượng thành phần tích cực của phương án tham chiếu không được vượt quá T.

Kế hoạch tham khảo được gọi là không thoái hóa, nếu nó chứa T thành phần tích cực, nếu không nó được gọi là thoái hóa.

Phương án tối ưu hoặc giải pháp tối ưu Phương án được gọi là phương án mang lại giá trị lớn nhất (nhỏ nhất) của hàm tuyến tính (2.3.1).

Tập hợp tất cả các kế hoạch của PPP (nếu có) là đa diện lồi. Mỗi điểm góc (cực) của khối đa diện nghiệm tương ứng với kế hoạch tham khảo(các nghiệm cơ bản không âm của hệ phương trình KZLP). Mỗi kế hoạch tham chiếu được xác định bởi hệ thống T các vectơ độc lập tuyến tính chứa trong một hệ thống nhất định của P vectơ D, D,..., Một trang. Nếu có một phương án tối ưu thì sẽ có một điểm góc của khối đa diện quyết định mà tại đó hàm tuyến tính đạt giá trị lớn nhất (nhỏ nhất).

Để tìm ra phương án tối ưu, chỉ cần kiểm tra các phương án tham khảo là đủ. Giới hạn trên của số lượng sơ đồ tham chiếu có trong một bài toán được xác định bằng số cách kết hợp S t p (xem đoạn 1.4).

Ví dụ 2.3.3. Tìm giải pháp cho vấn đề về sử dụng tối ưu nguồn lực hạn chế (giải AP P):

Giải pháp. Chúng ta hãy đưa vấn đề về dạng chính tắc bằng cách giới thiệu các biến bổ sung x 3, x 4 và x 5:

Hãy cùng tìm tất cả các phương án hỗ trợ của hệ thống hạn chế của KZLP này (l? - 5; /77 - 3); số lượng của chúng không vượt quá 10:

Sử dụng phương pháp Jordan-Gauss (xem đoạn 1.4), ta viết được tất cả các nghiệm cơ bản của hệ phương trình (Bảng 2.3.2).

Con số nền tảng không các giải pháp	Nền tảng	Kế hoạch

Trong số mười giải pháp cơ bản năm hỗ trợ:

Các kế hoạch tham khảo được chỉ định trong Hình. 2.3.1 tương ứng với các điểm góc sau và các giá trị của CF trong đó:

Cơm. 2.3.1.

Theo lý thuyết LP giải pháp tối ưu nằm trong số các kế hoạch tham khảo.

Như vậy hàm mục tiêu đạt giá trị lớn nhất bằng 2300 tại điểm TRONG về kế hoạch tham khảo X 5 = (70; 80; 0; 60; 0).

Trả lời. Kế hoạch nhiệm vụ tối ưu: x ( = 70, x 2 = 80, giá trị hàm mục tiêu f(x v x 2) = 2300.

nhiệm vụ MP

ZLP chung được gọi là <,=,>=)bi (i=1,n) (2) phụ thuộc xj>

đối xứng < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Chuẩn Trộn.

tối thiểu f(x) = -max(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Giải thích hình học của hàm mục tiêu và các ràng buộc của ZLP. Công thức hình học của ZLP.

Giả sử bài toán f=c1x1+c2x2-max (1)

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

Sơ đồ của bài toán (x1,x2) là một điểm trên mặt phẳng. Mỗi bất đẳng thức có 2 cách biểu diễn. là một nửa mặt phẳng. Nửa mặt phẳng là một tập lồi. lồiđược gọi là một tập hợp trong đó các điểm của đoạn nối (x1 và x2) thuộc tập hợp này cũng thuộc tập hợp đó. C-ma 2 biểu thị giao điểm của hai nửa mặt phẳng. Khi băng qua bạn có thể nhận được:

1) vùng kín đa giác lồi.

2) diện tích đa giác mở lồi

3) điểm duy nhất

4) bộ trống

5) chùm và đoạn

Giải thích hình học của hàm mục tiêu: Hàm 1 là họ các đường thẳng song song, được gọi là đường mức (đường có giá trị không đổi của hàm mục tiêu). Đạo hàm riêng của hàm số đối với x1 và x2 biểu thị tốc độ tăng của hàm mục tiêu dọc theo tọa độ của các trục. Vectơ chuyển màu thể hiện hướng tăng nhanh nhất của hàm mục tiêu.Đối với bài toán 1-3, vectơ gradient = (c1; c2) rời khỏi điểm (0,0) và hướng đến điểm có tọa độ (c1; c2). Vectơ gradient vuông góc với các đường mức. Giao điểm của hai nửa mặt phẳng thường được gọi là lĩnh vực giải pháp được chấp nhận (ADD).

Định lý cơ bản của LP. Sơ đồ nghiệm của ZLP, suy ra từ định lý này.

Nếu ZLP có nghiệm thì hàm mục tiêu đạt giá trị cực trị tại ít nhất một trong các điểm cực trị của khối đa diện phẳng. Nếu hàm mục tiêu đạt đến một giá trị cực trị tại nhiều hơn một điểm cực trị, thì nó đạt đến một và cùng một giá trị tại bất kỳ điểm nào, đó là sự kết hợp tuyến tính lồi của chúng. Tại quyết định của PPP Thật thuận tiện khi sử dụng mục nhập bảng theo cách thủ công.

BP		SP -Xm+1 -Xm+2 -Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
f	ôi	bo1 bo2 bon-m

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

1. Đưa mô hình bài toán về dạng chính tắc;

2. tìm kế hoạch tham khảo ban đầu;

3. viết bài toán dưới dạng đơn giản. bàn;

5. chuyển sang một kế hoạch tham khảo mới, một bản giao hưởng mới. bàn. Để chuyển sang gói tham chiếu mới, chỉ cần thay thế một biến cơ bản bằng một biến miễn phí là đủ. Biến có trong cơ sở và cột độ phân giải tương ứng được xác định bởi phần tử âm tuyệt đối lớn nhất của hàng f. Biến loại trừ khỏi cơ sở và đường phân giải tương ứng được xác định bằng tỷ lệ đơn hình nhỏ nhất, tức là. mối quan hệ giữa các phần tử của cột đơn vị với phần tử tương ứng của cột độ phân giải. Tỷ lệ đơn giản là một đại lượng không âm. Tại giao điểm của hàng phân giải và cột phân giải có một phần tử phân giải, mà phép biến đổi đơn giản được thực hiện theo cách sau. quy tắc: 1. các phần tử của chuỗi cho phép được chia thành phần tử cho phép; 2. Các phần tử của cột độ phân giải được chia thành phần tử độ phân giải và đổi dấu ngược lại; 3. Các phần tử còn lại của bảng được sắp xếp lại theo quy tắc hình chữ nhật:

bij bis bkj=(bkj*bis-bij*bks)/bi

Định lý nhị nguyên thứ hai.

nếu một trong các bài toán kép có phương án tối ưu thì bài toán kia cũng có thể giải được, tức là. có một kế hoạch quang học. Trong trường hợp này, các giá trị cực trị của hàm mục tiêu trùng nhau (j=từ 1 đến n) Σcjxj*= (i=từ 1 đến m)Σbiyi* nếu ở bản gốc. vấn đề, hàm mục tiêu là không giới hạn trên tập kế hoạch, thì trong vấn đề kép hệ thống hạn chế không nhất quán.

Định lý về hạng của ma trận TK.

Hạng của ma trận A của bài toán vận chuyển nhỏ hơn số phương trình: r(A)=m+n-1 một đơn vị.

39. Thuật toán xây dựng sơ đồ tham chiếu ban đầu của ZLP.

Để tìm kế hoạch tham khảo ban đầu, chúng tôi có thể đề xuất như sau thuật toán:

1. Viết bài toán dưới dạng bảng Jordan sao cho tất cả các phần tử của cột số hạng tự do đều không âm, tức là. bất đẳng thức aio>=0 (i=1,m) được thỏa mãn. Những phương trình trong đó số hạng tự do âm trước tiên được nhân với -1.

		-x1….. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	tình yêu	am1…..amn
f=		-c1…. -cn

Chuyển đổi bảng bằng các bước loại bỏ Jordan, thay thế các số 0 ở cột bên trái bằng x tương ứng. Đồng thời, tại mỗi bước cho phép có thể được lựa chọn bất kỳ cột nào chứa ít nhất một phần tử dương. Hàng phân giải được xác định bằng tỷ lệ nhỏ nhất của các số hạng tự do với các phần tử dương tương ứng của cột phân giải. Nếu trong quá trình loại bỏ, gặp một hàng 0, tất cả các phần tử của nó đều bằng 0 và số hạng tự do khác 0 thì hệ phương trình ràng buộc không có nghiệm. Nếu chúng ta gặp một hàng 0 trong đó, ngoài số hạng tự do, không có phần tử dương nào khác, thì tập phương trình giới hạn không có nghiệm không âm. chung, thì sau một số bước nhất định, tất cả các số 0 ở cột bên trái sẽ được thay thế bằng x và từ đó có được một cơ sở nhất định và do đó, một sơ đồ tham chiếu tương ứng.

40. Thuật toán xây dựng sơ đồ tham chiếu tối ưu của ZLP.

Kế hoạch hỗ trợ ban đầu của Hồ được kiểm tra tính tối ưu.

Nếu không có phần tử âm nào trong hàng f (không tính số hạng tự do) thì -plan là tối ưu. Nếu cũng không có phần tử 0 nào trong hàng f thì chỉ có một phương án tối ưu; nếu trong số các phần tử có ít nhất một phần tử bằng 0 thì có vô số phương án tối ưu. Nếu có ít nhất một phần tử âm trong hàng f và không có phần tử dương nào trong cột tương ứng thì hàm mục tiêu không bị giới hạn trong vùng khả thi. Vấn đề không thể giải quyết được. Nếu có ít nhất một phần tử âm trong hàng f và trong mỗi cột có phần tử như vậy có ít nhất một phần tử dương, thì bạn có thể chuyển sang sơ đồ tham chiếu mới gần với sơ đồ tối ưu hơn. Để làm điều này, cột có phần tử âm trong hàng f được lấy là dễ dãi; Họ xác định chuỗi phân giải từ quan hệ đơn hình tối thiểu và thực hiện bước loại bỏ Jordan. Kế hoạch tham chiếu thu được một lần nữa được kiểm tra để tìm mức tối ưu. Điều này được lặp lại cho đến khi tìm được phương án tham chiếu tối ưu hoặc tính không thể giải quyết được của vấn đề được xác lập.

Thuật toán của phương pháp Gomori.

1. Bằng phương pháp đơn hình tìm ra phương án tối ưu của bài toán. Nếu tất cả các thành phần của một phương án tối ưu đều là số nguyên thì phương án đó là tối ưu. Nếu không thì chuyển sang bước 2

2. Trong số các thành phần không nguyên, bạn nên chọn thành phần có phân số là lớn nhất và sử dụng hàng tương ứng của bảng đơn, xây dựng đường cắt chính xác bằng công thức

(n-m,s=1)∑ (αkm+1)Xm+1 ≥(βk)

3. Chuyển đổi bất đẳng thức đã xây dựng thành đẳng thức 0 tương đương và đưa nó vào bảng đơn với phương án tối ưu không nguyên

4. Bài toán mở rộng thu được được giải bằng phương pháp đơn hình. Nếu kế hoạch kết quả không phải là số nguyên, hãy chuyển sang bước 2.

Nếu trong quá trình giải, một dòng xuất hiện với số hạng tự do không nguyên và các hệ số nguyên khác, thì phương trình tương ứng không có nghiệm là số nguyên. Trong trường hợp này, và vấn đề ban đầu không thể giải được trong số nguyên.Phương pháp của Gomori có ứng dụng hạn chế. Với sự trợ giúp của nó, bạn nên giải quyết các vấn đề nhỏ, bởi vì... số lượng tương tác có thể rất lớn.

Các dạng ký hiệu khác nhau của ZLP (chung, chuẩn, đối xứng)

nhiệm vụ MP: xác định phương án tối ưu, xác định khối lượng sản lượng tối ưu, xác định sự kết hợp tối ưu giữa các loại cây trồng, hình thành gói tài sản tối ưu, tối đa hóa lợi nhuận ngân hàng, v.v.

ZLP chung được gọi là vấn đề tối đa hóa (tối thiểu hóa) hàm tuyến tính f=Σcj*xj-max(min) (1) dưới các giới hạn tuyến tính ∑aij *xj(=<,=,>=)bi (i=1,n) (2) được cung cấp xj>=0(j=1,n1), xj-tùy ý (j=n1+1,n)(3) trong đó cj,aij, hai hằng số .

đối xứng Dạng viết ZLP gọi là bài toán cực đại hóa hàm (1) dưới ràng buộc tuyến tính trong bất đẳng thức có dấu< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >hoặc = và các biến không âm. Chuẩn hình thức ghi PAP được gọi là một nhiệm vụ hàm tối đa(1) dưới các ràng buộc tuyến tính của đẳng thức và các biến không âm. Bất kỳ hình thức nào khác được gọi là Trộn.

tối thiểu f(x) = -max(-f(x))

Việc chuyển bất đẳng thức thành phương trình và ngược lại được thực hiện trên cơ sở Bổ đề: với mọi nghiệm x1...xn của bất đẳng thức a1x1+...+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) và ngược lại. Mọi nghiệm x1…xn,xn+1 của phương trình 6 và bất đẳng thức 7 đều tương ứng với nghiệm x1…xn của bất đẳng thức 5.

Để chuyển từ dạng back sim sang dạng back canonical bạn phải nhập các biến cân bằng (cân bằng).Điều này dựa trên định lý bất đẳng thức: bất kỳ bất đẳng thức nào cũng có thể được biểu diễn dưới dạng phương trình hoặc bất đẳng thức đơn giản.