【正文】 第一章 線性規(guī)劃與單純形方法 第一節(jié) 線性規(guī)劃問題及數(shù)學(xué)模型 線性規(guī)劃（ Linear Programming)創(chuàng)始人： 1947年美國人 （ Dantzing） 線性規(guī)劃（概論） 線性規(guī)劃（ Linear Programming)創(chuàng)始人： 1947年美國人 （ Dantzing） 1951年提出單純形算法（ Simpler） 線性規(guī)劃（概論） 線性規(guī)劃（ Linear Programming)創(chuàng)始人： 1947年美國人 （ Dantzing） 1951年提出單純形算法（ Simpler） 1963年 Dantzing寫成“ Linear Programming and Extension” 線性規(guī)劃（概論） 線性規(guī)劃（ Linear Programming)創(chuàng)始人： 1947年美國人 （ Dantzing） 1951年提出單純形算法（ Simpler） 1963年 Dantzing寫成 “ Linear Programming and Extension” 1979年蘇聯(lián)的 Khachian提出 “ 橢球法 ” 線性規(guī)劃（概論） 線性規(guī)劃（ Linear Programming)創(chuàng)始人： 1947年美國人 （ Dantzing） 1951年提出單純形算法（ Simpler） 1963年 Dantzing寫成 “ Linear Programming and Extension” 1979年蘇聯(lián)的 Khachian提出 “ 橢球法 ” 1984年印度的 Karmarkar提出“投影梯度法” 線性規(guī)劃（概論） 線性規(guī)劃（ Linear Programming)創(chuàng)始人： 1947年美國人 （ Dantzing） 1951年提出單純形算法（ Simpler） 1963年 Dantzing寫成“ Linear Programming and Extension” 1979年蘇聯(lián)的 Khachian提出“橢球法” 1984年印度的 Karmarkar提出“投影梯度法” 線性規(guī)劃是研究線性不等式組的理論，或者說是研究（高維空間中）凸多面體的理論，是線性代數(shù)的應(yīng)用和發(fā)展。 1 線性規(guī)劃發(fā)展史 線性規(guī)劃（ Linear Programming)創(chuàng)始人： 1947年美國人 （ Dantzing） 1951年提出單純形算法（ Simpler） 1963年 Dantzing寫成“ Linear Programming and Extension” 1979年蘇聯(lián)的 Khachian提出“橢球法” 1984年印度的 Karmarkar提出“投影梯度法” 線性規(guī)劃是研究線性不等式組的理論，或者說是研究（高維空間中）凸多面體的理論，是線性代數(shù)的應(yīng)用和發(fā)展。 2 線性規(guī)劃基本概念 生產(chǎn)計劃問題 ?如何合理使用有限的人力 ， 物力和資金 ， 使得收到最好的經(jīng)濟(jì)效益 。 ?如何合理使用有限的人力 ， 物力和資金 ， 以達(dá)到最經(jīng)濟(jì)的方式 ， 完成生產(chǎn)計劃的要求 。 例 1 生產(chǎn)計劃問題 （ 資源利用問題 ） 某 家具廠生產(chǎn)桌子和椅子兩種家具 。桌子售價 50元 /個 ， 椅子銷售價格 30元 /個 ， 生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種 。 生產(chǎn)一個桌子需要木工 4小時 ， 油漆工 2小時 。 生產(chǎn)一個椅子需要木工 3小時 ， 油漆工 1小時 。 該廠每個月可用木工工時為 120小時 ， 油漆工工時為50小時 。 問該廠如何組織生產(chǎn)才能使每月的銷售收入最大 ？ 桌子 椅子 總工時 （小時） 木工 （小時） 4 3 120 油漆工 2 1 50 價格 （元 /個） 50 30 解： 將此問題列成圖表如下： 將一個實際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟： 將一個實際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟： 1． 確定決策變量： x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量 解： 將一個實際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟： 1． 確定決策變量： x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量 2． 確定目標(biāo)函數(shù)： 家具廠的目標(biāo)是銷售收入最大 max z=50x1+30x2 解：將一個實際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟： 1． 確定決策變量： x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量 2． 確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大 max z=50x1+30x2 3． 確定約束條件： 4x1+3x2 ? 120（ 木工工時限制 ） 2x1+x2 ? 50 （ 油漆工工時限制 ） 解： 將一個實際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟： 1． 確定決策變量： x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量 2． 確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大 max z=50x1+30x2 3． 確定約束條件： 4x1+3x2 ? 120（ 木工工時限制 ） 2x1+x2 ? 50 （ 油漆工工時限制 ） 4． 變量取值限制： 一般情況 ， 決策變量只取正值 （ 非負(fù)值 ） x1 ? 0, x2 ? 0 解： 將一個實際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟： 1． 確定決策變量： x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量 2． 確定目標(biāo)函數(shù)： 家具廠的目標(biāo)是銷售收入最大 max z=50x1+30x2 3． 確定約束條件： 4x1+3x2?120（ 木工工時限制 ） 2x1+x2 ? 50 （ 油漆工工時限制 ） 4． 變量取值限制： 一般情況 ， 決策變量只取正值 （ 非負(fù)值 ） x1 ? 0, x2 ? 0 數(shù)學(xué)模型 max S=50x1+30x2 . 4x1+3x2 ? 120 2x1+ x2 ? 50 x1,x2 ? 0 線性規(guī)劃數(shù)學(xué)模型三要素： 決策變量 、 約束條件 、 目標(biāo)函數(shù) 一、問題的提出 產(chǎn) 品 資 源 I II 可 利 用 資 源 設(shè) 備 1 2 8 材 料 A 4 0 16 材 料 B 0 4 12 單 位 利 潤 （ 元 ） 2 3 例 2 某廠生產(chǎn)兩種產(chǎn)品，下表給 出了單位產(chǎn)品所需資源及單位產(chǎn)品 利潤 問：應(yīng)如何安排生產(chǎn)計劃，才能使 總利潤最大？ 解： ：設(shè)產(chǎn)品 I、 II的產(chǎn)量分 別為 x x2 ：設(shè)總運費為 z，則有： max z = 2 x1 + 3 x2 ： x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1， x2≥0 3 線性規(guī)劃問題的數(shù)學(xué)模型 例 3 營養(yǎng)配餐問題 假定一個成年人每天需要從食物中獲得 3000千卡的熱量、 55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費用最小？ 序號 食品名 稱 熱 量 （千卡） 蛋白質(zhì)（克） 鈣 （毫克） 價格 ( 元 /kg ） 1 豬肉 1 0 0 0 50 4 0 0 14 2 雞蛋 8 0 0 60 2 0 0 6 3 大米 9 0 0 20 3 0 0 3 4 白菜 2 0 0 10 5 0 0 2 各種食物的營養(yǎng)成分表 每天需要