新運(yùn)籌學(xué)課件

運(yùn)籌學(xué)

(OperationsResearch)任課教師：楊芳玲聯(lián)系方式：yangfangll@126.com經(jīng)濟(jì)管理類院校核心課程運(yùn)籌學(xué)

運(yùn)籌學(xué)（OperationsResearch）是用數(shù)學(xué)方法研究各種系統(tǒng)的最優(yōu)化問(wèn)題，運(yùn)籌學(xué)強(qiáng)調(diào)發(fā)揮現(xiàn)有系統(tǒng)的效能，應(yīng)用數(shù)學(xué)模型求得合理利用各種資源的最佳方案，為決策者提供科學(xué)決策的依據(jù)。本課程的教材及參考書(shū)選用教材《運(yùn)籌學(xué)教程》胡運(yùn)權(quán)主編（第2版）清華出版社參考教材《運(yùn)籌學(xué)》牛英武主編西安交通大學(xué)出版社《運(yùn)籌學(xué)》(修訂版)錢頌迪主編清華出版社先修課程

高等數(shù)學(xué)線性代數(shù)概率論緒論（1）運(yùn)籌學(xué)的產(chǎn)生發(fā)展及發(fā)展趨勢(shì)（2）運(yùn)籌學(xué)的性質(zhì)特點(diǎn)及解題思路（3）運(yùn)籌學(xué)的分支簡(jiǎn)介（4）運(yùn)籌學(xué)在管理中的應(yīng)用本章主要內(nèi)容：運(yùn)籌學(xué)產(chǎn)生與發(fā)展一、運(yùn)籌學(xué)（OperationsResearch）的產(chǎn)生、發(fā)展及發(fā)展趨勢(shì)

運(yùn)籌學(xué)的發(fā)展：三個(gè)來(lái)源（軍事、經(jīng)濟(jì)及管理）

1.軍事：運(yùn)籌學(xué)的主要發(fā)源地

古代軍事運(yùn)籌學(xué)思想

中國(guó)古代的“孫子兵法”；（1981年美國(guó)軍事運(yùn)籌學(xué)會(huì)出版了一本書(shū)，書(shū)中第一句話就是說(shuō)孫武子是世界上第一個(gè)軍事運(yùn)籌學(xué)的實(shí)踐家），中國(guó)古代運(yùn)籌學(xué)思想的例子還有：田忌賽馬、圍魏救趙、行軍運(yùn)糧，等等。（幾個(gè)典故）

國(guó)外歷史上的阿基米德、伽利略研究過(guò)作戰(zhàn)問(wèn)題；第一次世界大戰(zhàn)時(shí)，英國(guó)的蘭徹斯特（Lanchester）提出了戰(zhàn)斗方程，指出了數(shù)量?jī)?yōu)勢(shì)、火力和勝負(fù)的動(dòng)態(tài)關(guān)系；美國(guó)的愛(ài)迪生為美國(guó)海軍咨詢委員會(huì)研究了潛艇攻擊和潛艇回避攻擊的問(wèn)題。運(yùn)籌學(xué)產(chǎn)生與發(fā)展運(yùn)籌學(xué)的歷史“運(yùn)作研究(OperationalResearch)小組”:解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍德空襲對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)損失最少；在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷力等。運(yùn)籌學(xué)產(chǎn)生與發(fā)展運(yùn)籌學(xué)的正式產(chǎn)生：第二次世界大戰(zhàn)

據(jù)不完全統(tǒng)計(jì)，二戰(zhàn)期間，僅在英、美和加拿大，參加運(yùn)籌學(xué)工作的科學(xué)家超過(guò)700名。2.管理(1)泰勒的時(shí)間動(dòng)作研究、甘特的用于生產(chǎn)計(jì)劃與控制的“甘特圖”、吉爾布雷思夫婦的動(dòng)作研究等(2)愛(ài)爾朗（Erlong）的排隊(duì)論公式1909－1920年間，丹麥哥本哈根電話公司工程師愛(ài)爾朗陸續(xù)發(fā)表了關(guān)于電話通路數(shù)量等方面的分析與計(jì)算公式。尤其是1909年的論文“概率與電話通話理論”，開(kāi)創(chuàng)了運(yùn)籌學(xué)的重要分支－－排隊(duì)論。運(yùn)籌學(xué)產(chǎn)生與發(fā)展3.經(jīng)濟(jì)（數(shù)理經(jīng)濟(jì)學(xué)）(1)VonNeumann與對(duì)策論

1932年，VonNeumann提出一個(gè)廣義經(jīng)濟(jì)平衡模型；1939年，提出了一個(gè)屬于宏觀經(jīng)濟(jì)優(yōu)化的控制論模型；1944年，與Morgenstern共著的《對(duì)策論與經(jīng)濟(jì)行為》開(kāi)創(chuàng)了對(duì)策論分支。(2)康托洛維奇與“生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法”

30年代，蘇聯(lián)數(shù)理經(jīng)濟(jì)學(xué)家康托洛維奇從事生產(chǎn)組織與管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪稱運(yùn)籌學(xué)的先驅(qū)著作－－《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》，其思想和模型被歸入線性規(guī)劃范疇。運(yùn)籌學(xué)產(chǎn)生與發(fā)展

我國(guó)運(yùn)籌學(xué)的研究始于20世紀(jì)50年代中期，當(dāng)時(shí)由錢學(xué)森教授將運(yùn)籌學(xué)從西方國(guó)家引入我國(guó)，以華羅庚教授為代表的一大批科學(xué)家在有關(guān)企事業(yè)單位積極推廣和普及運(yùn)籌學(xué)方法，在建筑、紡織、交通運(yùn)輸、水利建設(shè)和郵電等行業(yè)都有不少應(yīng)用。關(guān)于郵遞員投遞的最佳路線問(wèn)題就是由我國(guó)年輕的數(shù)學(xué)家管梅谷于1962年首先提出的，在國(guó)際上統(tǒng)稱為中國(guó)郵遞員問(wèn)題。我國(guó)運(yùn)籌學(xué)的理論和應(yīng)用研究在較短時(shí)間內(nèi)趕上了世界水平。運(yùn)籌學(xué)產(chǎn)生與發(fā)展

如今對(duì)運(yùn)籌學(xué)的研究大致在三個(gè)領(lǐng)域發(fā)展：運(yùn)籌學(xué)應(yīng)用、運(yùn)籌科學(xué)和運(yùn)籌數(shù)學(xué)。一般的共識(shí)是，運(yùn)籌學(xué)的研究不能忘記其原有的應(yīng)用性強(qiáng)的特色，必須強(qiáng)調(diào)多學(xué)科的交叉聯(lián)系和解決實(shí)際問(wèn)題的研究。我們面臨的很多系統(tǒng)通常涉及到大量的經(jīng)濟(jì)、技術(shù)、社會(huì)、政治和心理等綜合因素，這些綜合因素受到人的影響和干預(yù)，存在非結(jié)構(gòu)性的復(fù)雜問(wèn)題，僅用數(shù)學(xué)模型是很難加以描述和解決的?？傊S著社會(huì)的不斷發(fā)展和進(jìn)步，實(shí)踐將對(duì)運(yùn)籌學(xué)提出更新更多的研究課題，運(yùn)籌學(xué)正處于不斷發(fā)展，不斷進(jìn)步的時(shí)期。二、運(yùn)籌學(xué)的研究對(duì)象、研究特征及解題思路1.運(yùn)籌學(xué)的定義《中國(guó)企業(yè)管理百科全書(shū)》：運(yùn)籌學(xué)是運(yùn)用分析，試驗(yàn)，量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物(時(shí)間)等有限資源，進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案（滿意方案），以實(shí)現(xiàn)最有效地管理?！掇o海》對(duì)運(yùn)籌學(xué)解釋為：“二十世紀(jì)四十年代開(kāi)始形成的一門科學(xué)，主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量來(lái)表達(dá)的有關(guān)運(yùn)用，籌劃與管理方面的問(wèn)題，它根據(jù)問(wèn)題的要求，通過(guò)數(shù)學(xué)的分析與運(yùn)算，作出綜合性的合理的安排，以達(dá)到較經(jīng)濟(jì)、較有效地使用人力、物力。近年來(lái)，它在理論與應(yīng)用方面都有較大發(fā)展。其主要分支有規(guī)劃論、對(duì)策論、排隊(duì)論及質(zhì)量控制等?！边\(yùn)籌學(xué)的研究對(duì)象、研究特征及解題思路11運(yùn)籌學(xué)的研究對(duì)象、研究特征及解題思路

