JournalonComputing第一章線(xiàn)性規(guī)劃01線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式03線(xiàn)性規(guī)劃問(wèn)題的單純形方法線(xiàn)性規(guī)劃問(wèn)題的圖解法及其解的性質(zhì)0204線(xiàn)性規(guī)劃問(wèn)題的建模與應(yīng)用CONTENTSPART01線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式突發(fā)公共衛(wèi)生事件下的人員排班問(wèn)題年初，某市出現(xiàn)了一場(chǎng)意想不到的大型傳染性疾病流行，城市的每個(gè)角落都籠罩著緊張和焦慮。衛(wèi)生健康部門(mén)迅速行動(dòng)，緊急抽調(diào)醫(yī)護(hù)人員，組織轄區(qū)內(nèi)所有居民進(jìn)行呼吸道樣本采集以用于檢測(cè)，希望借此控制疫情的蔓延。為了充分利用有限的醫(yī)護(hù)人員資源與高效組織采集工作，衛(wèi)生健康部門(mén)經(jīng)過(guò)精確計(jì)算，確定了周一到周日每天進(jìn)行檢測(cè)所需的醫(yī)護(hù)人員數(shù)量分別為：300,300,450,450,500,700和650。線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式但是，在如此繁重的工作任務(wù)下，他們也深知醫(yī)護(hù)人員需要得到充分的休息才能保持身心健康和高效工作。因此，他們采取了排班制度，規(guī)定每周連續(xù)工作5天后必須休息2天，并且進(jìn)行輪流休息的安排。然而，正當(dāng)衛(wèi)生健康部門(mén)認(rèn)為一切就緒時(shí)，他們卻面臨一個(gè)新的問(wèn)題：如何安排每天值班的醫(yī)護(hù)人員人數(shù)，使得其既能滿(mǎn)足醫(yī)療工作需求，又盡量減少醫(yī)護(hù)人員之間的流動(dòng)，從而降低感染風(fēng)險(xiǎn)呢？一、線(xiàn)性規(guī)劃問(wèn)題的導(dǎo)出現(xiàn)實(shí)社會(huì)活動(dòng)中，常常遇到兩類(lèi)問(wèn)題：若要以最少的資源消耗來(lái)完成一項(xiàng)確定的任務(wù)，如何統(tǒng)籌安排？—如何使成本最?。≡诩榷ㄙY源條件下，如何配置它們，能使完成的任務(wù)量最大？—如何使效益最大！線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式引例1—配比問(wèn)題

用濃度為45％和92％的硫酸配置100噸濃度為80％的硫酸。取45％和92％的硫酸分別為x1噸和x2噸，則有：求解二元一次方程組，得解。兩個(gè)未知數(shù)兩個(gè)方程線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式

如果目的相同，但若有5種不同濃度的硫酸可選（30％，45％，73％，85％，92％）會(huì)出現(xiàn)什么情況呢？取這5種硫酸分別為x1,x2,x3,x4,x5噸，則

問(wèn)：（1）有多少種配比方案？為什么？（2）何為最好？（最優(yōu)的標(biāo)準(zhǔn)是什么？）5個(gè)未知數(shù)兩個(gè)方程線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式5種硫酸價(jià)格分別為：400，700，1400，1900，2500元／噸，則有：觀察：目標(biāo)函數(shù)和約束條件有什么特點(diǎn)？目標(biāo)函數(shù)是線(xiàn)性的；約束條件是線(xiàn)性的；為什么叫線(xiàn)性規(guī)劃？線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式引例2—生產(chǎn)計(jì)劃問(wèn)題某工廠生產(chǎn)A、B、C三種產(chǎn)品，每噸利潤(rùn)分別為2000元，3000元，3000元。生產(chǎn)單位產(chǎn)品所需要的工時(shí)及原材料如表1－1所示。若供應(yīng)的原材料每天不超過(guò)9噸，所能利用的勞動(dòng)力日總工時(shí)為3個(gè)單位。問(wèn)：如何制定日生產(chǎn)計(jì)劃，使三種產(chǎn)品總利潤(rùn)最大？線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式如何制定生產(chǎn)計(jì)劃，使三種產(chǎn)品總利潤(rùn)最大？何為生產(chǎn)計(jì)劃？總利潤(rùn)如何描述？還要考慮什么因素？有什么需要注意的地方（技巧）？最終得到的數(shù)學(xué)模型是什么？問(wèn)題討論線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式引例3-偉恩德公司案例—產(chǎn)品組合問(wèn)題偉恩德公司總裁約翰·希爾對(duì)杰姆小組開(kāi)發(fā)的兩種新產(chǎn)品很有信心，一種是8英尺的鋁框玻璃門(mén)，另一種是4英尺×6英尺的雙把木框窗。公司有三個(gè)工廠，玻璃門(mén)需要工廠1和工廠3的生產(chǎn)能力，木框窗需要工廠2和工廠3的生產(chǎn)能力。已知工廠加工兩種新產(chǎn)品需要的工時(shí)數(shù)據(jù)和預(yù)測(cè)的單位利潤(rùn)。線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式管理部門(mén)需要考慮：1）公司是否應(yīng)該生產(chǎn)這兩種新產(chǎn)品？2）如果生產(chǎn)，兩種新產(chǎn)品的生產(chǎn)組合如何？每周分別生產(chǎn)多少數(shù)量？線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式偉恩德公司產(chǎn)品組合問(wèn)題的數(shù)據(jù)線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式需要回答的三個(gè)問(wèn)題：1）要做出的決策是什么？2）在做出這些決策上有哪些約束條件？3）這些決策的全部績(jī)效測(cè)度是什么？1）要做的決策是兩種產(chǎn)品的生產(chǎn)率（每周生產(chǎn)多少）2）對(duì)決策的約束條件是兩種產(chǎn)品在相應(yīng)工廠里每周生產(chǎn)時(shí)間不能超過(guò)每個(gè)工廠可得到的生產(chǎn)時(shí)間。3）對(duì)這些決策的全部績(jī)效測(cè)度是這兩種產(chǎn)品的總利潤(rùn)。線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式設(shè)兩種產(chǎn)品每周分別生產(chǎn)x1件和x2件。目標(biāo)函數(shù)：總利潤(rùn)最大約束條件：兩種產(chǎn)品在相應(yīng)工廠里每周生產(chǎn)時(shí)間不能超過(guò)每個(gè)工廠可得到的生產(chǎn)時(shí)間。引例4-利博公司廣告組合問(wèn)題

