Linear Programming&Integer Programming | JupyterMou’s Blog

type

status

date

slug

summary

Linear Programming基础笔记

01 Linear programming

Linear programming is a powerful mathematical technique used for optimizing a certain outcome (like profit or cost) given a set of constraints or limitations.

Case Description

raw materials： 3

products: 2, fuel additive and solvent base

production

products	material I(tons)	material II(tons)	material III(tons)
fuel additive	1	2	1
solvent base	0	3	1

profit contribution

products	profit($/unit)
fuel additive	5
solvent base	7

current supply(limited)

material I(tons)	material II(tons)	material III(tons)
6	19	8

goal: to determine the production quantity of the fuel additive and the solvent base that maximizes the total profit contribution.

Step 1: Problem Formulation

describe the problem clearly:

2.1 Describe the Decisions: What are the choices we need to make? In this case, we need to decide on the production quantities.

The quantity of Fuel Additive to produce.

The quantity of Solvent Base to produce.

2.2 Tabulate the Data: to organize the information into a table

Raw Material	Fuel Additive	Solvent Base	Capacity (Tons)
Material I	1	0	6
Material II	2	3	19
Material III	1	1	8
Profit per unit	$5	$7	ㅤ
Decision Variable	F	S	ㅤ

2.3 Describe the Objective: What is the main goal of the problem?

To maximize the total profit for the next production period.

2.4 Describe the Constraints: What are the limitations or restrictions?

The total amount of Material I used cannot exceed its available capacity.

The total amount of Material II used cannot exceed its available capacity.

The total amount of Material III used cannot exceed its available capacity

Step 2: Mathematical Modeling (Translation)

3.1 Define decision variables

Let F = the number(#) of units of Fuel Additive produced.

Let S = the number(#) of units of Solvent Base produced.

3.2 The objective function—the total profit—can be written as:

3.3. The constraints, which represent the limitations on raw materials, are expressed as inequalities:

Subject to (s.t.):

(Material I)

(Material II)

(Material III)

3.4 must include non-negativity constraints, as it is impossible to produce a negative quantity of a product.

(Non-negativity)

Step 3: The Graphical Solution Approach

For problems with two decision variables, we can solve them graphically. We will plot the constraints on a graph with F on the horizontal axis and S on the vertical axis.

4.1 Plot the constraints: We treat each inequality as a line.

Constraint 1: F = 6

Constraint 2: 2F + 3S = 19

Constraint 3: F + S = 8

4.2 Identify the Feasible Region: This is the area on the graph that satisfies all constraints simultaneously, including the non-negativity constraints.

(, )

4.3 Find the Optimal Solution: The optimal solution will lie at one of the corner points (vertices) of the feasible region. We can find it by either plotting the objective function line (an “iso-profit” line) and moving it outwards until it touches the last point of the feasible region.

Figure2: Graphical solution(xinyi.ver)

（想必一定是右图画得更好吧🤣

Step 4: Managerial Report (Backward Translation)

The final step is to translate our mathematical solution back into a practical business recommendation

5.1 Optimal Solution: The optimal decision is to produce 5 units of Fuel Additive and 3 units of Solvent Base.

5.2 Projected Objective Value: This production plan will yield a total

profit of $46.

5.3 Resource Utilization: We can check the usage of each material at the optimal solution (, ).

Material I: Used = 1 × 5 = 5 tons. Available = 6 tons. There is a surplus of 1 ton.

Material II: Used = 2 × 5 + 3 × 3 = 10 + 9 = 19 tons. Available = 19 tons. This material is fully used.

Material III: Used = 1× 5 + 1 × 3 = 8 tons. Available = 8 tons. This material is fully used.

Extended Topics

6.1 Standard Form

In linear programming, it is often useful to convert a model into what is called ”Standard Form”.

Requirements:

All variables must be non-negative.

All constraints must be equalities.

Conversion Method:

For a ”less than or equal to” (≤) constraint, we add a slack variable to the left side. A slack variable represents the unused amount of a resource.

For a ”greater than or equal to” (≥) constraint, we subtract a surplus variable from the left side. A surplus variable represents the amount by which the left side exceeds the right side.

Convert RMC model to standard form:

Model in Standard Form:

Interpretation of Slack Variables: Slack variables capture the unused capacity of a resource. They have no contribution to the profit, so their coefficient in the objective function is 0. At our optimal solution (, ), we have:

(1 ton of Material I is unused)

6.2 Binding and Redundant Constraints

A binding constraint is a constraint that is satisfied as an equality at the optimal solution (i.e., its slack/surplus variable is zero). In our case, the constraints for Material II and Material III are binding. A binding constraint prevents us from further improving the objective function value. If we had more of these resources, we might be able to increase our profit.

A redundant constraint is a constraint that is not used to calculate the feasible solution. If removed, the feasible region changes while the optimal solution would remain the same. In our problem, Constraint I is a redundant constraint.

General Model Formulation

7.1 Defining Uncontrollable Inputs (Environmental Factors)

Let be the index for products, so for n different products.

Let be the index for raw materials, so for m different raw materials.

: Marginal profit for each unit of product .

: Available capacity of raw material .

: The amount of raw material required to produce one unit of product .

7.2 Defining Decision Variables

: The quantity of product to produce.

7.3 The General Model

1. Expanded Form:

2. Summation Notation

for

看到字母表示就头疼…

7.4 Rewriting the Model with Linear Algebra

The most compact way to represent an LP model is using vectors and matrices.

Define Linear Algebra Elements:

Marginal Profit (column vector):
Decision Variables (column vector):
Capacity (column vector):
Production Matrix (Technology Matrix):

The Model in Matrix Form

02 Report Example-1

想了一则小红书广告流量分配的案例，稍后放上来。

03 Sensitivity Analysis

Ch02过了一遍，主要讲了LP的常规和特殊案例，以及通用符号。 Linear programming involves choosing a course of action when the mathematical model of the problem contains only linear functions.

Sensitivity analysis

Sensitivity analysis (or post-optimality analysis) is used to determine how the optimal solution is affected by changes, within specified ranges, in:

the objective function coefficients

the right-hand side (RHS) values

Sensitivity analysis allows a manager to ask certain ”what-if“ questions about the problem.

Objective Function Coefficients

How changes in the objective function coefficients might affect the optimal solution.

2.1 Range of Optimality

The range of optimality for each coefficient provides the range of values over which the current solution will remain optimal.

2.2 Right-Hand Sides

dual value: the change in the value of the optimal solution per unit increase in the right hand side of the constraint.

2.3 Sensitivity Analysis: Computer Solution

Relevant Cost

Sunk Cost

Limitations of Classical Sensitivity Analysis

链接失效或有疑问请随时联系我，感谢。