2.運(yùn)籌學(xué)的研究對(duì)象1）機(jī)器、工具、設(shè)備、人員等資源如何最佳利用問(wèn)題

研究方法有：線性規(guī)劃、整數(shù)規(guī)劃、網(wǎng)絡(luò)圖、動(dòng)態(tài)規(guī)劃、

目標(biāo)規(guī)劃等2）競(jìng)爭(zhēng)現(xiàn)象：如戰(zhàn)爭(zhēng)、投資、商品競(jìng)爭(zhēng)方法是對(duì)策論3）擁擠現(xiàn)象：如公共汽車排隊(duì)、打電話、買東西、飛機(jī)著陸、船舶進(jìn)港等方法是排隊(duì)論運(yùn)籌學(xué)的研究對(duì)象所以可對(duì)運(yùn)籌學(xué)的研究對(duì)象做如下概括：１.運(yùn)籌學(xué)的研究對(duì)象是各種系統(tǒng)。２.運(yùn)籌學(xué)的研究目的是實(shí)現(xiàn)系統(tǒng)的最優(yōu)化，求得合理利用各種資源的最優(yōu)方案。３.運(yùn)籌學(xué)的研究方法是運(yùn)用數(shù)學(xué)語(yǔ)言來(lái)描述實(shí)際系統(tǒng)，通過(guò)建立數(shù)學(xué)模型和優(yōu)化技術(shù)求得系統(tǒng)運(yùn)營(yíng)的最優(yōu)解。

４.運(yùn)籌學(xué)的研究動(dòng)機(jī)是為決策者提供科學(xué)決策的依據(jù)。運(yùn)籌學(xué)在工業(yè)、農(nóng)業(yè)、商業(yè)、物流、經(jīng)濟(jì)計(jì)劃、人力資源、軍事等行業(yè)都有著非常廣泛的應(yīng)用。有人曾對(duì)世界上500家著名的企業(yè)集團(tuán)或跨國(guó)公司進(jìn)行過(guò)調(diào)查，發(fā)現(xiàn)其中95%曾使用過(guò)線性規(guī)劃，75%使用過(guò)運(yùn)輸模型，90%使用過(guò)網(wǎng)絡(luò)計(jì)劃技術(shù)，90%使用過(guò)存儲(chǔ)模型，43%使用過(guò)動(dòng)態(tài)規(guī)劃。由此可見(jiàn)運(yùn)籌學(xué)是一門應(yīng)用性很強(qiáng)的學(xué)科。特別是隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，計(jì)算機(jī)成為運(yùn)籌學(xué)最強(qiáng)有力的運(yùn)算工具，運(yùn)籌學(xué)越來(lái)越顯示出其廣泛的使用價(jià)值。運(yùn)籌學(xué)的研究對(duì)象、研究特征及解題思路3.運(yùn)籌學(xué)的性質(zhì)特點(diǎn)1）運(yùn)籌學(xué)的性質(zhì)

應(yīng)用科學(xué)－“應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識(shí)和數(shù)學(xué)方法，解決實(shí)際中提出的專門問(wèn)題，為決策者選擇最優(yōu)決策提供定量依據(jù)”。2)運(yùn)籌學(xué)的特點(diǎn)定量化分析多學(xué)科交叉，如綜合利用了心理學(xué)、經(jīng)濟(jì)學(xué)、物理、化學(xué)等方法實(shí)現(xiàn)最優(yōu)決策(1)科學(xué)性：運(yùn)籌學(xué)是以研究事物內(nèi)在規(guī)律，并從定量分析的角度探求更好地解決問(wèn)題的一門科學(xué)。運(yùn)籌學(xué)的研究對(duì)象、研究特征及解題思路15(2)應(yīng)用性：運(yùn)籌學(xué)既對(duì)各種經(jīng)營(yíng)進(jìn)行創(chuàng)造性的科學(xué)研究，又涉及到組織的實(shí)際管理問(wèn)題，它具有很強(qiáng)的實(shí)踐性，最終應(yīng)能向決策者提供建設(shè)性意見(jiàn)，并應(yīng)收到實(shí)效；運(yùn)籌學(xué)的研究對(duì)象、研究特征及解題思路16(3)多學(xué)科的交叉性、綜合性：運(yùn)籌學(xué)研究中吸收了來(lái)自不同領(lǐng)域的經(jīng)驗(yàn)，并被廣泛應(yīng)用于工商企業(yè)、軍事部門、民政事業(yè)等研究組織內(nèi)的統(tǒng)籌協(xié)調(diào)問(wèn)題，故其應(yīng)用不受行業(yè)、部門之限制；運(yùn)籌學(xué)的研究對(duì)象、研究特征及解題思路17(4)系統(tǒng)性和最優(yōu)性:它以整體最優(yōu)為目標(biāo),從系統(tǒng)的觀點(diǎn)出發(fā),力圖以整個(gè)系統(tǒng)最佳的方式來(lái)解決該系統(tǒng)各部門之間的利害沖突。對(duì)所研究的問(wèn)題求出最優(yōu)解,尋求最佳的行動(dòng)方案,所以它也可看成是一門優(yōu)化技術(shù),提供的是解決各類問(wèn)題的優(yōu)化方法。運(yùn)籌學(xué)的研究對(duì)象、研究特征及解題思路18運(yùn)籌學(xué)的研究對(duì)象、研究特征及解題思路4.運(yùn)籌學(xué)的工作步驟提出和形成問(wèn)題，建立模型，求解，解的檢驗(yàn)，解的控制，解的實(shí)施

運(yùn)籌學(xué)的研究的主要步驟：真實(shí)系統(tǒng)系統(tǒng)分析問(wèn)題描述模型建立與修改模型求解與檢驗(yàn)結(jié)果分析與實(shí)施數(shù)據(jù)準(zhǔn)備運(yùn)籌學(xué)的主要分支數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃等）圖論存儲(chǔ)論排隊(duì)論對(duì)策論排序與統(tǒng)籌方法決策分析運(yùn)籌學(xué)在管理中的應(yīng)用運(yùn)籌學(xué)在管理中的應(yīng)用涉及幾個(gè)方面：生產(chǎn)計(jì)劃運(yùn)輸問(wèn)題人事管理庫(kù)存管理市場(chǎng)營(yíng)銷財(cái)務(wù)和會(huì)計(jì)另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項(xiàng)目的選擇與評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)等?！?.3運(yùn)籌學(xué)在管理中的應(yīng)用

生產(chǎn)計(jì)劃:

生產(chǎn)作業(yè)的計(jì)劃、日程表的編排、合理下料、配料問(wèn)題、物料管理等;

庫(kù)存管理:

多種物資庫(kù)存量的管理,庫(kù)存方式、庫(kù)存量等;

