教學(xué)第1章緒論線性規(guī)劃數(shù)學(xué)模型課件

課程基本介紹

夫運(yùn)籌帷幄之中，決勝千里之外?！妒酚洝じ咦姹炯o(jì)》

由來(lái)：西漢初年，天下已定，漢高祖劉邦在洛陽(yáng)南宮舉行盛大的宴會(huì)，喝了幾輪酒后，他向群臣提出一個(gè)問題：“我為什么會(huì)取得勝利？項(xiàng)羽為什么會(huì)失?。俊备咂?、王陵認(rèn)為高祖派有才能的人攻占城池與戰(zhàn)略要地，給立大功的人加官奉爵，所以能成大事業(yè)。而項(xiàng)羽恰恰相反，有人不用，立功不授獎(jiǎng)，賢人遭疑惑，所以他才失敗。漢高祖劉邦聽了，認(rèn)為他們說的有道理，但是最重要的取勝原因是能用人。他稱贊張良說：“夫運(yùn)籌帷幄之中，決勝千里之外，吾不如子房（古人有名，有字，子房為張良的字）?！币馑际钦f，張良坐在軍帳中運(yùn)用計(jì)謀，就能決定千里之外戰(zhàn)斗的勝利。這說明張良心計(jì)多，善用腦，善用兵。后來(lái)人們就用“運(yùn)籌帷幄”表示善于策劃用兵，指揮戰(zhàn)爭(zhēng)。課程基本介紹夫運(yùn)籌帷幄之中，決勝千里之外。無(wú)論哪種案例，這里都有籌劃，以策略取勝的意思課程基本介紹——起源與發(fā)展我國(guó)古代運(yùn)籌學(xué)應(yīng)用例子：田忌賽馬丁渭修皇宮運(yùn)籌學(xué)美：OperationsResearch英：OperationalResearch運(yùn)作研究/作業(yè)研究無(wú)論哪種案例，這里都有籌劃，以策略取勝的意思課程基本介紹——學(xué)科產(chǎn)生：第二次世界大戰(zhàn)英國(guó)波得塞（Bawdsey）雷達(dá)站的研究問題：隨著雷達(dá)性能的改善和配置數(shù)量的增多，出現(xiàn)了來(lái)自不同雷達(dá)站的信息以及雷達(dá)站和整個(gè)防空作戰(zhàn)系統(tǒng)的協(xié)調(diào)配合問題1938年7月，波得塞雷達(dá)站的負(fù)責(zé)人羅伊（A.P.Rowe）用OperationalResearch命名防空作戰(zhàn)系統(tǒng)運(yùn)行的研究，這是運(yùn)籌學(xué)OperationalResearch（O.R.）的由來(lái)1940年9月英國(guó)成立了由物理學(xué)家布萊克特(Blackett)領(lǐng)導(dǎo)的第一個(gè)運(yùn)籌學(xué)小組。l942年美國(guó)和加拿大也都相繼成立運(yùn)籌學(xué)小組據(jù)不完全統(tǒng)計(jì)，二戰(zhàn)期間，僅在英、美和加拿大，參加運(yùn)籌學(xué)工作的科學(xué)家超過700名。課程基本介紹——起源與發(fā)展學(xué)科產(chǎn)生：第二次世界大戰(zhàn)英國(guó)波得塞（Bawdsey）雷達(dá)站的課程基本介紹——起源與發(fā)展

