Ai đã tạo ra phương pháp quy hoạch tuyến tính. 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 là một trong những nhánh quan trọng nhất của toán học, nghiên cứu các lý thuyết và phương pháp 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 gần đây trong nhiều lĩnh vực kinh tế, công nghệ và quân sự, trong đó việc lập kế hoạch toán học và sử dụng máy tính kỹ thuật số tự động đóng một vai trò quan trọng trong sự phát triển của chúng. Nhánh khoa học này nghiên cứu các mô hình tối ưu hóa tuyến tính. Nói cách khác, lập trình tuyến tính là về các con số

Thuật ngữ “quy hoạch tuyến tính” lần đầu tiên được đề xuất bởi nhà kinh tế học người Mỹ T. Koopmans vào năm 1951. Vào năm 1975. Nhà toán học người Nga L.V. Kantorovich và T. Koopmans đã được trao giải Nobel về khoa học kinh tế vì những đóng góp của họ cho lý thuyết phân bổ nguồn lực tối ưu. T. Koopmans đề cao các phương pháp quy hoạch tuyến tính và bảo vệ những ưu tiên của L.V. Kantorovich, người đã phát hiện ra những phương pháp này.

Lịch sử của quy hoạch tuyến tính ở Hoa Kỳ bắt đầu từ năm 1947, khi J. Danzig viết về nó trong tác phẩm của mình. L.V. Kantorovich đã nghiên cứu khả năng ứng dụng toán học vào các vấn đề quy hoạch, trên cơ sở đó chuyên khảo “Các phương pháp toán học trong tổ chức và lập kế hoạch sản xuất” được xuất bản năm 1939. Khám phá (khám phá) quan trọng nhất của L.V. Kantorovich là khả năng hình thành một cách rõ ràng về mặt toán học các vấn đề sản xuất quan trọng nhất, giúp tìm ra cách tiếp cận định lượng cho những vấn đề này, cũng như giải pháp của chúng bằng phương pháp số.

Nếu các tác phẩm đầu tiên của L.V. Kantorovich nhận được đánh giá đúng đắn vào thời điểm đó, thì khả năng cao là quy hoạch tuyến tính sẽ có sự tiến bộ lớn hơn nữa ở thời điểm hiện tại. Thật không may, công việc của ông vẫn còn ít người biết đến cả ở Liên Xô và các nước khác, và như Dantzig lưu ý: "...và trong thời gian này lập trình tuyến tính đã trở thành một nghệ thuật thực sự."

Kế hoạch tối ưu của bất kỳ chương trình tuyến tính nào phải được tự động liên kết với mức giá tối ưu hoặc theo L.V. Kantorovich, với “ước tính được xác định khách quan”. Việc tích lũy từ ngữ này nhằm mục đích làm tăng sự "chỉ trích" thuật ngữ này. Bản chất khám phá kinh tế của L.V. Kantorovich nằm ở mối quan hệ giữa giải pháp tối ưu và mức giá tối ưu.

Phương pháp quy hoạch tuyến tính

Bằng cách sử dụng các phương pháp quy hoạch tuyến tính, một số lượng lớn các bài toán cực đoan liên quan đến kinh tế đã được giải quyết. Trong những trường hợp này, các giá trị cực trị (cực đại và cực tiểu) của một số hàm có đại lượng thay đổi được tìm thấy.

Cơ sở của quy hoạch tuyến tính là giải hệ phương trình tuyến tính được chuyển thành phương trình và bất phương trình. Nó được đặc trưng bởi biểu thức toán học của các biến, một thứ tự nhất định, trình tự tính toán và phân tích logic. Nó được áp dụng:

• với sự chắc chắn về mặt toán học và các hạn chế về mặt định lượng giữa các biến và yếu tố được nghiên cứu;
• khi các hệ số có thể hoán đổi cho nhau do trình tự tính toán;
• trong trường hợp kết hợp logic toán học với sự hiểu biết về bản chất của hiện tượng đang được nghiên cứu.

Trong sản xuất công nghiệp, phương pháp này giúp tính toán hiệu suất tổng hợp tối ưu của các máy, bộ phận, dây chuyền sản xuất (nếu cho dãy sản phẩm và các giá trị tương ứng), cũng như giải quyết bài toán sử dụng hợp lý nguyên vật liệu (có hiệu quả cao nhất). số lượng phôi có lợi).

Trong nông nghiệp, phương pháp này được sử dụng để xác định chi phí tối thiểu của khẩu phần thức ăn, có tính đến một lượng thức ăn nhất định (dựa trên loại và chất dinh dưỡng mà chúng chứa).

Trong sản xuất đúc, phương pháp này giúp giải quyết vấn đề hỗn hợp có trong phí luyện kim. Phương pháp tương tự cho phép chúng ta giải quyết bài toán vận tải, bài toán gắn kết tối ưu nhất của doanh nghiệp tiêu thụ với doanh nghiệp sản xuất sản phẩm.

Một đặc điểm khác biệt của tất cả các bài toán kinh tế có thể giải bằng phương pháp quy hoạch tuyến tính là việc lựa chọn các phương án giải cũng như các điều kiện giới hạn nhất định. Giải quyết vấn đề như vậy có nghĩa là chọn phương án tối ưu nhất trong tất cả các phương án thay thế.

Giá trị thiết yếu của việc sử dụng phương pháp quy hoạch tuyến tính trong kinh tế học là việc lựa chọn phương án tối ưu nhất từ ​​một số lượng lớn tất cả các phương án có thể. Hầu như không thể giải quyết những vấn đề như vậy theo những cách khác để tìm ra mức độ hợp lý trong việc sử dụng các nguồn lực trong sản xuất.

Một trong những vấn đề chính được giải quyết bằng cách sử dụng quy hoạch tuyến tính là vấn đề vận tải, nhằm mục đích giảm thiểu tốc độ luân chuyển hàng hóa của hàng tiêu dùng khi vận chuyển chúng từ nhà sản xuất đến người tiêu dùng.

