Các giai đoạn chính của việc viết một mô hình lập trình tuyến tính. Giải bài toán quy hoạch tuyến tính bằng phương pháp đồ họa
Lập trình tuyến tính
Lập trình tuyến tính- một môn toán dành cho lý thuyết và phương pháp giải các bài toán cực trị trên các tập hợp không gian vectơ có chiều được xác định bởi các hệ thống Các phương trình tuyến tính và sự bất bình đẳng.
Quy hoạch tuyến tính là một trường hợp đặc biệt của quy hoạch lồi, và quy hoạch lồi cũng là trường hợp đặc biệt của quy hoạch toán học. Đồng thời, nó là cơ sở của một số phương pháp giải các bài toán quy hoạch số nguyên và phi tuyến. Một trong những khái quát lập trình tuyến tính là quy hoạch tuyến tính phân số.
Nhiều tính chất của các bài toán quy hoạch tuyến tính cũng có thể được hiểu là các tính chất của khối đa diện và do đó được xây dựng và chứng minh về mặt hình học.
Câu chuyện
Phương pháp điểm trong được đề cập lần đầu tiên bởi I. I. Dikin vào năm 1967.
Nhiệm vụ
Bài toán quy hoạch tuyến tính chính (chuẩn) được gọi là bài toán tìm cực tiểu của hàm mục tiêu tuyến tính ( hình tuyến tính) có dạng:
trong những điều kiện
, .Bài toán quy hoạch tuyến tính sẽ có chế độ xem chuẩn , nếu trong bài toán chính thay vì hệ bất đẳng thức thứ nhất có hệ phương trình:
,Vấn đề chính có thể được giảm xuống thành vấn đề chính tắc bằng cách đưa vào các biến bổ sung.
Các bài toán quy hoạch tuyến tính ở dạng tổng quát nhất (bài toán có ràng buộc hỗn hợp: đẳng thức và bất đẳng thức, sự có mặt của các biến không có ràng buộc) có thể được quy về dạng tương đương (có cùng tập nghiệm) bằng cách thay thế các biến và thay thế đẳng thức bằng một cặp sự bất bình đẳng.
Dễ dàng nhận thấy bài toán tìm cực đại có thể được thay thế bằng nhiệm vụ tìm cực tiểu bằng cách lấy các hệ số trái dấu.
Vấn đề mẫu
Kết hợp tối đa
Xét bài toán so khớp tối đa trong đồ thị hai bên: có một số chàng trai và cô gái, và đối với mỗi chàng trai và cô gái, người ta biết liệu họ có hấp dẫn nhau hay không. Chúng ta cần kết hôn với số lượng cặp đôi tối đa với sự thông cảm lẫn nhau.
Hãy để chúng tôi giới thiệu các biến tương ứng với cặp -boy và -girl và thỏa mãn các hạn chế:
với hàm mục tiêu. Có thể chỉ ra rằng trong số các nghiệm tối ưu cho bài toán này có một nghiệm nguyên. Các biến bằng 1 sẽ tương ứng với các cặp đôi nên kết hôn.
Lưu lượng cực đại
Giả sử có một đồ thị (với các cạnh được định hướng), trong đó mỗi cạnh của nó thông lượng. Và hai đỉnh được đưa ra: cống và nguồn. Cần chỉ rõ cho mỗi cạnh bao nhiêu chất lỏng sẽ chảy qua nó (không quá dung tích của nó) để tối đa hóa tổng lưu lượng từ nguồn đến cống (chất lỏng không thể xuất hiện hoặc biến mất ở tất cả các đỉnh ngoại trừ cống và nguồn).
Chúng ta hãy lấy lượng chất lỏng chảy qua sườn làm biến số. Sau đó
,công suất của cạnh đó ở đâu. Những bất bình đẳng này phải được bổ sung bằng sự bằng nhau về lượng chất lỏng chảy vào và chảy ra ở mỗi đỉnh, ngoại trừ cống và nguồn. Là một chức năng, điều tự nhiên là lấy sự khác biệt giữa lượng chất lỏng chảy ra và chảy vào tại nguồn.
Một cách khái quát hóa của vấn đề trước đó là dòng chảy tối đa với chi phí tối thiểu. Trong bài toán này, chi phí cho mỗi cạnh được cho trước và bạn cần chọn luồng có chi phí tối thiểu trong số các luồng tối đa. Vấn đề này dẫn đến hai vấn đề quy hoạch tuyến tính: đầu tiên bạn cần giải vấn đề về luồng cực đại, sau đó thêm vào vấn đề này ràng buộc, giá trị của luồng tối đa ở đâu và giải quyết vấn đề với tính năng mới- chi phí dòng chảy.
Những vấn đề này có thể được giải quyết nhanh hơn thuật toán chung giải các bài toán quy hoạch tuyến tính do cấu trúc đặc biệt của phương trình và bất đẳng thức.
Nhiệm vụ vận chuyển
Có một số hàng hóa đồng nhất nhất định cần chuyển từ kho tới nhà máy. Đối với mỗi nhà kho, người ta biết được số lượng hàng hóa chứa trong đó và nhu cầu về hàng hóa của mỗi nhà máy cũng được biết. Chi phí vận chuyển tỷ lệ thuận với khoảng cách từ kho đến nhà máy (tất cả khoảng cách từ kho đến nhà máy đều đã biết). Cần phải soạn nhiều nhất gói giá rẻ vận tải.
Các biến quyết định trong trong trường hợp này là số lượng hàng hóa được vận chuyển từ kho thứ đến nhà máy thứ. Họ thỏa mãn các hạn chế:
Hàm mục tiêu có dạng: , phải được tối thiểu hóa.
Zero-sum trò chơi
Có một ma trận kích thước. Người chơi đầu tiên chọn một số từ 1 đến , người thứ hai - từ 1 đến . Sau đó, họ kiểm tra các con số và người chơi đầu tiên nhận được điểm, còn người thứ hai nhận được điểm (số do người chơi đầu tiên chọn sẽ nhận được số thứ hai). Chúng ta cần tìm ra chiến lược tối ưu cho người chơi đầu tiên.
Giả sử trong một chiến lược tối ưu chẳng hạn, người chơi đầu tiên phải chọn một số có xác suất . Khi đó chiến lược tối ưu là giải pháp cho bài toán quy hoạch tuyến tính sau:
, , (),trong đó hàm cần được tối đa hóa. Giá trị trong giải pháp tối ưu sẽ là kỳ vọng toán học về phần thưởng của người chơi đầu tiên trong trường hợp xấu nhất.
Thuật toán giải
Nổi tiếng nhất và được sử dụng rộng rãi trong thực tế để giải quyết nhiệm vụ chung Lập trình tuyến tính (LP) là một phương pháp đơn giản. Mặc dù thực tế rằng phương pháp đơn hình là một thuật toán khá hiệu quả đã cho thấy kết quả tốt khi quyết định bài toán ứng dụng LP, nó là một thuật toán có độ phức tạp theo cấp số nhân. Lý do cho điều này là tính chất tổ hợp của phương pháp đơn hình, trong đó liệt kê tuần tự các đỉnh của khối đa diện của các lời giải khả thi khi tìm kiếm lời giải tối ưu.
Thuật toán đa thức đầu tiên, phương pháp ellipsoid, được đề xuất vào năm 1979 bởi nhà toán học Liên Xô L. Khachiyan, nhờ đó giải được bài toán trong một khoảng thời gian dài vẫn chưa được giải quyết. Phương pháp ellipsoid có bản chất hoàn toàn khác, không tổ hợp so với phương pháp đơn hình. Tuy nhiên, từ quan điểm tính toán, phương pháp này hóa ra không hứa hẹn. Tuy nhiên, chính sự phức tạp đa thức của các bài toán đã dẫn đến việc tạo ra cả một lớp thuật toán hiệu quả LP - phương pháp điểm bên trong, đầu tiên trong số đó là thuật toán của N. Karmarkar được đề xuất vào năm 1984. Các thuật toán loại này sử dụng cách diễn giải liên tục bài toán LP, khi thay vì liệt kê các đỉnh của khối đa diện của lời giải cho bài toán LP, việc tìm kiếm được thực hiện dọc theo các quỹ đạo trong không gian. biến vấn đề, không đi qua các đỉnh của khối đa diện. Phương pháp điểm bên trong, không giống như phương pháp đơn hình, bỏ qua các điểm từ bên trong vùng giá trị chấp nhận được, sử dụng các phương pháp lập trình phi tuyến rào cản log được phát triển vào những năm 1960 bởi Fiacco và McCormick.
Xem thêm
- Phương pháp đồ họa để giải bài toán quy hoạch tuyến tính
Ghi chú
Văn học
- Thomas H. Corman và cộng sự. Chương 29. Lập trình tuyến tính // Thuật toán: xây dựng và phân tích = GIỚI THIỆU GIẢI PHÁP. - tái bản lần thứ 2. - M.: “Williams”, 2006. - P. 1296. - ISBN 5-8459-0857-4
- Akulich I.L. Chương 1. Bài toán quy hoạch tuyến tính, Chương 2. Bài toán quy hoạch tuyến tính đặc biệt // Lập trình toán học trong các ví dụ và bài toán. - M.: trường sau đại học, 1986. - 319 tr. - ISBN 5-06-002663-9
- Karmanov V. G. Lập trình toán học. - Tái bản lần thứ 3. - M.: Nauka, 1986. - 288 tr.
- Danzig George Bernard "Ký ức về sự khởi đầu của lập trình tuyến tính"
Liên kết
- - Gói tối ưu hóa miễn phí được thiết kế để giải quyết các vấn đề lập trình tuyến tính, số nguyên và mục tiêu.
- Vershik A. M. “Giới thiệu về L. V. Kantorovich và quy hoạch tuyến tính”
- Bolshakova I.V., Kuralenko M.V. “Lập trình tuyến tính. Cẩm nang giáo dục và phương pháp cho bài kiểm tra."
- Barsov A. S. “Lập trình tuyến tính là gì”, Các bài giảng phổ biến về toán học, Gostekhizdat, 1959.
- M. N. Vyalyi Bất đẳng thức tuyến tính và tổ hợp. - MCNMO, 2003.
Quỹ Wikimedia. 2010.
- Muối, Felix
- Glagow, Martina
Xem “Lập trình tuyến tính” là gì trong các từ điển khác:
lập trình tuyến tính- - lập trình tuyến tính Một lĩnh vực lập trình toán học dành cho lý thuyết và phương pháp giải các bài toán cực trị được đặc trưng bởi sự phụ thuộc tuyến tính giữa… … Hướng dẫn dịch thuật kỹ thuật
Lập trình tuyến tính
Lập trình tuyến tính- một lĩnh vực lập trình toán học dành cho lý thuyết và phương pháp giải các bài toán cực trị được đặc trưng bởi mối quan hệ tuyến tính giữa các biến. Chớm ban đầu nhìn chung vấn đề L.p. có thể được viết như thế này Được tặng… … Từ điển kinh tế và toán học
Giải pháp xảy ra trong ba giai đoạn:
- Chuyển sang KZLP. Bất kỳ LLP nào có dạng ax ≤ b , ax ≥ b , ax = b (F(X) → extr) rút gọn về dạng ax = b , F(X) → max ;
- Chuyển sang SZLP. Một CLLP có dạng ax = b rút gọn về dạng ax ≤ b , F(X) → max ;
- Giải bằng phương pháp đơn hình;
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.
Chuyển từ bài toán cực tiểu hóa hàm mục tiêu sang bài toán cực đại hóa
Bài toán cực tiểu hoá hàm mục tiêu F(X) có thể dễ dàng rút gọn thành bài toán cực đại hoá hàm F*(X) dưới cùng các ràng buộc bằng cách đưa ra hàm: F*(X) = -F(X) . Cả hai bài toán đều có cùng nghiệm X* và đồng thời min(F(X)) = -max(F*(X)) .Hãy minh họa thực tế này bằng đồ họa:
| F(x) → phút |
F(x) → tối đa  |
Gói cơ bản– một kế hoạch được xác định thông qua các biến cơ bản miễn phí.
Gói cơ bản– kế hoạch tham khảo không có biến cơ bản.
Phương án tối ưu– một kế hoạch cơ bản đáp ứng chức năng tối ưu bàn thắng (FC).
Phần tử dẫn đầu (giải quyết) là hệ số của ẩn số tự do, trở thành hệ số cơ bản và bản thân hệ số này được chuyển thành đơn vị.
Hướng dẫn– dòng của phần tử dẫn đầu, trong đó ẩn số cơ bản được định vị với hệ số đơn vị, bị loại trừ trong quá trình chuyển đổi (dòng có hệ số giới hạn tối thiểu, xem bên dưới).
Cột hướng dẫn– cột của phần tử dẫn đầu, ẩn số tự do được chuyển thành phần tử cơ bản (cột có lợi ích tối đa, xem bên dưới).
Các biến x 1, ..., x m chỉ có hệ số đơn vị trong một phương trình của hệ, các phương trình còn lại có hệ số bằng 0 được gọi là nền tảng hoặc sự phụ thuộc. Trong hệ thống chính tắc, mỗi phương trình tương ứng với chính xác một biến cơ bản. Việc chuyển đổi được thực hiện bằng phương pháp Gauss-Jordan. Ý tưởng chính của phương pháp này là rút gọn hệ m phương trình với n ẩn số thành hình thức kinh điển sử dụng các phép toán cơ bản trên chuỗi.
Nghỉ ngơi biến n-m(x m +1 ,…, x n) được gọi là không cơ bản hoặc biến độc lập.
Giải pháp cơ bản gọi điện giải pháp cơ bản được chấp nhận, nếu giá trị của các biến cơ bản có trong nó x j ≥0, tương đương với điều kiện không âm b j ≥0.
Có thể chấp nhận được giải pháp cơ bản là điểm góc tập S được chấp nhận của bài toán quy hoạch tuyến tính và đôi khi được gọi là kế hoạch tham khảo.
Nếu trong số các số không âm b j có bằng 0, thì nghiệm cơ bản chấp nhận được được gọi là thoái hóa(điểm góc suy biến) và bài toán quy hoạch tuyến tính tương ứng được gọi là thoái hóa.
Ví dụ số 1. Giảm bài toán quy hoạch tuyến tính thành ZLP tiêu chuẩn.
F(X) = x 1 + 2x 2 - 2x 3 → phút với giới hạn:
4x1 + 3x2 - x 3 10
- 2x2 + 5x3 ≥3
x 1 + 2x 3 = 9
Để đưa PAP đến hình thức kinh điển cần thiết:
1. Đổi dấu của hàm mục tiêu. Chúng ta hãy rút gọn bài toán F(X) → min thành bài toán F(X) → max. Để làm điều này, hãy nhân F(X) với (-1). Trong bất đẳng thức thứ nhất về ý nghĩa (≤), chúng tôi đưa vào biến cơ bản x 4 ; trong bất đẳng thức ý nghĩa thứ hai ( ≥), ta đưa vào biến cơ bản x 5 có dấu trừ.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x1 + 0x2 + 2x3 + 0x4 + 0x5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Chuyển sang SZLP.
Ma trận mở rộng của hệ ràng buộc đẳng thức cho bài toán này:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
Chúng ta hãy rút gọn hệ thống về ma trận nhận dạng bằng phương pháp biến đổi Jordan.
1. Bạn có thể chọn x 4 làm biến cơ sở.
2. Chúng ta chọn x 2 làm biến cơ sở.
Phần tử độ phân giải RE=-2. Dòng tương ứng với biến x 2 thu được bằng cách chia tất cả các phần tử của dòng x 2 cho phần tử phân giải RE = -2. Thay cho phần tử phân giải, chúng ta nhận được 1. Trong các ô còn lại của cột x 2, chúng ta viết các số 0. Tất cả các phần tử khác được xác định theo quy tắc hình chữ nhật. Hãy trình bày cách tính của từng phần tử dưới dạng bảng:
| 4-(0 3):-2 | 3-(-2 3):-2 | -1-(5 3):-2 | 1-(0 3):-2 | 0-(-1 3):-2 | 10-(3 3):-2 |
| 0: -2 | -2: -2 | 5: -2 | 0: -2 | -1: -2 | 3: -2 |
| 1-(0 0):-2 | 0-(-2 0):-2 | 2-(5 0):-2 | 0-(0 0):-2 | 0-(-1 0):-2 | 9-(3 0):-2 |
Chúng tôi nhận được một ma trận mới:
| 4 | 0 | 6 1 / 2 | 1 | -1 1 / 2 | 14 1 / 2 |
| 0 | 1 | -2 1 / 2 | 0 | 1 / 2 | -1 1 / 2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
3. Chúng tôi chọn x 3 làm biến cơ sở.
Phần tử độ phân giải RE=2. Dòng tương ứng với biến x 3 có được bằng cách chia tất cả các phần tử của dòng x 3 cho phần tử phân giải RE=2. Thay cho phần tử phân giải, chúng ta nhận được 1. Trong các ô còn lại của cột x 3, chúng ta viết số không. Tất cả các phần tử khác được xác định theo quy tắc hình chữ nhật. Hãy trình bày cách tính của từng phần tử dưới dạng bảng:
| 4-(1 6 1 / 2):2 | 0-(0 6 1 / 2):2 | 6 1 / 2 -(2 6 1 / 2):2 | 1-(0 6 1 / 2):2 | -1 1 / 2 -(0 6 1 / 2):2 | 14 1 / 2 -(9 6 1 / 2):2 |
| 0-(1 -2 1 / 2):2 | 1-(0 -2 1 / 2):2 | -2 1 / 2 -(2 -2 1 / 2):2 | 0-(0 -2 1 / 2):2 | 1 / 2 -(0 -2 1 / 2):2 | -1 1 / 2 -(9 -2 1 / 2):2 |
| 1: 2 | 0: 2 | 2: 2 | 0: 2 | 0: 2 | 9: 2 |
Chúng tôi nhận được một ma trận mới:
| 3 / 4 | 0 | 0 | 1 | -1 1 / 2 | -14 3 / 4 |
| 1 1 / 4 | 1 | 0 | 0 | 1 / 2 | 9 3 / 4 |
| 1 / 2 | 0 | 1 | 0 | 0 | 4 1 / 2 |
Do hệ có ma trận đồng nhất nên ta lấy X = (4,2,3) làm biến cơ sở.
Các phương trình tương ứng là:
3/4 x 1 + x 4 - 1 1/2 x 5 = -14 3/4
1 1/4 x 1 + x 2 + 1/2 x 5 = 9 3/4
1/2 x 1 + x 3 = 4 1/2
Hãy biểu thị các biến cơ bản theo phần còn lại:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1/4 x 1 - 1/2 x 5 +9 3/4
x 3 = - 1 / 2 x 1 +4 1 / 2
Hãy thay thế chúng vào hàm mục tiêu:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
hoặc
Hệ bất đẳng thức:
- 3/4 x 1 + 1 1/2 x 5 -14 3/4 ≥ 0
- 1 1/4 x 1 - 1/2 x 5 +9 3/4 ≥ 0
- 1/2 x 1 +4 1/2 ≥ 0
Chúng tôi giảm hệ thống bất bình đẳng để lượt xem tiếp theo:
3/4 x 1 - 1 1/2 x 5 ≤ -14 3/4
1 1/4 x 1 + 1/2 x 5 9 3/4
1/2 x 1 4 1/2
F(X) = 1/2 x 1 + x 5 -10 1/2 → tối đa
Hãy đơn giản hóa hệ thống.
3/4 x 1 - 1 1/2 x 2 ≤ -14 3/4
1 1/4 x 1 + 1/2 x 2 9 3/4
1/2 x 1 4 1/2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → tối đa
Ví dụ số 2. Tìm đầu tiên phương pháp đồ họa, rồi dùng phương pháp đơn hình để giải bài toán
F(X) = x 1 + x 2 - x 3 + x 5 +15 → tối đa (tối thiểu) với các hạn chế:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0
Lập trình tuyến tính nổi lên như một nhánh riêng của toán ứng dụng vào những năm 40 và 50. Thế kỷ XX nhờ công trình của nhà khoa học Liên Xô, người đoạt giải Nobel L.V. Kantorovich. Năm 1939, ông xuất bản tác phẩm “Các phương pháp toán học tổ chức và lập kế hoạch sản xuất”, trong đó ông giải quyết các bài toán kinh tế về tải về tốt nhất máy móc, cắt gọt vật liệu với chi phí thấp nhất, phân phối hàng hóa qua nhiều phương thức vận tải và các phương thức khác, đề xuất phương pháp giải số nhân 8.
L.V. Kantorovich là người đầu tiên hình thành các khái niệm toán học và kinh tế được sử dụng rộng rãi như kế hoạch tối ưu, phân bổ nguồn lực tối ưu, đánh giá được xác định một cách khách quan, chỉ ra nhiều lĩnh vực kinh tế có thể áp dụng chúng.
Khái niệm quy hoạch tuyến tính được đưa ra bởi nhà toán học người Mỹ D. Dantzig, người vào năm 1949 đã đề xuất một thuật toán để giải bài toán quy hoạch tuyến tính, được gọi là “phương pháp đơn giản”.
Lập trình toán học, bao gồm lập trình tuyến tính, hiện là một trong những lĩnh vực nghiên cứu hoạt động. Tùy thuộc vào loại vấn đề đang được giải quyết, nó phân biệt các lĩnh vực như quy hoạch tuyến tính, phi tuyến tính, rời rạc, động, v.v. Thuật ngữ “lập trình” được đưa ra do thực tế là các biến chưa biết trong quá trình giải quyết vấn đề thường xác định chương trình, kế hoạch hoạt động của một đơn vị kinh tế nào đó.
Trong phân tích toán học cổ điển, người ta nghiên cứu công thức tổng quát của bài toán xác định cực trị có điều kiện. Tuy nhiên, trước sự phát triển của sản xuất công nghiệp, giao thông, nông nghiệp và ngành ngân hàng, các kết quả phân tích toán học truyền thống là chưa đủ. Nhu cầu thực tiễn và sự phát triển của công nghệ máy tính đã dẫn đến nhu cầu xác định các giải pháp tối ưu khi phân tích các hệ thống kinh tế phức tạp.
Công cụ chính để giải quyết những vấn đề như vậy là mô hình toán học. Trong trường hợp này, một mô hình đơn giản trước tiên được xây dựng, sau đó nghiên cứu của nó được thực hiện, giúp có thể hiểu được đặc tính tích hợp nào của đối tượng không được sơ đồ hình thức nắm bắt, sau đó, bằng cách làm phức tạp mô hình, tính đầy đủ lớn hơn của nó được đảm bảo sát với thực tế. Trong nhiều trường hợp, phép tính gần đúng đầu tiên với thực tế là một mô hình trong đó tất cả sự phụ thuộc giữa các biến đặc trưng cho trạng thái của đối tượng là tuyến tính. Thực tiễn cho thấy có đủ số lượng các quá trình kinh tế được mô tả khá đầy đủ bằng các mô hình tuyến tính. Do đó, quy hoạch tuyến tính như một công cụ cho phép tìm cực trị có điều kiện trên một tập hợp được xác định bởi các phương trình tuyến tính và bất đẳng thức đóng một vai trò quan trọng trong việc phân tích các quá trình này.
Quy hoạch tuyến tính đã nhận được sự phát triển rộng rãi do người ta đã xác định rằng một số vấn đề lập kế hoạch và kiểm soát có thể được xây dựng dưới dạng các vấn đề quy hoạch tuyến tính, để giải quyết bằng các phương pháp hiệu quả. Theo các chuyên gia, khoảng 80–85% tất cả các bài toán tối ưu hóa được giải quyết trong thực tế đều liên quan đến các bài toán quy hoạch tuyến tính.
Bộ máy toán học được tạo ra kết hợp với các chương trình máy tính thực hiện các phép tính tốn nhiều công sức giúp có thể sử dụng rộng rãi các mô hình quy hoạch tuyến tính trong khoa học và thực tiễn kinh tế.
Định nghĩa 1 9 . Lập trình tuyến tính (LP) là một lĩnh vực lập trình toán học, là một nhánh của toán học nghiên cứu các phương pháp tìm giá trị cực trị (lớn nhất và nhỏ nhất) của hàm tuyến tính của một số hữu hạn các biến, các ẩn số phải tuân theo ràng buộc tuyến tính.
Hàm tuyến tính này được gọi là hàm mục tiêu và các ràng buộc thể hiện mối quan hệ định lượng giữa các biến thể hiện các điều kiện và yêu cầu của bài toán kinh tế và được viết dưới dạng toán học dưới dạng phương trình hoặc bất đẳng thức, được gọi là hệ thống các ràng buộc.
Một loạt các vấn đề về hoạch định các quá trình kinh tế được quy giản thành các bài toán quy hoạch tuyến tính, trong đó nhiệm vụ tìm ra giải pháp (tối ưu) tốt nhất được đặt ra.
Một bài toán quy hoạch tuyến tính tổng quát (GLP) là tìm giá trị cực trị (cực đại hoặc cực tiểu) của hàm tuyến tính, được gọi là mục tiêu 10:
từ N biến x 1 , x 2 , …, X N với các hạn chế chức năng áp đặt:
(3.2)
và các hạn chế trực tiếp (yêu cầu tính không âm của các biến)
, (3.3)
Ở đâu Một ij , b Tôi , c j- cho trước các giá trị không đổi.
Trong hệ thống hạn chế (3.2), các dấu “nhỏ hơn hoặc bằng”, “bằng” và “lớn hơn hoặc bằng” có thể xuất hiện đồng thời.
ZLP ở dạng ngắn gọn hơn có dạng:
,
với những hạn chế:
;
.
Vectơ` X = (x 1 , x 2 , …, X N) có các thành phần thỏa mãn các ràng buộc chức năng và ràng buộc trực tiếp của bài toán được gọi là kế hoạch(hoặc giải pháp chấp nhận được) ZLP.
Tất cả các giải pháp khả thi đều được hình thành lãnh địa vấn đề lập trình tuyến tính, hoặc vùng giải pháp khả thi (ODR). Một giải pháp khả thi mang lại giá trị tối đa hoặc tối thiểu của hàm mục tiêu f(`X), được gọi là phương án tối ưu của bài toán và được ký hiệu f(`X * ), Ở đâu ` X * =(x 1 * , x 2 * , …, X N * ).
Một hình thức ghi PPP khác:
,
Ở đâu f(`X * ) là giá trị lớn nhất (nhỏ nhất) f(VỚI, X), tiếp quản tất cả các giải pháp có trong bộ phương pháp khả thi X .
Định nghĩa 2 11 . Biểu thức toán học của hàm mục tiêu và các ràng buộc của nó được gọi là mô hình toán học của một bài toán kinh tế.
Để biên dịch một mô hình toán học, bạn cần:
1) xác định các biến;
2) tạo hàm mục tiêu dựa trên mục tiêu của vấn đề;
3) viết ra một hệ thống các hạn chế, có tính đến các chỉ số trong báo cáo vấn đề và các mẫu định lượng của chúng.
Chú thích: Bài giảng này đề cập đến một số vấn đề liên quan đến quy hoạch tuyến tính như một trong những nhánh của lập trình toán học; đặc biệt, xây dựng các loại bài toán quy hoạch tuyến tính chính, cho thấy sự khác biệt giữa các bài toán này và các bài toán cổ điển của phân tích toán học; giới thiệu các hình thức khác nhau để ghi lại các nhiệm vụ này, thực hiện việc xây dựng và nghiên cứu cấu trúc của chúng. Câu hỏi giải các bài toán quy hoạch tuyến tính bằng phương pháp đơn hình được khám phá đầy đủ nhất.
1. Khái niệm lập trình toán học
là một môn toán học trong đó các phương pháp được phát triển để tìm các giá trị cực trị của hàm mục tiêu trong tập hợp các giá trị có thể có của nó được xác định bởi các ràng buộc.
Sự hiện diện của các ràng buộc làm cho các bài toán về cơ bản khác với các bài toán phân tích toán học cổ điển về việc tìm các giá trị cực trị của hàm số. Phương pháp phân tích toán học để tìm kiếm cực trị của hàm trong nhiệm vụ lập trình toán học hóa ra là không phù hợp.
Để giải quyết vấn đề lập trình toán học Các phương pháp và lý thuyết đặc biệt đã được phát triển và đang được phát triển. Vì việc giải những bài toán này đòi hỏi phải thực hiện một lượng lớn các phép tính nên khi đánh giá so sánh phương pháp tầm quan trọng lớnđược mang lại cho sự hiệu quả và thuận tiện khi thực hiện chúng trên máy tính.
Nó có thể được coi là một tập hợp các phần độc lập liên quan đến việc nghiên cứu và phát triển các phương pháp để giải quyết một số loại vấn đề nhất định.
Tùy thuộc vào tính chất của hàm mục tiêu và hàm ràng buộc, mọi bài toán lập trình toán họcđược chia thành hai lớp chính:
- các bài toán quy hoạch tuyến tính,
- nhiệm vụ lập trình phi tuyến.
Nếu như hàm mục tiêu và các hàm ràng buộc – hàm tuyến tính, thì bài toán tìm cực trị tương ứng là bài toán quy hoạch tuyến tính. Nếu ít nhất một trong chức năng quy định là phi tuyến thì bài toán tìm cực trị tương ứng là bài toán lập trình phi tuyến.
2. Khái niệm quy hoạch tuyến tính. Các loại bài toán quy hoạch tuyến tính
Lập trình tuyến tính(LP) – một trong những phần đầu tiên và được nghiên cứu kỹ lưỡng nhất lập trình toán học. Chính xác lập trình tuyến tính là phần mà từ đó kỷ luật bắt đầu phát triển" lập trình toán học". Thuật ngữ "lập trình" trong tiêu đề của ngành học không có gì chung với thuật ngữ "lập trình (tức là biên dịch chương trình) cho máy tính" không liên quan gì đến ngành học ". lập trình tuyến tính" nảy sinh ngay cả trước thời điểm máy tính bắt đầu được sử dụng rộng rãi để giải quyết các vấn đề toán học, kỹ thuật, kinh tế và các vấn đề khác.
Thuật ngữ " lập trình tuyến tính" phát sinh do việc dịch từ "lập trình tuyến tính" tiếng Anh không chính xác. Một trong những nghĩa của từ "lập trình" là lập kế hoạch, lập kế hoạch. Do đó, dịch đúng Tiếng Anh "lập trình tuyến tính" sẽ không phải là " lập trình tuyến tính", và "quy hoạch tuyến tính", phản ánh chính xác hơn nội dung của môn học. Tuy nhiên, các thuật ngữ lập trình tuyến tính, lập trình phi tuyến, lập trình toán học vân vân. đã được chấp nhận rộng rãi trong văn học của chúng ta và do đó sẽ được bảo tồn.
Vì thế, lập trình tuyến tính nảy sinh sau Thế chiến thứ hai và bắt đầu phát triển nhanh chóng, thu hút sự chú ý của các nhà toán học, kinh tế học và kỹ sư nhờ khả năng ứng dụng rộng rãi trong thực tế cũng như sự hài hòa về mặt toán học.
Có thể nói rằng lập trình tuyến tính có thể áp dụng để giải các mô hình toán học của các quá trình và hệ thống đó có thể dựa trên giả thuyết về biểu diễn tuyến tính của thế giới thực.
Lập trình tuyến tính dùng trong giải quyết các bài toán kinh tế, trong các nhiệm vụ như quản lý, lập kế hoạch sản xuất; trong vấn đề xác định vị trí tối ưu trang thiết bị trên tàu biển, trong nhà xưởng; trong vấn đề xác định kế hoạch tối ưu vận tải hàng hóa (nhiệm vụ vận tải); trong các vấn đề về phân phối nhân sự tối ưu, v.v.
Bài toán quy hoạch tuyến tính(LP), như đã nói rõ ở trên, bao gồm việc tìm cực tiểu (hoặc cực đại) của hàm tuyến tính dưới các giới hạn tuyến tính.
Hình thức chung bài toán có dạng: tìm theo điều kiện
Cùng với dạng chung, chúng còn được sử dụng rộng rãi kinh điển Và tiêu chuẩn các hình thức. Ở cả dạng chuẩn và chuẩn
Những thứ kia. tất cả các biến trong bất kỳ lời giải khả thi nào của bài toán đều phải lấy giá trị không âm (các biến như vậy thường được gọi là không tiêu cực không giống như cái gọi là miễn phí các biến có phạm vi giá trị không bị hạn chế như vậy). Sự khác biệt giữa các dạng này là trong một trường hợp I 2 = 0 và trong trường hợp kia - I 1 = 0.
Bài toán LP ở dạng chính tắc.
Lập trình tuyến tính là một trong những nhánh quan trọng nhất của toán học, nơi nghiên cứu nền tảng lý thuyết và phương pháp luận để giải quyết một số vấn đề nhất định. Môn toán này được sử dụng rộng rãi trong những năm trước trong các lĩnh vực kinh tế và khu vực kỹ thuật, trong đó vai trò cuối cùng không được trao cho việc lập kế hoạch và sử dụng toán học hệ thống tự động tính toán. Nhánh khoa học này được dành cho việc nghiên cứu tuyến tính mô hình tối ưu hóa. Tức là, lập trình tuyến tính là về các con số. Đầu tiên thuật ngữ nàyđược T. Koopmans đề xuất vào năm 1951. Phương án tối ưu cho từng chương trình tuyến tính phải được tự động liên kết với mức giá tối ưu, tức là với những đánh giá được xác định một cách khách quan.
Lập trình tuyến tính: phương pháp
Sử dụng kỹ thuật này, có thể giải quyết được một số lượng đáng kể các vấn đề cực đoan liên quan đến kinh tế. Trong trường hợp này, thông thường cần phải tìm các giá trị cực trị của một số hàm có giá trị thay đổi. Lời giải của hệ phương trình biến đổi và bất đẳng thức được thể hiện dưới dạng cơ sở của quy hoạch tuyến tính. Loại này lập trình được đặc trưng bởi một công thức toán học của các biến, trình tự và theo một thứ tự nhất định tính toán cũng như phân tích logic. Áp dụng này:
Nếu có sự chắc chắn về mặt toán học và giới hạn về mặt định lượng giữa các yếu tố được nghiên cứu và số lượng thay đổi;
Nếu có sự thay thế lẫn nhau của các yếu tố do trình tự tính toán;
Nếu logic toán học được kết hợp với sự hiểu biết về bản chất của hiện tượng đang được nghiên cứu.
Lập trình tuyến tính trong việc thúc đẩy tính toán hiệu suất tối ưu toàn bộ máy móc, dây chuyền, đơn vị sản xuất cũng như giải quyết vấn đề sử dụng hợp lý nguyên vật liệu sẵn có.
TRONG nông nghiệp với sự giúp đỡ phương pháp này Chi phí tối thiểu của khẩu phần ăn được xác định có tính đến lượng thức ăn sẵn có. Điều này có tính đến loại và hàm lượng của một số chất có lợi trong đó.
Trong xưởng đúc kỹ thuật này cho phép bạn tìm ra giải pháp vấn đề vận chuyển và các vấn đề về hỗn hợp là một phần của điện tích luyện kim. Bản chất của bài toán vận tải trong trường hợp này hàm ý sự gắn kết tối ưu của doanh nghiệp tiêu dùng với doanh nghiệp sản xuất.
Lập trình tuyến tính: vấn đề
Tính năng đặc biệt mọi người nhiệm vụ kinh tế, được giải bằng kỹ thuật quy hoạch tuyến tính, là sự lựa chọn một số lựa chọn nhất định giải pháp cũng như các điều kiện hạn chế. Bằng cách giải quyết vấn đề này có thể tìm thấy giải pháp tối ưu của tất cả lựa chọn thay thế.
Giá trị quan trọng của việc sử dụng kỹ thuật quy hoạch tuyến tính trong kinh tế là việc lựa chọn phương pháp phương án tối ưu từ số lượng lớn tất cả các lựa chọn được coi là có thể chấp nhận được. Những vấn đề như vậy hầu như không thể giải quyết bằng những cách khác, vì chỉ có chúng mới cho phép người ta tìm ra mức độ hợp lý của ứng dụng. Từ nhà sản xuất.
Lập trình tuyến tính trong Excel
Trong quá trình giải các bài toán như vậy, trước tiên cần phải tạo ra một mô hình trong đó hàm ý việc xây dựng các điều kiện bằng ngôn ngữ toán học. Sau giai đoạn này, giải pháp có thể được tìm thấy bằng phương pháp đồ họa. Với mục đích này trong chương trình excel tồn tại chức năng đặc biệt"Tìm một giải pháp."
Như đã rõ ở trên, quy hoạch tuyến tính có phạm vi ứng dụng rất rộng.
