JournalonComputing

緒論教材：《運籌學》，徐渝，李鵬翔和鄭斐峰著中國人民大學出版社；《運籌學》，甘應愛，田豐等著，清華大學出版社01“OR”是什么？03“OR”有什么？“OR”能做什么？0204我們“學什么”？CONTENTS05應該“怎么學”？回答五個問題：PART01什么是運籌學？“運籌帷幄之中，決勝千里之外”西漢初年，天下已定，漢高祖劉邦在洛陽南宮舉行盛大的宴會，喝了幾輪酒后，他向群臣提出一個問題：“我為什么會取得勝利？而項羽為什么會失?。俊备咂鸬日J為高祖派有才能的人攻城略地，給立大功的人加官奉爵，所以能成大事業(yè)。而項羽恰恰相反，有人不利，立功不獎，賢人遭疑，所以他才失敗。漢高祖劉邦聽了，認為他們說的有道理，但是最重要的原因是能用人。他稱贊張良說：“夫運籌帷幄之中，決勝千里之外，吾不如子房?！币馑际钦f，張良坐在軍帳中運用計謀，就能決定千里之外戰(zhàn)斗的勝利。這說明張良心計多，善用腦，善用兵。

什么是運籌學？東北航空公司正在考慮購買新型長途、中途、短途噴氣客機。每架長途客機的購買成本是6700萬美元，每架中途客機的購買成本是5000萬美元，每架短途客機的購買成本是3500萬美元。董事會已經為本次購買批準了最多15億美元的金額。不考慮購買何種機型，公司希望每架飛機都能飛行盡可能多的距離以發(fā)揮最大的能力。公司估計(減去資本收回成本后)，每架長途客機年凈利潤能實現420萬美元，每架中途客機年凈利潤能實現300萬美元，每架短途客機年凈利潤能實現230萬美元。如果你是公司的管理層，你應該如何制定購買計劃以實現利潤最大化？什么是運籌學？如何才能作出一個滿意的決策？決策是管理者的主要工作內容什么是運籌學？兩類決策方法定性方法定量方法什么是運籌學？運籌學——OR（OperationsResearchorOperationalResearch）系統(tǒng)工程最重要的理論基礎之一，在美國有人把運籌學稱之為管理科學(ManagementScience)。運籌學所研究的問題，可簡單地歸結為一句話:“依照給定條件和目標，從眾多方案中選擇最佳方案“，故有人稱之為最優(yōu)化技術。什么是運籌學？制定決策管理者運用合理的分析來改善決策的制定運籌學由一支綜合性的隊伍，采用科學的方法，為一些涉及到有機系統(tǒng)（人-機）的控制系統(tǒng)問題提供解答，為該系統(tǒng)的總目標服務的學科。

——錢學森等什么是運籌學？運用科學方法來解決工業(yè)、商業(yè)、政府、國防等部門里有關人力、機器、物資、金錢等大型系統(tǒng)的指揮或管理中所出現的復雜問題的一門學科。其目的是“幫助管理者以科學方法確定其方針和行動”。

——英國運籌學會（世界上最早的運籌學會）運籌學是應用系統(tǒng)的、科學的、數學分析的方法，通過建模、檢驗和求解數學模型而獲得最優(yōu)決策的科學。

——近代一些運籌學工作者什么是運籌學？PART02運籌學的三個來源1、軍事兩次世界大戰(zhàn)期間的軍事運籌研究2、管理生產中的組織與計劃問題3、經濟馮·諾依曼宏觀經濟優(yōu)化的控制論模型運籌學的三個來源第一次世界大戰(zhàn)期間1914-1915蘭徹斯特的若干軍事論文研究戰(zhàn)爭的勝負同兵力多寡、火力強弱之間的關系；愛迪生解決反潛戰(zhàn)的“戰(zhàn)術對策演示盤”反潛戰(zhàn)的研究項目：匯編各項典型統(tǒng)計數據，用于選擇回避或擊毀潛艇的最佳方法，使用“戰(zhàn)術對策演示盤”解決免受潛艇攻擊的問題；運籌學的三個來源軍事大西洋反潛戰(zhàn)——Morse（莫爾斯）小組的重要工作1942年麻省Morse教授應美國大西洋艦隊反潛戰(zhàn)官員Baker（貝克）艦長的請求擔任反潛戰(zhàn)運籌組的計劃與監(jiān)督工作，其最出色的工作之一是協(xié)助英國打破了德國對英吉利海峽的海上封鎖，研究所提出的兩條重要建議是：

運籌學的三個來源軍事第二次世界大戰(zhàn)期間將反潛攻擊由反潛艦艇投擲水雷改為飛機投擲深水炸彈，起爆深度由100米改為25米左右，即當德方潛艇剛下潛時攻擊效果最佳；運送物資的船隊及護航艦艇的編隊由小規(guī)模、多批次改為大規(guī)模、少批次，從而減少了損失率；運籌學的三個來源軍事丘吉爾采納Morse的建議打破德國封鎖重創(chuàng)德國潛艇部隊Morse同時獲得英國及美國戰(zhàn)時最高勛章運籌學的三個來源軍事定量化系統(tǒng)化方法迅速發(fā)展采集真實的實際數據多學科密切協(xié)作解決方法滲透著物理學思想二戰(zhàn)時期軍事運籌學的特點運籌學的三個來源軍事管理科學的特點與學派科學性與藝術性古典學派、行為學派、系統(tǒng)學派、數理學派

古典管理學派對運籌學發(fā)展產生的影響尋求一些方法，使人們自愿地聯合與協(xié)作，保持個人的首創(chuàng)精神和創(chuàng)造能力，達到增加效率的目的。運籌學的三個來源管理動作研究與泰勒工作制切削效率與車速、進刀量等因素的數學關系——優(yōu)選問題提出管理的基本原則，研究了機構設置、權限、工廠布局、計劃等問題刺激性工資制舉世聞名用于生產活動分析和計劃安排的甘特橫道圖--

發(fā)展成為統(tǒng)籌方法運籌學的三個來源管理近三十年經濟數學和運籌學互相影響，相互促進，共同發(fā)展Vonneumann(馮．諾伊曼)的開創(chuàng)性工作近代博弈論創(chuàng)始人之一，1944年與Morgenstern(摩根斯坦)合作發(fā)表《博弈論與經濟行為》一書，將經濟活動中的沖突、協(xié)調、平衡分析題量化處理，解決了一些基本問題，如下棋、玩撲克牌等室內游戲中競賽者之間的討價還價，交涉，結伙，利益分配等行為方式的類似性。領導研究的電子計算機成為OR的技術實現支柱之一。慧眼識人最早肯定扶持當時未滿30歲的Dantzig從事的以單純形法為核心的線性規(guī)劃研究。運籌學的三個來源經濟PART03運籌學發(fā)展簡史1、萌芽時期2、早期研究3、形成與發(fā)展時期4、現代運籌學

三、

運籌學

發(fā)展

簡史

運籌學發(fā)展簡史1、萌芽時期樸素的OR思想自古有之例1、春秋戰(zhàn)國時期的孫臏斗馬術

例2、都江堰工程(“魚嘴”分水堤，“飛沙堰”溢洪道和“寶瓶口”進水口)