Phương pháp quy hoạch tuyến tính được sử dụng để giải nhiều bài toán cực đoan thường được xử lý trong kinh tế học. Việc giải các bài toán như vậy phụ thuộc vào việc tìm các giá trị cực trị (cực đại và cực tiểu) của một số hàm có đại lượng thay đổi.
Lập trình tuyến tính dựa trên việc giải một hệ phương trình tuyến tính (có biến đổi thành phương trình và bất phương trình), khi mối quan hệ giữa các hiện tượng đang được nghiên cứu là có tính hàm số chặt chẽ. Nó được đặc trưng bởi biểu thức toán học của các biến, một thứ tự nhất định, trình tự tính toán (thuật toán) và phân tích logic. Nó chỉ có thể được sử dụng trong trường hợp các biến và yếu tố đang được nghiên cứu có độ chắc chắn về mặt toán học và hạn chế về mặt định lượng, khi do một chuỗi tính toán đã biết, các yếu tố có thể thay thế cho nhau, khi logic trong tính toán, logic toán học được kết hợp với một sự hiểu biết logic về bản chất của hiện tượng đang được nghiên cứu.
Ví dụ, sử dụng phương pháp này trong sản xuất công nghiệp, năng suất tổng thể tối ưu của máy móc, bộ phận, dây chuyền sản xuất được tính toán (đối với một phạm vi sản phẩm nhất định và các giá trị nhất định khác), đồng thời giải quyết được vấn đề cắt giảm vật liệu hợp lý (với năng suất tối ưu). của phôi). Trong nông nghiệp, nó được sử dụng để xác định chi phí tối thiểu của khẩu phần thức ăn cho một lượng thức ăn nhất định (theo loại và chất dinh dưỡng có trong chúng). Bài toán hỗn hợp còn có thể tìm thấy ứng dụng trong sản xuất đúc (thành phần của điện tích luyện kim). Phương pháp tương tự được sử dụng để giải quyết bài toán vận tải, bài toán gắn hợp lý doanh nghiệp tiêu dùng với doanh nghiệp sản xuất.
Tất cả các bài toán kinh tế được giải bằng quy hoạch tuyến tính đều được phân biệt bằng các giải pháp thay thế và các điều kiện giới hạn nhất định. Để giải quyết một vấn đề như vậy có nghĩa là chọn phương án tốt nhất, Tối ưu, từ tất cả các phương án (thay thế) có thể chấp nhận được. Tầm quan trọng và giá trị của việc sử dụng phương pháp quy hoạch tuyến tính trong kinh tế học nằm ở chỗ phương án tối ưu được chọn từ một số lượng rất đáng kể các phương án thay thế. Hầu như không thể giải quyết những vấn đề như vậy bằng các phương pháp khác.

Ví dụ, hãy xem xét giải quyết vấn đề sử dụng hợp lý thời gian vận hành của thiết bị sản xuất.
Theo kế hoạch vận hành, bộ phận mài đã sản xuất được 500 vòng cho vòng bi loại A, 300 vòng cho vòng bi loại B và 450 vòng cho vòng bi loại B trong tuần đầu tiên của tháng 12. Tất cả các vòng được mài trên hai máy có thể hoán đổi cho nhau. năng lực khác nhau. Thời gian chạy máy của mỗi máy là 5000 phút. Độ phức tạp của các hoạt động (tính bằng phút trên mỗi vòng) trong sản xuất các loại vòng khác nhau được đặc trưng bởi dữ liệu sau (Bảng 6.5).
Bảng 6.5
Cần phải xác định tùy chọn tối ưu để phân phối hoạt động giữa các máy và thời gian dành cho tùy chọn tối ưu này. Hãy hoàn thành nhiệm vụ bằng phương pháp đơn giản.
Để biên soạn mô hình toán của bài toán này, chúng tôi đưa ra các ký hiệu sau: jc, x2, xъ, - tương ứng là số vòng ổ lăn loại L, B, B chế tạo trên máy I; x4, x5, x6 - tương ứng là số vòng ổ bi loại A, B, C sản xuất trên máy II.
Dạng tuyến tính phản ánh tiêu chí tối ưu sẽ có dạng:
min a(x) = 4x,-f 10x2-f 10x3-f 6x4-f 8x5+20x6 có hạn chế
4х, -f 10х2 -f 10;t3 lt; 5000
6x4 -f 8x5 -f 20x6 ~lt; 5000
x, = 500
x2 + x5 = 300
x3 + x6 = 450
Xj^0,j=l, ..., 6

