運(yùn)籌學(xué)-單純形法-預(yù)覽頁
【正文】 /28 10 第 5節(jié) 單純形法的進(jìn)一步討論 一、人工變量法（大 M法） 約束條件： “ ≤” → 加一個松弛變量 “ ≥” → 減一個剩余變量后，再加一個人工變量 “ ＝ ” → 加一個人工變量 目標(biāo)函數(shù)： 人工變量的系數(shù)為 “ － M”，即罰因子 若線性規(guī)劃問題有最優(yōu)解則人工變量必為 0。 ? 第二階段：將第一階段計(jì)算所得的單純形表劃去人工變量所在的列，并將目標(biāo)函數(shù)換為原問題的目標(biāo)函數(shù)作為第二階段的初始單純形表，進(jìn)行進(jìn)一步的求解。標(biāo)準(zhǔn)化過程按第 7種情況： 取 值 右端項(xiàng) 等式或不等式 極大或極小 新加變量系數(shù) xj無約束 xj ≤ 0 bi 0 ≤ = ≥ minZ xs xa 令 xj = xj′ xj″ xj′ ≥0 xj″ ≥0 令 xj′= xj 約束條件兩端同乘以1 加松弛變量 xs 加入人工變量xa 減去剩余變量 xs 加入人工變量 xa 令 z′= Z minZ =max z′ 0 M 2022/8/28 19 第 5節(jié) 單純形法的進(jìn)一步討論 人工變量法（大 M法）和兩階段法 約束條件： “ ≤” → 加一個松弛變量 “ ≥” → 減一個剩余變量后，再加一個人工變量 “ ＝ ” → 加一個人工變量 若線性規(guī)劃問題有最優(yōu)解則人工變量必為 0。 ? ⑴ .要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)； ? ⑵ .存在著多種方案； ? ⑶ .要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述。 ? 第三步：明確目標(biāo)要求，并用決策變量的線性函數(shù)來表示，確定對函數(shù)是取極大還是取極小的要求。 生產(chǎn)產(chǎn)品 B的同時(shí)產(chǎn)出副產(chǎn)品 C， 每生產(chǎn)一噸產(chǎn)品 B，可同時(shí)得到 2噸產(chǎn)品 C而毋需外加任何費(fèi)用；副產(chǎn)品 C一部分可以盈利 ， 剩下的只能報(bào)廢 。 2022/8/28 28 ? 數(shù)學(xué)模型： 設(shè)： x1—— 產(chǎn)品 A的產(chǎn)量 ， x2—— 產(chǎn)品 B的產(chǎn)量 ， x3—— 產(chǎn)品 C的銷售量 ， x4——產(chǎn)品 C的報(bào)廢量 。 根數(shù) 方案 需要 根數(shù) 長度 I II III IV V VI VII VIII 1 2 0 1 0 1 0 0 100 0 0 2 2 1 1 3 0 100 3 1 2 0 3 1 0 4 100 合計(jì) 6 料頭 0 – 解：依題意，在排除明顯不合理的方案后。 B: 第一年年初或第三年年初投資，每兩年每元投資可獲利潤，兩年后獲利。這項(xiàng)投資最多不超過 15 000元。標(biāo)準(zhǔn)化過程按第 7種情況： 取 值 右端項(xiàng) 等式或不等式 極大或極小 新加變量系數(shù) xj無約束 xj ≤ 0 bi 0 ≤ = ≥ minZ xs xa 令 xj = xj′ xj″ xj′ ≥0 xj″ ≥0 令 xj′= xj 約束條件兩端同乘以1 加松弛變量 xs 加入人工變量xa 減去剩余變量 xs 加入人工變量 xa 令 z′= Z minZ =max z′ 0 M 2022/8/28 38 添加松弛變量、人工變量列出初始單純形表 所有 基變量中有 非零人工變量 某非基變量 檢驗(yàn)數(shù)為零 唯一最優(yōu)解 無窮多最優(yōu)解 無可行解 對任一 有 換基繼續(xù) Y Y Y Y N N N 無界解 N ?? jjika???000?? jjika???000??jjika???000計(jì)算非基變量各列的 檢驗(yàn)數(shù) j?2022/8/28 39 對任一 有 ?? jj ika?? ?00 0??jjika???000N 換基繼續(xù) 令 m a x{ }kj???0m i n{ }ikiiiklillkabaxa??????對 所 有 計(jì) 算令為 換 出 變 量為 主 元 素39。( 1 )( 2) ( )
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1