線性規(guī)劃問題概述第一頁，共四十六頁，編輯于2023年，星期一線性規(guī)劃教學(xué)大綱一、本課程教學(xué)目的是使同學(xué)們從理論上，應(yīng)用上掌握運(yùn)籌學(xué)的一個(gè)基本分枝---線性規(guī)劃。二、基本要求：（1）通過學(xué)習(xí)，熟悉線性規(guī)劃的基本概念；能熟練的運(yùn)用線性規(guī)劃解決實(shí)際問題，包括建立模型。求解和解后的經(jīng)濟(jì)分析基本方法。（2）從數(shù)學(xué)理論上完善的了解線性規(guī)劃基本原理，以及該課題新近的發(fā)展動態(tài)。（3）強(qiáng)調(diào)掌握對偶單純形法及靈敏度的分析的經(jīng)濟(jì)意義。第二頁，共四十六頁，編輯于2023年，星期一（4）課后安排適量作業(yè)，鞏固所學(xué)內(nèi)容，要求按時(shí)完成。（5）對部分有能力的同學(xué)，引導(dǎo)他們通過計(jì)算機(jī)實(shí)習(xí)，編制程序解題。三、教學(xué)計(jì)劃與內(nèi)容提綱：1教學(xué)內(nèi)容與學(xué)時(shí)匹配，見教學(xué)日歷。2教學(xué)內(nèi)容大綱：第一章線性規(guī)劃問題概述

1花一節(jié)課時(shí)間介紹線性規(guī)劃的發(fā)展歷史和發(fā)展動態(tài)以及在經(jīng)濟(jì)分析等實(shí)際工作中的應(yīng)用，調(diào)動同學(xué)們的學(xué)習(xí)興趣。

2建模部分著重講一些實(shí)際問題的線性規(guī)劃模型建立過程；突出模型的三要素：目標(biāo)方程，決策變量，約束方程。

3線形規(guī)劃的幾何解法，主要是在平面上用圖形如何解二維的規(guī)劃問題，注意從中得出結(jié)論，最優(yōu)解在解這一領(lǐng)域的頂點(diǎn)達(dá)到。第三頁，共四十六頁，編輯于2023年，星期一

1交代清楚基本概念。

2基本定理2.2.2是重點(diǎn)講解內(nèi)容，其證明過程的推導(dǎo)過程要詳細(xì)講解。由此定理，強(qiáng)調(diào)一個(gè)結(jié)論，若一個(gè)線性規(guī)劃問題有最優(yōu)解，則必有最優(yōu)基本可行解。也就是說最優(yōu)解必可在可行解域的極點(diǎn)上達(dá)到。這是后面單純形法的基本啟發(fā)思想。

3極射向和可行解表示定理，這部分內(nèi)容比較偏重理論推導(dǎo)過程，要求同學(xué)們對定理2.3.2特別清楚的了解，這是后面判一個(gè)問題設(shè)有最優(yōu)解的基本理論，也是單純形法的一個(gè)終止原則。至于可行解的表示定理，純屬理論證明之用，故此講解時(shí)，注意把證明的思想將清楚。第二章線性規(guī)劃的基本概念和基本定理第四頁，共四十六頁，編輯于2023年，星期一第三章單純形法本章是線性規(guī)劃的一個(gè)核心內(nèi)容，要重點(diǎn)介紹一下。

