這是用戶在 2024-7-28 11:42 為 https://app.immersivetranslate.com/pdf-pro/79640435-772a-40d8-a81b-5f9a9028e09c 保存的雙語快照頁面,由 沉浸式翻譯 提供雙語支持。了解如何保存?
2024_07_28_89334a39736be02ae257g

CSE392/CSE39284
L2 - Linear Programming
CSE392/CSE39284
L2 - 線性編程

Dr Tony Sze Tony Sze 博士

Lecture 2
Linear Programming
第2 講
線性規劃

■ Content 內容
  • Two variables linear inequalities.
    兩變量線性不等式
  • 2D Linear programming: geometric approach.
    二維線性規劃:幾何方法。
  • Geometric introduction to the Simplex method.
    簡約法的幾何介紹。
  • Simplex Method. 單工法

Lecture 2 第二講

Linear Programming 線性規劃

  • Objective of this lecture
    本講座的目的
  • Graph the solution set for a system of linear inequalities.
    繪製線性不等式系統的解集。
  • Construct a mathematical model in linear programming and solve it graphically.
    建構線性規劃數學模型,並以圖形方式求解。
  • Learn Simplex method. 學習單純形法。
  • Solve linear programming using simplex method.
    使用單純形法求解線性規劃。

2D Linear Inequalities 二維線性方程

  • Consider the vertical line .
    請看垂直線
  • Any points on the Left hand side of the red line has value:
    紅線左側的任何點都有價值:
  • .
  • Any points on the right hand side of the
    右側的任何點

red line has value: 紅線有價值:
  • .

2D Linear Inequalities 二維線性方程

  • Consider the 考慮到
Inequalities Horizontal line .
不等式水平線
  • Any points above the red line has value:
    任何高於紅線的點都有價值:
  • .
  • Any points below the red line has value:
    任何低於紅線的點都有價值:
  • .

2D Linear Inequalities 二維線性方程

Equation divides the planes Inequalities into 3 regions:
等式 平面不等式分為3 個區域:
means a line  表示一行
means a region, a plane with a boundary .
指一個區域,一個有邊界的平面。

2D Linear Inequalities 二維線性方程

How do you see it?
你怎麼看?
Inequalities 不平等
rearrange  重排
then plot the line on a graph.
然後將該線繪製在圖表上。
For any given value of x , there is exactly 1 value for such that lies on the line.
對於x 的任何給定值, 恰好有1 個值,使得 位於直線上。

2D Linear Inequalities 二維線性方程

Inequalities 不平等
For the same x and smaller values of , the point will be below the line, since .
對於相同的x 和較小的 值,點 將位於直線下方,因為 .
Thus the lower half plan corresponds to the solution of the inequality .
因此,下半部平面圖對應於不等式 的解。
Similarly the upper plane corresponds to
同樣,上平面對應於
.

2D Linear Inequalities 二維線性方程

Note that there are altogether 4 types of inequalities for one line:
請注意,一條直線共有4 種不等式:
  1. the lower plane together with the line
    下平面連同直線
  2. lower plane without the line
    下平面,不含線
  3. upper plane together with the line
    上平面連線
  4. upper plane without the line
    不含線的上平面

Example 範例

  • the red line is 紅線是
  • substitute  代替
  • is  
  • thus the side with 因此
  • is  
  • Thus the upper plane is
    因此,上平面為

Exercise 運動

  • Simultaneous inequalities:
    同時不等式
  • where is the region with
    的區域
Inequalities 不平等

common region 共同區域

Check 檢查

  • Check the region by picking a test point. Choose the point
    選取一個測試點,檢查該區域。選擇
Inequalities 不平等
  • but 0 is  但0 是
  • thus the point 因此
  • belongs  屬於
  • to the region. 對該地區的影響。
  • Try  試試

Exercise 運動

  • Check the region by picking a test point. Choose the point )
    選取一個測試點來檢查該區域。選擇點 )
Inequalities 不平等
  • but 10 is  但10 是
  • thus the point 因此
  • does not  沒有
  • belong to the 屬於
  • region. 地區

Exercise 運動

  • Simultaneous inequalities:
    同時不等式
  • where is the region with Inequalities
    這裡是不等式的區域

Reverse shaded region 反陰影區域

  • We can also reverse the shading
    我們還可以反轉陰影