運(yùn)輸問(wèn)題:

確定最小成本的運(yùn)輸線路、物資的調(diào)撥、運(yùn)輸工具的調(diào)度以及建廠地址的選擇等;人事管理:

對(duì)人員的需求和使用的預(yù)測(cè)，確定人員編制、人員合理分配，建立人才評(píng)價(jià)體系等;23§1.3運(yùn)籌學(xué)在工商管理中的應(yīng)用市場(chǎng)營(yíng)銷:

廣告預(yù)算、媒介選擇、定價(jià)、產(chǎn)品開(kāi)發(fā)與銷售計(jì)劃制定等;

財(cái)務(wù)和會(huì)計(jì):

預(yù)測(cè)、貸款、成本分析、定價(jià)、證券管理、現(xiàn)金管理等;***設(shè)備維修、更新，項(xiàng)目選擇、評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)與管理等;24本課程授課方式與考核學(xué)科總成績(jī)平時(shí)成績(jī)（20％）課堂考勤（50％）平時(shí)作業(yè)（50％）期末成績(jī)（80％）講授為主，結(jié)合習(xí)題作業(yè)“田忌賽馬”是家喻戶曉的歷史故事。戰(zhàn)國(guó)時(shí)齊威王與齊相田忌賽馬，雙方各出三匹馬比賽，每勝一場(chǎng)贏得一千金。由于王府的馬比相府的馬好，所以田忌每次比賽都要輸?shù)羧Ы?。后?lái)田忌的謀士孫臏獻(xiàn)了一計(jì)：在每次開(kāi)賽前要求對(duì)方先報(bào)馬名，由此區(qū)分對(duì)方參賽的是上馬、中馬還是下馬；然后以自己的上馬對(duì)對(duì)方的中馬、自己的中馬對(duì)對(duì)方和下馬、自己的下馬對(duì)對(duì)方的上馬。這樣，兩勝一負(fù)反而贏得一千金。幾個(gè)典故

我國(guó)古代運(yùn)籌思想運(yùn)用的典故1．“田忌賽馬”

26第一章緒論

我國(guó)古代運(yùn)籌思想運(yùn)用的典故2．晉國(guó)公重建皇城

晉國(guó)公重建皇城的施工方案，體現(xiàn)了運(yùn)籌學(xué)的樸素思想。要使重建工程的各個(gè)工序,在時(shí)間、空間上彼此協(xié)調(diào),環(huán)環(huán)相扣,就需要運(yùn)用行列式的相關(guān)知識(shí),進(jìn)行精確計(jì)算.273.沈括運(yùn)糧

沈括(1031-1095年),北宋時(shí)期大科學(xué)家、軍事家.在率兵抗擊西夏侵?jǐn)_的征途中,曾經(jīng)從行軍中各類人員可以背負(fù)糧食的基本數(shù)據(jù)出發(fā),分析計(jì)算了后勤人員與作戰(zhàn)士兵在不同行軍天數(shù)中的不同比例關(guān)系,同時(shí)也分析計(jì)算了用各種牲畜運(yùn)糧與人力運(yùn)糧之間的利弊,最后做出了從敵國(guó)就地征糧,保障前方供應(yīng)的重要決策.從而減少了后勤人員的比例,增強(qiáng)了前方作戰(zhàn)的兵力.

28“管理運(yùn)籌學(xué)”軟件介紹“管理運(yùn)籌學(xué)”2.0版包括：線性規(guī)劃、運(yùn)輸問(wèn)題、整數(shù)規(guī)劃（0-1整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對(duì)策論、最短路徑、最小生成樹(shù)、最大流量、最小費(fèi)用最大流、關(guān)鍵路徑、存儲(chǔ)論、排隊(duì)論、決策分析、預(yù)測(cè)問(wèn)題和層次分析法，共15個(gè)子模塊。Chapter1線性規(guī)劃

(LinearProgramming)

LP的數(shù)學(xué)模型圖解法單純形法單純形法的進(jìn)一步討論－人工變量法

LP模型的應(yīng)用本章主要內(nèi)容：線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.規(guī)劃問(wèn)題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問(wèn)題。線性規(guī)劃通常解決下列兩類問(wèn)題：（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)最大.）線性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.1如圖所示，如何截取x使鐵皮所圍成的容積最大？xa線性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1、(生產(chǎn)計(jì)劃問(wèn)題）

某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤(rùn)最大？設(shè)備產(chǎn)品

A

B

C

D利潤(rùn)（元）甲

2

1

4

0

2乙

2

2

0

4

3有效臺(tái)時(shí)

12

8

16

12線性規(guī)劃問(wèn)題的數(shù)學(xué)模型解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：maxZ=2x1+3x2

x1≥0,x2≥0s.t.

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12線性規(guī)劃問(wèn)題的數(shù)學(xué)模型例2（下料問(wèn)題）長(zhǎng)度為1米的圓鋼多根，欲截成40、30、20cm長(zhǎng)的用料分別為20、45、50根，問(wèn)如何下料才能使用料最??？

分析：在長(zhǎng)度確定的原料上截取三種不同規(guī)格的圓鋼，可以歸納出8種不同的下料方案：圓鋼（米）ⅠⅡⅢⅣⅤⅥⅦⅧ402111000030021032102010130235料頭（米）00100100100線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

上述問(wèn)題歸納為如何混合使用這8種不同的下料方案，來(lái)制造20,45,50根不同的鋼料，且要使用料最??？用料最省反映在兩個(gè)方面：1.所用圓鋼數(shù)最少2.使剩余的料頭總長(zhǎng)為最短

設(shè)xj表示用第j種下料方案下料的原料根j=1,2,…,8,目標(biāo)：料頭總長(zhǎng)度=圓鋼數(shù)=線性規(guī)劃問(wèn)題的數(shù)學(xué)模型例3（運(yùn)輸問(wèn)題）兩個(gè)倉(cāng)庫(kù)A1、A2，每月可分別調(diào)出鋼材28、29噸，工地B1、B2、B3每月需鋼材分別12、15、30噸均由倉(cāng)庫(kù)A1、A2供應(yīng)，各倉(cāng)庫(kù)運(yùn)往各工地每噸鋼材的運(yùn)費(fèi)（元/噸）如下表，問(wèn)如何安排運(yùn)輸計(jì)劃可是總費(fèi)用最小？B1B2B3供應(yīng)量A118252028A221222429需求量121530例4、（合理配料問(wèn)題）要求所分配飼料每單位的營(yíng)養(yǎng)標(biāo)準(zhǔn)為：含蛋白質(zhì)不少于21%，纖維不少于5%，脂肪不少于3.4%，鐵不少于1%但不大于1.05%，鈣不少于0.45%但不大于0.6%。要求得出成本最小的配比方案線性規(guī)劃問(wèn)題的數(shù)學(xué)模型線性規(guī)劃問(wèn)題的數(shù)學(xué)模型例5、（廣告方式的選擇）某公司推銷一種新產(chǎn)品，有關(guān)數(shù)據(jù)如下表，銷售部第一個(gè)月的廣告預(yù)算費(fèi)為2萬(wàn)元，要求至少有8次電視廣告，15次報(bào)紙廣告，電視廣告費(fèi)不得超過(guò)1.2萬(wàn)元，電臺(tái)廣播至少隔日一次，問(wèn)公司銷售部應(yīng)采用怎樣的廣告宣傳計(jì)劃，才能取得最好的宣傳效果？廣告方式廣告費(fèi)用（元/次）可用最高次數(shù)（每月）期望宣傳效果電視（白天）5001650電視（晚上）10001080每日晨報(bào)1002430星期日?qǐng)?bào)廣播電臺(tái)300804254015線性規(guī)劃問(wèn)題的數(shù)學(xué)模型2.線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問(wèn)題的約束條件是一組多個(gè)決策變量的線性不等式或等式。

