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

數(shù)學(xué)建模--線性規(guī)劃第1頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月

線性規(guī)劃問(wèn)題的提出線性規(guī)劃的基本概念線性規(guī)劃的數(shù)學(xué)模型繼續(xù)返回一線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第2頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月問(wèn)題的提出例:生產(chǎn)計(jì)劃問(wèn)題第3頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月產(chǎn)品I產(chǎn)品2如何安排生產(chǎn)使利潤(rùn)最大？第4頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月決策變量（Decisionvariables）目標(biāo)函數(shù)（Objectivefunction）約束條件（Constraintconditions）可行域（Feasibleregion)最優(yōu)解（Optimalsolution)基本概念問(wèn)題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。它是決策變量的函數(shù)指決策變量取值時(shí)受到的各種資源條件的限制，通常表達(dá)為含決策變量的等式或不等式。滿足約束條件的決策變量的取值范圍可行域中使目標(biāo)函數(shù)達(dá)到最優(yōu)的決策變量的值第5頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月是問(wèn)題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量設(shè)——I的產(chǎn)量——II的產(chǎn)量——利潤(rùn)第6頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月第2步--定義目標(biāo)函數(shù)MaxZ=x1+x2決策變量第7頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月

MaxZ=2x1+3x2系數(shù)第2步--定義目標(biāo)函數(shù)第8頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月對(duì)我們有何限制?第9頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月第3步--表示約束條件

x1+2x2

84x1

164x2

12x1、x2

0第10頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月該計(jì)劃的數(shù)學(xué)模型

目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第11頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃問(wèn)題的共同特征一組決策變量X表示一個(gè)方案,一般X大于等于零。約束條件是線性等式或不等式。目標(biāo)函數(shù)是線性的。求目標(biāo)函數(shù)最大化或最小化第12頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月

線性規(guī)劃模型的一般形式第13頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃模型建立步驟從實(shí)際問(wèn)題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟；1.根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量；

2.由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)；

3.由決策變量所受的限制條件確定決策變量所要滿足的約束條件。第14頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月1.線性規(guī)劃的標(biāo)準(zhǔn)形式：用單純法求解時(shí)，常將標(biāo)準(zhǔn)形式化為：2.線性規(guī)劃的基本算法——單純形法二.線性規(guī)劃的基本算法——單純形法第15頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月引入松弛變量x3,x4,x5,將不等式化為等式,即單純形標(biāo)準(zhǔn)形:顯然A的秩ran(A)=3,任取3個(gè)線性無(wú)關(guān)的列向量,如P3P4P5稱為一組基,記為B.其余列向量稱為非基,記為N.第16頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月于是f=cBxB+cNxN,Ax=BxB+NxN=b,則xB=B-1b-B-1NxN,f=cBB-1b+(cN–cBB-1N)xN

若可行基進(jìn)一步滿足:cN–cBB-1N≥0,即:cBB-1N-cN≤0則對(duì)一切可行解x,必有f(x)≥cBB-1b,此時(shí)稱基可行解x=(B-1b,0)T為最優(yōu)解.

3.最優(yōu)解的存在性定理將A的列向量重排次序成A=(B,N),相應(yīng)x=(xB,xN)T,c=(cB,cN)基對(duì)應(yīng)的變量xB稱為基變量,非基對(duì)應(yīng)的變量xN稱為非基變量.定理如果線性規(guī)劃(1)有最優(yōu)解，那么一定存在一個(gè)基可行解是最優(yōu)解.第17頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月4.基可行解是最優(yōu)解的判定準(zhǔn)則檢驗(yàn)數(shù)因?yàn)锳x=BxB+NxN=b,得xB=B-1b-B-1NxN,而f=cBxB+cNxN,故f=cBB-1b+(cN–cBB-1N)xN

