線性規(guī)劃運(yùn)用舉例課件

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

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

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

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

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

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