运筹优化学习21:Java调用Cplex实现求解Cuting Stock Porblem的列生成算法详解(上)

简介: 运筹优化学习21:Java调用Cplex实现求解Cuting Stock Porblem的列生成算法详解

1 CSP问题与模型

1.1 问题描述

我们有以下问题,原纸卷每个长为L=16m,顾客们分别需要25个3m长,20个6m长,18个7m长的纸卷。那么需要怎样切割才能使得浪费最小呢?

1.2 模型构建

假设有 n 中可行的裁切方案

image.png

由此我们得到模型如下:

gif.png

2 列生成方法理论

2.1 引子

列生成方法是求解大规模线性规划问题的有效方法,这里的大规模是指问题的约束数目有限变量数目随着问题规模的膨胀而急速膨胀的线性规划问题。

我们刚才讨论的CSP就很好的满足了这一点:

顾客需求确定,约束个数就是确定的;但是有效的方案数目是不确定的

假定n=100时,变量数为100;当n=1,000,000,000时,变量数为1,000,000,000

2.2 单纯形法到列生成

我们都知道求解线性规划的最经典的方法是单纯形法,它是一种在解空间的顶点上迁移来找到问题最优解的算法;但是对于变量很多的LP时,我们遍历顶点的代价是很大的。但是有一点我们肯定知道,那就是我们的约束个数是等于基变量的个数的。另外i啊我们每一步的操作只会让一个非基变量进基。


为了更好的说明先澄清几个概念:


image.png

image.png

基于上面的解释和概念定义,我们就可以描述单纯形法到列生成的演变路径:


将MP限制到一个变量更少的子问题RMP,使用单纯形法求解RMP的最优解

使用subproblem去检验剩余变量的reduced cost是否小于0;若是,将与该变量相关的系数列加入到RMP中,返回第1步;否则,得到了原问题的最优解。


2.3 subproblem

这里终点讨论一下子问题,子问题的作用是为了检查剩余非基变量的reduced cost,确定它能否作为入基变量。

先来一张规范的单纯形表:

20191108144037152.png

在单纯形法中,我们通过计算非基变量检验数 ,为负且最小的情况下的变量作为入基变量


在这个问题中,我们求解的关键是,它包含两重含义:


通过求解RMP问题得到的影子价格(shadow price)。

通过求解RMP对偶问题得到的对偶变量(dual variable)。

通俗的理解,影子价格是针对RMP本身而言的,而对偶变量是针对RMP的对偶问题而言的。


若对影子价格和对偶变量理论不熟悉,可前去阅读2.3.1和2.3.2的内容;否则我们继续


作为一个懒虫,我们肯定是咋简单咋来:


要想得到影子价格,我们就得解RMP,但是很不幸RMP有很多变量,单纯形法可能解不了;此路不通

对偶问题变量少啊,那我们当然选择从对偶变量下手

那就好办了,我们通过求RMP的对偶问题来求解gif.gif,从而得到非基变量的检验数gif.gif,然后建立以检验数最小为目标的subproblem,如果它的目标函数为负,说明这个列可以加入到RMP中;如果它非负,说明已经得到了最优解


2.3.1 对偶理论

对于每个线性规划问题都有一个对偶问题,得到了一个问题的解,另一个问题的解也就迎刃而解了。

20200202211511782.png

20200202212051210.png

再啰嗦一下:


对偶问题的目标函数的系数是原问题约束的右端项

对偶问题的系数矩阵是原问题系数矩阵的转置

对偶问题的约束都是 ≤ ;原问题的约束都是 ≥

对偶问题求最小则原问题求最大

对偶问题的剩余变量和原问题的基变量共同构成了变量空间

对偶问题研究的是资源的估价问题,原问题研究的是资源的最优分配问题


2.3.2 影子价格

对偶变量gif.gif表示市场对单位第 i 种资源的估价,这种估价是由资源在生产过程发挥的作用决定的。


在资源最优利用条件下的估价,被我们称为该资源的影子价格;


下面是几点解释:


也可认为是在最优条件下,增加每单位 i 资源,对目标函数的增量贡献值。

当资源利用不充分时,他的影子价格为0;而影子价格不为0时,表示该资源已经耗尽

结合检验数的计算,gif.gif,前一项为产品 j 的产值,后一项为生产该产品消耗各资源的影子价格之和(隐含成本)。当产品产值大于资源隐含成本时,生成才有意义,所以检验数必须为非负


2.4 小结


列生成就是从一个变量较少的RMP开始,在得到RMP最优解后,利用其对偶变量建立起一个检验数最小化subproblem;若subproblem目标值为负,则增加新列到RMP中;如果subproblem目标值非负,则得到RMP的最优解。


所谓列生成,就是在每次迭代中添加一个列,直到无列可加时,得到的RMP的最优解就是原问题最优解。


列生成解决的是线性规划问题,如果要解决整数规划问题,还需要借助分支定界法、分支定价、分支切割等方法


3 Cplex OPL演示列生成迭代过程

3.1 第一次迭代

