分享兴趣，传播快乐，增长见闻，留下美好！
亲爱的您，这里是LearningYard新学苑。
今天小编给您带来
【周周记：数学建模学习（5）】
欢迎您的访问！
Share interest, spread happiness, increase knowledge, leave a beautiful!
Dear, this is LearningYard New Academy.
Today, the editor brings you
"Weekly Diary: Learning Mathematical Modeling (5)"
Welcome to your visit!
割平面算法求解整数规划基本原理与编程实现
Programming Implementation of Gomory's Cutting Plane Algorithm for Integer Programming
一、基本原理
I. Basic Principles
（1）如果松弛问题（P0）无解，则（P）无解；
（1） If the relaxed problem (P0) has no solution, then the original problem (P) has no solution.
（2）如果（P0）的最优解为整数向量，则也是（P）的最优解；
（2） If the optimal solution of (P0) is an integer vector, it is also the optimal solution of (P)
（3）如果(P0)的解含有非整数分量，则对(P）增加割平面条件（根据限制条件来限制取值区间）：即对(P)增加一个线性约束，将(P)的可行区域割掉一块，使得非整数解恰好在割掉的一块中，但又没有割掉原问题(P)的可行解（切掉没有整数解的部分），得到问题(P0)，重复上述的过程。
（3） If the solution of (P0) contains non-integer components, then a cutting plane condition is added to (P) (based on the constraints to restrict the value range): A linear constraint is added to (P) to cut off a portion of the feasible region, such that the non-integer solution falls precisely in the cut-off part, but without cutting off any feasible solution of the original problem (P). This process is repeated with the updated problem (P0).
（实质：增加限制条件）
(Essence: Adding constraints)
例题：
Example
步骤1：用约束条件限制取值区间
Step 1: Restrict the value range using the given constraints.
步骤2：切割不含整数区域（绿色部分舍弃；x2属于【1,7/4】）
Step 2: Cut off the region that does not contain integer solutions (discard the green part; x2 belongs to [1, 7/4]).
对可行解没有影响；
This does not affect the feasible solutions.
步骤三：切去后添加限制条件x2≤1，得到整数规划最优解
Step 3: After cutting, add the constraint x2 ≤ 1 to obtain the optimal solution for the integer programming problem.
局限：x2的限制条件较为简单，若限制较为困难将出现问题；
Limitation: The constraint on x2 is relatively simple. More complex constraints may pose challenges.
上图，区别在图中2中含有变量x3、x4，将问题由不等式变成等式；
In the figure, the difference in Figure 2 lies in the inclusion of variables x3 and x4, which transform the problem from inequalities to equalities.
对图中2限制条件等式对变量1、2进行用变量3、4限制。
The equality constraints in Figure 2 restrict variables x1 and x2 using variables x3 and x4.
将1倍的x1与x3（整数）放于一边，3/4倍的x3与1/4倍的x4（小数）放于另一边；最终写出关于x3、x4的两表达式
Variables x1 and x3 (integers) are placed on one side, while 3/4 of x3 and 1/4 of x4 (fractions) are placed on the other side. This results in two expressions involving x3 and x4.
二、基本步骤
II. Basic Steps
三、Matlab的流程
III. Matlab Implementation Flow
今天的分享就到这里了。
如果您对今天的文章有独特的看法，
欢迎给我们留言，
让我们相约明天，
祝您今天过得开心！
That's all for today's share.
If you have a unique view of today's article,
Please leave us a message,
Let's meet tomorrow,
Have a nice day!
本文由LearningYard新学苑原创，如有侵权，请联系删除。
参考资料：哔哩哔哩
翻译：文心一言