1、運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一章 線性規劃及單純形法n線性規劃問題及其數學模型n圖解法n單純形法原理n單純形法計算步驟n應用舉例運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型例例1 1 美佳公司計劃制造I,II兩種家電產品.已知各制造一件時分別占用的設備A,B,C的臺時, 每天可用于這兩種家電的能力，各售出一件時的獲利情況如下表所示.問該公司應制造兩種家電各多少件,使獲利最多。1.1 問題的提出產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1運籌學運籌學-線性規劃及單純形法線性規劃

2、及單純形法第一節 線性規劃問題及其數學模型例例1 1 美佳公司計劃制造I,II兩種家電產品.已知各制造一件時分別占用的設備A,B,C的臺時, 每天可用于這兩種家電的能力，各售出一件時的獲利情況如下表所示.問該公司應制造兩種家電各多少件,使獲利最多。分析產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1目標運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型例例1 1 美佳公司計劃制造I,II兩種家電產品.已知各制造一件時分別占用的設備A,B,C的臺時, 每天可用于這兩種家電的能力，各售出一件時的獲利情況如下表所示

3、.問該公司應制造兩種家電各多少件,使獲利最多。分析產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1目標約束條件運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型例例1 1 美佳公司計劃制造I,II兩種家電產品.已知各制造一件時分別占用的設備A,B,C的臺時, 每天可用于這兩種家電的能力，各售出一件時的獲利情況如下表所示.問該公司應制造兩種家電各多少件,使獲利最多。分析產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1目標約束條件如何體現目標?運籌學運籌學-線

4、性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型例例1 1 美佳公司計劃制造I,II兩種家電產品.已知各制造一件時分別占用的設備A,B,C的臺時, 每天可用于這兩種家電的能力，各售出一件時的獲利情況如下表所示.問該公司應制造兩種家電各多少件,使獲利最多。分析產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1目標約束條件如何體現目標?運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型例例1 1 美佳公司計劃制造I,II兩種家電產品.已知各制造一件時分別占用的設備A,B,C的臺時, 每天可用于這兩

5、種家電的能力，各售出一件時的獲利情況如下表所示.問該公司應制造兩種家電各多少件,使獲利最多。分析產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1目標約束條件如何體現約束?運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1解解: : 設該公司應制造產品設該公司應制造產品I,II分別為分別為x1 1, ,x2 2件件則則, ,目標函數目標函數 max z = 2 x1 + 1 x2 約束條件約束條件 0 x1

6、 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1解解: : 設該公司應制造產品設該公司應制造產品I,II分別為分別為x1 1, ,x2 2件件則則, ,目標函數目標函數 max z = 2 x1 + 1 x2 約束條件約束條件 0 x1 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20運籌學運籌學-線性規劃及單純形法

7、線性規劃及單純形法第一節 線性規劃問題及其數學模型建模產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1解解: : 設該公司應制造產品設該公司應制造產品I,II分別為分別為x1 1, ,x2 2件件則則, ,目標函數目標函數 max z = 2 x1 + 1 x2 約束條件約束條件 0 x1 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(

8、h)1 15利潤(h)2 1解解: : 設該公司應制造產品設該公司應制造產品I,II分別為分別為x1 1, ,x2 2件件則則, ,目標函數目標函數 max z = 2 x1 + 1 x2 約束條件約束條件 0 x1 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模產品I產品II每天可用能力設備A(h)0515設備B(h)6224設備C(h)1 15利潤(h)2 1解解: : 設該公司應制造產品設該公司應制造產品I,II分別為分別為x1 1, ,x2 2件件則則,

9、 ,目標函數目標函數 max z = 2 x1 + 1 x2 約束條件約束條件 0 x1 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20非負性約束運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型例例2 2 靠近某河流有2個化工廠，流經第1化工廠的河流流量為500萬立方米/天，兩個工廠之間有一條流量為200萬立方米/天的支流。第1化工廠每天排污2萬立方米，第2化工廠每天排污1.4萬立方米。從第1化工廠排出的污水流到第2化工廠前，有20%可自然凈化。根據環保要求，河流中污水含量不能大于0.2%。這兩個工廠污水處理成本