例3、宋真宗重建皇宮的方案例4、沈括《夢溪筆談》中記錄的戰(zhàn)例運籌學發(fā)展簡史2、早期研究《經濟表》——1758年一次大戰(zhàn)期間（1914.8~1918.11）的軍事運籌研究、蘭徹斯特的若干軍事論文·博弈論與投入產出——經濟平衡理論的基礎生產組織與計劃——《生產組織與計劃中的數學方法》康特洛維奇運籌學發(fā)展簡史3、形成與發(fā)展時期二戰(zhàn)中OR逐步形成獨立學科：歐戰(zhàn)中英國的“布萊克特雜技班”提高對敵船的沉擊率分析德國以V1導彈進攻倫敦的目的性盟軍對日作戰(zhàn)中最優(yōu)化投放魚雷的戰(zhàn)略研究軍事、經濟全面動員，促進OR各個分支的全面研究運籌學發(fā)展簡史戰(zhàn)后軍事活動分析轉向經濟發(fā)展47年單純形法研究成功，LP走向成熟，OR進入工業(yè)管理運籌學發(fā)展簡史50~60年代走向成熟標志：隊伍壯大，成立學會，創(chuàng)辦刊物，高校開課軍事運籌學面向未來要求大量理論成果問世，系統(tǒng)專著出版各個分支得到充實、完善運籌學發(fā)展簡史4、現代運籌學計算機的崛起使OR進入飛速發(fā)展期LP算法的研究帶動各個分支理論與方法的更大發(fā)展新領域新方法不斷萌發(fā)應用范圍更加廣泛運籌學發(fā)展簡史PART04走向成熟的運籌學1、各個分支充實完善形成體系確定性模型數學規(guī)劃線性規(guī)劃整數規(guī)劃非線性規(guī)劃動態(tài)規(guī)劃幾何規(guī)劃參數規(guī)劃多目標規(guī)劃組合優(yōu)化圖論與網絡分析優(yōu)選與統(tǒng)籌方法隨機性模型對策論排隊論（隨機服務系統(tǒng)）可靠性理論庫存論搜索論計算機隨機模擬決策論走向成熟的運籌學從整體優(yōu)化的角度出發(fā)，使用科學方法具有整體性觀點科學方法：使用的人員是一支綜合性隊伍研究解決問題的一般過程如下：走向成熟的運籌學提出界定問題確定問題構造OR模型問題導向適當選擇優(yōu)化求解過程模型求解進行解的評價檢查模型的有效性提供決策支持考察執(zhí)行情況走向成熟的運籌學

使用的數學方法——代數、分析、概率統(tǒng)計、組合分析、具有一定實驗性質的模擬方法，大量使用計算機與其他學科的交融滲透——計算機科學、行為科學、控制論、管理科學、系統(tǒng)分析與系統(tǒng)工程等

走向成熟的運籌學2.運籌學方法論1947年Dantzig提出單純形法50-56年LP對偶理論誕生1951年Kuhn-Tucker(庫恩-塔克)定理奠定非線性規(guī)劃理論基礎(將多個位移約束簡化為單一位移約束(稱為最臨界位移約束),建立位移約束下的優(yōu)化設計準則)1954年網絡流理論建立1955年創(chuàng)立隨機規(guī)劃1958年創(chuàng)立整數規(guī)劃及割平面解法1958年求解動態(tài)規(guī)劃的Bellman原理發(fā)表1960年Dantzig-Wolfe建立大LP分解算法走向成熟的運籌學3.大量理論成果問世4.日益廣泛的應用領域①運用分析理論——用于分配、選址、資源最佳利用、設備最佳運行等；②競爭理論——用于體育比賽、產品競爭、投標、宏觀金融博弈分析、經濟博弈等；③隨機服務理論——用于研究擁擠和排隊現象，如：電話呼喚、CPU運行和程序的排隊、防空武器系統(tǒng)的評價，計算機科學和技術及通訊網絡，供應鏈管理等。走向成熟的運籌學④前沿與熱點在“數字地球”的關鍵技術中尋求OR的切入點（大規(guī)模科學計算，海量存儲，高精度衛(wèi)星圖象，寬帶網，互操作）復雜巨系統(tǒng)與計算機模擬生物信息學中的OR方法DP引入生物分子序列比較，預測外顯子和內含子尋找基因、啟動子和序列對齊等隱藏統(tǒng)計規(guī)律的隱馬氏過程方法走向成熟的運籌學DNA分子生物計算機經濟博弈論與宏觀金融博弈分析現代物流與供應鏈管理現代優(yōu)化算法禁忌搜索模擬退火遺傳算法人工神經網絡模糊OR與隨機OR現代軍事OR走向成熟的運籌學平時訓練（紅藍軍對抗）醫(yī)療后送系統(tǒng)的計算機仿真計算機模擬軍事演習電子對抗（海灣戰(zhàn)爭中Karmarkar算法的運用）運籌學發(fā)展現代軍事運籌學PART05運籌學的影響運籌學的影響改善全世界大量組織的效率提高國家的經濟生產力促進商業(yè)運作的規(guī)范性節(jié)約大量稀有的資源為運籌與管理科學實踐者頒發(fā)的最負盛名的獎項是弗蘭茨·厄德曼(FranzEdelman)獎，該獎是全球運籌和管理科學界的最高工業(yè)應用獎，被廣泛譽為工業(yè)工程界的“諾貝爾”。自設立以來，英特爾、先正達、惠普、通用汽車、摩托羅拉等國際一流的科技企業(yè)，以及聯合國糧食計劃署等機構都曾榮膺過此獎項。2021年開始，弗蘭茲·厄德曼獎連續(xù)三年出現“中國面孔”，這也打破了該獎項四十余年的記錄。華為、阿里巴巴、聯想等中國科技企業(yè)都曾先后入圍。2023年1月18日，運籌學與管理科學學會（INFORMS）正式公布了2023年弗蘭茲·厄德曼獎（FranzEdelmanAward）最終入圍名單，全球共有六家企業(yè)獲得決賽資格。其中，華為、美團等進入六強名單，成為入圍決賽的中國科技企業(yè)代表。

運籌學的影響2021年，京東集團自主研發(fā)的無人倉調度算法應用最終入圍弗蘭茲·厄德曼獎名單?；诰〇|物流無人倉技術團隊的深入研究，該算法可以實現復雜的多智能體任務分配和路徑規(guī)劃，在毫秒內求解百億級復雜度的優(yōu)化問題并給出最優(yōu)解，最終形成規(guī)?；臋C器人調度系統(tǒng)。目前，在京東物流遍布全國的倉儲體系中，無人倉算法技術已成為“標配”，京東自營商品超500萬SKU，庫存周轉天數僅34天，無人倉算法為這一世界級水平數字的實現提供了重要技術支撐。基于數智化社會供應鏈，京東正與眾多合作伙伴推動中國社會化物流成本在十年內降至10%以內，比肩歐美等發(fā)達國家。運籌學的影響2022年，阿里巴巴供應鏈與運籌優(yōu)化技術憑借集成預測、庫存、價格推薦的優(yōu)化決策算法及其在新零售場景的實踐成果，成功闖入了總決賽六強。阿里巴巴已連續(xù)兩年（2021，2022）入圍弗蘭茲·厄德曼總決賽，是最近20年來唯一一家連續(xù)兩年入圍該獎項總決賽的公司，也是當年唯一入圍的中國公司，代表了中國在供應鏈技術和運籌科學應用中的杰出貢獻。運籌學的影響2023年，美團憑借智能決策分析平臺，一同入圍FranzEdelman獎決賽圈。它背后的技術、解決的問題，你我雖然感受不到，但在日常中都會用到。它背后的技術價值也是獎項最為重視的幾個方面。第一、有先進技術：美團基于高效路徑優(yōu)化算法和業(yè)內首創(chuàng)的城市級萬人萬單秒級匹配調度技術，可以實現在極其復雜環(huán)境下的高效調度。第二、有廣泛落地：美團每日即時訂單超過6000萬個，配送“智能決策平臺”已覆蓋至全國2800個城市。第三、帶來社會影響：如今美團已成為國民級應用，而“外賣買萬物”成為更多人的生活習慣，此前在疫情期間，美團還為保供需提供支持。運籌學的影響2023年，華為云憑借走在行業(yè)前列的云資源調度技術和優(yōu)異的市場表現入圍決賽六強。這是該獎項設立50余年來，全球首次有云計算公司憑借調度技術入圍。云資源利用率最優(yōu)且保證服務質量是業(yè)界公認的云資源調度難題，華為云在云資源調度技術上處于業(yè)界領先隊列，針對媒體網絡資源調度難題，通過一系列創(chuàng)新算法應對挑戰(zhàn)，實現媒體網絡利用率優(yōu)化超過30%；同時，提高了QoS服務質量，兩年內業(yè)務規(guī)模增長10倍。運籌學的影響PART06運籌學的應用倉儲物流中心選擇與物資運輸問題運籌學的應用劃分消防站片區(qū)劃分問題運籌學的應用排課問題?運籌學的應用外賣配送問題運籌學的應用理財與投資問題運籌學的應用人力資源管理與任務分配問題運籌學的應用PART07課程目的與要求通過講授、討論、平時作業(yè)、考試、課程設計(《運籌學實踐》)等教學環(huán)節(jié)&正確理解運籌學方法論，掌握運籌學整體優(yōu)化思想；&掌握線性規(guī)劃、整數規(guī)劃、動態(tài)規(guī)劃、網絡模型和非線性規(guī)劃等基本模型的功能和特點，熟悉其建模條件、步驟及相應的技巧，能根據實際背景抽象出適當的運籌學模型；課程目的與要求&熟練掌握各種模型特別是確定性模型的求解方法，并能對求解結果作簡單分析；&掌握與基本模型有關的基本概念及基本原理，做到思路清晰、概念明確；&接觸本領域的新發(fā)展，具有初步運用運籌學思想和方法分析、解決實際問題的能力和創(chuàng)新思維與應用的意識；課程目的與要求課堂講授與討論——啟發(fā)式、提問交流式、隨堂（或集中）討論式；作業(yè)；考核與成績（結構化記分方式）；閉卷考試

