整數(shù)線性規(guī)劃問題ppt課件-資料下載頁
2025-04-30 18:15本頁面
【正文】 解嗎？ 整數(shù)規(guī)劃問題的可行解集合是它的松弛問題可行解集合的一個(gè)子集 , 因此 整數(shù)規(guī)劃問題的可行解一定是它 的松弛問題 的可行解，反之不一定。 整數(shù)規(guī)劃問題的 最優(yōu)值不會(huì)優(yōu)于 它松弛問題 最優(yōu)值。 例：設(shè)整數(shù)規(guī)劃問題如下 首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為 松弛問題 ）。用圖解法求出最優(yōu)解為： x1＝ 3/2, x2 = 10/3， 且有 Z = 29/6x1x2 ⑴ ⑵33(3/2,10/3)現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法 ”可得到 4個(gè)點(diǎn)即 (1， 3) (2， 3)(1， 4)(2， 4)。顯然，它們都不是整數(shù)規(guī)劃的可行解 ,因而不是最優(yōu)解。按整數(shù)規(guī)劃約束條件，當(dāng)可行解為有界集時(shí)，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)（格點(diǎn)）。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如圖所示。 因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（ 2， 2）（ 3， 1）點(diǎn)為最大值值點(diǎn)， Z=4。域的頂點(diǎn)上達(dá)到 .解 .，枚舉法不可取 .注意 :整數(shù)規(guī)劃問題的求解方法： 目前，常用的求解整數(shù)規(guī)劃的方法有： 割平面法、分支定界法和完全枚舉法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1