Inequalities 不平等

Corner Points 角點

Exercise 運動

  • Simultaneous inequalities:
    同時不等式
  • where is the region with
    的區域
  1. (means right side of axis)
    (指 軸的右側)
  2. (means above axis)
    (指 軸上方)
(4) & (5) restrain the solution to first quadrant.
(4) & (5) 將解法限制在第一象限。

Exercise 運動

Inequalities 不平等

Bounded and unbounded solution
有界和無界解決方案

region 地區
A solution region is bounded if it can be enclosed within a circle. Otherwise it is unbounded.
如果一個解區可以被圈在一個圓內,那麼它就是有界的。否則就是無界。

Linear Programming in two Dimensions
二維線性規劃

Linear Programming problem
線性規劃問題

A manufacturer of fire extinguishers makes 2 models. Water (type A) and (type B)
某滅火器製造商生產2 種型號的滅火器。水型(A 型)和 型(B 型)
Each A requires 1 hour from filling, 3 hrs from assembly.
每個A 需1 小時填充,3 小時組裝。
Each B requires 2 hrs from filling, 4 hrs from assembly.
每個B 從填充開始需要2 小時,從組裝開始需要4 個小時。
The maximum hrs available are 32 hr filling and 84 hr assembly.
可利用的最長時間為32 小時填充和84 小時組裝。
Profit: $50 on A and on B.
利潤:A 上50 美元,B 上 美元。
How to max the profit? Assume all can be sold
如何獲得最大利潤?假設可以全部​​售出

Linear Programming problem
線性規劃問題

Let be the no of per day and
為每天的 次數,且
be the no of per day.
是每天的 數量。
The profit is  利潤為
The profit P is called the objective function
利潤P 稱為目標函數
Constraints: 限制因素:
  1. ,
  2. , (positive production)
    ,(積極生產)
  3. (filling department)
    (填充部門)
  4. (assembly department)
    (裝配部門)

Linear Programming problem
線性規劃問題

  • that is the intersection of two boundary lines.
    即兩條邊界線的交點。
Fire Extinguisher Manufacturing
滅火器製造

Region of contraints 限制區域

  1. Draw the lines of all 5 constraints.
    畫出所有5 條約束線。
  2. Find the region of each constrain.
    找出每個約束的區域。
  3. Find the intersection regions (feasible region).
    找出交叉區域(可行區域)。
  4. Any points in the feasible region is achievable. e.g. is a point inside the region. The profit is then
    例如, 是可行區域內的一個點。那麼利潤為
. Another point (23, 2), P = $1310.
。另一點(23,2),P = 1310 美元。
  1. So different points inside the feasible region are associate with different profit.
    因此,可行區域內的不同點會帶來不同的利潤。

Region of contraints 限制區域

  1. But the question is, out of all the possible points, which combination produces the maximum profit?
    但問題是,在所有可能的點數中,哪一種組合能產生最大的利潤?
  2. It is impossible to test all points.
    不可能對所有要點進行測試。
  3. One way is to assign an arbitrary value to P say , the we can draw one constant profit line.
    一種方法是給P 指定一個任意值,例如 ,這樣我們就可以畫出一條恆定的利潤線。
  4. All points on this line will produce the same profit.
    這條線上的所有點都會產生相同的利潤。

Region of contraints 限制區域

  1. By varying P we can draw a few constant profit lines e.g. , 2000 etc.
    透過改變P,我們可以畫出幾條恆定的利潤線,例如 、2000 等。
  2. Observe that all these constant profit lines are parallel to one another.
    請注意,所有這些恆定利潤線都相互平行。
  3. If we convert P lines into slope intercept form: .
    如果我們將P 直線轉換成斜率截距形式,那麼
  4. the slope is and the intercept is
    斜率為 截距為

Maximizing Profit 利潤最大化

- Constant Profit lines - 恆定利潤線

Tent Manufacturing 帳篷製造

Region of contraints 限制區域

  1. When we look at the constant profit lines, the profit increase as the lines move up.
    當我們觀察恆定利潤線時,利潤會隨著利潤線的上移而增加。
  2. The line with the largest P that coincide with the feasible region is exactly at the point where and meet.
    與可行區域重合的最大P 的直線恰好位於 點,即 相交處。
  3. .
  4. is called the optimal solution
    稱為最優解

