線性規(guī)劃的概念及圖解法第1頁，共25頁，2023年，2月20日，星期六

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

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

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

s.t.是subjectto的縮寫。意思為“滿足于，受約束于”決策變量為：x1,x2第6頁，共25頁，2023年，2月20日，星期六數(shù)學規(guī)劃模型

實際問題中的優(yōu)化模型x~決策變量f(x)~目標函數(shù)gi(x)0~約束條件數(shù)學規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃第7頁，共25頁，2023年，2月20日，星期六線性規(guī)劃問題（LP）：

一組線性不等式約束下求線性目標函數(shù)的極大值或極小值問題。決策變量的一組取值便構(gòu)成了線性規(guī)劃問題的一個解；滿足約束條件的解稱為可行解；所有可行解構(gòu)成的集合稱為可行解集；使目標函數(shù)達到所追求極值的可行解稱為最優(yōu)解；最優(yōu)解所對應的目標函數(shù)值稱為最優(yōu)值。相關定義：第8頁，共25頁，2023年，2月20日，星期六二、線性規(guī)劃的表現(xiàn)形式一般形式：目標函數(shù)和所有的約束條件都是設計變量的線性函數(shù).目標函數(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第9頁，共25頁，2023年，2月20日，星期六基本線性規(guī)劃形式目標函數(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第10頁，共25頁，2023年，2月20日，星期六建模過程1.理解要解決的問題，了解解題的目標和條件；2.定義決策變量（x1，x2，…

，xn

），每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標函數(shù)，確定最大化或最小化目標；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件第11頁，共25頁，2023年，2月20日，星期六三、線性規(guī)劃問題的數(shù)學模型生產(chǎn)安排原料搭配問題條件下料問題物資運輸問題第12頁，共25頁，2023年，2月20日，星期六

某家具廠需要長80cm的角鋼與長60cm的角鋼，它們皆從長210cm的角鋼截得?，F(xiàn)在對長80cm角鋼的需要量為150根，對長60cm角鋼的需要量為330根。問工廠應如何下料，才能使得用料最省？寫出數(shù)學模型。條件下料問題1第13頁，共25頁，2023年，2月20日，星期六

分析：共有三種下料方式，第一種是將1根長210的角鋼截得2根長80cm的角鋼；第二種是將1根長210的角鋼截得1根長80cm和2根60cm的角鋼；第三種是將210cm的角鋼截得3根長60cm的角鋼?，F(xiàn)這三種下料方式應該混合使用。第14頁，共25頁，2023年，2月20日，星期六解：設第一種下料方式用掉x1根角鋼；第二種下料方式用掉x2根角鋼；第三種下料方式用掉x3根角鋼；變量x1x2x3即為決策變量。第15頁，共25頁，2023年，2月20日，星期六數(shù)學模型為：第16頁，共25頁，2023年，2月20日，星期六

某車間有一批長度為7.4m的同型鋼管，因生產(chǎn)需要，需將其截成長2.9m、2.1m、1.5m三種不同長度的管料。若三種管料各需100根，問應如何下料，才能使得用料最??？寫出數(shù)學模型。條件下料問題2第17頁，共25頁，2023年，2月20日，星期六

分析：第18頁，共25頁，2023年，2月20日，星期六解：設第一種下料方式用掉x1根管料；第二種下料方式用掉x2根管料；第三種下料方式用掉x3根管料；第四種下料方式用掉x4根管料；第五種下料方式用掉x5根管料；變量x1x2x3x4x5即為決策變量。第19頁，共25頁，2023年，2月20日，星期六數(shù)學模型為：第20頁，共25頁，2023年，2月20日，星期六例1.目標函數(shù)：

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

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

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

第21頁，共25頁，2023年，2月20日，星期六四圖解法

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

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