二次世界大戰(zhàn)后，從事這些活動(dòng)的許多專家轉(zhuǎn)到了民用部門，使運(yùn)籌學(xué)很快推廣到了工業(yè)企業(yè)和政府工作的各個(gè)方面，從而促進(jìn)了運(yùn)籌學(xué)有關(guān)理論和方法的研究和實(shí)踐，使得運(yùn)籌學(xué)迅速發(fā)展并逐步成熟起來(lái)。運(yùn)籌學(xué)發(fā)展到現(xiàn)在，但其內(nèi)容已相當(dāng)豐富，所涉及領(lǐng)域也十分廣泛?，F(xiàn)在這門新興學(xué)科的應(yīng)用已深入到國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域，成為促進(jìn)國(guó)民經(jīng)濟(jì)多快好省，健康協(xié)調(diào)發(fā)展的有效方法。這門課的目的就是要系統(tǒng)地了解運(yùn)籌學(xué)的基本概念、基本原理、研究方法及其應(yīng)用，掌握運(yùn)籌學(xué)整體優(yōu)化的思想和定量分析的優(yōu)化技術(shù)，并能正確應(yīng)用各類模型分析和解決實(shí)際問題。課程基本介紹——起源與發(fā)展二次世界大戰(zhàn)后，從課程基本介紹——定義“運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)”，“運(yùn)籌學(xué)為掌管這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具”?！洞笥倏迫珪愤\(yùn)籌學(xué)“用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和國(guó)防等部門在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財(cái)力等資源，使實(shí)際系統(tǒng)有效運(yùn)行的技術(shù)科學(xué)，它可以用來(lái)預(yù)測(cè)發(fā)展趨勢(shì)，制定行動(dòng)規(guī)劃或優(yōu)選可行方案”——《中國(guó)大百科全書》課程基本介紹——定義“運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)課程基本介紹——定義運(yùn)籌學(xué)“主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量來(lái)表達(dá)有關(guān)運(yùn)用、籌劃與管理方面的問題，它根據(jù)問題的要求，通過數(shù)學(xué)的分析與運(yùn)算，作出綜合性的合理安排，以達(dá)到較經(jīng)濟(jì)較有效地使用人力物力”——《辭?！愤\(yùn)籌學(xué)“應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理”。——《中國(guó)企業(yè)管理百科全書》課程基本介紹——定義運(yùn)籌學(xué)“主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用課程基本介紹——定義運(yùn)籌學(xué)所研究的，就是在經(jīng)營(yíng)管理活動(dòng)中如何行動(dòng)，如何以盡可能小的代價(jià)，獲取盡可能好的結(jié)果，即所謂“最優(yōu)化”問題。中國(guó)學(xué)者根據(jù)“運(yùn)籌于帷幄之中，決勝于千里之外”意譯為“運(yùn)籌學(xué)”，其意為運(yùn)算籌劃，出謀獻(xiàn)策，以最佳策略取勝。這實(shí)際上極為恰當(dāng)?shù)馗爬诉@門學(xué)科的精髓。課程基本介紹——定義運(yùn)籌學(xué)所研究的，就是在經(jīng)營(yíng)管理活動(dòng)中如何運(yùn)籌學(xué)具有如下的性質(zhì)特點(diǎn)運(yùn)籌學(xué)是一門應(yīng)用科學(xué)，應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識(shí)和數(shù)學(xué)方法，解決實(shí)際中提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)”，這也是運(yùn)籌學(xué)的目地定量化分析：通過數(shù)學(xué)方法的應(yīng)用來(lái)對(duì)問題建立模型，并對(duì)模型的分析與求解最優(yōu)化思想多學(xué)科的交叉與結(jié)合，如交通工程、物流工程、經(jīng)濟(jì)學(xué)、物理、化學(xué)等方法課程基本介紹——性質(zhì)系統(tǒng)的整體思想運(yùn)籌學(xué)具有如下的性質(zhì)特點(diǎn)運(yùn)籌學(xué)是一門應(yīng)用科學(xué)，應(yīng)用現(xiàn)有的科學(xué)課程基本介紹——分支規(guī)劃理論線性規(guī)劃非線性規(guī)劃運(yùn)輸問題

整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃目標(biāo)規(guī)劃圖論與網(wǎng)絡(luò)理論排隊(duì)論存儲(chǔ)論決策論對(duì)策論課程基本介紹——分支規(guī)劃理論本課程具體內(nèi)容與性質(zhì)運(yùn)籌學(xué)教學(xué)大綱運(yùn)籌學(xué)進(jìn)度安排本課程具體內(nèi)容與性質(zhì)運(yùn)籌學(xué)教學(xué)大綱運(yùn)籌學(xué)進(jìn)度安排課程特點(diǎn)與相關(guān)要求課程特點(diǎn)與線性代數(shù)聯(lián)系緊密，做好相關(guān)數(shù)學(xué)知識(shí)的復(fù)習(xí)課程要求認(rèn)真聽講。有問題及時(shí)反映按時(shí)完成作業(yè)。每周第一次課之前交。要求獨(dú)立、準(zhǔn)時(shí)完成答疑時(shí)間每周二下午2:30-3:30，其它時(shí)間課程特點(diǎn)與相關(guān)要求課程特點(diǎn)與線性代數(shù)聯(lián)系緊密，課程要求認(rèn)真聽課程考試方式與成績(jī)構(gòu)成考試方式閉卷考試成績(jī)構(gòu)成平時(shí)成績(jī)占50%，期末考試占50%平時(shí)成績(jī)由考勤和平時(shí)表現(xiàn)、平時(shí)作業(yè)、測(cè)驗(yàn)和實(shí)驗(yàn)等環(huán)節(jié)共同構(gòu)成。課程考試方式與成績(jī)構(gòu)成考試方式閉卷考試成績(jī)構(gòu)成平時(shí)成績(jī)占50

第一章線性規(guī)劃和單純形法本章主要內(nèi)容：線性規(guī)劃問題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子第一章線性規(guī)劃和單純形法本章主要內(nèi)容：線性規(guī)劃問

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型1.線性規(guī)劃（Linearprogramming）問題的提出

生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤(rùn)最大.）第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型1.線性規(guī)劃（

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型

