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