Linear Programming Problems

Definitions

Decision Variables: Number of each of the things that can be varied

Constraints: 用来创建不等式

Feasible Solution, the region of it called feasible region

Optimal Solution: 在feasible region里的

Formulate the problem

创建问题步骤：

1. Define decision variables(x, y, z, etc.)
2. State the objective(maxmise or minimise)
3. Write the constraints as inequalities

举个书上的例子：

Mrs Cook is making cakes to sell for charity. She makes two types of cake, fruit and chocolate.

Amongst other ingredients, each fruit cake requires 1 egg, 250g of flour and 200g of sugar.

Each chocolate cake requires 2 eggs, 250g of flour and 300g of sugar.

Mrs Cook has 36 eggs, 7 kg of flour and 6 kg of sugar.

She will sell the fruit cakes for £3.50 and the chocolate cakes for £5.

She wishes to maximise the money she makes from these sales.

You may assume she sells all the cakes that she makes.

Formulate this as a linear programming problem.

那么，

let f be the number of fruit cake, c be the number of chocolate cake.

Maximise P = 3.5f + 5c

eggs: f + 2c <= 36
flour: 250f + 250c <= 7000   =>simplifies into f + c <= 29
sugar: 200f + 300c <= 6000   =>simplifies into 2f + 3c <= 60

别忘了Non-nagativity:  f, c >= 0

Graphical Methods

用方格图来查看Feasible Region

注意：大于 小于用虚线， 大于等于 或 小于等于用实线

Locating the Optimal Point

Ruler Method

直尺法是一种用于求解线性规划问题的图解方法，尤其适用于两个变量的情况。步骤如下：

1. 使用直尺找到最优解：
   • 选取一把直尺（或者一条直线），使其与目标函数 Z=ax+by 的等值线平行，即使其斜率等于 −a/b。
   • 在可行区域内平移该直线，寻找其能到达的最远（或最近）点，即最优解所在的位置。
2. 确定最优解：
   • 若目标函数是最大化(Maximise)，则寻找直线能到达的最远边界点。
   • 若目标函数是最小化(Minimise)，则寻找直线能到达的最近边界点。

直尺法的关键是目标函数的斜率，并通过平移找到极值点。

Vertex Testing Method

求出所有顶点（交点）：

• 计算约束直线的交点，这些交点构成可行区域的顶点。

计算目标函数值：

• 将所有顶点的坐标代入目标函数 Z=ax+by 计算值。

选出最优解：

• 若目标函数是最大化，选择 ZZ 值最大的点。
• 若目标函数是最小化，选择 ZZ 值最小的点。

特殊的玩意

有时候， 题目会规定变量为整数

步骤：

1. 先求出最优解（不考虑整数约束）
2. 在可行区域内找出所有满足约束的整数点
3. 计算目标函数值， 在满足整数约束的点中选取最优解

–未完待续–