1單純形法的概念部分主要講述三個(gè)內(nèi)容：（1）極軸的運(yùn)算（2）判別數(shù)定義（3）最優(yōu)判別定理2對單純形法分兩種方式介紹：（1）數(shù)值迭代公式方法，這里要注意推導(dǎo)極軸運(yùn)算過程，證出迭代公式。（2）表上作業(yè)法兩種方法都重要，前者便于計(jì)算機(jī)運(yùn)算，后者便于手工計(jì)算。在介紹他們時(shí)都要注意以下問題：<A>極軸元的選擇方式，過程。<B>數(shù)值迭代或表變換過程，步驟。<C>終止準(zhǔn)則（有或無最優(yōu)解）。<D>收斂性定理。第五頁，共四十六頁，編輯于2023年，星期一5Bland先行循環(huán)的方法，粗略介紹。6修正單純形法，主要用于計(jì)算機(jī)運(yùn)算，請同學(xué)們自學(xué)7求最優(yōu)基本可行解，每個(gè)最優(yōu)基本可行解對于實(shí)際工作的決策者來說，就是一種最優(yōu)決策方案，因此能夠求出最優(yōu)基本可行解，就能為決策者提供可用方案。3人工變量方法，為了尋找單純形法的新始基可行解，引進(jìn)人工變量，介紹兩階段方法求解過程；增加內(nèi)容：大M方法產(chǎn)生新始基可行解。4退化與循環(huán)問題，講情楚Beale的例子，說明線性規(guī)劃中在退化情性下可能出現(xiàn)循環(huán)現(xiàn)象，著重介紹-攝動法先行循環(huán)；注意從理論上完備S-攝動法即定理3.4.2的結(jié)論及其的證明過程要交代清楚，著重講解。第六頁，共四十六頁，編輯于2023年，星期一第四章線形規(guī)劃的對偶定理及應(yīng)用1注意從實(shí)際問題中引出對偶規(guī)劃的概念。

2重點(diǎn)介紹對稱形式對規(guī)劃及對偶定理。對定理4.1.1，4.1.2，4.1.3，全面地描述了一對偶規(guī)劃的解之間的關(guān)系，注意把這三個(gè)定理串聯(lián)起來對對偶規(guī)劃綜合分析。

對偶定理4.1.4，注意說明由此引出的松緊概念。

3非對稱對偶規(guī)劃。與對稱對偶規(guī)劃的四個(gè)對偶定理對比研究，啟發(fā)同學(xué)們對對偶單純形法基本思想的初步認(rèn)識。第七頁，共四十六頁，編輯于2023年，星期一

4混合形對偶規(guī)劃，要舉出幾個(gè)實(shí)例證明如何由一個(gè)問題，寫出另一個(gè)對偶問題的方法，強(qiáng)調(diào)解題過程，第一要對問題形式規(guī)范化，第二要掌握對偶表，根據(jù)對偶表寫出對偶問題。5對偶單純形法，與第三章的單純形法對比研究，哪些不同，哪些相同，迭代公式，表格形式，迭代過程。6對偶單純形法的經(jīng)濟(jì)意義，舉一個(gè)實(shí)際例子，證明由一個(gè)對偶單純形最終表，一個(gè)決策者可以得到什么信息第八頁，共四十六頁，編輯于2023年，星期一第五章靈敏度分析

1為什么要對線性規(guī)劃問題進(jìn)行靈敏度分析，主要從經(jīng)濟(jì)分析方面回答。

2本章各節(jié)均與第四章內(nèi)容緊密聯(lián)系，因此講授時(shí)，一要提醒同學(xué)們復(fù)習(xí)，二要簡明提出一些重要內(nèi)容課堂復(fù)習(xí)。

3對三個(gè)靈敏度分析專題：新增變量，新增約束，系數(shù)cj,bi,aij

變化。各舉一到兩個(gè)實(shí)例說明分析的方法和經(jīng)濟(jì)意義。第九頁，共四十六頁，編輯于2023年，星期一第六章變量有界限制的線性規(guī)劃問題

1

問題的標(biāo)準(zhǔn)形式及其基本概念，重點(diǎn)講解最優(yōu)判別定理7.1.1。

2

問題的算法，主要介紹第一階段算法的最優(yōu)準(zhǔn)則算法思想和算法過程，及第二階段中心樞紐運(yùn)算過程尋找新的基矩陣。

3迭代收斂性定理7.4.1重點(diǎn)講解。它證明了上面建立的算法是有限終止的。

4花一課時(shí)間深細(xì)講一個(gè)例子，說明算法步驟及其中諸深細(xì)細(xì)節(jié)問題。第十頁，共四十六頁，編輯于2023年，星期一

線性規(guī)劃

LinearProgramming

前言

一線性規(guī)劃的發(fā)展史參考書目：北京理工大學(xué)出版社，

許萬蓉，《線性規(guī)劃》。山東科學(xué)技術(shù)出版社

《線性規(guī)劃》。29.183GMG