Chúng ta hãy biến đổi điều kiện của bài toán bằng cách đưa vào các biến bổ sung (phụ trợ) và các biến giả định. Hãy viết điều kiện như thế này:
tăng đột biến lt;x(x) = 4dg, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Mx9 + Mx(0+Mx(,
Hệ phương trình phản ánh điều kiện hạn chế về thời gian sử dụng máy tính và số lượng sản phẩm sản xuất ra:
4x, + l(bc2 + 10x3 +x1 = 5000
6x4 + 8x5 + 20x6 + xs = 5000
Xj + x4 + x9 = 500
x2 + x5 + x10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Giải pháp cho vấn đề này được trình bày trong bảng. 6.6. Tùy chọn tối ưu đã đạt được ở giai đoạn thứ bảy (lặp lại). Nếu máy I sản xuất được 125 vòng bi loại A, 450 vòng bi loại B, máy II sản xuất được 375 vòng bi loại A và 300 vòng bi loại B thì với tải trọng thiết bị như vậy thời gian máy sẽ là 350 phút. giải phóng cho máy II. Tổng thời gian sử dụng theo phương án tối ưu sẽ là 9650 phút, trong khi thực tế là 10.000 phút sử dụng máy tính.
Một bài toán rất điển hình được giải bằng quy hoạch tuyến tính là bài toán vận chuyển. Ý nghĩa của nó là giảm thiểu luân chuyển hàng hóa khi vận chuyển hàng tiêu dùng từ nhà sản xuất đến người tiêu dùng, từ kho và cơ sở bán buôn đến điểm bán lẻ. Nó có thể được giải bằng phương pháp đơn hình hoặc phương pháp phân phối.
Giải pháp cho vấn đề vận tải bằng phương pháp phân phối đã được đưa ra trong ấn bản thứ ba của sách giáo khoa “Lý thuyết phân tích kinh tế” (“Tài chính và Thống kê”, 1996).

Giải bài toán sử dụng hợp lý máy công cụ bằng phương pháp đơn công

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) là một trong những nhánh đầu tiên và được nghiên cứu kỹ lưỡng nhất của lập trình toán học. Chính quy hoạch tuyến tính là phần mà từ đó nguyên tắc “lập trình toán học” bắt đầu phát triển. 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”, bởi vì Môn 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" xuất hiện do bản dịch không chính xác của "lập trình tuyến tính" tiếng Anh. 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 đó, bản dịch chính xác của “lập trình tuyến tính” trong tiếng Anh sẽ không phải là “lập trình tuyến tính”, mà là “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ữ quy hoạch tuyến tính, quy hoạch phi tuyến, quy hoạch toán học, v.v... đã đượ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ì vậy, quy hoạch 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, nhà kinh tế và kỹ sư do khả năng ứng dụng thực tế rộng rãi cũng như tính hài hòa về mặt toán học của nó.

Chúng ta có thể nói rằng quy hoạch 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.

Quy hoạch tuyến tính được sử dụng để giải các bài toán kinh tế như quản lý và lập kế hoạch sản xuất; trong nhiệm vụ xác định vị trí bố trí tối ưu thiết bị trên tàu biển và trong xưởng; trong bài toán xác định phương án vận chuyển hàng hóa tối ưu (bài toán vận tải); trong các vấn đề về phân phối nhân sự tối ưu, v.v.

Nhiệm vụ của lập trình tuyến tính (LP), như đã rõ ở trên, bao gồm việc tìm giá trị tối thiểu (hoặc tối đa) của hàm tuyến tính dưới các ràng buộc tuyến tính.

Có một số phương pháp để giải bài toán LP. Bài viết này sẽ thảo luận về một số trong số họ, đặc biệt:

Phương pháp đồ họa để giải bài toán LP;

phương pháp đơn giản;

Giải bài toán LP bằng bảng tính Excel;

3. Khái niệm quy hoạch phi tuyến

Trong hầu hết các bài toán kỹ thuật, việc xây dựng mô hình toán học không thể đơn giản hóa thành bài toán quy hoạch tuyến tính.

Các mô hình toán học trong các bài toán thiết kế vật thể thực hoặc quy trình công nghệ phải phản ánh các quá trình vật lý thực tế và theo quy luật, các quá trình phi tuyến xảy ra trong chúng. Các biến số của các đối tượng hoặc quá trình này được kết nối với nhau bằng các định luật phi tuyến vật lý, chẳng hạn như các định luật bảo toàn khối lượng hoặc năng lượng. Chúng được giới hạn ở phạm vi tối đa để đảm bảo khả năng thực hiện được về mặt vật lý của một đối tượng hoặc quy trình nhất định. Kết quả là hầu hết các bài toán lập trình toán học gặp phải trong các dự án nghiên cứu và bài toán thiết kế đều là các bài toán lập trình phi tuyến (NP).

Trong nghiên cứu này, chúng ta sẽ coi phương pháp giải các bài toán NP như vậy là phương pháp nhân tử Lagrange.

Phương pháp nhân tử Lagrange cho phép bạn tìm giá trị lớn nhất (hoặc nhỏ nhất) của hàm dưới các ràng buộc đẳng thức. Ý tưởng chính của phương pháp là chuyển từ bài toán tìm cực trị có điều kiện sang bài toán tìm cực trị vô điều kiện của một số hàm Lagrange đã xây dựng.

4. Lập trình động

Lập trình động là một công cụ toán học cho phép bạn nhanh chóng tìm ra giải pháp tối ưu trong trường hợp tình huống được phân tích không chứa các yếu tố không chắc chắn nhưng có một số lượng lớn các tùy chọn hành vi mang lại kết quả khác nhau, trong đó cần phải chọn phương án tốt nhất. một. Phương pháp lập trình động giải quyết một loại vấn đề nhất định bằng cách chia chúng thành các vấn đề nhỏ hơn, ít phức tạp hơn. Về nguyên tắc, những vấn đề thuộc loại này có thể được giải quyết bằng cách tìm kiếm qua tất cả các phương án có thể và chọn phương án tốt nhất trong số đó, nhưng thường thì việc tìm kiếm như vậy rất khó khăn. Trong những trường hợp này, quá trình đưa ra quyết định tối ưu có thể được chia thành các bước (giai đoạn) và được nghiên cứu bằng phương pháp quy hoạch động.

Việc giải bài toán bằng phương pháp quy hoạch động được thực hiện trên cơ sở nguyên lý tối ưu do R.E. Bellman xây dựng: hành vi tối ưu có đặc tính là bất kể trạng thái ban đầu của hệ thống và lời giải ban đầu, lời giải tiếp theo phải xác định hành vi tối ưu liên quan đến trạng thái thu được khi thực hiện nghiệm ban đầu.

Do đó, việc lập kế hoạch cho từng bước phải được thực hiện có tính đến lợi ích tổng thể thu được khi hoàn thành toàn bộ quá trình, điều này cho phép tối ưu hóa kết quả cuối cùng theo tiêu chí đã chọn.

Tuy nhiên, quy hoạch động không phải là một phương pháp giải phổ quát. Hầu hết mọi vấn đề được giải quyết bằng phương pháp này đều có đặc điểm riêng và đòi hỏi phải tìm kiếm bộ phương pháp thích hợp nhất để giải quyết nó. Ngoài ra, khối lượng lớn và độ phức tạp của việc giải các bài toán nhiều bước với nhiều trạng thái dẫn đến nhu cầu lựa chọn các bài toán ít chiều hoặc sử dụng thông tin nén.

Lập trình động được sử dụng để giải quyết các vấn đề như: phân bổ vốn đầu tư khan hiếm giữa các lĩnh vực sử dụng mới; xây dựng các quy tắc quản lý nhu cầu và hàng tồn kho; lập kế hoạch lịch trình cho việc sửa chữa thiết bị hiện tại và lớn cũng như việc thay thế thiết bị; tìm kiếm khoảng cách ngắn nhất trên mạng lưới giao thông, v.v.

Hãy chia quá trình tối ưu hóa thành n bước. Ở mỗi bước, cần xác định hai loại biến - biến trạng thái S và biến điều khiển X. Biến S xác định trạng thái nào mà hệ thống có thể tìm thấy ở bước thứ k nhất định. Tùy thuộc vào S, ở bước này có thể áp dụng một số điều khiển được đặc trưng bởi biến X. Việc áp dụng điều khiển X ở bước thứ k mang lại một số kết quả Wk(S,Xk) và chuyển hệ thống sang một số trạng thái mới S"( S,Xk). Đối với mỗi trạng thái có thể có ở bước thứ k, trong số tất cả các điều khiển có thể, một điều khiển tối ưu X*k được chọn sao cho kết quả đạt được ở các bước từ lượt thứ k đến lượt thứ n ra là tối ưu Đặc tính số của kết quả này được gọi là hàm Bellman Fk(S) và phụ thuộc vào số bước k và trạng thái của hệ thống S.

Tất cả các giải pháp cho vấn đề được chia thành hai giai đoạn. Ở giai đoạn đầu tiên, được gọi là tối ưu hóa có điều kiện, hàm Bellman và các điều khiển tối ưu được tìm thấy cho tất cả các trạng thái có thể có ở mỗi bước, bắt đầu từ bước cuối cùng.

Sau khi tìm thấy hàm Bellman và các điều khiển tối ưu tương ứng cho tất cả các bước từ bước thứ n đến bước đầu tiên, giai đoạn thứ hai của việc giải bài toán được thực hiện, được gọi là tối ưu hóa không bị ràng buộc.

Nói chung, bài toán quy hoạch động được phát biểu như sau: cần xác định điều khiển X* để chuyển hệ thống từ trạng thái ban đầu S0 sang trạng thái cuối cùng Sn, tại đó hàm mục tiêu F(S0,X*) lấy giá trị lớn nhất (nhỏ nhất).

Đặc điểm của mô hình toán học quy hoạch động như sau:

bài toán tối ưu hóa được xây dựng dưới dạng một quy trình điều khiển hữu hạn gồm nhiều bước;

hàm mục tiêu có tính cộng và bằng tổng các hàm mục tiêu của từng bước

việc lựa chọn điều khiển Xk ở mỗi bước chỉ phụ thuộc vào trạng thái của hệ thống ở bước này Sk-1 và không ảnh hưởng đến các bước trước đó (không có phản hồi);

trạng thái của hệ thống Sk sau mỗi bước điều khiển chỉ phụ thuộc vào trạng thái trước đó của hệ thống Sk-1 và hành động điều khiển Xk này (không có hậu quả) và có thể được viết dưới dạng phương trình trạng thái:

ở mỗi bước, điều khiển Xk phụ thuộc vào số lượng hữu hạn các biến điều khiển và trạng thái của hệ thống Sk phụ thuộc vào số lượng hữu hạn các biến;

điều khiển tối ưu X* là một vectơ được xác định bởi chuỗi các điều khiển từng bước tối ưu:

X*=(X*1, X*2, …, X*k, …, X*n),

số lượng trong đó xác định số bước của nhiệm vụ.

Tối ưu hóa có điều kiện. Như đã lưu ý ở trên, ở giai đoạn này, hàm Bellman và các điều khiển tối ưu được tìm thấy cho tất cả các trạng thái có thể có ở mỗi bước, bắt đầu từ bước cuối cùng theo thuật toán quét lùi. Ở bước thứ n cuối cùng, việc tìm điều khiển tối ưu X*n và giá trị của hàm Bellman Fn(S) không khó, vì

Fn(S)=max(Wn(S,Xn)),

trong đó mức tối đa được tìm kiếm trên tất cả các giá trị có thể có của Xn.

Các phép tính tiếp theo được thực hiện theo quan hệ truy hồi nối hàm Bellman ở mỗi bước với cùng một hàm nhưng được tính ở bước trước:

Fk(S)=max(Wk(S,Xk)+Fk+1(S"(S,Xk))).(1)

Mức tối đa (hoặc tối thiểu) này được xác định bởi tất cả các giá trị có thể có của biến điều khiển X cho k và S.

Tối ưu hóa vô điều kiện. Sau khi tìm được hàm Bellman và các điều khiển tối ưu tương ứng cho tất cả các bước từ bước thứ n đến bước thứ nhất (ở bước đầu tiên k=1 trạng thái của hệ bằng trạng thái ban đầu S0), giai đoạn thứ hai của việc giải bài toán là đã tiến hành. Điều khiển tối ưu được tìm thấy ở bước đầu tiên X1, việc áp dụng nó sẽ đưa hệ thống đến trạng thái S1(S,x1*), biết được điều gì có thể, sử dụng kết quả của tối ưu hóa có điều kiện, để tìm ra điều khiển tối ưu ở bước thứ hai. bước, cứ tiếp tục như vậy cho đến bước thứ n cuối cùng.

Bài thí nghiệm số 1 (Bài toán quy hoạch tuyến tính)

Đối với một công thức toán học đã cho của bài toán LP, giả sử thêm điều kiện không âm của các biến, hãy thực hiện các hành động sau:

Giải quyết vấn đề bằng đồ họa;

Đưa vấn đề về dạng ký hiệu kinh điển;

Tạo một bảng đơn giản;

Giải quyết vấn đề bằng phương pháp đơn giản theo cách thủ công hoặc sử dụng máy tính;

Tiến hành xây dựng bài toán LP kép;

Tìm lời giải cho bài toán kép từ bảng đơn thu được trước đó và phân tích kết quả thu được;

Kiểm tra kết quả giải trên bảng tính Excel;

Viết báo cáo chứa kết quả cho từng mục.

Phương pháp đồ họa. Để xây dựng một đa giác nghiệm, chúng ta chuyển đổi hệ thống ban đầu

, chúng tôi nhận được

Hãy vẽ các đường ranh giới.

Hàm tuyến tính F=f(x) là phương trình của đường thẳng c1x1 + c2x2 = const. Hãy vẽ hàm mục tiêu cho f(x)=0. để dựng đường thẳng 3x1 + 4x2 = 0, hãy dựng vectơ bán kính N = (3; 4) và qua điểm 0 vẽ một đường thẳng vuông góc với nó. Chúng ta di chuyển đường thẳng dựng sẵn F=0 song song với chính nó theo hướng của vectơ N.

Từ Hình 1, đường thẳng này trở thành đường tham chiếu liên quan đến đa giác được dựng của các nghiệm tại điểm B, trong đó hàm F lấy giá trị lớn nhất của nó. Điểm B nằm ở giao điểm của các đường thẳng 0,7x1 + 2x2 ≤ 13,1 và 2,3x1 + 2x2 =23/ Để xác định tọa độ của nó, ta giải hệ phương trình:

Phương án nhiệm vụ tối ưu: x1 = 6,187; x2 = 4,38, thay giá trị của x1 và x2 vào hàm mục tiêu, ta thu được Fmax = 3*6,187+4*4,38=36,08.

Vì vậy, để đạt được lợi nhuận tối đa là 36,06 USD, cần lập kế hoạch sản xuất 6 đơn vị. sản phẩm P1 và 4 đơn vị. Sản phẩm P2.

Dạng chính tắc của bài toán LP. Chúng ta hãy viết bài toán phân bổ tài nguyên ở dạng chuẩn. Bằng cách thêm các biến không âm x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 vào hệ ràng buộc ban đầu, ta có:

Bảng đơn giản của LP. Trong trường hợp các biến cơ bản (x3, x4, x5), bảng đơn giản ban đầu sẽ có dạng:

Bảng 1.

Nó đã tương ứng với kế hoạch tham chiếu x(0) = T (cột các thuật ngữ tự do).

Cùng với sự phát triển của công nghệ và sự tăng trưởng của sản xuất công nghiệp, nhiệm vụ tìm kiếm giải pháp tối ưu trong các lĩnh vực hoạt động khác nhau của con người ngày càng đóng vai trò quan trọng. Công cụ chính để giải quyết những vấn đề này là mô hình toán học - một mô tả chính thức về hiện tượng đang được nghiên cứu và nghiên cứu bằng các công cụ toán học.

Bất kỳ mô hình nào của một quá trình thực tế đều giả định trước sự lý tưởng hóa và trừu tượng hóa, nhưng chúng không nên đi quá xa nội dung của vấn đề để mô hình được xây dựng không làm mất đi những đặc điểm cơ bản của đối tượng được mô hình hóa, tức là phù hợp với đối tượng đó. Mặt khác, nếu bạn xây dựng một mô hình phức tạp có tính đến tất cả các đặc điểm tinh tế của quá trình đang được nghiên cứu, điều này có thể vi phạm ý nghĩa của việc lập mô hình, một trong những mục tiêu của nó là đơn giản hóa việc trình bày vấn đề sao cho nó nghiên cứu nó dễ dàng hơn (một mô hình quá phức tạp thường không thể phân tích được).

Trong một số lượng lớn các trường hợp, mức độ 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 được giả định là tuyến tính. Ở đây có một sự tương tự hoàn toàn với việc thông tin rất quan trọng và thường toàn diện về hành vi của một hàm tùy ý dựa trên nghiên cứu đạo hàm của nó - hàm này được thay thế trong vùng lân cận của mỗi điểm bằng sự phụ thuộc tuyến tính. Một số lượng đáng kể các quy trình kinh tế, kỹ thuật và các quy trình khác được mô tả khá tốt và đầy đủ bằng các mô hình tuyến tính. Điều này xác định tầm quan trọng của vai trò của lập trình tuyến tính - một phương pháp tìm cực trị có điều kiện của hàm tuyến tính trên một tập hợp được chỉ định bằng cách sử dụng các quan hệ tuyến tính như đẳng thức và bất đẳng thức (ràng buộc tuyến tính).

Điều kiện áp dụng mô hình tuyến tính

Tính chia được. Nếu phương pháp được áp dụng với cường độ a và b (a< b), то его можно применять с любой интенсивностью x .

Điều kiện này không tầm thường. Ví dụ: nếu cường độ của một công việc được đo bằng số lượng công nhân được giao cho nó thì chỉ các giá trị cường độ nguyên mới được chấp nhận. Nếu cường độ được đo bằng số giờ công mỗi ngày thì nguyên tắc phân chia rõ ràng được thỏa mãn.

Tính tỉ lệ. Đầu vào, đầu ra và tiện ích được tạo ra bởi mỗi phương pháp tỷ lệ thuận với cường độ của nó.

Đây là điều kiện của lợi nhuận không đổi (theo mọi nghĩa), không có tính kinh tế theo quy mô. Cần đặc biệt chú ý đến việc xác định phạm vi cường độ của phương pháp công nghệ trong đó phương pháp này thỏa mãn điều kiện tỷ lệ. Ví dụ, nếu một thợ hàn hàn một thùng chứa trong 6 giờ thì hai thợ hàn có thể hoàn thành công việc đó trong 3 giờ. Nhưng sáu người sẽ không nấu được một hộp trong một giờ.

Tính cộng. Các tiện ích và - đối với mỗi thành phần - chi phí và sản phẩm được tạo ra bằng tất cả các phương pháp đều được tổng hợp lại.

Nguyên tắc cộng tính đòi hỏi phải mô tả cẩn thận và nhất quán các thuật ngữ có trong mô hình: phương pháp công nghệ, thành phần, công dụng.

Các dạng viết bài toán quy hoạch tuyến tính

Ở dạng tổng quát nhất, bài toán LP được viết như sau:

• 2 (2)
• 3 (3)

• 4 (4)
• 5 (5)

Định nghĩa 1. Ma trận được gọi là ma trận bài toán (1) - (5). ?

Một cách biểu diễn thống nhất hơn của bài toán LP là dạng chuẩn:

với i(1,…,m), x 0.

Đặc điểm của dạng chuẩn: tất cả các biến đều không âm (n1 = n), không có hạn chế về đẳng thức (m1 = 0). Nếu CF cực đại thì m2 = 0 và không có hạn chế nào ở dạng (3); ngược lại m2 = m và không có hạn chế nào ở dạng (4). Giả sử và, dạng chuẩn có thể được viết như sau:

6c x max (phút) tại Ax() b, x 0. (6)

Nhưng dạng đơn giản nhất là dạng chuẩn mực của việc viết các bài toán LP.

Định nghĩa 2. Bài toán (1) - (4) được trình bày dưới dạng chính tắc nếu tất cả các ràng buộc, ngoại trừ điều kiện không âm của các biến, đều bằng nhau (m1 = m) và tất cả các biến đều không âm (n1 = n) . ?

Do đó, bài toán LP ở dạng chính tắc có dạng

• 7c x max (phút) tại Ax = b, x 0. (7)
• 1.2 Cơ bản của phương pháp đơn hình

Chúng ta hãy xem xét vấn đề LP ở dạng chính tắc:

• 9 (9)
• 10x 0 (10)

Gọi và lần lượt là hàng i và cột j của ma trận A0. Chúng ta sẽ giả sử rằng các hàng của ma trận là độc lập tuyến tính.

Bất kỳ vấn đề LP nào cũng có thể được rút gọn về dạng chính tắc; nếu một bài toán ở dạng chính tắc có thể giải được thì trong số các lời giải của nó có ít nhất một điểm cực trị của tập hợp lời giải được chấp nhận; các điểm cực trị của tập nghiệm có thể chấp nhận được của bài toán LP ở dạng chính tắc trùng với BDD.

Dựa trên những thực tế trên, chúng ta có thể hình dung quy trình sau để giải quyết vấn đề. Hãy kiểm tra bằng cách nào đó xem bài toán có lời giải hay không và nếu có thì đưa nó về dạng chuẩn. Cho ma trận A0 ở dạng chính tắc có thứ nguyên m × n và hạng m. Chúng ta hãy xây dựng tất cả các ma trận con m × m của ma trận A0, loại bỏ các ma trận suy biến, các ma trận con còn lại tương ứng với các cơ số của ma trận A0. Chúng ta hãy chọn các cơ sở có thể chấp nhận được từ chúng và xây dựng các BFS tương ứng. Chúng ta hãy chọn một BDD mang lại hàm mục tiêu tối đa.

Nhưng thuật toán như vậy không thể được triển khai trong thực tế vì số lượng BDD tăng theo cấp số nhân theo quy mô của vấn đề (số lượng biến và/hoặc ràng buộc). Quy trình có thể được đẩy nhanh nếu nó được tổ chức sao cho trong quá trình liệt kê BDR, giá trị của CF không giảm (cải tiến nhất quán của kế hoạch). Đây là ý tưởng ban đầu của phương pháp đơn hình, được thực hiện như sau.

1. 3 bảng đơn giản

lập trình tuyến tính tối ưu hóa đơn giản

Các phép biến đổi của bài toán LP ở dạng chính tắc, được thực hiện bằng phương pháp đơn hình, được biểu diễn thuận tiện dưới dạng các phép biến đổi của bảng đơn. Khung nhìn chung của bảng đơn giản, tương ứng với lần lặp hiện tại của phương pháp đơn giản, được trình bày trong Bảng 1.

Dòng trên cùng chứa: tiêu đề của cột đầu tiên, mã định danh của tất cả các biến nhiệm vụ (chính, bổ sung, phụ, v.v.) và tiêu đề của cột cuối cùng. M dòng tiếp theo mô tả các phương trình của bài toán có dạng:

mà họ có khi bắt đầu lặp lại. Đầu tiên, định danh của biến cơ sở (trong cơ sở hiện tại) cho phương trình tương ứng được chỉ định. Sau đó theo dõi hệ số của các biến (theo thứ tự ghi các biến ở dòng đầu tiên). Phần tử cuối cùng của dòng là phía bên phải của ràng buộc.

Dòng dưới cùng tương ứng với phương trình

12, ở đâu và. (12)

đại diện cho CF Biến z đóng vai trò là biến cơ bản trong đó (nó có hệ số 1 và không có trong các phương trình khác); số F là vế phải của phương trình (12), giá trị của CF trên nghiệm cơ bản hiện tại.

Bảng 1. Tổng quan về bảng đơn

Bình luận. Bảng mô tả hệ phương trình (11), do đó BDD hiện tại có thể thu được bằng cách đặt các biến cơ bản bằng các phần tử tương ứng của cột cuối cùng và các biến không cơ bản bằng 0. ?

Tại lần lặp đang được xem xét, điều sau đây sẽ xảy ra.

Nếu không có phần tử âm nào trong hàng z hoặc trong các cột tương ứng với các biến thì BDD hiện tại là tối ưu và các biến cơ sở tối ưu được ghi vào cột đầu tiên của bảng. Ngược lại, cột của biến xs mà s< 0, становится направляющим.

Nếu tất cả các phần tử của cột hướng dẫn đều không dương thì bài toán không bị chặn. Mặt khác, chúng tôi tính tỷ lệ các phần tử của cột cuối cùng và cột hướng dẫn cho tất cả các hàng có phần tử dương trong cột hướng dẫn. Hàng r có tỷ lệ này tối thiểu sẽ trở thành hàng hướng dẫn. Trong cột đầu tiên của bảng đơn sau, biến xs sẽ thay thế biến xj(r).

Bây giờ ars là một yếu tố kích hoạt. Các phần tử của bảng đơn sau được tính bằng công thức:

13 lúc lúc tôi r (13)

• 14 (14)
• 15 (15)

Xét j = j(k). Từ (11) và (12) suy ra cột j (cơ bản) có số 1 ở hàng k và số 0 ở các hàng còn lại: j = 0, aij = 1 với i = k, ngược lại aij = 0. Đặt k r (cột j được bảo toàn ở cơ sở mới). Khi đó ari = 0 và từ (13), (14), (16) suy ra với mọi i và. Khi tính đến điều này, chúng ta hãy xây dựng các quy tắc để chuyển đổi bảng đơn khi chuyển sang cơ sở mới:

• · Trong tiêu đề của dòng hướng dẫn chúng ta đặt tiêu đề của cột hướng dẫn;
• · chia tất cả các số của đường dẫn cho phần tử phân giải;
• · cột hướng dẫn trở thành một, với một cột ở hàng hướng dẫn;
• · Các cột cơ sở hiện tại có số khác j(r) không thay đổi;
• · Tất cả các số khác trong bảng (bao gồm các phần tử ở hàng dưới cùng và cột cuối cùng) được tính lại theo công thức (13) - (15), (16).

Phương pháp này là một phương pháp liệt kê có mục đích các nghiệm tham chiếu cho bài toán quy hoạch tuyến tính. Nó cho phép, trong một số bước hữu hạn, tìm ra giải pháp tối ưu hoặc xác định rằng không có giải pháp tối ưu.

1. Nêu phương pháp tìm lời giải tham chiếu tối ưu
2. Chỉ ra phương pháp chuyển đổi từ giải pháp tham chiếu này sang giải pháp tham chiếu khác, tại đó giá trị của hàm mục tiêu sẽ gần với giá trị tối ưu hơn, tức là. chỉ ra cách cải thiện giải pháp tham khảo
3. Đặt ra các tiêu chí cho phép bạn nhanh chóng dừng việc tìm kiếm giải pháp hỗ trợ ở giải pháp tối ưu hoặc đưa ra kết luận về việc chưa có giải pháp tối ưu.

Thuật toán của phương pháp đơn hình giải bài toán quy hoạch tuyến tính

1. Đưa vấn đề về dạng chính tắc
2. Tìm giải pháp hỗ trợ ban đầu bằng “cơ sở đơn vị” (nếu không có giải pháp hỗ trợ thì bài toán không có lời giải do hệ thống ràng buộc không tương thích)
3. Tính toán ước lượng phân rã vectơ dựa trên lời giải tham chiếu và điền vào bảng phương pháp đơn hình
4. Nếu tiêu chuẩn về tính duy nhất của lời giải tối ưu được thỏa mãn thì lời giải của bài toán kết thúc
5. Nếu điều kiện tồn tại của tập hợp các lời giải tối ưu được thỏa mãn thì tất cả các lời giải tối ưu đều được tìm thấy bằng cách liệt kê đơn giản.

Ví dụ về giải bài toán bằng phương pháp đơn hình

Giải bài toán bằng phương pháp đơn hình:

Giải pháp:

Chúng tôi đưa vấn đề về dạng kinh điển.

Để làm điều này, chúng tôi đưa vào một biến bổ sung x 6 với hệ số +1 ở vế trái của ràng buộc bất đẳng thức thứ nhất. Biến x 6 được đưa vào hàm mục tiêu với hệ số bằng 0 (tức là không được đưa vào).

Chúng tôi nhận được:

Chúng tôi tìm giải pháp hỗ trợ ban đầu. Để làm điều này, chúng ta đánh đồng các biến tự do (chưa được giải) bằng 0 x1 = x2 = x3 = 0.

Chúng tôi nhận được giải pháp tham khảo X1 = (0,0,0,24,30,6) với cơ sở đơn vị B1 = (A4, A5, A6).

Chúng tôi tính toán ước tính phân rã vectơđiều kiện trên cơ sở lời giải đối chiếu theo công thức:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vectơ hệ số của hàm mục tiêu đối với các biến cơ bản
• X k = (x 1k, x 2k, ..., x mk) - vectơ khai triển của vectơ tương ứng A k theo cơ sở của nghiệm tham chiếu
• C k là hệ số của hàm mục tiêu đối với biến x k.

Các ước lượng của các vectơ có trong cơ sở luôn bằng 0. Lời giải tham chiếu, hệ số khai triển và ước lượng khai triển của vectơ điều kiện dựa trên lời giải tham chiếu được viết bằng bảng đơn:

Ở đầu bảng, để dễ tính toán ước tính, người ta viết các hệ số của hàm mục tiêu. Trong cột đầu tiên "B", các vectơ có trong cơ sở của nghiệm tham chiếu được viết. Thứ tự viết các vectơ này tương ứng với số lượng ẩn số được phép trong các phương trình ràng buộc. Trong cột thứ hai của bảng "C b", các hệ số của hàm mục tiêu cho các biến cơ bản được viết theo cùng thứ tự. Với việc sắp xếp chính xác các hệ số của hàm mục tiêu trong cột “C b”, các ước lượng của vectơ đơn vị có trong cơ sở luôn bằng 0.

Ở hàng cuối cùng của bảng có ước tính Δ k trong cột “A 0”, các giá trị của hàm mục tiêu trên nghiệm tham chiếu Z(X 1) được ghi.

Giải pháp hỗ trợ ban đầu không phải là tối ưu, vì trong bài toán cực đại các ước lượng Δ 1 = -2, Δ 3 = -9 đối với các vectơ A 1 và A 3 đều âm.

Theo định lý cải tiến nghiệm hỗ trợ, nếu trong bài toán cực đại có ít nhất một vectơ có ước lượng âm thì có thể tìm ra nghiệm hỗ trợ mới mà giá trị của hàm mục tiêu sẽ lớn hơn.

Chúng ta hãy xác định vectơ nào trong hai vectơ sẽ dẫn đến mức tăng lớn hơn trong hàm mục tiêu.

Gia số của hàm mục tiêu được tìm theo công thức: .

Chúng tôi tính toán các giá trị của tham số θ 01 cho cột thứ nhất và thứ ba bằng công thức:

Ta thu được θ 01 = 6 với l = 1, θ 03 = 3 với l = 1 (Bảng 26.1).

Chúng ta tìm thấy sự gia tăng của hàm mục tiêu khi đưa vào cơ sở vectơ đầu tiên ΔZ 1 = - 6*(- 2) = 12 và vectơ thứ ba ΔZ 3 = - 3*(- 9) = 27.

Do đó, để tiếp cận lời giải tối ưu nhanh hơn, cần đưa vectơ A3 vào cơ sở của lời giải tham chiếu thay vì vectơ đầu tiên của cơ sở A6, vì giá trị tối thiểu của tham số θ 03 đạt được ở hàng đầu tiên ( l = 1).

Thực hiện phép biến đổi Jordan với phần tử X13 = 2, ta thu được nghiệm tham chiếu thứ hai X2 = (0,0,3,21,42,0) với cơ sở B2 = (A3, A4, A5). (Bảng 26.2)

Lời giải này không tối ưu vì vectơ A2 có ước lượng âm Δ2 = - 6. Để cải thiện lời giải cần đưa vectơ A2 vào cơ sở của lời giải tham chiếu.

Chúng tôi xác định số lượng vectơ xuất phát từ cơ sở. Để làm điều này, chúng tôi tính toán tham số θ 02 cho cột thứ hai, nó bằng 7 với l = 2. Do đó, chúng tôi rút ra vectơ cơ sở thứ hai A4 từ cơ sở. Thực hiện phép biến đổi Jordan với phần tử x 22 = 3, ta thu được nghiệm tham chiếu thứ ba X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Bảng 26.3).

Giải pháp này là giải pháp tối ưu duy nhất, vì đối với tất cả các vectơ không có trong cơ sở thì ước tính đều dương

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Trả lời: max Z(X) = 201 tại X = (0,7,10,0,63).

Phương pháp quy hoạch tuyến tính trong phân tích kinh tế

Phương pháp lập trình tuyến tính giúp có thể biện minh cho giải pháp kinh tế tối ưu nhất trong điều kiện bị hạn chế nghiêm trọng liên quan đến nguồn lực sử dụng trong sản xuất (tài sản cố định, vật tư, nguồn lao động). Việc sử dụng phương pháp này trong phân tích kinh tế giúp giải quyết các vấn đề chủ yếu liên quan đến việc lập kế hoạch hoạt động của một tổ chức. Phương pháp này giúp xác định số lượng sản phẩm đầu ra tối ưu cũng như phương hướng sử dụng hiệu quả nhất các nguồn lực sản xuất sẵn có của tổ chức.

Sử dụng phương pháp này, cái gọi là bài toán cực trị được giải quyết, bao gồm việc tìm các giá trị cực trị, nghĩa là hàm cực đại và cực tiểu của các đại lượng thay đổi.

Giai đoạn này dựa trên việc giải hệ phương trình tuyến tính trong trường hợp các hiện tượng kinh tế được phân tích được kết nối bởi sự phụ thuộc tuyến tính, hàm chặt chẽ. Phương pháp quy hoạch tuyến tính được sử dụng để phân tích các biến khi có các yếu tố giới hạn nhất định.

Việc giải bài toán được gọi là bài toán vận chuyển bằng phương pháp quy hoạch tuyến tính là rất phổ biến. Nội dung của nhiệm vụ này là giảm thiểu chi phí phát sinh liên quan đến việc vận hành các phương tiện theo các hạn chế hiện có về số lượng phương tiện, khả năng chuyên chở, thời gian hoạt động của chúng nếu có nhu cầu phục vụ số lượng khách hàng tối đa.

Ngoài ra, phương pháp này còn được sử dụng rộng rãi để giải bài toán lập lịch. Nhiệm vụ này bao gồm việc phân bổ thời gian hoạt động cho nhân sự của một tổ chức nhất định sao cho có thể chấp nhận được nhất đối với cả các thành viên của nhân sự này và khách hàng của tổ chức đó.

Nhiệm vụ này là tối đa hóa số lượng khách hàng được phục vụ trong điều kiện hạn chế về số lượng nhân viên sẵn có cũng như quỹ thời gian làm việc.

Vì vậy, phương pháp quy hoạch tuyến tính rất phổ biến trong việc phân tích việc bố trí và sử dụng các loại nguồn lực khác nhau, cũng như trong quá trình lập kế hoạch và dự báo hoạt động của các tổ chức.

Tuy nhiên, lập trình toán học cũng có thể được áp dụng cho những hiện tượng kinh tế đó, mối quan hệ giữa chúng không phải là tuyến tính. Với mục đích này, các phương pháp quy hoạch phi tuyến, động và lồi có thể được sử dụng.

Lập trình phi tuyến dựa trên bản chất phi tuyến của hàm mục tiêu hoặc các ràng buộc hoặc cả hai. Các dạng của hàm mục tiêu và các ràng buộc bất đẳng thức trong những điều kiện này có thể khác nhau.

Lập trình phi tuyến tính được sử dụng trong phân tích kinh tế, đặc biệt khi thiết lập mối quan hệ giữa các chỉ số thể hiện hiệu quả hoạt động của tổ chức và khối lượng của hoạt động này, cơ cấu chi phí sản xuất, điều kiện thị trường, v.v.

Lập trình động dựa trên việc xây dựng cây quyết định. Mỗi tầng của cây này đóng vai trò là một giai đoạn để xác định hậu quả của một quyết định trước đó và loại bỏ các lựa chọn không hiệu quả cho quyết định đó. Như vậy, lập trình động có tính chất nhiều bước, nhiều giai đoạn. Kiểu lập trình này được sử dụng trong phân tích kinh tế để tìm ra các phương án tối ưu cho sự phát triển của một tổ chức cả hiện tại và tương lai.

Lập trình lồi là một loại lập trình phi tuyến. Kiểu lập trình này thể hiện bản chất phi tuyến tính của mối quan hệ giữa kết quả hoạt động của tổ chức và chi phí của nó. Lập trình lồi (hay còn gọi là lõm) phân tích các hàm mục tiêu lồi và hệ thống ràng buộc lồi (điểm khả thi). Lập trình lồi được sử dụng trong phân tích các hoạt động kinh tế với mục đích giảm thiểu chi phí và lập trình lõm với mục đích tối đa hóa thu nhập dưới những hạn chế hiện có đối với hành động của các yếu tố ảnh hưởng đến các chỉ số được phân tích theo cách ngược lại. Do đó, với các loại quy hoạch đang được xem xét, các hàm mục tiêu lồi được giảm thiểu và các hàm mục tiêu lõm được tối đa hóa.