Thực đơn
trang chủMicrosoft

Lý thuyết quy hoạch tuyến tính. Phương pháp đơn giản giải bài toán quy hoạch tuyến tính

Lập trình tuyến tính biểu thị các phương pháp giải một loại bài toán nhất định về tìm giá trị cực trị (kiểm tra hoặc min). Chúng dựa trên giải pháp của hệ thống Các phương trình tuyến tính, khi sự phụ thuộc có tính hàm chặt chẽ. Trong mô hình lập trình tuyến tính ba thành phần được phân biệt: hàm mục tiêu (cực đại hóa hoặc cực tiểu), hệ thống các ràng buộc và điều kiện không âm của các biến. Bộ máy toán học của quy hoạch tuyến tính được sử dụng để giải các bài toán kinh tế, kỹ thuật, quân sự, v.v.

TRONG nhiệm vụ kinh tế Trong lập kế hoạch tối ưu, việc giải hàm mục tiêu phụ thuộc vào việc tìm ra mức tối đa, chẳng hạn như lợi nhuận, khối lượng sản xuất, năng suất lao động hoặc mức tối thiểu của chi phí hiện tại, đầu tư vốn, thời gian hoàn thành công việc, v.v.

Đồng thời, cần lưu ý rằng không phải mọi bài toán quy hoạch tối ưu đều có thể được xây dựng và giải quyết trong khuôn khổ quy hoạch tuyến tính. Để làm được điều này, phải đáp ứng bốn điều kiện cơ bản.

  • 1. Vấn đề phải được xây dựng và định lượng rõ ràng tiêu chí tối ưu,điều này không dễ thực hiện trong thực tế. Hiệu quả hoạt động của một doanh nghiệp thường được đánh giá bằng một số chỉ số: khối lượng sản xuất, phạm vi và chất lượng sản phẩm, lợi nhuận sản xuất, v.v. Việc lựa chọn một tiêu chí có thể không phải là tiêu chí tốt nhất theo quan điểm của tiêu chí khác và ngược lại .
  • 2. Quan trọng một phần không thể thiếu Các bài toán quy hoạch tuyến tính được những hạn chế, liên quan đến nguồn lực sẵn có, nhu cầu hoặc các yếu tố khác. Trong nền kinh tế thực, không phải lúc nào cũng có thể tính đến sự tương tác số lượng lớn do đó xây dựng một mô hình đơn giản hóa sẽ phản ánh đúng bản chất thực tế hơn.
  • 3. Quy hoạch tuyến tính liên quan đến việc lựa chọn các phương án và chỉ được áp dụng khi các điều kiện cụ thể của bài toán kinh tế xác định điều này quyền tự do lựa chọn.
  • 4. Mô hình phải chứa chỉ các phương trình tuyến tính hoặc bất đẳng thức, những thứ kia. tất cả các biến của bài toán phải có lũy thừa bậc một. Sự phụ thuộc kinh tế thực sự không phải lúc nào cũng tuyến tính.

Xét các điều kiện liên quan và tính gần đúng tình hình kinh tế để giải bài toán quy hoạch tuyến tính, cũng cần tính đến việc áp đặt biến những hạn chế quá chặt chẽ có thể dẫn đến sự không nhất quán của toàn bộ hệ thống các điều kiện ban đầu của bài toán.

Dựa vào bản chất của vấn đề đang giải quyết, các phương pháp quy hoạch tuyến tính có thể được chia thành hai nhóm.

  • 1.Phương pháp phổ quát. Với sự giúp đỡ của họ, mọi vấn đề về quy hoạch tuyến tính đều có thể được giải quyết. Phổ biến nhất là phương pháp đơn giản, được đề xuất bởi J. Danzig, phương pháp giải số nhân, được phát triển bởi học giả L.V. Kantorovich vào năm 1939, khoảng 10 năm trước khi nó xuất hiện ở nước ngoài.
  • 2. Các phương pháp đặc biệt. Những phương pháp này đơn giản hơn những phương pháp phổ quát nhưng không thể áp dụng cho tất cả các nhiệm vụ. Bao gồm các phương pháp phân phốiđể giải quyết vấn đề vận tải, phương pháp giải thuật ngữ A. L. Lurie, phương pháp niên kim chênh lệch MỘT. L. Brudno, Phương pháp Hungary.

Một nhóm đặc biệt của phương pháp quy hoạch tuyến tính bao gồm phương pháp gần đúng, khác với những cái khác ở chỗ chúng không đảm bảo một giải pháp tối ưu hoàn toàn cho vấn đề, nhưng chúng đơn giản và thích ứng tốt với các tính toán thủ công. Bao gồm các phương pháp chỉ số, Phương pháp xấp xỉ Vogel và vân vân.

Phương pháp đơn giản. Để hiểu rõ hơn ý tưởng của phương pháp đơn giản, hãy xem xét giải quyết vấn đề tối ưu hóa việc sử dụng tài nguyên để đạt được lợi nhuận tối đa.

Ví dụ 2.21

Có cơ sở sản xuất phụ trợ sử dụng nguyên vật liệu còn lại của dây chuyền sản xuất chính. TRÊN sản xuất này Việc sản xuất các loại cửa khác nhau đã được đưa ra: sử dụng kính (dòng LAN) và không sử dụng kính (dòng DV). Việc bán các sản phẩm này được đảm bảo, tức là Sản phẩm có thể được sản xuất theo bất kỳ tỷ lệ nào, nhưng có hạn chế về số lượng công việc trong xưởng và nguồn nguyên liệu cơ bản. Nhiệm vụ là lập kế hoạch cho xưởng sản xuất hàng tháng để mang lại lợi nhuận lớn nhất có thể.

Nhiệm vụ không đặt ra điều kiện cho việc bắt buộc sử dụng toàn bộ khối lượng tài nguyên. Điều cần thiết là việc tiêu thụ thời gian làm việc không vượt quá giới hạn quy định.

Hãy xem xét chương trình 1, liên quan đến việc chỉ sản xuất các cửa thuộc dòng DV mà không sử dụng kính để sản xuất.

Nếu bạn chỉ phát hành TV, sử dụng tất cả các tài nguyên có sẵn thì chúng sẽ đủ để phát hành:

  • - theo thời gian làm việc: 520/9,2 = 56 (cái);
  • - gỗ: 24/0,3 = 80 (chiếc.).

Vì vậy, mọi nguồn lực chỉ đủ để sản xuất 56 cánh cửa.

Lợi nhuận từ đợt phát hành này sẽ là 168.000 rúp. (56 3000).

Chương trình 2 giả định chỉ sản xuất các cửa từ phạm vi mạng LAN. TRONG trong trường hợp này sẽ có đủ nguồn lực để phát hành:

  • - nhưng thời gian làm việc: 520/4 = 130 (cái);
  • - gỗ: 24/0,6 = 40 (cây);
  • - kính: 40/2 = 20 (chiếc.).

Một cách tối ưu, chỉ có thể sản xuất 20 cửa LAN, bị hạn chế bởi sự hiện diện của kính. Việc này sẽ mất 12 m gỗ, từ phần còn lại có thể sản xuất thêm 40 miếng nữa. cửa của phạm vi DV. Để sản xuất 20 chiếc. ICE và 40 chiếc. DV sẽ được sử dụng 448 giờ công.

