Giải bài toán bằng phương pháp đơn hình có lời giải chi tiết. Mục đích của nhiệm vụ sản xuất
. Thuật toán phương pháp đơn giản
Ví dụ 5.1. Giải quyết vấn đề sau lập trình tuyến tính phương pháp đơn giản:
Giải pháp:
TÔI lặp lại:
x3, x4, x5, x6 x1,x2. Hãy biểu diễn các biến cơ bản theo các biến tự do:
Hãy cung cấp cho hàm mục tiêuĐẾN lượt xem tiếp theo:
Dựa vào bài toán thu được, ta sẽ lập bảng đơn ban đầu:
Bảng 5.3
Bảng đơn giản ban đầu
Mối quan hệ đánh giá |
||||
Theo định nghĩa của nghiệm cơ bản, các biến tự do bằng 0 và giá trị của các biến cơ bản bằng giá trị tương ứng của các số tự do, tức là:
Giai đoạn 3: kiểm tra tính tương thích của hệ thống hạn chế PAP.
Ở lần lặp này (trong Bảng 5.3), không xác định được dấu hiệu mâu thuẫn của hệ ràng buộc (dấu 1) (tức là không có dòng nào có số tự do âm (ngoại trừ dòng của hàm mục tiêu) mà sẽ không có có ít nhất một phần tử âm (tức là hệ số âm cho một biến tự do)).
Ở lần lặp này (trong Bảng 5.3), không xác định được dấu vô biên của hàm mục tiêu (dấu 2) (tức là không có cột nào chứa phần tử âm trong hàng của hàm mục tiêu (trừ cột số tự do). ) trong đó sẽ không có ít nhất một phần tử dương) .
Kể từ khi những gì được tìm thấy giải pháp cơ bản không chứa thành phần âm thì chấp nhận được.
Giai đoạn 6: Kiểm tra tính tối ưu
Lời giải cơ bản tìm được là không tối ưu, vì theo tiêu chí tối ưu (dấu 4) không được có phần tử âm nào trên dòng của hàm mục tiêu (số tự do của dòng này không được tính đến khi xem xét tiêu chí này). Do đó, theo thuật toán của phương pháp đơn hình, chúng ta chuyển sang giai đoạn 8.
Vì nghiệm cơ bản tìm được có thể chấp nhận được nên chúng tôi sẽ tìm kiếm cột giải theo sơ đồ sau: chúng tôi xác định các cột có phần tử âm trong hàng của hàm mục tiêu (ngoại trừ cột số tự do). Theo Bảng 5.3 có 2 cột như vậy là cột “ x1" và cột " x2" Từ các cột như vậy, cột chứa phần tử nhỏ nhất trong hàng của hàm đích sẽ được chọn. Cô ấy sẽ là người cho phép. Cột " x2" chứa phần tử nhỏ nhất (–3) so với cột " x1
Để xác định đường phân giải, chúng ta tìm tỷ lệ ước tính dương của các số tự do với các phần tử của cột phân giải; đường tương ứng với tỷ lệ đánh giá dương nhỏ nhất được chấp nhận là đã giải.
Bảng 5.4
Bảng đơn giản ban đầu
Trong Bảng 5.4, mối quan hệ đánh giá tích cực nhỏ nhất tương ứng với đường “ x5", do đó, nó sẽ được cho phép.
Phần tử nằm ở giao điểm của cột kích hoạt và hàng kích hoạt được chấp nhận là kích hoạt. Trong ví dụ của chúng tôi, đây là phần tử nằm ở giao điểm của đường “ x5" và các cột " x2».
Phần tử phân giải hiển thị một cơ sở và một biến tự do phải được hoán đổi trong bảng đơn để chuyển sang giải pháp cơ sở “cải tiến” mới. TRONG trong trường hợp nàyđây là những biến x5 Và x2, trong bảng đơn giản mới (Bảng 5.5) chúng ta hoán đổi chúng.
9.1. Sự biến đổi của phần tử phân giải.
Phần tử độ phân giải của Bảng 5.4 được chuyển đổi như sau:
Chúng ta nhập kết quả thu được vào một ô tương tự trong Bảng 5.5.
9.2. Chuyển đổi chuỗi độ phân giải.
Ta chia các phần tử của hàng phân giải của bảng 5.4 cho phần tử phân giải của bảng đơn này, kết quả khớp vào các ô tương tự của bảng đơn giản mới (bảng 5.5). Các phép biến đổi của các phần tử chuỗi phân giải được cho trong Bảng 5.5.
9.3. Chuyển đổi cột độ phân giải.
Ta chia các phần tử của cột độ phân giải của Bảng 5.4 cho phần tử độ phân giải của bảng đơn này và kết quả lấy dấu ngược lại. Kết quả thu được khớp với các ô tương tự của bảng đơn giản mới (Bảng 5.5). Biến đổi các phần tử của cột độ phân giải được cho trong bảng 5.5.
9.4. Chuyển đổi các phần tử còn lại của bảng đơn.
Việc chuyển đổi các phần tử còn lại của bảng đơn (tức là các phần tử không nằm trong hàng phân giải và cột phân giải) được thực hiện theo quy tắc “hình chữ nhật”.
Ví dụ: hãy xem xét việc chuyển đổi một phần tử nằm ở giao điểm của dòng " x3" và các cột "", chúng tôi sẽ biểu thị nó một cách có điều kiện " x3" Trong Bảng 5.4, chúng ta tưởng tượng vẽ một hình chữ nhật, một đỉnh của nó nằm trong ô có giá trị mà chúng ta đang chuyển đổi (tức là trong ô “ x3") và đỉnh còn lại (đỉnh chéo) nằm trong ô có phần tử phân giải. Hai đỉnh còn lại (của đường chéo thứ hai) được xác định duy nhất. Sau đó, giá trị được chuyển đổi của ô " x3" sẽ bằng giá trị trước đó của ô này trừ đi phân số, trong mẫu số của nó là phần tử phân giải (từ Bảng 5.4) và trong tử số là tích của hai đỉnh khác không được sử dụng, tức là:
« x3»: .
Giá trị của các ô khác cũng được quy đổi tương tự:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Kết quả của những phép biến đổi này là một bảng đơn giản mới đã được thu được (Bảng 5.5).
II lặp lại:
Bước 1: Vẽ bảng đơn.
Bảng 5.5
Bảng đơn giảnII lần lặp lại
Ước lượng mối quan hệ |
||||
| ||||
|
|
Giai đoạn 2: xác định giải pháp cơ bản.
Kết quả của phép biến đổi đơn hình là thu được một nghiệm cơ bản mới (Bảng 5.5):
Như bạn có thể thấy, với giải pháp cơ bản này, giá trị của hàm mục tiêu = 15, lớn hơn so với giải pháp cơ bản trước đó.
Chưa xác định được sự thiếu nhất quán của hệ thống hạn chế theo đặc điểm 1 trong Bảng 5.5.
Giai đoạn 4: kiểm tra giới hạn của hàm mục tiêu.
Tính không bị chặn của hàm mục tiêu theo tiêu chí 2 trong Bảng 5.5 không được bộc lộ.
Giai đoạn 5: kiểm tra khả năng chấp nhận của giải pháp cơ bản được tìm thấy.
Lời giải cơ bản tìm được theo tiêu chí 4 là không tối ưu, do dòng hàm mục tiêu của bảng đơn (Bảng 5.5) chứa phần tử âm: –2 (số tự do của dòng này không được tính đến khi xét điều này). đặc trưng). Vì vậy, chúng ta chuyển sang giai đoạn 8.
Giai đoạn 8: xác định phần tử phân giải.
8.1. Định nghĩa của cột độ phân giải.
Lời giải cơ bản tìm được là chấp nhận được, ta xác định các cột có phần tử âm trong hàng của hàm mục tiêu (trừ cột số tự do). Theo Bảng 5.5 chỉ có một cột như vậy: “ x1" Vì vậy, chúng tôi chấp nhận nó như được cho phép.
8.2. Định nghĩa chuỗi kích hoạt.
Theo các giá trị thu được của các quan hệ đánh giá tích cực ở Bảng 5.6, nhỏ nhất là quan hệ tương ứng với đường “ x3" Vì vậy, chúng tôi chấp nhận nó như được cho phép.
Bảng 5.6
Bảng đơn giảnII lần lặp lại
Ước lượng mối quan hệ |
||||
3/1=3 – phút |
||||
Giai đoạn 9: chuyển đổi bảng đơn giản.
Các phép biến đổi của bảng đơn (Bảng 5.6) được thực hiện tương tự như trong lần lặp trước. Kết quả phép biến đổi các phần tử của bảng đơn được cho trong bảng 5.7.
III sự lặp lại
Dựa trên kết quả của các phép biến đổi đơn giản của lần lặp trước, chúng tôi biên soạn một bảng đơn giản mới:
Bảng 5.7
Bảng đơn giảnIII lần lặp lại
Ước lượng mối quan hệ |
||||
| ||||
|
|
Giai đoạn 2: xác định giải pháp cơ bản.
Kết quả của phép biến đổi đơn hình là thu được một nghiệm cơ bản mới (Bảng 5.7):
Giai đoạn 3: kiểm tra tính tương thích của hệ thống hạn chế.
Chưa xác định được sự thiếu nhất quán của hệ thống hạn chế theo đặc điểm 1 trong Bảng 5.7.
Giai đoạn 4: kiểm tra giới hạn của hàm mục tiêu.
Tính không bị chặn của hàm mục tiêu theo tiêu chí 2 trong Bảng 5.7 không được bộc lộ.
Giai đoạn 5: kiểm tra khả năng chấp nhận của giải pháp cơ bản được tìm thấy.
Lời giải cơ bản tìm được theo tiêu chí 3 là chấp nhận được vì nó không chứa các thành phần âm.
Giai đoạn 6: kiểm tra tính tối ưu của lời giải cơ bản tìm được.
Lời giải cơ bản tìm được theo tiêu chí 4 là không tối ưu, do dòng hàm mục tiêu của bảng đơn (Bảng 5.7) chứa phần tử âm: –3 (số tự do của dòng này không được tính đến khi xét điều này). đặc trưng). Vì vậy, chúng ta chuyển sang giai đoạn 8.
Giai đoạn 8: xác định phần tử phân giải.
8.1. Định nghĩa của cột độ phân giải.
Lời giải cơ bản tìm được là chấp nhận được, ta xác định các cột có phần tử âm trong hàng của hàm mục tiêu (trừ cột số tự do). Theo Bảng 5.7 chỉ có một cột như vậy: “ x5" Vì vậy, chúng tôi chấp nhận nó như được cho phép.
8.2. Định nghĩa chuỗi kích hoạt.
Theo các giá trị thu được của các quan hệ đánh giá tích cực ở Bảng 5.8, nhỏ nhất là quan hệ tương ứng với đường “ x4" Vì vậy, chúng tôi chấp nhận nó như được cho phép.
Bảng 5.8
Bảng đơn giảnIII lần lặp lại
Ước lượng mối quan hệ |
||||
5/5=1 – phút |
||||
Giai đoạn 9: chuyển đổi bảng đơn giản.
Các phép biến đổi của bảng đơn giản (Bảng 5.8) được thực hiện theo cách tương tự như trong lần lặp trước. Kết quả phép biến đổi các phần tử của bảng đơn được cho trong bảng 5.9.
IV sự lặp lại
Giai đoạn 1: xây dựng một bảng đơn giản mới.
Dựa trên kết quả của các phép biến đổi đơn giản của lần lặp trước, chúng tôi biên soạn một bảng đơn giản mới:
Bảng 5.9
Bảng đơn giảnIV lần lặp lại
Ước lượng mối quan hệ |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Giai đoạn 2: xác định giải pháp cơ bản.
Kết quả của phép biến đổi đơn hình thu được nghiệm cơ bản mới, theo Bảng 5.9 nghiệm như sau:
Giai đoạn 3: kiểm tra tính tương thích của hệ thống hạn chế.
Chưa xác định được sự thiếu nhất quán của hệ thống hạn chế theo đặc điểm 1 trong Bảng 5.9.
Giai đoạn 4: kiểm tra giới hạn của hàm mục tiêu.
Tính không bị chặn của hàm mục tiêu theo tiêu chí 2 trong Bảng 5.9 không được bộc lộ.
Giai đoạn 5: kiểm tra khả năng chấp nhận của giải pháp cơ bản được tìm thấy.
Lời giải cơ bản tìm được theo tiêu chí 3 là chấp nhận được vì nó không chứa các thành phần âm.
Giai đoạn 6: kiểm tra tính tối ưu của lời giải cơ bản tìm được.
Lời giải cơ bản tìm được theo đặc điểm 4 là tối ưu, vì không có phần tử âm nào trên dòng của hàm mục tiêu của bảng đơn (Bảng 5.9) (số tự do của dòng này không được tính đến khi xét đặc điểm này) .
Giai đoạn 7: kiểm tra tính khả thi của giải pháp.
Giải pháp được tìm thấy là duy nhất, vì không có phần tử 0 nào trong dòng của hàm mục tiêu (Bảng 5.9) (số tự do của dòng này không được tính đến khi xem xét tính năng này).
Trả lời: giá trị tối ưu hàm mục tiêu của bài toán đang xét =24, đạt được tại.
Ví dụ 5.2. Giải bài toán quy hoạch tuyến tính ở trên với điều kiện là hàm mục tiêu được cực tiểu hóa:
Giải pháp:
TÔI lặp lại:
Giai đoạn 1: hình thành bảng đơn giản ban đầu.
Bài toán quy hoạch tuyến tính ban đầu được đưa ra ở dạng chuẩn. Hãy mang nó đến hình thức kinh điển bằng cách đưa vào mỗi ràng buộc của bất đẳng thức một biến không âm bổ sung, tức là
Trong hệ phương trình thu được, chúng ta lấy các biến được phép (cơ bản) x3, x4, x5, x6, thì các biến tự do sẽ là x1,x2. Chúng ta hãy biểu diễn các biến cơ bản dưới dạng các biến tự do.
Hãy xem xét phương pháp đơn giảnđể giải các bài toán quy hoạch tuyến tính (LP). Nó dựa trên sự chuyển đổi từ kế hoạch tham chiếu này sang kế hoạch tham chiếu khác, trong đó giá trị của hàm mục tiêu tăng lên.
Thuật toán của phương pháp đơn giản như sau:
- Chúng tôi chuyển đổi vấn đề ban đầu thành dạng chính tắc bằng cách đưa vào các biến bổ sung. Đối với các bất đẳng thức có dạng ≤, các biến bổ sung được đưa vào với dấu (+), nhưng nếu có dạng ≥ thì thêm vào dấu (-). Các biến bổ sung được đưa vào hàm mục tiêu có dấu tương ứng với hệ số bằng 0 , bởi vì hàm mục tiêu không nên thay đổi ý nghĩa kinh tế của nó.
- Các vectơ được viết ra Số Pi từ các hệ số của các biến và cột các số hạng tự do. Hành động này xác định số lượng vectơ đơn vị. Quy tắc là số lượng vectơ đơn vị phải bằng số lượng bất đẳng thức trong hệ ràng buộc.
- Sau đó, dữ liệu nguồn được nhập vào một bảng đơn giản. Các vectơ đơn vị được đưa vào cơ sở và bằng cách loại trừ chúng khỏi cơ sở, giải pháp tối ưu sẽ được tìm thấy. Các hệ số của hàm mục tiêu được viết với dấu ngược lại.
- Dấu hiệu tối ưu cho bài toán LP là giải pháp tối ưu nếu trong f– trong hàng tất cả các hệ số đều dương. Quy tắc tìm cột kích hoạt - đã xem f– một chuỗi và trong số các phần tử âm của nó, phần tử nhỏ nhất được chọn. Vectơ Số Pi việc chứa đựng nó trở nên dễ dãi. Quy tắc chọn phần tử phân giải - tỷ lệ giữa các phần tử dương của cột phân giải với các phần tử của vectơ được biên soạn P 0 và số cho tỷ lệ nhỏ nhất sẽ trở thành phần tử phân giải mà bảng đơn sẽ được tính toán lại. Dòng chứa phần tử này được gọi là dòng kích hoạt. Nếu không có phần tử tích cực nào trong cột độ phân giải thì bài toán không có lời giải. Sau khi xác định được phần tử phân giải, họ tiến hành tính toán lại bảng đơn giản mới.
- Quy tắc điền vào một bảng đơn giản mới. Đơn vị được đặt thay cho phần tử phân giải và các phần tử khác được coi là bằng nhau 0 . Vectơ phân giải được thêm vào cơ sở, từ đó vectơ 0 tương ứng bị loại trừ và các vectơ cơ sở còn lại được viết mà không thay đổi. Các phần tử của đường phân giải được chia cho phần tử độ phân giải, các phần tử còn lại được tính toán lại theo quy tắc hình chữ nhật.
- Việc này được thực hiện cho đến khi f– tất cả các phần tử của chuỗi sẽ không trở thành số dương.
Hãy xem xét việc giải quyết vấn đề bằng thuật toán được thảo luận ở trên.
Được cho:
Chúng tôi đưa vấn đề về dạng chính tắc:
Chúng tôi soạn các vectơ:
Điền vào bảng đơn:
:
Hãy tính lại phần tử đầu tiên của vectơ P 0, mà chúng ta tạo một hình chữ nhật gồm các số: và chúng ta nhận được: 
.
Chúng tôi thực hiện các phép tính tương tự cho tất cả các phần tử khác của bảng đơn:
Trong kế hoạch nhận được f– dòng chứa một phần tử âm – (-5/3), vector P 1. Nó chứa trong cột của nó một phần tử tích cực duy nhất, phần tử này sẽ là phần tử kích hoạt. Hãy tính toán lại bảng liên quan đến yếu tố này:
Không có yếu tố tiêu cực trong f– dòng có nghĩa là tìm thấy phương án tối ưu:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Lập trình tuyến tính, M: Nauka, 1998,
- Ventzel E.S. Nghiên cứu Hoạt động, M: Đài phát thanh Liên Xô, 2001,
- Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Lập trình toán học, M: trường sau đại học, 1986
Giải pháp lập trình tuyến tính tùy chỉnh
Bạn có thể đặt bất kỳ bài tập nào trong chuyên ngành này trên trang web của chúng tôi. Bạn có thể đính kèm tập tin và chỉ định thời hạn tại
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | St. thành viên | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | St. thành viên | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F-1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F-1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F-13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Lý thuyết tóm tắt
Nhiều phương pháp khác nhau đã được đề xuất để giải các bài toán quy hoạch tuyến tính. Tuy nhiên, phương pháp đơn giản hóa ra lại hiệu quả và phổ biến nhất trong số đó. Cần lưu ý rằng khi giải quyết một số vấn đề, các phương pháp khác có thể hiệu quả hơn. Ví dụ: đối với ZLP có hai biến, phương pháp tối ưu là , và để giải nó, phương pháp tiềm năng được sử dụng. Phương pháp đơn giản là cơ bản và có thể áp dụng cho bất kỳ PPL nào ở dạng chuẩn.
Liên quan đến định lý chính của quy hoạch tuyến tính, một cách tự nhiên nảy sinh ý tưởng về con đường sau quyết định PPP với bất kỳ số lượng biến nào. Bằng cách nào đó, hãy tìm tất cả các điểm cực trị của khối đa diện của các mặt phẳng (không có điểm nào nhiều hơn ) và so sánh các giá trị của hàm mục tiêu tại chúng. Đường giải này, ngay cả với số lượng biến và hạn chế tương đối nhỏ, thực tế là không thể, vì quá trình tìm điểm cực trị có độ khó tương đương với quá trình giải. vấn đề ban đầu, hơn nữa, số lượng điểm cực trị của khối đa diện của sơ đồ có thể rất lớn. Liên quan đến những khó khăn này, vấn đề liệt kê hợp lý các điểm cực trị đã nảy sinh.
Bản chất của phương pháp đơn giản như sau. Nếu đã biết một số điểm cực trị và giá trị của hàm mục tiêu tại đó thì tất cả các điểm cực trị mà tại đó hàm mục tiêu có giá trị xấu nhất rõ ràng là không cần thiết. Do đó, mong muốn tự nhiên là tìm cách di chuyển từ một điểm cực trị nhất định đến một điểm cực trị tốt hơn liền kề dọc theo rìa, từ điểm đó đến điểm cực trị tốt hơn (không tệ hơn), v.v. Để làm được điều này, bạn cần phải có một dấu hiệu cho thấy không có điểm cực trị nào tốt hơn một điểm cực trị cho trước. Đây là ý tưởng chung của phương pháp đơn giản được sử dụng rộng rãi nhất hiện nay (phương pháp cải tiến tuần tự kế hoạch) để giải ZLP. Vì vậy, theo thuật ngữ đại số, phương pháp đơn hình giả định:
- khả năng tìm thấy một kế hoạch tham khảo ban đầu;
- sự hiện diện của một dấu hiệu tối ưu của kế hoạch tham chiếu;
- khả năng chuyển sang một kế hoạch tham khảo không tệ nhất.
Ví dụ về giải pháp vấn đề
Nhiệm vụ
Để bán được ba nhóm hàng hóa, một doanh nghiệp thương mại có ba loại nguồn lực vật chất, tiền tệ có hạn với số lượng , , , đơn vị. Đồng thời, bán 1 nhóm hàng hóa với giá 1 nghìn rúp. Doanh thu hàng hóa tiêu thụ tài nguyên loại thứ nhất về số lượng đơn vị, tài nguyên loại thứ hai về số lượng đơn vị, tài nguyên loại thứ ba về số lượng đơn vị. Để bán 2 và 3 nhóm hàng hóa với giá 1 nghìn rúp. Kim ngạch hàng hóa được chi theo nguồn lực loại thứ nhất tính bằng số lượng, đơn vị, tài nguyên loại thứ hai tính bằng số lượng, đơn vị, tài nguyên loại thứ ba tính bằng số lượng, đơn vị. Lợi nhuận từ việc bán ba nhóm hàng hóa với giá 1 nghìn rúp. doanh thu tương ứng là 1 nghìn rúp.
- Xác định khối lượng và cơ cấu kim ngạch thương mại dự kiến sao cho doanh nghiệp thương mại thu được lợi nhuận tối đa.
- Đối với bài toán trực tiếp quy hoạch doanh thu, giải bằng phương pháp đơn hình, tạo ra bài toán quy hoạch tuyến tính kép.
- Thiết lập các cặp biến liên hợp của bài toán trực tiếp và đối ngẫu.
- Theo các cặp biến liên hợp từ lời giải của bài toán trực tiếp, thu được lời giải vấn đề kép, trong đó đánh giá các nguồn lực dành cho việc bán hàng.
Nếu việc tham gia phiên của bạn phụ thuộc vào việc giải quyết một loạt vấn đề và bạn không có thời gian cũng như không muốn ngồi xuống để tính toán, hãy sử dụng các khả năng của trang web. Nhiệm vụ đặt hàng chỉ mất vài phút. Bạn có thể đọc chi tiết (cách gửi yêu cầu, giá cả, điều khoản, phương thức thanh toán) trên trang Mua giải pháp cho bài toán quy hoạch tuyến tính...
Giải pháp của vấn đề
Xây dựng mô hình
Chúng ta hãy biểu thị kim ngạch của loại hàng hóa thứ nhất, thứ hai và thứ ba tương ứng.
Khi đó hàm mục tiêu thể hiện lợi nhuận nhận được:
Hạn chế về nguồn lực vật chất, tiền tệ:
Ngoài ra, theo ý nghĩa của nhiệm vụ
Chúng ta nhận được bài toán quy hoạch tuyến tính sau:
Rút gọn về dạng chuẩn của ZLP
Chúng ta hãy rút gọn vấn đề về dạng kinh điển. Để chuyển đổi bất đẳng thức thành đẳng thức, chúng tôi giới thiệu các biến bổ sung. Các biến được đưa vào giới hạn với hệ số 1. Chúng tôi đưa tất cả các biến bổ sung vào hàm mục tiêu với hệ số bằng 0.
Hạn chế có dạng thích hợp hơn nếu, nếu vế phải không âm bên trái có một biến được bao gồm với hệ số bằng 1 và các ràng buộc đẳng thức còn lại - với hệ số bằng 0. Trong trường hợp của chúng tôi, các hạn chế thứ 1, 2, 3 có dạng ưu tiên với các biến cơ bản tương ứng.
Giải bằng phương pháp đơn hình
Điền vào bảng đơn lần lặp thứ 0.
| BP | một mặt mối quan hệ |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 520 | 16 | 18 | 9 | 1 | 0 | 0 | 65/2 | 0 | 140 | 7 | 7 | 2 | 0 | 1 | 0 | 20 | 0 | 810 | 9 | 2 | 1 | 0 | 0 | 1 | 90 | 0 | -8 | -6 | -4 | 0 | 0 | 0 |
Vì chúng ta đang giải bài toán ở mức tối đa nên việc xuất hiện các số âm trên dòng chỉ số khi giải bài toán ở mức tối đa cho thấy chúng ta chưa thu được lời giải tối ưu và cần phải chuyển từ bảng lặp thứ 0 sang cái tiếp theo.
Chúng ta tiến hành lần lặp tiếp theo như sau:
Cột đầu tương ứng với .
Hàng khóa được xác định bởi tỷ lệ tối thiểu của các số hạng tự do và các thành viên của cột dẫn đầu (quan hệ đơn giản):
Tại giao điểm của cột khóa và hàng khóa, chúng ta tìm thấy phần tử kích hoạt, tức là 7.
Bây giờ chúng ta bắt đầu biên dịch lần lặp đầu tiên. Thay vì vectơ đơn vị, chúng tôi giới thiệu vectơ .
TRONG bảng mới thay cho phần tử kích hoạt, chúng ta viết 1, tất cả các phần tử khác của cột khóa đều là số 0. Các phần tử chuỗi khóa được chia thành phần tử kích hoạt. Tất cả các phần tử khác của bảng được tính bằng quy tắc hình chữ nhật.
Chúng ta nhận được bảng của lần lặp đầu tiên:
| BP | một mặt mối quan hệ |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 200 | 0 | 2 | 31/7 | 1 | -16/7 | 0 | 1400/31 | 8 | 20 | 1 | 1 | 2/7 | 0 | 1/7 | 0 | 70 | 0 | 630 | 0 | -7 | -11/7 | 0 | -9/7 | 1 | - | 160 | 0 | 2 | -12/7 | 0 | 8/7 | 0 |
Cột khóa cho lần lặp đầu tiên tương ứng với .
Chúng tôi tìm thấy dòng chính, vì điều này chúng tôi xác định:
Tại giao điểm của cột khóa và hàng khóa, chúng ta tìm thấy phần tử kích hoạt, tức là. 31/7.
Vectơ có nguồn gốc từ cơ sở và vectơ được giới thiệu.
Chúng ta nhận được bảng của lần lặp thứ 2:
| BP | một mặt mối quan hệ |
8 | 6 | 4 | 0 | 0 | 0 | 4 | 1400/31 | 0 | 14/31 | 1 | 7/31 | -16/31 | 0 | 8 | 220/31 | 1 | 27/31 | 0 | -2/31 | 9/31 | 0 | 0 | 21730/31 | 0 | -195/31 | 0 | 11/31 | -65/31 | 1 | 7360/31 | 0 | 86/31 | 0 | 12/31 | 8/31 | 0 |
Trong hàng chỉ số, tất cả các số hạng đều không âm, do đó thu được lời giải sau cho bài toán quy hoạch tuyến tính (chúng ta viết nó ra từ cột các số hạng tự do):
Vì vậy, cần phải bán 7,1 nghìn rúp. hàng hóa loại 1 và 45,2 nghìn rúp. hàng loại 3. Bán sản phẩm loại 2 sẽ không có lãi. Trong trường hợp này, lợi nhuận sẽ tối đa và lên tới 237,4 nghìn rúp. Nếu phương án tối ưu được thực hiện thì nguồn lực loại 3 còn lại sẽ là 701 đơn vị.
Vấn đề LP kép
Hãy để chúng tôi viết ra một mô hình của vấn đề kép.
Để xây dựng một bài toán kép, bạn phải sử dụng các quy tắc sau:
1) nếu bài toán trực tiếp được giải ở mức tối đa thì bài toán kép được giải ở mức tối thiểu và ngược lại;
2) trong bài toán cực đại, các ràng buộc bất đẳng thức có ý nghĩa ≤, và trong bài toán cực tiểu hóa chúng có ý nghĩa ≥;
3) mỗi ràng buộc của bài toán trực tiếp tương ứng với một biến của bài toán đối ngẫu và ngược lại, mỗi ràng buộc của bài toán đối ngẫu tương ứng với một biến của bài toán trực tiếp;
4) Ma trận hệ các ràng buộc của bài toán đối ngẫu được lấy từ ma trận hệ các ràng buộc của bài toán gốc bằng cách chuyển vị;
5) Các số hạng tự do của hệ ràng buộc của bài toán trực tiếp là hệ số của các biến tương ứng của hàm mục tiêu của bài toán đối ngẫu và ngược lại;
6) nếu một điều kiện không âm được áp đặt cho biến của bài toán trực tiếp thì ràng buộc tương ứng của bài toán đối ngẫu được viết dưới dạng ràng buộc bất đẳng thức, nếu không thì là ràng buộc đẳng thức;
7) nếu bất kỳ ràng buộc nào của bài toán trực tiếp được viết dưới dạng đẳng thức thì điều kiện không âm không được áp đặt cho biến tương ứng của bài toán đối ngẫu.
Chúng ta hoán vị ma trận của bài toán ban đầu:
Chúng ta hãy rút gọn vấn đề về dạng kinh điển. Hãy giới thiệu các biến bổ sung. Chúng tôi đưa tất cả các biến bổ sung vào hàm mục tiêu với hệ số bằng 0. Chúng ta thêm các biến bổ sung vào vế trái của các giới hạn không có dạng ưu tiên và chúng ta thu được các đẳng thức.
Giải pháp cho vấn đề LP kép
Sự tương ứng giữa các biến của bài toán gốc và bài toán kép:
Dựa trên bảng đơn giản, người ta đã thu được giải pháp sau đây cho bài toán quy hoạch tuyến tính kép (chúng tôi viết nó ra từ dòng dưới cùng):
Vì vậy, nguồn lực loại thứ nhất là khan hiếm nhất. Điểm của nó là tối đa và bằng . Tài nguyên loại thứ ba là dư thừa - giá trị kép của nó bằng 0. Mỗi đơn vị hàng hóa tăng thêm của nhóm thứ 2 được bán ra sẽ làm giảm lợi nhuận tối ưu đi một lượng
Được xem xét phương pháp đồ họa giải bài toán quy hoạch tuyến tính (LPP) hai biến. Một ví dụ về nhiệm vụ được đưa ra miêu tả cụ thể dựng bản vẽ và tìm cách giải.
Giải quyết bài toán vận tải
Đã xem xét chi tiết vấn đề vận chuyển, cô ấy mô hình toán học và phương pháp giải - tìm phương án tham chiếu bằng phương pháp phần tử tối thiểu và tìm kiếm lời giải tối ưu bằng phương pháp thế năng.
Ra quyết định trong điều kiện không chắc chắn
Lời giải của trò chơi ma trận thống kê trong điều kiện không chắc chắn được xem xét bằng cách sử dụng tiêu chí Wald, Savage, Hurwitz, Laplace và Bayes. Sử dụng một bài toán ví dụ, việc xây dựng ma trận thanh toán và ma trận rủi ro được trình bày chi tiết.
Đã thích? Thêm vào dấu trang
Giải quyết vấn đề bằng phương pháp đơn giản: ví dụ trực tuyến
Nhiệm vụ 1. Công ty sản xuất kệ phòng tắm với hai kích cỡ - A và B. Các đại lý bán hàng ước tính có thể bán được tới 550 kệ trên thị trường mỗi tuần. Mỗi kệ loại A yêu cầu 2 m2 vật liệu, mỗi kệ loại B yêu cầu 3 m2 vật liệu. Công ty có thể nhận tới 1200 m2 nguyên liệu mỗi tuần. Để sản xuất một kệ loại A cần thời gian sử dụng máy là 12 phút, để sản xuất một kệ loại B là 30 phút; Máy có thể được sử dụng 160 giờ một tuần. Nếu lợi nhuận từ việc bán kệ loại A là 3 đơn vị tiền tệ và từ kệ loại B - 4 đơn vị tiền tệ. đơn vị thì mỗi tuần nên sản xuất bao nhiêu kệ mỗi loại?
Nhiệm vụ 2. Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình. 
Nhiệm vụ 3. Công ty sản xuất 3 loại sản phẩm: A1, A2, A3, sử dụng 2 loại nguyên liệu. Chi phí của từng loại nguyên liệu trên một đơn vị sản xuất, lượng nguyên liệu dự trữ trong kỳ kế hoạch cũng như lợi nhuận thu được từ một đơn vị sản xuất của từng loại đều được biết.
- Phải sản xuất bao nhiêu mặt hàng mỗi loại để tối đa hóa lợi nhuận?
- Xác định trạng thái của từng loại nguyên liệu và giá trị cụ thể của nó.
- Xác định khoảng thời gian tối đa cho những thay đổi trong tồn kho của từng loại nguyên vật liệu, trong đó xây dựng phương án tối ưu, tức là. Danh pháp sản xuất sẽ không thay đổi.
- Xác định số lượng sản phẩm sản xuất và lợi nhuận từ sản xuất khi tăng lượng dự trữ một trong những loại nguyên liệu thô khan hiếm lên giá trị tối đa có thể (trong phạm vi sản lượng nhất định).
- Xác định các khoảng thời gian thay đổi lợi nhuận từ một đơn vị sản xuất của từng loại mà tại đó phương án tối ưu đạt được sẽ không thay đổi.
Nhiệm vụ 4. Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình: 
Nhiệm vụ 5. Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình: 
Nhiệm vụ 6. Giải bài toán bằng phương pháp đơn hình, coi phương án đã cho trong điều kiện là phương án tham chiếu ban đầu: 
Nhiệm vụ 7. Giải bài toán bằng phương pháp đơn hình đã sửa đổi.
Để sản xuất hai loại sản phẩm A và B, ba loại thiết bị công nghệ được sử dụng. Để sản xuất một đơn vị sản phẩm A, thiết bị loại thứ nhất sử dụng a1=4 giờ, thiết bị loại thứ hai a2=8 giờ và thiết bị loại thứ ba a3=9 giờ. Để sản xuất một đơn vị sản phẩm B, thiết bị loại thứ nhất sử dụng b1=7 giờ, thiết bị loại thứ hai b2=3 giờ và thiết bị loại thứ ba b3=5 giờ.
Thiết bị loại thứ nhất có thể hoạt động để sản xuất các sản phẩm này không quá t1=49 giờ, thiết bị loại thứ hai không quá t2=51 giờ, thiết bị loại thứ ba không quá t3=45 giờ.
Lợi nhuận từ việc bán một đơn vị thành phẩm A là ALPHA = 6 rúp và sản phẩm B là BETTA = 5 rúp.
Lập kế hoạch sản xuất cho sản phẩm A và B, đảm bảo lợi nhuận tối đa từ việc bán chúng.
Nhiệm vụ 8. Tìm thấy giải pháp tối ưu phương pháp đơn giản kép 
