線性規(guī)劃及其基本理論

（優(yōu)選）線性規(guī)劃及其基本理論目前一頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃及其基本理論線性規(guī)劃概述線性規(guī)劃問題線性規(guī)劃數(shù)學(xué)模型一般模型標(biāo)準(zhǔn)模型線性規(guī)劃解的概念可行解、最優(yōu)解基陣、基解、基可行解線性規(guī)劃的基本性質(zhì)目前二頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃概述線性規(guī)劃（LinearProgramming，簡(jiǎn)記為L(zhǎng)P）是運(yùn)籌學(xué)中的一個(gè)最重要、應(yīng)用最廣泛的分支。線性規(guī)劃及其通用解法--單純形法一般認(rèn)為是美國學(xué)者丹捷格（G.Dantzig）在1947年研究美國空軍軍事規(guī)劃時(shí)提出的。蘇聯(lián)學(xué)者康托洛維奇在1939年解決工業(yè)生產(chǎn)組織與計(jì)劃問題時(shí)就提出類似線性規(guī)劃的模型及解法；康托洛維奇的工作當(dāng)時(shí)沒有被重視，但直到1960年康托洛維奇再次發(fā)表《最佳資源利用的經(jīng)濟(jì)計(jì)算》一書后，才受到重視。一些常見的帶有Spreadsheet的軟件，如：Excel、Lotus1-2-3等，均有內(nèi)置的線性規(guī)劃求解功能。最優(yōu)化問題求解軟件，如：Lindo、Lingo、Matlab等。目前三頁\總數(shù)四十三頁\編于十八點(diǎn)

線性規(guī)劃問題提出

在生產(chǎn)管理和經(jīng)營活動(dòng)中經(jīng)常會(huì)提出這樣一類問題：如何利用有限的人力、物力、財(cái)力等資源，取得最好的效果。例如：

配載問題一交通工具，運(yùn)輸幾種不同體積、重量的物資，如何裝配，所運(yùn)的物資最多？下料問題用圓鋼制造長(zhǎng)度不等的機(jī)軸，如何下料，所剩的余料最少？生產(chǎn)計(jì)劃問題企業(yè)生產(chǎn)A、B兩種電器產(chǎn)品，兩種產(chǎn)品的市場(chǎng)需求狀況可以確定，按當(dāng)前的定價(jià)可確保所有產(chǎn)品均能銷售出去。企業(yè)可提供的兩種原材料和勞動(dòng)時(shí)間的數(shù)量是有限的。產(chǎn)品A與產(chǎn)品B各應(yīng)生產(chǎn)多少，可使企業(yè)總利潤(rùn)最大?目前四頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃問題提出上述這些問題有如下共同特點(diǎn)：?jiǎn)栴}解決要滿足一定條件，稱為約束條件；問題有多個(gè)滿足條件的解決方案；問題解決有明確的目標(biāo)要求，對(duì)應(yīng)不同方案有不同目標(biāo)值，可表示成目標(biāo)函數(shù)。目前五頁\總數(shù)四十三頁\編于十八點(diǎn)何謂線性規(guī)劃問題最優(yōu)化問題我們稱如下一般問題：“在一定約束條件下，求目標(biāo)函數(shù)的最大或最小值”為最優(yōu)化問題，用數(shù)學(xué)模型描述的最優(yōu)化問題，稱為數(shù)學(xué)規(guī)劃問題。線性規(guī)劃問題在最優(yōu)化問題中，如果約束條件與目標(biāo)函數(shù)均是線性的，我們就稱之為線性規(guī)劃問題。

目前六頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃問題的三個(gè)要素決策變量決策問題待定的量值稱為決策變量。決策變量的取值有時(shí)要求非負(fù)。約束條件任何問題都是限定在一定的條件下求解，把各種限制條件表示為一組等式或不等式，稱之為約束條件。約束條件是決策方案可行的保障。LP的約束條件，都是決策變量的線性函數(shù)。目標(biāo)函數(shù)衡量決策方案優(yōu)劣的準(zhǔn)則，如時(shí)間最省、利潤(rùn)最大、成本最低。目標(biāo)函數(shù)是決策變量的線性函數(shù)。有的目標(biāo)要實(shí)現(xiàn)極大，有的則要求極小。目前七頁\總數(shù)四十三頁\編于十八點(diǎn)