利博(Profit&Gambit)公司生產(chǎn)家用的清潔產(chǎn)品，這是一個(gè)高度競(jìng)爭(zhēng)的市場(chǎng)，公司為了增加市場(chǎng)份額連續(xù)掙扎多年。管理層決定集中在下列三個(gè)主要產(chǎn)品上實(shí)行一個(gè)大規(guī)模的新的廣告運(yùn)動(dòng)。一種噴霧去污劑一種新的液體洗滌劑一種成熟的洗衣粉線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式這一廣告運(yùn)動(dòng)會(huì)采用電視和印刷媒體。一個(gè)商業(yè)廣告已經(jīng)形成，要在全國(guó)的電視上做液體洗滌劑的廣告來(lái)幫助推出這一產(chǎn)品。印刷媒體的廣告將用來(lái)促銷(xiāo)所有三種產(chǎn)品，包括消費(fèi)者可用來(lái)以低價(jià)購(gòu)買(mǎi)產(chǎn)品的象征性?xún)?yōu)惠券。管理部門(mén)已經(jīng)設(shè)定了廣告運(yùn)動(dòng)的最低目標(biāo)：(1)噴霧去污劑必須再增加3％的市場(chǎng)份額；(2)新的液體洗滌劑必須在洗滌劑市場(chǎng)上獲得18％的份額；(3)洗衣粉占洗滌劑市場(chǎng)的份額必須增加4％。線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式上表顯示了在各自的媒體上做一單位廣告的相應(yīng)產(chǎn)品市場(chǎng)份額的估計(jì)增加額。（一個(gè)單位是指利博公司通常采用的一個(gè)廣告標(biāo)準(zhǔn)批量，但其他數(shù)量也是允許的。）在電視一列中洗衣粉的增加份額為－1％的原因是新的液體洗滌劑的電視商業(yè)廣告會(huì)帶走一些洗衣粉的銷(xiāo)售額。表中最后一行顯示了兩種媒體中每一種媒體上做廣告的單位成本。