管梅谷，鄭漢鼎。研究線性規(guī)劃最早的是蘇聯(lián)的П.В.канторович（康脫洛維奇），1939年，他發(fā)表了《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書。主要討論了機(jī)床、負(fù)荷、下料運(yùn)輸?shù)葐栴}。但他提出的問題在當(dāng)時(shí)并未引起人們的注意。他自己也未能提出一個(gè)統(tǒng)一的求解方法。第十一頁，共四十六頁，編輯于2023年，星期一在第二次世界大戰(zhàn)期間，由于軍事運(yùn)輸?shù)男枰?，提出線性問題的解法，美國的經(jīng)濟(jì)學(xué)家柯普曼（Koupman）也研究了運(yùn)輸問題。直到1947年，美國的G.B.Dantzig提出了求解線性規(guī)劃的單純形法，才使線性規(guī)劃這門學(xué)科在理論上趨于成熟，并成功地運(yùn)用到了工業(yè)、交通、農(nóng)業(yè)、軍事等各個(gè)領(lǐng)域內(nèi)，使線性規(guī)劃的理論與方法成為管理科學(xué)的重要內(nèi)容。在當(dāng)今電子技術(shù)高度發(fā)展的信息社會中，線性規(guī)劃給人類在經(jīng)濟(jì)管理、生產(chǎn)管理、人才事務(wù)管理等方面發(fā)揮了巨大作用?，F(xiàn)在對于成千上萬個(gè)約束條件、成千上萬個(gè)變量的線性規(guī)劃問題在計(jì)算上已沒有任何問題。據(jù)20世紀(jì)80年代末美國一個(gè)雜志對全美500家大公司的調(diào)查，線性規(guī)劃的應(yīng)用范圍名列前茅，有85%的公司頻繁使用線性規(guī)劃。第十二頁，共四十六頁，編輯于2023年，星期一二線性規(guī)劃問題的特點(diǎn)由于是管理科學(xué)的重要分支，也是它的最成熟，最完整的分支。而管理科學(xué)的特點(diǎn)是利用數(shù)學(xué)模型為管理人員提供方針，以便在現(xiàn)有信息的情況下作出有效的決策，或現(xiàn)有信息不足作出決策時(shí)，而去搜索更多的信息。這里我們要抓住以下幾個(gè)要素：第一管理科學(xué)的核心是建立模型。即運(yùn)用數(shù)學(xué)的抽象，住所要探討對策問題最重要的特征。模型是現(xiàn)實(shí)的簡化表示。

笫二通過模型設(shè)計(jì)，給管理工作提供方便.

笫三進(jìn)行有效決策所需信息的多少，決策所要探討問題的復(fù)雜程度，而不決定于研究過程所用的工具。模型要求過多的信息就不是好模型。線性規(guī)劃也是這樣通過模型，求解，分析綜合，為決策者提供科學(xué)決策依據(jù)。第十三頁，共四十六頁，編輯于2023年，星期一三線性規(guī)劃的主要應(yīng)用線性規(guī)劃主要應(yīng)用在以下幾個(gè)方面：（1）在某一企業(yè)內(nèi)部，如何配合產(chǎn)品的銷售時(shí)間，在各部門的原料，產(chǎn)品的存儲，分配的數(shù)量等最為合理。（2）在某一企業(yè)生產(chǎn)的產(chǎn)品數(shù)量（或產(chǎn)值），如何使現(xiàn)有的設(shè)備，人力，原料等條件限制下，合理組織生產(chǎn)，使經(jīng)濟(jì)效益最高。（3）在某地的交通網(wǎng)中，如何合理組織運(yùn)輸，使運(yùn)費(fèi)最小。（4）在市場上產(chǎn)品的（或原料）價(jià)格變動時(shí)，對于這些變動，企業(yè)如何做出最優(yōu)決策。（5）合理下料問題，即利用某種原料下料時(shí)，如何達(dá)到既滿足要求，又使原料最少。第十四頁，共四十六頁，編輯于2023年，星期一（6）配料問題，即生產(chǎn)由各種原料生產(chǎn)的的產(chǎn)品時(shí)（如混合飼料等）時(shí)，如何既滿足規(guī)定的質(zhì)量的標(biāo)準(zhǔn)，又使產(chǎn)品的成本最低。（7）庫存問題，在倉庫的容量及其他條件的限制下，確定庫存物資的品種，數(shù)量，期限，使庫存的效益最高。（8）在投入產(chǎn)出問題中，引進(jìn)某一目標(biāo)函數(shù)，制定最優(yōu)的企業(yè)（或地區(qū)）經(jīng)濟(jì)計(jì)劃。當(dāng)前，我國正在進(jìn)行以城市為重點(diǎn)的整個(gè)經(jīng)濟(jì)體制的改革，企業(yè)的自主權(quán)在擴(kuò)大。一個(gè)企業(yè)要適應(yīng)國內(nèi)，國際的市場競爭，就必須改善經(jīng)營管理，提高經(jīng)濟(jì)效益，制定最優(yōu)的生產(chǎn)計(jì)劃，并對瞬息萬變的市場信息作出反映，應(yīng)用現(xiàn)代數(shù)學(xué)方法，特別是線性規(guī)劃方法，對于提高企業(yè)管理水平和企業(yè)活力，將會起著極大的作用。第十五頁，共四十六頁，編輯于2023年，星期一第一章線性規(guī)劃問題概述