70%

平時作業(yè)

30%課程目的與要求教學內容

線性規(guī)劃整數規(guī)劃動態(tài)規(guī)劃圖與網絡分析非線性規(guī)劃（選講）課程目的與要求課程目的與要求要求和希望轉變觀念、加強溝通、相互配合、共同探索教與學的創(chuàng)新之路；放得開、坐得住、勤思考、多動手，努力把握邏輯思維和非邏輯思維相互緊密配合的思維藝術，培養(yǎng)自己的創(chuàng)造性思維；遵守紀律、排除干擾、勤奮踏實、積極實踐、提高效率。課程目的與要求幾點學習建議

1、制定一張嚴格的時間表，按課內外1：2的比例安排；2、充分發(fā)揮小組團隊學習作用，互幫互學,相互鼓勵與督促；3、留心處處皆學問，對于學習中的問題與靈感要隨時記錄、不斷積累；4、壓力促成長，堅持扎扎實實地獨立完成作業(yè)，積極參與小組討論，認真完成課程設計，你會體會到成功的喜悅和受益的歡樂。課程目的與要求只要耕耘，就會有收獲。祝大家學有所成，取得優(yōu)異成績！課程目的與要求JournalonComputing第一章線性規(guī)劃01線性規(guī)劃問題及其標準形式03線性規(guī)劃問題的單純形方法線性規(guī)劃問題的圖解法及其解的性質0204線性規(guī)劃問題的建模與應用CONTENTSPART01線性規(guī)劃問題及其標準形式線性規(guī)劃問題及其標準形式突發(fā)公共衛(wèi)生事件下的人員排班問題年初，某市出現了一場意想不到的大型傳染性疾病流行，城市的每個角落都籠罩著緊張和焦慮。衛(wèi)生健康部門迅速行動，緊急抽調醫(yī)護人員，組織轄區(qū)內所有居民進行呼吸道樣本采集以用于檢測，希望借此控制疫情的蔓延。為了充分利用有限的醫(yī)護人員資源與高效組織采集工作，衛(wèi)生健康部門經過精確計算，確定了周一到周日每天進行檢測所需的醫(yī)護人員數量分別為：300,300,450,450,500,700和650。線性規(guī)劃問題及其標準形式但是，在如此繁重的工作任務下，他們也深知醫(yī)護人員需要得到充分的休息才能保持身心健康和高效工作。因此，他們采取了排班制度，規(guī)定每周連續(xù)工作5天后必須休息2天，并且進行輪流休息的安排。然而，正當衛(wèi)生健康部門認為一切就緒時，他們卻面臨一個新的問題：如何安排每天值班的醫(yī)護人員人數，使得其既能滿足醫(yī)療工作需求，又盡量減少醫(yī)護人員之間的流動，從而降低感染風險呢？一、線性規(guī)劃問題的導出現實社會活動中，常常遇到兩類問題：若要以最少的資源消耗來完成一項確定的任務，如何統(tǒng)籌安排？—如何使成本最??！在既定資源條件下，如何配置它們，能使完成的任務量最大？—如何使效益最大！線性規(guī)劃問題及其標準形式引例1—配比問題

用濃度為45％和92％的硫酸配置100噸濃度為80％的硫酸。取45％和92％的硫酸分別為x1噸和x2噸，則有：求解二元一次方程組，得解。兩個未知數兩個方程線性規(guī)劃問題及其標準形式

如果目的相同，但若有5種不同濃度的硫酸可選（30％，45％，73％，85％，92％）會出現什么情況呢？取這5種硫酸分別為x1,x2,x3,x4,x5噸，則

問：（1）有多少種配比方案？為什么？（2）何為最好？（最優(yōu)的標準是什么？）5個未知數兩個方程線性規(guī)劃問題及其標準形式5種硫酸價格分別為：400，700，1400，1900，2500元／噸，則有：觀察：目標函數和約束條件有什么特點？目標函數是線性的；約束條件是線性的；為什么叫線性規(guī)劃？線性規(guī)劃問題及其標準形式引例2—生產計劃問題某工廠生產A、B、C三種產品，每噸利潤分別為2000元，3000元，3000元。生產單位產品所需要的工時及原材料如表1－1所示。若供應的原材料每天不超過9噸，所能利用的勞動力日總工時為3個單位。問：如何制定日生產計劃，使三種產品總利潤最大？線性規(guī)劃問題及其標準形式線性規(guī)劃問題及其標準形式線性規(guī)劃問題及其標準形式如何制定生產計劃，使三種產品總利潤最大？何為生產計劃？總利潤如何描述？還要考慮什么因素？有什么需要注意的地方（技巧）？最終得到的數學模型是什么？問題討論線性規(guī)劃問題及其標準形式引例3-偉恩德公司案例—產品組合問題偉恩德公司總裁約翰·希爾對杰姆小組開發(fā)的兩種新產品很有信心，一種是8英尺的鋁框玻璃門，另一種是4英尺×6英尺的雙把木框窗。公司有三個工廠，玻璃門需要工廠1和工廠3的生產能力，木框窗需要工廠2和工廠3的生產能力。已知工廠加工兩種新產品需要的工時數據和預測的單位利潤。線性規(guī)劃問題及其標準形式線性規(guī)劃問題及其標準形式管理部門需要考慮：1）公司是否應該生產這兩種新產品？2）如果生產，兩種新產品的生產組合如何？每周分別生產多少數量？線性規(guī)劃問題及其標準形式偉恩德公司產品組合問題的數據線性規(guī)劃問題及其標準形式需要回答的三個問題：1）要做出的決策是什么？2）在做出這些決策上有哪些約束條件？3）這些決策的全部績效測度是什么？1）要做的決策是兩種產品的生產率（每周生產多少）2）對決策的約束條件是兩種產品在相應工廠里每周生產時間不能超過每個工廠可得到的生產時間。3）對這些決策的全部績效測度是這兩種產品的總利潤。線性規(guī)劃問題及其標準形式設兩種產品每周分別生產x1件和x2件。目標函數：總利潤最大約束條件：兩種產品在相應工廠里每周生產時間不能超過每個工廠可得到的生產時間。引例4-利博公司廣告組合問題