線性規(guī)劃數(shù)學(xué)模型

例生產(chǎn)計(jì)劃問題

某廠生產(chǎn)甲乙兩種產(chǎn)品，各自的零部件分別在A、B車間生產(chǎn)，最后都需在C車間裝配，相關(guān)數(shù)據(jù)如表所示：

問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤(rùn)為最大。35單位產(chǎn)品獲利81236123234ABC生產(chǎn)能力工時(shí)單耗甲乙產(chǎn)品車間目前八頁\總數(shù)四十三頁\編于十八點(diǎn)

線性規(guī)劃數(shù)學(xué)模型建立數(shù)學(xué)模型的步驟：Step1分析實(shí)際問題；Step2確定決策變量；Step3找出約束條件；Step4確定目標(biāo)函數(shù)；Step5整理、寫出數(shù)學(xué)模型。目前九頁\總數(shù)四十三頁\編于十八點(diǎn)【例1.1】某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應(yīng)量見下表：要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2)，求建造方案。水泥(公斤/m2)4000(千工日)147000(千塊)150000(噸)20000(噸)110000(千元)資源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105磚混住宅人工(工日/m2)磚(塊/m2)鋼材(公斤/m2)造價(jià)(元/m2)資源住宅體系線性規(guī)劃問題舉例目前十頁\總數(shù)四十三頁\編于十八點(diǎn)【例1.2】最優(yōu)生產(chǎn)計(jì)劃問題。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要要在設(shè)備A、B上加工，需要消耗材料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表1.1所示。已知在計(jì)劃期內(nèi)設(shè)備的加工能力各為200臺(tái)時(shí)，可供材料分別為360、300公斤；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤(rùn)分別為40、30、50元，假定市場(chǎng)需求無限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大？線性規(guī)劃問題舉例產(chǎn)品

資源甲

