線性規(guī)劃經(jīng)典運(yùn)籌學(xué)

1、第一章 線性規(guī)劃（Linear Programming )運(yùn)籌學(xué)的一個(gè)重要分枝研究較早發(fā)展較快理論較成熟應(yīng)用極為廣泛簡(jiǎn)記為L(zhǎng)P1典型的線性規(guī)劃的在經(jīng)濟(jì)管理上的應(yīng)用舉例: 1、合理利用線材問題:現(xiàn)有一批長(zhǎng)度一定的鋼管,由于生產(chǎn)的需要,要求截出不同規(guī)格的鋼管若干。試問應(yīng)如何下料，既滿足了生產(chǎn)的需要，又使得使用的原材料鋼管的數(shù)量最少。2、配料問題：用若干種不同價(jià)格不同成分含量的原料，用不同的配比混合調(diào)配出一些不同價(jià)格不同規(guī)格的產(chǎn)品。在原料供應(yīng)量的限制和保證產(chǎn)品成分的含量的前提下，如何獲取最大的利潤。23、投資問題：從不同的投資項(xiàng)目中選出一個(gè)投資方案，使投資的回報(bào)最大。 4、產(chǎn)品生產(chǎn)計(jì)劃：合理充分利用

2、廠里現(xiàn)有的人力、物力、才力，作出最優(yōu)的產(chǎn)品生產(chǎn)計(jì)劃，使得工廠獲利最大。5、勞動(dòng)力安排：某單位由于工作需要，在不同時(shí)間段需要不同數(shù)量的勞動(dòng)力，在每個(gè)勞動(dòng)力工作日連續(xù)工作8小時(shí)的規(guī)定下，如何安排勞動(dòng)力，才能用最少的勞動(dòng)力來滿足工作的需要。6、運(yùn)輸問題：一個(gè)公司有若干個(gè) 生產(chǎn)單位與銷售單位，根據(jù)各生產(chǎn)單位的產(chǎn)量及銷售單位的情況，如何制定調(diào)運(yùn)方案，將產(chǎn)品運(yùn)到各銷售單位而總的運(yùn)費(fèi)最少。3線性規(guī)劃研究的問題： 1、在現(xiàn)有的人、財(cái)、物等資源的條件下， 研究如何合理地計(jì)劃、安排，可使得 某一目標(biāo)達(dá)到最大， 尋求在一定約束 條件下使某個(gè)指標(biāo)達(dá)到最優(yōu)如產(chǎn)量、利潤等。2、在任務(wù)確定后，如何計(jì)劃、安排，使 用最少的人

3、、財(cái)、物等資源，去實(shí)現(xiàn) 該任務(wù)，如使生產(chǎn)成本、費(fèi)用最少等。41.1 線性規(guī)劃的基本概念1.1.1 線性規(guī)劃模型一、 線性規(guī)劃問題舉例5例1 （生產(chǎn)安排問題）假定某工廠生產(chǎn)甲、乙、丙三種產(chǎn)品，每種產(chǎn)品都要經(jīng)過三種不同的工序加工。每一件產(chǎn)品所需要的加工時(shí)間（分鐘）和每天對(duì)各道工序的加工能力（每天多少分鐘）以及銷售各種產(chǎn)品的單位利潤如下表所示：假定所生產(chǎn)的三種產(chǎn)品都能全部售出，問這三種產(chǎn)品每天要各生產(chǎn)多少件才能使得獲得的利潤最大？設(shè)：決策變量目標(biāo)函數(shù)6對(duì)第三道工序，有對(duì)第二道工序，有對(duì)第一道工序，有約束條件非負(fù)性約束條件問題歸結(jié)為：目標(biāo)函數(shù)：線性7例2 （營養(yǎng)搭配問題） 如果有甲、乙、丙、丁四種食品

4、，都含有不同成分的維生素，其含量和單價(jià)如下表所示現(xiàn)在我們希望每天得到的維生素不少于所規(guī)定的最低需要量，問應(yīng)該如何搭配各種食品才能使所花的費(fèi)用最少？解：8約束條件：決策變量：?jiǎn)栴}歸結(jié)為：線性9二、線性規(guī)劃模型的建立 1、建模的一般步驟： 步驟一：確定決策變量 即用變量取不同的值來表示可供選擇的各種不同方案步驟二：建立目標(biāo)函數(shù)即找到目標(biāo)值與決策變量的數(shù)量關(guān)系步驟三：確定約束條件即決策變量所受到的外界條件的制約。約束條件一般為決策變量的等式或不等式要求：目標(biāo)函數(shù)與約束條件均是線性的， 且目標(biāo)函數(shù)只能是一個(gè)。102、線性規(guī)劃模型的一般形式：決策變量約束方程非負(fù)約束 目標(biāo)函數(shù)maximumminimum

