計算機(jī)算法設(shè)計與分析--第8章線性規(guī)劃與網(wǎng)絡(luò)流-展示頁
2024-10-25 14:35本頁面
【正文】 本變量，等式右邊的變量稱為非基本變量。 ?在求解過程中，應(yīng)當(dāng)將松弛變量與原來變量同樣對待。 ?把 ()或 ()形式的不等式約束轉(zhuǎn)換為等式約束。 2021年 11月 12日 14 約束標(biāo)準(zhǔn)型線性規(guī)劃問題 ?例如： ?此例中， n=6， m=3；基本變量為 ， 和 ；非基本變量為 ， 和 。剩下的nm個變量稱為右端變量或 非基本變量 。 ?在每一約束方程中選擇一個這樣的變量，并以它作為變量求解該約束方程。 ?因?yàn)榭尚袇^(qū)域是凸的且目標(biāo)函數(shù)是線性的，所以局部最優(yōu)實(shí)際上是全局最優(yōu)的。 ?單純形算法以一個線性規(guī)劃作為輸入，輸出它的一個最優(yōu)解。 線性規(guī)劃問題及表示 2021年 11月 12日 8 ?考察包含兩個變量的線性規(guī)劃 最大化： 滿足約束： 21 xx ?0,2251028421212121????????xxxxxxxx 1x2x0102 21 ?? xx225 21 ??? xx84 21 ?? xx 線性規(guī)劃問題及表示 2021年 11月 12日 9 ?考察包含兩個變量的線性規(guī)劃 最大化： 滿足約束： 21 xxz ??0,2251028421212121????????xxxxxxxx 1x2x0421 ?? xx821 ?? xx021 ?? xx 線性規(guī)劃問題及表示 2021年 11月 12日 10 線性規(guī)劃基本定理 ?定理 1： 線性規(guī)劃問題的可行區(qū)域是凸集； ?定理 2：線性規(guī)劃問題有最優(yōu)解的充要條件是它必有一基本可行最優(yōu)解； ?定理 3：若線性規(guī)劃問題有最優(yōu)解，必在可行區(qū)域的某頂點(diǎn)上得到。 ? 有些情況下 可能不存在最優(yōu)解 。 ? 使目標(biāo)函數(shù)取得最值的可行解稱為 最優(yōu)解 。 ? 使約束條件 ()()式中的某 n個約束以等號滿足的可行解稱為線性規(guī)劃問題的 基本可行解 。右邊表格給出這種信息： 政策 市區(qū) 郊區(qū) 鄉(xiāng)村 修路 2 5 3 槍械管理 8 2 5 農(nóng)業(yè)補(bǔ)貼 0 0 10 汽油稅 10 0 2 任務(wù)：如何花費(fèi)最少的錢，去贏得每個選區(qū)至少一半的選票。主要政策有修路、槍械管理、農(nóng)業(yè)補(bǔ)貼以及增加公共運(yùn)輸?shù)钠投?。計算機(jī)算法設(shè)計與分析 Design and Analysis of Computer Algorithms 第八章 線性規(guī)劃與網(wǎng)絡(luò)流 Linear Programming and Network Flow 2021年 11月 12日 2 提綱 一、線性規(guī)劃問題和單純形算法 二、最大網(wǎng)絡(luò)流問題 三、最小費(fèi)用流問題 2021年 11月 12日 3 提綱 一、線性規(guī)劃問題和單純形算法 二、最大網(wǎng)絡(luò)流問題 三、最小費(fèi)用流問題 2021年 11月 12日 4 線性規(guī)劃問題及表示 ?例子：政治家選舉問題 有三種不同類型的選區(qū)：市區(qū)、郊區(qū)和鄉(xiāng)村，這些區(qū)域分別有100 000、 200 000和 50 000個登記選民。一個政治家希望在每一個選區(qū)都贏得大多數(shù)的選票。根據(jù)其競選班子的研究，可以估計通過在某項(xiàng)政策上花費(fèi) 1000美元做廣告，在每個選區(qū)可以贏取或輸?shù)暨x民的千人數(shù)。 2021年 11月 12日 5 線性規(guī)劃問題及表示 ?問題表示 設(shè) 、 、 、 分別表示支出在修路、槍械管理、農(nóng)業(yè)補(bǔ)貼以及汽油稅廣告上的千美元數(shù) 目標(biāo)：最小化表達(dá)式 滿足約束： 1x 2x 3x 4x4321 xxxx ???5010082 4321 ????? xxxx1000025 4321 ???? xxxx2521053 4321 ???? xxxx0, 4321 ?xxxx2021年 11月 12日 6 線性規(guī)劃問題及表示 ?一般線性規(guī)劃問題表示 . )(,2,10)(,1)(,1)(,2,1321211211111njxmmmmmkbxammmtbxamibxajnjkjkjnjtjtjnjijij???????????????????????? )(mi nma x1??njjj xc2021年 11月 12日 7 ? 滿足約束條件 ()()式的一組變量值稱為線性規(guī)劃問題的一個 可行解 。 ? 所有可行解構(gòu)成的集合稱為線性規(guī)劃問題的 可行區(qū)域 。 ? 在最優(yōu)解處目標(biāo)函數(shù)的值稱為 最優(yōu)值 。通常有兩種情況： ?(1)根本沒有可行解，即給定的約束條件之間是相互排斥的； ?(2)目標(biāo)函數(shù)沒有極值，也就是說在 n 維空間中的某個方向上，目標(biāo)函數(shù)值可以無限增大或減小，而仍滿足約束條件，此時目標(biāo)函數(shù)值無界。 2021年 11月 12日 11 單純形及單純形算法 ?如果有 個變量，每個約束定義了 維空間中的一個半空間，這些半空間的交集形成的可行區(qū)域稱作單純形。它從單純形的某個頂點(diǎn)開始，執(zhí)行一系列迭代，在每次迭代中，它沿著單純形的一條邊從當(dāng)前頂點(diǎn)移動到一個目標(biāo)值大于（或小于）當(dāng)前頂點(diǎn)的相鄰頂點(diǎn)，當(dāng)達(dá)到一個局部的最優(yōu)值時，單純形算法結(jié)束。 nn2021年 11月 12日 12 約束標(biāo)準(zhǔn)型線性規(guī)劃問題 ?標(biāo)準(zhǔn)型線性規(guī)劃： . )(,2,10)(,2,11njxmibxajnjijij????????)(m a x1??njjj xc2021年 11月 12日 13 約束標(biāo)準(zhǔn)型線性規(guī)劃問題 ?在標(biāo)準(zhǔn)型線性規(guī)劃問題中，如果每一個等式約束中，至少有一個變量的系數(shù)為正，且這個變量只在該約束中出現(xiàn)。這樣選出來的變量稱為左端變量或 基本變量 ，其總數(shù)為 m個。 ?這一類特殊的標(biāo)準(zhǔn)型線性規(guī)劃問題稱為 約束標(biāo)準(zhǔn)型線性規(guī)劃問題 。 532 23m a x xxxz ????10834124272353263245321???????????xxxxxxxxxxx6,5,4,3,2,10 ?? ix i1x2x 3x4x6x 5x2021年 11月 12日
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1