例1美佳公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A，B的臺(tái)時(shí)、調(diào)試工序時(shí)間及每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況，如表1-1所示。問該公司應(yīng)制造兩種家電各多少件，使獲取的利潤(rùn)為最大。問題的提出第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例1美佳公

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2

捷運(yùn)公司在下一年度的1~4月的4個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知各月份所需倉(cāng)庫(kù)面積列于表1-2。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見表1-3。租借倉(cāng)庫(kù)的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。表1-2單位：100m2表1-3單位：元/100m2第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2捷運(yùn)公司在下一年度課程基本介紹——解決問題步驟

(1)提出和形成問題。即要弄清問題的目標(biāo)，可能的約束，問題的可控變量以及有關(guān)參數(shù)；

(2)建立模型。即把問題中可控變量、參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來(lái)；

(3)求解。用各種手段(主要是數(shù)學(xué)方法，也可用其他方法)將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計(jì)算機(jī)，解的精度要求可由決策者提出；

(4)解的檢驗(yàn)。首先檢查求解步驟和程序有無(wú)錯(cuò)誤，然后檢查解是否反應(yīng)現(xiàn)實(shí)問題；

(5)解的控制。通過控制解的變化過程決定對(duì)解是否要作一定的改變；

(6)解的實(shí)施。是指將解用到實(shí)際中必須考慮到實(shí)施的問題，如向?qū)嶋H部門講清楚用法、在實(shí)施中可能產(chǎn)生的問題和修改。課程基本介紹——解決問題步驟 (1)提出和形成問題。即要

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型2.線性規(guī)劃問題模型的建立對(duì)例1試著建模：

例1美佳公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A，B的臺(tái)時(shí)、調(diào)試工序時(shí)間及每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況，如表1-1所示。問該公司應(yīng)制造兩種家電各多少件，使獲取的利潤(rùn)為最大。第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型2.線性規(guī)劃問

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型解：用變量x1和x2分別表示美佳公司制造家電Ⅰ和Ⅱ的數(shù)量。這時(shí)該公司可獲取的利潤(rùn)為(2x1+x2)元，問題中要求獲取的利潤(rùn)為最大，即max(2x1+x2)，稱為目標(biāo)函數(shù)，它是變量x1，x2的線性表達(dá)式函數(shù)。x1，x2的取值受到設(shè)備A、B和調(diào)試工序能力的限制，用于描述限制條件的數(shù)學(xué)表達(dá)式稱為約束條件。(1.1c)目標(biāo)函數(shù)約束條件(1.1a)(1.1b)(1.1d)max:maximize的縮寫，“最大化”s.t.

subjectto的縮寫，“受限制于……”第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型解：用變量x1和

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2

捷運(yùn)公司在下一年度的1~4月的4個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知各月份所需倉(cāng)庫(kù)面積列于表1-2。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見表1-3。租借倉(cāng)庫(kù)的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。表1-2單位：100m2表1-3單位：元/100m2第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2捷運(yùn)公司在下一年度

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2中：若用變量xij表示捷運(yùn)公司在第i(i=1,…,4)個(gè)月初簽訂的租借期為j(j=1,…,4)個(gè)月的倉(cāng)庫(kù)面積的合同。因5月份起該公司不需要租借倉(cāng)庫(kù)，故x24，x33，x34，x42，x43，x44均為零。該公司希望總的租借費(fèi)用為最小，故有如下數(shù)學(xué)模型：目標(biāo)函數(shù)約束條件s.t.第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2中：若用變量xij表

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型

分析以上的建模過程，我們可以看出要對(duì)規(guī)劃問題建模，基本遵循以下三個(gè)步驟：決策變量、目標(biāo)函數(shù)和約束條件通常稱為規(guī)劃問題的三要素。（3）確定約束條件。決策變量的取值受到各種資源的限制，這些限制通常用包含決策變量的等式或不等式表示，這就是約束條件的表示。（1）確定變量，即問題中的未知量。它是由決策者決定的影響決策目標(biāo)的未知量，未知量的取值代表一種方案，故我們把這些變量稱之為決策變量。

（2）確定目標(biāo)函數(shù)，即要用來(lái)實(shí)現(xiàn)的目標(biāo)，一般用決策變量的線性函數(shù)來(lái)表示，通常要求實(shí)現(xiàn)該函數(shù)的最大或最小。第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型分析以上的

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型

如何辨別一個(gè)模型是線性規(guī)劃問題？

當(dāng)一個(gè)規(guī)劃問題的模型具備上述特點(diǎn)時(shí)我們稱之為線性規(guī)劃其特征是：（1）問題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個(gè)決策變量的線性不等式或等式。將以上問題推廣,可得線性規(guī)劃含義：對(duì)于求取一組變量xj(j=1,2,…..,n)，使之既滿足線性約束條件，又使具有線性的目標(biāo)函數(shù)取得極值的一類最優(yōu)化問題稱為線性規(guī)劃問題。第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型如何辨第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型max（或min）

