※ 引述《shunit (dontshunit)》之铭言： : 有一家工厂生产一个20公分长的原料，目前有三家公司分别来订购 : 5公分15000支、7公分20000支及9公分30000支， : 该工厂的裁切台可以设定以下6种裁切方式， : 1. 请写一个模式求解剩余料最少的裁切方式，剩余料包括废料及超出订单的部分(只写模 : 式即可,不必求解); : 2. 请用Σ form重写模式。 : https://i.imgur.com/7s2Dd0Y.jpg : 不知道这发文该如何分类 : 虽然不求解但好复杂想出最佳模式脑袋已打结 这是作业研究中的Cutting Stock Problem 计算复杂度为NP-hard 对於中型或大规模的问题要在合理的时间内找到最佳解很困难 本问题是小规模 只有三种需求跟六种切割的模式 推文之中有人一开始用直观式的想法要大量使用废料为零的模式D 这就是作业研究中所谓的Heuristics 启发式算法的想法 不保证找到的解为全局最佳 但是求解时间快 工业界的困难问题通常都用Heuristics 因为有时候找到一个可行满足所有限制的解都很花费时间了 不在乎全局最佳 Cutting Stock problem在作业研究的课程中通常是拿来讲解「分解式演算法」 Decomposition method for large-scale optimization 因为变数跟限制式很多的时候如果能够聪明的分解问题透过迭代来找到全局最佳 会比直接用求解器(optimization solver)求解快 而Cutting Stock对应的分解演算法叫做(delayed) column generation 因为本问题在实际应用上 最佳化模型的变数会比限制式多出非常多 需要透过分解式的演算法 去慢慢的加入变数 而不是一次列出求解 怎麽求解超出原Po的需求就不多说 想回文澄清一下这是 作业研究的整数规划范围 而不是线性代数也不是线性规划 （线性规划我们通常指变数为连续而不是离散） 回到原Po的问题 已知参数 给定 m 个订单 每份订单对应 q_j 个需求 j = 1~m 另外总共有k种切割方式 每一种切割方式会产生 c_i 个剩余料 i = 1~k 让a_ij 代表订单j在切割方式i可裁出的方式 定义决策变数 x_i 为裁切方式i的使用次数 注意x_i 为非负整数 目标函数为极小化剩余料 min 4x_A + 3x_B + x_C + x_E + 2x_F 限制式 2x_B + 2x_C + 4x_D + x_E >= 15000 订单一的需求 x_A + x_B + 2x_E >= 20000 订单二的需求 x_A + x_C + 2x_F >= 30000 订单三的需求 x_i >= 0 and integer 求解之後为 x_D = 1250, x_E = 10000, x_F = 15000 因为是NP-hard的关系，直觉上可能会想要使用没有废料的裁切方式D去满足需求 但最佳解并不是这样，另外这个问题是小规模m=3 k=6 所以可以推论出来 但是想像100种裁切方式30份订单就不可能用这样推论的 第二题general form 我都帮你定义好index了 要写出来并不难 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 104.187.117.98 (美国) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1666832775.A.668.html ※ 编辑: illousion (104.187.117.98 美国), 10/27/2022 09:11:49