第一章線性規(guī)劃ppt課件

1、線性規(guī)劃研究的主要問(wèn)題線性規(guī)劃研究的主要問(wèn)題 一類是已有一定數(shù)量的資源人力、物質(zhì)、時(shí)間一類是已有一定數(shù)量的資源人力、物質(zhì)、時(shí)間等），研究如等），研究如何充分合理地使用它們，才能使完成的任務(wù)量為最大。何充分合理地使用它們，才能使完成的任務(wù)量為最大。 實(shí)際上，上述兩類問(wèn)題是一個(gè)問(wèn)題的兩個(gè)不同的方面，都是求問(wèn)題的最優(yōu)解（ max 或 min ）。 另一類是當(dāng)一項(xiàng)任務(wù)確定以后，研究如何統(tǒng)籌安排，才能使完成任務(wù)所耗費(fèi)的資源量為最少。第一部分第一部分 線性規(guī)劃線性規(guī)劃（Linear Programming，簡(jiǎn)稱，簡(jiǎn)稱LP）第一章第一章 線性規(guī)劃基礎(chǔ)線性規(guī)劃基礎(chǔ)例1.1 某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品

2、所需資源及單位產(chǎn)品利潤(rùn) 問(wèn)：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使 總利潤(rùn)最大？ 1.1 1.1 線性規(guī)劃的基本概念線性規(guī)劃的基本概念一、問(wèn)題的提出一、問(wèn)題的提出解：解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分 別為 x1、x22.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有： max z = 2 x1 + 3 x23.約束條件： x1 + 2x2 8 4x1 16 4x2 12 x1， x20例1.2 某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過(guò)180單位，且使原料總成本最小。解：解：1.決策變量：設(shè)四種原料的

3、使用 量分別為： x1、x2 、x3 、x42.目標(biāo)函數(shù)：設(shè)總成本為z，則有： min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.約束條件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x40 藥物原料ABC單位成本（元噸）甲1235乙2016丙1417丁1228二、數(shù)學(xué)模型二、數(shù)學(xué)模型1.決策變量： X = (x1,x2,.,xn)T2.目標(biāo)函數(shù)：max(minz) = c1 x1 + c2 x2 + . + cnxn3.約束條件： a11x1 + a12 x2 +.

4、+ a1n xn (=) b1 a21x1 + a22 x2 +.+ a2n xn (=) b2 am1x1 + am2 x2 +.+ amn xn (=) bm x1,x2,xn0三、模型特點(diǎn)三、模型特點(diǎn)1 都用一組決策變量X = (x1,x2,xn)T表示某一方案，且決策變量取值非負(fù)； 滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃2 都有一個(gè)要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成決策變量的線性函數(shù)；3 都有一組約束條件，這些約束條件可以用決策變量的線性等式或線性不等 式來(lái)表示。),2, 1(0),2, 1(M11njxmibxaxcaxzjnjijnjjjji標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式線形規(guī)劃的標(biāo)準(zhǔn)化線形規(guī)劃的標(biāo)準(zhǔn)化1如果求如果求min2如果約束條件如果約束條件3. 如果如果b0，則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu)?！皯土P” 人工變量！m1ijiij0ibPP)a(x bPX bxPin1ii線性規(guī)劃問(wèn)題的一般形式線性