如果每个纸卷只裁切一个类别的纸卷,我们可以得到初始方案:

A = [5,0,0; 0,2,0; 0,0,2]

因此我们选择前三个方案,构建的RMP模型为:

gif.png

Cplex OPL代码:

 dvar int+ y1; dvar int+ y2; dvar int+ y3;
 minimize y1 + y2 + y3;
 subject to{
5*y1 + 0*y2 + 0*y3 >= 25;
0*y1 + 2*y2 + 0*y3 >= 20;
0*y1 + 0*y2 + 2*y3 >= 18;
} 


得到结果为:Y = [5, 10, 9];

对偶变量为:gif.gif

现在我们要加一列到RMP中,记为gif.gif,计算其检验数:

gif.gif

我们便得到了一个子问题:

gif.png

Cplex代码:

dvar int+ a14; dvar int+ a24; dvar int+ a34;
minimize 1 - (0.2*a14 + 0.5*a24 + 0.5*a34);
subject to{
3*a14 + 6*a24 + 7*a34 <= 16;
}

得到image.png,ruduce cost的取值为负数,因此加入image.png

目录
打赏
0
0
0
0
7
分享
相关文章
Java 大数据在智能教育在线实验室设备管理与实验资源优化配置中的应用实践
本文探讨Java大数据技术在智能教育在线实验室设备管理与资源优化中的应用。通过统一接入异构设备、构建四层实时处理管道及安全防护双体系,显著提升设备利用率与实验效率。某“双一流”高校实践显示,设备利用率从41%升至89%,等待时间缩短78%。该方案降低管理成本,为教育数字化转型提供技术支持。
37 0
java 最新技术驱动的智能教育在线实验室设备管理与实验资源优化实操指南
这是一份基于最新技术的智能教育在线实验室设备管理与实验资源优化的实操指南,涵盖系统搭建、核心功能实现及优化策略。采用Flink实时处理、Kafka消息队列、Elasticsearch搜索分析和Redis缓存等技术栈,结合强化学习动态优化资源调度。指南详细描述了开发环境准备、基础组件部署、数据采集与处理、模型训练、API服务集成及性能调优步骤,支持高并发设备接入与低延迟处理,满足教育机构数字化转型需求。代码已提供下载链接,助力快速构建智能化实验室管理系统。
82 44
银行流水生成器在线制作,银行转账p图在线生成,java实现最牛的生成器【仅供学习用途】
本资料探讨银行系统核心技术,涵盖交易记录生成、电子回单加密验真及基于Java的财务管理系统开发。主要内容包括:交易记录实体类设计(不可变性与数字签名)
Java 大视界 -- Java 大数据在智能教育学习社区用户互动分析与社区活跃度提升中的应用(274)
本文系统阐述 Java 大数据技术在智能教育学习社区中的深度应用,涵盖数据采集架构、核心分析算法、活跃度提升策略及前沿技术探索,为教育数字化转型提供完整技术解决方案。
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。
基于遗传优化ELM网络的时间序列预测算法matlab仿真
本项目实现了一种基于遗传算法优化的极限学习机(GA-ELM)网络时间序列预测方法。通过对比传统ELM与GA-ELM,验证了参数优化对非线性时间序列预测精度的提升效果。核心程序利用MATLAB 2022A完成,采用遗传算法全局搜索最优权重与偏置,结合ELM快速训练特性,显著提高模型稳定性与准确性。实验结果展示了GA-ELM在复杂数据中的优越表现,误差明显降低。此方法适用于金融、气象等领域的时间序列预测任务。
java 入门学习视频_2025 最新 java 入门零基础学习视频教程
《Java 21 入门实操指南(2025年版)》提供了Java最新特性的开发指导。首先介绍了JDK 21和IntelliJ IDEA 2025.1的环境配置,包括环境变量设置和预览功能启用。重点讲解了Java 21三大核心特性:虚拟线程简化高并发编程,Record模式优化数据解构,字符串模板提升字符串拼接可读性。最后通过图书管理系统案例,展示如何运用Record定义实体类、使用Stream API进行数据操作,以及结合字符串模板实现控制台交互。该指南完整呈现了从环境搭建到实际项目开发的Java 21全流程实
42 1
Java 从入门到实战完整学习路径与项目实战指南
本文详细介绍了“Java从入门到实战”的学习路径与应用实例,涵盖基础、进阶、框架工具及项目实战四个阶段。内容包括环境搭建、语法基础、面向对象编程,数据结构与算法、多线程并发、JVM原理,以及Spring框架等核心技术。通过学生管理系统、文件下载器和博客系统等实例,帮助读者将理论应用于实践。最后,提供全链路电商系统的开发方案,涉及前后端技术栈与分布式架构。附代码资源链接,助力成为合格的Java开发者。
47 4
|
18天前
|
银行转账p图软件,对公转账截图生成器,java版开发银行模拟器【仅供学习参考】
这是一套简单的银行账户管理系统代码,包含`BankAccount`和`BankSystem`两个核心类。`BankAccount`负责单个账户的管理

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问