線(xiàn)性規(guī)劃：建模與應(yīng)用

1、運(yùn)籌學(xué)Operations Research,Operations Research,Chapter 4. Linear Programming: Formulation and Applications,第四章. 線(xiàn)性規(guī)劃：建模與應(yīng)用,Operations Research,滿(mǎn)足以下三個(gè)條件的模型稱(chēng)為線(xiàn)性規(guī)劃模型 每一個(gè)問(wèn)題都用一組決策變量(通常非負(fù))表示某一方案，這組決策變量的值就代表一個(gè)具體方案 存在一定的約束條件，這些約束條件可以用一組線(xiàn)性等式或線(xiàn)性不等式來(lái)表示 都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量的線(xiàn)性函數(shù)(稱(chēng)為目標(biāo)函數(shù))來(lái)表示，按照問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化,什么

2、是線(xiàn)性規(guī)劃模型,線(xiàn)性規(guī)劃模型的一般形式,什么是線(xiàn)性規(guī)劃模型,資源分配問(wèn)題(resource-allocation)：資源約束。偉恩德玻璃制品公司產(chǎn)品組合問(wèn)題 成本收益平衡問(wèn)題(cost-benefit-trade-off)：收益約束。利博公司廣告組合問(wèn)題，大沼澤地金色年代公司的現(xiàn)金流問(wèn)題 網(wǎng)絡(luò)配送問(wèn)題(distribution-network)：確定需求約束。 混合問(wèn)題(mix)：多種約束,線(xiàn)性規(guī)劃問(wèn)題的分類(lèi),Super Grain Corp. Advertising-Mix Problem (Section 4.1)(超級(jí)食品公司的廣告組合問(wèn)題) Resource Allocation Pr

3、oblems j = C1, C2, C3) Minimize (最小化) Cost = $700SF1-C1 + $900SF1-C2 + $800SF1-C3 + $800SF2-C1 + $900SF2-C2 + $700SF2-C3,subject to (約束)Factory 1:SF1-C1 + SF1-C2 + SF1-C3 = 12Factory 2:SF2-C1 + SF2-C2 + SF2-C3 = 15Customer 1: SF1-C1 + SF2-C1 = 10Customer 2: SF1-C2 + SF2-C2 = 8Customer 3: SF1-C3 + SF

