管理運(yùn)籌學(xué)復(fù)習(xí)ppt課件-在線瀏覽
2025-02-27 04:16本頁面
【正文】 xn a11x1+a12x2+…+a 1nxn ＝ b1 a21x1+a22x2+…+a 2nxn ＝ b2 … … … … … am1x1+am2x2+…+a mnxn＝ bm x1,x2,…,x n ≥0 maxZ= cjxj aijxj＝ bi ( i=1,2,…,m ) xj≥0 ( j=1,2,…,n ) ??nj 1??nj 1簡記 SHUFE 11 線性規(guī)劃標(biāo)準(zhǔn)型 ? 目標(biāo)函數(shù)極小化問題 只需將目標(biāo)等式兩端乘以 1 即變?yōu)闃O大化問題 。 ? 決策變量 xk沒有非負(fù)性要求 令 xk=xk′x k〃 ， xk=xk′， x k〃 ≥0， 用 xk′、 x k〃 取代模型中 xk ? 非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化 SHUFE 12 線性規(guī)劃解的概念 ? 基 ? m個(gè)線性無關(guān)的約束方程，稱為一個(gè)基，用 B表示。 ? 基變量 ? 與基向量 Pj相對應(yīng)的 m個(gè)變量 xj稱為基變量 ? 其余的 mn個(gè)變量為非基變量。 ? 基可行解：滿足非負(fù)性約束的基解。 SHUFE 13 表格單純形法 maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 ? 單純形法計(jì)算 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 3 5 0 0 0 8 1 0 1 0 0 12 0 2 0 1 0 36 3 4 0 0 1 x3 x4 x5 0 0 0 0 3 5 0 0 0 12/2=6 36/4=9 SHUFE 14 表格單純形法 8 1 0 1 0 0 6 0 1 0 1/2 0 12 3 0 0 2 1 x3 x2 x5 0 5 0 30 3 0 0 5/2 0 8 4 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 3 5 0 0 0 檢驗(yàn)數(shù) ?j 4 0 0 1 2/3 1/3 6 0 1 0 1/2 0 4 1 0 0 2/3 1/3 x3 x2 x1 0 5 3 42 0 0 0 1/2 1 最優(yōu)解 :X*=(4,6,4,0,0)T， Z*=42 SHUFE 15 表格單純形法 ? 最優(yōu)基 Cj 3 5 0 0 0 比 值 CB XB b x1 x2 x3 x4 x5 0 x3 4 0 0 1 2/3 1/3 5 x2 6 0 1 0 1/2 0 3 x1 4 1 0 0 2/3 1/3 檢驗(yàn)數(shù) ?j 42 0 0 0 1/2 1 ???????????340020101*Bx3 x2 x1 ????????????????????313200210313211*B? 最優(yōu)基的逆 ? 最優(yōu)基和最優(yōu)基的逆 SHUFE 擴(kuò)展題 16 下表是某求極大化線性規(guī)劃問題計(jì)算得到的單純形表。試說明這些常數(shù)分別取何值時(shí)，以下結(jié)論成立。 SHUFE 17 基 b 1x 2x 3x 4x 5x 6x 3x d 2 1a 1 0 2a 0 4x 2 3 2 0 1 2 0 6x 3 3a 1 0 0 3 1 jjcz? 1c 2c 0 0 1 0 SHUFE 18 對偶理論 ? 對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純型法表中，初始基變量的檢驗(yàn)數(shù)的負(fù)值。 ? 對偶變量的值 y
公司管理相關(guān)推薦
鄂ICP備17016276號-1