Giải bằng phương pháp đơn hình, ví dụ về cách giải. Một ví dụ về giải bài toán trực tiếp và kép bằng phương pháp đơn giản
. 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:
Chúng ta hãy giảm hàm mục tiêu xuống 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) .
Vì nghiệm cơ bản tìm được không chứa các thành phần phủ định nên có 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 biến cơ bản và một biến tự do phải được hoán đổi trong bảng đơn giản để chuyển sang biến “cải tiến” mới. giải pháp cơ bản. 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.
Vấn đề ban đầu quy hoạch tuyến tính đượ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.
Một ví dụ về giải một bài toán bằng phương pháp đơn hình, cũng như một ví dụ về giải một bài toán kép, được xem xét.
Nhiệm vụ
Để bán được ba nhóm hàng hóa, doanh nghiệp thương mại có ba loại nguồn lực vật chất, tiền tệ hạn chế với số lượng b 1 = 240, b 2 = 200, b 3 = 160 đơ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, tài nguyên loại thứ nhất được tiêu thụ với số lượng a 11 = 2 đơn vị, tài nguyên loại thứ hai với số lượng a 21 = 4 đơn vị, tài nguyên loại thứ ba với số lượng a 31 = 4 đơn vị. Để bán 2 và 3 nhóm hàng hóa với giá 1 nghìn rúp. doanh thu được tiêu thụ theo tài nguyên loại thứ nhất với số lượng a 12 = 3, a 13 = 6 đơn vị, tài nguyên loại thứ hai với số lượng a 22 = 2, a 23 = 4 đơn vị, tài nguyên của loại thứ ba với số lượng a 32 = 6, a 33 = 8 đơ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 lần lượt là c 1 = 4, c 2 = 5, c 3 = 4 (ngà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 vấn đề trực tiếp về lập kế hoạch doanh thu, giải bằng phương pháp đơn hình, soạn, biên soạn vấn đề kép lập trình tuyến tính.
Cài đặt cặp biến liên hợp vấn đề trực tiếp và kép.
Theo cặp biến liên hợp, từ nghiệm của bài toán trực tiếp ta thu được giải pháp của vấn đề kép, nơi nó được sản xuất đánh giá tài nguyên, chi cho việc bán hàng hóa.
Giải bài toán bằng phương pháp đơn hình
Gọi x 1, x 2, x 3 là số lượng hàng bán được, tính bằng nghìn rúp, lần lượt là 1, 2, 3 nhóm. Sau đó mô hình toán học nhiệm vụ có dạng:F = 4 x 1 + 5 x 2 + 4 x 3 -> tối đa
0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}
Ta giải theo phương pháp đơn hình.
Chúng tôi đưa vào thêm các biến x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 để chuyển các bất đẳng thức về dạng đẳng thức.
Hãy lấy x 4 = 240 làm cơ sở; x 5 = 200; x6 = 160.
Chúng tôi nhập dữ liệu vào bảng đơn
Bảng đơn giản số 1
Hàm mục tiêu:
0 240 + 0 200 + 0 160 = 0
Chúng tôi tính toán ước tính bằng công thức:
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Vì có những ước tính âm nên kế hoạch này không tối ưu. Điểm thấp nhất:
Chúng tôi đưa biến x 2 vào cơ sở.
Chúng tôi xác định một biến xuất hiện từ cơ sở. Để làm điều này, chúng tôi tìm tỷ lệ không âm nhỏ nhất cho cột x2.
= 26.667
Không âm nhỏ nhất: Q 3 = 26,667. Ta suy ra biến x 6 từ cơ sở
Chia dòng thứ 3 cho 6.
Ở dòng thứ 1 trừ dòng thứ 3 rồi nhân với 3
Ở dòng thứ 2 trừ dòng thứ 3 rồi nhân với 2
Chúng tôi tính toán:
Chúng tôi nhận được bảng mới:
Bảng đơn giản số 2
Hàm mục tiêu:
0 160 + 0 440/3 + 5 80/3 = 400/3
Chúng tôi tính toán ước tính bằng công thức:
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6
Vì có ước tính âm Δ 1 = - 2/3 nên phương án này không tối ưu.
Chúng tôi đưa biến x 1 vào cơ sở.
Chúng tôi xác định một biến xuất hiện từ cơ sở. Để làm điều này, chúng tôi tìm tỷ lệ không âm nhỏ nhất cho cột x 1.
Không âm nhỏ nhất: Q 3 = 40. Ta suy ra biến x 2 từ cơ sở
Chia dòng thứ 3 cho 2/3.
Từ dòng thứ 2 trừ dòng thứ 3, nhân với 8/3
Chúng tôi tính toán:
Chúng tôi nhận được một bảng mới:
Bảng đơn giản số 3
Hàm mục tiêu:
0 160 + 0 40 + 4 40 = 160
Chúng tôi tính toán ước tính bằng công thức:
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1
Vì không có xếp hạng tiêu cực nên kế hoạch này là tối ưu.
Giải pháp của vấn đề:
Trả lời
x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F tối đa = 160Tức là cần bán loại hàng hóa đầu tiên với số tiền 40 nghìn rúp. Không cần thiết phải bán hàng loại 2 và loại 3. Trong trường hợp này, lợi nhuận tối đa sẽ là F max = 160 nghìn rúp.
Giải quyết vấn đề kép
Bài toán kép có dạng:
Z = 240 y 1 + 200 y 2 + 160 y 3 ->phút
Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}
Chúng tôi đưa vào các biến bổ sung y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 để chuyển các bất đẳng thức thành đẳng thức.
Cặp biến liên hợp của bài toán trực tiếp và đối ngẫu có dạng:
Từ bảng đơn cuối cùng số 3 của bài toán trực tiếp, ta tìm nghiệm của bài toán kép:
Z phút = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;
Đã 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 phẩm, 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 ra 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 phương pháp đơn giản:
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 
Mục đích của dịch vụ. Dịch vụ này dành cho giải pháp trực tuyến Các bài toán quy hoạch tuyến tính (LPP) sử dụng phương pháp đơn hình có dạng ký hiệu sau:
- ở dạng bảng đơn giản (phương pháp biến đổi Jordan); hình thức ghi chép cơ bản;
- phương pháp đơn giản sửa đổi; ở dạng cột; ở dạng dòng.
Hướng dẫn. Chọn số lượng biến và số lượng hàng (số lượng ràng buộc). Dung dịch thu được được bảo quản trong Tệp từ và Excel.
Trong trường hợp này không tính đến các hạn chế như x i ≥ 0. Nếu không có hạn chế nào trong nhiệm vụ đối với một số x i thì ZLP phải được chuyển đổi thành KZLP hoặc sử dụng dịch vụ này. Khi giải quyết, việc sử dụng được xác định tự động phương pháp M(phương pháp đơn giản với cơ sở nhân tạo) và phương pháp đơn hình hai giai đoạn.Những điều sau đây cũng được sử dụng với máy tính này:
Phương pháp đồ họa để giải ZLP
Giải quyết bài toán vận tải
Giải một trò chơi ma trận
Sử dụng dịch vụ tại chế độ online bạn có thể xác định giá của trò chơi ma trận (giới hạn dưới và giới hạn trên), kiểm tra tính khả dụng điểm yên ngựa, tìm giải pháp cho chiến lược hỗn hợp bằng các phương pháp sau: phương pháp minimax, phương pháp đơn giản, phương pháp đồ họa (hình học), phương pháp Brown.
Cực trị của hàm hai biến
Các vấn đề về lập trình động
Phân phối 5 lô hàng hóa đồng nhất giữa ba thị trường để thu được thu nhập tối đa từ việc bán hàng. Thu nhập từ việc bán hàng ở mỗi thị trường G(X) phụ thuộc vào số lô sản phẩm X bán ra và được trình bày trong bảng.
| Khối lượng sản phẩm X (theo lô) | Thu nhập G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Thuật toán phương pháp đơn giản bao gồm các bước sau:
- Lập kế hoạch cơ bản đầu tiên. Chuyển sang dạng chính tắc của bài toán quy hoạch tuyến tính bằng cách đưa vào các biến cân bằng bổ sung không âm.
- Kiểm tra phương án tối ưu. Nếu có ít nhất một hệ số đường chỉ số nhỏ hơn 0 thì phương án đó không tối ưu và cần được cải thiện.
- Xác định cột và hàng đầu. Trong số các hệ số âm của đường chỉ số, hệ số lớn nhất được chọn giá trị tuyệt đối. Sau đó, các phần tử của cột thành viên tự do của bảng đơn được chia thành các phần tử cùng dấu của cột đầu.
- Xây dựng kế hoạch tham khảo mới. Việc chuyển đổi sang một kế hoạch mới được thực hiện bằng cách tính toán lại bảng đơn bằng phương pháp Jordan-Gauss.
Nếu cần tìm cực trị của hàm mục tiêu thì Chúng ta đang nói về về tìm kiếm giá trị tối thiểu(F(x) → min , xem ví dụ về giải pháp tối thiểu hóa hàm) và giá trị tối đa ((F(x) → max , xem ví dụ về giải pháp tối ưu hóa hàm)
Một nghiệm cực trị đạt được trên ranh giới của miền nghiệm khả thi tại một trong các đỉnh của các điểm góc của đa giác hoặc trên đoạn giữa hai điểm góc liền kề.
Định lý cơ bản của quy hoạch tuyến tính. Nếu hàm mục tiêu ZLP đạt đến giá trị cực trị tại một điểm nào đó trong vùng nghiệm khả thi thì nó sẽ lấy giá trị này tại điểm góc. Nếu hàm mục tiêu ZLP đạt đến giá trị cực trị tại nhiều hơn một điểm góc thì nó sẽ nhận cùng một giá trị tại bất kỳ tổ hợp tuyến tính lồi nào của các điểm này.
Bản chất của phương pháp đơn hình. Việc di chuyển đến điểm tối ưu được thực hiện bằng cách di chuyển từ điểm góc này sang điểm lân cận, điều này mang lại X opt gần hơn và nhanh hơn. Một sơ đồ liệt kê các điểm như vậy, gọi là phương pháp đơn hình, do R. Danzig đề xuất.
Điểm góc được đặc trưng bởi m biến cơ bản, do đó, việc chuyển đổi từ một điểm góc sang điểm lân cận có thể được thực hiện bằng cách chỉ thay đổi một biến cơ bản trong cơ sở thành một biến từ không cơ sở.
Triển khai áp dụng phương pháp đơn hình Các tính năng khác nhau và báo cáo vấn đề, LP có nhiều sửa đổi khác nhau.
Việc xây dựng các bảng đơn giản tiếp tục cho đến khi đạt được giải pháp tối ưu. Làm thế nào bạn có thể sử dụng bảng đơn để xác định rằng giải pháp cho bài toán quy hoạch tuyến tính là tối ưu?
Nếu như dòng cuối cùng(các giá trị của hàm mục tiêu) không chứa phần tử âm nên sẽ tìm được phương án tối ưu.
Nhận xét 1. Nếu một trong các biến cơ bản bằng 0 thì điểm cực trị tương ứng với nghiệm cơ bản đó là suy biến. Suy thoái xảy ra khi có sự mơ hồ trong việc lựa chọn đường hướng dẫn. Bạn có thể không nhận thấy sự thoái hóa của vấn đề nếu bạn chọn một dòng khác làm hướng dẫn. Trong trường hợp không rõ ràng, nên chọn hàng có chỉ số thấp nhất để tránh lặp.
Nhận xét 2. Giả sử tại một điểm cực trị nào đó tất cả các sai phân đơn giản đều không âm D k ³ 0 (k = 1..n+m), tức là. thu được một nghiệm tối ưu và tồn tại A k - một vectơ không cơ sở mà D k = 0. Khi đó đạt cực đại ít nhất tại hai điểm, tức là. có một phương án tối ưu thay thế. Nếu ta đưa biến x k này vào cơ sở thì giá trị của hàm mục tiêu sẽ không thay đổi.
Nhận xét 3. Lời giải của bài toán kép nằm ở câu cuối cùng bảng đơn. M thành phần cuối cùng của vectơ hiệu đơn hình (trong các cột biến số cân bằng) là nghiệm tối ưu cho bài toán đối ngẫu. Nghĩa chức năng mục tiêu Các vấn đề trực tiếp và kép trùng khớp ở những điểm tối ưu.
Nhận xét 4. Khi giải bài toán cực tiểu hóa, vectơ có hiệu đơn giản dương lớn nhất được đưa vào cơ sở. Tiếp theo, thuật toán tương tự được áp dụng như đối với bài toán cực đại hóa.
Nếu quy định điều kiện “Cần tiêu thụ hết nguyên liệu loại III” thì điều kiện tương ứng là đẳng thức.