怎樣辨別一個(gè)模型是線性規(guī)劃模型？

線性規(guī)劃問(wèn)題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：3.線性規(guī)劃數(shù)學(xué)模型的一般形式簡(jiǎn)寫(xiě)為：線性規(guī)劃問(wèn)題的數(shù)學(xué)模型通常稱

為決策變量，

為價(jià)值系數(shù)，

為消耗系數(shù),

。為資源限制系數(shù)。線性規(guī)劃問(wèn)題的數(shù)學(xué)模型向量形式：其中：線性規(guī)劃問(wèn)題的數(shù)學(xué)模型矩陣形式：其中：線性規(guī)劃問(wèn)題的數(shù)學(xué)模型4.線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式特點(diǎn)：(1)目標(biāo)函數(shù)求最大值（有時(shí)求最小值）(2)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3)決策變量xj為非負(fù)。線性規(guī)劃問(wèn)題的數(shù)學(xué)模型（1）如何化標(biāo)準(zhǔn)形式目標(biāo)函數(shù)的轉(zhuǎn)換如果是求極小值即則可將目標(biāo)函數(shù)乘以(-1)可化為求極大值問(wèn)題。也就是：令可得到上式。即若存在取值無(wú)約束的變量可令其中：變量的轉(zhuǎn)換線性規(guī)劃問(wèn)題的數(shù)學(xué)模型約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量變量的變換當(dāng)可令，顯然線性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.3將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式用替換，且解:（１）因?yàn)閤3無(wú)符號(hào)要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以線性規(guī)劃問(wèn)題的數(shù)學(xué)模型(2)第一個(gè)約束條件是“≤”號(hào)，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個(gè)約束條件是“≥”號(hào)，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1),將右端常數(shù)項(xiàng)化為正數(shù)；(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當(dāng)z達(dá)到最小值時(shí)z′達(dá)到最大值，反之亦然;線性規(guī)劃問(wèn)題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：線性規(guī)劃問(wèn)題的數(shù)學(xué)模型5.線性規(guī)劃問(wèn)題的解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題，就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。線性規(guī)劃問(wèn)題的求解方法線性規(guī)劃問(wèn)題的求解方法一般有兩種方法圖解法單純形法兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡(jiǎn)單的情況——只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，這時(shí)可以通過(guò)圖解的方法來(lái)求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。圖解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.5用圖解法求解線性規(guī)劃問(wèn)題圖解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值

maxZ=17.2可行域maxZ=2X1+X2圖解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）34.2=3X1+5.7X2

藍(lán)色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏驁D解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZ

minZ

8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點(diǎn)是唯一最優(yōu)解圖解法246x1x2246無(wú)界解(無(wú)最優(yōu)解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)

maxZ

minZx1x2O10203040102030405050無(wú)可行解(即無(wú)最優(yōu)解)maxZ=3x1+4x2例1.7圖解法 學(xué)習(xí)要點(diǎn)：

1.通過(guò)圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解）

2.作圖的關(guān)鍵有三點(diǎn)：

(1)可行解區(qū)域要畫(huà)正確

(2)目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò)

(3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)線性規(guī)劃問(wèn)題的求解方法

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。

基：設(shè)A為約束條件②的m×n階系數(shù)矩陣(m<n)，其秩為m，B是矩陣A中m階滿秩子矩陣（∣B∣≠0），稱B是規(guī)劃問(wèn)題的一個(gè)基。設(shè)：稱B中每個(gè)列向量Pj(j=12……m)

為基向量。與基向量Pj

對(duì)應(yīng)的變量xj

為基變量。除基變量以外的變量為非基變量。線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

基解：對(duì)某一確定的基B，令所有的非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個(gè)數(shù)不大于方程數(shù)m，基解的總數(shù)不超過(guò)

基可行解：滿足變量非負(fù)約束條件的基本解，簡(jiǎn)稱基可行解。可行基：對(duì)應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解線性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.4求線性規(guī)劃問(wèn)題的所有基矩陣。解:約束方程的系數(shù)矩陣為2×5矩陣r(A)=2，2階子矩陣有10個(gè)，其中基矩陣只有9個(gè)，即單純形法基本原理凸集：對(duì)于集合C中的任意兩個(gè)點(diǎn)X1、X2，其連線上的所有點(diǎn)也都是集合C中的點(diǎn)，則稱C為凸集。凸集凸集不是凸集頂點(diǎn)單純形法基本原理極點(diǎn)（凸集的頂點(diǎn)）凸集上不在兩個(gè)不同點(diǎn)的連線上的點(diǎn)。定理1：若線性規(guī)劃問(wèn)題存在可行解，則該問(wèn)題的可行域是凸集。定理2：線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)可行域(凸集)的頂點(diǎn)。定理3：若問(wèn)題存在最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解或最優(yōu)解一定在某個(gè)頂點(diǎn)上取得）線性規(guī)劃問(wèn)題的幾個(gè)特點(diǎn)：線性規(guī)劃問(wèn)題的可行解的集合是凸集線性規(guī)劃問(wèn)題的基可行解一般都對(duì)應(yīng)于凸集的極點(diǎn)凸集的極點(diǎn)的個(gè)數(shù)是有限的最優(yōu)解只可能在凸集的頂點(diǎn)上，而不可能發(fā)生在凸集的內(nèi)部。

我們可以證明以下結(jié)論：線性規(guī)劃的基本可行解就是可行域的極點(diǎn)。這個(gè)結(jié)論被稱為線性規(guī)劃的基本定理，它的重要性在于把可行域的極點(diǎn)這一幾何概念與基本可行解這一代數(shù)概念聯(lián)系起來(lái)，因而可以通過(guò)求基本可行解的線性代數(shù)的方法來(lái)得到可行域的一切極點(diǎn)，從而有可能進(jìn)一步獲得最優(yōu)極點(diǎn)。線性規(guī)劃問(wèn)題的幾個(gè)特點(diǎn)：

線性規(guī)劃問(wèn)題的單純形解法線性規(guī)劃的標(biāo)準(zhǔn)型的向量和矩陣表達(dá)形向量式和矩陣形式

maxZ=CX

maxZ=CXs.t.p1x1+p2x2+…+pnxn=b

s.t.AX=b

xj≥0（j=1，2，…n）

X≥0式中：pj=（a1j，a2j，…，amj）TC=（c1，c2，…，cn）

X

=（x1，x2，…，xn）T

b=（b1，b2，…，bm）T

線性規(guī)劃問(wèn)題的單純形解法再給出單純形解法之前先回顧前面的例子：解:約束方程的系數(shù)矩陣為2×5矩陣r(A)=2，2階子矩陣有10個(gè)，其中基矩陣只有9個(gè)，即線性規(guī)劃問(wèn)題的單純形解法1、寫(xiě)出對(duì)應(yīng)于每一個(gè)基的解。2、找出基可行解。3、找出最優(yōu)解。對(duì)應(yīng)于基B1的基解令對(duì)應(yīng)于基B2的基解令以上兩個(gè)基本解中對(duì)應(yīng)于B1的解為基本可行解，B1為可行基

線性規(guī)劃問(wèn)題的單純形解法類似可得到x(3)=(3/5,0,0,0,8)T

（對(duì)應(yīng)B3）

x(4)=(0,1/3,0,8/3,0)T

（對(duì)應(yīng)B4）

x(7)=(0,0,1,4,0)T

