2.1線性規(guī)劃的對偶問題(經(jīng)典運(yùn)籌學(xué))ppt課件

第2章線性規(guī)劃的對偶理論及其應(yīng)用,線性規(guī)劃最重要的理論之一進(jìn)行經(jīng)濟(jì)分析的重要工具,1,2.1線性規(guī)劃的對偶問題,一、對偶問題的提出二、原問題與對偶問題的對應(yīng)關(guān)系三、原問題與對偶問題的數(shù)學(xué)模型,2,一、對偶問題的提出,3,例1：大眾家電廠家利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：,設(shè)產(chǎn)量產(chǎn)量,問如何安排生產(chǎn)，使獲利最多？,4,例2.1*有一個企業(yè)家接到一批加工定單，需用到設(shè)備A,B,C,有意租用大眾家電廠的三種設(shè)備，問該企業(yè)家應(yīng)如何出價，才能使家電廠覺得有利可圖肯把設(shè)備出租，又使自己付出的租金最少？,企業(yè)家,付出的代價最小,出讓代價應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤。,對方能接受,廠家,5,廠家能接受的條件：收購方的意愿：,出讓代價應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤。,設(shè)：設(shè)備Ay1元時,設(shè)備By2元時,設(shè)備Cy3元時,6,對偶問題,原問題,企業(yè)家,廠家,一對對偶問題,7,例2.2假定一個成年人每天需要從食物中獲取3000kcal的熱量、55g蛋白質(zhì)和800mg的鈣。如果市場上只有四種食品可供選擇，問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最小？,8,例2.2*有一個廠商生產(chǎn)三種可代替食品中熱量、蛋白質(zhì)、鈣的營養(yǎng)素，問該廠商應(yīng)如何制定每種營養(yǎng)素單位營養(yǎng)量的價格，使其獲得最大的收益？,9,消費(fèi)者：,經(jīng)營者：,原問題,對偶問題,一對對偶問題,10,3個約束2個變量,2個約束3個變量,一般規(guī)律,二、原問題與對偶問題的對應(yīng)關(guān)系,11,對偶問題：,原問題：,3個約束,4個變量,4個約束,3個變量,12,三、原問題與對偶問題的數(shù)學(xué)模型,1、對稱型對偶問題,2、標(biāo)準(zhǔn)型對偶問題,3、混合型對偶問題,13,定義：設(shè)原線性規(guī)劃問題為：,則稱下列線性規(guī)劃問題：,bi無正負(fù)限制,1、對稱型對偶問題,為其對偶規(guī)劃，,（P）,（D）,一對對偶問題,互為對偶,14,所求對偶問題為：,15,所求對偶問題為：,16,對稱型對偶問題的矩陣形式：,17,2、標(biāo)準(zhǔn)型對偶問題,設(shè)原問題（P）為標(biāo)準(zhǔn)型：,化為對稱型,18,所求對偶問題為：,19,所求對偶問題為：,所求對偶問題為：,20,所求對偶問題為：,與對稱型對偶問題比較：,規(guī)則：,若原問題（P）的約束方程為“=”約束,則對偶原問題（D）的變量無符號限制,21,因此若原問題（P）為標(biāo)準(zhǔn)型：,則對偶問題（D）為：,22,3、混合型對偶問題,化為對稱型,23,化為對稱型,24,25,對偶規(guī)劃問題（D）為,26,對偶規(guī)劃問題（D）為,對偶規(guī)劃問題（D）為：,27,對偶規(guī)劃問題（D）為：,原問題（P）,對偶問題（D）,變量約束：,方程約束：,變量,方程,變量無限制,方程=,變量,方程,方程約束：,變量約束：,方程=,變量無限制,方程,變量,方程,變量,結(jié)構(gòu)與對稱型相似,28,（P）與(D)的關(guān)系對應(yīng)表：,目標(biāo)函數(shù)max,目標(biāo)函數(shù)min,目標(biāo)函數(shù)系數(shù),約束方程常數(shù)列,約束方程常數(shù)列,目標(biāo)函數(shù)系數(shù),變量個數(shù)n,約束方程個數(shù)n,約束方程個數(shù)m,變量個數(shù)m,約束方程,變量0,0,=,無符號約束,變量0,約束方程,0,無符號約束,=,系數(shù)矩陣A,=-3,29,（P）與(D)的關(guān)系對應(yīng)表：,目標(biāo)函數(shù)max,目標(biāo)函數(shù)min,目標(biāo)函數(shù)系數(shù),約束方程常數(shù)列,約束方程常數(shù)列,目標(biāo)函數(shù)系數(shù),變量個數(shù)n,約束方程個數(shù)n,約束方程個數(shù)m,變量個數(shù)m,約束方程,變量0,0,=,無符號約束,變量0,約束方程,0,無符號約束,=,系數(shù)矩陣A,=-3,30,練習(xí)：,（P）與(D)的關(guān)系對應(yīng)表：,目標(biāo)函數(shù)max,目標(biāo)函數(shù)min,目標(biāo)函數(shù)系數(shù),約束方程常數(shù)列,約束方程常數(shù)列,目標(biāo)函