lingo求解01整数规划

LINGO软件求解整数规划问题

2012——2013学年第 一 学期

合肥学院数理系

实验报告

课程名称： 运筹学

实验项目： LINGO软件求解整数规划问题

√ 验证性□ 实验类别：综合性□ 设计性 □

专业班级： 10数学与应用数学（1）班 姓 名： 学 号： 实验地点： 实验时间： 指导教师： 成 绩：

LINGO软件求解整数规划问题

一.实验目的

1、学会使用LINGO软件求解整数规划问题。 2、学会分析LINGO软件求解的结果。

二.实验内容

1、某班有男同学30人,女同学20人,星期天准备去植树。根据经验,一天中,

男同学平均每人挖坑20个,或栽树30棵,或给25棵树浇水,女同学平均每人挖坑10个,或栽树20棵,或给15棵树浇水。问应怎样安排,才能使植树(包括挖坑、栽树、浇水)最多。建立该问题的数学模型，并求其解。

2、求解线性规划：

maxZ x1 2x2 2x1

针对目前用＂化多为少法＂求解多目标规划问题时,计算过程繁琐或结果不理想的现状,提出了将理想目标转换为现实目标或约束,再用LINGO软件求解的方法。给出了2个实例的分析与求解过程,结果表明,与传统方法相比,该方法过程简单结果也较优。

第2卷第3 6期 21 0 2年 5月

湖

南

工

业

大

学

学

报

VOl2 No. -6 3 M a 201 v 2

J u a f n nUn v ri fT c n l g or l n o Hu a i e st o e h o o y y

d i 03 6/i n1 7— 8 32 1 .3 0 o: . 9 . s.6 3 9 3 . 2 . 2 1 9 js 0 0 0

多目标规划的 L N I GO求解法吴有平，刘杰，何杰

(. 1湖南工业大学土木工程学院，湖南株洲 4 2 0;2湖南省建筑工程集团总公司，湖南长沙 4 0 0 10 7 . 10 4)

摘要：针对目前用“多为少法”求解多目标规划问题时，计算过程繁琐或结果不理想的现状，提出化了将理想目标转换为现实目标或约束，再用 L NGO软件求解的方法。给出了2个实例的分析与求解过程，结 I

果表明，与传统方法相比，该方法过程简单结果也较优。关键词：多目标规划

甲乙公司不合作即竞争下所争取到的不同名专业推广者所建立的不同动态规划模 型的组合方案如下：其中X 为可能竞争到的专业推广者人数，即动态规划模型中第一天的

1

专业推广者推

广能力的份数，Y 为第二天需要的专业推广者推广能力的份数，即第三天安排从事推广 工作的专业推广者的人数；Z 为第三天需要的专业推广者推广能力的份数，即第三天安排从事推广工作的专业推广者的人数；a 为x 名专业推广者累计从事培训工作出来的兼职推广者的批数（每批20 人），其中，有多种组合方案；甲公司雇佣这些兼职推广者均工作一天，从事推广工作，第二天辞退a ?b批兼职推广员，其余的b批继续从事推广工作一天后辞退，即兼职宣传员总共最多雇佣2 天；cost 为花费的成本，即资金的使用数量；F 为不同方案下所达到的总推广效益。上表可以提供给甲公司做决策依据，根据效益的大小甲公司可以决策的目标方向顺序是从①--⑧，即不合作的情况下甲公司可以尽量争取到9 人，如若

不行，考虑争取4 人。

§5.4 0—1型整数规划模型

1、 0—1型整数规划模型概述

整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主

天大,考研,运筹学,管理科学与工程

例1 求解下列整数规划的最优解：

maxZ 4x1 5x2 6x3

3x1 4x2 5x3≤10s..t xj≥0 j 1,2,3 ,xj为整数.

解 （1）建立动态规划模型：

阶段变量：将给每一个变量xj赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3. 设状态变量sk表示从第k阶段到第3阶段约束右端最大值，则sj 10. 设决策变量xk表示第k阶段赋给变量xk的值(k 1,2,3). 状态转移方程：s2 s1 3x1,s3 s2 4x2.

阶段指标：u1(s1,x1) 4x1,u2(s2,x2) 5x2,u3(s3,x3) 6x3. 基本方程；

fk(sk) max uk sk,xk fk 1 sk 1 sk k 3,2,1 0≤x3≤

ak

f(s) 0. 44

其中a1 3,a2 4,a3 5. （1） 用逆序法求解： 当k 3时，

f3 s3 max 6x3 f4 s4 maxs

s

3 0≤x3

5

3

0≤x3≤

5

6x3 ,

而s3 0,1,2,3,4,5,6,7,8,9,10 . x 表示不超过x的最大整数。因此，当s3 0,1,2,3,

若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S1,S2．…，S10相应的钻探费用为C1 ,C2 ,… C10，并且井位选择要满足下列限制条件： (1)在s1，s2，S4中至多只能选择两个； （2）在S5，s6中至少选择一个；（3）在s3，s6，S7，S8中至少选择两个。 试建立这个问题的整数规划模型

解：设xj（j=1,…,10）为钻井队在第i个井位探油 minZ=?cjxj

j?110

背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。

序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 20 15 18 14 8 4 10