（對(duì)應(yīng)B7）x(9)=(0,0,0,3,2)T

（對(duì)應(yīng)B9）是基本可行解；而x(5)=(-1/5,0,0,4,0)T（對(duì)應(yīng)B5）

x(6)=(0,0,3,0,-4)T

（對(duì)應(yīng)B6）

x(8)=(0,3,0,0,-16)T

（對(duì)應(yīng)B8）是基本解。因此，對(duì)應(yīng)基本可行解（極點(diǎn)）的B1B3B4B7B9都是可行基。將基可行解代入目標(biāo)函數(shù)比較目標(biāo)函數(shù)值的大小，找出最優(yōu)解。線性規(guī)劃問(wèn)題的單純形解法在看書(shū)中的例子：基變量的個(gè)數(shù)為：線性規(guī)劃問(wèn)題的單純形解法對(duì)應(yīng)于這些基的基解為：線性規(guī)劃問(wèn)題的單純形解法其中基可行解有：對(duì)應(yīng)可行解域的5個(gè)頂點(diǎn)，帶入目標(biāo)函數(shù)求值比較即可線性規(guī)劃問(wèn)題的單純形解法這里指出了一種求解線性規(guī)劃問(wèn)題的可能途徑，就是先確定線性規(guī)劃問(wèn)題的基，如果是可行基，則計(jì)算相應(yīng)的基本可行解以及相應(yīng)解的目標(biāo)函數(shù)值。由于基的個(gè)數(shù)是有限的（最多個(gè)），因此必定可以從有限個(gè)基本可行解中找到最優(yōu)解。

利用求解線性規(guī)劃問(wèn)題基本可行解（極點(diǎn)）的方法來(lái)求解較大規(guī)模的問(wèn)題是不可行的。單純形法的基本思路是有選擇地取基本可行解，即是從可行域的一個(gè)極點(diǎn)出發(fā)，沿著可行域的邊界移到另一個(gè)相鄰的極點(diǎn)，要求新極點(diǎn)的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差單純形法的計(jì)算步驟單純形法的思路找出一個(gè)初始可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)基本可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束線性規(guī)劃問(wèn)題的單純形解法

單純形方法是Dantzig于1947年首先發(fā)明的。近50年來(lái)，一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問(wèn)題的求解。本節(jié)討論單純形法的基本算法。單純形法的初步討論。單純形法的計(jì)算步驟初始單純形表單純形法的計(jì)算步驟例1.8用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問(wèn)題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:單純形法的計(jì)算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicB基bx1x2x3x40x34021100x43013013400檢驗(yàn)數(shù)單純形法的計(jì)算步驟3）進(jìn)行最優(yōu)性檢驗(yàn)如果表中所有檢驗(yàn)數(shù)，則表中的基可行解就是問(wèn)題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。4）從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對(duì)應(yīng)的變量xj作為換入變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于0時(shí)，一般選擇最大的一個(gè)檢驗(yàn)數(shù)，即：，其對(duì)應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計(jì)算并選擇θ

，選最小的θ對(duì)應(yīng)基變量作為換出變量。 單純形法的計(jì)算步驟用換入變量xk替換基變量中的換出變量，得到一個(gè)新的基。對(duì)應(yīng)新的基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫(huà)出一個(gè)新的單純形表。5）重復(fù)3）、4）步直到計(jì)算結(jié)束為止。 單純形法的計(jì)算步驟cj3400θicB基變量bx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－1單純形法的計(jì)算步驟例1.9用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。單純形法的計(jì)算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3單純形法的計(jì)算步驟 學(xué)習(xí)要點(diǎn)：

1.線性規(guī)劃解的概念以及3個(gè)基本定理

2.熟練掌握單純形法的解題思路及求解步驟單純形法的進(jìn)一步討論－人工變量法人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。單純形法的進(jìn)一步討論－人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。單純形法的進(jìn)一步討論－人工變量法故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見(jiàn)下表。單純形法的進(jìn)一步討論－人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi0x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M0x63-650-1013/5-Mx58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→單純形法的進(jìn)一步討論－人工變量法 解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或無(wú)窮多最優(yōu)解）。3）無(wú)界解判別：某個(gè)λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無(wú)界解。4）無(wú)可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri>0時(shí)，則表明原線性規(guī)劃無(wú)可行解。5）退化解的判別：存在某個(gè)基變量為零的基本可行解。單純形法的進(jìn)一步討論－人工變量法單純性法小結(jié):建立模型個(gè)數(shù)取值右端項(xiàng)等式或不等式極大或極小新加變量系數(shù)兩個(gè)三個(gè)以上x(chóng)j≥0xj無(wú)約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj’

=-xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′=-ZminZ=－maxz′0-MA線性規(guī)劃問(wèn)題的Excel求解利用Excel求解書(shū)中例題：該問(wèn)題在excel的規(guī)劃模型如下：線性規(guī)劃問(wèn)題的Excel求解實(shí)際消耗A的計(jì)算=B3*B9+C3*C9;也可以用函數(shù)計(jì)算如圖:線性規(guī)劃問(wèn)題的Excel求解其中Array1中的單元格地址使用絕對(duì)應(yīng)用