Lợi nhuận sẽ là 160 nghìn rúp. (20 -2 + 40-3). Vì vậy, chương trình đầu tiên là thích hợp hơn. Có những lựa chọn khác.

Hạn chế của nhiệm vụ này là:

Hãy vẽ một đường thẳng trên đồ thị L bạn tương ứng với bất đẳng thức thứ nhất: Bất đẳng thức thứ hai tương ứng với đường thẳng b 2:

Bất đẳng thức thứ ba trong đồ thị ứng với đường thẳng song song với trục hoành L 3:

Vì kế hoạch phát hành phải dựa trên tất cả năm ràng buộc của vấn đề nên khu vực của các giải pháp khả thi trong trường hợp này sẽ là một đa giác được tô bóng.


Giá trị lớn nhất của hàm mục tiêu tìm được trong các phép tính trước sẽ tương ứng với các điểm của đường thẳng:

Đa giác giới hạn phạm vi của các giải pháp khả thi cho vấn đề. Trong số rất nhiều giải pháp, bạn cần chọn giải pháp có giá trị lợi nhuận tối đa. Trong trường hợp của chúng tôi, cái tôi sẽ là điểm giao nhau của các đường L ( Và 1 2 . Tiếp theo, hệ phương trình tuyến tính được giải:

Giải hệ phương trình, ta được: do đó lợi nhuận là:

Nếu đường thẳng tương ứng với hàm mục tiêu (trong phương pháp đồ họa) đi qua đỉnh của đa giác thì bài toán có một phương án tối ưu duy nhất. Nếu trùng với cạnh của đa giác thì bài toán có nhiều nghiệm.

Lời giải tối ưu phải đi qua một đỉnh hoặc một cạnh của đa giác. Do đó, một trong các đỉnh tương ứng với giải pháp tối ưu, nhưng lúc đầu người ta không biết đó là giải pháp nào.

Phương pháp đồ họa đơn giản và trực quan, nhưng ứng dụng của nó còn hạn chế.

Với ba biến, cần phải xây dựng một khối đa diện trong hệ tọa độ nhiều chiều. Với bốn hoặc nhiều biến hình ảnh đồ họa không thể nào. Nhưng có thể tưởng tượng không gian đa chiều một cách trừu tượng. Nếu điều kiện của vấn đề là nhất quán thì vùng giá trị chấp nhận được(ODZ) tạo thành một đa giác lồi trong không gian n chiều.

Trong trường hợp này, nghiệm tối ưu, nếu tồn tại, nhất thiết phải đạt được ở một đỉnh nào đó của khối đa diện (có thể ở nhiều đỉnh).

Vì vậy, để tìm lời giải cho bài toán quy hoạch tuyến tính, việc liệt kê các phương án tương ứng với các đỉnh của khối đa diện là đủ. Chúng được gọi là kế hoạch tham khảo. Tuy nhiên, trong nhiệm vụ phức tạp có thể có quá nhiều trong số chúng và việc xác định các kế hoạch tham khảo sẽ đòi hỏi một lượng tính toán khổng lồ.

Phương pháp đơn hình cho phép bạn thực hiện tìm kiếm theo thứ tự các đỉnh của khối đa diện.

Hãy xem xét trình tự tính toán bằng phương pháp đơn hình bằng một ví dụ.

Ví dụ 2.23

Doanh nghiệp có ba nhóm thiết bị (I, II, III), trên đó sản xuất ra bốn loại sản phẩm (A, B, C, D). Tất cả các sản phẩm đều có doanh số bán hàng không giới hạn và do đó, doanh nghiệp có thể lập kế hoạch chương trình phân loại trong phạm vi nhất định.

Các hạn chế sau đây được áp dụng:

  • - sự sẵn có của các thiết bị cơ bản;
  • - tiêu chuẩn về thời gian xử lý từng loại sản phẩm trên thiết bị của từng nhóm;
  • - số tiền lãi mà doanh nghiệp nhận được trên một đơn vị sản phẩm cụ thể.

Bạn cần thu được lợi nhuận tối đa.

Vấn đề bạn đang tìm kiếm: X (- biên tập. MỘT; X 2 - biên tập. B; X 3 - biên tập. TRONG; X 4 - biên tập. G.

Lợi nhuận tối đa:

Những hạn chế:

Để giải bài toán bằng phương pháp đơn hình, ta biến đổi mọi bất đẳng thức thành bất đẳng thức. Để làm điều này, chúng tôi đưa thêm ba biến không âm vào bài toán: X 5 , x 6, x 7 và cộng chúng vào vế trái của bất đẳng thức:

Theo ý nghĩa kinh tế của chúng, các biến số bổ sung không gì khác hơn là thời gian vận hành không được sử dụng của thiết bị cụ thể. Để giải quyết các vấn đề bằng phương pháp đơn hình, các bảng đơn giản đặc biệt sẽ được biên soạn.

Trong hầu hết dòng trên cùng các hệ số của hàm mục tiêu được ghi lại. Các biến bổ sung tương ứng với hệ số bằng 0. Thiết bị không sử dụng không tạo ra lợi nhuận. Các chỉ số 0 tương tự nằm trong cột VỚIđối với mỗi biến bổ sung.

Trong việc điền vào dòng Zj - Cj có những đặc điểm riêng của chúng. Được xem xét Zj cho mỗi cột. Nó được lấy bằng tổng các tích của các giá trị cột VỚI bằng các hệ số cột tương ứng j. Vì trong phiên bản gốc trong cột VỚI là 0 thì giá trị Zj cho tất cả các cột là 0 và giá trị Zj - Cj= -Cj. Do đó, ở phiên bản ban đầu, các hệ số của hàm mục tiêu được đặt ở đây với dấu ngược lại. Tất cả các biến chính được đặt thành 0 và không được đưa vào cơ sở của bài toán của chúng tôi. Các biến bổ sung bằng giá trị giới hạn theo phương trình ban đầu. Điều này có nghĩa là không có gì được sản xuất, không có tài nguyên nào được sử dụng và giá trị của hàm mục tiêu là 0 (không có lợi nhuận).

Giải pháp cho vấn đề bao gồm việc đưa các biến chính vào kế hoạch một cách tuần tự cho đến khi đạt được giải pháp tối ưu. Trong trường hợp này, ở mỗi giai đoạn tính toán, bạn chỉ có thể nhập một biến. Trong trường hợp này, một biến khác sẽ bị loại khỏi cơ sở, vì với ba hạn chế thì không thể có nhiều hơn ba biến trong cơ sở.

Vì vấn đề được giải quyết bằng tối đa lợi nhuận, bạn cần bắt đầu với sản phẩm có lợi nhuận cao nhất. Trong trường hợp của chúng tôi, đây là ed. D. Đưa vào cơ sở x4. Hãy để chúng tôi xác định cách xuất bản ấn phẩm có thể được dự kiến. D. Nó phụ thuộc vào số lượng nguồn lực và tiêu chuẩn chi phí. Thiết bị nhóm I có thể xử lý 3000 mặt hàng. (24.000/8), nhóm II không tham gia sản xuất G, còn nhóm III có thể gia công 30.000 mặt hàng. Chúng tôi chấp nhận giá trị nhỏ nhất trong số các giá trị (3000 ed.), trong bảng ở cột “cơ sở” X 4 đặt vào vị trí X 5 (thiết bị nhóm I bằng 0, vì nó đã được sử dụng hoàn toàn). Số 8 ở ngã tư x A Và X 5 gọi điện yếu tố hướng dẫn hoặc tổng quan, chìa khóa, cho phép.

Đường kẻ X 4 V. bảng mới thu được bằng cách chia chuỗi biến đầu ra X 5 của bảng trước vào phần tử dẫn hướng. Trong cột VỚI 0,8 được nhập - số tiền lãi trên mỗi đơn vị xuất bản. D. Sau đó, cột “kế hoạch” được tính toán lại. Trên thiết bị của nhóm II ed. G không được xử lý và ở phiên bản mới quỹ thời gian của nó không thay đổi (12.000 phút).

Quỹ thời gian của thiết bị nhóm III sẽ giảm đi 3000 phút (1 phút x x 3000 chiếc), do đó còn lại 27.000 phút chưa được sử dụng. Số tiếp theo trong cột "kế hoạch" là 2400 rúp. (0,8 3000) - lợi nhuận ở mức tùy chọn này. Sau cột “kế hoạch”, tất cả các cột còn lại đều được tính toán lại bảng đơn, ngoại trừ chuỗi biến đầu vào. Đồng thời, cần lưu ý rằng trong các cột của tất cả các biến có trong cơ sở, tại giao điểm của các hàng và cột cùng tên luôn có một đơn vị, các phần tử còn lại của cột đều bằng nhau. về không.

Vì vậy, bạn có thể điền ngay vào các cột x4, x6 Và x7. Nên tính toán lại theo “quy tắc tam giác”. Để tính bất kỳ hệ số nào trong phiên bản mới, bạn cần tìm ba số trong bảng đơn: số thay thế cho hệ số này trong phiên bản trước;

  • - một số trong cùng dòng của tùy chọn trước đó, nhưng trong cột của biến đầu vào;
  • - một số trong phiên bản mới trong cùng một cột với hệ số mong muốn, nhưng nằm trong hàng của biến mới nhập (các phần tử của hàng này đã được tính toán trước đó).

Ba số trong bảng tạo thành một tam giác vuông. Để xác định hệ số yêu cầu, cần trừ tích của hai góc còn lại với số nằm ở đỉnh của góc vuông.

Ví dụ: đối với cột.gr

Chúng tôi thực hiện tính toán:

cho hệ số theo dòng

cho hệ số hàng x 7:

Chỉ báo dòng Zj - Cj có thể được tính theo hai cách:

a) theo công thức

b) Theo quy tắc tam giác:

Chúng tôi thực hiện các phép tính tương tự cho các cột khác của phiên bản mới của bảng đơn.

Bây giờ chúng ta cần tìm hiểu xem phương án thứ hai có tối ưu hay có thể cải thiện được hay không. Để làm điều này, hãy nhìn vào dòng Zj - Cj. Nếu nó chứa số âm thì tùy chọn có thể được cải thiện.

Bằng 0,3 chà. trên mỗi đơn vị sản phẩm được giới thiệu, lợi nhuận sẽ tăng lên khi nhập vào số cơ sở! (ed. A) và bằng 0,1 chà. khi giới thiệu số 3 (ed. B). Những số liệu này có vẻ mâu thuẫn với dữ liệu gốc: theo đó ed. Và nó mang lại 0,4 rúp. lợi nhuận, B - 0,5 chà. Nhưng vấn đề là ở chỗ ở giai đoạn này nhiệm vụ, việc đưa các sản phẩm này vào kế hoạch sẽ thay thế một số sản phẩm đã được giới thiệu trước đó. D, để giải phóng thiết bị nhóm I cho sản xuất.


Ở giai đoạn tiếp theo, sẽ thích hợp hơn để giới thiệu X ((ed. A), vì nó tương ứng với giá trị lớn nhất giá trị tuyệt đối một số âm. Tương tự như tùy chọn trước, chúng ta sẽ đặt số lượng ed. Hoặc nó có thể được đưa vào kế hoạch, có tính đến thực tế là nó đã bao gồm việc phát hành một ấn phẩm. D. Để làm điều này, chúng ta chia các số từ cột “kế hoạch” cho các hệ số tương ứng (chỉ dương) từ cột của biến đầu vào X ( và từ các thương số thu được, chúng tôi chọn giá trị nhỏ nhất:

Nó theo sau đó trong tùy chọn mới không quá 4000 ed có thể được đưa vào tính toán. Và, vì yếu tố hạn chế là thiết bị nhóm II. Vì vậy, biến X ( sẽ thay thế biến trong cơ sở thế kỷ x

Tại giao điểm của cột x x và dây x 6 chúng ta tìm và đánh dấu phần tử hướng dẫn - 3. Tiếp theo, chúng ta tính chuỗi của biến đã nhập bằng cách chia các phần tử của chuỗi x 6 của phiên bản trước vào phần tử hướng dẫn. Sau đó, chúng tôi tính toán cột “kế hoạch”:

Lợi nhuận với quyền chọn mới sẽ là:

Theo quy tắc được mô tả, hãy điền vào các cột sau. Nhìn qua dòng Zj - Cj chúng ta thấy rằng nó chỉ chứa các số 0 và các phần tử dương, nghĩa là phương án 3 là giải pháp tối ưu và không thể cải thiện được. Nó chỉ bao gồm hai loại sản phẩm trong số bốn loại. Biến đổi x 3 tương ứng với dòng cuối cùng 0. Điều này có nghĩa là phần giới thiệu kế hoạch ở bước tiếp theo x 3 sẽ không làm tăng lợi nhuận nhưng cũng không làm giảm lợi nhuận và kết quả thu được cũng sẽ tối ưu. Chia các số ở cột “kế hoạch” cho hệ số cột x 3 và chọn mức tối thiểu từ những giá trị thu được, chúng tôi xác định rằng biến này nên được đưa vào cơ sở thay cho biến^. Nhờ những chuyển đổi tiếp theo, chúng tôi có được một kế hoạch tối ưu mới, cung cấp cho việc phát hành 2182 phiên bản. MỘT (X () và 5455 biên tập. B (.g 3). Chúng ta hãy tìm thêm một vài lựa chọn tối ưu giải quyết vấn đề của chúng tôi. Lựa chọn/: 50% từ chương trình đầu tiên và 50% từ chương trình thứ hai:

Phương án II: 80% từ chương trình đầu tiên và 20% từ chương trình thứ hai:

Các tùy chọn này cũng mang lại lợi nhuận 3.600 RUB.

Sự hiện diện của một số kế hoạch có hiệu quả thực tế như nhau giúp xác định được một số phương án trung gian mà trong các vấn đề kinh tế mang lại Tính năng bổ sungđể phân tích và lựa chọn chất lượng nhất trong số đó có thể chấp nhận được.

Khi giải các bài toán bằng phương pháp đơn hình có thể xảy ra trường hợp “thoái hóa”. Tại T hạn chế, một kế hoạch không suy biến luôn chứa T các biến tích cực và phần còn lại p - t biến vấn đề không được bao gồm trong cơ sở và bằng 0. Tuy nhiên, có thể một hoặc nhiều biến có trong cơ sở bằng 0, tức là sự hiện diện của một hoặc nhiều số 0 trong cột “kế hoạch” của bảng đơn. Kế hoạch này được gọi là thoái hóa. Với một kế hoạch thoái hóa, sự hiện diện số âm xếp hàng Zj - Cj không có nghĩa là tùy chọn tiếp theo sẽ làm tăng giá trị của hàm mục tiêu. Nó có thể không thay đổi, không chỉ trong một mà còn trong nhiều bước liên tiếp. Đây là những gì sẽ xảy ra vòng lặp, điều này ngăn cản việc tính toán thêm và chỉ có thể khắc phục được với sự trợ giúp của các kỹ thuật đặc biệt.

Hiện nay, khi giải các bài toán tối ưu chúng được sử dụng rộng rãi. những máy tính cá nhân. Trong trường hợp này, hệ thống được sử dụng bảng tính "Microsoft Excel».

Để giải quyết vấn đề tối ưu hóa trong MS Excel sử dụng tiện ích bổ sung Tìm kiếm giải pháp, được gọi từ mục menu chính “Công cụ”.


Nếu ở phiên bản Excelđược cài đặt trên máy tính của bạn, mục phụ này của menu “Dịch vụ” bị thiếu, bạn cần gọi mục menu “Tiện ích bổ sung” và trong danh sách đề xuất mô-đun bổ sung chọn “Tìm kiếm giải pháp”.

Hãy xem ví dụ về cách sử dụng bổ trợ này, sử dụng nó để giải quyết vấn đề lập kế hoạch sản xuất.

Ví dụ 2.24

Công ty sản xuất các sản phẩm A, B, C, D từ ba loại nguồn lực. Mô hình toán học có lượt xem tiếp theo: kiểm tra/(X) = 7,5i* 1 +3x2+ 6dg 3 + 12.g 4 ( hàm mục tiêu- tổng chi phí phát hành).

Các hạn chế về trữ lượng tài nguyên và tính không âm của các biến như sau:

Hãy tạo một mẫu trong trình chỉnh sửa Excel.


Bây giờ hãy đặt nó vào nhiệm vụ này thông tin số.


Trong các ô trống đã chọn (giá trị của hàm mục tiêu và vế trái của các bất đẳng thức), cần nhập các công thức hiển thị mối liên hệ và mối quan hệ giữa các số trên màn hình.

Tế bào C 4 - F a được gọi vào Excel có thể thay đổi (trong mô hình của chúng tôi đây là những biến chưa biết). Việc tìm kiếm lời giải khi thay đổi chúng sẽ tìm được giá trị tối ưu của hàm mục tiêu. Các giá trị ban đầu được nhập vào các ô này thường là số 0 (các ô không được điền theo mặc định được coi là chứa giá trị 0).

Bây giờ bạn cần nhập công thức. Trong mô hình toán học của chúng ta, hàm mục tiêu là tích của vectơ hệ số và vectơ ẩn. Thật vậy, có thể coi biểu thức

là tích của vectơ (7, 5, 3, b, 12) bởi vectơ (.g, X 2 , tôi-*, xA).

TRONG Excel Có một hàm SUMPRODVEL cho phép bạn tìm tích vô hướng của vectơ. Chức năng này bạn cần gọi ô số 5 và đặt địa chỉ của các ô chứa hệ số của phương trình (trong trường hợp này là C5) làm vectơ cần nhân: F5) và các ô mà các giá trị sẽ được đặt vào đó là kết quả của giải pháp x và x 2, x 3, x 4(tế bào SA : FA).


Mỗi vế trái của ràng buộc cũng là tích của hai vectơ: hàng tương ứng của ma trận chi phí và một vectơ ẩn số. Sự biểu lộ 2x + x 2+ 0Dg 3 + 4x l(đối với ràng buộc đầu tiên 2x, + x 2 + 0,5x 3 + 4 x 4 2400) sẽ được coi là tích của vectơ hệ số (2,1,0,5,4) và vectơ biến (x và x 2, x 3, x 4).

Trong ô dành riêng cho công thức vế trái của ràng buộc thứ nhất ((79), ta gọi hàm SUMPRODVEL. Là địa chỉ của các vectơ nhân ta nhập địa chỉ của hàng hệ số C9: /0 và địa chỉ của các giá trị của biến C4: F.A.


Trong bốn ô còn lại của cột " Bên trái"Chúng tôi nhập các công thức tương tự bằng cách sử dụng hàng tương ứng của ma trận chi phí. Một mảnh màn hình với các công thức đã nhập trông như thế này.


Vào thời điểm dịch vụ “Tìm kiếm giải pháp” được gọi, các công thức cho vế trái của các ràng buộc và công thức cho giá trị của hàm mục tiêu phải được nhập vào màn hình có bài toán.

Trong menu “Dịch vụ”, chọn “Tìm kiếm giải pháp”. Trong cửa sổ xuất hiện, nhập thông tin sau:

  • a) đặt địa chỉ ô cho giá trị hàm mục tiêu #5 làm ô mục tiêu;
  • b) đặt “hộp kiểm” thành tùy chọn “giá trị tối đa”, vì trong trường hợp này hàm mục tiêu của thu nhập có thể tối đa hóa;
  • c) như tế bào có thể thay đổi nhập địa chỉ dòng giá trị của biến C4: F4;
  • d) ở bên phải cửa sổ dành cho việc nhập các hạn chế, hãy nhấp vào nút “Thêm”, một biểu mẫu để nhập các hạn chế sẽ xuất hiện;

