運(yùn)籌學(xué)習(xí)題課課件

運(yùn)籌學(xué)第一次習(xí)題課運(yùn)籌學(xué)第一次習(xí)題課1.1用圖解法求解下列線性規(guī)劃問題，并指出問題具有最優(yōu)解、無窮解無界解還是無可行解。（a）S.T1.1用圖解法求解下列線性規(guī)劃問題，并指出問題具有最優(yōu)解、無解：該問題有無窮最優(yōu)解，即滿足且

的所有（），此時(shí)目標(biāo)函數(shù)值為3

解：（c）由圖可知在點(diǎn)（10，6）處目標(biāo)函數(shù)取得最大值16。線性規(guī)劃有唯一最優(yōu)解。（c）（補(bǔ)充）（b）（補(bǔ)充）（b）解：用圖解法找不到滿足所有約束條件的公共范圍，則該問題無解。解：1.2對(duì)下述線性規(guī)劃找出所有基解，指出哪些是基可行解，并確定最優(yōu)解。（a）

s.t.1.2對(duì)下述線性規(guī)劃找出所有基解，指出哪些是基可行解，并確定解:寫出約束方程的系數(shù)矩陣A=14-28-1234R(A)=2，所以只要找出2個(gè)列向量組成矩陣滿秩，這兩個(gè)向量就是線性規(guī)劃問題的一個(gè)基，

由于與線性相關(guān)不能構(gòu)成基，構(gòu)建表格列出全部基，基解，指出基可行解，*標(biāo)注的為最優(yōu)解：解:寫出約束方程的系數(shù)矩陣基

是基可行解？目標(biāo)函數(shù)值

0?00是-2

8030是31*0001/4是-3/20?00是-20001/4是-3/2基解

基是基可行解？目標(biāo)函數(shù)值(補(bǔ)充)（b）(補(bǔ)充)（b）運(yùn)籌學(xué)習(xí)題課課件運(yùn)籌學(xué)習(xí)題課課件1.3分別用圖解法和單純形法求解下述線性規(guī)劃問題，并對(duì)照指出單純形表中的各基行解分別對(duì)應(yīng)圖解法中可行域的哪一個(gè)定點(diǎn).(b)S.t.1.3分別用圖解法和單純形法求解下述線性規(guī)劃問題，并對(duì)照指由圖可知最優(yōu)解為的解x=(7/2,3/2),最大值z(mì)=17/2由圖可知最優(yōu)解為(2)單純形法首先在各約束條件上添加松弛變臉，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式S.t.(2)單純形法首先在各約束條件上添加松弛變臉，將問題轉(zhuǎn)化為標(biāo)則組成一個(gè)基，令得基可行解，由此列出初始單純形表21000

基b0150240505100

6201011001-4521000則組成一個(gè)基，令21初始表對(duì)應(yīng)定點(diǎn)（0，0）對(duì)應(yīng)點(diǎn)（4，0）21000

基b015240105100

11/301/6002/30-1/613123/201/30-1/30初始表對(duì)應(yīng)定點(diǎn)（0，0）2100表明已經(jīng)找到問題的最優(yōu)解對(duì)應(yīng)點(diǎn)，最大值為17/221000

基b015/227/213/20015/4-15/2

