線性規(guī)劃問題的計算機求解.ppt

1、線性規(guī)劃問題的應(yīng)用,-以Excel工具為例,作業(yè)講解,P48習(xí)題1.7 (a)初始單純形表,最終單純形表,因-1/4,-1/2,-1/40，所以由判定準(zhǔn)則知原線性規(guī)劃問題為無界解,作業(yè)講解,P48習(xí)題1.7 (b)初始單純形表,最終單純形表,因為非基變量x3的檢驗數(shù)為0，并且3/50,所以可將x3換人基變量得到另一最優(yōu)解（2,0,3,0,0,0)，原線性規(guī)劃問題有無窮多最優(yōu)解，此時Z=7,線性規(guī)劃問題的特點,線性規(guī)劃問題的主要類型,資源分配問題,將有限的資源分配到各種活動中去的線性規(guī)劃問題。這一類問題的共性是在線性規(guī)劃模型中每一個函數(shù)限制均為資源限制, 并且每一種有限資源都可以表現(xiàn)為如下的形式

2、： 使用的資源數(shù)量 可用的資源數(shù)量,資源分配問題舉例,力浦公司是一家生產(chǎn)外墻涂料的建材公司。目前生產(chǎn)甲、乙兩種規(guī)格產(chǎn)品，這兩種產(chǎn)品在市場上的單位純利潤分別是4萬元和5萬元。甲、乙產(chǎn)品均需要同時消耗A、B、C三種化工材料，生產(chǎn)1個單位的甲產(chǎn)品需要消耗三種材料的情況是：1單位的A材料、2單位的B材料和1單位的C材料，而生產(chǎn)1個單位的乙產(chǎn)品需要1單位的A材料、1單位的B材料和3單位的C材料。當(dāng)前市場上的甲、乙產(chǎn)品供不應(yīng)求，但是在每個生產(chǎn)周期（假設(shè)一年）內(nèi)，公司的A、B、C三種原材料資源的儲備分別是45單位、80單位和90單位，年終剩余的資源必須無償調(diào)回，而且近期也沒有籌集到額外資源的渠道。面對這種局

3、面，力浦公司如何安排生產(chǎn)計劃，以獲得最大的市場利潤？,問題的數(shù)學(xué)模型,決策變量： 目標(biāo)函數(shù)： 約束條件： s.t：,B資源的使用量,C資源的使用量,非負約束,A資源的使用量,利潤最大-,資源的使用量有限,成本收益平衡問題,這類問題中，通過選擇各種活動水平的組合，從而以最小的成本來實現(xiàn)最低可接受的各種收益的水平。這類問題的共性是，所有的函數(shù)約束均為收益約束，并具有如下的形式： 完成的水平 最低可接受的水平,成本收益平衡問題舉例,在一塊地上種植某種農(nóng)作物，據(jù)以往經(jīng)驗，在其生長過程中至少需要氮32公斤，磷恰以24公斤為宜，鉀不得超過42公斤?，F(xiàn)有四種肥料，其單價及氮磷鉀含量（%）如下表所示。問在該地

4、塊上施用這四種肥料各多少公斤，才能滿足該農(nóng)作物對氮磷鉀的需要，又使施肥的總成本最低？,問題的數(shù)學(xué)模型,決策變量：四種肥料的使用數(shù)量 甲x1公斤 乙x2公斤 丙x3公斤 丁x4公斤 目標(biāo)函數(shù)：施肥的總成本 約束條件：,氮的需求量,磷的需求量,鉀的需求量,網(wǎng)絡(luò)配送問題,網(wǎng)絡(luò)配送問題能以最小的成本完成貨物的配送，所以稱之為網(wǎng)絡(luò)配送問題并具有如下的確定性約束形式： 提供的數(shù)量需要的數(shù)量,網(wǎng)絡(luò)配送問題舉例,光明公司是一家專門提供盒裝早餐的企業(yè)，現(xiàn)在該公司的經(jīng)營方式是通過全市不同位置的3個生產(chǎn)車間(代碼為Ai,i=1,2,3)為4個配送站(代碼為Bj,j=1,2,3,4)提供質(zhì)量一致的早餐。光明公司現(xiàn)在擁

5、有自己的運輸車隊，并在每天4點前必須完成所有的配送業(yè)務(wù)。請幫組光明公司針對以下不同情況，合理規(guī)劃出運輸成本最小的配送方案。各車間的產(chǎn)量、各配送點的需求量以及之間單位產(chǎn)品的運輸成本情況見下表。,運價單位：百元,問題的數(shù)學(xué)模型,決策變量：每個產(chǎn)地運往每個銷地的運量,目標(biāo)函數(shù)：使運費最少,問題的數(shù)學(xué)模型,約束條件,產(chǎn)地的運量和等于生產(chǎn)量,銷地的運量和等于需求量,非負約束,混合問題,資源分配問題，成本收益平衡問題以及網(wǎng)絡(luò)配送問題，都以一類約束條件為特色的。實際上，純資源分配問題的共性是它所有的函數(shù)約束均為資源約束，而成本收益平衡問題的共性是它所有的函數(shù)約束均為收益約束，網(wǎng)絡(luò)配送問題中，主要的函數(shù)約束為

6、一特定類型的確定需求的約束。 混合問題 是第四類線性規(guī)劃問題，這一類型包括了前三類約束函數(shù),混合問題舉例,某電視臺預(yù)安排一晚間新聞節(jié)目中各類型新聞的時間。晚間新聞的總時長為20分鐘，其中包括本地新聞、國內(nèi)新聞、天氣預(yù)報和體育節(jié)目四個子欄目。每種子欄目的制作費用分別為300元/分鐘、200元/分鐘、100元/分鐘、100元/分鐘。在安排的過程中要求本地新聞至少占總時長的15%，本地新聞和國內(nèi)新聞至少占總時長的50%，天氣預(yù)報的時間要不大于體育節(jié)目，天氣預(yù)報至少占總時長的20%。如何合理安排四種欄目的時間使得晚間新聞的總成本最小。,問題的數(shù)學(xué)模型,決策變量：每個節(jié)目的時間 本地新聞- 國內(nèi)新聞- 天氣預(yù)