數(shù)學(xué)規(guī)劃模型實驗

數(shù)學(xué)規(guī)劃模型實驗 數(shù)學(xué)教研組盧鵬2015 7 23 優(yōu)化問題及其一般模型 引言 優(yōu)化問題是人們在工程技術(shù) 經(jīng)濟管理和科學(xué)研究等領(lǐng)域中最常遇到的問題之一 例如 設(shè)計師要在滿足強度要求等條件下選擇材料的尺寸 使結(jié)構(gòu)總重量最輕 公司經(jīng)理要根據(jù)生產(chǎn)成本和市場需求確定產(chǎn)品價格 使所獲利潤最高 調(diào)度人員要在滿足物質(zhì)需求和裝載條件下安排從各供應(yīng)點到需求點的運量和路線 使運輸總費用最低 投資者要選擇一些股票 債券下注 使收益最大 而風(fēng)險最小 一般地 優(yōu)化模型可以表述下 這是一個多元函數(shù)的條件極值問題 其中 許多實際問題歸結(jié)出的這種優(yōu)化模型 若決策變量個數(shù)較少可用微分法求解 但是其決策變量個數(shù)n和約束條件個數(shù)m較大 并且最優(yōu)解往往在可行域的邊界上取得 數(shù)學(xué)規(guī)劃就是解決這類問題的有效方法 數(shù)學(xué)規(guī)劃模型分類 數(shù)學(xué)規(guī)劃是運籌學(xué)和管理科學(xué)中應(yīng)用及其廣泛的分支 數(shù)學(xué)規(guī)劃包括線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃 幾何規(guī)劃 多目標規(guī)劃等 用數(shù)學(xué)規(guī)劃方法解決實際問題 就要將實際問題經(jīng)過抽象 簡化 假設(shè) 確定變量與參數(shù) 建立適當層次上的數(shù)學(xué)模型 并求解 建立數(shù)學(xué)規(guī)劃模型的步驟 Step1 尋求決策 即回答什么 必須清楚 無歧義 閱讀完題目的第一步不是尋找答案或者解法 而是 Step2 確定決策變量第一來源 Step1的結(jié)果 用變量固定需要回答的決策第二來源 由決策導(dǎo)出的變量 具有派生結(jié)構(gòu) 其它來源 輔助變量 聯(lián)合完成更清楚的回答 Step3 確定優(yōu)化目標用決策變量表示的利潤 成本等 Step4 尋找約束條件決策變量之間 決策變量與常量之間的聯(lián)系 第一來源 需求 第二來源 供給 其它來源 輔助以及常識 Step5 構(gòu)成數(shù)學(xué)模型將目標以及約束放在一起 寫成數(shù)學(xué)表達式 目錄 線性規(guī)劃非線性規(guī)劃二次規(guī)劃整數(shù)規(guī)劃 例1 加工奶制品的生產(chǎn)計劃 一奶制品加工廠用牛奶生產(chǎn)A1 A2兩種奶制品 一桶牛奶可以在設(shè)備甲上用12小時加工成3公斤A1 或者在設(shè)備乙上用8小時加工成4公斤A2 根據(jù)市場需求 生產(chǎn)的A1 A2全部能夠售出 且每公斤A1獲利24元 每公斤A2獲利16元 現(xiàn)在加工廠每天能夠得到50桶牛奶的供應(yīng) 每天正式工人總的勞動時間為480小時 并且設(shè)備甲每天至多能加工100公斤A1 設(shè)備乙的加工能力沒有限制 試為該廠制定一個生產(chǎn)計劃 使每天獲利最大 每天 50桶牛奶 時間480小時 至多加工100公斤A1 制訂生產(chǎn)計劃 使每天獲利最大 問題分析 引入決策變量x1桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)A2 每天 目標函數(shù) 每天獲利 生產(chǎn)A1獲利 24 3x1生產(chǎn)A2獲利 16 4x2每天獲利總額 z 72x1 64x2約束條件原料供應(yīng) x1 x2 50勞動時間 12x1 8x2 480加工能力 3x1 100非負約束 x1 x2 0 模型構(gòu)成 線性規(guī)劃數(shù)學(xué)模型 線性規(guī)劃求解 標準形式 其中 均為列向量 為矩陣 調(diào)用格式 x fval linprog c A b Aeq beq lb ub options 其中 x給出極小點 fval給出目標函數(shù)極小值 options是控制參數(shù) 可用help查詢 Matlab程序如下 c 72 64 A 1 1 12 8 3 0 b 50 480 100 Ib 0 0 ub 1e 10 1 1 x fval linprog c A b lb ub 結(jié)果如下 x 20 30 fval 3360 例2 求解線性規(guī)劃問題 Matlab程序如下 c 2 3 5 A 2 5 1 b 10 Aeq 1 1 1 beq 7 lb 0 0 0 x fval linprog c A b Aeq beq lb 例3 求解非線性規(guī)劃問題 非線性規(guī)劃求解 標準形式 其中 調(diào)用格式 x fval h fmincon f x0 A b Aeq beq lb ub nonlcon 其中 nonlcon是非線性約束函數(shù) x0是迭代初始點 和 是非線性約束 Matlab程序如下 建立非線性約束函數(shù)的m文件lpnon mfunction c ceq lpcon x c x 1 1 2 x 2 Ceq 建立目標函數(shù)的m文件fun mfunctionf fun x f x 1 2 x 2 2 x 1 x 2 2 x 1 5 x 2 在命令窗口中輸入x0 0 1 A 23 b 6 Aeq beq lb ub x fval h fmincon fun x0 A b Aeq beq lb ub lpcon 結(jié)果 x 3 4 fval 13 h 1 例4 求解二次規(guī)劃問題 二次規(guī)劃求解 標準形式 其中 H是實對稱矩陣 調(diào)用格式 x fval quadprog H c A b Aeq beq lb ub x0 Matlab程序如下 H 1 1 1 2 c 2 6 A 1 1 1 2 2 1 b 2 2 3 Aeq beq lb zeros 2 1 ub x fval quadprog H c A b Aeq beq lb ub 結(jié)果 x 0 6667 1 3333 fval 8 2222 例5 求解整數(shù)規(guī)劃問題 整數(shù)規(guī)劃求解 隨機投點法 編寫目標函數(shù)和約束條件的m文件 function f g mengte x f x 1 2 x 2 2 3 x 3 2 4 x 4 2 2 x 5 2 8 x 1 2 x 2 3 x 3 x 4 2 x 5 g 1 sum x 400 g 2 x 1 2 x 2 2 x 3 x 4 6 x 5 800 g 3 2 x 1 x 2 6 x 3 200 g 4 x 3 x 4 5 x 5 200 Matlab程序如下 p0 0 x0 zeros 5 1 ticfori 1 100000 x1 99 rand