第18頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月5.基可行解的改進(jìn)第19頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月改進(jìn)方法：返回第20頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月練習(xí)建立LP數(shù)學(xué)模型一、有兩個(gè)煤廠A、B，每月分別供應(yīng)三個(gè)居民區(qū)X、Y、Z。求運(yùn)費(fèi)最少的方案。供需平衡第21頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月1、LINGO使用簡(jiǎn)介L(zhǎng)INGO軟件是美國(guó)的LINDO系統(tǒng)公司（LindoSystemInc）開(kāi)發(fā)的一套用于求解最優(yōu)化問(wèn)題的軟件包.LINGO除了能用于求解線性規(guī)劃和二次規(guī)劃外，還可以用于非線性規(guī)劃求解以及一些線性和非線性方程（組）的求解.LINGO軟件的最大特色在于它允許優(yōu)化模型中的決策變量為整數(shù)，而且執(zhí)行速度快.LINGO內(nèi)置了一種建立最優(yōu)化模型的語(yǔ)言，可以簡(jiǎn)便地表達(dá)大規(guī)模問(wèn)題，利用LINGO高效的求解器可快速求解并分析結(jié)果，這里簡(jiǎn)單介紹LINGO的使用方法.

LINGO可以求解線性規(guī)劃、二次規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、圖論及網(wǎng)絡(luò)優(yōu)化和排隊(duì)論模型中的最優(yōu)化問(wèn)題等.一個(gè)LINGO程序一般會(huì)包含集合段、數(shù)據(jù)輸入段、優(yōu)化目標(biāo)和約束段、初始段和數(shù)據(jù)預(yù)處理段等部分，每一部分有其獨(dú)特的作用和語(yǔ)法規(guī)則，讀者可以通過(guò)查閱相關(guān)的參考書(shū)或者LINGO的HELP文件詳細(xì)了解，這里就不展開(kāi)介紹了.

三.線性規(guī)劃軟件求解第22頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月LINGO的主要功能特色為：既能求解線性規(guī)劃問(wèn)題，也有較強(qiáng)的求解非線性規(guī)劃問(wèn)題的能力；輸入模型簡(jiǎn)練直觀；運(yùn)算速度快、計(jì)算能力強(qiáng)；內(nèi)置建模語(yǔ)言，提供幾十個(gè)內(nèi)部函數(shù)，從而能以較少語(yǔ)句，較直觀的方式描述大規(guī)模的優(yōu)化模型；將集合的概念引入編程語(yǔ)言，很容易將實(shí)際問(wèn)題轉(zhuǎn)換為L(zhǎng)INGO模型；并且能方便地與Excel、數(shù)據(jù)庫(kù)等其他軟件交換數(shù)據(jù).

第23頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月第一步：?jiǎn)?dòng)Lingo屏幕顯示如下：標(biāo)記LINGO的外窗口是主框架窗口，主框架窗口的上面包含所有的命令菜單和命令工具欄；標(biāo)記LINGOMODEL-LINGO1的子窗口是一個(gè)新的、空白的模型窗口。第24頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月第二步：在模型窗口中輸入模型model:max=2*x1+3*x2;4*x1+3*x2<10;3*x1+5*x2<12;endMax2x1+3x2St.4x1+3x2<=103x1+5x2<=12x1≥0x2≥0第25頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月第三步：求解模型

1)選擇菜單

LINGO|Solve

或者按工具欄的

第26頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月

2)LINGO開(kāi)始編譯模型，如有語(yǔ)法錯(cuò)誤將返回一個(gè)錯(cuò)誤的消息并指明錯(cuò)誤出現(xiàn)的位置；如果通過(guò)編譯,LINGO將激活Solver運(yùn)算器尋求模型的最優(yōu)解；3)首先出現(xiàn)solverstatus窗口，其作用是監(jiān)控solver的進(jìn)展和顯示模型的維數(shù)等信息；第27頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月第28頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月4)計(jì)算完成后出現(xiàn)SolutionReport窗口顯示模型解的詳細(xì)信息；第29頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月SolutionReport窗口Globaloptimalsolutionfoundatiteration:2Objectivevalue:7.454545VariableValueReducedCostx11.2727270.000000x21.6363640.000000RowSlackorSurplusDualPrice17.4545451.00000020.0000000.9090909E-0130.0000000.5454545（對(duì)目標(biāo)函數(shù)而言）第30頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月LINGO的語(yǔ)法規(guī)定、運(yùn)算符及函數(shù)：（1）求目標(biāo)函數(shù)的最大值或最小值分別用MAX=…或MIN=…來(lái)表示；（2）每個(gè)語(yǔ)句必須以分號(hào)“；”結(jié)束，每行可以有許多語(yǔ)句，語(yǔ)句可以跨行；（3）變量名稱必須以字母（A~Z）開(kāi)頭，由字母、數(shù)字（0~9）和下劃線所組成，長(zhǎng)度不超過(guò)32個(gè)字符，不區(qū)分大小寫(xiě)；（4）可以給語(yǔ)句加上標(biāo)號(hào)，例如[OBJ]MAX=200*X1+300*X2；（5）以驚嘆號(hào)“！”開(kāi)頭，以分號(hào)“；”結(jié)束的語(yǔ)句是注釋語(yǔ)句；（6）如果對(duì)變量的取值范圍沒(méi)有作特殊說(shuō)明，則默認(rèn)所有決策變量都非負(fù)；（7）LINGO模型以語(yǔ)句“MODEL：”開(kāi)頭，以“END”結(jié)束，對(duì)于比較簡(jiǎn)單的模型，這兩個(gè)語(yǔ)句可以省略.(8)可以用<表示<=；用>表示>=；

