優(yōu)化問(wèn)題的算法簡(jiǎn)介

1、20140630-培訓(xùn)三規(guī)劃問(wèn)題 一、線性規(guī)劃1. 等價(jià)于（一）單純形法求解線性規(guī)劃例： 解法一：圖解法解法二：?jiǎn)渭冃畏?表上作業(yè)：，確定主列，確定主列，確定主列因此，（二）西北角法例：運(yùn)輸問(wèn)題B1B2B3B4產(chǎn)量A1293440A2835760A3452520需求量35403025初始解(西北角法)：B1B2B3B4產(chǎn)量A13550040A203525060A30051520需求量35403015位勢(shì)檢驗(yàn)法：B1B2B3B4產(chǎn)量A1× 2×9 -8-1014A212× 3×5 -18A3115× 2×5 5需求量-12-5 -30由

2、公式計(jì)算檢驗(yàn)數(shù)計(jì)算回路法：B1B2B3B4產(chǎn)量A1355-tt40A235+t25-t*60A35+t15-t20需求量35403015B1B2B3B4產(chǎn)量A13500540A204020060A300101020需求量35403015B1B2B3B4產(chǎn)量A1× 2 102×44A22× 3×5 -18A315× 2×5 5需求量-2-5 -30B1B2B3B4產(chǎn)量A13500540A204020060A300101020需求量35403015B1B2B3B4產(chǎn)量A13500540A2040101060A30020020需求量3540

3、3015B1B2B3B4產(chǎn)量A1× 2 91×44A23× 3×5 ×77A325× 2 14需求量-2-4 -20所有檢驗(yàn)數(shù)非負(fù)時(shí)，即得最優(yōu)解（三）行列變換求指派問(wèn)題1、最小化問(wèn)題：ABCD甲215134乙1041415丙9141613丁78119效率矩陣：每行減去其行的最小值，即進(jìn)行行變換，得到，然后每列減去其列最小值，即進(jìn)行列變換，得到，圈零即得最優(yōu)解最優(yōu)解為：4+4+9+11=282、 最大化問(wèn)題：甲乙丙丁 30254032323530363540342728433238最大值最小化行變換 列變換 未圈到零的行打勾，打勾的行有零列處打勾，打勾的列劃線，未打勾的行劃線，（即最小劃線數(shù)），未劃線元素中取最小，并減其他數(shù)擴(kuò)容増零二、整數(shù)規(guī)劃（一）一般整數(shù)規(guī)劃分支定界法 解一：圖解法去掉要求看 求問(wèn)題 定界（下界）對(duì)分支： 可行域?yàn)榭占?空集（二）0-1規(guī)劃問(wèn)題例： 隱枚舉法：考慮松弛問(wèn)題：（不是原問(wèn)題的可行解，但是是上界）按系數(shù)最大分類： （剪掉） 考慮