利博(Profit&Gambit)公司生產家用的清潔產品，這是一個高度競爭的市場，公司為了增加市場份額連續(xù)掙扎多年。管理層決定集中在下列三個主要產品上實行一個大規(guī)模的新的廣告運動。一種噴霧去污劑一種新的液體洗滌劑一種成熟的洗衣粉線性規(guī)劃問題及其標準形式線性規(guī)劃問題及其標準形式這一廣告運動會采用電視和印刷媒體。一個商業(yè)廣告已經形成，要在全國的電視上做液體洗滌劑的廣告來幫助推出這一產品。印刷媒體的廣告將用來促銷所有三種產品，包括消費者可用來以低價購買產品的象征性優(yōu)惠券。管理部門已經設定了廣告運動的最低目標：(1)噴霧去污劑必須再增加3％的市場份額；(2)新的液體洗滌劑必須在洗滌劑市場上獲得18％的份額；(3)洗衣粉占洗滌劑市場的份額必須增加4％。線性規(guī)劃問題及其標準形式上表顯示了在各自的媒體上做一單位廣告的相應產品市場份額的估計增加額。（一個單位是指利博公司通常采用的一個廣告標準批量，但其他數量也是允許的。）在電視一列中洗衣粉的增加份額為－1％的原因是新的液體洗滌劑的電視商業(yè)廣告會帶走一些洗衣粉的銷售額。表中最后一行顯示了兩種媒體中每一種媒體上做廣告的單位成本。

管理部門的任務是：若要以最低的總成本達到市場份額的目標要求，那么在每種媒體上做多少錢的廣告？線性規(guī)劃問題及其標準形式若用百分數，就都用百分數；否則，就兩邊同乘100。數學模型線性規(guī)劃問題及其標準形式對于求取一組變量，使之既滿足線性約束條件，又使具有線性表達式的目標函數取得極大值或極小值的一類最優(yōu)化問題稱為線性規(guī)劃問題，簡稱線性規(guī)劃（LinearProgramming）。1.線性規(guī)劃的定義與數學描述（模型）線性規(guī)劃問題及其標準形式對決策變量有非負要求。用一組未知變量表示要求的方案，這組未知變量稱為決策變量；存在一定的限制條件，且為線性表達式，叫約束條件；有一個目標要求（最大化／最小化），目標表示為未知變量的線性表達式，稱之為目標函數；2.引例中線性規(guī)劃模型的特點：3.線性規(guī)劃的數學描述（數學模型）（1）一般形式：線性規(guī)劃問題及其標準形式目標函數？價值系數？約束條件？技術系數？限額系數？線性規(guī)劃問題及其標準形式模型的參數是數學模型中的常數。決策變量的任何一個取值稱為模型的一個解。滿足所有約束條件的解稱為可行解。反之，一個非可行解至少違反一個約束條件。全部可行解的集合稱為可行域。使目標函數達到最大值的可行解稱為最優(yōu)解。該目標函數值為最優(yōu)值。線性規(guī)劃問題及其標準形式一般情況下，m<n.模型隱含的假設：比例性：每種經營活動對目標函數的貢獻和對資源的消耗是一個常數(不存在邊際效用遞減效用)。可加性：決策變量是相互獨立的，決策變量之間不發(fā)生關聯，不允許變量之間的交叉。連續(xù)性：決策變量應取連續(xù)值。確定性：所有參數是確定的，不包含不確定因素。（2）緊縮形式線性規(guī)劃問題及其標準形式（3）矩陣形式其中:線性規(guī)劃問題及其標準形式（4）向量—矩陣形式：其中：線性規(guī)劃問題及其標準形式線性規(guī)劃問題及其標準形式1、LP標準型的概念（1）什么是LP的標準型？（2）LP標準型的特點？目標函數約定是極大化Max(或極小化Min；約束條件均用等式表示；決策變量限于取非負值；右端常數均為非負值；線性規(guī)劃問題及其標準形式（3）數學表達式:

有幾種形式?為什么?如何書寫?2.LP問題的標準化（1）目標函數的標準化

線性規(guī)劃問題及其標準形式目標函數標準化示意圖線性規(guī)劃問題及其標準形式（2）約束條件的標準化約束條件是“≤”類型——左邊加

非負松弛變量，變?yōu)榈仁剑患s束條件是“≥”類型——左邊減

非負松弛變量，變?yōu)榈仁?；變量符號不限——引入新變量線性規(guī)劃問題及其標準形式將下面的線性規(guī)劃問題化為標準型：討論：

如何下手？標準化過程排序

-------課堂練習1-2線性規(guī)劃問題及其標準形式課堂練習1-2

提問、答疑、討論

總結，看最終結果線性規(guī)劃問題及其標準形式線性規(guī)劃問題及其標準形式注釋一：線性規(guī)劃問題的標準形式是與原始形式等價的，即一個線性規(guī)劃問題的最優(yōu)解與其標準形式的最優(yōu)解的值應該是一樣的。一個問題的標準形式并不改變問題的本質，它只是改變對問題約束條件的寫法。Matlab,LINDO與LINGO等中關于線性規(guī)劃問題的結論顯示就是這類標準化形式。線性規(guī)劃問題及其標準形式注釋二：在標準型中，松弛變量的系數為零，表示松弛變量是未使用的資源，不對目標函數產生任何影響。但是在實際問題中，可以出售未使用的資源，以使公司獲得利潤。在此情形下，松弛變量就變成表示公司可以出售多少未使用資源的決策變量?？尚薪猓簼M足約束條件和非負條件的決策變量的一組取值。最優(yōu)解：使目標函數達到最優(yōu)值的可行解。基本解：設AX=b是含n個決策變量、m個約束條件的LP的約束方程組，B是LP問題的一個基，若令不與B的列相應的n-m個分量（非基變量）都等于零，所得的方程組的解稱為方程組AX=b關于基B的基本解，簡稱為LP的基本解。B

對應的決策變量

令非基變量取值為零，計算出基變量取值，兩者搭配構成基本解。線性規(guī)劃問題解的概念和性質4.基本可行解（對應的基為可行基）：滿足非負條件的基本解。

5.基本最優(yōu)解（對應的基為最優(yōu)基）：使目標函數達到最優(yōu)值的基本可行解。最優(yōu)解基本最優(yōu)解線性規(guī)劃問題解的概念和性質基解與基可行解有如下性質：每一個變量是非基變量或基變量，二者必居其一?；兞總€數等于方程之個數。令非基變量為0，同時由方程組的右端項系數得到基變量之值。若基變量滿足非負性約束，則基解就是一個基可行解。線性規(guī)劃問題解的概念和性質用畫圖、模型制作、三維動畫等方法清楚地顯示其可行解、基本解、基本可行解。進一步具體計算出這些解來，說明它們之間的關系。課后小組討論1研究約束集合線性規(guī)劃問題解的概念和性質PART02線性規(guī)劃問題的圖解法與解的性質線性規(guī)劃問題的圖解法（解的幾何表示）1．什么是圖解法？線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過程。求解思路是：先將約束條件加以圖解，求得滿足約束條件的解的幾何區(qū)域（可行域），然后結合目標函數的要求從可行域中找出最優(yōu)解。

線性規(guī)劃問題的圖解法（解的幾何表示）1．圖解法舉例

實施圖解法，以求出最優(yōu)生產計劃（最優(yōu)解）。線性規(guī)劃問題的圖解法（解的幾何表示）由于線性規(guī)劃模型中只有兩個決策變量，因此只需建立平面直角坐標系就可進行圖解了

