經(jīng)濟(jì)數(shù)學(xué) 課件 ch05 線性規(guī)劃初步

線性規(guī)劃初步第五章經(jīng)濟(jì)數(shù)學(xué)高等職業(yè)教育公共基礎(chǔ)課規(guī)劃教材01線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型在經(jīng)濟(jì)活動中常常要考慮兩類問題，一類是目標(biāo)任務(wù)確定后，如何統(tǒng)籌安排，用最少的人力、物力去完成任務(wù)。另一類是對現(xiàn)有的人力、物力如何進(jìn)行合理分配，使經(jīng)濟(jì)效益最大。例如，最優(yōu)運(yùn)輸問題、生產(chǎn)組織與計(jì)劃問題、合理下料問題等。線性規(guī)劃問題的數(shù)學(xué)模型一般地，在滿足某些約定條件下，使目標(biāo)函數(shù)達(dá)到極大（?。┲档膯栴}稱為數(shù)學(xué)規(guī)劃問題。如果目標(biāo)函數(shù)和約束條件都是線性的，則稱為線性規(guī)劃。線性規(guī)劃問題的數(shù)學(xué)模型運(yùn)輸問題的數(shù)學(xué)模型【例5.1】線性規(guī)劃問題的數(shù)學(xué)模型生產(chǎn)組織與計(jì)劃問題【例5.2】線性規(guī)劃問題的數(shù)學(xué)模型生產(chǎn)組織與計(jì)劃問題【例5.2】線性規(guī)劃問題的數(shù)學(xué)模型合理下料問題【例5.3】線性規(guī)劃問題的數(shù)學(xué)模型合理下料問題【例5.3】線性規(guī)劃問題的數(shù)學(xué)模型合理下料問題【例5.3】線性規(guī)劃問題的數(shù)學(xué)模型滿足以上三個條件的數(shù)學(xué)問題模型稱為線性規(guī)劃數(shù)學(xué)模型，其一般形式為：對于一個線性規(guī)劃問題，全部決策變量都滿足所有約束條件的一組數(shù)值稱為該線性規(guī)劃問題的一個可行解。全體可行解的集合稱為該線性規(guī)劃問題的可行解集（或可行解域）。使得目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解稱為最優(yōu)解。一個線性規(guī)劃數(shù)學(xué)模型問題可能沒有最優(yōu)解，也可能有有限個或無窮多個最優(yōu)解。線性規(guī)劃問題的數(shù)學(xué)模型02線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法圖解法【例5.4】線性規(guī)劃問題的圖解法圖解法的求解步驟【例5.5】線性規(guī)劃問題的圖解法【例5.6】線性規(guī)劃問題的圖解法重要結(jié)論【例5.7】線性規(guī)劃問題的圖解法【例5.8】線性規(guī)劃問題的圖解法當(dāng)目標(biāo)函數(shù)與可行解域有唯一的公共點(diǎn)時，則線性規(guī)劃問題有唯一最優(yōu)解；當(dāng)目標(biāo)函數(shù)與可行解域有無數(shù)個公共點(diǎn)時，則線性規(guī)劃問題有無窮多個最優(yōu)解（或者有可行解但無最優(yōu)解）；線性規(guī)劃問題的圖解法當(dāng)目標(biāo)函數(shù)與可行解域沒有公共點(diǎn)時，則線性規(guī)劃問題沒有最優(yōu)解。線性規(guī)劃問題的最優(yōu)解如果存在，必然在可行解域的某一個“頂點(diǎn)”處或某一條“邊”上取得。當(dāng)公共點(diǎn)在可行解域的上方時，能使目標(biāo)函數(shù)s=c1x1+c2x2取得最大值。當(dāng)公共點(diǎn)在可行解域的下方時，能使目標(biāo)函數(shù)s=c1x1+c2x2取得最小值。線性規(guī)劃問題的圖解法03線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法線性規(guī)劃問題的標(biāo)準(zhǔn)型線性規(guī)劃問題可以有多種形式，為了便于研究一般解法，可以將線性規(guī)劃問題的約束條件統(tǒng)一化為一個線性方程組和一組非負(fù)限制條件。如果目標(biāo)函數(shù)s是求最大值，則可轉(zhuǎn)化為求-s的最小值。線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法【例5.9】單純形解法線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法在用圖解法求解兩個變量的線性規(guī)劃問題時，可以看到。如果線性規(guī)劃問題存在最優(yōu)解，則其最優(yōu)解一定可以在可行解域的頂點(diǎn)上找到。線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法若令其中任意（n-m）個變量為零（這些變量稱為非基本變量），得到的新方程組有唯一解（解所對應(yīng)的變量稱為基本變量）。則這個唯一解與其為零的（n-m）個變量組成的解稱為線性規(guī)劃問題的基本解。如果基本解又是可行的，則稱之為基本可行解。在求解線性規(guī)劃問題的最優(yōu)可行解時，只需研究它的基本可行解。這時可從對應(yīng)的可行解域出發(fā)，從一個頂點(diǎn)過渡到另一個頂點(diǎn)，并使目標(biāo)函數(shù)值不斷減小。線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法這種尋求線性規(guī)劃問題最優(yōu)解的方法稱為單純形法。單純形法是針對標(biāo)準(zhǔn)形式的線性規(guī)劃問題進(jìn)行演算的，它是求解線性規(guī)劃問題的一般方法。線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法【例5.10】線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法制作初始單純形表見表5-5。線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法轉(zhuǎn)換點(diǎn)如表5-5所示5，用行變換的方法，使轉(zhuǎn)換點(diǎn)位置上的數(shù)化為1，轉(zhuǎn)換點(diǎn)所在列的其他數(shù)全部化為0，得表5-6。線性規(guī)劃問題的標(biāo)準(zhǔn)型及單純形解法再次進(jìn)行行變換得到表5-7。04數(shù)學(xué)家的故事數(shù)學(xué)家的故事華羅庚——自學(xué)成才的數(shù)學(xué)大師華羅庚（1910—1985），男，江蘇省金壇縣人。華羅庚同志是當(dāng)代自學(xué)成才的科學(xué)巨匠，是蜚聲中外的數(shù)學(xué)家。他是中國解析數(shù)論、典型群、矩陣幾何學(xué)、自守函數(shù)論與多復(fù)變函數(shù)論等很多方面的創(chuàng)始人與開拓者。數(shù)學(xué)家的故事數(shù)學(xué)家的故事華羅庚1910年11月12日出生于江蘇省金壇縣一個小商人家庭，身高1.65米，父親華瑞棟，開一間小雜貨鋪，母親是一位賢惠的家庭婦女。他12歲從縣城仁劬小學(xué)畢業(yè)后，進(jìn)入金壇縣立初級中學(xué)學(xué)習(xí)。1925年初中畢業(yè)后，因家境貧寒，無力進(jìn)入高中學(xué)習(xí)，只好到黃炎培在上海創(chuàng)辦的中華職業(yè)學(xué)校學(xué)習(xí)會計(jì)。數(shù)學(xué)家的故事不到一年，由于生活費(fèi)用昂貴，被迫中途輟學(xué)，回到金壇幫助父親料理雜貨鋪。在單調(diào)的站柜臺生活中，他開始自學(xué)數(shù)學(xué)。1927年秋，和吳筱之結(jié)婚。1929年冬天，他得了嚴(yán)重的傷寒癥，經(jīng)過近半年的治理，病雖好了，但左腿的關(guān)節(jié)卻受到嚴(yán)重?fù)p害，落下了終身殘疾，走路要借助手杖。當(dāng)時在金壇中學(xué)任教的華羅庚的數(shù)學(xué)老師，我國著名教育家、翻譯家王維克發(fā)現(xiàn)華羅庚雖貪玩，但思維敏捷。1929年，華羅庚受雇為金壇中學(xué)庶務(wù)員，并開始在上?！犊茖W(xué)》等雜志上發(fā)表論文。其實(shí)華羅庚讀初中時，一度功課并不好，有時數(shù)學(xué)還考不及格。數(shù)學(xué)家的故事數(shù)學(xué)家的故事要知道金子被埋在沙里的時候，粗看起來和沙子并沒有什么兩樣，我們當(dāng)教書匠的一雙眼睛，最需要有沙里淘金的本領(lǐng)，否則就會埋沒人才??！”1930年春，他的論文《蘇家駒之代數(shù)的五次方程式解法不能成立的理由》在上?！犊茖W(xué)》雜志上發(fā)表。數(shù)學(xué)家的故事當(dāng)時在清華大學(xué)數(shù)學(xué)系擔(dān)任系主任的熊慶來教授看到后，即多方打聽并推薦他到清華大學(xué)數(shù)學(xué)系當(dāng)圖書館助理員。1931年秋冬之交，華羅庚進(jìn)了清華園。華羅庚在清華大學(xué)一面工作一面學(xué)習(xí)。他用了兩年的時間走完了一般人需要八年才能走完的道路，1933年被破格提升為助教，1935年成為講師。1936年，他經(jīng)清華大學(xué)推薦，派往英國劍橋大學(xué)留學(xué)。他在劍橋的兩年中，把全部精力用于研究數(shù)學(xué)理論中的難題，不愿為申請學(xué)位浪費(fèi)時間。數(shù)學(xué)家的故事他的研究成果引起了國際數(shù)學(xué)界的注意。1938年回國，受聘為西南聯(lián)合大學(xué)教授。在聞一多先生的影響下，他還積極參加當(dāng)時如火如荼的抗日民主愛國運(yùn)動之中。從1939年到1941年，他在極端困難的條件下，寫了20多篇論文，完成了他的第一部數(shù)學(xué)專著《堆壘數(shù)素論》。數(shù)學(xué)家的故事《堆壘數(shù)素論》后來成為數(shù)學(xué)經(jīng)典名著，1947年在蘇聯(lián)出版，又先后在各國被翻譯出版了德文、英文、匈牙利和中文版。1946年2月至5月，他應(yīng)邀赴蘇聯(lián)訪問。1946年，當(dāng)時的國民政府也想搞原子彈，于是選派華羅庚、吳大猷、曾昭掄三位大名鼎鼎的科學(xué)家赴美考察。數(shù)學(xué)家的故事數(shù)學(xué)家的故事9月和李政道，朱光亞等離開上海前往美國，先在普林斯頓高等研究所擔(dān)任訪問教授，后又被伊利諾大學(xué)聘為終身教授。1949年新中國成立，華羅庚感到無比興奮，決心偕家人回國。數(shù)學(xué)家的故事他們一家五人乘船離開美國，1950年2月到達(dá)香港。他在香港發(fā)表了一封致留美學(xué)生的公開信，信中充滿了愛國激情，鼓勵海外學(xué)子回來為新中國服務(wù)。3月11日新華社播發(fā)了這封信。1950年3月16日，華羅庚和夫人、孩子乘火車抵達(dá)北京。接著，他受中國科學(xué)院院長郭沫若的邀請開始籌建數(shù)學(xué)研究所。1952年7月，數(shù)學(xué)所成立，他擔(dān)任所長?；貒蠖潭痰膸啄曛校跀?shù)學(xué)領(lǐng)域里的研究碩果累累。華羅庚回到了清華園，擔(dān)任清華大學(xué)數(shù)學(xué)系主任。他潛心為新中國培養(yǎng)數(shù)學(xué)人才，王元、陸啟鏗、龔升、陳景潤、萬哲先等在他的培養(yǎng)下成為著名的數(shù)學(xué)家。數(shù)學(xué)家的故事他寫成的論文《典型域上的多元復(fù)變函數(shù)論》于1957年1月獲國家發(fā)明一等獎，并先后出版了中、俄、英文版專著。1963年他和他的學(xué)生萬哲先合寫的《典型群》一書出版。1957年出版《數(shù)論導(dǎo)引》；1959年萊比錫首先用德文出版了《指數(shù)和的估計(jì)及其在數(shù)論中的應(yīng)用》，又先后出版了俄文版和中文版。數(shù)學(xué)家的故事他為培養(yǎng)青少年學(xué)習(xí)數(shù)學(xué)的熱情，在北京發(fā)起了中學(xué)生數(shù)學(xué)競賽活動，從出題、監(jiān)考、閱卷，都親自參加，并多次到外地去推廣這一活動。他還寫了一系列數(shù)學(xué)通俗讀物，在青少年中影響極大。他主張?jiān)诳茖W(xué)研究中要培養(yǎng)學(xué)術(shù)空氣，開展學(xué)術(shù)討論。數(shù)學(xué)家的故事數(shù)學(xué)家的故事他發(fā)起創(chuàng)建了我國計(jì)算機(jī)技術(shù)研究所，也是我國最早主張研制電子計(jì)算機(jī)的科學(xué)家之一。這里的“三強(qiáng)”說明是戰(zhàn)國時期韓、趙、魏三個