管理部門(mén)的任務(wù)是：若要以最低的總成本達(dá)到市場(chǎng)份額的目標(biāo)要求，那么在每種媒體上做多少錢(qián)的廣告？線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式若用百分?jǐn)?shù)，就都用百分?jǐn)?shù)；否則，就兩邊同乘100。數(shù)學(xué)模型線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式對(duì)于求取一組變量，使之既滿(mǎn)足線(xiàn)性約束條件，又使具有線(xiàn)性表達(dá)式的目標(biāo)函數(shù)取得極大值或極小值的一類(lèi)最優(yōu)化問(wèn)題稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題，簡(jiǎn)稱(chēng)線(xiàn)性規(guī)劃（LinearProgramming）。1.線(xiàn)性規(guī)劃的定義與數(shù)學(xué)描述（模型）線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式對(duì)決策變量有非負(fù)要求。用一組未知變量表示要求的方案，這組未知變量稱(chēng)為決策變量；存在一定的限制條件，且為線(xiàn)性表達(dá)式，叫約束條件；有一個(gè)目標(biāo)要求（最大化／最小化），目標(biāo)表示為未知變量的線(xiàn)性表達(dá)式，稱(chēng)之為目標(biāo)函數(shù)；2.引例中線(xiàn)性規(guī)劃模型的特點(diǎn)：3.線(xiàn)性規(guī)劃的數(shù)學(xué)描述（數(shù)學(xué)模型）（1）一般形式：線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式目標(biāo)函數(shù)？?jī)r(jià)值系數(shù)？約束條件？技術(shù)系數(shù)？限額系數(shù)？線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式模型的參數(shù)是數(shù)學(xué)模型中的常數(shù)。決策變量的任何一個(gè)取值稱(chēng)為模型的一個(gè)解。滿(mǎn)足所有約束條件的解稱(chēng)為可行解。反之，一個(gè)非可行解至少違反一個(gè)約束條件。全部可行解的集合稱(chēng)為可行域。使目標(biāo)函數(shù)達(dá)到最大值的可行解稱(chēng)為最優(yōu)解。該目標(biāo)函數(shù)值為最優(yōu)值。線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式一般情況下，m<n.模型隱含的假設(shè)：比例性：每種經(jīng)營(yíng)活動(dòng)對(duì)目標(biāo)函數(shù)的貢獻(xiàn)和對(duì)資源的消耗是一個(gè)常數(shù)(不存在邊際效用遞減效用)。可加性：決策變量是相互獨(dú)立的，決策變量之間不發(fā)生關(guān)聯(lián)，不允許變量之間的交叉。連續(xù)性：決策變量應(yīng)取連續(xù)值。確定性：所有參數(shù)是確定的，不包含不確定因素。（2）緊縮形式線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式（3）矩陣形式其中:線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式（4）向量—矩陣形式：其中：線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式1、LP標(biāo)準(zhǔn)型的概念（1）什么是LP的標(biāo)準(zhǔn)型？（2）LP標(biāo)準(zhǔn)型的特點(diǎn)？目標(biāo)函數(shù)約定是極大化Max(或極小化Min；約束條件均用等式表示；決策變量限于取非負(fù)值；右端常數(shù)均為非負(fù)值；線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式（3）數(shù)學(xué)表達(dá)式:

有幾種形式?為什么?如何書(shū)寫(xiě)?2.LP問(wèn)題的標(biāo)準(zhǔn)化（1）目標(biāo)函數(shù)的標(biāo)準(zhǔn)化

線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式目標(biāo)函數(shù)標(biāo)準(zhǔn)化示意圖線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式（2）約束條件的標(biāo)準(zhǔn)化約束條件是“≤”類(lèi)型——左邊加

非負(fù)松弛變量，變?yōu)榈仁?；約束條件是“≥”類(lèi)型——左邊減

非負(fù)松弛變量，變?yōu)榈仁剑蛔兞糠?hào)不限——引入新變量線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式將下面的線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型：討論：

如何下手？標(biāo)準(zhǔn)化過(guò)程排序

-------課堂練習(xí)1-2線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式課堂練習(xí)1-2

提問(wèn)、答疑、討論

總結(jié)，看最終結(jié)果線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式注釋一：線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式是與原始形式等價(jià)的，即一個(gè)線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解與其標(biāo)準(zhǔn)形式的最優(yōu)解的值應(yīng)該是一樣的。一個(gè)問(wèn)題的標(biāo)準(zhǔn)形式并不改變問(wèn)題的本質(zhì)，它只是改變對(duì)問(wèn)題約束條件的寫(xiě)法。Matlab,LINDO與LINGO等中關(guān)于線(xiàn)性規(guī)劃問(wèn)題的結(jié)論顯示就是這類(lèi)標(biāo)準(zhǔn)化形式。線(xiàn)性規(guī)劃問(wèn)題及其標(biāo)準(zhǔn)形式注釋二：在標(biāo)準(zhǔn)型中，松弛變量的系數(shù)為零，表示松弛變量是未使用的資源，不對(duì)目標(biāo)函數(shù)產(chǎn)生任何影響。但是在實(shí)際問(wèn)題中，可以出售未使用的資源，以使公司獲得利潤(rùn)。在此情形下，松弛變量就變成表示公司可以出售多少未使用資源的決策變量。可行解：滿(mǎn)足約束條件和非負(fù)條件的決策變量的一組取值。最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解?；窘猓涸O(shè)AX=b是含n個(gè)決策變量、m個(gè)約束條件的LP的約束方程組，B是LP問(wèn)題的一個(gè)基，若令不與B的列相應(yīng)的n-m個(gè)分量（非基變量）都等于零，所得的方程組的解稱(chēng)為方程組AX=b關(guān)于基B的基本解，簡(jiǎn)稱(chēng)為L(zhǎng)P的基本解。B

對(duì)應(yīng)的決策變量

令非基變量取值為零，計(jì)算出基變量取值，兩者搭配構(gòu)成基本解。線(xiàn)性規(guī)劃問(wèn)題解的概念和性質(zhì)4.基本可行解（對(duì)應(yīng)的基為可行基）：滿(mǎn)足非負(fù)條件的基本解。

5.基本最優(yōu)解（對(duì)應(yīng)的基為最優(yōu)基）：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的基本可行解。最優(yōu)解基本最優(yōu)解線(xiàn)