第二章 線性規(guī)劃圖解法

1、管理運(yùn)籌學(xué)第二章第二章 線性規(guī)劃圖解法線性規(guī)劃圖解法第二章線性規(guī)劃的圖解法線性規(guī)劃的圖解法 線性規(guī)劃是運(yùn)籌學(xué)一個重要分支管理上的典型應(yīng)用：典型線性規(guī)劃應(yīng)用典型線性規(guī)劃應(yīng)用應(yīng)用場景應(yīng)用場景合理利用線材問題用料最少配料問題獲利最大投資問題投資回報最大的方案產(chǎn)品生產(chǎn)計(jì)劃合理利用人力、物力、財力等使獲利最大勞動力安排用最少的勞動力滿足需要運(yùn)輸問題總運(yùn)費(fèi)最少第二章線性規(guī)劃的圖解法線性規(guī)劃的圖解法線性規(guī)劃的組成：線性規(guī)劃的組成1目標(biāo)函數(shù)：MIN/MAX2約束條件：限制條件3決策變量：可控因素線性規(guī)劃問題的提出線性規(guī)劃的圖解法圖解法的靈敏度分析本章內(nèi)容本章內(nèi)容123 1線性規(guī)劃問題的提出線性規(guī)劃問題的提出例

2、1.1.某工廠在計(jì)劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及 A、B 兩種原材料的消耗以及資源的限制，如下表所示。問：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？資源資源產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品資源限制資源限制設(shè)備11300臺時原料A21400kg原料B01250kg單位產(chǎn)品獲利（元）50100 1線性規(guī)劃問題的提出線性規(guī)劃問題的提出約束條件：資源資源產(chǎn)品產(chǎn)品 產(chǎn)品產(chǎn)品資源限資源限制制設(shè)備11300臺時原料A21400kg原料B01250kg單位產(chǎn)品獲利（元）50100 1線性規(guī)劃問題的提出線性規(guī)劃問題的提出建模過程步驟步驟建立線性規(guī)劃模型建立線性規(guī)劃模型1在什么條件下追求什么目標(biāo)

3、2定義決策變量表，每組 代表一個方案3用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)4必須遵循的約束條件 1線性規(guī)劃問題的提出線性規(guī)劃問題的提出問題的提出圖解法圖解法的靈敏度分析本章內(nèi)容本章內(nèi)容123 2圖解法圖解法兩個決策變量的線性問題，可以用圖解法求解。 2圖解法圖解法每個約束條件都代表一個半平面。 2圖解法圖解法每個約束條件都代表一個半平面。 2圖解法圖解法把五個限制條件對應(yīng)的五個半平面合并成一個圖，各約束條件的公共部分即為可行域。 2圖解法圖解法得到最優(yōu)解：B:x1=50,x2=250 最優(yōu)目標(biāo)值 z=27500 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1x2M ax Z=

4、2 x1 +3 x2 st . .1/3 x +1/3 x 1 1/3x +4/3 x 3 x ,x0 121212 （3，0）Z=6（9，0）（0，9/4）Z=0（0，3） 2圖解法圖解法重要結(jié)論 解的情況解的情況場景場景有最優(yōu)解一定有一個可行域的頂點(diǎn)，對應(yīng)一個最優(yōu)點(diǎn)無窮多個最優(yōu)解若將例一中的目標(biāo)函數(shù)變?yōu)閦=50 x1+50 x2，則線段BC上的所有點(diǎn)都代表最優(yōu)解無可行解可行域?yàn)榭沼?，不存在滿足約束條件的解無界解可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小 2圖解法圖解法重要結(jié)論無界解（無最優(yōu)解的情況）目標(biāo)函數(shù)：max z = x1 + x2 ；約束條件：x1 - x2 1 -3

