運籌學(xué)：1 緒論 2 線性規(guī)劃

1、 研究的問題是：設(shè)計將雷達信息傳送到指揮系統(tǒng)和武器系統(tǒng)的最佳方式；雷達與武器的最佳配置；對探測、信息傳遞、作戰(zhàn)指揮、戰(zhàn)斗機與武器的協(xié)調(diào)，作了系統(tǒng)的研究，并獲得成功?！?B l a c k e t t 馬 戲 團 ” 在 秘 密 報 告 中 使 用 了“Operational Research”，即“運籌學(xué)”。 “二戰(zhàn)二戰(zhàn)”范例范例大西洋反潛戰(zhàn)（1942年） 1942年，美國大西洋艦隊反潛戰(zhàn)官員W.D.BAKER艦長請求成立反潛戰(zhàn)運籌組，麻省理工學(xué)院的物理學(xué)家P.W.MORSE被請來擔任計劃與監(jiān)督。MORSE 出色的工作之一，是協(xié)助英國打破了德國對英吉利海峽的封鎖。1941-1942年，德國潛艇

2、嚴密封鎖了英吉利海峽，企圖切斷英國的“生命線”。海軍幾次反封鎖，均不成功應(yīng)英國要求，美國派MORSE率領(lǐng)一個小組去協(xié)助。MORSE經(jīng)過多方實地考察，最后提出了兩條重要建議： 將反潛攻擊由反潛潛艇投擲水雷，改為飛機投擲深水炸彈。起爆深度由100米左右改為25米左右。即當潛艇剛下潛時攻擊效果最佳。(提高效率4-7倍) 運送物資的船隊及護航艦隊編隊，由小規(guī)模多批次，改為加大規(guī)模、減少批次，這樣，損失率將減少。（25%下降到10%）。 丘吉爾采納了MORSE的建議，最終成功地打破封鎖，并重創(chuàng)了德國潛艇。MORSE同時獲得英國和美國的最高勛章。( ,)( ,)0ijkijkoptVF x y uG x

3、y u最優(yōu)化的目標函數(shù)：約束條件如果把運籌學(xué)及相關(guān)內(nèi)容比作一棵大樹，則大樹的主干就是“最優(yōu)化”。 大樹的根系是其基礎(chǔ)科學(xué)，大樹的分枝是在各個角度和方向上的最優(yōu)化，大樹的茂密枝葉是其豐富的內(nèi)容，而大樹的果實則是運籌學(xué)在各個領(lǐng)域中的應(yīng)用成果。一個線性不等式確定一個半平面一個線性不等式確定一個半平面如不等式如不等式 ( E ) x1 + x2 300 確定的半平面為確定的半平面為x1x2100300300100200200 x1 + x2 = 300 x1 + x2 300Ex1x2x20 x2=0 x1x2x10 x1=05個半平面的交得到可行域個半平面的交得到可行域EF1002003001002

4、00300GABCz = 50 x1+100 x2=275000Dz = 50 x1+100 x2=10000z = 50 x1+100 x2=20000例、例、max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0解：解：(1)、確定可行域、確定可行域 X1 0 0 X1 =0=0 ( (縱縱) ) X2 0 0 X2=0=0 ( (橫橫) ) X1+2X2 30 X1+2X2 =30 (0,15) (30,0)2030100102030X2DABC3X1+2X2 =60(0,30) (20,0) 2X2 =24(2)、求最優(yōu)解、求最優(yōu)

5、解解：解：X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C點：點： X1+2X2 =30 3X1+2X2 =600203010102030X1X2DABC可行域目標函數(shù)等值線最優(yōu)解64-860 x1x2max z=x1+3x2s.t.x1+ x26-x1+2x28x1 0, x20啟示啟示: :(1)(1)、LP問題的約束集合問題的約束集合( (可行域可行域) )是凸集是凸集( (凸多邊形凸多邊形) )。(2)(2)、若有最優(yōu)解，定可在凸多邊形的頂點得到。、若有最優(yōu)解，定可在凸多邊形的頂點得到。凸集凸集不是凸集頂點最優(yōu)解

6、是唯一解最優(yōu)解是唯一解；x2504030201010203040 x1x2504030201010203040 x1Q1（25，0）Q2（15，20）x2504030201010203040 x1例例 max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 00Z= 40 X1 + 80X2 =0 X1 + 2X2 =30DABCX2X1最優(yōu)解：最優(yōu)解：BC線段線段 max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0無界無界無有限最優(yōu)解無有限最優(yōu)解例、例、 max Z=2X1+ 4X

7、2 2X1+X2 8 8-2X1+X2 2X1 , X2 0 0Z=02X1+ X2=8-2X1+ X2=28246X240X1例、例、 max Z=3X1+2X2 -X1 -X2 1 1X1 , X2 0 0無解無解無可行解無可行解-1X2-1X10線性規(guī)劃的標準形式有如下四個要求：線性規(guī)劃的標準形式有如下四個要求： 目標最大化目標最大化 約束方程為等式約束方程為等式 決策變量為非負決策變量為非負 右端項為非負右端項為非負 對于各種非標準形式的線性規(guī)劃問題，我們對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標準形式總可以通過以下變換，將其轉(zhuǎn)化為標準形式: : 1.極小化