10、分別是1000元/萬立方米和800元/萬立方米，問在滿足環保要求的前提下，每個工廠應處理多少污水使總的污水處理費用最小。運籌學運籌學-線性規劃及單純形法線性規劃及單純形法工廠1工廠2500萬m3/天200萬m3/天排污量2萬m3/天治污成本：1000元/萬m3排污量1.4萬m3/天治污成本：800元/萬m3污水含量不大于0.2%x1x2(2-x1)/500=0.2%0.8(2-x1)+(1.4-x2)/700=0.2%x1=2,x2=1.4Min z=1000 x1+800 x2運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型例例3 3 捷運公司擬在下一年度的

11、1-4月的4個月內需租用倉庫堆放物資。已知各月所需倉庫面積列于表1。倉庫租借費用隨合同期而定，期限越長，折扣越大，具體數字見表2。租借倉庫的合同每月初都可以辦理，每份合同具體規定租用面積數和期限。因此該廠可根據需要，在任何一個月初辦理租借合同。每次辦理時可簽一份，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優決策，使所付租借費用最小。月份1234所需面積(100m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型例例3

12、3 捷運公司擬在下一年度的1-4月的4個月內需租用倉庫堆放物資。已知各月所需倉庫面積列于表1。倉庫租借費用隨合同期而定，期限越長，折扣越大，具體數字見表2。租借倉庫的合同每月初都可以辦理，每份合同具體規定租用面積數和期限。因此該廠可根據需要，在任何一個月初辦理租借合同。每次辦理時可簽一份，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優決策，使所付租借費用最小。分析目標約束租借費用最小租借費用由每月初制定的不同的租借合同決定租借合同即租期和租借面積每月的租借面積因此可以將決策變量設為每月初簽訂的合同類型運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問

13、題及其數學模型建模解解: : 設則設則xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的月的租借面積合同。即租借面積合同。即x11 表示表示1月份簽訂的合同期限為月份簽訂的合同期限為1個月的租借面積個月的租借面積x12表示表示1月份簽訂的合同期限為月份簽訂的合同期限為2個月的租借面積個月的租借面積x13表示表示1月份簽訂的合同期限為月份簽訂的合同期限為3個月的租借面積個月的租借面積x14表示表示1月份簽訂的合同期限為月份簽訂的合同期限為4個月的租借面積個月的租借面積月份1234所需面積(100m2)15102012表2合同租借期限(月 )1234合同期內租金（元/1

14、00m2)2800450060007300表1運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模解解: : 設則設則xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的月的租借面積合同。即租借面積合同。即x11 表示表示1月份簽訂的合同期限為月份簽訂的合同期限為1個月的租借面積個月的租借面積x12表示表示1月份簽訂的合同期限為月份簽訂的合同期限為2個月的租借面積個月的租借面積x13表示表示1月份簽訂的合同期限為月份簽訂的合同期限為3個月的租借面積個月的租借面積x14表示表示1月份簽訂的合同期限為月份簽訂的合同期限為4個月的租借面積個

15、月的租借面積x21 表示表示2月份簽訂的合同期限為月份簽訂的合同期限為1個月的租借面積個月的租借面積x22表示表示2月份簽訂的合同期限為月份簽訂的合同期限為2個月的租借面積個月的租借面積x23表示表示2月份簽訂的合同期限為月份簽訂的合同期限為3個月的租借面積個月的租借面積x31表示表示3月份簽訂的合同期限為月份簽訂的合同期限為1個月的租借面積個月的租借面積x32 表示表示3月份簽訂的合同期限為月份簽訂的合同期限為2個月的租借面積個月的租借面積x41表示表示4月份簽訂的合同期限為月份簽訂的合同期限為1個月的租借面積個月的租借面積運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問

16、題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(100m2)

17、15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1合同期為一個月的租金運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21

