Các dạng viết bài toán lập trình tuyến tính đa dạng.
Trong trường hợp tổng quát, một bài toán lập trình tuyến tính được viết sao cho cả phương trình và bất phương trình đều là các ràng buộc, và các biến có thể vừa không âm vừa biến 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 thỏa mãn điều kiện không âm thì bài toán lập trình tuyến tính được gọi là chính tắc. Nó có thể được biểu diễn dưới dạng ký hiệu tọa độ, vectơ hoặc ma trận.
1. Bài toán lập trình tuyến tính chính tắc trong kí hiệu tọa độ có dạng
.
Trong một hình thức nhỏ gọn hơn, bài toán này có thể được viết bằng cách sử dụng dấu tổng kết,
(1.7)
2. Bài toán lập phương trình tuyến tính chính tắc trong kí hiệu vectơ có dạng
(1.8)
ở đâu 
,
.
3. Bài toán lập trình 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, NS- cột ma trận của các biến vấn đề, - cột ma trận của vế phải của hệ thống ràng buộc.
Thường được sử dụng là các bài toán lập trình tuyến tính được gọi là đối xứng, trong ký hiệu ma trận có dạng
(1.10)
(1.11)
1.4. Rút gọn vấn đề lập trình tuyến tính tổng quát
sang dạng chuẩn
Trong hầu hết các phương pháp giải các bài toán lập trình tuyến tính, người ta cho rằng hệ thống các ràng buộc bao gồm các phương trình và các điều kiện tự nhiên đối với tính không phủ định của các biến. Tuy nhiên, khi biên soạn các mô hình toán các bài toán kinh tế, các ràng buộc chủ yếu được hình thành thành các hệ bất phương trình, do đó cần có khả năng chuyển từ hệ bất phương trình sang hệ phương trình. Cuối cùng, chúng tôi chứng minh định lý sau.
Định lý 1.1. Thay một bất đẳng thức bằng một phương trình. Đối với mọi quyết định 
sự bất bình đẳng
có một nghiệm duy nhất cho phương trình
và 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 phương trình (1.14) tương ứng với một nghiệm duy nhất của bất phương trình (1.12).
Bằng chứng.Để cho được 
Khi đó, là một nghiệm cho bất phương trình (1.12). Chúng ta biểu thị sự khác biệt giữa vế phải và vế trái của bất bình đẳng này bằng, tức là
Rõ ràng 
... Hãy để chúng tôi thay thế trong phương trình (1.13) thay vì các biến các giá trị 
, chúng tôi nhận được
Do đó, nó thỏa mãn phương trình (1.13) và bất phương trình (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 để nó thỏa mãn phương trình (1.13) và bất đẳng thức (1.14), tức là, chúng ta có
VÀ 
Loại bỏ đại lượng không âm ở bên trái của đẳng thức cuối cùng, chú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 một bất đẳng thức, thì một biến bổ sung không âm phải được đưa vào bên trái của nó với một 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 phương trình được gọi là các 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 không 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 tự ý thay đổi, thì bất kỳ biến nào như vậy được thay thế bằng hiệu của hai biến không âm, tức là. 
, ở đâu 
và 
.
Đôi khi cần chuyển bài toán từ tìm giá trị nhỏ nhất sang tìm giá trị lớn nhất, hoặc ngược lại. Để làm điều này, chỉ cần thay đổi dấu hiệu của tất cả các hệ số của hàm mục tiêu thành ngược lại, và giữ nguyên phần còn lại của bài toán. Các giải pháp 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 nhau, và các giá trị của hàm mục tiêu trên các giải pháp tối ưu chỉ khác nhau về dấu hiệu.
Ví dụ 1.1.Đưa bài toán lập trình tuyến tính về dạng chính tắc.
| NS |
Dung dịch... Chúng ta hãy chuyển sang vấn đề tìm cực đại của hàm mục tiêu. Để làm điều này, chúng tôi thay đổi các dấu hiệu của các hệ số hàm mục tiêu. Để biến đổi hệ thống các ràng buộc thành phương trình của bất phương trình thứ hai và thứ ba, chúng tôi giới thiệu các biến bổ sung không âm (trên mô hình toán học, phép toán này được đánh dấu bằng chữ D). Biến được đưa vào bên 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 bên 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 không. Biến không tuân theo điều kiện không âm được thay thế bằng hiệu 
, 
... Viết vấn đề ở dạng chuẩn
Trong một số trường hợp, cần giảm bài toán chính tắc thành bài toán đối xứng. Hãy xem một ví dụ.
Ví dụ 1.2. Rút gọn bài toán lập trình tuyến tính về dạng đối xứng
Trong cài đặt ban đầu, các LPP có thể thừa nhận nhiều hình thức ghi âm khác nhau. Vì vậy, trong một số nhiệm vụ, nó được yêu cầu để tối đa hóa chức năng mục tiêu, trong những nhiệm vụ khác - để giảm thiểu; một số ràng buộc tuyến tính có thể ở dạng bình đẳng, những ràng buộc khác ở dạng bất bình đẳng, v.v.
Đối với tính đồng nhất của bản ghi LPP, cái gọi là hình thức kinh điển Hồ sơ.
Họ nói rằng ZLP được viết ở dạng chuẩn nếu nó có dạng sau:
Lưu ý các đặc điểm sau của biểu mẫu chuẩn:
1) nó được yêu cầu để giảm thiểu hàm mục tiêu;
2) tất cả các ràng buộc tuyến tính, ngoại trừ yêu cầu về tính không phủ định của các biến, đều có dạng bằng nhau;
tất cả các biến đều tuân theo các yêu cầu không phủ định.
Hãy để chúng tôi chứng minh rằng bất kỳ LPP nào cũng có thể được rút gọn thành dạng chuẩn.
1) Nếu trong LPP bắt buộc phải đạt cực đại hàm mục tiêu f, thì chúng ta đặt g = - f và yêu cầu hàm g phải được tối thiểu hóa. Bạn nhận được một LPP mới, tương đương với LPP ban đầu theo nghĩa là mỗi giải pháp tối ưu cho vấn đề ban đầu sẽ là giải pháp tối ưu cho vấn đề mới và ngược lại.
2) Giả sử rằng LPP có một ràng buộc tuyến tính có dạng
Chúng tôi thay thế ràng buộc này bằng hai ràng buộc sau:
ở đâu z - một biến mới được đưa vào hàm mục tiêu với hệ số bằng 0 (nói cách khác, biến z không được nhập vào hàm mục tiêu). Giá trị của biến z có thể được bỏ qua sau khi giải một bài toán mới.
Tương tự, ràng buộc khung nhìn được thay thế bằng hai ràng buộc:
3) Giả sử rằng trong LPP, không phải tất cả các biến đều được yêu cầu là không âm. Sau đó, mỗi biến 
, trên đó yêu cầu về tính không âm không được áp đặt, có thể được biểu diễn dưới dạng hiệu số của hai biến không âm:
Mỗi lần xuất hiện một biến 
vào hàm mục tiêu hoặc các ràng buộc, chúng tôi thay thế sự khác biệt 
... Sau khi giải quyết vấn đề mới với sự trợ giúp của (2.6), chúng ta quay trở lại các biến trước đó.
Với các phương pháp được chỉ định, bất kỳ LPP nào cũng được giảm xuống dạng chuẩn.
Thí dụ. Đưa về dạng chuẩn
Hãy thực hiện các hành động được mô tả.
Bây giờ chúng ta nhận được ZLP ở dạng chuẩn:
2.7. Khái niệm về phương án cơ bản zlp.
Hãy để ILP được đưa ra ở dạng chính tắc (2.3 - 2.5). Giả sử rằng hệ phương trình (2.4) được rút gọn thành dạng Jordan với các vế phải không âm:
(2.6)
ở đâu 
.
Cân bằng các biến tự do bằng 0, chúng ta thu được nghiệm cơ bản của hệ thống (2.4)
Do điều kiện 
tập giá trị của các biến (2.7) cũng thỏa mãn các ràng buộc (2.5). Do đó (2,6) là quyết định có thể chấp nhận được của LPP.
Một giải pháp khả thi (2.7) được gọi là cơ bản có thể chấp nhận quyết định hoặc kế hoạch cơ bản của ZLP.Đồng thời, họ nói rằng các biến 
tạo thành một cơ sở có thể chấp nhận được.
Nó chỉ ra rằng nếu ODR được mô tả bằng hình học, thì mỗi mặt bằng cơ sở của ZLP tương ứng với đỉnh của đa diện. Do đó, định lý sau là đúng.
Nếu LPP có thể giải quyết được thì cần có phương án hỗ trợ tối ưu.
3. Phương pháp Simplex để giải zlp
3.1. Đặc điểm chung và các giai đoạn chính của phương pháp simplex
Người sáng lập ra phương pháp simplex là nhà toán học Liên Xô L.V. Kantorovich và nhà toán học người Mỹ J. Danzig.
Bất kỳ LPP nào cũng có thể được giải quyết bằng phương pháp simplex hoặc tính không xác định của nó có thể được phát hiện. Nhiều lớp đặc biệt của LPP có thể được giải quyết bằng các phương pháp khác hiệu quả hơn cho các lớp này. Tuy nhiên, ưu điểm của phương pháp simplex là tính linh hoạt của nó. Đối với hầu hết tất cả các máy tính, các chương trình tiêu chuẩn đã được phát triển để giải quyết LPP bằng phương pháp simplex.
Hãy để chúng tôi mô tả ý tưởng chung của phương pháp simplex.
Chúng tôi giả định rằng LPP được viết ở dạng chuẩn và hàm mục tiêu cần được giảm thiểu. Như chúng ta đã biết, phương án tối ưu nên được tìm kiếm trong số các phương án hỗ trợ của LPP. Phương pháp simplex không lặp lại tất cả các kế hoạch cơ sở (điều này thường là không thể do số lượng lớn của chúng), nhưng, bắt đầu từ một số kế hoạch cơ sở ban đầu, nó tuần tự chuyển sang các kế hoạch cơ sở khác với hàm mục tiêu giảm. Phương pháp simplex ngừng hoạt động khi tìm thấy một kế hoạch cơ sở tối ưu hoặc vấn đề được phát hiện là không thể giải quyết được.
Khi giải quyết LPP bằng phương pháp simplex, có thể phân biệt các giai đoạn sau:
1) đưa LPP về dạng chuẩn;
2) giảm hệ phương trình tuyến tính về dạng Jordan với vế phải không âm với việc kiểm tra đồng thời tính không xác định của LPP do sự không nhất quán của hệ thống các ràng buộc tuyến tính;
3) nghiên cứu kế hoạch tham chiếu để có tính tối ưu;
4) điều tra LPP về tính không xác thực do không có giới hạn từ bên dưới đối với ODR của hàm mục tiêu;
5) chuyển đổi sang một kế hoạch tham chiếu mới, "tốt hơn".
Một phương pháp phân tích để giải một bài toán lập trình tuyến tính là phương pháp simplex.Đối với ứng dụng của nó, các vấn đề LP, được trình bày theo những cách khác nhau, phải được rút gọn về dạng chính tắc. Bài toán lập trình tuyến tính, được viết dưới dạng (2.1.1) - (2.1.3), là một dạng mở rộng của bài toán lập trình tuyến tính tổng quát (LPP).
Bài toán sau sẽ được gọi là bài toán lập trình tuyến tính chuẩn (LCPP):
dưới những ràng buộc dưới dạng bình đẳng,
Nếu bài toán dạng (2.3.1) - (2.3.4) thỏa mãn điều kiện m = n, thì nghiệm của nó được rút gọn thành giải hệ phương trình
- (2.3.2). Trong trường hợp này, vấn đề sẽ không có giải pháp nếu điều kiện
- (2.3.3) không thỏa mãn hoặc hệ phương trình không có nghiệm.
tình trạng NS
- 1. Đi từ nhiệm vụ tối đa hóa chức năng mục tiêu (2.3.1) đến vấn đề giảm thiểuđầy đủ lấy tất cả các 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 đề kết quả ở mức tối đa. Sau khi tìm được cực đại, giá trị của hàm mục tiêu phải lấy ngược dấu. Giải pháp tối ưu sẽ được giữ nguyên.
- 2. Đi từ ràng buộc như "nhỏ hơn hoặc bằng" thành bình đẳng nó cần với một dấu cộng:
3. Đi từ ràng buộc "lớn hơn hoặc bằng" thành bình đẳng nó cần giới thiệu một biến bổ sung không âm với một dấu trừ:
Trong trường hợp này, mỗi bất đẳng thức đưa ra (n +/) - Tôi là một biến bổ sung.
- 4. Tất cả số bằng với các số hạng tự do âm được chia cho-1 để điều kiện (2.3.4) được thỏa mãn.
- 5. Nếu đối với một số biến Xj điều kiện không âm không được áp đặt, sau đó thực hiện sự thay đổi của các biến Xj = x ”.- NS" x "j> 0, x "> 0. Trong bài toán đã biến đổi tất cả các biến không âm.
Có một khẳng định rằng bất kỳ LPP nào cũng có thể được rút gọn về dạng chuẩn.
Ví dụ 2.3.1. Chúng ta hãy chuyển bài toán cho trong ví dụ 2.2.2 thành dạng chính tắc. Hàm mục tiêu và hệ thống các hạn chế như sau:
Chúng tôi đưa vào bất đẳng thức đầu tiên một biến bổ sung jc 3> 0 với dấu cộng, vào bất đẳng thức thứ hai x 4> 0 với một dấu trừ và ở phần ba x 5> 0 cũng với một dấu cộng. Kết quả là, chúng tôi có được một hệ thống các ràng buộc cho bài toán ở dạng chuẩn:
Theo các ràng buộc 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 của việc 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)[17 J.
Nhà máy sử dụng một lượng nhất định ba loại tài nguyên: lao động (80 ngày công), nguyên liệu thô (480 kg) và thiết bị (130 giờ máy công cụ). 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 mỗi nguồn lực cần thiết để sản xuất một tấm thảm của mỗi loại và về thu nhập mà doanh nghiệp nhận được từ một đơn vị của từng loại hàng hoá, được đưa ra trong bảng. 2.3.1.
Cần phải tìm ra một kế hoạch sản xuất như vậy, trong đó tổng chi phí của nó sẽ được tối đa hóa.
Mô hình kinh tế và toán học của vấn đề Biến: x x, x 2, x 3, x 4 - số lượng thảm của từng loại. Hàm mục tiêu -đây là tổng chi phí sản xuất được tối đa hóa:
Giới hạn tài nguyên:
Hãy để chúng tôi giảm vấn đề xuống dạng chuẩn bằng cách giới thiệu các biến bổ sung x 5, x 6 và x 7:
Hơn nữa, nó sẽ được 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 hoá tổng chi phí sản xuất cần sản xuất 30 tấm thảm loại hai và 10 tấm thảm loại ba. Thay thế các giá trị tối ưu của vectơ NS trong các hạn chế của KZLP:
Chúng tôi nhận thấy rằng tài nguyên "lao động" và "thiết bị" được sử dụng đầy đủ, tài nguyên "nguyên liệu thô" rất dồi dào:
Trong trường hợp này x trong cho thấy còn 200 kg nguyên liệu.
Do đó, các biến chính x v x 2, x 3, x l nghĩa là số lượng thảm của mỗi loại và các biến bổ sung x 5, x 6 của chúng 7 - số lượng tài nguyên không được sử dụng.
Bài giải. Kế hoạch sản xuất tối ưu X * = (0; 30;
10; 0).
Kế hoạch, hoặc quyết định có thể chấp nhận được, KZLP được gọi là vectơ X =(jc p NS 2 ,..., x n) thỏa mãn các điều kiện (2.3.2) - (2.3.4).
Nếu tất cả các thành phần của giải pháp cơ bản cho hệ thống ràng buộc của KZLP là không âm, thì một giải pháp như vậy được gọi là quyết định tham khảo hoặc kế hoạch cơ bản. Số lượng các thành phần tích cực của kế hoạch tham chiếu không được vượt quá NS.
Kế hoạch cơ bản được gọi là không thoái hóa, nếu nó chứa NS các thành phần tích cực, nếu không nó được gọi là thoái hóa.
Kế hoạch tối ưu hoặc giải pháp tối ưu LPP được gọi là phương án cung cấp 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 LPP (nếu chúng tồn tại) là khối đa diện lồi.Đối với mỗi điểm góc (cực trị) của đa giác của các nghiệm ở đó tương ứng với kế hoạch cơ sở(nghiệm cơ bản không âm của hệ phương trình KZLP). Mỗi đường cơ sở được xác định bởi hệ thống NS vectơ độc lập tuyến tính chứa trong hệ thống này từ NS vectơ Д, Д, ..., Một p. Nếu có một thiết kế tối ưu, thì tại đó có một điểm góc của đa giác nghiệm mà tại đó hàm tuyến tính đạt giá trị lớn nhất (nhỏ nhất) của nó.
Để tìm ra phương án tối ưu, chỉ cần điều tra các phương án hỗ trợ là đủ. Giới hạn trên về số lượng kế hoạch tham chiếu có trong một nhiệm vụ được xác định bởi số lượng kết hợp C t p (xem đoạn 1.4).
Ví dụ 2.3.3. Có được giải pháp cho vấn đề sử dụng tối ưu các nguồn lực hạn chế (giải LP P):
Dung dịch. Hãy để chúng tôi giảm vấn đề xuống dạng chuẩn bằng cách giới thiệu các biến bổ sung x 3, x 4 và x 5:
Hãy để chúng tôi tìm tất cả các phương án hỗ trợ của hệ thống các ràng buộc của KZLP đã cho (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 Phần 1.4), chúng tôi viết ra 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 Chân các giải pháp |
Nền tảng |
Kế hoạch |
|||||
Trong số mười giải pháp cơ bản, có năm giải pháp cơ bản:
Các kế hoạch tham khảo được chỉ ra trong Hình. 1 tương ứng với các điểm có góc sau và giá trị của CF tại chúng:
Lúa gạo. 2.3.1.
Theo lý thuyết LP giải pháp tối ưu được chứa 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 V trên mặt phẳng tham chiếu X 5 = (70; 80; 0; 60; 0).
Bài giải. Kế hoạch nhiệm vụ tối ưu: x (= 70, x 2 = 80, giá trị của hàm mục tiêu f (x v x 2) = 2300.
hình thức kinh điển, nếu nó được yêu cầu để cực đại hóa hàm mục tiêu, tất cả các ràng buộc của hệ 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 lập trình tuyến tính được đưa ra trong hình dạng đối xứng, nếu yêu cầu tối đa hóa hàm mục tiêu, tất cả các ràng buộc của hệ là bất đẳng thức "" (hoặc để cực tiểu hàm mục tiêu, tất cả các ràng buộc của hệ là bất đẳng thức "") và điều kiện không âm được áp đặt cho tất cả các biến.
Bộ số được gọi là quyết định chấp nhận (kế hoạch) nếu nó thỏa mãn hệ thống hạn chế của LPP.
Tập hợp tất cả các giải pháp khả thi được gọi là miền các giải pháp khả thi(ODR).
Giải pháp khả thi mà giá trị lớn nhất (nhỏ nhất) của hàm đạt được được gọi là kế hoạch tối ưu của LPP.
Các thuật ngữ "kế hoạch" và "kế hoạch tối ưu" phát sinh từ các ứng dụng kinh tế.
Cả ba dạng ký hiệu LPP đều tương đương với nghĩa là có các thuật toán cho việc chuyển đổi từ dạng này sang dạng khác. Do đó, nếu có một cách giải quyết vấn đề ở một trong các dạng thì bạn luôn có thể xác định được phương án tối ưu cho một 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 đồ thị và ở dạng chính tắc - bằng phương pháp đơn giản.
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. Quá trình chuyển đổi được thực hiện bằng cách thêm một biến bổ sung 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 thêm 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 bằng 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 cực tiểu hàm Z được thay bằng bài toán cực đại hàm (–Z) và sử dụng min Z = –max (–Z).
Hình nón đối xứng.Để thực hiện một quá trình chuyển đổi như vậy, người ta tìm ra một 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. Hơn nữa, bằng cách sử dụng tính không phủ định của các biến cơ bản, người ta có thể loại trừ chúng khỏi vấ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à một 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 thấy từ nghiệm tổng quát của hệ phương trình ban đầu.
Tổng quát chính tắc. Mỗi biến chưa tuân theo đ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 thành phương trình bằng cách đưa một biến số dư vào bên trái của mỗi bất đẳng thức theo cách tương tự như được mô tả trong quá trình chuyển từ dạng đối xứng sang dạng chính tắc. Bài toán cực tiểu hàm Z được thay thế bằng bài toán cực đại hàm (–Z) giống như cách mô tả khi chuyển từ đối xứng sang dạng chính tắc.
Một phương pháp đồ họa để giải một bài toán lập trình tuyến tính
Tập hợp các điểm được gọi là lồi lõm nếu đối với hai điểm bất kỳ của tập hợp, nó chứa một đoạn kết nối chúng.
ví dụ 1
Tập hợp các điểm sau đây trong mặt phẳng là lồi:
Tập hợp các điểm sau đây trong 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à tập lồi.
Định lý 2 Cho có hai điểm tùy ý và trong không gian NS n... Sau đó, đối với bất kỳ điểm nào của đoạn [ PQ] phải được thực thi: ở đâu.
Siêu phẳng trong không gian NS n là tập hợp các điểm thỏa mãn đẳng thức. 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 của 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 hợp lồi.
Hậu quả Giao của một số nửa không gian bất kỳ là một tập lồi.
Khối đa diện giao của một hoặc nhiều nửa không gian được gọi. Một đa diện trong trường hợp hai chiều được gọi là một đa giác.
Ví dụ 2
Các tập hợp sau đây là các đa giác.
Bộ hạn chế
Bộ không giới hạn
Điểm duy nhất
Bộ trống
Một điểm thuộc tập lồi được gọi là góc cạnh nếu nó không nằm bên trong bất kỳ đoạn nào nối hai điểm khác từ 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 trong số chúng). Các điểm ở góc của một đường tròn là các điểm của đường tròn giới hạn nó (có vô số chúng).
Điểm ở góc của một hình đa diện được gọi là đỉnh cao.
Hãy xem xét một LPP được cho dưới dạng đối xứng.
Định lý 4 Thiết kế tối ưu của LPP tương ứng với đỉnh của đa hình nghiệm được xác định bởi hệ thống các ràng buộc của nó.
Bài toán lập trình tuyến tính dạng ax = b trong đó a là ma trận các hệ số, b là vectơ ràng buộc.
Thí dụ:
Trong mỗi bài toán LP, giá trị của các biến được tìm kiếm với điều kiện:
- những giá trị này thỏa mãn một hệ phương trình hoặc bất phương trình tuyến tính nào đó;
- tại các giá trị này, hàm mục tiêu sẽ chuyển sang giá trị nhỏ nhất hoặc tối đa.
Hướng dẫn. Chọn số lượng biến và số dòng (số lượng ràng buộc). Giải pháp kết quả được lưu trong tệp Word.
Một trong những phương pháp LP phổ biến là phương pháp simplex, 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ệ chỉ 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 phủ định của các biến) và hàm mục tiêu phải là cực tiểu.
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ệ thống các ràng buộc (1) và một hàm mục tiêu (2).
Tuy nhiên, trong hầu hết các bài toán kinh tế, thông thường, hệ thống các hạn chế ban đầu không chỉ bao gồm các phương trình, mà còn cả các bất đẳng thức.
Tuyên bố. Bất kỳ vấn đề LP chung nào đều có thể được rút gọn thành dạng chuẩn.
Việc giảm vấn đề LP tổng quát về dạng chính tắc đạt được bằng cách đưa vào các biến mới (chúng được gọi là bổ sung).
Hệ thống các ràng buộc (3) của bài toán này bao gồm bốn bất phương trình. 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, bạn có thể chuyển đến hệ thống các hạn chế: 
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 hoạt động không được sử dụng (thời gian chết máy tôi-loại thứ).
Ví dụ, nếu máy loại thứ nhất làm việc trong 18 giờ thì x + y = 18, do đó, y 1 = 0. Nhưng chúng tôi thừa nhận khả năng sử dụng không đầy đủ thời gian hoạt động của máy thứ nhất. NS + y<18. В этом случае y 1 trở thành số dương và có thể được coi là giới hạn thời gian không sử dụng. Ví dụ, biết giải pháp cho vấn đề này từ đoạn 3.3.2, NS = 12, y= 6, chúng ta có thể kết luận từ hệ thống các ràng buộc (3.9) rằng y 1 = y 2 = y 3 = 0 và y 4 = 12 - 6 = 6. Tức là các máy thuộc loại thứ nhất, thứ hai, thứ ba sử dụng hết thời gian làm việc của chúng. Nhưng ô tô thứ tư mới chở được một nửa, 6 giờ, và không tải ở phương án tối ưu đã cho. Có lẽ, sau khi kết luận như vậy, người đứng đầu doanh nghiệp sẽ muốn tải nó sang làm việc khác, cho thuê trong 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 kiểu bất đẳng thức nào cho một phương trình.
Xem xét vấn đề hỗn hợp. Hệ thống các hạn chế như sau: 
Các bất đẳng thức được chuyển sang "nhiều hơn", do đó, khi đưa vào các biến bổ sung y 1, y 2, y 3 ≥ 0, chúng phải được trừ ở bên trái để cân bằng với bên phải. Chúng tôi nhận được hệ thống các hạn chế ở dạng chuẩn:
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ẽ có nghĩa là lượng chất A dư trong hỗn hợp, y 2 - lượng chất dư V trong hỗn hợp, y 3 - thặng dư VỚI trong hỗn hợp.
Bài toán 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 giá trị nhỏ nhất của hàm - NS theo quan điểm rõ ràng của khẳng định max F = –min (- F). Nhìn vào bức tranh: nếu một lúc nào đó NS= NS 0 chức năng y= NS(NS) đạt cực đại, khi đó hàm y= –NS(NS), đối xứng với nó qua trục CON BÒ ĐỰC, tại cùng một điểm NS 0 đạt mức tối thiểu và NS tối đa = - (- NS tối thiểu) lúc NS = NS 0 .
Đầu ra.Để biểu diễn vấn đề LP ở dạng chuẩn, cần:
- các bất đẳng thức đưa vào hệ thống các ràng buộc của bài toán, biến đổi thành phương trình bằng cách đưa thêm các biến số;
- nếu hàm mục tiêu NS→ max (tối đa), nó được thay thế bằng một hàm - NS→ min (được tối thiểu hóa).