乙丙現(xiàn)有資源設(shè)備A312200設(shè)備B224200材料C451360材料D235300利潤(rùn)（元/件）403050產(chǎn)品資源消耗表目前十一頁\總數(shù)四十三頁\編于十八點(diǎn)【例1.3】某商場(chǎng)決定：營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。根據(jù)統(tǒng)計(jì)，商場(chǎng)每天需要的營業(yè)員如表1.2所示。表1.2營業(yè)員需要量統(tǒng)計(jì)表商場(chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場(chǎng)總的營業(yè)員最少。星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四400線性規(guī)劃問題舉例目前十二頁\總數(shù)四十三頁\編于十八點(diǎn)【例1.4】合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來做，圓鋼長(zhǎng)度為4m?，F(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？線性規(guī)劃問題舉例目前十三頁\總數(shù)四十三頁\編于十八點(diǎn)【解】這是一個(gè)條材下料問題，設(shè)切口寬度為零。設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y3≤4表示，求這個(gè)不等式關(guān)于y1，y2，y3的非負(fù)整數(shù)解。象這樣的非負(fù)整數(shù)解共有10組，也就是有10種下料方式，如表1.3所示。表1．3下料方案方案規(guī)格12345678910需求量y1(根)22111000001000y210210432101000y3

01023012451000余料（m）00.30.50.1o.400.30.60.20.5目前十四頁\總數(shù)四十三頁\編于十八點(diǎn)設(shè)xj(j=1,2…,10)為第j種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學(xué)模型為:注意：（１）求下料方案時(shí)應(yīng)注意，余料不能超過最短毛坯的長(zhǎng)度；（２）最好將毛坯長(zhǎng)度按降的次序排列，即先切割長(zhǎng)度最長(zhǎng)的毛坯，再切割次長(zhǎng)的，最后切割最短的，不能遺漏了方案。（３）如果方案較多，用計(jì)算機(jī)編程排方案，去掉余料較長(zhǎng)的方案，進(jìn)行初選。目前十五頁\總數(shù)四十三頁\編于十八點(diǎn)【例1.5】配料問題。某鋼鐵公司生產(chǎn)一種合金，要求的成分規(guī)格是：錫不少于28%，鋅不多于15%，鉛恰好10%，鎳要界于35%~55%之間，不允許有其他成分。鋼鐵公司擬從五種不同級(jí)別的礦石中進(jìn)行冶煉，每種礦物的成分含量和價(jià)格如表1.4所示。礦石雜質(zhì)在治煉過程中廢棄，現(xiàn)要求每噸合金成本最低的礦物數(shù)量。假設(shè)礦石在冶煉過程中，合金含量沒有發(fā)生變化。表1.4礦石的金屬含量合金礦石錫%鋅%鉛%鎳%雜質(zhì)%費(fèi)用（元/t）125101025303402400030302603015520601804202004020230585151755190線性規(guī)劃問題舉例目前十六頁\總數(shù)四十三頁\編于十八點(diǎn)解:設(shè)xj（j=1,2，…，5）是第j種礦石數(shù)量，得到下列線性規(guī)劃模型注意，礦石在實(shí)際冶煉時(shí)金屬含量會(huì)發(fā)生變化，建模時(shí)應(yīng)將這種變化考慮進(jìn)去，有可能是非線性關(guān)系。配料問題也稱配方問題、營養(yǎng)問題或混合問題，在許多行業(yè)生產(chǎn)中都能遇到。目前十七頁\總數(shù)四十三頁\編于十八點(diǎn)【例1.6】投資問題。某投資公司在第一年有200萬元資金，每年都有如下的投資方案可供考慮采納：“假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的一倍金額”。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多。線性規(guī)劃問題舉例目前十八頁\總數(shù)四十三頁\編于十八點(diǎn)【例1.7】均衡配套生產(chǎn)問題。某產(chǎn)品由2件甲、3件乙零件組裝而成。兩種零件必須經(jīng)過設(shè)備A、B上加工，每件甲零件在A、B上的加工時(shí)間分別為5分鐘和9分鐘，每件乙零件在A、B上的加工時(shí)間分別為4分鐘和10分鐘。現(xiàn)有2臺(tái)設(shè)備A和3臺(tái)設(shè)備B，每天可供加工時(shí)間為8小時(shí)。為了保持兩種設(shè)備均衡負(fù)荷生產(chǎn)，要求一種設(shè)備每天的加工總時(shí)間不超過另一種設(shè)備總時(shí)間1小時(shí)。怎樣安排設(shè)備的加工時(shí)間使每天產(chǎn)品的產(chǎn)量最大。線性規(guī)劃問題舉例目前十九頁\總數(shù)四十三頁\編于十八點(diǎn)

線性規(guī)劃數(shù)學(xué)模型一般形式假定線性規(guī)劃問題有n個(gè)決策變量，m個(gè)約束條件。一般地，線性規(guī)劃問題數(shù)學(xué)模型中可表示成如下形式：目前二十頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃數(shù)學(xué)模型標(biāo)準(zhǔn)形式線性規(guī)劃問題的數(shù)學(xué)模型有各種不同的形式，如目標(biāo)函數(shù)有極大化和極小化；約束條件有“≤”、“≥”和“＝”三種情況；決策變量一般有非負(fù)性要求，有的則沒有。為了求解方便，特規(guī)定一種線性規(guī)劃的標(biāo)準(zhǔn)形式，非標(biāo)準(zhǔn)型可以轉(zhuǎn)化為標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)形式為：目標(biāo)函數(shù)極大化，約束條件為等式，右端常數(shù)項(xiàng)bi≥0，決策變量非負(fù)。目前二十一頁\總數(shù)四十三頁\編于十八點(diǎn)

線性規(guī)劃數(shù)學(xué)模型標(biāo)準(zhǔn)形式目前二十二頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃數(shù)學(xué)模型標(biāo)準(zhǔn)形式目前二十三頁\總數(shù)四十三頁\編于十八點(diǎn)

線性規(guī)劃數(shù)學(xué)模型標(biāo)準(zhǔn)形式目前二十四頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃數(shù)學(xué)模型標(biāo)準(zhǔn)形式目前二十五頁\總數(shù)四十三頁\編于十八點(diǎn)如何化線性規(guī)劃標(biāo)準(zhǔn)形式目前二十六頁\總數(shù)四十三頁\編于十八點(diǎn)如何化線性規(guī)劃標(biāo)準(zhǔn)形式例1.8

minz=

x1+2x2

-3x3x1+2x2-x3≤52x1+3x2-x3≥6

-x1

-x2

+x3≥-2x1

≥0,x3≤0目前二十七頁\總數(shù)四十三頁\編于十八點(diǎn)【例1.9】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型如何化線性規(guī)劃標(biāo)準(zhǔn)形式目前二十八頁\總數(shù)四十三頁\編于十八點(diǎn)如何化線性規(guī)劃標(biāo)準(zhǔn)形式目前二十九頁\總數(shù)四十三頁\編于十八點(diǎn)當(dāng)某個(gè)變量xj≤0時(shí),令x/j=－xj

。當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束將其化為兩個(gè)不等式再加入松馳變量化為等式。如何化線性規(guī)劃標(biāo)準(zhǔn)形式目前三十頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃解的概念可行解與可行域滿足約束條件（AX=b,X≥0）的X稱為線性規(guī)劃問題的可行解所有可行解的集合稱為可行域，記D={X|AX=b,X≥0}。最優(yōu)解使目標(biāo)函數(shù)值達(dá)最大的可行解稱為線性規(guī)劃問題的最優(yōu)解。若X*是最優(yōu)解，則對(duì)任意的X∈D，恒有C

X*≥CX。目前三十一頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃解的概念基（基陣、基礎(chǔ)矩陣）

為m×n維系數(shù)矩陣，秩為m。稱系數(shù)矩陣A中m個(gè)線性獨(dú)立的列向量構(gòu)成的矩陣B為線性規(guī)劃問題的一個(gè)基。矩陣B非奇異，|B|≠0，存在逆陣。|B|≠0,B為非奇異子矩陣；當(dāng)m=n時(shí)，基矩陣唯一，當(dāng)m<n時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過A中最多有目前三十二頁\總數(shù)四十三頁\編于十八點(diǎn)【例1.11】線性規(guī)劃求所有基矩陣。目前三十三頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃基解的概念基向量與非基向量系數(shù)矩陣A中構(gòu)成基B的列向量稱為基向量。系數(shù)矩陣A中除基向量之外的列向量稱為基向量。A=(B,N)基變量與非基變量與基向量對(duì)應(yīng)的變量稱為基變量。與非基向量對(duì)應(yīng)的變量稱為非基變量。

目前三十四頁\總數(shù)四十三頁\編于十八點(diǎn)在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量?；兞?、非基變量是針對(duì)某一確定基而言的，不同的基對(duì)應(yīng)的基變量和非基變量也不同。線性規(guī)劃基解的概念目前三十五頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃基解的概念基(礎(chǔ))解基(礎(chǔ))可行解滿足變量非負(fù)約束條件的基解，稱為線性規(guī)劃問題的基可行解?？尚谢c基可行解對(duì)應(yīng)的基稱為可行基。目前三十六頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃解的關(guān)系目前三十七頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃的退化與非退化一個(gè)基可行解，若其中所有基變量都取正值，則稱它是非退化的。一個(gè)基可行解，若其中有某一個(gè)基變量取零值，則稱它是退化的。一個(gè)線性規(guī)劃問題，若它的所有基可行解都是非退化的，則稱這個(gè)線性規(guī)劃問題是非退化的。目前三十八頁\總數(shù)四十三頁\編于十八點(diǎn)線性規(guī)劃基解求取基解與基可行解是線性規(guī)劃的重要概念，求線性規(guī)劃的基解與基可行解是各類運(yùn)籌學(xué)考試中的常考題。求線性規(guī)劃的基解與基可行解時(shí)，首先要先化標(biāo)準(zhǔn)形，然后根據(jù)概念求解。例選擇不同基，求如下LP的基解和基可行解：

maxz=x1+4x2x1+x2+x3=4-x1+