Summary of the Procedures
程序概要

Step 1: Introduce Decision Variables
步驟1:引入決策變量
Step 2: Summarize relevant material in table form, relating the decision variables with the columns in the table
步驟2:以表格形式彙整相關資料,將決策變數與表格中的各欄位連結起來
Step 3: Determine the objective and write a Linear Objective Function
步驟3:確定目標並編寫線性目標函數
Step 4: Write problem constraints using
步驟4:使用
linear equations and/or inequalities
線性方程式和/或不等式
Step 5: Write non-negative constraints
步驟5:編寫非負約束條件
Second Example Farmer's Product Food A $0.02/lb, food B $0.04/lb. A contains 3000 nutrient
第二個例子農民產品A 食品0.02 美元/磅,B 食品0.04 美元/磅。 A 含有3000 種營養
B contains 4000 nutrient chicks needs /day How many lbs of A and B to minimize cost?
B 含有4000 種營養物質 雛雞每天需要 多少磅A 和B 才能讓成本最小化?

Four steps to construct the mathematical model
建構數學模型的四個步驟

Step 1: Define the Decision Variables
步驟1:確定決策變數

Let be the no of A per day and be the no of B per day.
為每天A 的次數, 為每天B 的次數。
Step 2: Summarize relevant data in a table
第2 步:用表格匯總相關數據
Product 產品

Minimum Daily 要求
Minimum
Daily
requirement
3000 4000 36000

營養素 N2
Nutrient
N2
1000 4000 20000

Step 3: Determine the objective and the Objective Function
Minimize
步驟3:確定目標和目標函數
最小化

Step 4: Write the constraints
步驟4:編寫約束條件
  1. ,
  2. , (positive production)
    ,(積極生產)

Four steps of Geometric Solution
幾何解法的四個步驟

Step 1: Graph the feasible region. If an optimal solution exists, find the coordinates of each corners.
步驟1:繪製可行區域圖。如果存在最優解,則找出每個角的座標。
Step 2: Construct a corner point table listing the value of the objective function at each corner point.
步驟2:建立角點表,列出每個角點的目標函數值。
Step 3: Determine the optimal solution from the table.
步驟3:從表格中決定最優解。
Step 4: Interpret the optimal solution in terms of the original applied problem.
步驟4:依原應用問題解釋最優解。

Geometric Method 幾何方法

Intersection of two boundary lines
兩條邊界線的交點

Geometric method 幾何方法

Corner Table 轉角桌


目標函數
Objective function
per day  每天
per day  每天
per day  每天

Introduction to Simplex Method
單純形法簡介

Standard Maximization Problem
標準最大化問題

When the number of variables is more than two, it is difficult to find the feasible region by graphs.
當變數數量超過兩個時,很難透過圖形找到可行區域。
We need to turn to algebraic method.
我們需要使用代數方法。
Standard Maximization Problem
標準最大化問題
A linear programming problem is said to be a standard maximization problem in standard form if its model is:
如果一個線性規劃問題的模型是這樣的,那麼它就是一個標準形式的最大化問題:
Maximize the objective function:
最大化目標函數
subject to problem constraints:
問題的限制條件:
and all  和所有

Convert inequalities into equations
將不等式轉換為方程

Add a slack variable :
新增一個鬆弛變數
e.g. is a point inside the feasible
例如, 是可行範圍內的一點。
however, = 32 .
但是, = 32 。

Basic and Non-basic variables
基本變數和非基本變數

The new system involve 2 equations and 4 variables.
新系統涉及2 個方程式和4 個變數。
We divide the variables into 2 groups: basic and nonbasic variables.
我們將變數分為兩組:基本變數和非基本變數。

Basic and Non-basic variables
基本變數和非基本變數

Basic variables are selected arbitrarily up to the number of the equations.
基本變數可任意選擇,但不得超過方程式的數量。
The remaining variables are nonbasic variables.
其餘變數為非基本變數。
A solution found by setting the nonbasic variables equal to 0 and solve for the other basic variables is a basic solution.
將非基本變數設為0 並求解其他基本變數的解就是基本解。

Basic and Non-basic variables
基本變數和非基本變數

(1) select as basic, then are non basic.
(1) 選擇 為基本,則 為非基本。
(2) set , then
(2) 設定 ,則
(3) the basic solution is
(3) 基本解為