Lingo無(wú)嚴(yán)格小于，欲使a<b，可以適當(dāng)選取小的正常數(shù)e表示成a+e<b，第31頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月(9)LINGO編輯器用藍(lán)色顯示LINGO關(guān)鍵字;

綠色顯示注釋

;其他文本用黑色

匹配的括號(hào)用紅色高亮度顯示(10)標(biāo)準(zhǔn)運(yùn)算符算術(shù)運(yùn)算符：^*/+-邏輯運(yùn)算符：

#EQ##NE#(相等，不等）為真

#GE##GT#（左邊大于或等于，左邊大于）為真

#LE##LT#（左邊小于或等于，左邊小于）為真

#NOT##AND##OR#（取反，取交（積），取并（和）)第32頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月(11).變量界定函數(shù)lingo變量默認(rèn)域?yàn)榉秦?fù)實(shí)數(shù)@free(variable)

取消默認(rèn)域，使變量可以取任意實(shí)數(shù)@gin(variable)限制變量取整數(shù)值@bin(variable)限制變量取值為0，1@bnd(low,variable,up)限制變量于一個(gè)有限的范圍第33頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月例題1：某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)A、B兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需設(shè)備臺(tái)時(shí)及對(duì)甲、乙兩種原材料的消耗，有關(guān)數(shù)據(jù)如表1.1.問(wèn)：應(yīng)如何安排生產(chǎn)計(jì)劃，使工廠獲利最大？產(chǎn)品資源AB可利用資源設(shè)備128臺(tái)時(shí)甲4016公斤乙0412公斤單位利潤(rùn)2元3元建立線性規(guī)劃問(wèn)題的數(shù)學(xué)模型，用LINGO求出最優(yōu)解并做相應(yīng)的分析.第34頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月問(wèn)題1.1設(shè)計(jì)劃生產(chǎn)A,B兩種產(chǎn)品分別為x1,x2，則建立線性規(guī)劃問(wèn)題數(shù)學(xué)模型模型：maxS=2x1+