線性規(guī)劃問題的圖解法（解的幾何表示）約束條件的圖解：

每一個約束不等式在平面直角坐標系中都代表一個半平面，只要先畫出該半平面的邊界，然后確定是哪個半平面。

?

怎么畫邊界

怎么確定半平面線性規(guī)劃問題的圖解法（解的幾何表示）如果全部的勞動工時都用來生產A產品而不生產B產品，那么A產品的最大可能產量為3噸，計算過程為：

這個結果對應著右圖中的點A(3,0)，同樣我們可以找到B產品最大可能生產量對應的點B(0,3)。連接A、B兩點得到約束：

所代表的半平面的邊界:

即直線AB。線性規(guī)劃問題的圖解法（解的幾何表示）第二個約束條件的邊界---直線CD:

線性規(guī)劃問題的圖解法（解的幾何表示）

線性規(guī)劃問題的圖解法（解的幾何表示）

線性規(guī)劃問題的圖解法（解的幾何表示）

線性規(guī)劃問題的圖解法（解的幾何表示）0123456789x1

54321x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）

線性規(guī)劃問題的圖解法0123456789x1

321x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）

無窮多個最優(yōu)解線性規(guī)劃問題的圖解法0123456789x1

321x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）

無窮多個最優(yōu)解線性規(guī)劃問題的圖解法

唯一最優(yōu)解0123456789x1x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）線性規(guī)劃問題的圖解法例1-3：無界解

線性規(guī)劃問題的圖解法本例中的可行域是一個無界區(qū)域，如圖中陰影區(qū)所示。虛線為目函數等值線，沿著箭頭所指的方向平移可以使目標函數值無限制地增大，因此找不到最優(yōu)解。這種情況通常稱為無“有限最優(yōu)解”或“最優(yōu)解無界”。如果一個實際問題抽象成像例4這樣的線性規(guī)劃模型，比如是一個生產計劃問題，其經濟含義就是某些資源是無限的，產品的產量可以無限大，解釋不合理。此時應重新檢查和修改模型，否則就沒有實際意義。無界解

線性規(guī)劃問題的圖解法無界解和無可行解統(tǒng)稱為無最優(yōu)解產生無界解的原因是遺漏了約束條件。改變目標函數可能會使一個無界問題變成一個有界問題。(缺乏必要的約束條件)無可行解同目標函數無關，是因為約束條件太苛刻。（矛盾的約束條件）注釋：線性規(guī)劃問題的圖解法綜上，用圖解法求解線性規(guī)劃時，各種求解結果與各種類型的可行域之間的對應關系可以用下圖加以描述：解的類型可行域類型唯一最優(yōu)解非空有界無窮多最優(yōu)解最優(yōu)解無界（無“有限最優(yōu)解”）無界無解（不存在可行域）空集線性規(guī)劃問題的圖解法注釋線性規(guī)劃問題的可行域非空時，它是有界或無界凸多變形。若線性規(guī)劃問題存在最優(yōu)解，它一定在可行域的某個頂點得到。若在兩個頂點同時得到最優(yōu)解，則它們連線上的任意一點都是最優(yōu)解，即無窮多最優(yōu)解。線性規(guī)劃問題的圖解法

線性規(guī)劃問題的圖解法

線性規(guī)劃問題的圖解法圖解法小結使用條件：僅有兩個至多不超過三個決策變量的線性規(guī)劃?；静襟E：第一步---建立平面直角坐標系；第二步---根據約束條件和非負條件畫出可行域。第三步---作出目標函數等值線（至少兩條），結合目標函數優(yōu)化要求，平移目標函數等值線求出最優(yōu)解。圖解法的優(yōu)缺點：簡單、直觀但有局限性。圖解法求解線性規(guī)劃圖解法的局限性(1)圖解法的優(yōu)點:簡單、直觀;(2)局限性:對僅含有兩個至多不超過三個決策變量的線性規(guī)劃才適于使用圖解法，大多數情況下僅對含有兩個決策變量的線性規(guī)劃才使用圖解法求解;(3)對含有三個以及三個以上決策變量的線性規(guī)劃則應考慮使用更加有效的通用算法——單純形法來進行求解。

線性規(guī)劃問題的圖解法用圖解法求解以下的線性規(guī)劃問題：課堂練習按小組分工完成：①畫約束條件1,2；②畫約束條件3并標明可行域；③畫目標函數等值線；④說明如何得到最優(yōu)解,算出相應的目標函數最優(yōu)值。其他小組進行講評。線性規(guī)劃問題的圖解法課堂練習(2,2)

12345x1X2

543210

C=2C=10線性規(guī)劃問題的圖解法

12345x1X2543210(2,2)

C=2C=10I(4,0)E(0,-2)H(6,4)G(0,4)F(-2,0)2.1基本可行解的幾何意義1、討論課堂練習

（1）如何求得基本解？

（2）觀察圖解法求解圖，其中點I、H、G均在第一象限，它們是基本解，但不是基本可行解，這與基本可行解非負性有無矛盾？

基本可行解的幾何意義

基本可行解的幾何意義求解結果：H(6,4,-6,0,0)T,C(3,1,0,3,0)T,

B(2,2,0,0,2)T,D(2,0,2,4,0)T,

F(-2,0,6,0,4)T,I(4,0,0,6,-2)T,

E(0,-2,6,6,0)T,A(0,1,3,0,3)T,

G(0,4,0,-8,6)T,O(0,0,4,2,2)T;基本可行解的幾何意義2、結論：

(1)基本解對應所有可行域邊界及其延長線、坐標軸之間的交點；

(2)基本可行解對應可行域的頂點。線性規(guī)劃解的性質

線性規(guī)劃解的性質

線性規(guī)劃解的性質2、線性規(guī)劃問題解的性質定理：

線性規(guī)劃解的性質

X是D的一個頂點<=>X的正分量所對應的系數列向量線性無關線性規(guī)劃解的性質

線性規(guī)劃解的性質（2）定理1-2（反證法）

線性規(guī)劃解的性質

線性規(guī)劃解的性質（2）定理1-2（反證法）

線性規(guī)劃解的性質定理1-3若可行域非空有界，則線性規(guī)劃問題的目標函數一定可以在可行域的頂點上達到最優(yōu)值。

線性規(guī)劃解的性質

線性規(guī)劃解的性質

線性規(guī)劃解的性質

線性規(guī)劃解的性質課后討論：（1）讀懂證明，理清思路，寫出從最羅嗦的證明過渡到最簡潔的證明過程（加上邊注——段落大意）線性規(guī)劃解的性質

LP的可行域一定是凸集，但是凸集不一定成為LP的可行域，而非凸集一定不會是LP的可行域。（為什么？能舉例說明嗎？）線性規(guī)劃的基本可行解和可行域的頂點是一一對應的（類似于坐標與點的對應關系?。┰诳尚杏蛑袑ふ襆P的最優(yōu)解可以轉化為只在可行域的頂點中找，從而把一個無限的問題轉化為一個有限的問題。若已知一個LP有兩個或兩個以上最優(yōu)解，那么就一定有無窮多個最優(yōu)解。PART03單純形法單純形法圖解法的局限性？

1947年G.B.Dantzig提出的單純形法提供了方便、有效的通用算法求解線性規(guī)劃。單純形法1、頂點的逐步轉移即從可行域的一個頂點（基本可行解）開始，轉移到另一個頂點（另一個基本可行解）的迭代過程，轉移的條件是使目標函數值得到改善（逐步變優(yōu)），當目標函數達到最優(yōu)值時，問題也就得到了最優(yōu)解。一、單純形法的基本思想單純形法單純形法2、頂點轉移的依據？根據線性規(guī)劃問題的可行域是凸多邊形或凸多面體，一個線性規(guī)劃問題有最優(yōu)解，就一定可以在可行域的頂點上找到。因此，若某線性規(guī)劃只有唯一的一個最優(yōu)解，這個最優(yōu)解所對應的點一定是可行域的頂點；若該線性規(guī)劃有多個最優(yōu)解，那么肯定在可行域的頂點中可以找到至少一個最優(yōu)解。單純形法