4.線性規(guī)劃數(shù)學(xué)模型的形式稱為價(jià)值系數(shù)或目標(biāo)函數(shù)系數(shù)

稱為資源常數(shù)或約束右端常數(shù)稱為技術(shù)系數(shù)或約束系數(shù)

稱為決策變量

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型max（或min）

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型簡(jiǎn)寫形式如下：max（或min）

Mathematicalmodel第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型簡(jiǎn)矩陣形式：max（或min）

稱為決策變量向量稱為價(jià)值系數(shù)向量或目標(biāo)函數(shù)系數(shù)向量稱為資源常數(shù)向量或約束右端常數(shù)向量稱為技術(shù)系數(shù)或約束系數(shù)矩陣

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型矩陣形式：max（或min） 稱為決策變量向量稱為價(jià)值向量形式：其中：

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型注意：向量形式時(shí)，每一個(gè)列向量Pj都是對(duì)應(yīng)變量的系數(shù)，如P1對(duì)應(yīng)的是x1的系數(shù)向量形式：其中：第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型注意：向第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型5.線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點(diǎn)：(1)目標(biāo)函數(shù)統(tǒng)一變成求最大值（有些書規(guī)定求最小值）(2)約束條件統(tǒng)一變?yōu)榈仁椒匠?，且右端常?shù)項(xiàng)bi都大于或等于零(3)決策變量xj為非負(fù)。即：第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型5.線性規(guī)劃問題的標(biāo)準(zhǔn)如何化標(biāo)準(zhǔn)形式？第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型設(shè)目標(biāo)函數(shù)為

minf=c1x1

+c2x2

+…+cnxn

則可以令z

＝-f

，該極小化問題與下面的極大化問題有相同的最優(yōu)解，即

maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即

minf

＝-maxz（1）極小化目標(biāo)函數(shù)的問題：如何化標(biāo)準(zhǔn)形式？第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型設(shè)（2）約束條件不是等式的問題：第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型

若約束條件為ai1x1+ai2x2+…+ainxn

≤bi

可以引進(jìn)一個(gè)新的變量s

，使它等于約束右邊與左邊之差，即s=bi–(ai1x1

+ai2x2

+…+ainxn

)

顯然，s

也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為ai1x1+ai2x2+…+ainxn+s=bi化標(biāo)準(zhǔn)型時(shí)為了使約束由小于等于不等式成為等式而引進(jìn)的變量s稱為“松弛變量”。

松弛變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)是多少呢？?jī)r(jià)值系數(shù)應(yīng)為0（2）約束條件不是等式的問題：第一節(jié)線性規(guī)劃問題及數(shù)（2）約束條件不是等式的問題：第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型當(dāng)約束條件為ai1x1+ai2x2+…+ainxn

≥bi時(shí)，類似地令s=(ai1x1+ai2x2+…+ainxn)-bi

顯然，s

也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為ai1x1+ai2x2+…+ainxn-s=bi

化標(biāo)準(zhǔn)型時(shí)為了使約束由大于等于不等式成為等式而引進(jìn)的變量s稱為“剩余變量”。

剩余變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)也是零（2）約束條件不是等式的問題：第一節(jié)線性規(guī)劃問題及數(shù)第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型剩余量：線性規(guī)劃中，一個(gè)大于等于約束條件中超過資源或能力最底限的部分稱之為剩余量。2xl+x2≥400，假如最優(yōu)解為（150,110）那么剩余量就為10。兩個(gè)概念松弛量：線性規(guī)劃中，小于等于約束條件中未被使用的資源或能力的值成為松弛量。xl+x2≤300，假如最優(yōu)解為（150,140）那么本約束的松弛量就為10。第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型剩余量：線性規(guī)劃中，一個(gè)例1：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

minf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z=-f=-3.6x1+5.2x2-1.8x3

例1：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

第一節(jié)線性規(guī)第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型其次考慮約束，有2個(gè)不等式約束，引進(jìn)松弛變量x4和剩余變量x5，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：maxz=-3.6x1+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9x1+x2+x3=38x1,x2,x3,x4,x5≥0第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型其次考慮約束，有2個(gè)不等第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型（3）右端項(xiàng)有負(fù)值的問題：在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。

當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如bi<0，則把該等式約束兩端同時(shí)乘以-1，得到：

-ai1x1-ai2x2-…-ainxn

=-bi第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型（3）右端項(xiàng)有負(fù)值的問題（4）

變量無(wú)符號(hào)限制的問題：在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量xj沒有非負(fù)約束時(shí)，可以令xj=xj’-xj”(xj’≥0，xj”≥0)

或xj=-xj’(xj’≥0)第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型（4）變量無(wú)符號(hào)限制的問題：第一節(jié)線性規(guī)劃問題及數(shù)第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2：將以下線性規(guī)劃問題第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換成極大化令z=-f=3x1–5x2–8x3+7x4