3x2在LINGO的MODEL窗口內(nèi)輸入如下模型：model:max=2*x1+3*x2;x1+2*x2<=8;4*x1<=16;4*x2<=12;end第35頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月選菜單Lingo|Solve(或按Ctrl+S),或用鼠標(biāo)點(diǎn)擊“求解”按紐，如果模型有語(yǔ)法錯(cuò)誤，則彈出一個(gè)標(biāo)題為“LINGOErrorMessage”(錯(cuò)誤信息)的窗口，指出在哪一行有怎樣的錯(cuò)誤，每一種錯(cuò)誤都有一個(gè)編號(hào)（具體含義可查閱相關(guān)文獻(xiàn)或LINGO的Help）.改正錯(cuò)誤以后再求解，如果語(yǔ)法通過(guò)，LINGO用內(nèi)部所帶的求解程序求出模型的解，然后彈出一個(gè)標(biāo)題為“LINGOSolverStatus”（求解狀態(tài)）的窗口，其內(nèi)容為變量個(gè)數(shù)、約束條件個(gè)數(shù)、優(yōu)化狀態(tài)、耗費(fèi)內(nèi)存、所花時(shí)間等信息，點(diǎn)擊Close關(guān)閉窗口，屏幕上出現(xiàn)標(biāo)題為“SolutionReport”（解的報(bào)告）的信息窗口，顯示優(yōu)化計(jì)算（線性規(guī)劃中換基迭代）的步數(shù)、優(yōu)化后的目標(biāo)函數(shù)值、列出各變量的計(jì)算結(jié)果.求解結(jié)果：第36頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月Globaloptimalsolutionfoundatiteration:5Objectivevalue:14.00000VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPrice114.000001.00000020.0000001.50000030.0000000.125000044.0000000.000000第37頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月該報(bào)告說(shuō)明：運(yùn)行5步找到全局最優(yōu)解，目標(biāo)函數(shù)值為14，變量值分別為x1=4,x2=2.“ReducedCost”的含義是需縮減成本系數(shù)或需增加利潤(rùn)系數(shù)（最優(yōu)解中取值非零的決策變量的ReducedCost值等于零）.“Row”是輸入模型中的行號(hào)，目標(biāo)函數(shù)是第一行；“SlackorSurplus”的意思是松弛或剩余，即約束條件左邊與右邊的差值，對(duì)于“≤”的不等式，右邊減左邊的差值為Slack（松弛），對(duì)于“>=”的不等式，左邊減右邊的差值為Surplus（剩余），當(dāng)約束條件兩邊相等時(shí)，松弛或剩余的值等于零.“DualPrice”的意思是對(duì)偶價(jià)格（或稱為影子價(jià)格），上述報(bào)告中Row2的松弛值為0，表明生產(chǎn)甲產(chǎn)品4單位、乙產(chǎn)品2單位，所需設(shè)備8臺(tái)時(shí)已經(jīng)飽和，對(duì)偶價(jià)格1.5的含義是：如果設(shè)備增加1臺(tái)時(shí)，能使目標(biāo)函數(shù)值增加1.5.報(bào)告中Row4的松弛值為4，表明生產(chǎn)甲產(chǎn)品4單位、乙產(chǎn)品2單位，所需原材料乙8公斤還剩余4公斤，因此增加原材料乙不會(huì)使目標(biāo)函數(shù)值增加，所以對(duì)偶價(jià)格為0.第38頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX

1、模型：命令：x=linprog（c，A，b）2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒(méi)有不等式：存在，則令A(yù)=[]，b=[].第39頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月3、模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若沒(méi)有等式約束:,則令A(yù)eq=[],beq=[].[2]其中X0表示初始點(diǎn)4、命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標(biāo)函數(shù)值fval.第40頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月解編寫(xiě)M文件xxgh1.m如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

ToMatlab(xxgh1)第41頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月

投資的收益和風(fēng)險(xiǎn)四.線性規(guī)劃應(yīng)用舉例第42頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月(二)、基本假設(shè)和符號(hào)規(guī)定第43頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月(三)、模型的建立與分析1.總體風(fēng)險(xiǎn)用所投資的Si中最大的一個(gè)風(fēng)險(xiǎn)來(lái)衡量,即max{qixi|i=1，2,…n}4.模型簡(jiǎn)化：第44頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月第45頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月(四)、模型1的求解

由于a是任意給定的風(fēng)險(xiǎn)度，到底怎樣給定沒(méi)有一個(gè)準(zhǔn)則，不同的投資者有不同的風(fēng)險(xiǎn)度。我們從a=0開(kāi)始，以步長(zhǎng)△a=0.001進(jìn)行循環(huán)搜索，編制程序如下：第46頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月a=0;while(1.1-a)>1c=[-0.05-0.27-0.19-0.185-0.185];Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')ToMatlab（xxgh5）第47頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月計(jì)算結(jié)果：第48頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月(五)、結(jié)果分析返回4.在a=0.006附近有一個(gè)轉(zhuǎn)折點(diǎn)，在這一點(diǎn)左邊，風(fēng)險(xiǎn)增加很少時(shí)，利潤(rùn)增長(zhǎng)很快。在這一點(diǎn)右邊，風(fēng)險(xiǎn)增加很大時(shí)，利潤(rùn)增長(zhǎng)很緩慢，所以對(duì)于風(fēng)險(xiǎn)和收益沒(méi)有特殊偏好的投資者來(lái)說(shuō)，應(yīng)該選擇曲線的拐點(diǎn)作為最優(yōu)投資組合，大約是a*=0.6%，Q*=20%，所對(duì)應(yīng)投資方案為:

風(fēng)險(xiǎn)度收益x0x1x2x3x40.00600.201900.24000.40000.10910.22123.曲線上的任一點(diǎn)都表示該風(fēng)險(xiǎn)水平的最大可能收益和該收益要求的最小風(fēng)險(xiǎn)。對(duì)于不同風(fēng)險(xiǎn)的承受能力，選擇該風(fēng)險(xiǎn)水平下的最優(yōu)投資組合。2.當(dāng)投資越分散時(shí)，投資者承擔(dān)的風(fēng)險(xiǎn)越小，這與題意一致。即:

冒險(xiǎn)的投資者會(huì)出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資。1.風(fēng)險(xiǎn)大，收益也大。第49頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月實(shí)驗(yàn)作業(yè)某廠生產(chǎn)甲乙兩種口味的飲料,每百箱甲飲料需用原料6千克,工人10名,可獲利10萬(wàn)元;每百箱乙飲料需用原料5千克,工人20名,可獲利9萬(wàn)元.今工廠共有原料60千克,工人150名,又由于其他條件所限甲飲料產(chǎn)量不超過(guò)8百箱.問(wèn)如何安排生產(chǎn)計(jì)劃,即兩種飲料各生產(chǎn)多少使獲利最大.進(jìn)一步討論:1)若投資0.8萬(wàn)元可增加原料1千克,問(wèn)應(yīng)否作這項(xiàng)投資.2)若每百箱甲飲料獲利可增加1萬(wàn)元,問(wèn)應(yīng)否改變生產(chǎn)計(jì)劃.返回第50頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月圖解法線性規(guī)劃問(wèn)題求解的幾種可能結(jié)果由圖解法得到的啟示2線性規(guī)劃的圖解法繼續(xù)返回第51頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月例1的數(shù)學(xué)模型

目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第52頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2

=8(0,4)(8,0)

目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

04x1

=164x2

=12圖解法第53頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

=84x1

=164x2

=12可行域圖解法第54頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

=84x1

=164x2

=12可行域BCDEA圖解法第55頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

=84x1

=164x2

=12BCDEA2x1+3x2=6圖解法第56頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

=164x2

=12BCDEAx1+2x2=84x1=16最優(yōu)解(4,2)圖解法第57頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月圖解法求解步驟由全部約束條件作圖求出可行域；作目標(biāo)函數(shù)等值線，確定使目標(biāo)函數(shù)最優(yōu)的移動(dòng)方向；平移目標(biāo)函數(shù)的等值線，找出最優(yōu)點(diǎn)，算出最優(yōu)值。第58頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃問(wèn)題求解的

幾種可能結(jié)果(a)唯一最優(yōu)解

x26—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1第59頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月(b)無(wú)窮多最優(yōu)解6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1線性規(guī)劃問(wèn)題求解的

幾種可能結(jié)果第60頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月(c)無(wú)界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

x2x1線性規(guī)劃問(wèn)題求解的

幾種可能結(jié)果第61頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月(d)無(wú)可行解

MaxZ=2x1+3x2x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

0可行域?yàn)榭占€性規(guī)劃問(wèn)題求解的

幾種可能結(jié)果第62頁(yè)，課件共70頁(yè)，創(chuàng)作于2023年2月圖解法的幾點(diǎn)結(jié)論:

（由圖解法得到的啟示）可行域是有界或無(wú)界的凸多邊形。若線性規(guī)劃問(wèn)題存在最優(yōu)解，它一定可以在可行域的頂點(diǎn)得到。若兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則其連線上的所有點(diǎn)都是最優(yōu)解。解題思路：找出凸集的頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值，比較即得。第63頁(yè)，課件共70頁(yè)，創(chuàng)作于