:線性規(guī)劃問(wèn)題的Excel求解單擊選項(xiàng)按鈕出現(xiàn)如下對(duì)話框:線性規(guī)劃問(wèn)題的Excel求解單擊確定按鈕；又出現(xiàn)規(guī)劃參數(shù)求解對(duì)話框,再單擊求解按鈕：線性規(guī)劃模型的應(yīng)用 一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿足以下條件時(shí)，才能建立線性規(guī)劃模型。要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù)存在著多種方案要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述線性規(guī)劃在管理中的應(yīng)用人力資源分配問(wèn)題例1.11某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示：班次時(shí)間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段開(kāi)始時(shí)上班，并連續(xù)工作8小時(shí)，問(wèn)該公交線路應(yīng)怎樣安排司機(jī)和乘務(wù)人員，即能滿足工作需要，又使配備司機(jī)和乘務(wù)人員的人數(shù)最少?線性規(guī)劃在管理中的應(yīng)用解：設(shè)xi表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員人數(shù)。此問(wèn)題最優(yōu)解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司機(jī)和乘務(wù)員150人。線性規(guī)劃在管理中的應(yīng)用2.生產(chǎn)計(jì)劃問(wèn)題某工廠生產(chǎn)A、B兩種產(chǎn)品，均須經(jīng)過(guò)兩道工序，每生產(chǎn)1噸 A產(chǎn)品需要第一道工序2小時(shí)，第二道工序3小時(shí)，每生產(chǎn)1噸B產(chǎn)品需要第一道工序3小時(shí)，第二道工序4小時(shí)，可供利用的第一道工序15小時(shí)，第二道工序25小時(shí)；生產(chǎn)產(chǎn)品B的同時(shí)可生產(chǎn)副產(chǎn)品C，每生產(chǎn)一噸產(chǎn)品B，可同時(shí)得到兩噸產(chǎn)品C而不需要外加任何費(fèi)用，這副產(chǎn)品C一部分可以盈利，但剩下的只能報(bào)廢，報(bào)廢需要一定的費(fèi)用。各項(xiàng)費(fèi)用的情況為：出售產(chǎn)品A，每噸能盈利400元，出售產(chǎn)品B,每噸能盈利800元，每售出一噸副產(chǎn)品C能盈利300元；當(dāng)剩余的產(chǎn)品C報(bào)廢時(shí)，每噸損失費(fèi)為200元，經(jīng)市場(chǎng)預(yù)測(cè)，在計(jì)劃期內(nèi)產(chǎn)品C的最大銷售量為5噸，試列出本問(wèn)題的線性規(guī)劃模型，如何安排A、B兩種產(chǎn)品的產(chǎn)量，可使工廠總盈利最大？解：設(shè)決策變量……線性規(guī)劃在管理中的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題某公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，也可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。有關(guān)情況的數(shù)據(jù)如表所示，問(wèn)公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？（甲、乙兩種產(chǎn)品的鑄件中本公司鑄造和外包協(xié)作各應(yīng)多少件？）線性規(guī)劃在管理中的應(yīng)用產(chǎn)品工時(shí)與成甲乙丙工時(shí)限制單件鑄造工時(shí)51078000單件機(jī)加工工時(shí)64812000單件裝配工時(shí)3221000自產(chǎn)鑄件成本354外協(xié)鑄件成本56機(jī)加工成本213裝配成本322產(chǎn)品售價(jià)231816線性規(guī)劃在管理中的應(yīng)用解：設(shè)線性規(guī)劃在管理中的應(yīng)用下料問(wèn)題：某工廠要制作50套規(guī)格的產(chǎn)品，這種產(chǎn)品每套需要用長(zhǎng)為1.5米的料2根，1.45米的料2根，1.3米的料6根和0.35米的料12根，已知可供使用的原料長(zhǎng)度為8米，問(wèn)如何考慮可是使用的原料數(shù)最少？線性規(guī)劃在管理中的應(yīng)用項(xiàng)目投資優(yōu)化問(wèn)題：某公司有一批資金用A、B、C、D、E、5個(gè)工程項(xiàng)目的投資已知用于各工程項(xiàng)目時(shí)所得之凈收益（投入資金的百分比）如下表，由于某種原因用于項(xiàng)目A的投資不大于其他各項(xiàng)目投資之和，而用于項(xiàng)目B和E的投資之和不小于項(xiàng)目C的投資，試確定使該公司受益最大的投資分配方案？工程項(xiàng)目ABCDE收益（％）108659線性規(guī)劃在管理中的應(yīng)用廠址選擇問(wèn)題：甲、乙、丙三地，每地都生產(chǎn)一定數(shù)量的原料，也消耗一定數(shù)量的產(chǎn)品（數(shù)據(jù)如下表），已知制造每噸產(chǎn)品需要3噸原料，各地之間的距離為甲→乙為150公里，甲→丙為100公里，乙→丙為200公里，假定每萬(wàn)噸原料運(yùn)輸1公里的造價(jià)為5000元，假定每萬(wàn)噸產(chǎn)品運(yùn)輸1公里的造價(jià)為6000元，由于地區(qū)差異，在不同的地區(qū)該廠的生產(chǎn)費(fèi)用也不同，試問(wèn)究竟在那些地方設(shè)廠、規(guī)模多大，才能使總費(fèi)用最??？另外，由于其他條件限制，在乙處建廠的規(guī)模（生產(chǎn)的產(chǎn)品數(shù)量）不能超過(guò)5萬(wàn)噸。線性規(guī)劃在管理中的應(yīng)用

地點(diǎn)年產(chǎn)原料（萬(wàn)噸）年消耗產(chǎn)品萬(wàn)噸）年生產(chǎn)費(fèi)用（萬(wàn)元/萬(wàn)噸）甲207150乙1613120丙240100線性規(guī)劃在管理中的應(yīng)用2.生產(chǎn)計(jì)劃問(wèn)題 某廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1和A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序。已知產(chǎn)品Ⅰ可在A、B任何一種設(shè)備上加工；產(chǎn)品Ⅱ可在任何規(guī)格的A設(shè)備上加工，但完成B工序時(shí)，只能在B1設(shè)備上加工；產(chǎn)品Ⅲ只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。線性規(guī)劃在管理中的應(yīng)用設(shè)備產(chǎn)品設(shè)備有效臺(tái)時(shí)設(shè)備加工費(fèi)（單位小時(shí)）ⅠⅡⅢ27910000321B168124000250B247000783B37114000200原料費(fèi)（每件）0.250.350.5售價(jià)（每件）1.252.002.8線性規(guī)劃在管理中的應(yīng)用解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條件有：線性規(guī)劃在管理中的應(yīng)用目標(biāo)是利潤(rùn)最大化，即利潤(rùn)的計(jì)算公式如下：帶入數(shù)據(jù)整理得到：線性規(guī)劃在管理中的應(yīng)用因此該規(guī)劃問(wèn)題的模型為：線性規(guī)劃在管理中的應(yīng)用3.套裁下料問(wèn)題例：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米，需要截取2.5米長(zhǎng)的毛坯100根，長(zhǎng)1.3米的毛坯200根。問(wèn)如何才能既滿足需要，又能使總的用料最少？解：為了找到一個(gè)省料的套裁方案，必須先設(shè)計(jì)出較好的幾個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計(jì)出4種下料方案以供套裁用。ⅠⅡⅢⅣ2.5m32101.3m0246料頭0線性規(guī)劃在管理中的應(yīng)用設(shè)按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根數(shù)分別為xj(j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：線性規(guī)劃在管理中的應(yīng)用4.配料問(wèn)題例：某人每天食用甲、乙兩種食物（如豬肉、雞蛋），其資料如下：?jiǎn)杻煞N食物各食用多少，才能既滿足需要、又使總費(fèi)用最?。?/p>

21.5原料單價(jià)1.007.5010.00

0.751.101.30A1A2A3

最低需要量

甲乙含量食物成分線性規(guī)劃在管理中的應(yīng)用解：設(shè)Xj表示Bj

種食物用量Chapter2對(duì)偶理論

(DualityTheory)線性規(guī)劃的對(duì)偶模型對(duì)偶性質(zhì)對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋－影子價(jià)格對(duì)偶單純形法本章主要內(nèi)容：線性規(guī)劃的對(duì)偶模型 設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表：產(chǎn)品數(shù)據(jù)表設(shè)備產(chǎn)品ABCD產(chǎn)品利潤(rùn)（元／件）

甲

21402乙

22043設(shè)備可利用機(jī)時(shí)數(shù)（時(shí)）

1281612問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤(rùn)？1.對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源線性規(guī)劃的對(duì)偶模型解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學(xué)模型為：反過(guò)來(lái)問(wèn)：若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么４種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？線性規(guī)劃的對(duì)偶模型在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠長(zhǎng)的最佳決策顯然應(yīng)符合兩條：

（1）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于加工甲、乙型產(chǎn)品所獲利潤(rùn)。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。（2）競(jìng)爭(zhēng)性原則。即在上述不吃虧原則下，盡量降低機(jī)時(shí)總收費(fèi)，以便爭(zhēng)取更多用戶。設(shè)A、B、C、D設(shè)備的機(jī)時(shí)價(jià)分別為y1、y2、y3、y4，則新的線性規(guī)劃數(shù)學(xué)模型為：線性規(guī)劃的對(duì)偶模型把同種問(wèn)題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象。原問(wèn)題與對(duì)偶問(wèn)題對(duì)比表A（y1）

B（y2）C（y3）

D（y4）

甲（x1）

21402乙（x2）

220431281612

minωmaxz