Basic and Non-basic variables
基本變數和非基本變數

(1) select as basic, then are non basic.
(1) 選擇 為基本,則 為非基本。
(2) set , then
(2) 設定 ,則
(3) the basic solution is
(3) 基本解決方案是

Basic and Non-basic variables
基本變數和非基本變數

You can try all combination of basic/nonbasic variables.
您可以嘗試所有基本變數/非基本變數的組合。
Actually you are evaluating at the intersection points of the 4 lines:
實際上,您是在4 條線的交叉點進行評估:

Basic Solution 基本解決方案

Basic & Nonbasic Variables
基本變數和非基本變數

Basic Solutions 基本解決方案


Intersection point
Intersection
point
Intersecting lines 相交線 feasible 可行
0 0 32 84
yes 
0 16 0 20
yes 
0 21 -10 0
No 沒有
32 0 0 -12
no 沒有
28 0 4 0
yes 
20 6 0 0
yes 

Basic and Non-basic Variables
基本變數和非基本變數

The intersection point is within the feasible region, it is called a feasible solution.
交點 在可行區域內,稱為可行解。
Also when one of the basic non basic variables is zero that the solution is not feasible.
此外,當一個基本變量 非基本變數為零時,解也不可行。
The basic feasible solutions are all associated with the corners of the feasible region.
基本可行解都與可行區域的四角有關。
which one or more are the optimal solutions.
其中一個或多個是最優解。

Basic and Non-basic Variables
基本變數和非基本變數

Given a system of linear equations associated with a linear programming problem (variables > no of equations),
給定一個與線性規劃問題相關的線性方程組(變數> 方程個數)、
The variables are divided into basic and nonbasic.
變數分為基本變數和非基本變數。
A solution found by setting the nonbasic variables to 0 and solving for the basic variables is called a basic solution. If a basic solution has no negative value, it is a basic feasible solution.
將非基本變數設為0 並求解基本變數的解稱為基本解。如果基本解沒有負值,它就是基本可行解。

Theorem 定理

If the optimal value of the objective function in a linear programming problem exists, that that value must occur at one (or more) of the basic feasible solutions.
如果線性規劃問題中存在目標函數的最優值,那麼該值必須出現在一個(或多個)基本可行解中。
This method identifying all the corner points of a feasible region without drawing its graph.
這種方法無需繪製可行區域的圖形,即可識別該區域的所有角點。
Next step is to find a method that do not require all corners to be evaluated.
下一步是找到一種不需要評估所有角落的方法。

Simplex Method 簡約法

Simplex Method 簡約法

System A: 系統A:
Maximize with constraints:
在有約束條件的情況下最大化
Form a new set of system B:
形成一套新的系統B:
,

Simplex Method 簡約法

  • The method is to find one easy basic solution.
    方法是找到一個簡單的基本解決方案。
  • Starting with this easily obtained initial basic feasible solution, the Simplex method moves through each iteration to another basic feasible solution until the optimal solution is reached. Then the process stops.
    從這個容易得到的初始基本可行解開始,單純形法每次迭代都會得到另一個基本可行解,直到達到最佳解為止。然後過程停止。

Simplex Tableau 簡單表格

Simplex Tableau 簡單表格

  • Objective function P is always on the bottom row.
    目標函數P 總是位於最下面一行。
  • When , P are selected as basic variables, each basic variable is within a column that has all 0 except a single 1 and that no 2 such columns contain 1 in the same row.
    、P 被選為基本變數時,每個基本變數都位於一列中,這一列中除了一個1 之外都是0,並且在同一行中沒有2 個這樣的列包含1。

Simplex Procedures 簡易程式

  • Given a simplex tableau 給定一個單純形表
  • Determine the number of basic variables and no of nonbasic. These nos do not change during the simplex process.
    確定基本變數的數量和非基本變數的數量。這些變數的個數在單純形過程中不會改變。
  • Select basic variables. Such a basic variable can only correspond to a column in the tableau that has exactly one nonzero element and the nonzero element is not in the same row as the nonzero element in the column of another basic variable.
    選擇基本變數。這樣的基本變數只能對應於表中的一列,而這一列恰好有一個非零元素,且該非零元素與另一個基本變數列中的非零元素不在同一行。
  • Select the remaining as nonbasic variables.
    將其餘變數選為非基本變數。