e) ở phần bên trái của biểu mẫu “Liên kết ô”, nhập địa chỉ của công thức cho phần bên trái của ràng buộc đầu tiên G 9, dấu bất đẳng thức cần thiết được chọn (trong trường hợp của chúng tôi,

f) tất cả các ràng buộc của nhiệm vụ được nhập theo cùng một cách, sau đó nhấn nút “OK”.

Cửa sổ “Tìm kiếm giải pháp” với thông tin đã nhập trông như thế này.


Tiếp theo, bạn cần nhấp vào nút “Tùy chọn”, đánh dấu vào “hộp kiểm” mô hình tuyến tính" và "Giá trị không âm", vì trong trường hợp này vấn đề liên quan đến quy hoạch tuyến tính và ràng buộc yêu cầu các giá trị không âm.


Sau đó nhấp vào “OK”, “Run”, sau đó cửa sổ kết quả giải pháp sẽ xuất hiện.


Nếu, do tất cả các hành động, bạn nhận được một cửa sổ có thông báo "Đã tìm thấy giải pháp", thì bạn sẽ có cơ hội nhận được ba loại báo cáo, rất hữu ích khi phân tích độ nhạy của mô hình. TRONG trong ví dụ này Chỉ cần lưu giải pháp được tìm thấy bằng cách nhấp vào “OK”. Kết quả là, một giải pháp cho vấn đề đã thu được.


Nếu trong quá trình giải quyết vấn đề, một cửa sổ xuất hiện với thông báo về việc không thể tìm ra giải pháp, điều này có nghĩa là đã xảy ra lỗi trong quá trình xây dựng vấn đề (các công thức cho các ràng buộc không được điền vào, "cờ" , tối đa hóa (tối thiểu hóa), v.v. không được đặt chính xác).


