【正文】 的轉(zhuǎn)軸變換得到新單純形表。 ? 它所在列中有惟一的正元素 5/2，即基本變量 x1相應(yīng)行的元素。 ? 在上面的單純形表中，惟一的值為正的 z行元素是非基本變量 x2相應(yīng)的列，其值為 1/2。 ? 不斷重復(fù)上述過程，直到 z行的所有非基本變量系數(shù)都變成負(fù)值為止。 ? 給入基變量一個增值，使之成為基本變量； ? 修改離基變量，讓入基變量所在列中，離基變量所在行的元素值減為零，而使之成為非基本變量。 ? 單純形算法的第 3步：轉(zhuǎn)軸變換 。 ? 上例中，惟一的一個值為正的 z行元素是 3，它所在列中有 2個正元素，即4和 3。所得到數(shù)值越小說明受到限制越多。 ? 如果選出的列中有一個或多個元素為正數(shù)，要弄清是哪個數(shù)限制了入基變量值的增加。 ? 如果入基變量所在的列與基本變量所在行交叉處的表元素為負(fù)數(shù)，那么該元素將不受任何限制，相應(yīng)的基本變量只會越變越大。 ? 在單純形表中考察由第 1步選出的入基變量所相應(yīng)的列。 ? 選取非基本變量 x3作為入基變量。 ? z行中的正系數(shù)非基本變量都滿足要求。 ? 查看單純形表的第 1行（也稱之為 z行）中標(biāo)有非基本變量的各列中的值。 ? 基本可行解 x=(7,0,0,12,0,10)。 ? 單純形算法的基本思想就是從一個基本可行解出發(fā)，進行一系列的基本可行解的變換。 ? 稍后將看到，任意一個線性規(guī)劃問題可以轉(zhuǎn)換為約束標(biāo)準(zhǔn)型線性規(guī)劃問題。 ? 這一類特殊的標(biāo)準(zhǔn)形式線性規(guī)劃問題稱為 約束標(biāo)準(zhǔn)型線性規(guī)劃問題 。這樣選出來的變量稱為左端變量或 基本變量 ，其總數(shù)為 m個。這一類線性規(guī)劃問題中，每一個等式約束中，至少有一個變量的系數(shù)為正，且這個變量只在該約束中出現(xiàn)。 7 約束標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形算法 ? 當(dāng)線性規(guī)劃問題中沒有不等式約束 ()和 ()式，而只有等式約束 ()和變量非負(fù)約束 ()時，稱該線性規(guī)劃問題具有標(biāo)準(zhǔn)形式 。 ? Dantzig于 1948年提出了線性規(guī)劃問題的單純形算法。 ? 上述定理的重要意義在于，它把一個最優(yōu)化問題轉(zhuǎn)化為一個組合問題，即在 () ()式的 m+n個約束條件中，確定最優(yōu)解應(yīng)滿足其中哪 n個約束條件的問題。 ? 若 nm，則基本可行解中至少有 nm個分量為 0，也就是說，基本可行解中最多有 m個分量非零。 5 ? 這個問題的解為 (x1,x2,x3,x4) = (0,1)；最優(yōu)值為 16。 ? 有些情況下可能不存在最優(yōu)解。 ? 使目標(biāo)函數(shù)取得極值的可行解稱為 最優(yōu)解 。算法設(shè)計與分析 山東師范大學(xué)計算機系 授課：徐連誠，軟件工程研究所 (3432) 2022年 9月 5日 — 2022年 1月 20日 主頁： 郵箱： 鏡像： ) ) 2 第八章 線性規(guī)劃與網(wǎng)絡(luò)流 ? 學(xué)習(xí)要點 ? 理解線性規(guī)劃算法模型 ? 掌握解線性規(guī)劃問題的單純形算法 ? 理解網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念 ? 掌握網(wǎng)絡(luò)最大流的增廣路算法 ? 掌握網(wǎng)絡(luò)最大流的預(yù)流推進算法 ? 掌握網(wǎng)絡(luò)最小費用流的消圈算法 ? 掌握網(wǎng)絡(luò)最小費用流的最小費用路算法 ? 掌握網(wǎng)絡(luò)最小費用流的網(wǎng)絡(luò)單純形算法 3 線性規(guī)劃問題和單純形算法 ? 線性規(guī)劃問題及其表示 ? 線性規(guī)劃問題可表示為如下形式： ? . )(ma x1??nj jjxc)(,2,10)(,1)(,1)(,2,1321211211111ntxmmmmmkbxammmjbxamibxatntktktntjtjtntitit????????????????????????4 ? 變量滿足約束條件 ()()式的一組值稱為線性規(guī)劃問題的一個 可行解 。 ? 所有可行解構(gòu)成的集合稱為線性規(guī)劃問題的 可行區(qū)域 。 ? 在最優(yōu)解處目標(biāo)函數(shù)的值稱為 最優(yōu)值 。 ? 通常有兩種情況： ? (1)根本沒有可行解，即給定的約束條件之間是相互排斥的，可行區(qū)域為空集； ? (2)目標(biāo)函數(shù)沒有極值，也就是說在 n 維空間中的某個方向上，目標(biāo)函數(shù)值可以無限增大，而仍滿足約束條件，此時目標(biāo)函數(shù)值無界。 4321 3m ax xxxxz ????12907218243243214231???????????xxxxxxxxxxx4,3,2,10 ?? ix i6 線性規(guī)劃基本定理 ? 約束條件 ()()中 n個約束以等號滿足的可行解稱為線性規(guī)劃問題的 基本可行解 。 ? 線性規(guī)劃基本定理： 如果線性規(guī)劃問題有最優(yōu)解，則必有一基本可行最優(yōu)解。 ? 由此可知，只要對各種不同的組合進行測試，并比較每種情況下的目標(biāo)函數(shù)值，直到找到最優(yōu)解。 ? 單純形算法的特點是： ? 1）只對約束條件的若干組合進行測試，測試的每一步都使目標(biāo)函數(shù)的值增加； ? 2）一般經(jīng)過不大于 m或 n次迭代就可求得最優(yōu)解。 ? 為便于討論，不妨先考察一類更特殊的標(biāo)準(zhǔn)形式線性規(guī)劃問題。 ? 在每一約束方程中選擇一個這樣的變量，并以它作為變量求解該約束方程。剩下的 nm個變量稱為右端變量或 非基本變量 。 ? 雖然約束標(biāo)準(zhǔn)型線性規(guī)劃問題非常特殊，但是對于理解線性規(guī)劃問題的單純形算法是非常重要的。 8 532 23m ax xxxz ????10834124272353263245321???????????xxxxxxxxxxx6,5,4,3,2,10 ?? ix ix2 x3 x5 z 0 1 3 2 x1 7 3 1 2 x4 12 2 4 0 x6 10 4 3 8 ? 任何約束標(biāo)準(zhǔn)型線性規(guī)劃問題，只要將所有非基本變量都置為 0，從約束方程式中解出滿足約束的基本變量的值，可求得一個基本可行解。 ? 每次變換將一個非基本變量與一個基本變量互調(diào)位置，且保持當(dāng)前的線性規(guī)劃問題是一個與原問題完全等價的標(biāo)準(zhǔn)線性規(guī)劃問題。 ? 單純形算法的第 1步： 選出使目標(biāo)函數(shù)增加的非基本變量作為 入基變量 。 ? 選出使目標(biāo)函數(shù)增加的非基本變量作為入基變量。 ? 在上面單純形表的 z行中只有 1列為正，即非基本變量相應(yīng)的列，其值為 3。 ? 單純形算法的第 2步： 選取 離基變量 。 ? 在一個基本變量變?yōu)樨?fù)值之前，入基變量可以增到多大。 ? 如果入基變量所在列的所有元素都是負(fù)值，則目標(biāo)函數(shù)無界，已經(jīng)得到了問題的無界解。 ? 受限的增加量可以用入基變量所在列的元素（稱為主元素）來除主元素所在行的“常數(shù)列”（最左邊的列）中元素而得到。 ? 應(yīng)該選取受到限制最多的基本變量作為離基變量，才能保證將入基變量與離基變量互調(diào)位置后，仍滿足約束條件。 ? min{12/4,10/3}=4，應(yīng)該選取 x4為離基變量； ? 入基變量 x3取值為 3。 ? 轉(zhuǎn)軸變換的目的是將入基變量與離基變量互調(diào)位置。 11 ? 解離基變量所相應(yīng)的方程，將入基變量 x3用離基變量 x4表示為 ? 再將其代入其他基本變量和所在的行中消去 x3 ， ? 代入目標(biāo)函數(shù)得到 ? 形成新單純形表 34121 423 ??? xxx184325102412554265421????????xxxxxxxx542 243219 xxxz ????x2 x4 x5 z 9 1/2 3/4 2 x1 10 5/2 1/2 2 x3 3 1/2 1/4 0 x6 1 5/2 3/4 8 ? 單純形算法的第 4步： 轉(zhuǎn)回并重復(fù)第 1步，進一步改進目標(biāo)函數(shù)值。這表明目標(biāo)函數(shù)不可能再增加了。 ? 因此，選取