8、目標函數(shù)的問題：極小化目標函數(shù)的問題：設(shè)目標函數(shù)為設(shè)目標函數(shù)為 min f = c1x1 + c2x2 + + cnxn (可以可以)令令 z - f ，則該極小化問題與下面的極大化問題有相同的最優(yōu)解，則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即即 max z = - c1x1 - c2x2 - - cnxn 。 但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標函數(shù)值卻相差一個符號，即們最優(yōu)解的目標函數(shù)值卻相差一個符號，即 min f - max z 。目標函數(shù)目標函數(shù)xoZ-Z2. 約束條件不是等式的問題：約束條件不是等式的問題

9、：設(shè)約束條件為設(shè)約束條件為 ai1 x1 + ai2 x2 + + ain xn bi可以引進一個新的變量可以引進一個新的變量 s ，使它等于約束右邊與左邊，使它等于約束右邊與左邊之差之差 s = bi (ai1 x1 + ai2 x2 + + ain xn ) 。顯然，顯然，s 也具有非負約束，即也具有非負約束，即 s0 ，這時新的約束條，這時新的約束條件成為件成為 ai1 x1 + ai2 x2 + + ain xn + s = bi 。當約束條件為當約束條件為 ai1 x1+ai2 x2+ +ain xn bi時，類似地令時，類似地令 s = (ai1 x1+ai2 x2+ +ain x

10、n) - bi 。顯然，顯然，s 也具有非負約束，即也具有非負約束，即s0，這時新的約束條，這時新的約束條件成為件成為 ai1 x1+ai2 x2+ +ain xn - s = bi 。 為了使約束由不等式成為等式而引進的變量為了使約束由不等式成為等式而引進的變量 s 當不等式為當不等式為“小于等于小于等于”時稱為時稱為“松弛變量松弛變量” 當不等式為當不等式為“大于等于大于等于”時稱為時稱為“剩余變量剩余變量” 如果原問題中有若干個非等式約束，則將如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標準形式時，必須對各個約束引進不其轉(zhuǎn)化為標準形式時，必須對各個約束引進不同的變量，有時也將它們統(tǒng)稱為同

11、的變量，有時也將它們統(tǒng)稱為松弛變量松弛變量。 例：例：將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式 min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1，x2，x3 0 解：首先解：首先, , 將目標函數(shù)轉(zhuǎn)換成極大化：令將目標函數(shù)轉(zhuǎn)換成極大化：令z = -f = -3.6x1 + 5.2x2 - 1.8x3 其次考慮約束，有其次考慮約束，有 2 個不等式約束，引進松弛變量個不等式約束，引進松弛變量 和剩余變量和

12、剩余變量 x4，x5 0。于是，我們可以得到以下標于是，我們可以得到以下標準形式的線性規(guī)劃問題：準形式的線性規(guī)劃問題： max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s. t. 2.3x1 + 5.2x2- 6.1x3 + x4 = 15.7 4.1x1 + 3.3x3 - x5 = 8.9 x1 + x2 + x3 = 38 x1，x2，x3，x4，x5 0 。3. 變量無符號限制的問題：變量無符號限制的問題：在標準形式中，必須每一個變量均有非負約束。當在標準形式中，必須每一個變量均有非負約束。當某一個變量某一個變量 xj 沒有非負約束時，可以令沒有非負約束時，可以令

13、 xj = xj - xj”其中其中 xj0， xj”0即用兩個非負變量之差來表示一個無符號限制的變即用兩個非負變量之差來表示一個無符號限制的變量，當然量，當然 xj 的符號取決于的符號取決于xj 和和 xj” 的大小的大小。4.右端項有負值的問題：右端項有負值的問題： 在標準形式中，要求右端項必須每一個分在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數(shù)為負時，如量非負。當某一個右端項系數(shù)為負時，如 bi0，則把該等式約束兩端同時乘以則把該等式約束兩端同時乘以- -1，得到：，得到： - ai1 x1 - ai2 x2 - - ain xn = -bi 例例: 將以下線性規(guī)劃問題

14、轉(zhuǎn)化為標準形式將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式 min f = -3 x1 + 5 x2 + 8 x3 - 7 x4 s. t. 2 x1 - 3 x2 + 5 x3 + 6 x4 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1，x3，x4 0解：首先，解：首先，將目標函數(shù)轉(zhuǎn)換成極大化將目標函數(shù)轉(zhuǎn)換成極大化： 令令 z = -f = 3x15x28x3+7x4 ；其次考慮約束，有其次考慮約束，有 3 個不等式約束，引進個不等式約束，引進 2 個松弛變個松弛變量和量和 1 個剩余變量個剩余變量 x5 , x6 , x7 0 ；由于由于 x2 無非負限制，無非負限制，引入兩個非負變量引入兩個非負變量，可令，可令x2= x2- x2”, 其中其中 x20，x2”0 ；由于第由于第 3 個約束右端項系數(shù)為個約束右端項系數(shù)為 - -58，于是，于是把該式兩端把該式兩端乘以乘以 - -1 。于是，我們可以得到以下標準形式的線性規(guī)劃問題：于是，我們可以得到以下標準形式的線性規(guī)劃問題：max z = 3x1 5x2 + 5x2” 8x3 + 7x4 s. t. 2x1 3x2 + 3x2” + 5x3 + 6x4 + x5 = 28 4x1 + 2x2 - 2x2” + 3x