管理系統優(yōu)化ppt課件(編輯修改稿)
2025-02-06 04:09 本頁面
【文章內容簡介】 ignment Problem） 市政府有四項市政建設工程招標。經過初選，四家建設公司最后參與這四項工程競標。每家公司對每個工程的報價如下表所示： 報價（萬元） 工程 A 工程 B 工程 C 工程 D 甲公司 920 480 650 340 乙公司 870 510 700 350 丙公司 880 500 720 400 丁公司 930 490 680 410 市政府規(guī)定，每項工程只能有一家公司中標，每家公司只能承擔一項工程。求總價最低的決標方案。設： ????jijixij 承接工程公司不承接工程公司10max =920x11+480x12+650x13+340x14+870x21+510x22+700x23+350x24+ 880x31+500x32+720x33+400x34+930x41+490x42+680x43+410x44 . x11+x12+x13+x14=1 甲公司只能中標一項工程 x21+x22+x23+x24=1 乙公司只能中標一項工程 x31+x32+x33+x34=1 丙公司只能中標一項工程 x41+x42+x43+x44=1 丁公司只能中標一項工程 x11+x21+x31+x41=1 工程 A只能由一家公司承接 x12+x22+x32+x42=1 工程 B只能由一家公司承接 x13+x23+x33+x43=1 工程 C只能由一家公司承接 x14+x24+x34+x44=1 工程 D只能由一家公司承接 xij=0,1 01變量約束 決策變量 工程 A 工程 B 工程 C 工程 D 甲公司 x11 x12 x13 x14 乙公司 x21 x22 x23 x24 丙公司 x31 x32 x33 x34 丁公司 x41 x42 x43 x44 最優(yōu)解為： x13=1， x24=1， x31=1， x42=1， max z=2370 甲公司中標工程 C，乙公司中標工程 D，丙公司中標工程 A，丁公司中標工程 B，四個標總價為 2370萬元。 中標 工程 A 工程 B 工程 C 工程 D 甲公司 0 0 1 0 乙公司 0 0 0 1 丙公司 1 0 0 0 丁公司 0 1 0 0 報價 工程 A 工程 B 工程 C 工程 D 甲公司 920 480 650 340 乙公司 870 510 700 350 丙公司 880 500 720 400 丁公司 930 490 680 410 可以看出，每項工程并不是都由報價最低的公司中標。 min(max) z=c1x1+c2x2+……+c nxn . a11x1+a12x2+……+a 1nxn ≥ (≤, ＝ )b1 a21x1+a22x2+……+a 2nxn ≥ (≤, ＝ )b2 …… am1x1+am2x2+……+a mnxn ≥ (≤, ＝ )bm x1, x2, ……, x n ≥0 (≤, Free) 線性規(guī)劃模型的目標函數必須是變量的線性函數，約束條件必須是變量的線性等式或不等式。如右的問題就不是線性規(guī)劃問題： 0x,x,x9x4+x+x8xx+x+xx2+x3=zm i n32132113212121≥≤≤ 線性規(guī)劃問題的基本概念 max z=x1+3x2 . x1+ x2≤6 x1+2x2≤8 x1 ≥0, x2≥0 可行域 目標函數等值線 最優(yōu)解 6 5 4 3 2 1 1 2 3 4 5 6 8 7 6 5 4 3 2 1 0 x1 x2 z=6 z=3 z=9 z=12 問題： 線性規(guī)劃的最優(yōu)解是否可能位于可行域的內部？ 線性規(guī)劃的最優(yōu)解是否可能位于可行域的邊界上？ 線性規(guī)劃的圖解 凸集 凸集 不是凸集 ? 線性規(guī)劃的可行域是凸集 ? 線性規(guī)劃如果有最優(yōu)解，最優(yōu)解至少在可行域的一個極點上 可行域的性質 可行域封閉 唯一最優(yōu)解 可行域封閉 多個最優(yōu)解 可行域開放 唯一最優(yōu)解 可行域開放 多個最優(yōu)解 可行域開放 目標函數無界 無可行解 線性規(guī)劃可行域和最優(yōu)解的幾種情況 用規(guī)劃求解工具求解線性規(guī)劃問題 ?Excel規(guī)劃求解工具 ?Excel規(guī)劃求解報告 ?線性規(guī)劃 Excel規(guī)劃求解模型 Excel中提供了一個求解線性和非線性規(guī)劃的工具。打開菜單：工具 /規(guī)劃求解就可以啟動這個工具。 Excel規(guī)劃求解工具 如果菜單中沒有“規(guī)劃求解”，打開菜單：工具 /加載宏，選定“規(guī)劃求解”。
公司管理相關推薦
鄂ICP備17016276號-1