5、subject to11三、線性規(guī)劃求解：四、線性規(guī)劃應(yīng)用舉例計(jì)算機(jī)應(yīng)用軟件12時(shí)間所需售貨員 人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3 福安商場(chǎng)是個(gè)中型的百貨商場(chǎng)，它對(duì)售貨人員的 需求經(jīng)過統(tǒng)計(jì)分析如下所示：為保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應(yīng)該如何安排售貨人員的作息，既滿足了工作的需要，又使配備的售貨人員的人數(shù)最少？解13時(shí)間所需售貨員人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人約束條件 :星期日 售貨員人數(shù)要求: 星期一 售貨員人數(shù)要求: 星期二

6、 售貨員人數(shù)要求: 星期三 售貨員人數(shù)要求: 星期四 售貨員人數(shù)要求: 星期五 售貨員人數(shù)要求: 星期六 售貨員人數(shù)要求: 數(shù)學(xué)模型:非負(fù)約束 :14數(shù)學(xué)模型:解得: 15時(shí)間所需售貨員 人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3 福安商場(chǎng)是個(gè)中型的百貨商場(chǎng)，它對(duì)售貨人員的 需求經(jīng)過統(tǒng)計(jì)分析如下所示：為保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應(yīng)該如何安排售貨人員的作息，既滿足了工作的需要，又使配備的售貨人員的人數(shù)最少？解16方案下料數(shù)(根)長(zhǎng)度例4 某工廠要做100套鋼架,每套用長(zhǎng)為2.9m,2.1m,

