b規(guī)劃 圖解法及標(biāo)準(zhǔn)型的轉(zhuǎn)化

會(huì)計(jì)學(xué)1b規(guī)劃圖解法及標(biāo)準(zhǔn)型的轉(zhuǎn)化第二章

線性規(guī)劃第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第二節(jié)線性規(guī)劃問(wèn)題的圖解法第三節(jié)單純形法第四節(jié)線性規(guī)劃的對(duì)偶問(wèn)題第五節(jié)線性規(guī)劃在衛(wèi)生管理中的應(yīng)用小結(jié)??第1頁(yè)/共47頁(yè)

第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型一、線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型二、線性規(guī)劃問(wèn)題的共同特征三、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式（第三節(jié)介紹）上次課內(nèi)容回顧??第2頁(yè)/共47頁(yè)資源給定一、線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃研究?jī)?nèi)容最大效益合理計(jì)劃統(tǒng)籌安排最少資源合理計(jì)劃統(tǒng)籌安排任務(wù)給定第3頁(yè)/共47頁(yè)表示為決策變量的線性函數(shù)目標(biāo)函數(shù)用一組變量來(lái)表示（x1，x2,…,xn）決策變量用線性等式或不等式來(lái)表示約束條件方程式二、線性規(guī)劃問(wèn)題的共同特征問(wèn)題的方案存在限制條件一個(gè)目標(biāo)要求第4頁(yè)/共47頁(yè)線性規(guī)劃問(wèn)題建立模型的三個(gè)步驟①確定一組變量（決策變量）；

②表示出一定的限制條件；

③寫(xiě)出目標(biāo)函數(shù)。第5頁(yè)/共47頁(yè)Max(Min)Z=c1x1

+c2

x2

+…+cn

xna11x1+a12

x2

+…+a1n

xn≤(=,≥)b1a21x1+a22x2

+…+a2n

xn≤(=,≥)b2

┆am1x1+am2

x2

+…+amn

xn≤(=,≥)bmx1

，x2，…

，xn≥0約束條件：目標(biāo)函數(shù)：線性規(guī)劃數(shù)學(xué)模型的一般形式Cj稱(chēng)為成本或利潤(rùn)系數(shù)bi稱(chēng)為限定系數(shù)

a21稱(chēng)為約束條件中未知變量的系數(shù)

#第6頁(yè)/共47頁(yè)第二章

線性規(guī)劃第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第二節(jié)線性規(guī)劃問(wèn)題的圖解法第三節(jié)單純形法第四節(jié)線性規(guī)劃的對(duì)偶問(wèn)題第五節(jié)線性規(guī)劃在衛(wèi)生管理中的應(yīng)用?第7頁(yè)/共47頁(yè)第二節(jié)線性規(guī)劃問(wèn)題的圖解法

1、圖解法解極大化問(wèn)題2、圖解法求解極小化問(wèn)題一、線性規(guī)劃問(wèn)題解的基本概念二、兩個(gè)變量的線性規(guī)劃問(wèn)題的圖解法三、線性規(guī)劃問(wèn)題解的特點(diǎn)第8頁(yè)/共47頁(yè)Max(Min)Z=c1x1

+c2

x2

+…+cn

xna11x1+a12

x2

+…+a1n

xn≤(=,≥)b1a21x1+a22x2

+…+a2n

xn≤(=,≥)b2

┆am1x1+am2

x2

+…+amn

xn≤(=,≥)bmx1

，x2，…

，xn≥0約束條件：目標(biāo)函數(shù)：滿(mǎn)足約束條件的解，稱(chēng)為線性規(guī)劃問(wèn)題的可行解．所有可行解的集合稱(chēng)為可行域.線性規(guī)劃問(wèn)題的最優(yōu)解和最優(yōu)值一、線性規(guī)劃問(wèn)題解的基本概念第9頁(yè)/共47頁(yè)（一）用圖解法解極大化問(wèn)題

例1．MaxZ

＝60x

＋50y

2x

＋4y≤80

3x

＋2y≤60

x,y≥0(1)以x、y作為坐標(biāo)軸，建立平面直角坐標(biāo)系根據(jù)x、y非負(fù)的約束，可行解區(qū)域位于第一象限（見(jiàn)圖（a））xyo圖(a)1.圖示全部約束條件，確定可行解區(qū)域

解：第10頁(yè)/共47頁(yè)（2）用等式約束代替非等

式約束，畫(huà)出直線

2x＋4y＝80

3x＋2y＝60

（見(jiàn)圖（b））（3）根據(jù)不等式約束,確定可行

解區(qū)域

2x＋4y≤

80

3x＋2y≤

60

（見(jiàn)圖（c））0xy圖(b)2x＋4y＝803x＋2y＝600xy圖(c)2x

＋4y≤80

3x

＋2y≤60第11頁(yè)/共47頁(yè)（1）等直線法：把目標(biāo)函數(shù)Z＝60x＋50y

看成是隨著Z的取值不同而產(chǎn)生的一族直線。令目標(biāo)函數(shù)值分別為0、600、1200作平行線族（圖（2））

