单纯形法:格式与迭代

格式 目标函最大化 所有约束都是等式(变量的非负限制除外),并且具有非负右端项。 所有的变量都是非负的。 将不等式转化成带有非负右端项的等式约束 为了把(≤)不等式约束转换成等式约束,在约束的左端添加非负的松弛变量。为了把(≥)不等式约束转换成等式约束,在约束的右端添加非负的剩余变量。 e.g. 将约束6x_1+4x_2≤24转换成6x_1+4x_2+s_1=24,s_1≥0,其中s_1 是松弛变量。 将约束x_1+x_2≥800转换成x_1+x_2−s_2… 阅读全文

开始使用MiniZinc

MiniZinc是一个用来描述整数和实数的优化约束和决策问题的语言,它允许用户以接近问题的数学公式的方式编写模型。 MiniZinc界面如下: 着色问题 首先来看一个简单的着色问题:以州为单位,用3种颜色为澳大利亚地图着色,相邻的两个州不能用同一种颜色。澳大利亚地图如下: 在MiniZinc中写入如下代码: % 用nc种颜色为澳大利亚地图着色 int: nc = 3; var 1..nc : wa; var 1..nc: nt;… 阅读全文