線性規(guī)劃：建模與應用

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

2、是線性規(guī)劃模型,線性規(guī)劃模型的一般形式,什么是線性規(guī)劃模型,資源分配問題(resource-allocation)：資源約束。偉恩德玻璃制品公司產(chǎn)品組合問題 成本收益平衡問題(cost-benefit-trade-off)：收益約束。利博公司廣告組合問題，大沼澤地金色年代公司的現(xiàn)金流問題 網(wǎng)絡(luò)配送問題(distribution-network)：確定需求約束。 混合問題(mix)：多種約束,線性規(guī)劃問題的分類,Super Grain Corp. Advertising-Mix Problem (Section 4.1)(超級食品公司的廣告組合問題) 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ù)學模型,Spreadsheet Formulation (電子表格模型,配送網(wǎng)絡(luò)問題,配送網(wǎng)絡(luò)問題的函數(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)和克萊略認為公司的電子表格模型還需要進一步擴展以增加一些考慮事項) In particular, they feel that two audiences should be targeted young children and parents of young children. (他們尤其覺得必須將目標觀眾定位為兒童及他們的家長,Two new goals (兩個新的目標) The advertising should be seen by at least five million young children. (必須至少有500百萬兒童看到該廣告) The

6、advertising should be seen by at least five million parents of young children. (必須至少有500萬兒童家長看到該廣告) Furthermore, exactly $1,490,000 should be allocated for cents-off coupons. (而且正好還有149萬美元的預算可以分配到商家優(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ù)目)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 (廣告花費): 300TV + 150M +

8、100SS 4,000 ($thousand)Planning Cost (計劃成本): 90TV + 30M + 30SS 1,000 ($thousand)Number of TV Spots (TV廣告時段數(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,混合問題,混合問題也是一類典型的線性規(guī)劃問題，它包含的約束是多種多樣的，即可能有資源約束，也可能有收益約束，還可能有確定需求的約束,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)營一個回收中心，專

10、門從事四種固體廢棄物的回收，并將回收物處理、混合成為可銷售的產(chǎn)品) Three different grades of product can be made: A, B, and C (depending on the mix of materials used) (不同的原料混合，一共可以生成3種不同等級的產(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? (四種原料各應使用多少？三種不同等級的產(chǎn)品各應生產(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,混合問題建模過程,明確問題的各種活動 確定總績效測度 確定活動對績效測度的單位貢獻 確定分配給各種活動的有限資源，明確每一種資源的可用量和活動的單位使用量 確定各種活動可獲得的收益，明確