；其次考慮約束，有3個(gè)不等式約束，引進(jìn)松弛變量x5,x7和剩余變量x6；由于x2無(wú)非負(fù)限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；由于第3個(gè)約束右端項(xiàng)系數(shù)為-58，于是把該式兩端乘以-1。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型

maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型maxz=3x第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型總結(jié)：把一般的LP化成標(biāo)準(zhǔn)型的過程：1目標(biāo)標(biāo)準(zhǔn)化

minZ

等價(jià)于max(-Z)maxZ’=-∑cjxj2化約束為等式加松弛變量、減剩余變量3右端非負(fù)4變量非負(fù)化做變換或第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型總結(jié)：把一般的LP化成標(biāo)

1、P43：1.2（1）；P45：1.13；選作1.15、1.17；2、復(fù)習(xí)線性代數(shù)相關(guān)知識(shí)本次作業(yè)

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型1、P43：1.2（1）；P45：1.13；選作1課程基本介紹

夫運(yùn)籌帷幄之中，決勝千里之外。——《史記·高祖本紀(jì)》

由來(lái)：西漢初年，天下已定，漢高祖劉邦在洛陽(yáng)南宮舉行盛大的宴會(huì)，喝了幾輪酒后，他向群臣提出一個(gè)問題：“我為什么會(huì)取得勝利？項(xiàng)羽為什么會(huì)失??？”高起、王陵認(rèn)為高祖派有才能的人攻占城池與戰(zhàn)略要地，給立大功的人加官奉爵，所以能成大事業(yè)。而項(xiàng)羽恰恰相反，有人不用，立功不授獎(jiǎng)，賢人遭疑惑，所以他才失敗。漢高祖劉邦聽了，認(rèn)為他們說的有道理，但是最重要的取勝原因是能用人。他稱贊張良說：“夫運(yùn)籌帷幄之中，決勝千里之外，吾不如子房（古人有名，有字，子房為張良的字）?！币馑际钦f，張良坐在軍帳中運(yùn)用計(jì)謀，就能決定千里之外戰(zhàn)斗的勝利。這說明張良心計(jì)多，善用腦，善用兵。后來(lái)人們就用“運(yùn)籌帷幄”表示善于策劃用兵，指揮戰(zhàn)爭(zhēng)。課程基本介紹夫運(yùn)籌帷幄之中，決勝千里之外。無(wú)論哪種案例，這里都有籌劃，以策略取勝的意思課程基本介紹——起源與發(fā)展我國(guó)古代運(yùn)籌學(xué)應(yīng)用例子：田忌賽馬丁渭修皇宮運(yùn)籌學(xué)美：OperationsResearch英：OperationalResearch運(yùn)作研究/作業(yè)研究無(wú)論哪種案例，這里都有籌劃，以策略取勝的意思課程基本介紹——學(xué)科產(chǎn)生：第二次世界大戰(zhàn)英國(guó)波得塞（Bawdsey）雷達(dá)站的研究問題：隨著雷達(dá)性能的改善和配置數(shù)量的增多，出現(xiàn)了來(lái)自不同雷達(dá)站的信息以及雷達(dá)站和整個(gè)防空作戰(zhàn)系統(tǒng)的協(xié)調(diào)配合問題1938年7月，波得塞雷達(dá)站的負(fù)責(zé)人羅伊（A.P.Rowe）用OperationalResearch命名防空作戰(zhàn)系統(tǒng)運(yùn)行的研究，這是運(yùn)籌學(xué)OperationalResearch（O.R.）的由來(lái)1940年9月英國(guó)成立了由物理學(xué)家布萊克特(Blackett)領(lǐng)導(dǎo)的第一個(gè)運(yùn)籌學(xué)小組。l942年美國(guó)和加拿大也都相繼成立運(yùn)籌學(xué)小組據(jù)不完全統(tǒng)計(jì)，二戰(zhàn)期間，僅在英、美和加拿大，參加運(yùn)籌學(xué)工作的科學(xué)家超過700名。課程基本介紹——起源與發(fā)展學(xué)科產(chǎn)生：第二次世界大戰(zhàn)英國(guó)波得塞（Bawdsey）雷達(dá)站的課程基本介紹——起源與發(fā)展