線性規(guī)劃的對(duì)偶模型2.原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）線性規(guī)劃的對(duì)偶模型（1）對(duì)稱形式 特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為≤號(hào)，變量非負(fù);目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為≥號(hào)，變量非負(fù).已知P，寫(xiě)出D線性規(guī)劃的對(duì)偶模型例2.1寫(xiě)出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題解：首先將原問(wèn)題變形為對(duì)稱形式線性規(guī)劃的對(duì)偶模型線性規(guī)劃的對(duì)偶模型(2)非對(duì)稱型對(duì)偶問(wèn)題 若給出的線性規(guī)劃不是對(duì)稱形式，可以先化成對(duì)稱形式再寫(xiě)對(duì)偶問(wèn)題。也可直接按教材表2-2中的對(duì)應(yīng)關(guān)系寫(xiě)出非對(duì)稱形式的對(duì)偶問(wèn)題。線性規(guī)劃的對(duì)偶模型原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個(gè)m個(gè)變量≤≥0≥≤0=無(wú)約束變量n個(gè)n個(gè)約束條件≥0≥≤0≤無(wú)約束=線性規(guī)劃的對(duì)偶模型例2.2寫(xiě)出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.解：原問(wèn)題的對(duì)偶問(wèn)題為對(duì)偶性質(zhì)例2.3分別求解下列2個(gè)互為對(duì)偶關(guān)系的線性規(guī)劃問(wèn)題分別用單純形法求解上述2個(gè)規(guī)劃問(wèn)題，得到最終單純形表如下表：對(duì)偶性質(zhì)XBb原問(wèn)題的變量原問(wèn)題的松弛變量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2000－1/4－1/2XBb對(duì)偶問(wèn)題的變量對(duì)偶問(wèn)題的剩余變量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2原問(wèn)題最優(yōu)表對(duì)偶問(wèn)題最優(yōu)表對(duì)偶性質(zhì)原問(wèn)題與其對(duì)偶問(wèn)題的變量與解的對(duì)應(yīng)關(guān)系： 在單純形表中，原問(wèn)題的松弛變量對(duì)應(yīng)對(duì)偶問(wèn)題的變量，對(duì)偶問(wèn)題的剩余變量對(duì)應(yīng)原問(wèn)題的變量。對(duì)偶性質(zhì)性質(zhì)1對(duì)稱性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥bX≥0對(duì)偶性質(zhì)性質(zhì)2

弱對(duì)偶原理(弱對(duì)偶性)：設(shè)和分別是問(wèn)題(P)和(D)的可行解，則必有推論1:原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下屆；反之，對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。推論2:

在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若其中一個(gè)問(wèn)題可行但目標(biāo)函數(shù)無(wú)界，則另一個(gè)問(wèn)題無(wú)可行解；反之不成立。這也是對(duì)偶問(wèn)題的無(wú)界性。對(duì)偶性質(zhì)推論3：在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若一個(gè)可行（如P），而另一個(gè)不可行（如D），則該可行的問(wèn)題目標(biāo)函數(shù)值無(wú)界。性質(zhì)3

最優(yōu)性定理：如果是原問(wèn)題的可行解，是其對(duì)偶問(wèn)題的可行解，并且:則是原問(wèn)題的最優(yōu)解，是其對(duì)偶問(wèn)題的最優(yōu)解。對(duì)偶性質(zhì)性質(zhì)4強(qiáng)對(duì)偶性：若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。 還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個(gè)問(wèn)題無(wú)最優(yōu)解，則另一問(wèn)題也無(wú)最優(yōu)解。性質(zhì)5

互補(bǔ)松弛性：設(shè)X0和Y0分別是P問(wèn)題和D問(wèn)題的可行解，則它們分別是最優(yōu)解的充要條件是：其中：Xs、Ys為松弛變量對(duì)偶性質(zhì)性質(zhì)5的應(yīng)用： 該性質(zhì)給出了已知一個(gè)問(wèn)題最優(yōu)解求另一個(gè)問(wèn)題最優(yōu)解的方法，即已知Y＊求X＊或已知X＊求Y＊互補(bǔ)松弛條件由于變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：若Y＊≠0，則Xs必為0；若X＊≠0，則Ys必為0利用上述關(guān)系，建立對(duì)偶問(wèn)題（或原問(wèn)題）的約束線性方程組，方程組的解即為最優(yōu)解。對(duì)偶性質(zhì)例2.4

已知線性規(guī)劃的最優(yōu)解是X＊=(6,2,0)T,求其對(duì)偶問(wèn)題的最優(yōu)解Y＊。解：寫(xiě)出原問(wèn)題的對(duì)偶問(wèn)題，即標(biāo)準(zhǔn)化對(duì)偶性質(zhì)設(shè)對(duì)偶問(wèn)題最優(yōu)解為Y＊＝(y1，y2),由互補(bǔ)松弛性定理可知，X＊和Y＊滿足：即：因?yàn)閄1≠0，X2≠0，所以對(duì)偶問(wèn)題的第一、二個(gè)約束的松弛變量等于零，即y3＝0，y4＝0，帶入方程中：解此線性方程組得y1=1,y2=1,從而對(duì)偶問(wèn)題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。對(duì)偶性質(zhì)例2.5已知線性規(guī)劃的對(duì)偶問(wèn)題的最優(yōu)解為Y＊=(0,-2)，求原問(wèn)題的最優(yōu)解。解:對(duì)偶問(wèn)題是標(biāo)準(zhǔn)化對(duì)偶性質(zhì)設(shè)對(duì)偶問(wèn)題最優(yōu)解為X＊＝(x1，x2，x3)T,由互補(bǔ)松弛性定理可知，X＊和Y＊滿足：將Y＊帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1?！遹2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0將x2，x5分別帶入原問(wèn)題約束方程中，得：解方程組得：x1=-5,x3=-1,所以原問(wèn)題的最優(yōu)解為X＊=(-5,0,-1)，最優(yōu)值z(mì)=-12對(duì)偶性質(zhì)原問(wèn)題與對(duì)偶問(wèn)題解的對(duì)應(yīng)關(guān)系小結(jié)對(duì)應(yīng)關(guān)系原問(wèn)題最優(yōu)解無(wú)界解無(wú)可行解對(duì)偶問(wèn)題最優(yōu)解(Y,Y)(N,N)————無(wú)界解————(Y,Y)無(wú)可行解——(Y,Y)無(wú)法判斷思考題判斷下列結(jié)論是否正確，如果不正確，應(yīng)該怎樣改正？1）任何線性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線性規(guī)劃.2）原問(wèn)題第i個(gè)約束是“≤”約束，則對(duì)偶變量yi≥0.3）互為對(duì)偶問(wèn)題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無(wú)最優(yōu)解.4）對(duì)偶問(wèn)題有可行解，則原問(wèn)題也有可行解.5）原問(wèn)題有多重解，對(duì)偶問(wèn)題也有多重解.6）對(duì)偶問(wèn)題有可行解，原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題具有無(wú)界解.7）原問(wèn)題無(wú)最優(yōu)解，則對(duì)偶問(wèn)題無(wú)可行解.8）對(duì)偶問(wèn)題不可行，原問(wèn)題可能無(wú)界解.9）原問(wèn)題與對(duì)偶問(wèn)題都可行，則都有最優(yōu)解.10）原問(wèn)題具有無(wú)界解，則對(duì)偶問(wèn)題不可行.11）對(duì)偶問(wèn)題具有無(wú)界解，則原問(wèn)題無(wú)最優(yōu)解.12）若X*、Y*是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解，則X*=Y*.對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋－影子價(jià)格1.影子價(jià)格的數(shù)學(xué)分析：定義：在一對(duì)P和D中，若P的某個(gè)約束條件的右端項(xiàng)常數(shù)bi（第i種資源的擁有量）增加一個(gè)單位時(shí)，所引起目標(biāo)函數(shù)最優(yōu)值z(mì)*的改變量稱為第i種資源的影子價(jià)格，其值等于D問(wèn)題中對(duì)偶變量yi*。由對(duì)偶問(wèn)題得基本性質(zhì)可得：對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋－影子價(jià)格2.影子價(jià)格的經(jīng)濟(jì)意義1）影子價(jià)格是一種邊際價(jià)格 在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即對(duì)偶變量yi就是第i種資源的影子價(jià)格。即：

