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

Lecture 2
Linear Programming
第2 講
線性規劃

• 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
  右側的任何點

• .

2D Linear Inequalities 二維線性方程

• Consider the 考慮到

• Any points above the red line has value:
  任何高於紅線的點都有價值：
• .
• Any points below the red line has value:
  任何低於紅線的點都有價值：

• .

2D Linear Inequalities 二維線性方程

2D Linear Inequalities 二維線性方程

2D Linear Inequalities 二維線性方程

2D Linear Inequalities 二維線性方程

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
  的區域

common region 共同區域

Check 檢查

• Check the region by picking a test point. Choose the point
  選取一個測試點，檢查該區域。選擇 點

• but 0 is  但0 是
• thus the point 因此
• belongs  屬於
• to the region. 對該地區的影響。
• Try  試試

Exercise 運動

• Check the region by picking a test point. Choose the point )
  選取一個測試點來檢查該區域。選擇點 )

• 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
  我們還可以反轉陰影

Corner Points 角點

Exercise 運動

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

4. (means right side of axis)
   （指 軸的右側）
5. (means above axis)
   （指 軸上方）

Exercise 運動

Inequalities 不平等

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

region 地區

Linear Programming in two Dimensions
二維線性規劃

Linear Programming problem
線性規劃問題

Linear Programming problem
線性規劃問題

1. ,
2. , (positive production)
   ，（積極生產）
3. (filling department)
   （填充部門）
4. (assembly department)
   （裝配部門）

Linear Programming problem
線性規劃問題

• that is the intersection of two boundary lines.
  即兩條邊界線的交點。

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
   例如， 是可行區域內的一個點。那麼利潤為

5. 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 - 恆定利潤線

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
程序概要

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

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

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

1. ,
2. , (positive production)
   ，（積極生產）

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

Geometric Method 幾何方法

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

Corner Table 轉角桌

Introduction to Simplex Method
單純形法簡介

Standard Maximization Problem
標準最大化問題

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

Add a slack variable :
新增一個鬆弛變數 ：

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

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

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

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

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

Basic Solution 基本解決方案

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

Basic Solutions 基本解決方案

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

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

Theorem 定理

Simplex Method 簡約法

Simplex Method 簡約法

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：線性組合不同行，將樞軸列中所有非零元素轉換為零。

• Now return to the maximization problem
  現在回到最大化問題
• When , profit
  當 時，利潤

• is not the maximum profit because there is still a -10 in the bottom row. We have to continue the process.
  不是最大利潤，因為最下面一行還有一個-10。我們必須繼續這個過程。

• When , profit
  當 時，利潤
• Since there is no more negative indicators on the bottom row, we can stop. 1480 must be the maximum profit.
  由於下檔已無負面指標，我們可以停損。 1480 必須是最大利潤。

• 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.
  單純形過程從 開始，移動到相鄰角點 ，然後移動到下一個角點的最優解 。

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 範例

• When , profit
  當 時，利潤

End of Lecture 2 第2 講結束

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