Pivot Operations 支點操作

  • After making the tableau, we try to switch one nonbasic variable with a basic variable by performing row operations.
    製作完表格後,我們嘗試透過行操作將一個非基本變數與一個基本變數進行切換。
  • We try to turn 1 column into zero and 1.
    我們嘗試把1 列變成0 和1。
  • There is a specific procedure to follow
    有具體的程序可循

Pivot Operations 支點操作

  • Locate the most negative indicator in the bottom row. The column containing this indicator is selected as the pivot column. If 2 same no, any one will do.
    找出最下面一行中最負的指標。包含此指標的欄位被選為樞軸列。如果2 個相同,則任何一個都可以。
  • Row operation: Divide the last column element by the positive element in the pivot column. Repeat for all rows
    行操作:以最後一列元素除以樞軸列中的正元素。對所有行重複操作
  • Select the row with the minimum quotient as pivot row.
    選擇商最小的一行作為樞軸行。
  • If the pivot column above the dashed line has no positive elements, there is no solution, we can stop.
    如果虛線上方的樞軸列沒有正元素,則沒有解,我們可以停止。

Pivot Operations 支點操作

  • The pivot is the element in the intersection of the pivot column and pivot row.
    樞軸是樞軸列和樞軸行交叉處的元素。
  • The pivot is always positive and never in the bottom row.
    樞軸永遠為正,且從不位於底行。
  • The entering variable is at the top of the pivot column and the exiting variable is at the left of the pivot row.
    輸入變數位於透視列的頂部,輸出變數位於透視行的左側。

Pivot Operations 支點操作

  • We are trying to perform row operation so that the pivot element is transformed into 1 and all other elements in the pivot column to 0 so that we switch one non basic variable with a basic variable.
    我們正在嘗試執行行操作,以便將樞軸元素轉換為1,將樞軸列中的所有其他元素轉換為0,從而將一個非基本變數轉換為基本變數。
  • Step 1: multiply the pivot row by the reciprocal of the pivot element to transform the pivot element into 1.
    步驟1:將樞軸行乘以樞軸元素的倒數,將樞軸元素轉換為1。
  • Step 2: Linearly combine different rows to convert all nonzero elements in the pivot column to zero.
    步驟2:線性組合不同行,將樞軸列中所有非零元素轉換為零。

swapped with as
互換,因為
basic variable. 基本變數。
  • Now return to the maximization problem
    現在回到最大化問題
  • When , profit
    時,利潤
■ When , profit
時,利潤
  • is not the maximum profit because there is still a -10 in the bottom row. We have to continue the process.
    不是最大利潤,因為最下面一行還有一個-10。我們必須繼續這個過程。
-10 is most negative -10為最負
20 is , so 1 is the pivot
20 是 ,因此1 是樞軸
 
swapped with as
互換,因為
basic variable. Make pivot 1
基本變數。樞軸 1
make other 0 將其他 0
  • When , profit
    時,利潤
  • Since there is no more negative indicators on the bottom row, we can stop. 1480 must be the maximum profit.
    由於下檔已無負面指標,我們可以停損。 1480 必須是最大利潤。
■ Reasons: The last row becomes:
原因:最後一行變成
 
  • Since and are positive numbers. Max P is at
    因為 都是正數。最大P 在

Geometric Interpretation 幾何解讀

  • The simplex process started at , moved to the adjacent corner , and then to the optimal solution at the next corner point.
    單純形過程從 開始,移動到相鄰角點 ,然後移動到下一個角點的最優解
Basic & Nonbasic Variables
基本變數和非基本變數

Pivot Operations 支點操作

  • When to stop? 何時停止?
  • When there is no negative indicators on the bottom row. Solution found!
    當底行沒有負指示符時。找到解決方案!
  • When there is no positive elements in the pivot column above the dashed line. The problem has no solution.
    當虛線上方的樞軸列沒有正元素時。問題無解。
Example 範例

Example 範例

Example 範例
  • When , profit
    時,利潤

End of Lecture 2 第2 講結束

You have learnt the Linear Programming
您已學會線性規劃

Next lecture we will start a new series of lectures in Elementary Statistics.
下一堂課,我們將開始新的初級統計學系列講座。