1001/4-1/2010-1/43/2000-1/4-1/221000(補(bǔ)充)（a）st(補(bǔ)充)（a）（圖解法）（圖解法）（單純形法）（單純形法）運(yùn)籌學(xué)習(xí)題課課件運(yùn)籌學(xué)習(xí)題課課件運(yùn)籌學(xué)習(xí)題課課件1.6將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式，并列出初始單純形表。（a）st1.6將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式，并列出初始單純形表。（解：在約束條件中添加松弛變量或剩余變量，且令，，該問題轉(zhuǎn)化為解：在約束條件中添加松弛變量或剩余變量，且令其約束系數(shù)矩陣為23-3410A=41-1-20-13-11-300在A中人為的添加兩列單位向量運(yùn)籌學(xué)習(xí)題課課件23-341000A=41-1-20-1103-11-30001令得到初始單純形表23-34100-3-11-200-M-M基b01223-341000-M841-1-20-110-M63-11-300017M-3-11-2-M0-M00-3-11-200-M-M基b01223-341000-M81.7分別用單純形法中的大M法和兩階段法求解下列線性規(guī)劃問題,并指出屬那里類解(a)st1.7分別用單純形法中的大M法和兩階段法求解下列線性規(guī)劃問題(1)大M法將上述線性規(guī)劃問題中分別減去剩余變量再加上人工變量，得st(1)大M法將上述線性規(guī)劃問題中分別減去剩余變量其中M是一個(gè)任意大的正數(shù)。據(jù)此列出單純形表2-120-M0-M0-M基b-M6111-1100006-M2-20100-1100--M002-10000-1102-M3M-12+M-M0-M0-M0其中M是一個(gè)任意大的正數(shù)。據(jù)此列出單純形表2-120-M0-2-120-M0-M0-M基b-M6103/2-11001/204-M2-20100-11002-1001-1/20000-1/21-2-M0-M0-M02-120-M0-M0-M基b-M6103/2-11001/2-120-M0-M0-M基b-M3400-113/2-3/21/2-1/23/422-20100-1100--11-11000-1/21/2-1/2-1/2-4M+500-M02-120-M0-M0-M基b-M3400-113/2-3/由于>0且，則該線性規(guī)劃問題有無界解2-120-M0-M0-M基b23/4100-1/4?3/8-3/81/8-1/83/427/2001-1/2?-1/41/41/4-1/4--17/4010-1/41/4-1/81/8-3/8-5/8-0005/4-3/82-120-M0-M0-M基b23/4100-1/4?3/8（2）兩階段法現(xiàn)在上述線性規(guī)劃問題的約束條件中分別減去剩余變量，再加上人工變量，得第一階段的數(shù)學(xué)模型由此可列出單純形表（2）兩階段法現(xiàn)在上述線性規(guī)劃問題的約束條件中分別減去剩余變000010101基b16111-110000612-20100-1100-1002-10000-1-01-3-111000010101基b16111-110000612-201000010101基b16103/2-11001/2-1/2412-20100-110020001-1/20000-1/21/2-10-5/211000010101基b16103/2-11001/2-1/2-000010101基b13400-113/2-3/21/2-1/23/402-20100-1100-01-11000-1/21/2-1/21/2--4001-3/23/2-1/2-000010101基b13400-113/2-3/21/2第一階段求得最優(yōu)解目標(biāo)函數(shù)的最優(yōu)值為0。000010101基b03/4100-1/41/43/8-3/81/8-1/807/2001-1/2-1/2-1/41/41/4-//407/4010-1/41/4-1/81/8-3/83/8000010101000010101基b03/4100-1/41/43/8-3因?yàn)槿斯ぷ兞咳繛?，則X是線性規(guī)劃問題的基可行解，于是可以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量表取消，并填入原問題的目標(biāo)函數(shù)的系數(shù)，進(jìn)行第二階段的運(yùn)算，其表如下：因?yàn)槿斯ぷ兞咳繛?，則X是線性規(guī)劃問題的基可行解，于是可以You有表知道>0,而所以線性規(guī)劃問題有無界解2-12000基b23/4100-1/43/81/827/2001-1/2-1/41/4-17/4010-1/4-1/8-3/80005/4-3/8-9/8You2-12000基b23/4100-1/43/81/82(補(bǔ)充)（b）st(補(bǔ)充)（b）（大M法）化成標(biāo)準(zhǔn)形（大M法）化成標(biāo)準(zhǔn)形-2-3-100-M-M基b-M8142-10102-M62300-10134M-26M-32M-1-M-M00-2-3-100-M-M基b-M8142-10102-M62-2-3-100-M-M基b-321/411/2-1/401/408-M25/20-11/2-1-1/214/50-M0-2-3-100-M-M基b-321/411/2-1/401-2-3-100-M-M基b-39/5013/5-3/101/103/10-1/10-24/510-2/51/5-2/5-1/52/5000-1/2-1/2-2-3-100-M-M基b-39/5013/5-3/101運(yùn)籌學(xué)習(xí)題課課件（二階段法）（二階段法）運(yùn)籌學(xué)習(xí)題課課件運(yùn)籌學(xué)習(xí)題課課件運(yùn)籌學(xué)習(xí)題課課件1.10判斷并說明理由（a）對(duì)取值無約束的變量通常令

，其中，，在單純形法求得的最優(yōu)解中，有可能同時(shí)出現(xiàn)（b）若X1,X2分別是某一線性規(guī)劃的最優(yōu)解，則X=aX1+(1-a)X2也該是線性規(guī)劃問題的最優(yōu)解，其中0a1。1.10判斷并說明理由（a）對(duì)取值無約束的變量通常令（c）單純形法計(jì)算中選取最大正校驗(yàn)數(shù)

對(duì)應(yīng)的變量作為換入基的變量，將使得迭代后的目標(biāo)函數(shù)值得到最快增長。（d）含有n個(gè)變量m個(gè)約束的標(biāo)準(zhǔn)型的線性規(guī)劃問題，基解數(shù)恰好為。（e）如線性規(guī)劃問題存在可行域，則可行域一定包含坐標(biāo)的原點(diǎn)。（c）單純形法計(jì)算中選取最大正校驗(yàn)數(shù)1.12已知線性規(guī)劃問題St用單純形法求解最終單純形表如下，表中

為松弛變量1.12已知線性規(guī)劃問題1/5103/5-1/53/501-1/52/5-7/1000-3/5-4/51/5103/5-1/53/501-1/52/5-7/100解：由表可知為此線性規(guī)劃問題最優(yōu)解，必在可行域頂點(diǎn)上，此頂點(diǎn)為帶入解得解：由表可知為此線性規(guī)劃問題最優(yōu)解，必在可由表可知解得由表可知1.19已知線性規(guī)劃問題迭代某步的單純形表如下：b41002-1-501-103-300-4100001.19已知線性規(guī)劃問題迭代某步的單純形表如下：b41002問在什么條件下：（a）表中解為唯一最優(yōu)解；（b）表中解最優(yōu)，但具有無窮多最優(yōu)解；（c）現(xiàn)有基解為退化解；（d）問題具有無界解；（e）現(xiàn)有基解中，用替換后目標(biāo)函數(shù)進(jìn)一步優(yōu)化。問在什么條件下：運(yùn)籌學(xué)習(xí)題課課件運(yùn)籌學(xué)習(xí)題課課件

1.21北海銀行一個(gè)分理處每天個(gè)時(shí)間段對(duì)職員的需求如下表：