[ppt模板]線性規(guī)劃-展示頁
2025-01-28 09:52本頁面
【正文】 法、兩階段法的原理和計算步驟。 線性規(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ā)展。 ?如何合理使用有限的人力 ， 物力和資金 ， 以達到最經(jīng)濟的方式 ， 完成生產(chǎn)計劃的要求 。 桌子售價 50元 /個 ， 椅子銷售價格30元 /個 ， 生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種 。 生產(chǎn)一個椅子需要木工 3小時 ， 油漆工 1小時 。 問該廠如何組織生產(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)的前提下使購買食品的費用最??？ 序號 食品名稱 熱量 （千卡） 蛋白質(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)于如何從現(xiàn)有的一些基地向海灣運送海灣戰(zhàn)爭所需要的人員和物資的決策 ? Chessie道路系統(tǒng)關(guān)于購買和修理價值 40億美圓貨運汽車決策 用于成功決策的實例： ?魁北克水利部門關(guān)于用哪幾個水庫來滿足每天電力需求決策 ?農(nóng)場信貸系統(tǒng)聯(lián)邦土地銀行關(guān)于如何支付到期債券和應發(fā)售多少新債券以獲取資金（每年共計 60億美圓）來維持發(fā)展決策 ?北美長途運輸公司關(guān)于每周如何調(diào)度數(shù)千輛貨車的決策 ??？松瓱捰蛷S關(guān)于調(diào)節(jié)冶煉能力去適應關(guān)于無鉛燃料生產(chǎn)的法律更改的決策 線性規(guī)劃問題的一般形式： Max(Min)S=c1x1+c2x2+… ..+xn . a11x1+a12x2+… .+a1nxn ?(=, ?)b1 a21x1+a22x2+… .+a2nxn ?(=, ?)b2 ………………… . am1x1+am2x2+… .+amnxn ?(=, ?)bm x1,x2… .xn ? 0 線性規(guī)劃問題隱含的假定： ?比例性假定 ?可加性假定 ?連續(xù)性假定 ?確定性假定 線性規(guī)劃問題隱含的假定： ?比例性假定： 決策變量變化引起的目標函數(shù)的改變量和決策變量的改變量成比例，同樣，每個決策變量的變化引起約束方程左端值的改變量和該變量的改變量成比例。 ?連續(xù)性假定： 線性規(guī)劃問題中的決策變量應取連續(xù)值。線性規(guī)劃問題不包含隨機因素。 xj無非負限制，引進兩個非負變量 xj ? xj ? ? 0 令 xj= xj? xj?（可正可負）
教學課件相關(guān)推薦
鄂ICP備17016276號-1