1、線性規(guī)劃運用舉例,汽油調和問題 生產(chǎn)工藝優(yōu)化問題 多周期動態(tài)生產(chǎn)計劃問題 .,1,學習交流PPT,1、汽油調和問題,例：原點煉油廠生產(chǎn)的70,80,85號三種汽油由三種原料調和而成，且有不同的質量要求，每種原料每日可用量、質量指標、成本以及每種汽油的質量要求和價格見表。該煉油廠如何調和才能使得利潤最大？假定調和中的質量指標都符合線性相加關系。,2,學習交流PPT,問題分析:最優(yōu)調和方案 什么原料調入什么產(chǎn)品，調入的數(shù)量是多少 目標：調和方案的利潤最大 利潤=銷售收入-調和成本 =產(chǎn)品價格*銷售數(shù)量-原料成本*用量 變量：產(chǎn)品數(shù)量？原料數(shù)量？其他量？ j產(chǎn)品生產(chǎn)數(shù)量=各原料調入j產(chǎn)品數(shù)量和 i原

2、料使用量=i原料調入各個產(chǎn)品的數(shù)量和 xij = i原料調入各j產(chǎn)品的數(shù)量和,3,學習交流PPT,2、生產(chǎn)工藝優(yōu)化問題,例：麗佳化工廠生產(chǎn)洗滌劑。原料可從市場上以每公斤5元的價格買到。處理1公斤原料可生產(chǎn)0.5公斤洗衣粉和0.3公斤洗滌劑。處理1公斤原料的費用為1元。工廠還可繼續(xù)對其進行精加工。用1公斤普通洗衣粉生產(chǎn)0.5公斤濃縮洗衣粉，用1公斤普通洗滌劑生產(chǎn)0.25公斤高級洗滌劑。工廠每日可處理4噸原材料。產(chǎn)品價格，生產(chǎn)成本指標見表。如果市場和原料供應沒有限制，問該工廠如何生產(chǎn)才能使其利潤最大？,4,學習交流PPT,3、多周期動態(tài)生產(chǎn)計劃問題,例：華新機器制造廠專為拖拉機廠配套生產(chǎn)柴油機。今

3、年頭四個月收到的訂單數(shù)量分別為3000，4500,3500,5000臺柴油機，該廠正常生產(chǎn)每月可生產(chǎn)柴油機3000臺，利用加班還可生產(chǎn)1500臺。正常生產(chǎn)成本為每臺5000元，加班生產(chǎn)還要追加1500元成本，庫存成本為每臺每月200元。華新廠如何組織生產(chǎn)才能使其生產(chǎn)成本最低？,5,學習交流PPT,整數(shù)規(guī)劃應用舉例,整數(shù)變量 特殊約束處理 背包問題 集合覆蓋問題 固定費用問題 旅行推銷商問題 下料問題 ,6,學習交流PPT,1、整數(shù)變量,表示不可分割的數(shù)量； 表示決策變量（0-1整數(shù)變量，具有很多優(yōu)良特點）； 表示決策變量之間的邏輯關系，例如，決策i必須以決策 j的結果為前提； 描述互斥的選擇，

4、從多種方案中選擇一個方案；,7,學習交流PPT,項目投資問題,例：某公司有600萬元資金用于投資，有5個項目列入投資計劃，各項目投資額和期望受益見下表。由于技術原因，投資受到以下約束： 項目1,2和3中必須且只能有一項被選中； 項目3和4最多只能被選中一項； 項目5被選中的前提是項目1被選中； 問如何選擇最好的投資方案，使投資收益最大。,8,學習交流PPT,2、特殊約束處理,互為矛盾的約束：須同時出現(xiàn)的矛盾約束； 絕對值約束（改寫成兩個矛盾約束）； 多種選一的約束（n個約束中只有一個約束有效）； 描述互斥的選擇，從多種方案中選擇一個方案； 邏輯關系約束（if then 約束）,9,學習交流PP

5、T,3、排班問題,郵局一年356天都要有人值班，每天需要的職工人數(shù)因業(yè)務忙閑而異，據(jù)統(tǒng)計郵局每天需要的人數(shù)按周期變化，一周內每天需要的人數(shù)如下：,排班要符合每周連續(xù)工作五天，休息兩天的規(guī)定，如何排班可使用人最少？,10,學習交流PPT,4、背包問題,例：一登山隊員做登山準備，需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相機和通訊設備。每種物品的重要性系數(shù)和重量見下表：,11,學習交流PPT,5、集合覆蓋問題,例：某城市有6個區(qū)，規(guī)劃建消防站，任何區(qū)發(fā)生火警時消防車要在15分鐘內趕到，各區(qū)間消防車行駛的時間見下表，求設置消防站最少的方案。,12,學習交流PPT,6、固定費用問題,人們經(jīng)常會

6、遇到固定費用問題。例如，要建一條生產(chǎn)線，由生產(chǎn)能力確定的投資規(guī)模是固定的，要建設，就要投入一筆固定數(shù)量資金；再如，如果生產(chǎn)要租用設備，則不管如何使用該設備，你都要支付一筆固定的租金，租金一般不隨生產(chǎn)量的變化而變化，求解這類不連續(xù)變化的固定費用問題也要借助整數(shù)規(guī)劃。,13,學習交流PPT,例：服裝廠可生產(chǎn)西服，襯衫和羽絨服。生產(chǎn)不同服裝要使用不同設備，該廠可從租賃公司租用這些設備。假定市場需求不成問題，服裝廠每月可用人工工時為2000小時，該廠如何安排生產(chǎn)可使每月利潤最大。設備租金和其它經(jīng)濟參數(shù)見下表：,14,學習交流PPT,7、旅行推銷商問題（TSP）,旅行推銷商問題是求訪n個城市。每個城市必須訪問到，且只能訪問一次的最短旅行路線問題（類似中國郵路問題，沿著街道走，走過所有街道，回到原地，網(wǎng)絡中的問題）。,