從圖中可見(jiàn)，Z值越高，目標(biāo)函數(shù)直線離原點(diǎn)越遠(yuǎn)。所以，尋找最優(yōu)解問(wèn)題可歸結(jié)為：找出離原點(diǎn)最遠(yuǎn)的一條直線與可行解集的交點(diǎn)。2．從可行解中找出最優(yōu)解（1）等直線法（2）試算法0xy(c)MaxZ

＝60x

＋50y第12頁(yè)/共47頁(yè)（2）試算法：（a）線性規(guī)劃的可行域是凸多邊形或凸集；（b）線性規(guī)劃的最優(yōu)解如果存在，必然在可行解集的某個(gè)頂點(diǎn)上達(dá)到。試算法的依據(jù)先求出可行解集各頂點(diǎn)的坐標(biāo)然后試算目標(biāo)函數(shù)之值使目標(biāo)函數(shù)達(dá)到極值的解為最優(yōu)解（見(jiàn)下面表1－3）第13頁(yè)/共47頁(yè)表1－3例1試算結(jié)果目標(biāo)函數(shù)可行解集頂點(diǎn)頂點(diǎn)的坐標(biāo)目標(biāo)函數(shù)之值Ｏ0Ａ1200Ｂ1350(最優(yōu)解)Ｃ1000最優(yōu)解為（x，y）＝（10，15）

最優(yōu)值為ZMax＝

1350（2）試算法：第14頁(yè)/共47頁(yè)（二）圖解法求解極小化問(wèn)題例２MinZ

＝50x

＋80y4x+10y

≥4010x

＋5y≥5035x

+35y≥245

x，

y≥0解：1、圖示全部約束條件，確定可行解區(qū)域

第15頁(yè)/共47頁(yè)2．可行解中找出最優(yōu)解

（1）用等直線法求最優(yōu)解。本例是極小值問(wèn)題，因此目標(biāo)函數(shù)值取離原點(diǎn)盡可能近的等直線的值（見(jiàn)圖（4））。通過(guò)p2點(diǎn)的等直線離原點(diǎn)最近，p2點(diǎn)的坐標(biāo)既滿(mǎn)足全部約束條件又能使目標(biāo)函數(shù)取得最小值，

故為最優(yōu)解。

（2）用試算法求最優(yōu)解（見(jiàn)表1－4）第16頁(yè)/共47頁(yè)

表1-4例2試算結(jié)果目標(biāo)函數(shù)可行解集頂點(diǎn)頂點(diǎn)的坐標(biāo)目標(biāo)函數(shù)之值Ｐ1500Ｐ2410(最優(yōu)解)Ｐ3470Ｐ4800最優(yōu)解為（x，y）＝（5，2）

最優(yōu)值為ZMin＝410第17頁(yè)/共47頁(yè)例3三、線性規(guī)劃問(wèn)題解的特點(diǎn)第18頁(yè)/共47頁(yè)

解：在本例中，由于目標(biāo)函數(shù)（Z＝2x＋4y）的等直線與約束條件（x＋2y≤8）的直線相平行，故最優(yōu)解同時(shí)在兩個(gè)頂點(diǎn)上達(dá)到。則在此兩頂點(diǎn)連線上的任何一點(diǎn)都是最優(yōu)解，即有無(wú)限多個(gè)最優(yōu)解。第19頁(yè)/共47頁(yè)

從圖（6）可見(jiàn)，本

例的可行域無(wú)上界，目

標(biāo)函數(shù)的值可趨于無(wú)窮

大。在這種情況下無(wú)法

確定最優(yōu)解。解：例4第20頁(yè)/共47頁(yè)

從圖（7）可以看出，

本題的可行域是一個(gè)空集，

因此無(wú)可行解。這是由于

本題中包括了相互矛盾的

約束條件的緣故。解：

例5第21頁(yè)/共47頁(yè)線性規(guī)劃問(wèn)題解的幾種情況（1）有唯一的最優(yōu)解。這時(shí)最優(yōu)解一定在可行域的某個(gè)頂點(diǎn)達(dá)到；（2）有最優(yōu)解，但不唯一。這時(shí)最優(yōu)解一定充滿(mǎn)一個(gè)線段，此線段是可行域的一條邊；（3）有可行解，但沒(méi)有最優(yōu)解。這時(shí)可行域上的點(diǎn)能使目標(biāo)函數(shù)趨向無(wú)窮大；（4）沒(méi)有可行解（空集）。即線性規(guī)劃問(wèn)題是不可行的。第22頁(yè)/共47頁(yè)圖解法的優(yōu)點(diǎn)及局限性圖解法的局限性：

一般僅適用于只有兩個(gè)變量的。對(duì)于三維以上的模型，約束條件表現(xiàn)為平面，這就難用圖解法去求解了。圖解法的優(yōu)點(diǎn)：

直觀、形象，它容易使人具體地認(rèn)識(shí)線性規(guī)劃模型的求解過(guò)程。#第23頁(yè)/共47頁(yè)第二章