3.轉移條件？4.轉移結果？使目標函數值得到改善得到LP最優(yōu)解，目標函數達到最優(yōu)值（單純形法的由來？）

單純形法5.單純形算法要解決的四個問題：（1）找到一個初始的基本可行解，使迭代開始；（2）如何判斷一個基本可行解是否為最優(yōu)解？判斷準則是什么？（3）如果不是最優(yōu)解，怎樣找到下一個基本可行解（始終保持基的可行性），同時使目標函數取值得到改善（更大或更?。浚?）如何判斷是否沒有有限最優(yōu)解？單純形法二、單純形法原理

（原材料約束）

（勞動力約束）例1-5單純形法第一步：引入非負的松弛變量x4,x5,將該LP化為標準型單純形法第二步：尋求初始可行基，確定基變量

第三步：寫出初始基本可行解和相應的目標函數值單純形法兩個關鍵的基本表達式：①用非基變量表示基變量的表達式單純形法②用非基變量表示目標函數的表達式請解釋結果的經濟含義——不生產任何產品，資源全部節(jié)余（x4=3，x5=9），三種產品的總利潤為0！

單純形法第四步：分析兩個基本表達式，看看目標函數是否可以改善？①分析用非基變量表示目標函數的表達式

非基變量前面的系數均為正數，所以任何一個非基變量進基都能使Z值增加通常把非基變量前面的系數叫“檢驗數”；單純形法②選哪一個非基變量進基？

選x1為進基變量（換入變量）問題討論：能否選其他的非基變量進基？

任意一個

任意一個正檢驗數對應的非基變量

最大正檢驗數對應的非基變量

排在最前面的正檢驗數對應的非基變量×

單純形法③確定出基變量：問題討論

單純形法用非基變量表示基變量的表達式

當x1增加時，x4，x5會減小，但有限度——必須大于等于0，以保持解的可行性！于是單純形法

當x1的值從0增加到3時，x4首先變?yōu)?，此時x5=6>0因此選x4為出基變量（換出變量）。這種用來確定出基變量的規(guī)則稱為“最小比值原則”（或θ原則）。如果P1≤0，會出現什么問題？

最小比值原則會失效！單純形法

基變換新的基變量——x1,x5；新的非基變量x2,x3,x4；寫出用非基變量表示基變量的表達式：

由→單純形法⑤寫出用非基變量表示目標函數的表達式:可得相應的目標函數值為Z（1）=6檢驗數仍有正的返回①進行討論。單純形法第五步：上述過程何時停止？——分析用非基變量表示目標函數的表達式，如果讓負檢驗數所對應的變量進基，目標函數值將下降！當用非基變量表示目標函數的表達式中，非基變量的系數（檢驗數）全部非正時，當前的基本可行解就是最優(yōu)解!

為什么？三、表格單純形法：1、

初始單純形表的建立

(1)表格結構：

單純形法（2）表格設計依據：

將-Z看作不參與基變換的基變量，把目標函數表達式改寫成方程的形式，和原有的m個約束方程組成一個具有n+m+1個變量、m+1個方程的方程組：單純形法取出系數寫成增廣矩陣的形式：

-ZX1X2…XnXn+1Xn+2…Xn+mb-Z，Xn+1，…，Xn+m所對應的系數列向量構成一個基單純形法用矩陣的初等行變換將該基變成單位陣,這時

變成0，相應的增廣矩陣變成如下形式：

單純形法（3）檢驗數的兩種計算方法：①利用矩陣的行變換，把目標函數表達式中基變量前面的系數變?yōu)?；②使用計算公式——

增廣矩陣的最后一行就是用非基變量表示目標函數的表達式,(j=1,2,…,n)就是非基變量的檢驗數。單純形法2、例1-5的表格單純形法計算過程：2330003111103/109147019/102330023111103/106036-116/3-6011-202110-14/3-1/332012-1/31/3-800-1-5/3-1/3

單純形法

單純形法四、單純形法的一般描述：1、

初始可行解的確定

(1)初始可行基的確定

觀察法——觀察系數矩陣中是否含有現成的單位陣？

LP限制條件中全部是“≤”類型的約束

——將新增的松弛變量作為初始基變量，對應的系數列向量構成單位陣；單純形法

先將約束條件標準化，再引入非負的人工變量，以人工變量作為初始基變量，其對應的系數列向量構成單位陣，稱為“人造基”；然后用大M法或兩階段法求解；

線性規(guī)劃限制條件都是“≥”或“=”類型的約束——單純形法等式約束左端引入人工變量的目的使約束方程的系數矩陣中出現一個單位陣，用單位陣的每一個列向量對應的決策變量作為“基變量”，這樣，出現在單純形表格中的B(i)列（即約束方程的右邊常數）值正好就是基變量的取值。（注意：用非基變量表示基變量的表達式）單純形法①如果限制條件中既有“≤”類型的約束，又有“≥”或“=”類型的約束，怎么辦？構造“不完全的人造基”！

討論②為什么初始可行基一定要選單位陣？b列正好就是基變量的取值，檢驗數行和b列交叉處元素也正好對應目標函數值，因此稱b列為解答列單純形法（2）寫出初始基本可行解——

根據“用非基變量表示基變量的表達式”，非基變量取0，算出基變量，搭配在一起構成初始基本可行解。

2、建立判別準則：（1）兩個基本表達式的一般形式就LP限制條件中全部是“≤”類型約束，新增的松弛變量作為初始基變量的情況來描述：單純形法此時LP的標準型為單純形法初始可行基：初始基本可行解：

單純形法

一般（經過若干次迭代），對于基B，用非基變量表出基變量的表達式為：用非基變量表示目標函數的表達式：

單純形法單純形法

（2）最優(yōu)性判別定理（3）無“有限最優(yōu)解”的判別定理

單純形法證明思路——構造性證明：依據用非基變量表示基變量的表達式構造一族可行解，其對應的目標函數值趨于無窮大。幾何意義：沿著無界邊界前進的一族可行解單純形法舉例：用非基變量表示基變量的表達式

代表兩個約束條件：x2對應的系數列向量P2=（1，3）T，當前的換入變量是

X2，按最小比值原則確定換出變量：單純形法要求：

于是：

如果x2的系數列變成P2’=（-1，0）T,則用非基變量表示基變量的表達式就變成；

可行性自然滿足,最小比值原則失效,意即x2的值可以任意增大→原線性規(guī)劃無“有限最優(yōu)解”。單純形法3、進行基變換（1）選擇進基變量——原則：正檢驗數（或最大正檢驗數）所對應的變量進基，目的是使目標函數得到改善（較快增大）；

進基變量對應的系數列稱為主元列。（2）出基變量的確定——按最小比值原則確定出基變量，為的是保持解的可行性；

出基變量所在的行稱為主元行。主元行和主元列的交叉元素稱為主元素。單純形法思考題

這樣進行基變換后得到的新解對應的系數列向量是否線性獨立？

4、主元變換（旋轉運算或樞運算）

按照主元素進行矩陣的初等行變換——把主元素變成1，主元列的其他元素變成0（即主元列變?yōu)閱挝幌蛄浚懗鲂碌幕究尚薪?，返回最?yōu)性檢驗。單純形法單純形法小結

求解思想－－

頂點的逐步轉移，

條件是使目標函數值不斷得到改善。單純形法表格單純形法求解步驟第一步：將LP化為標準型，并加以整理。引入適當的松馳變量、剩余變量和人工變量，使約束條件化為等式，并且約束方程組的系數陣中有一個單位陣。（這一步計算機可自動完成）