解：引入0—1变量xi, xi=1表示应携带物品i，,xi=0表示不应携带物品I

naxz?20x1?15x2?18x3?14x4?8x5?4x6?10x7?5x1?5x2?2x3?6x4?12x5

2.关于“规划求解”

2.1 规划求解介绍

“规划求解”是Excel中的一个加载宏，借助“规划求解”，可求得工作表上某个单元格（被称为目标单元格）中公式（公式:单元格中的一系列值、单元格引用、名称或运算符的组合，可生成新的值。公式总是以等号（=）开始）的最优值。“规划求解”将对直接或间接目标单元格中公式相关联的一组单元格中的数值进行调整，最终在目标单元格公式中求得期望的结果。“规划求解”通过调整所指定的可更改的单元格（可变单元格）中的值，从目标单元格公式中求得所需的结果。在创建模型过程中，可以对“规划求解”中的可变单元格数值应用约束条件（约束条件：“规划求解”中设置的限制条件。可以将约束条件应用于可变单元格、目标单元格或其它与目标单元格直接或间接相关的单元格。而且约束条件可以引用其它影响目标单元格公式的单元格。使用“规划求解”可通过更改其它单元格来确定某个单元格的最大值或最小值。）

Microsoft Excel的“规划求解”工具取自德克萨斯大学奥斯汀分校的Leon Lasdon 和克里夫兰州立大学的Allan Waren共同开发的Generalized Reduced Gradient(GRG2)非线性最优化代码。线性和整数规划问题取自Fr

第五章 整数规划习题

5.1 考虑下列数学模型 min且满足约束条件

z?f1(x1)?f2(x2)

（1）或x1?10，或x2?10；

（2）下列各不等式至少有一个成立：

?2x1?x2?15??x1?x2?15?x?2x?152 ?1

（3）

x1?x2?0或5或10

?0（4）x1其中

?0，x2

?20?5x1,如x1?0?,如x1?0f1(x1)?0=

将此问题归结为混合整数规划的模型。 解：min

z?10y1?5x1?12y2?6x2?12?6x2,如x2?0?,如x2?0f2(x2)??0

5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题

maxz?x1?x2x3?x323（?0）x1?y1?M；x2?y2?M?（1）x1?10?y3?M??x2?10?(1?y3)?M?（?2）x1?x2?15?y4M?x1?x2?15?y5M??x1?2x2?15?y6M??y4?y5?y6?2?（?3）x1?x2?0y7?5y8?5y9?10y10?11y11?y7?y8?y9?y10?y11?1??1i＝1，.???，11）?(4)x1?0，x2?

第五章 整数规划习题

5.1 考虑下列数学模型 min且满足约束条件

z?f1(x1)?f2(x2)

（1）或x1?10，或x2?10；

（2）下列各不等式至少有一个成立：

?2x1?x2?15??x1?x2?15?x?2x?152 ?1

（3）

x1?x2?0或5或10

?0（4）x1其中

?0，x2

?20?5x1,如x1?0?,如x1?0f1(x1)?0=

将此问题归结为混合整数规划的模型。 解：min

z?10y1?5x1?12y2?6x2?12?6x2,如x2?0?,如x2?0f2(x2)??0

5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题

maxz?x1?x2x3?x323（?0）x1?y1?M；x2?y2?M?（1）x1?10?y3?M??x2?10?(1?y3)?M?（?2）x1?x2?15?y4M?x1?x2?15?y5M??x1?2x2?15?y6M??y4?y5?y6?2?（?3）x1?x2?0y7?5y8?5y9?10y10?11y11?y7?y8?y9?y10?y11?1??1i＝1，.???，11）?(4)x1?0，x2?

整数规划+指派问题

解：设 xij

1, 如果第i项由第j个人完成 0, 如果第i项未由第j个人完成

,用

f (x )

表示所花费的总时间，由题意

现有 A、B、C、D、E 共 5 个人，挑选其中

可得如下模型

的时间如表所示。规定每项工作只能由

m i n f ( x ) 1 0 x1 1 2 x1 2 3 x1 3 1 5 x1 4 9 x1 5 5 x 21 1 0 x 22 1 5 x 23 2 x 24 4 x 25 1 5 x31 5 x32 1 4 x33 7 x34 1 5 x35 2 0 x 41 1 5 x 42 1 3 x 43 6 x 44 8 x 45 x1 1 x1 2 x 21 x 22 x31 x32 x 41 x 42 x x 21 11 x1 2 x 2 2 x x 23 13 x1 4 x 2 4 x1 5 x 2 5 x 44 0 x ij 0 x1 3 x1 4 x1 5 1 x 23 x

遗传算法求解01背包问题

一、问题描述

01背包问题属于组合优化问题的一个例子，求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：

给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。 01背包问题是NP问题，传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决01背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。

二、遗传算法

1、遗传算法的基本思想 遗传算法的搜索从一个被称作种群的候选解集开始，新的种群由旧的种群中产生以期得到更好的种群。从旧种群中按照解的适应度来选择解以产生新的解；适应度越大，解被选择生成后代的机率也越大。这个从已有种群中选择双亲并产生后代的迭代过程持续到遗传算法的停止条件满足为止。 2、遗传算法的基本元素。 遗传