18、+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(100m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1合同期為兩個月的租金運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z = 2800(x

19、11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(100m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1合同期為三個月的租金運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性

20、規劃問題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(100

21、m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1合同期為四個月的租金運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+

22、x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(100m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1一月份的租借面積約束運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z = 280

23、0(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(100m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1二月份的租借面積約束運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節

24、 線性規劃問題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(

25、100m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1三月份的租借面積約束運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x

26、14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(100m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1四月份的租借面積約束運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z =

27、2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(100m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1非負性約束運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線

28、性規劃問題及其數學模型建模解解: : 設設xij表示該公司在第表示該公司在第i月初簽訂的期限為月初簽訂的期限為j個個月的租借面積合月的租借面積合同。則同。則目標函數：目標函數：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面積(10

29、0m2)15102012表2合同租借期限(月 )1234合同期內租金（元/100m2)2800450060007300表1說明：建模時我們所設的決策變量（ x11,x21,x31,x41）,(x12,x22,x32),(x13,x23), x14只是說明一月份我們只是說明一月份我們最多可以簽署四份期限不同的合同最多可以簽署四份期限不同的合同,二月份可以簽署三份期限不二月份可以簽署三份期限不同的合同同的合同,三月份可以簽署兩份期限不同的合同三月份可以簽署兩份期限不同的合同,四月份一份合同四月份一份合同.這只是一種可能范圍這只是一種可能范圍,并不代表最終最優解中一定是要在一月份并不代表最終最優解中

30、一定是要在一月份簽署四份簽署四份,二月份簽三份等等二月份簽三份等等.如該題目的最優解為如該題目的最優解為:x11=3x31=8x14=12運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型構成要素模型構成要素變量（決策變量）目標函數約束條件1.2 線性規劃問題的數學模型決策者通過控制和決定決策變量來選擇和確定不同的方案、措施min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21+x22

31、+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型構成要素模型構成要素變量（決策變量）目標函數約束條件1.2 線性規劃問題的數學模型決策變量的線性函數，根據優化目標為max,minmin z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+

32、x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型構成要素模型構成要素變量（決策變量）目標函數約束條件1.2 線性規劃問題的數學模型反映為實現目標所受到的資源的約束，為不等式或等式。min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+

33、x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型假設模型假設比例性（或固定規模報酬）可疊加性連續性1.2 線性規劃問題的數學模型max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型假設模型假設比例性（或

34、固定規模報酬）可疊加性連續性1.2 線性規劃問題的數學模型規模報酬遞增：企業的生產規模擴大后，收益增加的幅度要大于規模擴大的幅度，或者說隨著生產能力和產量的擴大，單位產品的成本會隨之下降。比如：投資1000元獲得利潤150元，投資2000元可獲得利潤400元。 反之稱規模報酬遞減。max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型假設模型假設比例性（或固定規模報酬）可疊加性連續性1.2 線性規劃問題的數學模型每個決策變量對目

35、標函數和約束方程的影響是獨立于其它變量的，目標函數值是每個決策變量對目標函數的總和。 max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型假設模型假設比例性（或固定規模報酬）可疊加性連續性1.2 線性規劃問題的數學模型決策變量取連續值。max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節

36、線性規劃問題及其數學模型模型假設模型假設比例性（或固定規模報酬）可疊加性連續性確定性1.2 線性規劃問題的數學模型所有參數都是確定的參數，不包含隨機因素。max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型一般形式模型一般形式1.2 線性規劃問題的數學模型max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+

37、a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14約束條件：約束條件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x3

38、1+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20( (假定有假定有n n個決策變量個決策變量, ,m m個約束個約束) )運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型和式模型和式1.2 線性規劃問題的數學模型),.,1(0),.,1()(min)max(11njxmibxaxczjinjjijnjjj，或或max(max(或或min)z=cmin)z=c1 1

39、x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型和式模型和式1.2 線性規劃問題的數學模型),.,1(0),.,1()(min)ma

40、x(11njxmibxaxczjinjjijnjjj，或或max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節

41、線性規劃問題及其數學模型模型向量形式模型向量形式1.2 線性規劃問題的數學模型0)(min)max(1XbxPCXznjjj，或或C=（c1,c2,cn)max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1

42、 1,x,x2 2,x,xn n 00運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型向量形式模型向量形式1.2 線性規劃問題的數學模型0)(min)max(1XbxPCXznjjj，或或x1x2.xnmax(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+

43、a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型向量形式模型向量形式1.2 線性規劃問題的數學模型0)(min)max(1XbxPCXznjjj，或或mnmmnnnaaaaaaaaaPPP.),.,(21222211121121max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，

44、）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型向量形式模型向量形式1.2 線性規劃問題的數學模型0)(min)max(1XbxPCXznjjj，或或mbbb21max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1

45、111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型向量形式模型向量形式1.2 線性規劃問題的數學模型0)(min)max(1XbxPCXznjjj，或或nnnnxcxcxcxxxccc22112121max

46、(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型向量形式模型向量形式1.2 線性規劃

47、問題的數學模型0)(min)max(1XbxPCXznjjj，或或mnmnnnmmbbbxaaaxaaaxaaa21212222121121111P2PnPbmax(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx

48、x1 1,x,x2 2,x,xn n 00運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型模型矩陣和向量形式模型矩陣和向量形式1.2 線性規劃問題的數學模型0)(min)max(XbAXCXz，或或mnmnmmnnbbbxxxaaaaaaaaa2121212222111211),(或AXb運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式0maxXbAXCXz標準形式的特征?1 目標函數 最大化運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式0maxXbAXCXz

49、標準形式的特征?1 目標函數 最大化2 b0運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式0maxXbAXCXz標準形式的特征?1 目標函數 最大化2 b03 約束條件為等號運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式0maxXbAXCXz標準形式的特征?1 目標函數 最大化2 b03 約束條件為等號4 決策變量X 0運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式0maxXbAXCXz1 目標函數 min z化標準形式的方法化標準形式的方

50、法令z=-z則min z=CX 等價于max z= - CX)4 , 3 , 2 , 1(042634334min4213212121jxxxxxxxxxxxzj)4 , 3 , 2 , 1(042634334max4213212121jxxxxxxxxxxxzj令z=-z運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式0maxXbAXCXz1 目標函數 min z2 bi0化標準形式的方法化標準形式的方法第i個約束方程兩邊乘以(-1)-ai1-ai2-ain=-bi)4 , 3 , 2 , 1(042634334max4213212121jx

51、xxxxxxxxxxzj)4 , 3 , 2 , 1(042634334max4213212121jxxxxxxxxxxxzj運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式0maxXbAXCXz1 目標函數 min z2 bi03 約束條件或0化標準形式的方法化標準形式的方法若0，則加松弛變量若0，則減剩余變量（松弛變量，剩余變量均非負） 6x1+2x20標準化為6x1+2x2+x3=0 10 x1+12x20標準化為10 x1+12x2- x4 =0這里x3， x4 0運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及

52、其數學模型1.3 標準形式0maxXbAXCXz1 目標函數 min z2 bi03 約束條件或04 決策變量0或無約束 化標準形式的方法化標準形式的方法若xi0，則令xi=- xi若xi 無約束,則令xi= xi- xi xi, xi 0 6x1+2x2=0 X2無約束標準化為6x1+2x2- 2x2=0這里x2 ， x2 0運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz例例3 3 將下述線性規劃化為標準形式將下述線性規劃化為標準

53、形式分析1 目標函數不標準運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz例例3 3 將下述線性規劃化為標準形式將下述線性規劃化為標準形式分析1 目標函數不標準2 b不標準運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz例例3 3 將下述線性規劃化為標準形式將下述線性規劃化為

54、標準形式分析1 目標函數不標準2 b不標準3 決策變量不標準運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz例例3 3 將下述線性規劃化為標準形式將下述線性規劃化為標準形式分析1 目標函數不標準2 b不標準3 決策變量不標準4 不符合等式約束運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，約束加松弛變量x4,約束減去剩余變量x5,

55、約束兩邊乘以-1，則模型等價于取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，約束加松弛變量x4,約束減去剩余變量x5,約束兩邊乘以-1，則模型等價于取值無約束321321321321321, 0, 0632

56、44239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，約束加松弛變量x4,約束減去剩余變量x5,約束兩邊乘以-1，則模型等價于取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx4223

57、5 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，約束加松弛變量x4,約束減去剩余變量x5,約束兩邊乘以-1，則模型等價于取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054

58、3321xxxxxx 3321332maxxxxxz運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，約束加松弛變量x4,約束減去剩余變量x5,約束兩邊乘以-1，則模型等價于取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz運籌學運籌學-線性規劃及單純形法線性

59、規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，約束加松弛變量x4,約束減去剩余變量x5,約束兩邊乘以-1，則模型等價于取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型1.3 標準形式求解求解解：令x1=-x1

60、，x3-x3=x3，z=-z，約束加松弛變量x4,約束減去剩余變量x5,約束兩邊乘以-1，則模型等價于取值無約束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz運籌學運籌學-線性規劃及單純形法線性規劃及單純形法第一節 線性規劃問題及其數學模型練習1取值無約束43214321432143214321, 0,2321422245243minxxxxxxxxxxxxxxxxx