7、 和1.5m的圓鋼各一根,已知原料每根長(zhǎng)7.4m, 問應(yīng)如何下料,可使所用原料最省.分析:每根原料做一套鋼架,下角料：0.9m用套裁方式下料方案：17方案下料數(shù)(根)長(zhǎng)度下料方案：18方案下料數(shù)(根)長(zhǎng)度例4 某工廠要做100套鋼架,每套用長(zhǎng)為2.9m,2.1m, 和1.5m的圓鋼各一根,已知原料每根長(zhǎng)7.4m, 問應(yīng)如何下料,可使所用原料最省.下料方案：最優(yōu)下料方案： 按方案1下料30根，方案2下料10根，方案4下料50根，共需原料90根。19例5 (產(chǎn)品配套問題）假定一個(gè)工廠的甲、乙、丙三個(gè)車間生產(chǎn)同一個(gè)產(chǎn)品，每件產(chǎn)品包括4個(gè)A零件，和3個(gè)B零件。這兩種零件由兩種不同的原材料制成，而這兩種

8、原材料的現(xiàn)有數(shù)額分別為100克和200克。每個(gè)生產(chǎn)班的原材料需要量和零件產(chǎn)量如下表所示。問這三個(gè)車間各應(yīng)開多少班才能使這種產(chǎn)品的配套數(shù)達(dá)到最大約束條件為：20三個(gè)車間共生產(chǎn)A零件：三個(gè)車間共生產(chǎn)B零件非線性要求：目標(biāo)函數(shù)：目標(biāo)函數(shù) Z=x4線性21數(shù)學(xué)模型：線性規(guī)劃問題22例6 （多周期動(dòng)態(tài)生產(chǎn)計(jì)劃問題）華津機(jī)器制造廠專為拖拉機(jī)廠配套生產(chǎn)柴油機(jī)，今年頭四個(gè)月收到的定單數(shù)量分別為3000臺(tái)、4500臺(tái)、3500臺(tái)、5000臺(tái)。該廠正常生產(chǎn)每月可生產(chǎn)3000臺(tái)，利用加班還可生產(chǎn)1500臺(tái)，正常生產(chǎn)成本為每臺(tái)5000元，加工生產(chǎn)還要追加1500元，庫存成本為每臺(tái)每月200元。問華津廠如何組織生產(chǎn)才能

9、使生產(chǎn)成本最低？分析：設(shè)C=成本=四個(gè)月正常生產(chǎn)的成本+四個(gè)月加班生產(chǎn)的成本+四個(gè)月庫存成本約束條件：23需求約束：第4個(gè)月第3個(gè)月第2個(gè)月第1個(gè)月生產(chǎn)能力約束：數(shù)學(xué)模型：四個(gè)月定單數(shù)量分別為3000臺(tái)、4500臺(tái)、3500臺(tái)、5000臺(tái)每月可生產(chǎn)3000臺(tái)，利用加班還可生產(chǎn)1500臺(tái)庫存約束：24 例7 （ 投資證券組合的選擇）某人有一筆50萬元的資金可用于長(zhǎng)期投資，可供選擇的投資機(jī)會(huì)包括購買國庫券、購買公司債券、投資房地產(chǎn)、購買股票或銀行保值儲(chǔ)蓄等。不同的投資方式的具體參數(shù)如下表。投資者希望投資組合的平均年限不超過5年，平均年收益率不低于13%，平均風(fēng)險(xiǎn)系數(shù)不超過4，平均收益的增長(zhǎng)潛力不低

10、于10%。問在滿足上述要求的前提下投資者該如何選擇投資組合使平均年收益率最高？投資方式投資期限（年）年收益率（%）風(fēng)險(xiǎn)系數(shù)增長(zhǎng)潛力（%）國庫券31110公司債券1015315房地產(chǎn)625830股票220620短期定期存款11015長(zhǎng)期保值儲(chǔ)蓄512210現(xiàn)金存款0300方法一：Z=平均年收益率25投資方式投資期限（年）年收益率（%）風(fēng)險(xiǎn)系數(shù)增長(zhǎng)潛力（%）國庫券31110公司債券1015315房地產(chǎn)625830股票220620短期定期存款11015長(zhǎng)期保值儲(chǔ)蓄512210現(xiàn)金存款0300投資組合的平均年限5年平均年收益率13%平均風(fēng)險(xiǎn)系數(shù) 4，平均收益的增長(zhǎng)潛力 10%Z=平均年收益率資金50萬

11、26投資年限約束：收益率約束：投資方式投資期限（年年收益率（%）風(fēng)險(xiǎn)系數(shù)增長(zhǎng)潛力（%國庫券31110公司債券1015315房地產(chǎn)625830股票220620短期定期存款11015長(zhǎng)期保值儲(chǔ)蓄512210現(xiàn)金存款0300投資組合的平均年限5年平均年收益率13%平均風(fēng)險(xiǎn)系數(shù) 4，平均收益的增長(zhǎng)潛力 10%資金約束：資金50萬27投資方式投資期限（年）年收益率（%）風(fēng)險(xiǎn)系數(shù)增長(zhǎng)潛力（%）國庫券31110公司債券1015315房地產(chǎn)625830股票220620短期定期存款11015長(zhǎng)期保值儲(chǔ)蓄512210現(xiàn)金存款0300投資組合的平均年限5年平均年收益率13%平均風(fēng)險(xiǎn)系數(shù) 4，平均收益的增長(zhǎng)潛力 10

12、%資金50萬增長(zhǎng)潛力約束：風(fēng)險(xiǎn)系數(shù)約束：28數(shù)學(xué)模型：29方法二：數(shù)學(xué)模型：30例1.7（調(diào)和問題）調(diào)和問題：將若干種不同的原料按一定的技術(shù) 要求調(diào)和成不同的產(chǎn)品。目標(biāo)：在滿足產(chǎn)品需求和調(diào)和指標(biāo)的前提下 使調(diào)和成本最小或生產(chǎn)收益最大31例8 新星煉油廠生產(chǎn)三種牌號(hào)的汽油：80#、93#和97#汽油。每種汽油有不同的辛烷值和含硫量的質(zhì)量要求并由三種原料油調(diào)和而成。每種原料也有不同的質(zhì)量指標(biāo)。每種原料每日可用數(shù)量、質(zhì)量指標(biāo)和生產(chǎn)成本如表1，每種汽油的質(zhì)量要求和銷售價(jià)格如表2。問該煉油廠如何安排生產(chǎn)才能使其利潤最大？序號(hào)原料辛烷值含硫量%成本（元/噸可用量（噸/日1直餾汽油621.560020002

13、催化汽油780.890010003重整汽油900.21400500表1表2,R-收益L-利潤則L=R-C，C成本6009001400目標(biāo)函數(shù)L=R-C32目標(biāo)函數(shù)L=R-CR-售價(jià)，L-利潤則L=R-C，C成本約束條件：33原料可用量約束：第1種原料直餾汽油的約束第2種原料催化汽油的約束第3種原料重整汽油的約束決策變量非負(fù)約束：序號(hào)原料辛烷值含硫量%成本（噸/元）可用量（噸/日）1直餾汽油621.560020002催化汽油780.890010003重整汽油900.2140050034序號(hào)原料辛烷值含硫量%成本（噸/元可用量（噸/日1直餾汽油621.560020002催化汽油780.890010003重整汽油900.21400500辛烷值約束：第1種產(chǎn)品80#汽油的辛烷值約束：第2種產(chǎn)品的辛烷值約束：第3種產(chǎn)品的辛烷值約束：35序號(hào)原料辛烷值含硫量%成本（噸/元可用量（噸/日1直餾汽油621.560020002催化汽油780.890010003重整汽油900.21400500含硫量約束：第1種產(chǎn)品80#汽油的含硫量約束：第2種產(chǎn)品的含硫量約束：第3種產(chǎn)品的含硫量約束：36所求數(shù)學(xué)模型為：37本堂課主要內(nèi)容：一、線性規(guī)劃模型的建立 1、建模的一般步驟： 步驟一：