二次世界大戰(zhàn)后，從事這些活動(dòng)的許多專家轉(zhuǎn)到了民用部門，使運(yùn)籌學(xué)很快推廣到了工業(yè)企業(yè)和政府工作的各個(gè)方面，從而促進(jìn)了運(yùn)籌學(xué)有關(guān)理論和方法的研究和實(shí)踐，使得運(yùn)籌學(xué)迅速發(fā)展并逐步成熟起來(lái)。運(yùn)籌學(xué)發(fā)展到現(xiàn)在，但其內(nèi)容已相當(dāng)豐富，所涉及領(lǐng)域也十分廣泛?，F(xiàn)在這門新興學(xué)科的應(yīng)用已深入到國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域，成為促進(jìn)國(guó)民經(jīng)濟(jì)多快好省，健康協(xié)調(diào)發(fā)展的有效方法。這門課的目的就是要系統(tǒng)地了解運(yùn)籌學(xué)的基本概念、基本原理、研究方法及其應(yīng)用，掌握運(yùn)籌學(xué)整體優(yōu)化的思想和定量分析的優(yōu)化技術(shù)，并能正確應(yīng)用各類模型分析和解決實(shí)際問題。課程基本介紹——起源與發(fā)展二次世界大戰(zhàn)后，從課程基本介紹——定義“運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)”，“運(yùn)籌學(xué)為掌管這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具”?！洞笥倏迫珪愤\(yùn)籌學(xué)“用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和國(guó)防等部門在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財(cái)力等資源，使實(shí)際系統(tǒng)有效運(yùn)行的技術(shù)科學(xué)，它可以用來(lái)預(yù)測(cè)發(fā)展趨勢(shì)，制定行動(dòng)規(guī)劃或優(yōu)選可行方案”——《中國(guó)大百科全書》課程基本介紹——定義“運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)課程基本介紹——定義運(yùn)籌學(xué)“主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量來(lái)表達(dá)有關(guān)運(yùn)用、籌劃與管理方面的問題，它根據(jù)問題的要求，通過數(shù)學(xué)的分析與運(yùn)算，作出綜合性的合理安排，以達(dá)到較經(jīng)濟(jì)較有效地使用人力物力”——《辭?！愤\(yùn)籌學(xué)“應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理”?！吨袊?guó)企業(yè)管理百科全書》課程基本介紹——定義運(yùn)籌學(xué)“主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用課程基本介紹——定義運(yùn)籌學(xué)所研究的，就是在經(jīng)營(yíng)管理活動(dòng)中如何行動(dòng)，如何以盡可能小的代價(jià)，獲取盡可能好的結(jié)果，即所謂“最優(yōu)化”問題。中國(guó)學(xué)者根據(jù)“運(yùn)籌于帷幄之中，決勝于千里之外”意譯為“運(yùn)籌學(xué)”，其意為運(yùn)算籌劃，出謀獻(xiàn)策，以最佳策略取勝。這實(shí)際上極為恰當(dāng)?shù)馗爬诉@門學(xué)科的精髓。課程基本介紹——定義運(yùn)籌學(xué)所研究的，就是在經(jīng)營(yíng)管理活動(dòng)中如何運(yùn)籌學(xué)具有如下的性質(zhì)特點(diǎn)運(yùn)籌學(xué)是一門應(yīng)用科學(xué)，應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識(shí)和數(shù)學(xué)方法，解決實(shí)際中提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)”，這也是運(yùn)籌學(xué)的目地定量化分析：通過數(shù)學(xué)方法的應(yīng)用來(lái)對(duì)問題建立模型，并對(duì)模型的分析與求解最優(yōu)化思想多學(xué)科的交叉與結(jié)合，如交通工程、物流工程、經(jīng)濟(jì)學(xué)、物理、化學(xué)等方法課程基本介紹——性質(zhì)系統(tǒng)的整體思想運(yùn)籌學(xué)具有如下的性質(zhì)特點(diǎn)運(yùn)籌學(xué)是一門應(yīng)用科學(xué)，應(yīng)用現(xiàn)有的科學(xué)課程基本介紹——分支規(guī)劃理論線性規(guī)劃非線性規(guī)劃運(yùn)輸問題

整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃目標(biāo)規(guī)劃圖論與網(wǎng)絡(luò)理論排隊(duì)論存儲(chǔ)論決策論對(duì)策論課程基本介紹——分支規(guī)劃理論本課程具體內(nèi)容與性質(zhì)運(yùn)籌學(xué)教學(xué)大綱運(yùn)籌學(xué)進(jìn)度安排本課程具體內(nèi)容與性質(zhì)運(yùn)籌學(xué)教學(xué)大綱運(yùn)籌學(xué)進(jìn)度安排課程特點(diǎn)與相關(guān)要求課程特點(diǎn)與線性代數(shù)聯(lián)系緊密，做好相關(guān)數(shù)學(xué)知識(shí)的復(fù)習(xí)課程要求認(rèn)真聽講。有問題及時(shí)反映按時(shí)完成作業(yè)。每周第一次課之前交。要求獨(dú)立、準(zhǔn)時(shí)完成答疑時(shí)間每周二下午2:30-3:30，其它時(shí)間課程特點(diǎn)與相關(guān)要求課程特點(diǎn)與線性代數(shù)聯(lián)系緊密，課程要求認(rèn)真聽課程考試方式與成績(jī)構(gòu)成考試方式閉卷考試成績(jī)構(gòu)成平時(shí)成績(jī)占50%，期末考試占50%平時(shí)成績(jī)由考勤和平時(shí)表現(xiàn)、平時(shí)作業(yè)、測(cè)驗(yàn)和實(shí)驗(yàn)等環(huán)節(jié)共同構(gòu)成。課程考試方式與成績(jī)構(gòu)成考試方式閉卷考試成績(jī)構(gòu)成平時(shí)成績(jī)占50