4、2-C3 = 9andSij 0 (i = F1, F2; j = C1, C2, C3,Algebraic Formulation (數(shù)學(xué)模型,Spreadsheet Formulation (電子表格模型,配送網(wǎng)絡(luò)問(wèn)題,配送網(wǎng)絡(luò)問(wèn)題的函數(shù)約束是確定的需求約束，可表示為： 提供的數(shù)量=需要的數(shù)量,Continuing the Super Grain Case Study,David and Claire conclude that the spreadsheet model needs to be expanded to incorporate some additional conside

5、rations. (大衛(wèi)和克萊略認(rèn)為公司的電子表格模型還需要進(jìn)一步擴(kuò)展以增加一些考慮事項(xiàng)) In particular, they feel that two audiences should be targeted young children and parents of young children. (他們尤其覺(jué)得必須將目標(biāo)觀(guān)眾定位為兒童及他們的家長(zhǎng),Two new goals (兩個(gè)新的目標(biāo)) The advertising should be seen by at least five million young children. (必須至少有500百萬(wàn)兒童看到該廣告) The

6、advertising should be seen by at least five million parents of young children. (必須至少有500萬(wàn)兒童家長(zhǎng)看到該廣告) Furthermore, exactly $1,490,000 should be allocated for cents-off coupons. (而且正好還有149萬(wàn)美元的預(yù)算可以分配到商家優(yōu)惠卷,Continuing the Super Grain Case Study,Benefit and Fixed-Requirement Data,Algebraic Formulation,Let

7、 (假定) TV = Number of commercials for separate spots on television (電視上的廣告時(shí)段數(shù)目)M = Number of advertisements in magazines (雜志上的廣告數(shù)目)SS = Number of advertisements in Sunday supplements (星期天增刊上的廣告數(shù)目) Maximize (最大化廣告受眾量) Exposure = 1,300TV + 600M + 500SS,subject to (約束)Ad Spending (廣告花費(fèi)): 300TV + 150M +

8、100SS 4,000 ($thousand)Planning Cost (計(jì)劃成本): 90TV + 30M + 30SS 1,000 ($thousand)Number of TV Spots (TV廣告時(shí)段數(shù)): TV 5Young children: 1.2TV + 0.1M 5 (millions)Parents: 0.5TV + 0.2M + 0.2SS 5 (millions)Coupons (優(yōu)惠卷): 40M + 120SS = 1,490 ($thousand) andTV 0, M 0, SS 0,Algebraic Formulation,Spreadsheet For

9、mulation,Types of Functional Constraints,混合問(wèn)題,混合問(wèn)題也是一類(lèi)典型的線(xiàn)性規(guī)劃問(wèn)題，它包含的約束是多種多樣的，即可能有資源約束，也可能有收益約束，還可能有確定需求的約束,The Save-It Company operates a reclamation center that collects four types of solid waste materials and then treats them so that they can be amalgamated into a salable product. (賽維特公司經(jīng)營(yíng)一個(gè)回收中心，專(zhuān)

10、門(mén)從事四種固體廢棄物的回收，并將回收物處理、混合成為可銷(xiāo)售的產(chǎn)品) Three different grades of product can be made: A, B, and C (depending on the mix of materials used) (不同的原料混合，一共可以生成3種不同等級(jí)的產(chǎn)品：A、B和C,Save-It Company Waste Reclamation,Product Data for the Save-It Company,Material Data for the Save-It Company,Save-It Company Waste Recl

11、amation,What quantity of each of the three grades of product should be produced from what quantity of each of the four materials? (四種原料各應(yīng)使用多少？三種不同等級(jí)的產(chǎn)品各應(yīng)生產(chǎn)多少,Algebraic Formulation,Let (假定) xij = Pounds of material j allocated to product i per week (i = A, B, C; j = 1, 2, 3, 4) (每周原料j分配給產(chǎn)品i的數(shù)量) Maxim

12、ize (最大化收益) Profit = 5.5(xA1 + xA2 + xA3 + xA4) + 4.5(xB1 + xB2 + xB3 + xB4) + 3.5(xC1 + xC2 + xC3 + xC4,subject to (約束) Mixture Specifications (混合比例規(guī)定): xA1 0.3 (xA1 + xA2 + xA3 + xA4) xA2 0.4 (xA1 + xA2 + xA3 + xA4) xA3 0.5 (xA1 + xA2 + xA3 + xA4) xA4 = 0.2 (xA1 + xA2 + xA3 + xA4) xB1 0.5 (xB1 + x

13、B2 + xB3 + xB4) xB2 0.1 (xB1 + xB2 + xB3 + xB4) xB4 = 0.1 (xB1 + xB2 + xB3 + xB4) xC1 0.7 (xC1 + xC2 + xC3 + xC4,Algebraic Formulation,Availability of Materials (可獲得的材料): xA1 + xB1 + xC1 3,000 xA2 + xB2 + xC2 2,000 xA3 + xB3 + xC3 4,000 xA4 + xB4 + xC4 1,000 Restrictions on amount treated (處理的材料數(shù)量約束

14、): xA1 + xB1 + xC1 1,500 xA2 + xB2 + xC2 1,000 xA3 + xB3 + xC3 2,000 xA4 + xB4 + xC4 500,Algebraic Formulation,Restriction on treatment cost (處理成本約束): 3(xA1 + xB1 + xC1) + 6(xA2 + xB2 + xC2) + 4(xA3 + xB3 + xC3) + 5(xA4 + xB4 + xC4) = 30,000and xij 0 (i = A, B, C; j = 1, 2, 3, 4,Algebraic Formulation,Spreadsheet Formulation,混合問(wèn)題建模過(guò)程,明確問(wèn)題的各種活動(dòng) 確定總績(jī)效測(cè)度 確定活動(dòng)對(duì)績(jī)效測(cè)度的單位貢獻(xiàn) 確定分配給各種活動(dòng)的有限資源，明確每一種資源的可用量和活動(dòng)的單位使用量 確定各種活動(dòng)可獲得的收益，明確