線(xiàn)性規(guī)劃的概念及圖解法

線(xiàn)性規(guī)劃的概念及圖解法第一頁(yè)，共二十五頁(yè)，編輯于2023年，星期三

例1：某中藥廠(chǎng)用當(dāng)歸作原料制成當(dāng)歸丸與當(dāng)歸膏，生產(chǎn)1盒當(dāng)歸丸需要5個(gè)勞動(dòng)工時(shí)，使用2kg當(dāng)歸原料，銷(xiāo)售后獲得利潤(rùn)160元；生產(chǎn)1盒當(dāng)歸膏需要2個(gè)勞動(dòng)工時(shí)，使用5kg當(dāng)歸原料，銷(xiāo)售后獲得利潤(rùn)80元；工廠(chǎng)現(xiàn)有可供利用的勞動(dòng)工時(shí)為4000工時(shí)，可供使用的當(dāng)歸原料為5800kg，為避免當(dāng)歸原料存放時(shí)間過(guò)長(zhǎng)而變質(zhì)，要求把5800kg當(dāng)歸原料都用掉。問(wèn)工廠(chǎng)如何安排生產(chǎn)，才能使得兩種產(chǎn)品銷(xiāo)售后獲得的總利潤(rùn)最大？一、概念的引出第二頁(yè)，共二十五頁(yè)，編輯于2023年，星期三解設(shè)工廠(chǎng)生產(chǎn)x1盒當(dāng)歸丸與x2瓶當(dāng)歸膏，可建立以下數(shù)學(xué)模型：第三頁(yè)，共二十五頁(yè)，編輯于2023年，星期三目標(biāo)函數(shù)為：約束條件為：決策變量為：x1,x2第四頁(yè)，共二十五頁(yè)，編輯于2023年，星期三例2

某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購(gòu)進(jìn)125噸。但由于A(yíng)，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)格為2萬(wàn)元，每噸B原料的價(jià)格為3萬(wàn)元，試問(wèn)在滿(mǎn)足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買(mǎi)A，B兩種原料，使得購(gòu)進(jìn)成本最低？第五頁(yè)，共二十五頁(yè)，編輯于2023年，星期三解：設(shè)購(gòu)買(mǎi)A種原料為x1，B種原料為x2，可建立以下數(shù)學(xué)模型：目標(biāo)函數(shù)：MinS=2x1+3x2約束條件：

s.t.x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0

s.t.是subjectto的縮寫(xiě)。意思為“滿(mǎn)足于，受約束于”決策變量為：x1,x2第六頁(yè)，共二十五頁(yè)，編輯于2023年，星期三數(shù)學(xué)規(guī)劃模型

實(shí)際問(wèn)題中的優(yōu)化模型x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件數(shù)學(xué)規(guī)劃線(xiàn)性規(guī)劃非線(xiàn)性規(guī)劃整數(shù)規(guī)劃第七頁(yè)，共二十五頁(yè)，編輯于2023年，星期三線(xiàn)性規(guī)劃問(wèn)題（LP）：

一組線(xiàn)性不等式約束下求線(xiàn)性目標(biāo)函數(shù)的極大值或極小值問(wèn)題。決策變量的一組取值便構(gòu)成了線(xiàn)性規(guī)劃問(wèn)題的一個(gè)解；滿(mǎn)足約束條件的解稱(chēng)為可行解；所有可行解構(gòu)成的集合稱(chēng)為可行解集；使目標(biāo)函數(shù)達(dá)到所追求極值的可行解稱(chēng)為最優(yōu)解；最優(yōu)解所對(duì)應(yīng)的目標(biāo)函數(shù)值稱(chēng)為最優(yōu)值。相關(guān)定義：第八頁(yè)，共二十五頁(yè)，編輯于2023年，星期三二、線(xiàn)性規(guī)劃的表現(xiàn)形式一般形式：目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線(xiàn)性函數(shù).目標(biāo)函數(shù)：Max(Min）z=c1x1+c2x2+…+cnxn

約束條件：

s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2

……

……

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…

，xn≥0第九頁(yè)，共二十五頁(yè)，編輯于2023年，星期三基本線(xiàn)性規(guī)劃形式目標(biāo)函數(shù)：Max（Min)S=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn≤b1

a21x1+a22x2+…+a2nxn≤b2

……

……

am1x1+am2x2+…+amnxn≤bm

x1，x2，…

