【正文】 無窮多最優(yōu)解。 ?求解原理：從可行域中的某一頂點開始，逐一進行比較，使目標函數(shù)最優(yōu)的頂點即為最優(yōu)解。 線性規(guī)劃問題基本理論及方法 ?線性規(guī)劃的基本原理 （以例圖解法說明）： ?解的類型： 一定無解 解的結(jié)果 有可行域 無可行域 可行域有界 可行域無界 唯一解 無窮解 唯一解 無窮解 無解 線性規(guī)劃問題基本理論及方法 ?單純形法求解步驟： ? 將線性規(guī)劃模型轉(zhuǎn)化為標準型（目標函數(shù)求極大、約束條件為等式、決策變量大于 0）； ? 找出初始基本可行解（即： m個約束條件中存在 m個單位列向量，組成單位矩陣）； ? 檢驗初始基本可行解是否為最優(yōu)解？（若所有非基變量的檢驗數(shù) σ j≤0 ，則基本可行解為最優(yōu)解）； ? 如果不是最優(yōu)解，進行迭代，求出新的基本可行解。（根據(jù)最小比值原則選擇出基變量和進基變量） ?單純形法計算過程在單純形表中具體實現(xiàn)。 應用 EXCEL工具求解線性規(guī)劃問題 一、在 EXCEL電子表格中建立線性規(guī)劃模型 把相關(guān)數(shù)據(jù)輸入到 EXCEL電子表格中 應用 EXCEL工具求解線性規(guī)劃問題 主要求解結(jié)果 ■ 兩種新產(chǎn)品 x x2每周的產(chǎn)量； ■ 兩種新產(chǎn)品每周各實際使用的工時（不能 超過計劃工時）； ■ 兩種新產(chǎn)品的總利潤 z。 應用 EXCEL工具求解線性規(guī)劃問題 主要結(jié)果的計算方法 （ 1）兩種新產(chǎn)品的每周產(chǎn)量： C1 D12，試驗解為 0。 （ 2）實際使用工時計算 （ 三種方法） ● 分別在 E E E9中輸入相應的計算公式： E7： C7*C12+D7*D12； E8： C8*C12+D8*D12； E9： C9*C12+D9*D12 ● 復制、粘貼方法： 在 E7中輸入： C7*$C$12+D7*$D$12，然后復制 E7單元格到 E E9 ● 公式法： 在 E7中輸入： =SUMPRODUCT（ C7： D7， $C$12， $D$12） 復制 E7單元格到 E E9 應用 EXCEL工具求解線性規(guī)劃問題 （ 3）總利潤計算： 在 G12單元格輸入公式： =C4*C12+D4*D12 或： =SUMPRODUCT（ C4： D4， C12： D12） 應用 EXCEL工具求解線性規(guī)劃問題 ? 收集問題數(shù)據(jù)； ? 在 EXCEL表格中輸入數(shù)據(jù)（ 數(shù)據(jù)單元格 ）； ? 確定決策變量單元格（ 可變單元格 ）； ? 輸入約束條件左邊的公式（ 輸出單元格 ） ,使用 SUMPRODUCT函數(shù)簡化輸入； ? 輸入目標函數(shù)公式（ 目標單元格 ）。使用 SUMPRODUCT函數(shù)簡化輸入。 在 EXCEL中建立線性規(guī)劃模型步驟總結(jié) 應用 EXCEL工具求解線性規(guī)劃問題 二、在 EXCEL電子表格中求解線性規(guī)劃模型 求解參數(shù)設(shè)置： “ 工具 ” —— ”規(guī)劃求解 “ ，彈出 “ 規(guī)劃求解參數(shù) ” 對話框，設(shè)置求解相關(guān)參數(shù)。 應用 EXCEL工具求解線性規(guī)劃問題 約束的設(shè)置： 單擊 “ 添加 ” ，彈出 “ 添加約束 ” ，添加約束條件。 應用 EXCEL工具求解線性規(guī)劃問題 求解選項設(shè)置： 單擊 “ 選項 ” ，彈出 “ 規(guī)劃求解選項 ” 對話框。選擇 “ 采用線性模型 ” 和 “ 假定非負 ” 。 應用 EXCEL工具求解線性規(guī)劃問題 求解及結(jié)果 單擊 “ 求解 ” ，開始規(guī)劃求解。彈出 “ 規(guī)劃求解結(jié)果 ” 對話框。選擇 “ 保存規(guī)劃求解結(jié)果 ” 。 應用 EXCEL工具求解線性規(guī)劃問題 電子表格顯示結(jié)果： 單擊 “ 確定 ” ，在電子表格的可變單元格、輸出單元格及目標單元格出現(xiàn)求解結(jié)果。 ? 輸入數(shù)據(jù) ? 標識數(shù)據(jù) ? 每個數(shù)據(jù)對應唯一單元格 ? 在電子表格中顯示完整模型 ? 數(shù)據(jù)、公式分離 ? 保持簡單化 ? 使用相對和絕對地址簡化公式并復制 ? 使用邊框、底色區(qū)分單元格類型 ? 例 13 建模求解要點回顧 應用 EXCEL工具求解線性規(guī)劃問題 四、線性規(guī)劃問題解的表現(xiàn) EXCEL建模求解，其解的結(jié)果在 “ 規(guī)劃求解結(jié)果 ” 對話框中提示： 唯一最優(yōu)解為 ” 找到一個解 “ 無窮多最優(yōu)解為 ” 滿足條件有多個解 “ 無解為 ” 未找到可行解 “ 線性規(guī)劃問題建模求解實例分析 一、生產(chǎn)計劃問題 例 1： 某工廠生產(chǎn)甲、乙、丙三種產(chǎn)品，都要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，也可自行生產(chǎn)，但產(chǎn)品丙必須在本廠鑄造才能保證質(zhì)量。數(shù)據(jù)見表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品應各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄件應由本公司鑄造和由外包協(xié)作各多少件 ? 線性規(guī)劃問題建模求解實例分析 產(chǎn)品甲 產(chǎn)品乙 產(chǎn)品丙 工時限制 單件鑄造工時（小時） 5 10 7 8000 單件機加工工時（小時） 6 4 8 12023 單件裝配工時（小時） 3 2 2 10000 自產(chǎn)鑄件成本（元 /件） 3 5 4 外協(xié)鑄件成本（元 /件） 5 6 機加工成本（元 /件） 2 1 3 裝配成本（元 /件） 3 2 2 產(chǎn)品售價（元 /件） 23 18 16 線性規(guī)劃問題建模求解實例分析 例 2： 某工廠生產(chǎn) A、 B種產(chǎn)品，均需經(jīng)過兩道工序，每生產(chǎn) 1噸 A產(chǎn)品需要經(jīng)過第一道工序加工 2小時，第二道工序加工 3小時；每生產(chǎn) 1噸 B產(chǎn)品需要經(jīng)過第一道工序加工 3小時，第二道工序加工 4小時。可供利用的第一道工序工時為 15小時；第二道工序工時為 25小時。 生產(chǎn)產(chǎn)品 B的同時可產(chǎn)出副產(chǎn)品 C，每生產(chǎn) 1噸產(chǎn)品 B，可同時得到 2噸產(chǎn)品 C而不需要外加任何費用。副產(chǎn)品 C一部分可以贏利，但剩下的只能報廢，報廢需要有一定的費用。 出售產(chǎn)品 A每噸能贏利 400元；出售產(chǎn)品 B每噸能贏利 800元；出售副產(chǎn)品 C每噸能贏利 300元；當剩余的產(chǎn)品 C報廢時，每噸損失費為 200元。經(jīng)市場預測，在計劃期內(nèi)產(chǎn)品 C的最大銷售量為 5噸。 問：如何安排 A、 B兩種產(chǎn)品的產(chǎn)量可使工廠總盈利最大？ 線性規(guī)劃問題建模求解實例分析 二、生產(chǎn)存儲問題 某公