1、第2章線性規(guī)劃單純形法,線性規(guī)劃單純形法,3,由上一章可知，線性規(guī)劃模型有各種不同的形式；即目標(biāo)函數(shù)可以求極大值，也可以求極小值；約束條件可以是等式也可以是不等式，不等號可以是“”也可以是“”；決策變量一般是非負的，但在理論模型中可能會允許在區(qū)間（，+）內(nèi)取值。 為適應(yīng)通用的代數(shù)求解方法，將不同形式的線性規(guī)劃模型轉(zhuǎn)化為統(tǒng)一的標(biāo)準(zhǔn)形式是十分必要的。,2.1 線性規(guī)劃問題的標(biāo)準(zhǔn)型,4,一般線性規(guī)劃問題的標(biāo)準(zhǔn)型為（SLP）,2.1 線性規(guī)劃問題的標(biāo)準(zhǔn)型,代數(shù)式：,5,矩陣式：,2.1 線性規(guī)劃問題的標(biāo)準(zhǔn)型,6,和式：,2.1 線性規(guī)劃問題的標(biāo)準(zhǔn)型,向量式：,7,目標(biāo)函數(shù)值總為求最大。 約束條件全為線

2、性等式。 約束條件右端常數(shù)項全部為非負數(shù)。 決策變量全大于或等于零。,2.1 線性規(guī)劃問題的標(biāo)準(zhǔn)型,標(biāo)準(zhǔn)型有以下4個特征,8,目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化： minZ=-max(-Z)，求z的最小值就是求z的最大值 不等式約束的轉(zhuǎn)化: 加入松弛變量 減去剩余變量 當(dāng)約束條件中第個方程出現(xiàn)ai1x1+ai2x2+ainxnbi時，則減去一個“松弛變量”xi10，使它成為等式ai1x1+ ai2x2+ainxn xi1=bi。,2.1.2 非標(biāo)準(zhǔn)型線性規(guī)劃問題的標(biāo)準(zhǔn)化,9,當(dāng)決策變量xj不滿足xj0時，則增加兩個新的非負決策變量xj0和xj0，用xj-xj替代xj，即令xj=xj-xj。 當(dāng)約束條件中第i個方程右端出現(xiàn)常數(shù)項bi0時，則在方程兩邊同時乘(-1)，得到bi0。,2.1.2 非標(biāo)準(zhǔn)型線性規(guī)劃問題的標(biāo)準(zhǔn)化,例2.1 將下列非標(biāo)準(zhǔn)型線性規(guī)劃問題化為標(biāo)準(zhǔn)型。,2.1.2 非標(biāo)準(zhǔn)型線性規(guī)劃問題的標(biāo)準(zhǔn)化,解 按照前面的變換方法，執(zhí)行下列步驟。 將min z轉(zhuǎn)化為max (z)。 令x3 = x3 x3，且x30，x30。 將第一個約束方程的左邊減去一個非負的松弛變量x4，將第2、第3個約束方程的左邊分別加上一個非負的松弛變量x5和x6 這樣，可以將原來的線性規(guī)劃問題標(biāo)準(zhǔn)化為,2.1.2 非