5、x1 +2 x2 6 x1 0， x2 0該問題可行域無界，目標(biāo)函數(shù)值無窮大，無界解，即無最優(yōu)解。 2圖解法圖解法例2 某公司由于生產(chǎn)需要，共需A,B兩種原料至少350噸（A，B有一定替代性）限制條件具體如下：求目標(biāo)函數(shù)最小化的線性規(guī)劃問題試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買 A，B 兩種原料，使得購進(jìn)成本最低？資源需求資源需求加工時間加工時間（小時（小時/噸）噸）成本成本（萬元（萬元/噸）噸）A125噸22B無限制13總資源需求（A+B）需求350噸時間限制（小時）600 2圖解法圖解法得 B 點(diǎn)坐標(biāo)（250，100）為最優(yōu)解建立模型：問題的提出圖解法圖解法的靈敏度分

6、析本章內(nèi)容本章內(nèi)容123 3圖解法的靈敏度分析圖解法的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，通過變換轉(zhuǎn)化為標(biāo)準(zhǔn)形式。標(biāo)準(zhǔn)形式的線性規(guī)劃的四大特點(diǎn)線性規(guī)劃標(biāo)準(zhǔn)線性規(guī)劃標(biāo)準(zhǔn)形式的形式的四個特點(diǎn)四個特點(diǎn)1目標(biāo)最大化2約束為等式3決策變量均非負(fù)4右端項(xiàng)非負(fù) 3圖解法的靈敏度分析圖解法的靈敏度分析極小化目標(biāo)函數(shù)的標(biāo)準(zhǔn)化問題注意注意：以上兩個問題的最優(yōu)解相同，但最優(yōu)值相差一個負(fù)號，即min f = max z 3圖解法的靈敏度分析圖解法的靈敏度分析約束條件不是等式的標(biāo)準(zhǔn)化問題引入一個非負(fù)變量s，令其等于等式左右兩邊的差值為了使約

7、束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于”時稱為“松弛變量松弛變量”；當(dāng)不等式為“大于等于”時稱為“剩余變量剩余變量”。 3圖解法的靈敏度分析圖解法的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析通過標(biāo)準(zhǔn)化得： 3圖解法的靈敏度分析圖解法的靈敏度分析* 變量無符號限制（自由變量）的標(biāo)準(zhǔn)化問題 3圖解法的靈敏度分析圖解法的靈敏度分析考慮例1 的情況，目標(biāo)函數(shù) z = 50 x1 + 100 x2 斜線在右圖兩條紅線之間,-1 （-c1/c2） 0最優(yōu)解不變，仍為B. 3圖解法的靈敏度分析圖解法的靈敏度分析等值線斜率在-1 （-c1/c2）

8、 0 范圍內(nèi)則最優(yōu)值不變。 當(dāng)某一線性規(guī)劃問題在不考慮非負(fù)約束時（即可當(dāng)某一線性規(guī)劃問題在不考慮非負(fù)約束時（即可行域不一定限定在第一象限時），僅存在行域不一定限定在第一象限時），僅存在max(max(或或min)min)時，如果目標(biāo)函數(shù)就是要求求解時，如果目標(biāo)函數(shù)就是要求求解max(max(或或min)min)，此時該結(jié)論有效。如例此時該結(jié)論有效。如例1 1，習(xí)題，習(xí)題2 2（1 1），習(xí)題），習(xí)題6 6等。等。 當(dāng)某一線性規(guī)劃問題在不考慮非負(fù)約束時（即可當(dāng)某一線性規(guī)劃問題在不考慮非負(fù)約束時（即可行域不一定限定在第一象限時），既存在行域不一定限定在第一象限時），既存在maxmax也存也存在在minmin時，無論目標(biāo)函數(shù)是要求求解時，無論目標(biāo)函數(shù)是要求求解max(max(或或min)min)，此時該結(jié)論無效效。如此時該結(jié)論無效效。如P16P16的例的例2 2。 3圖解法的靈敏度分析圖解法的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析結(jié)論結(jié)論：當(dāng)某約束條件中的松弛（剩余）變量不為0時，其對偶價格一定為0，反之不成立。 3圖解法的靈敏度分析圖解法的靈敏度分析在一定范圍內(nèi)，當(dāng)約束條件中常數(shù)項(xiàng)增加 1 個單位