線性規劃問題舉例作為上述線性規劃問題的數學模型的應用，下面將對三個問題建立線性規劃模型．這些問題以及其他線性規劃問題的更詳細的討論，在本書的第三部分給出．運輸問題一個制造廠希望把若干單位的產品從幾個倉庫發送到若干個零售點．每個零售點都需要一定數量的產品，而每個倉庫也能供應一定數量的產品．這里作如下規定：m=倉庫的數目．n=零售點的數目．ai=第i個倉庫能供應產品的總量．bj=第j個零售點所需產品的總量．xij=從倉庫i運到零售點j的產品數量．這里xij是待定的未知量．如作出表格(當m=2，n=3)則可以看出從倉庫1運出產品的總量能用線性方程表示為x11＋x12＋x13=a1．(2．1)對于倉庫2有x21＋x22＋x23=a2．(2．2)也要考慮三個零售點所需產品的總量，用下列方程表示：制造廠知道從倉庫i運到零售點j一個單位產品的費用為cij．我們還假定費用關系是線性的，即運送xij單位的費用為cijxij．制造廠希望確定，從每個倉庫到每個零售點，要運送多少數量的產品，才能使全部運輸費用為極小．使費用為極小的目標，可通過極小化線性費用函數c11x11＋c12x12＋c13x13＋c13x13＋c21x21＋c22x22＋c23x23(2．4)來實現．因為一個非負的xij表示從倉庫i到零售點j的運輸量，所以我們要求全部變量xij≥0．把等式(2．1)至(2．3)，目標函數(2．4)和變量非負的條件聯合起來，則m=2，n=3的運輸問題就可以表示成下列線性規劃問題：作為運輸問題的一個數值例子，讓我們考慮兩個倉庫三個零售點的問題，其中可把這個問題寫成線性規劃問題如下：我們注意上述方程可代表一組會計上的帳目，它們記錄了倉庫與零售點之間貨物流通量．類似地，許多線性規劃問題的方程只不過是會計步驟的數學表達．下表給出一個平凡解即x11=0，x12=5，x13=0，x21=8，x22=0，x28=2．相應的目標函數值是2x12＋3x21＋x23=2·5＋3·8＋1·2=36．第二組解(許多組解中的一組)是其目標函數值為26．由第十章的方法可以證明，這個解是極小解．(對于此例，讀者應能驗證，任何其他解所得到的運輸費用都大于26．)活動性分析問題某公司掌握了幾種數量固定的資源(如原材料，勞動力和設備)，合起來能生產若干不同產品中的一種或這些產品的某種組合．已知公司每生產一個單位的j種產品所需要的i種資源的數量，同時也已知每生產一個單位的j種產品所能獲得利潤的數量．公司希望生產的產品組合能使其獲得的總利潤為最大．對此問題可以作如下定義：m=資源的種類數．n=產品的種類數．aij=生產一個單位的j種產品所需i種資源的數量．bi=i種資源的最大可用量．cj=生產單位j種產品的利潤數．xj=j種產品的活動水平(或產量)．有時稱aij為投入－產出系數或技術系數．使用i種資源的總量可表示為線性函數ai1x1＋ai2x2＋…＋ainxn．因為上述使用i種資源的總量必須小于或等于i種資源的最大可用量，所以對i種資源有下列線性不等式：ai1x1＋ai2x2＋…＋ainxn≤bi．由于負的xj沒有實際意義，所以我們要求所有xj≥0．生產xj單位的j種產品所獲得的利潤為cjxj．上述極大化利潤函數問題的數學表達如下：如第二章將討論的那樣，一個不等式可等價于非負變量的一個等式，所以上述問題是一般線性規劃問題的另一種提法．為了說明上述模型，我們考慮在Gass[172]中所給出的例子．一個生產家具的公司計劃生產兩種產品——椅子和桌子，其可用資源包括400板英尺①的紅木板和450個工時．已知生產每把椅子需用紅木板5板英尺，10個工時，其利潤為45美元，而生產每張桌子需用紅木板20板英尺和15個工時，其利潤為80美元．問題是要確定，在資源約束范圍內，公司生產多少把椅子和多少張桌子，其總利潤最大．生產一把椅子需消耗5板英尺的木板和10個工時，而生產一張桌子需消耗20板英尺木板和15個工時．令x1為椅子的生產量，x2為桌子的生產量．上述活動性分析問題，用線性規劃的形式可寫成下述極大化利潤函數的問題：當然，對于上述約束條件，具有很多組可能的解．例如，僅生產椅子的解為x1=45，x2=0，其利潤為45×45=2025美元；僅生產桌子的解為x1=0，x2=20，其利潤為80×20=1600美元．求出的最優解為：生產椅子x1=24，生產桌子x2=14，其利潤為2200美元．食物配料問題這里給出若干不同食物的營養成分含量．例如，我們所考慮的不同食物中，已知每英兩食物含有多少毫克的鐵或磷，我們也已知每種營養成分的最低日需要量．因為每英兩食物的費用是已知的，所以問題是，在滿足營養成分的最低日需要量的條件下，確定費用最低的食物配方．定義m=營養成分的種類數．n=食物的種類數．aij=在每一英兩的第j種食物中含有第i種營養成分的毫克數．bi=第i種營養成分最低日需要量的毫克數．cj=每英兩第j種食物的費用．xj=購買第j種食物的英兩數(xj≥0)．購買的所有食物中含有第i種營養成分的總量可表示為ai1x1＋ai22＋…＋ainxn．因為這一總量必須大于或等于第i種營養成分的最低日需要量，這個線性規劃問題可表示如下：下面給出關于食物配料問題的一個簡單數值例題．考慮兩種食物x1和x2以及含有維生素B1、磷、鐵三種營養成分的食物配料問題．每種食物中含有各種營養成分的數量(毫克/英兩，簡寫為mg/oz)列于下表對于這兩種食物的飲食，至少要求獲得維生素毫克，磷毫克，鐵毫克．x1的費用為2美分/英兩，x2的費用為5/3美分/英兩．根據前述一般食物配料問題的格式，本例相應的線性規劃問題如下：這個問題的最優解為x1=20/7英兩，x2=40/7英兩的混合飲食，其費用為美元．把這一結果與單純用食物x1或單純用食物x2的解進行費用比較，讀者將會受到啟發．對于上面的一些例子，以及所有歸結為線性規劃問題一般形式的問題，我們都假定某些基本的線性關系式成立．線性規劃的比例性要求，可通過活動性分析和食物配料問題來說明，在這些問題中，我們假定活動(指產量或配料)水平的改變會引起所需資源或營養成分按比例地改變．當我們對全部生產所用的資源求和或對全部食物中的營養成分求和時，也用到了可加性的要求．雖然我們有權懷疑這些假定的普遍性，但它們的合理性或近似性已使它們在現實世界中得到大量重要的應用．附注最早的線性規劃方法的應用，分為三種主要類型：軍事應用——來源于空軍SCOOP方案，各種經濟間的Leontief投入－產出模型以及有關零和二人對策與線性規劃之間關系的問題．這些應用領域已得到擴大和發展，但線性規劃應用的重點已經轉移到工業領域．此外，線性規劃問題的應用已經發展到社會和城市的各種問題，例如教育、法律實施、衛生事業、環境保護等應用方面的書目包括在下述分類的文獻目錄中：農業、合同裁決、工業、經濟分析、軍事、人員分配、生產計劃與存貨控制、結構設計、交通研究、運輸與網絡理論、貨郎擔問題及其他應用．有關補充