Trong cửa sổ “Tìm kiếm giải pháp” có nút “Tùy chọn”.


Chọn hộp kiểm “Hiển thị kết quả lặp lại” và nhấp vào “OK”.


Sau đó nhấp vào nút “Chạy”.


MS Excel sẽ hiển thị cửa sổ sau.


Bảng tính sẽ hiển thị kết quả của lần lặp đầu tiên.


Sau đó, nhấp vào nút “Tiếp tục”, kết quả của lần lặp thứ hai sẽ được hiển thị trên bảng tính.


Nhấp lại vào nút “Tiếp tục” và bảng tính sẽ hiển thị kết quả của lần lặp thứ ba.


Lần tiếp theo bạn nhấp vào nút “Tiếp tục”, chương trình sẽ hiển thị cửa sổ “Kết quả tìm kiếm giải pháp”, nơi bạn cần lưu giải pháp tìm thấy và chọn loại báo cáo.


TRONG phần này dạng chung để giải các bài toán tối ưu hóa trong Excel. Tùy theo mô hình kinh tế mà có những điều chỉnh phù hợp.

Các báo cáo trông như thế này.

1. Báo cáo kết quả.


2. Báo cáo bền vững.


3. Báo cáo các hạn mức.


Bây giờ hãy xem xét một ví dụ trong đó mô hình toán học có cùng dạng nhưng các ràng buộc có dấu khác nhau.

Ví dụ 2.25

L. Giả sử mô hình toán học như sau: Nó có các hạn chế sau:


Báo cáo phát triển bền vững.


B. Bây giờ giả sử rằng mô hình toán học có những hạn chế khác:

Trong trường hợp này, chúng tôi có kết quả sau từ các báo cáo.