§1.1線性規(guī)劃問題舉例及數(shù)學(xué)模型例1．（生產(chǎn)安排問題）某廠生產(chǎn)A,B兩種產(chǎn)品。生產(chǎn)一噸A需用煤九噸，電力4千瓦，勞動力三個(gè)（以勞動日計(jì)算）；生產(chǎn)一噸B需用煤3噸，電力五千瓦，勞動力10個(gè)。已知一噸A可獲利C1元，一噸B可獲利C2元。該廠現(xiàn)有煤360噸，電力200千瓦，勞動力300個(gè)，問：生產(chǎn)A、B各多少噸獲利最大？試建立這一問題的數(shù)學(xué)模型。第十六頁，共四十六頁，編輯于2023年，星期一煤耗：9x1+4x2≤360

電耗：4x1+5x2≤200解：首先列出數(shù)據(jù)表：第十七頁，共四十六頁，編輯于2023年，星期一勞動力耗：3x1+10x2≤300

生產(chǎn)數(shù)量：x1≥0x2≥0注意：約束條件兩邊單位要一致。從而此問題的數(shù)學(xué)模型為：求一組變量x1，x2值，使?jié)M足：第十八頁，共四十六頁，編輯于2023年，星期一例2．設(shè)有鋼材150根，長15米，需軋成配套鋼料。每套由7根2米長與2根7米長的鋼梁組成，問如何下料使鋼材廢料最少（設(shè)不計(jì)下料損耗）？解：依題意，每根鋼材的下料有三種可能情形：

1）截7米長0根，2米的7根，余1米廢料。

2）截7米長1根，2米長4根，無廢料。

3）截7米長2根，2米長0根。余1米廢料。設(shè)用第j截法，用去鋼材xj根（j=1，2，3）。則這批鋼材截成7米長的鋼梁為x2+2x3根，2米長的7x1+4x2根，廢料總長x1+x3米.于是，得出問題的數(shù)學(xué)模型為：求一組變量x1,x2,x3,的值，使?jié)M足：第十九頁，共四十六頁，編輯于2023年，星期一第二十頁，共四十六頁，編輯于2023年，星期一主要配料是：石灰石，谷物，大豆粉，其營養(yǎng)成分如下：問應(yīng)如何處理配料，使在營養(yǎng)和物質(zhì)條件均滿足的情況解：設(shè)生產(chǎn)100斤飼料，需用x1斤石灰石，x2斤谷物，x3斤大豆粉，于是可找出問題的模型：第二十一頁，共四十六頁，編輯于2023年，星期一第二十二頁，共四十六頁，編輯于2023年，星期一由以上幾個(gè)例子，我們看到，所建立的數(shù)學(xué)模型其目標(biāo)函數(shù)和約束條件均是關(guān)于未知變量的線形函數(shù)。目的是要求目標(biāo)函數(shù)在約束下的極大或極小。我們稱這樣一類模型為線性規(guī)劃模型。建立數(shù)學(xué)規(guī)劃模型主要由以下三個(gè)步驟（隱含著三個(gè)要素）1．確定決策變量，亦即選取適當(dāng)?shù)牧繛閱栴}的待確定量，這是問題的基礎(chǔ)。2．建立適當(dāng)?shù)募s束條件。3．建立目標(biāo)函數(shù)。下面我們再舉一些例子說明如何建立線性規(guī)劃模型：