確定初始可行基，寫出初始基本可行解單純形法第二步：最優(yōu)性檢驗計算檢驗數，檢查：所有檢驗數是否≤0？

是——結束，寫出最優(yōu)解和目標函數最優(yōu)值；還有正檢驗數——檢查相應系數列≤

0？是——結束，該LP無“有限最優(yōu)解”！不屬于上述兩種情況，轉入下一步—基變換。確定是停止迭代還是轉入基變換？單純形法選擇（最大）正檢驗數對應的系數列為主元列，主元列對應的非基變量為換入變量；最小比值對應的行為主元行，主元行對應的基變量為換出變量。第三步：基變換確定進基變量和出基變量。單純形法

利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?，進基變量對應的檢驗數變成0，從而得到一張新的單純形表，返回第二步。第四步換基迭代（旋轉運算、樞運算)完成一次迭代，得到新的基本可行解和相應的目標函數值單純形法該迭代過程直至下列情況之一發(fā)生時停止

檢驗數行全部變?yōu)榉钦担唬ǖ玫阶顑?yōu)解）或主元列≤

0（最優(yōu)解無界）

停止迭代的標志（停機準則）

依據：最優(yōu)性檢驗的兩個定理最優(yōu)性判別定理；無“有限最優(yōu)解”判斷定理單純形法幾種特殊解的情形單純形法1.退化解在線性規(guī)劃中，當單純形表中的基本可行解中出現一個或多個基變量等于零，或者在確定換出基變量時存在兩個以上相同最小比值的情況，便稱為退化，退化問題的最優(yōu)解被稱為退化解。這種情況通常是由于模型中存在多余的約束，導致多個基本可行解對應同一頂點。退化解的出現可能會導致單純形法陷入循環(huán)，使得算法進展緩慢甚至無法繼續(xù)進行。單純形法1.退化解利用單純形法求解以上線性規(guī)劃問題得到的單純性表如下：單純形法

32000基基b084-1100201243010308410012032000

321-0.250.25001010-6023.50-2

084-1100201243010308410012032000

我們可以注意到，在迭代過程中出現了基變量為0的情況，進行了多次迭代，而基從B1，B2又返回到B1，即出現計算過程的循環(huán)，此時便出現了退化現象。單純形法2.無窮多最優(yōu)解線性規(guī)劃問題的最優(yōu)解有可能并非唯一，如果存在多個基本可行解（即不同的頂點）具有相同的最優(yōu)目標函數值，則可以推斷該線性規(guī)劃問題存在無窮多個最優(yōu)解。單純形法

5050000基b50501010-105000-2115025001001-1500000-5000

單純形法

5050000基b5010010-11005000-21150200012-10-1500000-5000單純形法由此我們可以推得，存在無窮多最優(yōu)解的判定條件是最終單純性表中的某個非基變量的檢驗數為0。但是需要注意的是，這只是一個必要條件而非充要條件，由最終單純性表中的某個非基變量的檢驗數為0并不能推得線性規(guī)劃問題存在無窮多最優(yōu)解，因為也可能存在兩個不同的最優(yōu)基可行解對應同一個頂點的情況，此時線性規(guī)劃的最優(yōu)解仍然是唯一的。PART04線性規(guī)劃的應用線性規(guī)劃的應用一、使用線性規(guī)劃方法處理實際問題必須具備的條件

(建模條件)：1、優(yōu)化條件---問題的目標有極大化或極小化的要求,而且能用決策變量的線性函數來表示。2、選擇條件---有多種可供選擇的可行方案，以便從中選取最優(yōu)方案。3、限制條件---達到目標的條件是有一定限制的（比如，資源的供應量有限度等），而且這些限制可以用決策變量的線性等式或線性不等式表示出來。此外，描述問題的決策變量相互之間應有一定的聯系，有可能建立數學關系，即這些變量之間是內部相關的。線性規(guī)劃的應用二、建模步驟：

第一步：設置要求解的決策變量。決策變量選取得當，不僅能順利地建立模型而且能方便地求解，否則很可能事倍功半。

第二步：找出所有的限制，即約束條件，并用決策變量的線性方程或線性不等式來表示。當限制條件多，背景比較復雜時，可以采用圖示或表格形式列出所有的已知數據和信息，以避免“遺漏”或“重復”所造成的錯誤。

第三步：明確目標要求，并用決策變量的線性函數來表示，確定對函數是取極大還是取極小的要求。決策變量的非負要求可以根據問題的實際意義加以確定。

討論：這三步的順序可以顛倒嗎？

為什么？線性規(guī)劃的應用

三、經濟管理領域中幾類典型的LP問題

經濟管理領域中有大量的實際問題可以歸結為線性規(guī)劃問題來研究，這些問題背景不同，表現各異，但數學模型卻有著完全相同的形式。盡可能多地掌握一些典型的模型不僅有助于深刻理解線性規(guī)劃本身的理論和方法，而且有利于靈活地處理千差萬別的實際問題，提高解決實際問題的能力。線性規(guī)劃的應用（一）

生產組織與計劃問題1.

產品計劃問題2.

產品配套問題線性規(guī)劃的應用1、產品計劃問題

問題的一般提法：用若干種原材料（資源）生產某幾種產品，原材料（或資源）供應有一定限制，要求制定一個產品生產計劃，使其在一定數量的資源限制條件下能得到最大的收益。線性規(guī)劃的應用

如果用，

單位產品所需資源數（如原材料、人力、時間等）、所得利潤及可供應的資源總量已知，如表所示，問應如何組織生產才能使利潤最大？線性規(guī)劃的應用線性規(guī)劃的應用設出產品的計劃數，可列出這類問題的數學模型如下：

線性規(guī)劃的應用一般的產品計劃問題舉例

例1-7某工廠生產A、B兩種產品，均需經過兩道工序，每生產一噸產品A需要經第一道工序加工2小時，第二道工序加工3小時；每生產一噸產品B需要經第一道工序加工3小時，第二道工序加工4小時?？晒├玫牡谝坏拦ば驗?2小時，第二道工序為24小時。生產產品B的同時產出副產品C，每生產一噸產品B，可同時得到2噸產品C而毋需外加任何費用；副產品C一部分可以盈利，剩下的只能報廢。出售產品A每噸能盈利400元、產品B每噸能盈利1000元，每銷售一噸副產品C能盈利300元，而剩余要報廢的則每噸損失200元。經市場預測，在計劃期內產品C最大銷量為5噸。試列出線性規(guī)劃模型，決定A、B兩種產品的產量，使工廠總的利潤最大。線性規(guī)劃的應用

信息整理：線性規(guī)劃的應用線性規(guī)劃的應用數學模型：設：x1——產品A的產量，x2——產品B的產量，x3——產品C的銷售量，x4——產品C的報廢量。依題意，可得線性規(guī)劃的應用2、產品配套問題

例1-8

某產品由兩個零件I和三個零件II組成，每個零件均可由三個車間各自生產，但各車間的生產效率和總工時限制各不相同，表中給出了有關信息。試確定各車間生產每種零件的工作時間，使生產產品的件數最多。

線性規(guī)劃的應用線性規(guī)劃的應用例1-8有關信息表處理：線性規(guī)劃的應用于是得到該問題的LP模型為：線性規(guī)劃的應用

(二)

合理下料問題在加工業(yè)中，經常遇到這類問題。

問題的一般提法是：已知某種尺寸的棒料或板材，需要將其切割成一定數量既定規(guī)格的幾種零件毛坯，問應如何選取合理的下料方法，使得既滿足對截出毛坯的數量要求，又使所用的原材料最少（或廢料最少）？線性規(guī)劃的應用解決這類問題一般有兩個步驟：

