Mô hình này được gọi là kinh điển. Dạng chính tắc của một bài toán quy hoạch tuyến tính
Phương pháp phân tích để giải quyết vấn đề lập trình 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 ký hiệu mở rộng nhiệm vụ chung lập trình tuyến tính (LPP).
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:
Chúng ta hãy xem xét ý nghĩa kinh tế của các biến bổ sung trong bài toán kinh điển về việc sử dụng tối ưu các nguồn tài nguyên.
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 ,..., xn), 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 PLP là kế hoạch mang lại giá trị lớn nhất (nhỏ nhất) 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. Hãy giảm vấn đề xuống hình thức kinh điển 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 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.
Bài toán quy hoạch tuyến tính có dạng ax = b trong đó a là ma trận hệ số, b là vectơ ràng buộc.
Ví dụ:
Trong mỗi bài toán LP, giá trị của biến được tìm với điều kiện:
- những giá trị này thỏa mãn một số hệ thống Các phương trình tuyến tính hoặc sự bất bình đẳng;
- tại các giá trị này, hàm mục tiêu sẽ chuyển sang mức tối thiểu hoặc tối đa.
Hướng dẫn. Chọn số lượng biến và số lượng hàng (số lượng ràng buộc). Giải pháp thu được được lưu trong tệp Word.
Một trong phương pháp phổ quát LP là một phương pháp đơn giản, tuy nhiên, có thể được sử dụng nếu bài toán LP có dạng chính tắc.
Sự định nghĩa. Bài toán LP có dạng chính tắc nếu tất cả các ràng buộc của hệ thống chỉ bao gồm các phương trình (ngoại trừ các bất đẳng thức biểu thị tính không âm của các biến) và hàm mục tiêu phải được cực tiểu hóa.
Một ví dụ về bài toán LP như vậy ở dạng chính tắc là Bài toán 1 – bài toán vận chuyển cân bằng với hệ các ràng buộc (1) và hàm mục tiêu (2).
Tuy nhiên, trong hầu hết nhiệm vụ kinh tế Thông thường, hệ thống ràng buộc ban đầu không chỉ bao gồm các phương trình mà còn bao gồm các bất đẳng thức.
Tuyên bố. Bất kỳ bài toán LP tổng quát nào cũng có thể được quy về dạng chính tắc.
Việc giảm bài toán LP tổng quát về dạng chính tắc có thể đạt được bằng cách đưa vào các biến mới (chúng được gọi là các biến bổ sung).
Hệ ràng buộc (3) của bài toán này gồm 4 bất đẳng thức. Bằng cách giới thiệu các biến bổ sung y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, ta có thể đi đến hệ điều kiện: 
Các biến bổ sung này y tôi có một ý nghĩa kinh tế hoàn toàn rõ ràng, cụ thể là, chúng có nghĩa là lượng thời gian làm việc không được sử dụng (thời gian ngừng hoạt động của máy Tôi-loại thứ).
Ví dụ: nếu máy thuộc loại thứ nhất làm việc suốt 18 giờ thì x + y = 18, do đó y 1 = 0. Nhưng chúng tôi cho phép khả năng sử dụng không đầy đủ thời gian hoạt động của máy thứ nhất x + y<18. В этом случае y 1 mang giá trị dương và có thể được coi là giới hạn thời gian chưa sử dụng. Ví dụ: biết giải pháp cho vấn đề này từ đoạn 3.3.2, x = 12, y= 6, từ hệ hạn chế (3.9) ta có thể kết luận rằng y 1 = y 2 = y 3 = 0, và y 4 = 12 – 6 = 6. Tức là các máy loại một, loại hai, loại ba sử dụng hoàn toàn thời gian làm việc. Nhưng máy thứ tư chỉ hoạt động được một nửa, trong 6 giờ và ở trạng thái không hoạt động, theo phương án tối ưu. Có lẽ, sau những kết luận như vậy, người đứng đầu doanh nghiệp sẽ muốn gánh công việc khác, cho thuê lại thời gian này, v.v.
Vì vậy, bằng cách đưa vào các biến bổ sung, chúng ta có thể giảm bất kỳ ràng buộc loại bất đẳng thức nào đối với một phương trình.
Hãy xem xét vấn đề hỗn hợp. Hệ điều kiện hạn chế có dạng: 
Các bất đẳng thức hướng về phía “nhiều hơn”, do đó khi đưa thêm các biến y 1, y 2, y 3 ≥ 0 thì phải trừ vế trái để cân bằng với vế phải. Chúng tôi thu được một hệ thống hạn chế ở dạng chính tắc:
Các biến y i cũng sẽ có ý nghĩa kinh tế. Nếu nhớ lại nội dung thực tế của bài toán thì biến y 1 sẽ là lượng chất dư A có trong hỗn hợp, y 2 là lượng chất dư TRONG trong hỗn hợp y 3 – thặng dư VỚI trong hỗn hợp.
Nhiệm vụ tìm giá trị lớn nhất của hàm mục tiêu có thể được rút gọn thành việc tìm giá trị nhỏ nhất của hàm - F do tính hiển nhiên của phát biểu max F = –min (- F). Nhìn vào bức tranh: nếu tại một thời điểm nào đó x= x 0 chức năng y= F(x) đạt cực đại thì hàm số y= –F(x), đối xứng với nó so với trục CON BÒ ĐỰC, tại cùng một điểm x 0 sẽ đạt mức tối thiểu và F tối đa = – (– F phút) tại x = x 0 .
Phần kết luận.Để biểu diễn bài toán LP ở dạng chính tắc cần thiết:
- chuyển các bất đẳng thức có trong hệ ràng buộc của bài toán thành phương trình bằng cách đưa thêm các biến;
- nếu hàm mục tiêu F→max (tối đa hóa), nó được thay thế bằng hàm – F→ phút (được giảm thiểu).
hình thức kinh điển, nếu bạn muốn cực đại hóa hàm mục tiêu, tất cả các ràng buộc của hệ thống đều là phương trình và điều kiện không âm được áp đặt cho tất cả các biến.
Bài toán quy hoạch tuyến tính được đưa ra ở hình dạng đối xứng, nếu cần cực đại hóa hàm mục tiêu thì mọi ràng buộc của hệ thống là các bất đẳng thức “” (hoặc cực tiểu hóa hàm mục tiêu, mọi ràng buộc của hệ thống là các bất đẳng thức “”) và điều kiện không âm được áp đặt cho tất cả các biến.
Một tập hợp số được gọi giải pháp chấp nhận được (kế hoạch), nếu nó thỏa mãn hệ thống giới hạn của ZLP.
Tập hợp tất cả các giải pháp khả thi được gọi là lĩnh vực giải pháp khả thi(ODR).
Một giải pháp chấp nhận được để đạt được giá trị tối đa (tối thiểu) của hàm được gọi là kế hoạch tối ưu cho PAP.
Các thuật ngữ “kế hoạch” và “kế hoạch tối ưu” bắt nguồn từ các ứng dụng kinh tế.
Cả ba dạng ghi ZLP đều tương đương nhau theo nghĩa là có các thuật toán để chuyển từ dạng này sang dạng khác. Như vậy, nếu có cách giải một bài toán ở một trong các dạng thì luôn có thể xác định được phương án tối ưu cho bài toán được đưa ra ở bất kỳ dạng nào khác. Bài toán ở dạng đối xứng được giải bằng phương pháp đồ họa và ở dạng chính tắc bằng phương pháp đơn hình.
Hãy xem xét các thuật toán chuyển đổi từ dạng này sang dạng khác.
Đối xứng chính tắc. Việc chuyển đổi được thực hiện bằng cách thêm một biến không âm vào vế trái của mỗi bất đẳng thức. Nếu bất đẳng thức là “<”, thì biến số dư được cộng vào vế trái của bất đẳng thức bằng dấu “+”. Nếu bất đẳng thức là “”, thì biến số dư được thêm vào vế trái của bất đẳng thức với dấu “-”. Các biến mới được giới thiệu được gọi là bảng cân đối kế toán. Bài toán tối thiểu hóa hàm Z được thay thế bằng bài toán cực đại hóa hàm (–Z) và người ta sử dụng min Z = –max (–Z).
Chính tắc đối xứng.Để thực hiện quá trình chuyển đổi như vậy, người ta tìm ra nghiệm tổng quát của hệ phương trình – ràng buộc, hàm mục tiêu được biểu diễn dưới dạng các biến tự do. Tiếp theo, lợi dụng tính không âm của các biến cơ bản, chúng ta có thể loại chúng ra khỏi bài toán. Dạng đối xứng của bài toán sẽ chứa các bất đẳng thức chỉ liên quan đến các biến tự do và hàm mục tiêu chỉ phụ thuộc vào các biến tự do. Giá trị của các biến cơ bản được tìm từ nghiệm tổng quát của hệ phương trình ban đầu.
Tổng quát kinh điển. Mỗi biến không áp đặt điều kiện không âm được biểu diễn dưới dạng hiệu của hai biến không âm mới. Các bất đẳng thức được chuyển đổi thành các phương trình bằng cách đưa vào một biến cân bằng ở vế trái của mỗi bất đẳng thức giống như cách được mô tả trong quá trình chuyển đổi từ dạng đối xứng sang dạng chính tắc. Bài toán cực tiểu hóa hàm Z được thay thế bằng bài toán cực đại hóa hàm (–Z) theo cách tương tự như đã được mô tả trong quá trình chuyển đổi từ dạng đối xứng sang dạng chính tắc.
Phương pháp đồ họa để giải bài toán quy hoạch tuyến tính
Tập hợp các điểm được gọi là lồi, nếu với hai điểm bất kỳ của tập hợp thì nó chứa một đoạn nối chúng.
ví dụ 1
Tập hợp các điểm sau đây trên mặt phẳng là lồi:
Các tập điểm sau đây trên mặt phẳng không lồi: 
Định lý 1 Giao của một số tập lồi bất kỳ là một tập lồi.
Định lý 2 Cho có hai điểm tùy ý trong không gian R N. Khi đó với bất kỳ điểm nào của đoạn [ PQ] phải được thực thi: .where .
Siêu phẳng trong không gian R N là tập hợp các điểm thỏa mãn phương trình. Lưu ý rằng trong trường hợp hai chiều siêu phẳng là một đường thẳng.
Nửa không gian là tập hợp các điểm thỏa mãn một trong các bất đẳng thức hoặc . Siêu phẳng chia các điểm trong không gian thành hai nửa không gian. Trong trường hợp hai chiều, siêu phẳng là một nửa mặt phẳng.
Định lý 3 Nửa không gian là một tập lồi.
Kết quả Giao của một số nửa không gian bất kỳ là một tập lồi.
đa diệnđược gọi là giao của một hoặc nhiều nửa không gian. Một khối đa diện trong trường hợp hai chiều được gọi là đa giác.
Ví dụ 2
Các tập hợp sau đây là đa giác.
Bộ giới hạn
Bộ không giới hạn
Điểm duy nhất
Bộ trống
Điểm của tập lồi được gọi là góc cạnh, nếu nó không nằm trong bất kỳ đoạn nào nối hai điểm khác trong tập hợp.
Ví dụ 3
Các điểm góc của một tam giác là các đỉnh của nó (có ba đỉnh). Các điểm góc của một vòng tròn là các điểm của đường tròn bao quanh nó (có vô số điểm).
Điểm góc của khối đa diện được gọi là đứng đầu.
Chúng ta hãy xem xét ZLP được cho ở dạng đối xứng.
Định lý 4 Sơ đồ tối ưu của ZLP tương ứng với đỉnh của khối đa diện quyết định được xác định bởi hệ ràng buộc của nó.
Bất kỳ bài toán quy hoạch tuyến tính nào cũng có thể được quy giản thành bài toán quy hoạch tuyến tính ở dạng chính tắc. Để làm được điều này, trong trường hợp tổng quát, 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 đưa một bài toán quy hoạch tuyến tính về dạng chính tắc như sau:
- nếu trong bài toán ban đầu cần xác định giá trị lớn nhất của 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 phía bên phải của các hạn chế là âm thì hạn chế 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 xj 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 vế trái bằng dấu “+”, và vào 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 giả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.
Các trường hợp sau có thể xảy ra khi giải bài toán trên tối đa:
1. Nếu tất cả các hệ số ở hàng cuối cùng của bảng đơ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 hệ số âm lớn nhất về giá trị tuyệt đối.
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. Thuộc tính quan trọng nhất của bất kỳ thuật toán tính toán nào là sự 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ặ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ể phát sinh ở khâu chọn giá trị r (phần 2”) trong trường hợp có cùng giá trị nhỏ nhất của tỷ số
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.