，xn≥0，bi≥0第十頁(yè)，共二十五頁(yè)，編輯于2023年，星期三建模過(guò)程1.理解要解決的問(wèn)題，了解解題的目標(biāo)和條件；2.定義決策變量（x1，x2，…

，xn

），每一組值表示一個(gè)方案；3.用決策變量的線(xiàn)性函數(shù)形式寫(xiě)出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問(wèn)題過(guò)程中必須遵循的約束條件第十一頁(yè)，共二十五頁(yè)，編輯于2023年，星期三三、線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型生產(chǎn)安排原料搭配問(wèn)題條件下料問(wèn)題物資運(yùn)輸問(wèn)題第十二頁(yè)，共二十五頁(yè)，編輯于2023年，星期三

某家具廠(chǎng)需要長(zhǎng)80cm的角鋼與長(zhǎng)60cm的角鋼，它們皆從長(zhǎng)210cm的角鋼截得?，F(xiàn)在對(duì)長(zhǎng)80cm角鋼的需要量為150根，對(duì)長(zhǎng)60cm角鋼的需要量為330根。問(wèn)工廠(chǎng)應(yīng)如何下料，才能使得用料最??？寫(xiě)出數(shù)學(xué)模型。條件下料問(wèn)題1第十三頁(yè)，共二十五頁(yè)，編輯于2023年，星期三

分析：共有三種下料方式，第一種是將1根長(zhǎng)210的角鋼截得2根長(zhǎng)80cm的角鋼；第二種是將1根長(zhǎng)210的角鋼截得1根長(zhǎng)80cm和2根60cm的角鋼；第三種是將210cm的角鋼截得3根長(zhǎng)60cm的角鋼?，F(xiàn)這三種下料方式應(yīng)該混合使用。第十四頁(yè)，共二十五頁(yè)，編輯于2023年，星期三解：設(shè)第一種下料方式用掉x1根角鋼；第二種下料方式用掉x2根角鋼；第三種下料方式用掉x3根角鋼；變量x1x2x3即為決策變量。第十五頁(yè)，共二十五頁(yè)，編輯于2023年，星期三數(shù)學(xué)模型為：第十六頁(yè)，共二十五頁(yè)，編輯于2023年，星期三

某車(chē)間有一批長(zhǎng)度為7.4m的同型鋼管，因生產(chǎn)需要，需將其截成長(zhǎng)2.9m、2.1m、1.5m三種不同長(zhǎng)度的管料。若三種管料各需100根，問(wèn)應(yīng)如何下料，才能使得用料最省？寫(xiě)出數(shù)學(xué)模型。條件下料問(wèn)題2第十七頁(yè)，共二十五頁(yè)，編輯于2023年，星期三

分析：第十八頁(yè)，共二十五頁(yè)，編輯于2023年，星期三解：設(shè)第一種下料方式用掉x1根管料；第二種下料方式用掉x2根管料；第三種下料方式用掉x3根管料；第四種下料方式用掉x4根管料；第五種下料方式用掉x5根管料；變量x1x2x3x4x5即為決策變量。第十九頁(yè)，共二十五頁(yè)，編輯于2023年，星期三數(shù)學(xué)模型為：第二十頁(yè)，共二十五頁(yè)，編輯于2023年，星期三例1.目標(biāo)函數(shù)：

MaxS=50x1+100x2約束條件：

s.t.x1+x2≤3002x1+x2≤400x2≤250x1≥0x2≥0四圖解法

對(duì)于只有兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示線(xiàn)性規(guī)劃問(wèn)題的有關(guān)概念，并求解。

第二十一頁(yè)，共二十五頁(yè)，編輯于2023年，星期三四圖解法

(1)分別取決策變量X1,X2

為坐標(biāo)向量建立直角坐標(biāo)系。取各約束條件的公共部分x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1第二十二頁(yè)，共二十五頁(yè)，編輯于2023年，星期三（2）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時(shí)得到一條直線(xiàn)，直線(xiàn)上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱(chēng)之為“等值線(xiàn)”。平行移動(dòng)等值線(xiàn)，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第二十三頁(yè)，共二十五頁(yè)，編輯于2023年，星期三重要結(jié)論1：當(dāng)線(xiàn)性規(guī)劃問(wèn)題的可行域非空時(shí)，它是有界或無(wú)界的凸多邊形（凸集）;如果線(xiàn)性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解；無(wú)窮多個(gè)最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙axz=50x1+50x2，