第一章線性規(guī)劃和單純形法本章主要內(nèi)容：線性規(guī)劃問題及數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法進(jìn)一步討論數(shù)據(jù)包絡(luò)分析其他應(yīng)用例子第一章線性規(guī)劃和單純形法本章主要內(nèi)容：線性規(guī)劃問

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型1.線性規(guī)劃（Linearprogramming）問題的提出

生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤(rùn)最大.）第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型1.線性規(guī)劃（

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型

例1美佳公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A，B的臺(tái)時(shí)、調(diào)試工序時(shí)間及每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況，如表1-1所示。問該公司應(yīng)制造兩種家電各多少件，使獲取的利潤(rùn)為最大。問題的提出第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例1美佳公

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2

捷運(yùn)公司在下一年度的1~4月的4個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知各月份所需倉(cāng)庫(kù)面積列于表1-2。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見表1-3。租借倉(cāng)庫(kù)的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。表1-2單位：100m2表1-3單位：元/100m2第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2捷運(yùn)公司在下一年度課程基本介紹——解決問題步驟

(1)提出和形成問題。即要弄清問題的目標(biāo)，可能的約束，問題的可控變量以及有關(guān)參數(shù)；

(2)建立模型。即把問題中可控變量、參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來(lái)；

(3)求解。用各種手段(主要是數(shù)學(xué)方法，也可用其他方法)將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計(jì)算機(jī)，解的精度要求可由決策者提出；

(4)解的檢驗(yàn)。首先檢查求解步驟和程序有無(wú)錯(cuò)誤，然后檢查解是否反應(yīng)現(xiàn)實(shí)問題；

(5)解的控制。通過控制解的變化過程決定對(duì)解是否要作一定的改變；

(6)解的實(shí)施。是指將解用到實(shí)際中必須考慮到實(shí)施的問題，如向?qū)嶋H部門講清楚用法、在實(shí)施中可能產(chǎn)生的問題和修改。課程基本介紹——解決問題步驟 (1)提出和形成問題。即要

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型2.線性規(guī)劃問題模型的建立對(duì)例1試著建模：

例1美佳公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A，B的臺(tái)時(shí)、調(diào)試工序時(shí)間及每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況，如表1-1所示。問該公司應(yīng)制造兩種家電各多少件，使獲取的利潤(rùn)為最大。第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型2.線性規(guī)劃問

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型解：用變量x1和x2分別表示美佳公司制造家電Ⅰ和Ⅱ的數(shù)量。這時(shí)該公司可獲取的利潤(rùn)為(2x1+x2)元，問題中要求獲取的利潤(rùn)為最大，即max(2x1+x2)，稱為目標(biāo)函數(shù)，它是變量x1，x2的線性表達(dá)式函數(shù)。x1，x2的取值受到設(shè)備A、B和調(diào)試工序能力的限制，用于描述限制條件的數(shù)學(xué)表達(dá)式稱為約束條件。(1.1c)目標(biāo)函數(shù)約束條件(1.1a)(1.1b)(1.1d)max:maximize的縮寫，“最大化”s.t.

subjectto的縮寫，“受限制于……”第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型解：用變量x1和

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2

捷運(yùn)公司在下一年度的1~4月的4個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知各月份所需倉(cāng)庫(kù)面積列于表1-2。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見表1-3。租借倉(cāng)庫(kù)的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。表1-2單位：100m2表1-3單位：元/100m2第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2捷運(yùn)公司在下一年度

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2中：若用變量xij表示捷運(yùn)公司在第i(i=1,…,4)個(gè)月初簽訂的租借期為j(j=1,…,4)個(gè)月的倉(cāng)庫(kù)面積的合同。因5月份起該公司不需要租借倉(cāng)庫(kù)，故x24，x33，x34，x42，x43，x44均為零。該公司希望總的租借費(fèi)用為最小，故有如下數(shù)學(xué)模型：目標(biāo)函數(shù)約束條件s.t.第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型例2中：若用變量xij表

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型

分析以上的建模過程，我們可以看出要對(duì)規(guī)劃問題建模，基本遵循以下三個(gè)步驟：決策變量、目標(biāo)函數(shù)和約束條件通常稱為規(guī)劃問題的三要素。（3）確定約束條件。決策變量的取值受到各種資源的限制，這些限制通常用包含決策變量的等式或不等式表示，這就是約束條件的表示。（1）確定變量，即問題中的未知量。它是由決策者決定的影響決策目標(biāo)的未知量，未知量的取值代表一種方案，故我們把這些變量稱之為決策變量。