Báo cáo phát triển bền vững.


  • Để giải quyết vấn đề tương tự, chúng ta sẽ sử dụng một trong các phương pháp quy hoạch tuyến tính - đồ họa. Ví dụ 2.22 Ta đưa ra ký hiệu sau: x( - số lượng cửa DV yêu cầu, x2 - số lượng cửa ICE yêu cầu.

Nếu một bài toán quy hoạch tuyến tính chỉ có hai biến thì có thể giải được phương pháp đồ họa.

Xét bài toán quy hoạch tuyến tính với hai biến và:
(1.1) ;
(1.2)
Ở đây có những con số tùy ý. Nhiệm vụ có thể là tìm mức tối đa (tối đa) hoặc tìm mức tối thiểu (tối thiểu). Hệ thống hạn chế có thể chứa cả biển báo và biển báo.

Xây dựng miền giải pháp khả thi

Phương pháp đồ họa để giải bài toán (1) như sau.
Đầu tiên chúng ta vẽ các trục tọa độ và chọn tỷ lệ. Mỗi bất đẳng thức của hệ ràng buộc (1.2) xác định một nửa mặt phẳng giới hạn bởi đường thẳng tương ứng.

Vậy bất đẳng thức thứ nhất
(1.2.1)
định nghĩa một nửa mặt phẳng giới hạn bởi một đường thẳng. Ở một bên của đường thẳng này và ở phía bên kia. Trên đường thẳng nhất. Để tìm ra bất đẳng thức (1.2.1) về phía nào đúng, chúng ta chọn một điểm tùy ý không nằm trên đường thẳng. Tiếp theo ta thay tọa độ của điểm này vào (1.2.1). Nếu bất đẳng thức đúng thì nửa mặt phẳng chứa điểm đã chọn. Nếu bất đẳng thức không đúng thì nửa mặt phẳng nằm ở phía bên kia (không chứa điểm đã chọn). Tô màu nửa mặt phẳng chứa bất đẳng thức (1.2.1).

Ta làm tương tự đối với các bất đẳng thức còn lại của hệ (1.2). Bằng cách này, chúng ta có được nửa mặt phẳng được tô bóng. Các điểm thuộc miền nghiệm thỏa mãn mọi bất đẳng thức (1.2). Do đó, về mặt đồ họa, vùng các lời giải khả thi (ADA) là giao điểm của tất cả các nửa mặt phẳng được xây dựng. Tạo bóng cho ODR. Nó là một đa giác lồi có các mặt thuộc các đường thẳng dựng sẵn. Ngoài ra, ODF có thể là một hình lồi không giới hạn, một đoạn, một tia hoặc một đường thẳng.

Trường hợp cũng có thể xảy ra là các nửa mặt phẳng không chứa các điểm chung. Khi đó miền của các lời giải khả thi là tập rỗng. Vấn đề này không có giải pháp.

Phương pháp này có thể được đơn giản hóa. Bạn không cần phải tô bóng từng nửa mặt phẳng mà trước tiên hãy dựng tất cả các đường thẳng
(2)
Tiếp theo, chọn một điểm tùy ý không thuộc bất kỳ đường nào trong số này. Thay tọa độ của điểm này vào hệ bất đẳng thức (1.2). Nếu mọi bất đẳng thức đều được thỏa mãn thì vùng nghiệm khả thi được giới hạn bởi các đường thẳng dựng sẵn và bao gồm điểm đã chọn. Chúng tôi tô bóng vùng các giải pháp khả thi dọc theo ranh giới của các đường sao cho nó bao gồm điểm đã chọn.

Nếu có ít nhất một bất đẳng thức không được thỏa mãn thì chọn điểm khác. Và cứ như vậy cho đến khi tìm được điểm có tọa độ thỏa mãn hệ (1.2).

Tìm cực trị của hàm mục tiêu

Vì vậy, chúng ta có một vùng bóng mờ gồm các giải pháp khả thi (ADA). Nó được giới hạn bởi một đường đứt đoạn gồm các đoạn và các tia thuộc đường thẳng dựng nên (2). ODS luôn là một tập lồi. Nó có thể là một tập bị chặn hoặc không bị chặn theo một số hướng.

Bây giờ chúng ta có thể tìm cực trị của hàm mục tiêu
(1.1) .

Để làm điều này, hãy chọn bất kỳ số nào và xây dựng một đường thẳng
(3) .
Để thuận tiện cho việc trình bày thêm, chúng ta giả sử rằng đường thẳng này đi qua ODR. Trên dòng này, hàm mục tiêu không đổi và bằng . một đường thẳng như vậy được gọi là đường mức hàm. Đường thẳng này chia mặt phẳng thành hai nửa mặt phẳng. Trên một nửa mặt phẳng
.
Trên một nửa mặt phẳng khác
.
Nghĩa là, về một phía của đường thẳng (3) hàm mục tiêu tăng. Và chúng ta càng di chuyển điểm ra xa đường thẳng (3) thì giá trị sẽ càng lớn. Bên kia đường thẳng (3), hàm mục tiêu giảm. Và chúng ta càng di chuyển điểm từ đường thẳng (3) sang phía bên kia thì giá trị sẽ càng nhỏ. Nếu vẽ một đường thẳng song song với đường thẳng (3) thì đường thẳng mới cũng sẽ là đường đồng mức của hàm mục tiêu nhưng có giá trị khác.

Như vậy, để tìm giá trị lớn nhất của hàm mục tiêu, cần vẽ một đường thẳng song song với đường thẳng (3), càng xa đường thẳng đó càng tốt theo hướng tăng dần giá trị và đi qua ít nhất một điểm. của ODD. Để tìm giá trị nhỏ nhất của hàm mục tiêu, cần vẽ một đường thẳng song song với đường thẳng (3) và càng xa nó càng tốt theo hướng giá trị giảm dần và đi qua ít nhất một điểm của ODD.

Nếu ODR không giới hạn thì có thể xảy ra trường hợp không thể vẽ được đường thẳng như vậy. Nghĩa là, dù chúng ta loại bỏ đường thẳng ra khỏi đường mức (3) theo hướng tăng (giảm) như thế nào thì đường thẳng đó sẽ luôn đi qua ODR. Trong trường hợp này nó có thể lớn (nhỏ) tùy ý. Do đó, không có giá trị tối đa (tối thiểu). Vấn đề không có giải pháp.

Chúng ta hãy xem xét trường hợp khi đường cực trị song song với một đường thẳng tùy ý có dạng (3) đi qua một đỉnh của đa giác ODR. Từ đồ thị chúng ta xác định tọa độ của đỉnh này. Khi đó giá trị lớn nhất (tối thiểu) của hàm mục tiêu được xác định theo công thức:
.
Giải pháp cho vấn đề là
.

Cũng có thể có trường hợp đường thẳng song song với một trong các mặt của ODR. Khi đó đường thẳng đi qua hai đỉnh của đa giác ODR. Chúng tôi xác định tọa độ của các đỉnh này. Để xác định giá trị tối đa (tối thiểu) của hàm mục tiêu, bạn có thể sử dụng tọa độ của bất kỳ đỉnh nào sau đây:
.
Bài toán có vô số cách giải. Giải pháp là bất kỳ điểm nào nằm trên đoạn giữa các điểm và , bao gồm các điểm và chính chúng.

Ví dụ giải bài toán quy hoạch tuyến tính bằng phương pháp đồ họa

Nhiệm vụ

Công ty sản xuất váy có hai mẫu A và B. Sử dụng ba loại vải. Để may một chiếc váy kiểu A cần 2 m vải loại thứ nhất, 1 m vải loại thứ hai, 2 m vải loại thứ ba. Để may một chiếc váy kiểu B cần 3 m vải loại thứ nhất, 1 m vải loại thứ hai, 2 m vải loại thứ ba. Kho vải loại thứ nhất là 21 m, loại thứ hai - 10 m, loại thứ ba - 16 m, việc tung ra một sản phẩm loại A mang lại thu nhập 400 den. đơn vị, một loại sản phẩm B - 300 den. các đơn vị

Lập kế hoạch sản xuất mang lại thu nhập lớn nhất cho công ty. Giải quyết vấn đề bằng đồ họa.

Giải pháp

Đặt các biến và biểu thị số lượng váy được sản xuất, mẫu A và B tương ứng. Khi đó số vải loại thứ nhất tiêu thụ sẽ là:
(m)
Số vải loại thứ 2 tiêu thụ sẽ là:
(m)
Số vải loại thứ 3 tiêu thụ sẽ là:
(m)
Vì số lượng váy sản xuất ra không thể âm nên
Và .
Thu nhập từ việc sản xuất trang phục sẽ là:
(den. đơn vị)

Khi đó mô hình toán kinh tế của bài toán có dạng:


Chúng tôi giải quyết nó bằng đồ họa.
Chúng ta vẽ các trục tọa độ và .

Chúng tôi đang xây dựng một đường thẳng.
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (0; 7) và (10,5; 0).

Chúng tôi đang xây dựng một đường thẳng.
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (0; 10) và (10; 0).

Chúng tôi đang xây dựng một đường thẳng.
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (0; 8) và (8; 0).



Chúng ta tô bóng khu vực sao cho điểm (2; 2) rơi vào phần bóng mờ. Ta được tứ giác OABC.


(A1.1) .
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (0; 4) và (3; 0).

Chúng tôi lưu ý thêm rằng vì các hệ số của hàm mục tiêu là dương (400 và 300), nên nó tăng dần và tăng. Chúng ta vẽ một đường thẳng song song với đường thẳng (A1.1), càng xa nó càng tốt theo hướng tăng dần và đi qua ít nhất một điểm của tứ giác OABC. Một đường thẳng như vậy đi qua điểm C. Từ công trình, chúng ta xác định tọa độ của nó.
.

Giải pháp của vấn đề: ;

Trả lời

.
Tức là để nhận thu nhập cao nhất, cần sản xuất 8 chiếc váy kiểu A. Thu nhập sẽ là 3200 den. các đơn vị

Ví dụ 2

Nhiệm vụ

Giải bài toán quy hoạch tuyến tính bằng đồ thị.

Giải pháp

Chúng tôi giải quyết nó bằng đồ họa.
Chúng ta vẽ các trục tọa độ và .

Chúng tôi đang xây dựng một đường thẳng.
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (0; 6) và (6; 0).

Chúng tôi đang xây dựng một đường thẳng.
Từ đây.
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (3; 0) và (7; 2).

Chúng tôi đang xây dựng một đường thẳng.
Chúng tôi xây dựng một đường thẳng (trục abscissa).

Vùng giải pháp chấp nhận được (ADA) bị giới hạn bởi các đường thẳng được xây dựng. Để tìm ra bên nào, chúng ta nhận thấy rằng điểm thuộc về ODR, vì nó thỏa mãn hệ bất đẳng thức:

Chúng ta tô bóng khu vực dọc theo ranh giới của các đường đã xây dựng sao cho điểm (4; 1) rơi vào phần được tô bóng. Ta được tam giác ABC.

Chúng tôi đang xây dựng bất kỳ dòng nào mức độ của hàm mục tiêu, ví dụ,
.
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (0; 6) và (4; 0).
Vì hàm mục tiêu tăng khi tăng và , chúng ta vẽ một đường thẳng, song song với đường thẳng mức và khoảng cách lớn nhất tới nó theo hướng tăng dần và đi qua ít nhất một điểm của tam giác ABC. Một đường thẳng như vậy đi qua điểm C. Từ công trình, chúng ta xác định tọa độ của nó.
.

Giải pháp của vấn đề: ;

Trả lời

Ví dụ về không có giải pháp

Nhiệm vụ

Giải bài toán quy hoạch tuyến tính bằng đồ thị. Tìm giá trị lớn nhất và nhỏ nhất của hàm mục tiêu.

Giải pháp

Chúng tôi giải quyết vấn đề bằng đồ họa.
Chúng ta vẽ các trục tọa độ và .

Chúng tôi đang xây dựng một đường thẳng.
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (0; 8) và (2.667; 0).

Chúng tôi đang xây dựng một đường thẳng.
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (0; 3) và (6; 0).

Chúng tôi đang xây dựng một đường thẳng.
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (3; 0) và (6; 3).

Các đường thẳng là trục tọa độ.

Vùng nghiệm chấp nhận được (ADA) bị giới hạn bởi các đường thẳng dựng sẵn và các trục tọa độ. Để tìm ra bên nào, chúng ta nhận thấy rằng điểm thuộc về ODR, vì nó thỏa mãn hệ bất đẳng thức:

Chúng ta tô bóng khu vực sao cho điểm (3; 3) rơi vào phần bóng mờ. Chúng ta có được một vùng không giới hạn được giới hạn bởi đường đứt nét ABCDE.

Chúng ta xây dựng một đường tùy ý về mức của hàm mục tiêu, ví dụ:
(A3.1) .
Tại .
Tại .
Vẽ đường thẳng đi qua các điểm (0; 7) và (7; 0).
Vì các hệ số của và là dương nên nó tăng khi tăng và .

Để tìm mức tối đa, bạn cần vẽ một đường thẳng song song càng xa càng tốt theo hướng tăng dần và đi qua ít nhất một điểm của vùng ABCDE. Tuy nhiên, vì diện tích là không giới hạn từ phía giá trị lớn và , thì không thể vẽ được đường thẳng như vậy. Cho dù chúng ta vẽ đường nào đi chăng nữa, sẽ luôn có những điểm trong vùng ở xa hơn theo hướng tăng dần và . Vì vậy không có mức tối đa. bạn có thể làm cho nó lớn như bạn muốn.

Chúng tôi đang tìm kiếm mức tối thiểu. Chúng ta vẽ một đường thẳng song song với đường thẳng (A3.1) và càng xa nó càng tốt theo hướng giảm dần và đi qua ít nhất một điểm của vùng ABCDE. Một đường thẳng như vậy đi qua điểm C. Từ công trình, chúng ta xác định tọa độ của nó.
.
Giá trị tối thiểu hàm mục tiêu:

Trả lời

Không có giá trị tối đa.
Giá trị tối thiểu
.

Lập trình tuyến tính là một nhánh của toán học nghiên cứu các 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 các biến và tiêu chí tối ưu tuyến tính.

Một vài lời về thuật ngữ lập trình tuyến tính. Anh ấy yêu cầu hiểu đúng. Trong trường hợp này, lập trình tất nhiên không phải là việc biên soạn các chương trình máy tính. Lập kế hoạch ở đây nên được hiểu là lập kế hoạch, lập kế hoạch, xây dựng chương trình hành động.

ĐẾN Bài toán Quy hoạch tuyến tính bao gồm các nghiên cứu về các tình huống sản xuất và kinh tế cụ thể, dưới hình thức này hay hình thức khác được hiểu là các vấn đề về sử dụng tối ưu nguồn tài nguyên giới hạn.

Phạm vi các bài toán được giải bằng phương pháp quy hoạch tuyến tính khá rộng. Đây là ví dụ:

· Vấn đề sử dụng tối ưu nguồn lực trong lập kế hoạch sản xuất;

· vấn đề hỗn hợp (lập kế hoạch thành phần sản phẩm);

· vấn đề tìm kiếm sự kết hợp tối ưu nhiều loại khác nhau sản phẩm để lưu trữ trong kho (quản lý hàng tồn kho hoặc “vấn đề về chiếc ba lô”);

· Nhiệm vụ vận chuyển (phân tích vị trí doanh nghiệp, di chuyển hàng hóa).

Lập trình tuyến tính là phần được phát triển và sử dụng rộng rãi nhất của lập trình toán học (ngoài ra, phần này bao gồm: số nguyên, động, phi tuyến, lập trình tham số). Điều này được giải thích như sau:

· mô hình toán học số lượng lớn các vấn đề kinh tế là tuyến tính đối với các biến số cần thiết;

· loại này vấn đề được nghiên cứu nhiều nhất hiện nay. Các phương pháp đặc biệt đã được phát triển cho nó để giải quyết những vấn đề này và các chương trình máy tính tương ứng;

· Nhiều bài toán quy hoạch tuyến tính đã được giải và có ứng dụng rộng rãi;

· một số vấn đề không tuyến tính trong công thức ban đầu, sau một loạt các hạn chế bổ sung và các giả định có thể trở thành tuyến tính hoặc có thể được rút gọn thành dạng mà chúng có thể được giải bằng các phương pháp quy hoạch tuyến tính.

Mô hình kinh tế và toán học của bất kỳ bài toán quy hoạch tuyến tính nào bao gồm: hàm mục tiêu, giá trị tối ưu của hàm này (cực đại hoặc cực tiểu) phải được tìm thấy; các hạn chế dưới dạng hệ phương trình tuyến tính hoặc hệ bất đẳng thức; yêu cầu tính không âm của các biến.

Nói chung, mô hình được viết như sau:

hàm mục tiêu:

F = c1x1 + c2x2 + ... + cnxn → max(min);

những hạn chế:

a11x1 + a12x2 + ... + a1nxn (≤ = ≥) b1,

a21x1 + a22x2 + ... + a2nxn (≤ = ≥) b2,

am1x1 + am2x2 + ... + amnxn (≤ = ≥) bm;

yêu cầu không âm:

Nhiệm vụ là tìm giá trị tối ưu các chức năng bị hạn chế.

Vì thế, Lập trình tuyến tính là một nhánh của lập trình toán học nghiên cứu các 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 và tiêu chí tuyến tính.

Điều kiện cần để đặt ra bài toán quy hoạch tuyến tính là những hạn chế về nguồn lực sẵn có, lượng cầu, năng lực sản xuất của doanh nghiệp và các yếu tố sản xuất khác.

Bản chất của quy hoạch tuyến tính là tìm các điểm có giá trị lớn nhất hoặc nhỏ nhất của một hàm nào đó tại một bộ nhất định các hạn chế áp đặt lên các lập luận và hình thành một hệ thống các hạn chế, theo quy luật, có vô số giải pháp. Mỗi tập giá trị của các biến (đối số của hàm F) thỏa mãn hệ ràng buộc được gọi là phương án chấp nhận được của bài toán quy hoạch tuyến tính. Hàm F, được xác định cực đại hoặc cực tiểu, được gọi là hàm mục tiêu của bài toán. Một phương án chấp nhận được mà tại đó đạt được cực đại hoặc cực tiểu của hàm F được gọi là phương án tối ưu của bài toán.

Hệ thống hạn chế quyết định nhiều kế hoạch được quyết định bởi các điều kiện sản xuất. Nhiệm vụ của lập trình tuyến tính (LP) là chọn ra phương án có lợi nhất (tối ưu) từ một tập hợp các phương án khả thi.

Phương pháp đơn giản là cái chính trong lập trình tuyến tính . Việc giải bài toán bắt đầu bằng việc xét một trong các đỉnh của khối đa diện có điều kiện. Nếu đỉnh đang nghiên cứu không tương ứng với đỉnh cực đại (tối thiểu), thì chúng sẽ chuyển sang đỉnh lân cận, tăng giá trị của hàm mục tiêu khi giải bài toán cực đại và giảm nó khi giải bài toán cực tiểu. Do đó, việc di chuyển từ đỉnh này sang đỉnh khác sẽ cải thiện giá trị của hàm mục tiêu. Vì số đỉnh của khối đa diện là có hạn nên trong một số bước hữu hạn, người ta đảm bảo tìm được giá trị tối ưu hoặc chứng minh được thực tế là bài toán không thể giải được.

Phương pháp này rất phổ biến, có thể áp dụng cho mọi bài toán quy hoạch tuyến tính trong hình thức kinh điển . Hệ ràng buộc ở đây là hệ phương trình tuyến tính trong đó số ẩn số số lượng nhiều hơn phương trình. Nếu cấp bậc của hệ thống là r , thì chúng ta có thể chọn r những ẩn số mà chúng ta sẽ thể hiện thông qua những ẩn số còn lại. Để xác định, chúng ta giả sử rằng các ẩn số liên tiếp đầu tiên được chọn X 1 , X 2 , ..., Xr . Khi đó hệ phương trình của chúng ta có thể được viết là

Nó có thể được đưa đến hình thức này bất kỳ hệ thống chung , ví dụ, bằng phương pháp Gaussian. Đúng, không phải lúc nào cũng có thể biểu diễn nó theo r ẩn đầu tiên còn lại (chúng tôi đã làm điều này để xác định ký hiệu). Tuy nhiên, như vậy r chắc chắn sẽ có những điều chưa biết. Những ẩn số (biến) này được gọi là cơ bản, còn lại là miễn phí.

Cho giá trị nhất định các biến tự do và tính giá trị của các biến cơ bản (được biểu thị bằng các biến tự do), chúng ta sẽ thu được giải pháp khác nhau hệ thống hạn chế của chúng tôi. Vì vậy, bất kỳ giải pháp có thể đạt được. Chúng ta sẽ quan tâm đến các nghiệm đặc biệt thu được trong trường hợp các biến tự do bằng 0. Những giải pháp như vậy được gọi là nền tảng, có rất nhiều trong số chúng cũng như có nhiều loại cơ bản khác nhau của một hệ thống hạn chế nhất định. Giải pháp cơ bản được gọi là giải pháp cơ bản được chấp nhận hoặc giải pháp tham khảo, nếu giá trị của các biến trong đó không âm. Nếu các biến được lấy làm cơ bản X 1 , X 2 , ..., Xr , thì giải pháp (b 1 , b 2 ,..., b r , 0, ..., 0) sẽ hỗ trợ với điều kiện là b 1 , b 2 ,..., b r ≥ 0 .

Phương pháp đơn hình dựa trên một định lý gọi là định lý cơ bản của phương pháp đơn hình. Trong số các phương án tối ưu của bài toán quy hoạch tuyến tính ở dạng chính tắc nhất thiết phải có một nghiệm tham chiếu cho hệ ràng buộc của nó. Nếu phương án tối ưu của bài toán là duy nhất thì nó trùng với một giải pháp tham chiếu nào đó. Có một số lượng hữu hạn các giải pháp hỗ trợ khác nhau cho hệ thống các ràng buộc. Do đó, có thể tìm ra giải pháp cho vấn đề ở dạng chính tắc bằng cách liệt kê các giải pháp tham chiếu và chọn trong số đó một giải pháp có giá trị F lớn nhất. Nhưng thứ nhất, tất cả các lời giải tham khảo đều chưa được biết và cần phải được tìm ra, thứ hai, trong các bài toán thực tế có rất nhiều lời giải như vậy và việc tìm kiếm trực tiếp là khó thực hiện được. Phương pháp đơn giản là một thủ tục nhất định để liệt kê trực tiếp các giải pháp hỗ trợ. Dựa trên một giải pháp tham chiếu nhất định được tìm thấy trước bằng thuật toán nhất định của phương pháp đơn hình, chúng tôi tính toán một giải pháp tham chiếu mới mà giá trị của hàm mục tiêu F không kém gì cái cũ. Sau một loạt các bước, chúng tôi đi đến một giải pháp tham khảo, đó là phương án tối ưu.

Vì vậy, phương pháp đơn giản đưa ra Thứ tự nhất định cả khi tìm giải pháp cơ bản (ban đầu) đầu tiên và khi chuyển sang các giải pháp cơ bản khác. Ý tưởng của anh ấy như sau.

Đang có hệ thống hạn chế , giảm xuống Nhìn tổng thể, nghĩa là đối với một hệ gồm m phương trình tuyến tính với N biến (m< n) , tìm thấy bất kỳ giải pháp cơ bản hệ thống này, chỉ quan tâm đến việc tìm ra nó một cách đơn giản nhất có thể.

Nếu giải pháp cơ bản đầu tiên được tìm thấy hóa ra là chấp nhận được , sau đó kiểm tra xem nó có sự tối ưu. Nếu nó không tối ưu , sau đó việc chuyển đổi sang cái khác được thực hiện, nhất thiết giải pháp cơ bản được chấp nhận .

Phương pháp đơn giản đảm bảo rằng với giải pháp mới này dạng tuyến tính, ngay cả khi nó không đạt đến mức tối ưu, nó sẽ tiếp cận nó. Họ làm tương tự với giải pháp cơ sở khả thi mới cho đến khi tìm được giải pháp tối ưu.

Nếu giải pháp cơ bản đầu tiên được tìm thấy hóa ra là không thể chấp nhận được , khi đó sử dụng phương pháp đơn hình có thể chuyển sang các giải pháp cơ bản khác, đưa chúng ta đến gần hơn với khu vực của các giải pháp có thể chấp nhận được, cho đến khi ở một bước quyết định nào đó, giải pháp cơ bản trở nên có thể chấp nhận được và thuật toán phương pháp đơn giản được áp dụng cho nó hoặc chúng ta bị thuyết phục về sự không nhất quán của hệ thống các hạn chế.

Vì vậy, việc áp dụng phương pháp đơn hình được chia thành hai giai đoạn: tìm giải pháp cơ bản có thể chấp nhận được cho hệ thống các ràng buộc hoặc xác định thực tế về tính không tương thích của nó; tìm ra giải pháp tối ưu.
Hơn nữa, mỗi giai đoạn có thể bao gồm một số bước tương ứng với một hoặc một giải pháp cơ bản khác. Nhưng kể từ khi số giải pháp cơ bản luôn bị giới hạn thì số bước của phương pháp đơn hình cũng bị giới hạn.

Sơ đồ đã cho của phương pháp đơn hình thể hiện rõ ràng bản chất thuật toán của nó (bản chất của một hướng dẫn rõ ràng về việc thực hiện các hoạt động tuần tự), giúp lập trình và thực hiện thành công phương pháp này trên máy tính. Các bài toán có số lượng biến và ràng buộc nhỏ có thể được giải thủ công bằng phương pháp đơn hình.

Không đi sâu vào chi tiết hơn về bản chất của thuật toán, chúng tôi sẽ mô tả khía cạnh tính toán của nó. Tính toán bằng phương pháp đơn hình được tổ chức dưới dạng bảng đơn giản, là cách biểu diễn ngắn gọn của bài toán quy hoạch tuyến tính ở dạng chính tắc. Trước khi biên dịch bảng đơn giản nhiệm vụ nên là chuyển đổi , hệ thống hạn chế giảm xuống hình thức cơ bản chấp nhận được, với sự trợ giúp của các biến cơ bản nào phải được loại trừ khỏi hàm mục tiêu. Chúng ta sẽ xem xét vấn đề của những biến đổi sơ bộ này dưới đây. Bây giờ chúng ta sẽ giả định rằng chúng đã được hoàn thành và nhiệm vụ có dạng sau.

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 hàm mục tiêu và hàm ràng buộc là 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 việc 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 phương án tối ưu vận chuyển hàng hoá ( vấn đề vận chuyển); 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.