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

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

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

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

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

③寫出目標(biāo)函數(shù)。第5頁/共47頁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稱為成本或利潤(rùn)系數(shù)bi稱為限定系數(shù)

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

#第6頁/共47頁第二章

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

1、圖解法解極大化問題2、圖解法求解極小化問題一、線性規(guī)劃問題解的基本概念二、兩個(gè)變量的線性規(guī)劃問題的圖解法三、線性規(guī)劃問題解的特點(diǎn)第8頁/共47頁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ī)劃問題的可行解．所有可行解的集合稱為可行域.線性規(guī)劃問題的最優(yōu)解和最優(yōu)值一、線性規(guī)劃問題解的基本概念第9頁/共47頁（一）用圖解法解極大化問題

例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ū)域位于第一象限（見圖（a））xyo圖(a)1.圖示全部約束條件，確定可行解區(qū)域

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

式約束，畫出直線

2x＋4y＝80

3x＋2y＝60

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

解區(qū)域

2x＋4y≤

80

3x＋2y≤

60

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

＋4y≤80

3x

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

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

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

＝60x

＋50y第12頁/共47頁（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)解（見下面表1－3）第13頁/共47頁表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頁/共47頁（二）圖解法求解極小化問題例２MinZ

＝50x

＋80y4x+10y

≥4010x

＋5y≥5035x

+35y≥245

x，

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

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

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

故為最優(yōu)解。

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

表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頁/共47頁例3三、線性規(guī)劃問題解的特點(diǎn)第18頁/共47頁

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

從圖（6）可見，本

例的可行域無上界，目

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

大。在這種情況下無法

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

從圖（7）可以看出，

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

因此無可行解。這是由于

本題中包括了相互矛盾的

約束條件的緣故。解：

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

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

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

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

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

第27頁/共47頁書寫形式（1）簡(jiǎn)縮形式

（2）矩陣形式見教材P12

第28頁/共47頁

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

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

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

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

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

第33頁/共47頁例1

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

例2

將線性規(guī)劃問題

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

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

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

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

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

個(gè)。

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