步驟一、按照一定的思路設法列出所有的排料方案（也稱下料方案或排料圖），當方案很多，甚至無法一一列出時，通常應先確定一些篩選原則，把明顯不合理的方案刪除，僅僅考慮剩余的為數不太多的方案；步驟二、設xi表示按第ｉ種方案下料的棒料根數（或板材塊數）i=1,2,…,n，按照問題的要求建立LP模型。線性規(guī)劃的應用例1-9

某廠接受了一批加工定貨，客戶要求加工100套鋼架，每套由長2.9米、2.1米和1.5米的圓鋼各一根組成?，F在僅有一批長7.4米的棒料毛坯，問應如何下料，使所用的棒料根數最少？線性規(guī)劃的應用

最簡單的處理方法：從一根棒料上截取2.9米、2.1米和1.5米的棒料各一根，正好配成一套鋼架，100套鋼架總共需要100根棒料毛坯。每根棒料毛坯剩下0.9米的料頭,100根毛坯總共剩90米料頭。

——這是最好的辦法嗎？合理套裁肯定會有更好的效果。先設法列出所有的下料方案，思路如圖。線性規(guī)劃的應用排列下料方案思路圖

線性規(guī)劃的應用

設xi為按第i種方案下料的棒料根數，建立LP模型如下：線性規(guī)劃的應用

（三）

合理配料問題

問題的一般提法：由多種原料配置成含有m種成分的產品，已知產品中所含各成分的需要量及每種原料的價格，同時知道各種原料中所含m種成分的數量，要求給出使產品成本最低的配料方案。如：伙食問題（也稱營養(yǎng)問題）、飼料配比問題、化工產品中的混合問題等都屬于這類問題。

線性規(guī)劃的應用例1-10營養(yǎng)問題

要求制定既經濟又合乎健康標準的食譜。一個簡單的例子：現準備采購甲、乙兩種食品，表中給出了已知價格及相關的營養(yǎng)成分。最右欄給出了按營養(yǎng)學標準每人每天的最低需要量。問應如何采購食品才能在保證營養(yǎng)要求的前提下花費最?。烤€性規(guī)劃的應用

營養(yǎng)問題已知數據表線性規(guī)劃的應用

線性規(guī)劃的應用

營養(yǎng)問題適用范圍：

&

運動員集訓隊食譜設計；

&

幼兒園、醫(yī)院等特殊群體的營養(yǎng)配餐；

&

機關、學校、企業(yè)等企事業(yè)單位團體伙食設計；

&家庭食譜設計；線性規(guī)劃的應用

對不同對象的營養(yǎng)要求——從營養(yǎng)學資料和通過醫(yī)生咨詢得到；

各種食品的價格——通過不同季節(jié)的市場調查獲?。?/p>

一些特殊要求，比如飲食習慣、偏好等——可通過適當處理，轉化為約束條件加入模型；資料獲取渠道及特殊要求的處理建議：線性規(guī)劃的應用

例1-11（飼料配比問題）某配合飼料廠生產以雞飼料為主的配合飼料，現準備研制一種新的肉用仔雞專用飼料，所用原料的營養(yǎng)成分和飼養(yǎng)標準見下表，希望這種新飼料能滿足肉用仔雞的喂養(yǎng)需要又使總成本盡可能低，應如何設計配比方案？線性規(guī)劃的應用線性規(guī)劃的應用

已知各種原料的購進價1公斤分別為:0.314(玉米)、054(豆餅)、0.22（麥麩）、1.20（魚粉）、0.40（骨粉）、0.50（雞促進素）元。線性規(guī)劃的應用

設每100公斤飼料中配給的玉米、豆餅、麥麩、魚粉、骨粉、雞促進素分別為x1、x2、x3、x4、x5、x6公斤，則飼料配比即為x1：x2：x3：x4：x5：x6；于是，可建立下面的線性規(guī)劃：線性規(guī)劃的應用

是否可以將約束條件兩邊分別擴大一個倍數再進行計算？

線性規(guī)劃的應用（四）

運輸問題運輸問題大體上可以分為四種類型：1、產銷平衡的運輸問題（也稱物資調運問題）2、產銷不平衡的運輸問題3、作物布局問題4、工廠布局問題線性規(guī)劃的應用類型1：產銷平衡的運輸問題（物資調運問題）線性規(guī)劃的應用

線性規(guī)劃的應用線性規(guī)劃的應用

線性規(guī)劃的應用

可得運輸問題的數學模型如下：

類型2：產銷不平衡的運輸問題線性規(guī)劃的應用對于產銷不平衡的運輸問題，可以通過將其轉化為一個產銷平衡的運輸問題來求解。當供大于求時，可以增加一個虛擬銷地，供不應求時則增加一個虛擬產地，對應的運距（或運價）均設為零，然后應用表上作業(yè)法求出最優(yōu)調運方案。類型3：作物布局問題一般提法是：在若干塊土地上種植若干種作物，已知各塊土地的面積、作物計劃播種面積及單產，問如何安排種植計劃，使總產量最高？類型4：工廠布局問題線性規(guī)劃的應用

作物布局問題和工廠布局問題表面上看和運輸問題沒有聯系，但從建立的線性規(guī)劃模型來看則完全類似，所以上述幾類問題均歸結為“運輸問題”。線性規(guī)劃的應用線性規(guī)劃的應用例1-12甲、乙兩個煤礦供應A、B、C三個城市用煤，各煤礦產量及各城市需煤量、各煤礦到各城市的運輸距離見下表，求使總運輸量最少的調運方案。線性規(guī)劃的應用

線性規(guī)劃的應用根據本題中的煤礦日產量約束城市需求約束，以及總運輸成本最小的目標可得該問題的數學模型如下：例1-13

某油田通過輸油管道向港口輸送原油，中間有4個泵站，每段管道上的輸送能力如圖所示，已知泵站沒有儲存能力，求這個系統(tǒng)的最大輸送能力。（五）最大流量問題線性規(guī)劃的應用泵站4泵站3油田S泵站2泵站1碼頭t512

481167

10線性規(guī)劃的應用

設從各點往其它點的輸送量如下表所示

出發(fā)點

到達點

輸送量SS泵站1泵站1泵站2泵站2泵站3泵站3泵站4泵站1泵站2泵站3碼頭t泵站3泵站4泵站4碼頭t碼頭tx1x2x3x4x5x6x7x8x9線性規(guī)劃的應用依題意：目標函數為輸送原油的總量；約束條件有兩類:一類是管道上的流量約束；另一類是每個中間泵站上的平衡約束，即中間泵站上的原油流入量和流出量相等根據上述分析建立線性規(guī)劃模型如下：線性規(guī)劃的應用1號泵站平衡約束2號泵站平衡約束3號泵站平衡約束4號泵站平衡約束相應弧上的約束線性規(guī)劃的應用（1）排班問題六、其他類型的問題線性規(guī)劃的應用例1-14某快遞公司新設了一個快遞分揀部，處理每天送達和外寄的快遞件，現需要招聘一批職工來操作機器進行分揀工作。該公司由以往的統(tǒng)計數據分析與經驗預測得到每個時間段到達的快件數如下表所示：時段到達快件數量時段到達快件數量10點前500014點-16點800010點-12點700016點-18點750012點-14點800018點-20點6000線性規(guī)劃的應用已知該分揀部共有11臺機器，每臺機器的分揀速度為500件/小時，每臺機器各需要配一名職工。分揀部一部分為正式職工，上班時間分別為10-18點、12-20點、14點-22點，每人每天工資200元；另一部分是臨時工（非正式職工），每天上班6小時，分別為12-18點、14-20點、16-22點，每天工資120元，職工上班的班次時間段如下表所示。快件處理的規(guī)則是從每個整點起可處理該整點前到達的快件數，因快件有時間性要求，凡是12點前到達的快