例四：（裝配成套）某產(chǎn)品的一個(gè)單件包括四個(gè)A個(gè)零和三個(gè)B零件。這兩種零件由兩種不同原料制成，而這兩種原料可利用的數(shù)額分別為100個(gè)單位和200個(gè)單位。由三個(gè)車間按不同的方法制造。下面表格給出每個(gè)生產(chǎn)班的原料耗用量和每種零件的產(chǎn)量。目標(biāo)是確定每個(gè)生產(chǎn)班數(shù)使產(chǎn)品得配套數(shù)最大？第二十三頁，共四十六頁，編輯于2023年，星期一17

5，，2解：設(shè),x1,x2,x3是第1.23車間的生產(chǎn)班數(shù)，則三個(gè)車間生產(chǎn)零件A的總數(shù)是x+6x+8x生產(chǎn)零件B的總數(shù)是x+9x+4x1233第二十四頁，共四十六頁，編輯于2023年，星期一而原料1和原料2對應(yīng)的約束條件分別是因?yàn)槟繕?biāo)是要使產(chǎn)品總件數(shù)達(dá)到最大，而每件產(chǎn)品要4個(gè)零件A和3個(gè)零件B。所以產(chǎn)品的最大數(shù)額不能超過第二十五頁，共四十六頁，編輯于2023年，星期一這是一個(gè)非線性的目標(biāo)函數(shù)，可以通過變換轉(zhuǎn)換成線性規(guī)劃模型：求：第二十六頁，共四十六頁，編輯于2023年，星期一例6

某廠準(zhǔn)備在電視臺做廣告，根據(jù)電視臺收費(fèi)標(biāo)準(zhǔn)，播出時(shí)間有三種選擇：時(shí)間（1）星期一至五18：30~22：30熱門時(shí)間，每半分鐘收費(fèi)300元；時(shí)間（2）星期六、日18：30~22：30熱門時(shí)間，每半分鐘收費(fèi)420元；時(shí)間（3）18：30~22：30以外的時(shí)間，即平時(shí)，每半分鐘收費(fèi)180元。工廠希望每天播出一次半分鐘時(shí)間的廣告。而電視臺希望放在時(shí)間（2）的播出次數(shù)不S.t.整理即得：求f=y的最大值第二十七頁，共四十六頁，編輯于2023年，星期一要超過在時(shí)間（1）的播出次數(shù)，工廠則希望不要在星期一至五熱門時(shí)間播出，以便平時(shí)也能看到廣告播出。因此規(guī)定在時(shí)間（1）的播出每月不超過15次。所以規(guī)定在時(shí)間（2）的播出每月不少于4次。工廠估計(jì)，認(rèn)為在時(shí)間（1）觀眾為平時(shí)的三倍。在時(shí)間（2）觀眾則為平時(shí)的五倍。試列出一個(gè)線性規(guī)劃模型，確定一個(gè)月內(nèi)播送廣告的方案。使（1）觀眾最多，（2）費(fèi)用最少。解：題中需要確定的是在不同的時(shí)間內(nèi)各播出幾次。以一個(gè)月30天來考慮，假定星期六、日共9天。設(shè)x為時(shí)間（1）播放次數(shù)。

y為時(shí)間（2）播放次數(shù)。