對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋－影子價(jià)格2）影子價(jià)格是一種機(jī)會(huì)成本 影子價(jià)格是在資源最優(yōu)利用條件下對(duì)單位資源的估價(jià)，這種估價(jià)不是資源實(shí)際的市場(chǎng)價(jià)格。因此，從另一個(gè)角度說(shuō)，它是一種機(jī)會(huì)成本。若第i種資源的單位市場(chǎng)價(jià)格為mi

，則有當(dāng)yi*>mi

時(shí)，企業(yè)愿意購(gòu)進(jìn)這種資源，單位純利為yi*－mi

，則有利可圖；如果yi*<mi

，則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利mi－yi

*

，否則，企業(yè)無(wú)利可圖，甚至虧損。結(jié)論：若yi*>mi則購(gòu)進(jìn)資源i，可獲單位純利yi*－mi

若yi*<mi則轉(zhuǎn)讓資源i，可獲單位純利mi－yi對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋－影子價(jià)格3）影子價(jià)格在資源利用中的應(yīng)用根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理:Y*Xs=0,YsX*=0表明生產(chǎn)過(guò)程中如果某種資源bi未得到充分利用時(shí)，該種資源的影子價(jià)格為0；若當(dāng)資源資源的影子價(jià)格不為0時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完。對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋－影子價(jià)格4）影子價(jià)格對(duì)單純形表計(jì)算的解釋單純形表中的檢驗(yàn)數(shù)其中cj表示第j種產(chǎn)品的價(jià)格;表示生產(chǎn)該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和,即產(chǎn)品的隱含成本。當(dāng)產(chǎn)值大于隱含成本時(shí)，即，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排；否則，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。對(duì)偶單純形法 對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它是根據(jù)對(duì)偶原理和單純形法原理而設(shè)計(jì)出來(lái)的，因此稱為對(duì)偶單純形法。不要簡(jiǎn)單理解為是求解對(duì)偶問(wèn)題的單純形法。對(duì)偶單純形法原理對(duì)偶單純形法基本思路： 找出一個(gè)對(duì)偶問(wèn)題的可行基，保持對(duì)偶問(wèn)題為可行解的條件下，判斷XB是否可行（XB為非負(fù)），若否，通過(guò)變換基解，直到找到原問(wèn)題基可行解（即XB為非負(fù)），這時(shí)原問(wèn)題與對(duì)偶問(wèn)題同時(shí)達(dá)到可行解，由定理4可得最優(yōu)解。對(duì)偶單純形法找出一個(gè)DP的可行基LP是否可行（XB≥0）保持DP為可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解最優(yōu)解是否循環(huán)結(jié)束對(duì)偶單純形法例2.9用對(duì)偶單純形法求解：解:（1）將模型轉(zhuǎn)化為求最大化問(wèn)題，約束方程化為等式求出一組基本解，因?yàn)閷?duì)偶問(wèn)題可行，即全部檢驗(yàn)數(shù)≤0（求max問(wèn)題）。對(duì)偶單純形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-2-2-1100-100x5-2-3-1010-120x6-1-1-5001-14(-9/-1.-12/-1.

-15/-5)λj-9-12-150000對(duì)偶單純形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14對(duì)偶單純形法cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3原問(wèn)題的最優(yōu)解為：X*=（2,2,2,0,0,0），Z*=72其對(duì)偶問(wèn)題的最優(yōu)解為：Y*=（1/3,3,7/3），W*=72對(duì)偶單純形法對(duì)偶單純形法應(yīng)注意的問(wèn)題：

用對(duì)偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對(duì)偶問(wèn)題的最優(yōu)解初始表中一定要滿足對(duì)偶問(wèn)題可行，也就是說(shuō)檢驗(yàn)數(shù)滿足最優(yōu)判別準(zhǔn)則最小比值中的絕對(duì)值是使得比值非負(fù)，在極小化問(wèn)題σj≥0，分母aij<0這時(shí)必須取絕對(duì)值。在極大化問(wèn)題中，σ

j≤0，分母aij<0，總滿足非負(fù)，這時(shí)絕對(duì)值符號(hào)不起作用，可以去掉。如在本例中將目標(biāo)函數(shù)寫(xiě)成這里σj≤0在求θk時(shí)就可以不帶絕對(duì)值符號(hào)。對(duì)偶單純形法對(duì)偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進(jìn)基變量后確定出基變量，對(duì)偶單純形法是先確定出基變量后確定進(jìn)基變量；普通單純形法的最小比值是其目的是保證下一個(gè)原問(wèn)題的基本解可行，對(duì)偶單純形法的最小比值是其目的是保證下一個(gè)對(duì)偶問(wèn)題的基本解可行對(duì)偶單純形法在確定出基變量時(shí)，若不遵循規(guī)則，任選一個(gè)小于零的bi對(duì)應(yīng)的基變量出基，不影響計(jì)算結(jié)果，只是迭代次數(shù)可能不一樣。本章小結(jié) 學(xué)習(xí)要點(diǎn)：

1.線性規(guī)劃解的概念以及3個(gè)基本定理

2.熟練掌握單純形法的解題思路及求解步驟Chapter3運(yùn)輸規(guī)劃

(TransportationProblem)運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型表上作業(yè)法運(yùn)輸問(wèn)題的應(yīng)用本章主要內(nèi)容：運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型例3.1某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1,B2,B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？B1B2B3產(chǎn)量A1646200A2655300銷量150150200運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型解：產(chǎn)銷平衡問(wèn)題：總產(chǎn)量=總銷量＝500

設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的一般形式：產(chǎn)銷平衡A1、A2、…、Am

表示某物資的m個(gè)產(chǎn)地；B1、B2、…、Bn

表示某物質(zhì)的n個(gè)銷地；ai

表示產(chǎn)地Ai的產(chǎn)量；bj

表示銷地Bj

的銷量；cij表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問(wèn)題的模型：運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型變化：

1）有時(shí)目標(biāo)函數(shù)求最大。如求利潤(rùn)最大或營(yíng)業(yè)額最大等；

2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入約束條件（等式或不等式約束)；

3）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。定理:

設(shè)有m個(gè)產(chǎn)地n個(gè)銷地且產(chǎn)銷平衡的運(yùn)輸問(wèn)題，則基變量數(shù)為m+n-1。表上作業(yè)法表上作業(yè)法是一種求解運(yùn)輸問(wèn)題的特殊方法，其實(shí)質(zhì)是單純形法。步驟描述方法第一步求初始基行可行解（初始調(diào)運(yùn)方案）最小元素法、元素差額法、第二步求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗(yàn)數(shù)σij全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)σij<0，說(shuō)明還沒(méi)有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位勢(shì)法第三步調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步表上作業(yè)法例3.2某運(yùn)輸資料如下表所示：?jiǎn)挝讳N地運(yùn)價(jià)產(chǎn)地產(chǎn)量311310719284741059銷量3656問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？表上作業(yè)法解：第1步求初始方案方法1：最小元素法基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開(kāi)始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058341633表上作業(yè)法總的運(yùn)輸費(fèi)＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元 元素差額法對(duì)最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。例如下面兩種運(yùn)輸方案。85102120151515510總運(yùn)費(fèi)是z=10×8+5×2+15×1=105最小元素法：表上作業(yè)法85102120151551510總運(yùn)費(fèi)z=10×5+15×2+5×1=85后一種方案考慮到C11與C21之間的差額是8－2=6，如果不先