（2）確定目標(biāo)函數(shù)，即要用來(lái)實(shí)現(xiàn)的目標(biāo)，一般用決策變量的線性函數(shù)來(lái)表示，通常要求實(shí)現(xiàn)該函數(shù)的最大或最小。第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型分析以上的

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型

如何辨別一個(gè)模型是線性規(guī)劃問題？

當(dāng)一個(gè)規(guī)劃問題的模型具備上述特點(diǎn)時(shí)我們稱之為線性規(guī)劃其特征是：（1）問題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個(gè)決策變量的線性不等式或等式。將以上問題推廣,可得線性規(guī)劃含義：對(duì)于求取一組變量xj(j=1,2,…..,n)，使之既滿足線性約束條件，又使具有線性的目標(biāo)函數(shù)取得極值的一類最優(yōu)化問題稱為線性規(guī)劃問題。第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型如何辨第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型max（或min）

4.線性規(guī)劃數(shù)學(xué)模型的形式稱為價(jià)值系數(shù)或目標(biāo)函數(shù)系數(shù)

稱為資源常數(shù)或約束右端常數(shù)稱為技術(shù)系數(shù)或約束系數(shù)

稱為決策變量

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型max（或min）

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型簡(jiǎn)寫形式如下：max（或min）

Mathematicalmodel第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型簡(jiǎn)矩陣形式：max（或min）

稱為決策變量向量稱為價(jià)值系數(shù)向量或目標(biāo)函數(shù)系數(shù)向量稱為資源常數(shù)向量或約束右端常數(shù)向量稱為技術(shù)系數(shù)或約束系數(shù)矩陣

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型矩陣形式：max（或min） 稱為決策變量向量稱為價(jià)值向量形式：其中：

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型注意：向量形式時(shí)，每一個(gè)列向量Pj都是對(duì)應(yīng)變量的系數(shù)，如P1對(duì)應(yīng)的是x1的系數(shù)向量形式：其中：第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型注意：向第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型5.線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點(diǎn)：(1)目標(biāo)函數(shù)統(tǒng)一變成求最大值（有些書規(guī)定求最小值）(2)約束條件統(tǒng)一變?yōu)榈仁椒匠?，且右端常?shù)項(xiàng)bi都大于或等于零(3)決策變量xj為非負(fù)。即：第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型5.線性規(guī)劃問題的標(biāo)準(zhǔn)如何化標(biāo)準(zhǔn)形式？第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型設(shè)目標(biāo)函數(shù)為

minf=c1x1

+c2x2

+…+cnxn

則可以令z

＝-f

，該極小化問題與下面的極大化問題有相同的最優(yōu)解，即

maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即

minf

＝-maxz（1）極小化目標(biāo)函數(shù)的問題：如何化標(biāo)準(zhǔn)形式？第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型設(shè)（2）約束條件不是等式的問題：第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型

若約束條件為ai1x1+ai2x2+…+ainxn

≤bi

可以引進(jìn)一個(gè)新的變量s

，使它等于約束右邊與左邊之差，即s=bi–(ai1x1

+ai2x2

+…+ainxn

)

顯然，s

也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為ai1x1+ai2x2+…+ainxn+s=bi化標(biāo)準(zhǔn)型時(shí)為了使約束由小于等于不等式成為等式而引進(jìn)的變量s稱為“松弛變量”。

松弛變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)是多少呢？?jī)r(jià)值系數(shù)應(yīng)為0（2）約束條件不是等式的問題：第一節(jié)線性規(guī)劃問題及數(shù)（2）約束條件不是等式的問題：第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型當(dāng)約束條件為ai1x1+ai2x2+…+ainxn

≥bi時(shí)，類似地令s=(ai1x1+ai2x2+…+ainxn)-bi

顯然，s

也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為ai1x1+ai2x2+…+ainxn-s=bi

化標(biāo)準(zhǔn)型時(shí)為了使約束由大于等于不等式成為等式而引進(jìn)的變量s稱為“剩余變量”。

剩余變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)也是零（2）約束條件不是等式的問題：第一節(jié)線性規(guī)劃問題及數(shù)第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型剩余量：線性規(guī)劃中，一個(gè)大于等于約束條件中超過資源或能力最底限的部分稱之為剩余量。2xl+x2≥400，假如最優(yōu)解為（150,110）那么剩余量就為10。兩個(gè)概念松弛量：線性規(guī)劃中，小于等于約束條件中未被使用的資源或能力的值成為松弛量。xl+x2≤300，假如最優(yōu)解為（150,140）那么本約束的松弛量就為10。第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型剩余量：線性規(guī)劃中，一個(gè)例1：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

minf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z=-f=-3.6x1+5.2x2-1.8