z為時(shí)間（3）播放次數(shù)。則x+y+z=30(每月中每天一次）第二十八頁，共四十六頁，編輯于2023年，星期一電視臺要求：y≤x廠方要求：x≤15及y≥4非負(fù)約束：x≥0，y≥0,z≥0.又一個(gè)月中:y≤9整理以上的約束條件得第二十九頁，共四十六頁，編輯于2023年，星期一一

標(biāo)準(zhǔn)形式:

我們由上面的實(shí)際例子已經(jīng)看到,線性規(guī)劃問題的模型是由一組線性等式或不等式表示的約束條件及一個(gè)線性目標(biāo)參數(shù)組成的.即下面的一般形式:

求一組變量§1.2線性規(guī)劃的標(biāo)準(zhǔn)形式并且使目標(biāo)函數(shù)：達(dá)到最大（或最?。㎡pt.第三十頁，共四十六頁，編輯于2023年，星期一為了便于求解線性規(guī)劃，有必要化線性規(guī)劃成一定形式，即為下面的標(biāo)準(zhǔn)形式：求一組變量第三十一頁，共四十六頁，編輯于2023年，星期一

因?yàn)橐话阈问降木€性規(guī)劃問題都能化成標(biāo)準(zhǔn)形式（后面介紹），因此只要會求解標(biāo)準(zhǔn)形式的線性規(guī)劃問題，就會求解一般形式的線性規(guī)劃問題了。下面介紹幾種形式的標(biāo)準(zhǔn)線性規(guī)劃[SLP]問題。1.縮寫形式：第三十二頁，共四十六頁，編輯于2023年，星期一矩陣形式：注：向量非負(fù)，代表向量的各分量非負(fù)第三十三頁，共四十六頁，編輯于2023年，星期一3.向量形式：第三十四頁，共四十六頁，編輯于2023年，星期一二化線性規(guī)劃問題為標(biāo)準(zhǔn)形式：

第二若約束條件中出現(xiàn)線性不等式則可能轉(zhuǎn)化為求目標(biāo)參數(shù)轉(zhuǎn)換方法：

第一若是求目標(biāo)函數(shù)第三十五頁，共四十六頁，編輯于2023年，星期一第四第三十六頁，共四十六頁，編輯于2023年，星期一下面根據(jù)這些方法來做幾個(gè)實(shí)例：例8

將下面的線性規(guī)劃問題標(biāo)準(zhǔn)化：第三十七頁，共四十六頁，編輯于2023年，星期一§1.3線性規(guī)劃的基本性質(zhì)一兩個(gè)變量線性規(guī)劃問題的圖解法：我們先對二維的簡單線性規(guī)劃問題利用圖解法進(jìn)行求解。從圖解法的幾何直觀可以啟發(fā)我們的思維，探尋線性規(guī)劃的一些基本性質(zhì)。例9：利用圖解法求解下面線性規(guī)劃問題：第三十八頁，共四十六頁，編輯于2023年，星期一解：在平面上取一個(gè)直角坐標(biāo)系，他的兩個(gè)坐標(biāo)是首先找出平面上滿足約束條件的點(diǎn)。第三十九頁，共四十六頁，編輯于2023年，星期一當(dāng)目標(biāo)函數(shù)取某一值h時(shí)。令h=0，得直線目標(biāo)函數(shù)的值為0

再令h=2,6,7.得另外三條直線，其上點(diǎn)分別對應(yīng)目標(biāo)值2，6，7，因此把叫做目標(biāo)函數(shù)的等值線。當(dāng)參數(shù)h變化時(shí)，就得到一族平行直線，他們形象的描繪了目標(biāo)函數(shù)的變化狀態(tài)。平面上滿足約束條件的點(diǎn)為上圖中的一個(gè)凸多邊形。表明原線性規(guī)劃問題的目標(biāo)函數(shù)只能在這個(gè)凸多邊形（含邊界）上取值，那么求解線性規(guī)劃問題就是如何從這個(gè)凸多邊形上求出使目標(biāo)函數(shù)達(dá)最大值的關(guān)系。為此，我們先看看目標(biāo)函數(shù)在凸多邊形上取值的變化性能。第四十頁，共四十六頁，編輯于2023年，星期一當(dāng)h由?。ù螅┳兇螅ㄐ。r(shí)，我們來觀察等值線在凸多邊形上的變化情形。取等值線的正（負(fù)）法向量，其方向指向目標(biāo)參數(shù)值增大（減?。┑姆较?。當(dāng)h由?。ù螅┳兇螅ㄐ。r(shí)，直線沿（負(fù)）法方向平行移動，目標(biāo)參數(shù)值不斷增大。這樣就可以看到，對于凸多邊形目標(biāo)參數(shù)在0~7之間取值，且：