線性規(guī)劃第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型第二節(jié)線性規(guī)劃問(wèn)題的圖解法第三節(jié)單純形法第四節(jié)線性規(guī)劃的對(duì)偶問(wèn)題第五節(jié)線性規(guī)劃在衛(wèi)生管理中的應(yīng)用?第24頁(yè)/共47頁(yè)第三節(jié)單純形法一、單純形法的基本原理

三、大M法二、單純形解法第25頁(yè)/共47頁(yè)一、單純形法的基本原理（一）線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)規(guī)范型（二）基本變量（三）基本解（四）基本可行解（五）單純形法的原理1.標(biāo)準(zhǔn)型（P11三）2.規(guī)范型（典型方程式）小結(jié)第26頁(yè)/共47頁(yè)1.線性規(guī)劃的標(biāo)準(zhǔn)型（一）線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型和規(guī)范型四個(gè)特點(diǎn)：目標(biāo)最大化約束為等式變量均非負(fù)右端項(xiàng)非負(fù)

第27頁(yè)/共47頁(yè)書(shū)寫(xiě)形式（1）簡(jiǎn)縮形式

（2）矩陣形式見(jiàn)教材P12

第28頁(yè)/共47頁(yè)

（1）極小化目標(biāo)函數(shù)的問(wèn)題

設(shè)目標(biāo)函數(shù)為令Z＝－f

則可轉(zhuǎn)化為標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形式的轉(zhuǎn)化第29頁(yè)/共47頁(yè)（2）約束條件不是等式的問(wèn)題顯然，S也具有非負(fù)約束，即S≥0可以引進(jìn)一個(gè)新的變量S，使得：①設(shè)約束條件為：第30頁(yè)/共47頁(yè)類(lèi)似地引進(jìn)一個(gè)新變量S，使得：為了使約束由不等式成為等式而引進(jìn)的變量S，稱(chēng)為“松弛變量”。如果原問(wèn)題中有若干個(gè)非等式約束，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。(S≥0)②當(dāng)約束條件為（2）約束條件不是等式的問(wèn)題第31頁(yè)/共47頁(yè)

在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量有非負(fù)約束，當(dāng)某一個(gè)變量xj沒(méi)有非負(fù)約束時(shí)，令（3）變量無(wú)符號(hào)限制的問(wèn)題第32頁(yè)/共47頁(yè)

（4）右端項(xiàng)有負(fù)值的問(wèn)題在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)，當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，則把該等式約束兩端同時(shí)乘以－1，得到：

第33頁(yè)/共47頁(yè)例1

將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：第34頁(yè)/共47頁(yè)

例2

將線性規(guī)劃問(wèn)題

轉(zhuǎn)化為標(biāo)準(zhǔn)形式

解：標(biāo)準(zhǔn)形式為第35頁(yè)/共47頁(yè)2.規(guī)范型（典型方程式）例:

解下列線性方程組第36頁(yè)/共47頁(yè)第37頁(yè)/共47頁(yè)一般情況典型方程式每個(gè)約束方程中要有一個(gè)變量的系數(shù)１，而這個(gè)變量在其余方程中不出現(xiàn)。系數(shù)矩陣中包含一個(gè)單位子矩陣第38頁(yè)/共47頁(yè)規(guī)范化典型方程組2.規(guī)范型（典型方程式）規(guī)范型方程組第39頁(yè)/共47頁(yè)（二）基本變量如果變量xj在某一方程中系數(shù)為1，而在其它一切方程中的系數(shù)為零，則稱(chēng)xj為該方程中的基本變量．否則為非基本變量.

基本變量為線性無(wú)關(guān)的方程的個(gè)數(shù)基本變量的組數(shù)為第40頁(yè)/共47頁(yè)（三）基本解在典型方程中，設(shè)非基本變量為零，求解基本變量得到的解，稱(chēng)為基本解．基本解的個(gè)數(shù)為個(gè)。

（四）基本可行解基本變量為非負(fù)的一組基本解稱(chēng)為基本可行解，基本可行解的個(gè)數(shù)最多不超過(guò)

個(gè)。

不是基本可行解第41頁(yè)/共47頁(yè)得到最優(yōu)解或證明最優(yōu)解不存在標(biāo)準(zhǔn)型從可行域某個(gè)頂點(diǎn)開(kāi)始檢查該點(diǎn)是否最優(yōu)解不是取一個(gè)“相鄰”、“更好”的頂點(diǎn)(五)單純形法的基本原理規(guī)范型初始基本可行解第42頁(yè)/共47頁(yè)第一步建立平面直角坐標(biāo)系第二步求滿(mǎn)足約束條件的可行解域（或判斷可行解域不存在）第三步用等值線法或試算法，確定最優(yōu)解（或判斷最優(yōu)解不存在）。第四步寫(xiě)出最優(yōu)解并確定最優(yōu)值。2.兩個(gè)變量的線性規(guī)劃問(wèn)題的圖解法步驟本次課小結(jié)第二節(jié)線性規(guī)劃問(wèn)題的圖解法３．線性規(guī)劃問(wèn)題解的幾種情況1.線性規(guī)劃問(wèn)題解的基本概念第43頁(yè)/共47頁(yè)①