[ppt模板]線性規(guī)劃(已修改)
2025-01-31 09:52 本頁面
【正文】 第一章 線性規(guī)劃與單純形方法 內(nèi)容： 線性規(guī)劃的數(shù)學(xué)模型，標(biāo)準(zhǔn)形式，基本概念及基本原理；線性規(guī)劃的圖解法，單純形法，大 M法，兩階段法。 ? 重點(diǎn) ： ? （ 1）線性規(guī)劃的基本概念 ? （ 2）單純形法的基本原理與計(jì)算步驟 ? 難點(diǎn)： ? （ 1）單純形法的基本原理與計(jì)算步驟 ? 基本要求： ? （ 1）理解線性規(guī)劃的基本概念：目標(biāo)函數(shù)、約束條件、可行解與可行域、基可行解、最優(yōu)解及它們之間的關(guān)系；會(huì)寫線性規(guī)劃的標(biāo)準(zhǔn)形式。 ? （ 2）理解并掌握線性規(guī)劃求解的基本理論：可行域，基本可行解與凸集頂點(diǎn)的關(guān)系，最優(yōu)解。 ? （ 3）掌握線性規(guī)劃的圖解法：可行域、等值線移動(dòng)方向、最優(yōu)解的存在性情況。 ? （ 4）熟練掌握線性規(guī)劃的單純形法：單純形法的基本原理、基本步驟、最優(yōu)解的判定。 ? （ 5）熟練掌握大 M法、兩階段法的原理和計(jì)算步驟。 ? （ 6）能利用線性規(guī)劃的知識(shí)對(duì)一些實(shí)踐問題，如：組織生產(chǎn)計(jì)劃問題、節(jié)約下料問題等，建模求解； ? （ 7）能利用當(dāng)前的計(jì)算機(jī)軟件求解線性規(guī)劃問題。 線性規(guī)劃（概論） 線性規(guī)劃（ Linear Programming)創(chuàng)始人： 1947年美國人 （ Dantzing） 1951年提出單純形算法（ Simpler） 1963年 Dantzing寫成“ Linear Programming and Extension” 1979年蘇聯(lián)的 Khachian提出“橢球法” 1984年印度的 Karmarkar提出“投影梯度法” 線性規(guī)劃是研究線性不等式組的理論，或者說是研究（高維空間中）凸多面體的理論，是線性代數(shù)的應(yīng)用和發(fā)展。 11 線性規(guī)劃基本概念 生產(chǎn)計(jì)劃問題 ?如何合理使用有限的人力 ， 物力和資金 ， 使得收到最好的經(jīng)濟(jì)效益 。 ?如何合理使用有限的人力 ， 物力和資金 ， 以達(dá)到最經(jīng)濟(jì)的方式 ， 完成生產(chǎn)計(jì)劃的要求 。 例 生產(chǎn)計(jì)劃問題 （ 資源利用問題 ） 勝利家具廠生產(chǎn)桌子和椅子兩種家具 。 桌子售價(jià) 50元 /個(gè) ， 椅子銷售價(jià)格30元 /個(gè) ， 生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種 。 生產(chǎn)一個(gè)桌子需要木工 4小時(shí) ， 油漆工 2小時(shí) 。 生產(chǎn)一個(gè)椅子需要木工 3小時(shí) ， 油漆工 1小時(shí) 。 該廠每個(gè)月可用木工工時(shí)為 120小時(shí) ， 油漆工工時(shí)為 50小時(shí) 。 問該廠如何組織生產(chǎn)才能使每月的銷售收入最大 ？ 解： 將一個(gè)實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個(gè)步驟： 1． 確定決策變量： x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量 2． 確定目標(biāo)函數(shù)： 家具廠的目標(biāo)是銷售收入最大 max z=50x1+30x2 3． 確定約束條件： 4x1+3x2?120（ 木工工時(shí)限制 ） 2x1+x2 ? 50 （ 油漆工工時(shí)限制 ） 4． 變量取值限制： 一般情況 ， 決策變量只取正值 （ 非負(fù)值 ） x1 ? 0, x2 ? 0 數(shù)學(xué)模型 max S=50x1+30x2 . 4x1+3x2 ? 120 2x1+ x2 ? 50 x1,x2 ? 0 線性規(guī)劃數(shù)學(xué)模型三要素： 決策變量 、 約束條件 、 目標(biāo)函數(shù) 12 線性規(guī)劃問題的數(shù)學(xué)模型 例 1 .2 營養(yǎng)配餐問題 假定一個(gè)成年人每天需要從食物中獲得 3000千卡的熱量、 55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價(jià)格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最小？ 序號(hào) 食品名稱 熱量 （千卡） 蛋白質(zhì)（克） 鈣 （毫克） 價(jià)格（元） 1 豬肉 1000 50 400 14 2 雞蛋 800 60 200 6 3 大米 900 20 300 3 4 白菜 200 10 500 2 各種食物的營養(yǎng)成分表 解： 設(shè) xj為第 j種食品每天的購入量 ， 則配餐問題的線性規(guī)劃模型為： min S=14x1+6x2 +3x3+2x4 . 1000x1+800x2 +900x3+200x4 ? 3000 50x1+ 60x2 + 20x3+ 10x4 ? 55 400x1+200x2 +300x3+500x4 ? 800 x1， x2 ， x3 ， x4 ? 0 其他典型問題： ?合理下料問題 ?運(yùn)輸問題 ?生產(chǎn)的組織與計(jì)劃問題 ?投資證券組合問題 ?分派問題 ?生產(chǎn)工藝優(yōu)化問題 用于成功決策的實(shí)例： ?美國航空公司關(guān)于哪架飛機(jī)用于哪一航班和哪些機(jī)組人員被安排于哪架飛機(jī)的決策 ?美國國防部關(guān)于如何
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1