最小费用运输问题
单 位 销地 运 价 产地 A1 A2 A3 A4 A5 A6 销量 B1 B2 B3 B4 B5 B6 B7 B8 产量 6 4 5 7 2 5 35 2 9 2 6 3 5 37 6 5 1 7 9 2 22 7 3 9 3 5 2 32 4 8 7 9 7 8 41 2 5 4 2 2 1 32 5 8 3 7 6 4 43 9 2 3 1 5 3 38 60 55 51 43 41 52 280/302 i.e:
model:
!6发点8收点运输问题; sets:
warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand;
links(warehouses,vendors): cost, volume; endsets !目标函数;
min=@sum(links: cost*volume); !需求约束;
@for(vendors(J):
@sum(warehouses(I): volume(I,J))=demand(J)); !产量约束;
@for(warehouses(I):
@sum(vendors(J): volume(I,J))<=capacity(I));
!这里是数据; data:
capacity=60 55 51 43 41 52;
demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3; enddata
1 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
1 LINGO中的集
1.1 The Sets Section of a Model
Sets are defined in an optional section of a LINGO model, called the sets section. Before you use sets in a LINGO model, you have to define them in the sets section of the model. The sets section begins with the keyword SETS: (including the colon), and ends with the keyword ENDSETS. A model may have no sets section, a single sets section, or multiple sets sections. A sets section may appear anywhere in a model. The only restriction is you must define a set and its attributes before they are referenced in the model's constraints.
1.2 Defining Primitive Sets
To define a primitive set in a sets section, you specify: ✓ the name of the set,
✓ optionally, its members (objects contained in the set), and ✓ optionally, any attributes the members of the set may have.
A primitive set definition has the following syntax:
setname [/ member_list /] [: attribute_list];
When using implicit set member lists, you do not have to list a name for each set member. Use the following syntax when using an implicit set member list:
2 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
setname / member1..memberN / [: attribute_list];
where member1 is the name of the first member in the set and memberN is the name of the last member. LINGO automatically generates all the intermediate member names between member1 and memberN. While this can be a very compact and convenient method for building a primitive set, there is one catch in that only certain formats of names are accepted for the initial and terminal member names. The following table details the available options:
Implicit Member 1..n stringM..stringN List Format 1..5 TRUCKS3..TRUCKS204 dayM..dayN monthM..monthN MON..FRI OCT..JAN MON, TUE, WED, THU, FRI OCT, NOV, DEC, JAN OCT2001, NOV2001, DEC2001, JAN2002 Example Set Members 1, 2, 3, 4, 5 TRUCK3, TRUCK4, ..., TRUCK204 monthYearM..monthYOCT2001..JAearN N2002 i.e1: !集部分;
sets:
students:sex,age; endsets !数据部分; data:
students,sex,age= John 1 16 Jill 0 14 Rose 0 17 Mike 1 13; enddata
3 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
i.e2:
data:
NUMBER_OF_WH = 6; enddata sets:
WAREHOUSES / 1..NUMBER_OF_WH/: CAPACITY; endsets
1.3 Defining Derived Sets
To define a derived set, you specify: ✓ the name of the set, ✓ its parent sets,
✓ optionally, its members, and
✓ optionally, any attributes the set members have.
A derived set definition has the following syntax:
setname( parent_set_list) [ / member_list /] [:
attribute_list];
i.e3:
sets:
product/ A ,B/; machine / M, N/; week/ 1..2/;
allowed(product,machine,week); endsets
allowed Set Membership: Index Member 1 (A,M,1) 2 (A,M,2)
4 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
3 (A,N,1) 4 (A,N,2) 5 (B,M,1) 6 (B,M,2) 7 (B,N,1) 8 (B,N,2)
i.e:
sets:
!学生集：性别属性sex，1表示男性，0表示女性；年龄属性age. ; students/John,Jill,Rose,Mike/:sex,age;
!男学生和女学生的联系集：友好程度属性friend，[0，1]之间的数。 ; linkmf(students,students)|sex(&1) #eq# 1 #and# sex(&2) #eq# 0: friend; !男学生和女学生的友好程度大于0.5的集;
linkmf2(linkmf) | friend(&1,&2) #ge# 0.5 : x; endsets data:
sex,age = 1 16 0 14 0 17 0 13;
friend = 0.3 0.5 0.6; enddata
Note：竖线是用来标记一个成员资格过滤器的开始。#eq#表示逻辑运算符，相等为真，&1表示派生集的第1个原始父集的索引，它取遍该原始父集的所有成员；，&2表示派生集的第2个原始父集的索引，它取遍该原始父集的所有成员；……以此类推。
2 LINGO中的数据部分
数据部分提供了模型相对静止部分和数据分离的可能性。
数据部分以关键字“data:”开始，以关键字“enddata”结束。在这里，可
5 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
以指定集成员、集的属性。其语法如下：
object_list = value_list;
对象列（object_list）包含要指定值的属性名、要设置集成员的集名，用逗号或空格隔开。一个对象列中至多有一个集名，而属性名可以有任意多。如果对象列中有多个属性名，那么它们的类型必须一致。如果对象列中有一个集名，那么对象列中所有的属性的类型就是这个集。
数值列（value_list）包含要分配给对象列中的对象的值，用逗号或空格隔开。注意属性值的个数必须等于集成员的个数。
i.e:
sets:
set1/A,B,C/: X,Y; endsets data:
X=1,2,3; Y=4,5,6; enddata
也可采用复合数据声明（data statement）实现同样的功能。
i.e:
sets:
set1/A,B,C/: X,Y; endsets data: X,Y=1 4 2 5 3 6; enddata
看到这个例子，可能会认为X被指定了1、4和2三个值，因为它们是数值列中前三个，而正确的答案是1、2和3。假设对象列有n个对象，LINGO在为对象指定值时，首先在n个对象的第1个索引处依次分配数值列中的前n个对象，
6 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
然后在n个对象的第2个索引处依次分配数值列中紧接着的n个对象，……，以此类推。
模型的所有数据——属性值和集成员——被单独放在数据部分，这可能是最规范的数据输入方式。
3 LINGO中的函数
3.1 逻辑运算符（Logical Operators）
LogicalOperator Return Value
#NOT# TRUE if the operand immediately to the right is FALSE, else FALSE. #EQ# TRUE if both operands are equal, else FALSE. #NE# TRUE if both operands are not equal, else FALSE.
#GT# TRUE if the left operand is strictly greater than the right operand, else FALSE. #GE# TRUE if the left operand is greater-than-or-equal-to the right operand, else FALSE. #LT# TRUE if the left operand is strictly less than the right operand, else FALSE. #LE# TRUE if the left operand is less-than-or-equal-to the right operand, else FALSE. #AND# TRUE only if both arguments are TRUE, else FALSE. #OR# FALSE only if both its arguments are FALSE, else TRUE. The priority ranking of the logical operators is: Priority Level Operator(s) Highest #NOT#
#EQ# #NE# #GT# #GE# #LT# #LE# Lowest #AND# #OR#
3.2 数学运算符（Mathematical Functions）
LINGO offers a number of standard, mathematical functions. These functions return a single result based on one or more scalar arguments. These functions are listed below: @ABS( X)
This returns the absolute value of X.
@COS( X)
This returns the cosine of X, where X is an angle in radians.
@EXP( X)
7 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
This returns e (2.718281...) raised to the power X.
@FLOOR( X)
This returns the integer part of X. To be specific, if X >=0, @FLOOR returns the largest integer, I, such that I <=X. If X is negative, @FLOOR returns the most negative integer, I, such that I >=X.
@LGM( X)
This returns the natural (base e) logarithm of the gamma function of X (i.e., log of (X - 1)!). It is extended to noninteger values of X by linear interpolation.
Note:伽玛方程表达式为：Γ(x)=∫e^(-t)*t^(x-1)dt (积分的下限式0,上限式+∞) 利用分部积分法(integration by parts)我们可以得到
Γ(x)=（x-1)*Γ(x-1)
@LOG( X)
This returns the natural logarithm of X.
@MOD( X,Y)
This returns the value of X modulo Y, or, in other words, the remainder of an integer divide of X by Y.
@POW( X,Y)
This returns the value of X rasied to the Y power.
@SIGN( X)
This returns -1 if X < 0. Otherwise, it returns +1.
@SIN( X)
This returns the sine of X, where X is the angle in radians.
@SMAX( X1, X2,..., XN)
This returns the maximum value of X1, X2, ..., and XN.
@SMIN( X1, X2,..., XN)
This returns the minimum value of X1, X2, ..., and XN.
8 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
@SQR( X)
This returns the value of X squared.
@SQRT( X)
This returns the square root of X.
@TAN( X)
This returns the tangent of X, where X is the angle in radians
3.3 金融函数（Financial Functions）
LINGO currently offers two financial functions. One computes the present value of an annuity. The other returns the present value of a lump sum.
@FPA( I, N)
This returns the present value of an annuity. That is, a stream of $1 payments per period at an interest rate of I for N periods starting one period from now. I is not a percentage, but a fraction representing the interest rate (e.g., you would use .1 to represent 10%). To get the present value of an annuity stream of $X payments, multiply the result by X.
返回如下情形的净现值：单位时段利率为I，连续n个时段支付，每个时段支付单位费用。若每个时段支付x单位的费用，则净现值可用x乘以@fpa(I,n)算得。@fpa的计算公式为
n11(1I)nkIk1(1I)。
净现值就是在一定时期内为了获得一定收益在该时期初所支付的实际费用。 年值，用A(Annuity)表示。它表示发生在每年的等额现金流量，即在某个特定时间序列内，每隔相同时间收入或支出的等额资金。在工程经济分析计算中，如无特
9 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
别说明，一般约定A 发生在期末，如第1 年末、第2 年末等。
i.e:
贷款买房问题 贷款金额50000元，贷款年利率5.31%，采取分期付款方式（每年年末还固定金额，直至还清）。问拟贷款10年，每年需偿还多少元？ LINGO代码如下：
50000 = x * @fpa(.0531,10); 结果：
Feasible solution found.
Total solver iterations: 0
Variable Value X 6573.069
Row Slack or Surplus 1 0.000000
10 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
@FPL( I, N)
This returns the present value of a lump sum of $1 N periods from now if the interest rate is I per period. I is not a percentage, but a fraction representing the interest rate (e.g., you would use .1 to represent 10%). To get the present value of a lump sum of $X, multiply the result by X.
返回如下情形的净现值：单位时段利率为I，第n个时段支付单位费用。@fpl(I,n)的计算公式为
(1I)n。
以上两个函数存在的关系为：
@fpa(I,n)@fpl(I,k)k1n。
3.4 概论函数（Probability Functions）
LINGO has a number of probability related functions. There are examples that make use of most of these functions in Developing More Advanced Models and in Additional Examples of LINGO Modeling.
@PBN( P, N, X) 二项分布的累积分布函数
This is the cumulative binomial probability. It returns the probability that a sample of N items, from a universe with a fraction of P of those items defective, has X or less defective items. It is extended to non-integer values of X and N by linear interpolation.
2
@PCX( N, X) 自由度为n的χ分布的累积分布函数
This is the cumulative distribution function for the Chi-squared distribution with N degrees of freedom. It returns the probability that an observation from this distribution is less-than-or-equal-to X.
@PEB( A, X) 当到达负荷为a，服务系统有x个服务器且允许无穷排队时的Erlang繁忙概率
This is Erlang抯 busy probability for a service system with X servers and an arriving load of A, with infinite queue allowed. The result of @PEB can be interpreted as either the fraction of time all servers are busy or the fraction of customers that must wait in the queue. It is extended to noninteger values of X by linear interpolation. The arriving load, A, is the expected number of customers arriving per unit of time multiplied by the expected time to process one customer.
@PEL( A, X) 当到达负荷为a，服务系统有x个服务器且不允许排队时的Erlang繁忙概率。
This is Erlang抯 loss probability for a service system with X servers and an arriving load of A, no queue allowed. The result of @PEL can be interpreted as either the fraction of time all servers are busy or the fraction of customers lost due to all servers being busy when they arrive. It is extended to noninteger
11 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
values of X by linear interpolation. The arriving load, A, is the expected number of customers arriving per unit of time multiplied by the expected time to process one customer.
@PFD( N, D, X) 自由度为n和d的F分布的累积分布函数。
This is the cumulative distribution function for the F distribution with N degrees of freedom in the numerator and D degrees of freedom in the denominator. It returns the probability that an observation from this distribution is less-than-or-equal-to X.
@PFS( A, X, C)
当负荷上限为a，顾客数为c，平行服务器数量为x时，有限源的Poisson服务系统的等待或返修顾客数的期望值。a是顾客数乘以平均服务时间，再除以平均返修时间。当c和（或）x不是整数时，采用线性插值进行计算。
This returns the expected number of customers waiting for or under repair in a finite source Poisson service system with X servers in parallel, C customers, and a limiting load A. It is extended to noninteger values of X and C by linear interpolation. A, the limiting load, is the number of customers multiplied by the mean service time divided by the mean repair time.
@PHG( POP, G, N, X)
超几何（Hypergeometric）分布的累积分布函数。pop表示产品总数，g是正品数。从所有产品中任意取出n（n≤pop）件。pop，g，n和x都可以是非整数，这时采用线性插值进行计算。
This is the cumulative hypergeometric probability. It returns the probability that X or fewer items in the sample are good, given a sample without replacement of N items from a population of size POP where G items in the population are good. It is extended to noninteger values of POP, G, N, and X by linear interpolation.
@PPL( A, X)
Poisson分布的线性损失函数，即返回max(0,z-x)的期望值，其中随机变量z服从均值为a的Poisson分布。
This is the linear loss function for the Poisson distribution. It returns the expected value of MAX( 0, Z-X), where Z is a Poisson random variable with mean value A.
@PPS( A, X)
均值为a的Poisson分布的累积分布函数。当x不是整数时，采用线性插值进行计算。
This is the cumulative Poisson probability distribution. It returns the probability that a Poisson random variable, with mean value A, is less-than-or-equal-to X. It is extended to noninteger values of X by linear interpolation.
12 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
@PSL( X)
单位正态线性损失函数，即返回max(0,z-x)的期望值，其中随机变量z服从标准正态分布。
This is the unit normal linear loss function. It returns the expected value of MAX( 0, Z-X), where Z is a standard normal random variable. In inventory modeling, @PSL( X) is the expected amount that demand exceeds a level X, if demand has a standard normal distribution.
@PSN( X)
标准正态分布的累积分布函数。
This is the cumulative standard normal probability distribution. A standard normal random variable has mean 0.0 and standard deviation 1.0 (the bell curve, centered on the origin). The value returned by @PSN is the area under the curve to the left of the point on the ordinate indicated by X.
@PTD( N, X)
自由度为n的t分布的累积分布函数。
This is the cumulative distribution function for the t distribution with N degrees of freedom. It returns the probability that an observation from this distribution is less-than-or-equal-to X.
@QRAND( SEED)
产生服从(0,1)区间的均匀拟随机数。@qrand只允许在模型的数据部分使用，它将用拟随机数填满集属性。通常，声明一个m×n的二维表，m表示运行实验的次数，n表示每次实验所需的随机数的个数。在行内，随机数是独立分布的；在行间，随机数是非常均匀的。这些随机数是用“分层取样”的方法产生的。
The @QRAND produces a sequence of \"quasi-random\" uniform numbers in the interval (0,1). @QRAND is only permitted in a data section. It will fill an entire attribute with quasi-random numbers. Generally, you will be filling two-dimensional tables with, say, m rows and n variables. m represents the number of scenarios, or experiments, you want to run. n represents the number of random variables you need for each scenario or experiment. Within a row, the numbers are independently distributed. Among rows, the numbers are \"super uniformly\" distributed. That is, the numbers are more uniformly distributed than you would expect by chance. These numbers are generated by a form of \"stratified sampling\".
For example, suppose m = 4 and n = 2. Even though the numbers are random, you will find that there will be exactly one row in which both numbers are in the interval (0, .5), exactly one row in which both numbers are in (.5, 1), and two rows in which one number is less than .5 and the other is greater than .5.
13 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
Using @QRAND allows you to get much more accurate results for a given number of random numbers in a Monte Carlo model. If you want 8 ordinary random numbers, then use @QRAND(1,8) rather than @QRAND(4,2). An example of @QRAND follows:
i.e:
MODEL: DATA:
M = 4; N = 2;
SEED = 1234567; ENDDATA SETS:
ROWS /1..M/; COLS /1..N/;
TABLE( ROWS, COLS): X; ENDSETS DATA:
X = @QRAND( SEED); ENDDATA END
i.e:
MODEL: DATA:
M = 8; N = 1;
SEED = 1234567; ENDDATA SETS:
ROWS /1..M/; COLS /1..N/;
TABLE( ROWS, COLS): X; ENDSETS DATA:
X = @QRAND( SEED); ENDDATA END
Example of @QRAND function
If you don’t specify a seed value for @QRAND, then LINGO will use the system clock to construct a seed value. 如果没有为函数指定种子，那么LINGO将用系统时间构造种子。 @rand(seed)
This returns a pseudo-random number between 0 and 1, depending deterministically on SEED.
返回0和1间的伪随机数，依赖于指定的种子。典型用法是U(I+1)=@rand(U(I))。注意如果seed不变，那么产生的随机数也不变。
利用@rand产生15个标准正态分布的随机数
14 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
model:
!产生一列正态分布的随机数; sets:
series/1..15/: u, znorm; endsets
!第一个均匀分布随机数是任意的; u( 1) = @rand( .1234);
!产生其余的均匀分布的随机数; @for(series( I)| I #GT# 1: u( I) = @rand( u( I - 1)) );
@for( series( I): !正态分布随机数;
@psn( znorm( I)) = u( I); !ZNORM可以是负数; @free( znorm( I)); ); end
3.5 变量界定函数（Variable Domain Functions）
The default assumption for a variable is that it is continuous with a lower bound of 0. Variable domain functions place additional restrictions on the values that variables can assume. The functions and their effects are as follows:
@BIN( variable) 限制x为0或1
This restricts variable to being a binary (0/1) integer value.
@BND( lower_bound, variable, upper_bound) 限制L≤x≤U
This limits variable to being greater-than-or-equal-to lower_bound and less-than-or-equal-to upper_bound.
@FREE( variable)
取消对变量x的默认下界为0的限制，即x可以取任意实数
This removes the default lower bound of zero on variable, allowing it to take any positive or negative value.
@GIN( variable) 限制x为整数
This restricts variable to integer values (e.g., 0,1,2, ...).
You may use the @FOR function to apply variable domain functions to all the elements of an attribute. Variable domain functions are discussed in detail in Using Variable Domain Functions.
15 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
3.6 集操作函数（Set Handling Functions）
LINGO offers several functions that assist with handling sets. The @IN function determines if a set element is contained in a set. The @INDEX function returns the index of a primitive set element within its set. The @SIZE function returns the number of elements in a set. Finally, the @WRAP function is useful for \"wrapping\" set indices from one end of a time horizon to another in multiperiod planning models. These are described in more detail below.
@IN( set_name, primitive_index_1 [, primitive_index_2 ...]) 如果元素在指定集中，返回1；否则返回0。
This returns TRUE if the set member referenced by the index tuple (primitive_index_1, primitive_index_2, ...) is contained in the set_name set. As the following example shows, the @IN operator is useful for generating complements of subsets in set membership conditions.
i.e:
全集为I，B是I的一个子集，C是B的补集。
sets:
I/x1..x4/; B(I)/x2/;
C(I)|#not#@in(B,&1):; endsets
@INDEX( [set_name,] primitive_set_element)
该函数返回在集set_name中原始集成员primitive_set_element的索引。如果set_name被忽略，那么LINGO将返回与primitive_set_element匹配的第一个原始集成员的索引。如果找不到，则产生一个错误。
This returns the index of the primitive set element primitive_set_element in the optionally supplied set set_name. If the set name is omitted, LINGO returns the index of the first primitive set element it finds with a name matching primitive_set_element. If LINGO is unable to find primitive_set_element, an error is generated.
@SIZE( set_name)
该函数返回集set_name的成员个数。在模型中明确给出集大小时最好使用该函数。它的使用使模型更加数据中立，集大小改变时也更易维护。
This returns the number of elements in the set_name set. Using the @SIZE function is preferred to explicitly listing the size of a set in a model. This serves to make your models more data independent and, therefore, easier to maintain should the size of your sets change. @WRAP( Index, Limit)
该函数返回j=Index-k*Limit，其中k是一个整数，取适当值保证j落在区间[1，Limit]内。该函数相当于Index模Limit再加1。该函数在循环、多阶段计划编制中特别有用。
This allows you to \"wrap\" an index around the end of a set and continue indexing at the other end of the set. That is, when the last (first) member of a set is reached in a set looping function, use of @WRAP will
16 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
allow you to wrap the set index to the first (last) member of the set. This is a particularly useful function in cyclical, multiperiod planning models.
Formally speaking, @WRAP returns J such that J = INDEX - K * LIMIT, where K is an integer such that J is in the interval [1,LIMIT]. Informally speaking,
@WRAP will subtract or add LIMIT to INDEX until it falls in the range 1 to LIMIT.
For an example on the use of the @WRAP function in a staff scheduling model, refer to the Primitive Set Example section in Using Sets.
i.e:
Suppose you run the popular Pluto Dogs hot dog stand which is open seven days a week. You hire employees to work a five day work week with two consecutive days off. Each employee receives the same weekly salary. Some days of the week are busier than others and, based on past experience, you know how many workers are required on a given day of the week. In particular, your forecast calls for these staffing requirements:
Day Mon Tue Wed Thu Fri Sat Sun Staff Req'd 20 16 13 16 19 14 12
You need to determine how many employees to start on each day of the week in order to minimize the total number of employees, while still meeting or exceeding staffing requirements each day of the week. The Formulation
The first question to consider when building a set based model is, \"What are the relevant sets and their attributes?\". In this model, we have a single primitive set, the days of the week. If we call this set DAYS, we can begin by writing our sets section as:
SETS:
DAYS / MON, TUE, WED, THU, FRI, SAT, SUN/;
ENDSETS
Alternatively, we could use LINGO’s implicit set definition capability and express this equivalently as:
SETS:
DAYS / MON..SUN/;
ENDSETS
We will be concerned with two attributes of the DAYS set. The first is the number of staff required on each
17 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
day, and the second is the number of staff to start on each day. If we call these attributes REQUIREMENTS and START, then we may add them to the sets section to get:
SETS:
DAYS / MON TUE WED THU FRI SAT SUN/: REQUIRED, START;
ENDSETS
After defining the sets and attributes, it is useful to determine which of the attributes are data, and which are decision variables. In this model, the REQUIRED attribute is given to us and is, therefore, data. The START attribute is something we need to determine, and constitutes the decision variables. Once you've identified the data, you may go ahead and initialize it. We can do this with the data section:
DATA:
REQUIRED = 20 16 13 16 19 14 12;
ENDDATA
We are now at the point where we can begin entering the model's mathematical relations (i.e., the objective and constraints). Let's begin by writing out the mathematical notation for the objective. Our objective is to minimize the total number of employees we start during the week. Using standard mathematical notation, this objective may be expressed as:
Minimize: ∑iSTARTi
The equivalent LINGO statement is very similar. Substitute \"MIN=\" for \"Minimize:\" and \"@SUM( DAYS( I):\" for ∑i and we have:
MIN = @SUM( DAYS( I): START( I));
Now, all that is left is to come up with our constraints. There is only one set of constraints in this model. Namely, we must have enough staff on duty each day to meet or exceed staffing requirements. In words, what we want is:
Staff on duty today>=Staff required today, for each day of the week
The right-hand side of this expression, Staff required today, is easy to calculate. It is simply the quantity REQUIRED( I). The left-hand side, Staff on duty today
, is a bit trickier to compute. Given that all employees are on a \"five day on, two day off\" schedule, the
18 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
number of employees working today is:
Number working today = Number starting today +
Number starting 1 day ago + Number starting 2 days ago +
Number starting 3 days ago + Number starting 4 days ago.
In other words, to compute the number of employees working today, we sum up the number of people starting today plus those starting over the previous four days. The number of employees starting five and six days back don't count because they are on their days off. So, using mathematical notation, what one might consider doing is adding the constraint:
∑= j-4, j STARTi ?REQUIRED j , for j?DAYS
Translating into LINGO notation, we can write this as: @FOR( DAYS( J):
@SUM( DAYS( I) | I #LE# 5: START( J - I + 1)) >= REQUIRED( J) );
In words, the LINGO statement says, for each day of the week, the sum of the employees starting over the five day period beginning four days ago and ending today must be greater-than-or-equal-to the required number of staff for the day. This sounds correct, but there is a slight problem. If we try to solve our model with this constraint we get the error message:
To see why we get this error message, consider what happens on Thursday. Thursday has an index of 4 in our set DAYS. As written, the staffing constraint for Thursday will be:
START( 4 - 1 + 1) + START( 4 - 2 + 1) +
START( 4 - 3 + 1) + START( 4 - 4 + 1) +
START( 4 - 5 + 1) >= REQUIRED( 4);
Simplifying, we get:
START( 4) + START( 3) +
START( 2) + START( 1) +
19 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
START( 0) >= REQUIRED( 4);
The START( 0) term is the root of our problem. START is defined for days 1 through 7. START( 0) does not exist. An index of 0 on START is considered \"out of range.\"
We would like to have any indices less-than-or-equal-to 0 wrap around to the end of the week. Specifically, 0 would correspond to Sunday (7), -1 to Saturday (6), and so on. LINGO has a function that does just this called @WRAP.
The @WRAP function takes two arguments—call them INDEX and LIMIT. Formally speaking, @WRAP returns J such that J = INDEX - K * LIMIT, where K is an integer such that J is in the interval [1, LIMIT]. Informally speaking, @WRAP will subtract or add LIMIT to INDEX until it falls in the range 1 to LIMIT. Therefore, this is just what we need to \"wrap around\" an index in multiperiod planning models.
Incorporating the @WRAP function, we get the corrected, final version of our staffing constraint:
@FOR( DAYS( J):
@SUM( DAYS( I) | I #LE# 5:
START( @WRAP( J - I + 1, 7))) >= REQUIRED( J) );
The Solution：
Below is our staffing model in its entirety:
SETS:
DAYS / MON TUE WED THU FRI SAT SUN/: REQUIRED, START; ENDSETS
DATA:
REQUIRED = 20 16 13 16 19 14 12; ENDDATA
MIN = @SUM( DAYS( I): START( I));
@FOR( DAYS( J):
@SUM( DAYS( I) | I #LE# 5:
START( @WRAP( J - I + 1, 7))) >= REQUIRED( J)
20 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
);
Model: STAFFDEM
Solving the model, we get the solution report:
Optimal solution found at step: 8
Objective value: 22.00000
Variable Value Reduced Cost START( MON) 8.000000 0.0000000 START( TUE) 2.000000 0.0000000 START( WED) 0.0000000 0.0000000 START( THU) 6.000000 0.0000000 START( FRI) 3.000000 0.0000000 START( SAT) 3.000000 0.0000000 START( SUN) 0.0000000 0.0000000
Row Slack or Surplus Dual Price 1 22.00000 1.000000 2 0.0000000 -0.2000000
3 0.0000000 -0.2000000 4 0.0000000 -0.2000000 5 0.0000000 -0.2000000 6 0.0000000 -0.2000000 7 0.0000000 -0.2000000
8 0.0000000 -0.2000000
Solution to STAFFDEM
The objective value of 22 means we need to hire 22 workers. We start our workers according to the schedule:
Mon Tue Wed Thu Fri Sat Sun Start 8 2 0 6 3 3 0
If we look at the surpluses on our staffing requirement rows (rows 2 - 7), we see that the slack values are 0 on all of the days. This means there are no more workers than required and we just meet staffing requirements on every day. Even though this is a small model, trying to come up with a solution this efficient \"by hand\" would be a difficult task.
21 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
职员时序安排模型 一项工作一周7天都需要有人（比如护士工作），每天（周一至周日）所需的最少职员数为20、16、13、16、19、14和12，并要求每个职员一周连续工作5天，试求每周所需最少职员数，并给出安排。注意这里我们考虑稳定后的情况。
model: sets:
days/mon..sun/: required,start; endsets data:
!每天所需的最少职员数;
required = 20 16 13 16 19 14 12; enddata
!最小化每周所需职员数;
min=@sum(days: start); @for(days(J):
@sum(days(I) | I #le# 5:
start(@wrap(J-I+1,7))) >= required(J));
end
计算的部分结果为
Global optimal solution found at iteration: 0 Objective value: 22.00000
Variable Value Reduced Cost REQUIRED( MON) 20.00000 0.000000 REQUIRED( TUE) 16.00000 0.000000 REQUIRED( WED) 13.00000 0.000000 REQUIRED( THU) 16.00000 0.000000 REQUIRED( FRI) 19.00000 0.000000 REQUIRED( SAT) 14.00000 0.000000 REQUIRED( SUN) 12.00000 0.000000 START( MON) 8.000000 0.000000 START( TUE) 2.000000 0.000000 START( WED) 0.000000 0.3333333 START( THU) 6.000000 0.000000 START( FRI) 3.000000 0.000000 START( SAT) 3.000000 0.000000 START( SUN) 0.000000 0.000000
每周最少:22个职员， 周一:8人， 周二:2人， 周三:0人， 周四:6人，
周五和周六:3人， 周日:0人。
用Matlab编程为： 先建立一个M文件：fssp.m 然后再建立：
%fssp.m
f=[1,1,1,1,1,1,1]; %ϵÊý A=[-1,0,0,-1,-1,-1,-1;
22 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
-1,-1,0,0,-1,-1,-1; -1,-1,-1,0,0,-1,-1; -1,-1,-1,-1,0,0,-1; -1,-1,-1,-1,-1,0,0; 0,-1,-1,-1,-1,-1,0; 0,0,-1,-1,-1,-1,-1];
b=[-20,-16,-13,-16,-19,-14,-12]; l=[0,0,0,0,0,0,0];
[xo,fo,exitflag]=linprog(f,A,b,[],[],l)
结果为： xo =
8.0000 2.0000 0.0000 6.0000 3.0000 3.0000 0.0000 fo =
22.0000
exitflag =
1
3.7集循环函数（Set Looping Functions）
Set looping functions operate over an entire set and, with the exception of the @FOR function, produce a single result. The syntax for a set looping function is:
@function( setname [ ( set_index_list)
[ | conditional_qualifier]] : expression_list);
@function corresponds to one of the set looping functions listed below. setname is the name of the set you want to loop over. The set_index_list is optional and is used to create a list of indices, which correspond to
23 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
the parent primitive sets that form the setname set. As LINGO loops through the members of the setname set, it will set the values of the indices in the set_index_list to correspond to the current member of the setname set.
The conditional_qualifier is optional and may be used to limit the scope of the set looping function. When LINGO is looping over each member of the setname set, it evaluates the conditional_qualifier. If the conditional_qualifier evaluates to true, then @function is performed for the set member. Otherwise, it is skipped.
The expression_list is a list of expressions to be applied to each member of the setname set. When using the @FOR function, the expression_list may contain multiple expressions, separated by semicolons. These expressions will be added as constraints to the model. When using the remaining three set looping functions (@SUM, @MAX, and @MIN), the expression_list must contain one expression only. If the set_index_list is omitted, all attributes referenced in the expression_list must be defined on the setname set.
The available set looping functions are listed below:
集循环函数遍历整个集进行操作。其语法为
@function(setname[(set_index_list)[|conditional_qualifier]]:
expression_list);
@function相应于下面罗列的四个集循环函数之一；setname是要遍历的集；set_ index_list是集索引列表；conditional_qualifier是用来限制集循环函数的范围，当集循环函数遍历集的每个成员时，LINGO都要对conditional_qualifier进行评价，若结果为真，则对该成员执行@function操作，否则跳过，继续执行下一次循环。expression_list是被应用到每个集成员的表达式列表，当用的是@for函数时，expression_list可以包含多个表达式，其间用逗号隔开。这些表达式将被作为约束加到模型中。当使用其余的三个集循环函数时，expression_list只能有一个表达式。如果省略set_index_list，那么在expression_list中引用的所有属性的类型都是setname集。
@FOR( setname [ ( set_index_list) [ | cond_qualifier]]: exp_list)
This generates the expressions contained in exp_list for all members of the setname set. @FOR is used to generate constraints over all the members of a set, and is one of the most powerful features of LINGO.
@MAX( setname [ ( set_index_list) [ | cond_qualifier]]: expression)
This returns the maximum value of expression taken over the setname set.
@MIN( setname [ ( set_index_list) [ | cond_qualifier]]: expression)
This returns the minimum value of expression taken over the setname set.
@PROD( setname [ ( set_index_list) [ | cond_qualifier]]: expression)
This returns the product of an expression over the setname set.
24 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
@SUM( setname [ ( set_index_list) [ | cond_qualifier]]: expression)
This returns the sum of an expression over the setname set.
Set looping functions are discussed in more detail in section Set Looping Functions in Chapter 2.
3.8 辅助功能函数（Miscellaneous Functions）
@IF( logical_condition, true_result, false_result)
The @IF function evaluates logical_condition and, if true, returns true_result, otherwise it returns false_result. For example, consider the following simple model that uses @IF to compute fixed production costs:
MIN = COST;
COST = XCOST + YCOST;
XCOST = @IF( X #GT# 0, 100, 0) + 2 * X; YCOST = @IF( Y #GT# 0, 60, 0) + 3 * Y;
X + Y >= 30;
Model: IFCOST
We produce two products梄 and Y. We want to minimize total cost, subject to producing at least 30 total units of X and Y. If we produce X, there is a fixed charge of 100 along with a variable cost of 2. Similarly, for Y, these respective values are 60 and 3. We use the @IF function to determine if either of the products are being produced in order to apply the relevant fixed cost. This is accomplished by testing to see if their production levels are greater than 0. If so, we return the fixed cost value, otherwise, we return zero.
Experienced modelers know that, without the benefit of an @IF function, modeling fixed costs requires invoking some \"tricks\" using binary integer variables. The resulting models are not as intuitive as models constructed using @IF. The caveat, however, is that the @IF function is not a linear function. At best, the graph of an @IF function will be piecewise linear. In our current example, the @IF functions are piecewise linear with a discontinuous break at the origin. As we discuss in the chapter On Mathematical Modeling, it is always best to try and keep a model linear. Barring this, it is best for all functions in a nonlinear model to be continuous. Clearly, then, the @IF function is a problem in that it violates both these conditions. Thus, models containing @IF functions may be tough to solve to global optimality. Fortunately, LINGO has two options that can help overcome the difficult nature of models containing @IF functions條inearization and global optimization.
25 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
To illustrate the difficulty in solving models with discontinuous functions such as @IF, we will solve our example model with both linearization and global optimization disabled. When we do this, we get the following solution:
Local optimal solution found at iteration: 42
Objective value: 160.0000
Variable Value COST 160.0000 XCOST 160.0000 YCOST 0.000000 X 30.00000
Y 0.000000
This solution involves producing only X at a total cost of 160. Clearly, this is merely a locally optimal point, given that producing only Y and not X will result in a lower total cost of 150. In order to find the globally optimal point we must resort to either the linearization or global optimization features in LINGO. Briefly, linearization seeks to reformulate a nonlinear model into a mathematically equivalent linear model. This is desirable for two reasons. First, and most important, linear models can always be solved to global optimality. Secondly, linear models will tend to solve much faster than equivalent nonlinear models. Unfortunately, linearization can抰 always transform a model into an equivalent linear state, in which case, it may be of no benefit. Fortunately, our sample model can be entirely linearized. To enable the linearization option, run the LINGO|Options command and set the Linearization Degree to High on the General Solver tab.
Global optimization breaks a model down into a series of smaller, local models. Once this series of local models has been solved, a globally optimal solution can be determined. To enable global optimization, run the LINGO|Options command, select the Global Solver tab, then click on the Global Solver checkbox. Note that the global solver is an add-on option to LINGO. The global solver feature will not be enabled for some installations. Run the
Help|About LINGO command to determine if your installation has the global solver capability enabled.
Regardless, whether using the linearization option or the global solver, LINGO obtains the true, global solution:
Global optimal solution found at iteration: 6
Objective value: 150.0000
Variable Value
26 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
COST 150.0000 XCOST 0.000000 YCOST 150.0000 X 0.000000
Y 30.00000
Note: Starting with release 9.0, the false branch of the @IF function may contain arithmetic errors without causing the solver to trigger an error. This makes the @IF function useful in avoiding problems when the solver strays into areas where certain functions become undefined. For instance, if your model involves division by a variable, you might use @IF as follows: @IF( X #GT# 1.E-10, 1/X, 1.E10).
@WARN( 'text', logical_condition)
This function displays the message 憈ext?if the logical_condition is met. This feature is useful for verifying the validity of a model's data. In the following example, if the user has entered a negative interest rate, the message \"INVALID營NTEREST燫ATE\" is displayed:
! A model of a home mortgage;
DATA:
! Prompt the user for the interest rate, years, and value of mortgage.
We will compute the monthly payment; YRATE = ?; YEARS = ?; LUMP = ?; ENDDATA
! Number of monthly payment; MONTHS = YEARS * 12;
! Monthly interest rate;
( 1 + MRATE) ^ 12 = 1 + YRATE;
! Solve next line for monthly payment;
LUMP = PAYMENT * @FPA( MRATE, MONTHS);
! Warn them if interest rate is negative
@WARN( 'INVALID INTEREST RATE',
YRATE #LT# 0);
27 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
@USER( user_determined_arguments)
The user can supply this in an external DLL or object code file. For a detailed example on the use of @USER, see User Defined Functions.
4.灵敏度分析 i.e：
某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：
木料 漆工 木工 成品单价 每个书桌 8单位 4单位 2单位 60单位 每个餐桌 6单位 2单位 1.5单位 30单位 每个椅子 1单位 1.5单位 0.5单位 20单位 现有资源总数 48单位 20单位 8单位 若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？ max=60*desks+30*tables+20*chairs; 8*desks+6*tables+chairs<=48;
4*desks+2*tables+1.5*chairs<=20; 2*desks+1.5*tables+.5*chairs<=8; tables<=5;
Global optimal solution found.
Objective value: 280.0000 Total solver iterations: 3
Variable Value Reduced Cost DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000
Row Slack or Surplus Dual Price 1 280.0000 1.000000 2 24.00000 0.000000 3 0.000000 10.00000 4 0.000000 10.00000 5 5.000000 0.000000
“Slack or Surplus”给出松驰变量的值：
第1行松驰变量 =280（模型第一行表示目标函数，所以第二行对应第一个约束） 第2行松驰变量 =24
28 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
第3行松驰变量 =0 第4行松驰变量 =0 第5行松驰变量 =5
“Reduced Cost”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时, 目标函数的变化率。其中基变量的reduced cost值应为0， 对于非基变量 Xj, 相应的 reduced cost值表示当某个变量Xj 增加一个单位时目标函数减少的量( max型问题)。本例中：变量tables对应的reduced cost值为5，表示当非基变量tables的值从0变为 1时（此时假定其他非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），最优的目标函数值 = 280 - 5 = 275。 “DUAL PRICE”（对偶价格）表示当对应约束有微小变动时, 目标函数的变化率。输出结果中对应于每一个约束有一个对偶价格。 若其数值为p， 表示对应约束中不等式右端项若增加1 个单位，目标函数将增加p个单位（max型问题）。显然，如果在最优解处约束正好取等号（也就是“紧约束”，也称为有效约束或起作用约束），对偶价格值才可能不是0。本例中：第3、4行是紧约束，对应的对偶价格值为10，表示当紧约束
3) 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 20 变为 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 21 时，目标函数值 = 280 +10 = 290。对第4行也类似。 对于非紧约束（如本例中第2、5行是非紧约束），DUAL PRICE 的值为0, 表示对应约束中不等式右端项的微小扰动不影响目标函数。有时, 通过分析DUAL PRICE, 也可对产生不可行问题的原因有所了解。
5.求解选项卡
（1）Interface（界面）选项卡
选项组 选项 含义 如果选择该选项，求解程序遇到错误时将打开一Errors In 个对话框显示错误，你关闭该对话框后程序才会Dialogs(错误对话继续执行；否则，错误信息将在报告窗口显示，框) 程序仍会继续执行 Splash Screen （弹出屏幕） General （一般选项） Status Bar （状态栏） Status Window （状态窗口） Terse Output （简洁输出） Toolbar （工具栏） 如果选择该选项，则LINGO每次启动时会在屏幕上弹出一个对话框，显示LINGO的版本和版权信息；否则不弹出 如果选择该选项，则LINGO系统在主窗口最下面一行显示状态栏；否则不显示 如果选择该选项，则LINGO系统每次运行LINGO|Solve命令时会在屏幕上弹出状态窗口；否则不弹出 如果选择该选项，则LINGO系统对求解结果报告等将以简洁形式输出；否则以详细形式输出 如果选择该选项，则显示工具栏；否则不显示 29 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
Solution Cutoff （解的截断） File Format （文件格式） 小于等于这个值的解将报告为“0”（缺省值是-910） lg4 （extended） 模型文件的缺省保存格式是lg4格式（这是一种（lg4，扩展格式） 二进制文件，只有LINGO能读出） lng （text only） （lng，纯文本格模型文件的缺省保存格式是lng格式（纯文本） 式） 语法配色的行数限制（缺省为1000）。LINGO模型窗口中将LINGO关键此显示为兰色，注释为绿色，其他为黑色，超过该行数限制后则不再区分颜色。特别地，设置行数限制为0时，整个文件不再区分颜色。 设置语法配色的延迟时间（秒，缺省为0，从最后一次击键算起）。 如果选择该选项，则模型中当前光标所在处的括号及其相匹配的括号将以红色显示；否则不使用该功能 Line limit （行数限制） Syntax Coloring （语法配色） Delay （延迟） Paren Match （括号匹配） Send Reports to Command Window 如果选择该选项，则输出信息会发送到命令窗（报告发送到命令口；否则不使用该功能 窗口） 如果选择该选项，则用File|Take Command命令Echo Input 执行命令脚本文件时，处理信息会发送到命令窗（输入信息反馈） 口；否则不使用该功能 命令窗口能显示的行数的最大值为Maximum（缺Line Count Limits 省为800）；如果要显示的内容超过这个值，每次（行数限制） 从命令窗口滚动删除的最小行数为Minimum（缺省为400） 命令窗口每次显示的行数的最大值为Length（缺Page Size Limit省为没有限制），显示这么多行后会暂停，等待（页面大小限制） 用户响应；每行最大字符数为Width（缺省为74，可以设定为64-200之间），多余的字符将被截断 Command Window （命令窗口） （2）General Solver（通用求解器）选项卡
选项组 选项 含义 缺省值为32M，矩阵生成器使用的内存超过该限Generator Memory Limit （MB）制，LINGO将报告\"The model generator ran out 矩阵生成器的内存限制（兆） of memory\" 30 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
Runtime Limits 运行限制 Iterations 迭代次数 求解一个模型时，允许的最大迭代次数（缺省值为无限） Time (sec) 求解一个模型时，允许的最大运行时间（缺省值运行时间（秒） 为无限） 求解时控制对偶计算的级别，有三种可能的设置： ·None: 不计算任何对偶信息； ·Prices：计算对偶价格（缺省设置）； ·Prices and Ranges：计算对偶价格并分析敏感性。 控制重新生成模型的频率，有三种可能的设置： ·Only when text changes：只有当模型的文本修改后才再生成模型； ·When text changes or with external references：当模型的文本修改或模型含有外部引用时（缺省设置）； ·Always：每当有需要时。 决定求解模型时线性化的程度，有四种可能的设置： Solver Decides：若变量数小于等于12个，则尽可能全部线性化；否则不做任何线性化（缺省设置） ·None：不做任何线性化 ·Low：对函数@ABS(), @MAX(), @MIN(), @SMAX(), @SMIN()，以及二进制变量与连续变量的乘积项做线性化 ·High：同上，此外对逻辑运算符#LE#, #EQ#, #GE#, #NE#做线性化 Dual Computations （对偶计算） Model Regeneration （模型的重新生成） Linearization（线性化） Degree （线性化程度） Big M（线性化6设置线性化的大M系数（缺省值为10）。 的大M系数） Delta（线性化的误差限） Allow Unrestricted Use of Primitive Set Member Names （允许无限制地使用基本集合的成员名） 设置线性化的误差限（缺省值为10）。 选择该选项可以保持与LINGO4.0以前的版本兼容：即允许使用基本集合的成员名称直接作为该成员在该集合的索引值（LINGO4.0以后的版本要求使用@INDEX函数）。 -6Check for Duplicate Names in 选择该选项,LINGO将检查数据和模型中的名称是Data and Model(检查数据和模否重复使用，如基本集合的成员名是否与决策变型中的名称是否重复使用) 量名重复。 31 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
Use R/C format names for MPS 在MPS文件格式的输入输出中，将变量和行名转I/O （在MPS文件格式的输入输换为R/C格式 出中使用R/C格式的名称） （3）Linear Solver（线性求解器）选项卡
选项组 选项 含义 求解时的算法，有四种可能的设置： ·Solver Decides：LINGO自动选择算法 （缺省设置） ·Primal Simplex：原始单纯形法 ·Dual Simplex：对偶单纯形法 ·Barrier: 障碍法 (即内点法) Method 求解方法 Initial Linear Feasibility 控制线性模型中约束满足的初始误差限（缺省值-6Tol 初始线性可行性误差限 为3*10） Final Linear Feasibility 控制线性模型中约束满足的最后误差限（缺省值-7Tol. 最后线性可行性误差限 为10） 控制是否检查模型中的无关变量，从而降低模型的规模： Model Reduction ·Off：不检查 模型降维 ·On：检查 ·Solver Decides：LINGO自动决定（缺省设置） 有三种可能的设置： ·Solver Decides：LINGO自动决定（缺省设置） ·Partial：LINGO 对一部分可能的出基变量进行Primal Solver 尝试 原始单纯形法 ·Devex：用Steepest-Edge（最陡边）近似算法对所有可能的变量进行尝试，找到使目标值下降最多的出基变量 有三种可能的设置： ·Solver Decides：LINGO自动决定（缺省设置） Dual Solver·Dantzig：按最大下降比例法确定出基变量 对偶单纯形法 ·Steepest-Edge：最陡边策略，对所有可能的变量进行尝试，找到使目标值下降最多的出基变量 选择该选项，LINGO将尝试将一个大模型分解为几个小模型求解；否则不尝试 选择该选项,LINGO检查模型中的数据是否平衡（数量级是否相差太大）并尝试改变尺度使模型平衡；否则不尝试 Pricing Strategies 价格策略（决定出基变量的策略） Matrix Decomposition 矩阵分解 Scale Model 模型尺度的改变 32 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
（4）Nonlinear Solver（非线性求解器）选项卡
选项组 选项 含义 Initial Nonlinear -3Feasibility Tol. 初始非线性控制模型中约束满足的初始误差限（缺省值为10） 可行性误差限 Final Nonlinear Feasibility -6控制模型中约束满足的最后误差限（缺省值为10） Tol. 最后非线性可行性误差限 Nonlinear Optimality Tol. 非线性规划的最优性误差限 当目标函数在当前解的梯度小于等于这个值以后，停止迭代（缺省值为2*10） -7Slow Progress Iteration 当目标函数在连续这么多次迭代没有显著改进以Limit缓慢改进的迭代次数的上后，停止迭代（缺省值为5） 限 Derivatives 导数 Numerical 数值法 Analytical 解析法 用有限差分法计算数值导数（缺省值） 用解析法计算导数（仅对只含有算术运算符的函数使用） Crash Initial 选择该选项, LINGO将用启发式方法生成初始解；Solution 否则不生成（缺省值） 生成初始解 Quadratic 选择该选项, LINGO将判别模型是否为二次规划，Recognition 若是则采用二次规划算法（包含在线性规划的内点识别二次规划 法中）；否则不判别（缺省值） Selective Constraint Eval 有选择地检查约束 SLP Directions SLP方向 选择该选项, LINGO在每次迭代时只检查必须检查的约束（如果有些约束函数在某些区域没有定义，这样做会出现错误）；否则，检查所有约束（缺省值） 选择该选项, LINGO在每次迭代时用SLP (Successive LP，逐次线性规划)方法寻找搜索方向（缺省值） Strategies 策略 选择该选项, LINGO在每次迭代时将对所有可能的Steepest Edge 变量进行尝试，找到使目标值下降最多的变量进行最陡边策略 迭代；缺省值为不使用最陡边策略 （5）Integer Pre-Solver（整数预处理求解器）选项卡
选项组 选项 含义 33 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
Heuristics 启发式方法 Level Min Seconds 控制采用启发式搜索的次数（缺省值为3，可能的值为0-100）. 启发式方法的目的是从分枝节点的连续解出发，搜索一个好的整数解。 每个分枝节点使用启发式搜索的最小时间（秒） 控制采用探测（Probing）技术的级别（探测能够用于混合整数线性规划模型，收紧变量的上下界和约束的右端项的值）。可能的取值为： ·Solver Decides：LINGO自动决定（缺省设置） ·1-7：探测级别逐步升高。 控制在分枝定界树中，哪些节点需要增加割（平面），可能的取值为： ·Root Only：仅根节点增加割（平面） ·All Nodes：所有节点均增加割（平面） ·Solver Decides：LINGO自动决定（缺省设置） 控制生成的割（平面）的个数相对于原问题的约束个数的上限（比值），缺省值为0.75 为了寻找合适的割，最大迭代检查的次数。有两个参数： ·Root：对根节点的次数（缺省值为200） ·Tree：对其他节点的次数（缺省值为2） 控制生成的割（平面）的策略，共有12种策略可供选择。 （如想了解细节，请参阅整数规划方面的专著） Probing Level 探测水平（级别） Application 应用节点 Constraint Cuts 约束的割（平面） Relative Limit 相对上限 Max Passes 最大迭代检查的次数 Types 类型 （6）Integer Solver（整数求解器）选项卡
整数预处理程序只用于整数线性规划模型（ILP模型），对连续规划和非线性模型无效。
选项组 选项 含义 控制分枝策略中优先对变量取整的方向，有三种选择： ·Both：LINGO自动决定（缺省设置） ·Up：向上取整优先 ·Down：向下取整优先 控制分枝策略中优先对哪些变量进行分枝，有两种选择： ·LINGO Decides：LINGO自动决定（缺省设置） ·Binary：二进制（0-1）变量优先 当变量与整数的绝对误差小于这个值时，该变量-6被认为是整数。缺省值为10 当变量与整数的相对误差小于这个值时，该变量-6被认为是整数。缺省值为8*10 Direction Branching 分枝 Priority Absolute Integrality 绝对误差限 整性 Relative 相对误差限 34 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
LP Solver LP求解程序 Warm Start 热启动 当以前面的求解结果为基础，热启动求解程序时采用的算法，有四种可能的设置： ·LINGO Decides：LINGO自动选择算法（缺省设置） ·Primal Simplex：原始单纯形法 ·Dual Simplex：对偶单纯形法 ·Barrier: 障碍法 (即内点法) 当不以前面的求解结果为基础，冷启动求解程序时采用的算法，有四种可能的设置：（同上，略） 当当前目标函数值与最优值的绝对误差小于这个值时，当前解被认为是最优解（也就是说：只需要搜索比当前解至少改进这么多个单位的解）。缺-8省值为8*10 当当前目标函数值与最优值的相对误差小于这个值时，当前解被认为是最优解（也就是说：只需要搜索比当前解至少改进这么多百分比的解）。缺-8省值为5*10 Cold Start 冷启动 Absolute 目标函数的绝对误差限 Optimality Relative 最优性 目标函数的相对误差限 Time To Relative 在程序开始运行后这么多秒内，不采用相对误差开始采用相对误限策略；此后才使用相对误差限策略。缺省值为差限的时间（秒） 100秒。 Hurdle 篱笆值 同上一章LINDO部分的介绍 控制如何选择节点的分枝求解，有以下选项： ·LINGO Decides： LINGO自动选择（缺省设置） Node Selection ·Depth First：按深度优先 节点选择 Tolerances ·Worst Bound：选择具有最坏界的节点 误差限 ·Best Bound：选择具有最好的界的节点 控制采用强分枝的层数。也就是说，对前这么多层的分枝，采用强分枝策略。所谓强分枝，就是在一个节点对多个变量分别尝试进行预分枝，找出其中最好的解（变量）进行实际分枝。 Strong Branch 强分枝的层数 （7）Global Solver（全局最优求解器）选项卡
选项组 Global Solver 全局最优求解程序 选项 含义 选择该选项,LINGO将用全局最优求解程序Use Global Solver 求解模型，尽可能得到全局最优解（求解花使用全局最优求解费的时间可能很长）；否则不使用全局最优求程序 解程序，通常只得到局部最优解 35 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
有两个域可以控制变量上界（按绝对值）： 1、 Value：设定变量的上界，缺省值为10； 2、 Application列表框设置这个界的三种 Upper 应用范围： ·None: 所有变量都不使用这个上界； ·All: 所有变量都使用这个上界； ·Selected：先找到第1个局部最优解，然后对满足这个上界的变量使用这个上界（缺省设置） 有两个域可以控制变量上界（按绝对值）： Tolerances 误差限 1、 Optimality：只搜索比当前解至少改进这么多个单位的解（缺省值为10）； 2、 Delta：全局最优求解程序在凸化过程中-7增加的约束的误差限（缺省值为10）。 可以控制全局最优求解程序的三类策略： 1、Branching：第1次对变量分枝时使用的分枝策略： ·Absolute Width（绝对宽度） ·Local Width（局部宽度） ·Global Width（全局宽度） ·Global Distance（全局距离） ·Abs (Absolute) Violation（绝对冲突） ·Rel (Relative) Violation（相对冲突，缺省设置） 2、Box Selection: 选择活跃分枝节点的方法： ·Depth First（深度优先） ·Worst Bound（具有最坏界的分枝优先，缺省设置） 3、Reformulation：模型重整的级别： ·None（不进行重整） ·Low（低） ·Medium（中） ·High（高，缺省设置） 尝试多少个初始点求解，有以下几种可能的设置： ·Solver Decides：由LINGO决定（缺省设置，对小规模NLP问题为5次，对大规模问题不使用多点求解） ·Off：不使用多点求解 ·N（>1的正整数）：N点求解 ·Barrier: 障碍法 (即内点法) -610Variable Bound 变量上界 Strategies 策略 Multistart Solver 多初始点求解程序 Attempts 尝试次数 36 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
6.综合案例
旅行售货员问题（Traveling Salesman Problem）
有一个推销员，从城市1出发，要遍访城市2，3，…，n各一次，最后返回城市1。已知从城市i到j的旅费为ij，问他应按怎样的次序访问这些城市，使得总旅费最少？
可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。
在下述意义下，引入一些0-1整数变量：
1，巡回路线是从i到j,且ijxij0，其它情况n 其目标只是使i,j1ccijxij为最小。
这里有两个明显的必须满足的条件：
访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。
xj1nij1,1,i1,2,,n
到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：
6 3
4 1 2
5
以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回。
这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量
i1xnijj1,2,,nui(i2,3,,n)附加到问题中。可把这些变量看作是连续的（最然这些变量在最优解中取普通的
uiujnxijn1,2ijn。
整数值）。现在附加下面形式的约束条件
为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。
首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为
i1i2iki1，则必有
ui1ui2nn1ui21ui3nn1uikui1nn1把这k个式子相加，有
37 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
nn1，矛盾！
故假设不正确，结论（1）得证。
下面证明（2），采用构造法。对于任意的总巡回
。下面来证明总巡回满足该约束条件。
1i1in11，可取
ui访问城市i的顺序数，取值范围为{0,1,,n2}。
2ijn因此，
(ⅰ)总巡回上的边
uiujn2,ui1ui2nn1n1ui2ui3nn1n1uunn1n1in1in2（ⅱ）非总巡回上的边
uirujn2n1,r1,2,,n2,j{2,3,,n}{ir,ir1}uin1ujn2n1,j{2,3,,n}{ir}
从而结论（2）得证。
这样我们把TSP转化成了一个混合整数线性规划问题。
显然，当城市个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发现多项式时间的算法。对于小规模问题，我们求解这个混合整数线性规划问题的方式还是有效的。
!旅行售货员问题; model: sets:
city / 1.. 5/: u; link( city, city): dist, ! 距离矩阵; x; endsets
n = @size( city);
data: !距离矩阵，它并不需要是对称的; dist = 0 2 6 7 4
mins.t.zni,j1ijcijnijxijxi1n1,1,j1,2,,ni1,2,,n2ijnxj1ijuiujnxijn1,xij0,1,ui0,i,j1,2,,ni2,3,,n 2 0 5 3 8 6 5 0 9 7 7 3 9 0 9
38 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
4 8 7 9 0 ; !随机产生，这里可改为你要解决的问题的数据;
enddata
!目标函数;
min = @sum( link: dist * x);
@FOR( city( K): !进入城市K;
@sum( city( I)| I #ne# K: x( I, K)) = 1;
!离开城市K;
@sum( city( J)| J #ne# K: x( K, J)) = 1; );
!保证不出现子圈;
@for(city(I)|I #gt# 1:
@for( city( J)| J#gt#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)<=n-1); );
!限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解; @for(city(I) | I #gt# 1: u(I)<=n-2 ); !定义X为0\\1变量;
@for( link: @bin( x)); end
Global optimal solution found.
Objective value: 25.00000 Extended solver steps: 0 Total solver iterations: 19
Variable Value Reduced Cost N 5.000000 0.000000 U( 1) 0.000000 0.000000 U( 2) 0.000000 0.000000 U( 3) 2.000000 0.000000 U( 4) 1.000000 0.000000 U( 5) 3.000000 0.000000 DIST( 1, 1) 0.000000 0.000000 DIST( 1, 2) 2.000000 0.000000 DIST( 1, 3) 6.000000 0.000000 DIST( 1, 4) 7.000000 0.000000 DIST( 1, 5) 4.000000 0.000000 DIST( 2, 1) 2.000000 0.000000 DIST( 2, 2) 0.000000 0.000000 DIST( 2, 3) 5.000000 0.000000 DIST( 2, 4) 3.000000 0.000000 DIST( 2, 5) 8.000000 0.000000 DIST( 3, 1) 6.000000 0.000000
39 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
DIST( 3, 2) 5.000000 0.000000 DIST( 3, 3) 0.000000 0.000000 DIST( 3, 4) 9.000000 0.000000 DIST( 3, 5) 7.000000 0.000000 DIST( 4, 1) 7.000000 0.000000 DIST( 4, 2) 3.000000 0.000000 DIST( 4, 3) 9.000000 0.000000 DIST( 4, 4) 0.000000 0.000000 DIST( 4, 5) 9.000000 0.000000 DIST( 5, 1) 4.000000 0.000000 DIST( 5, 2) 8.000000 0.000000 DIST( 5, 3) 7.000000 0.000000 DIST( 5, 4) 9.000000 0.000000 DIST( 5, 5) 0.000000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 1.000000 2.000000 X( 1, 3) 0.000000 6.000000 X( 1, 4) 0.000000 7.000000 X( 1, 5) 0.000000 4.000000 X( 2, 1) 0.000000 2.000000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 5.000000 X( 2, 4) 1.000000 3.000000 X( 2, 5) 0.000000 8.000000 X( 3, 1) 0.000000 6.000000 X( 3, 2) 0.000000 5.000000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 0.000000 9.000000 X( 3, 5) 1.000000 7.000000 X( 4, 1) 0.000000 7.000000 X( 4, 2) 0.000000 3.000000 X( 4, 3) 1.000000 9.000000 X( 4, 4) 0.000000 0.000000 X( 4, 5) 0.000000 9.000000 X( 5, 1) 1.000000 4.000000 X( 5, 2) 0.000000 8.000000 X( 5, 3) 0.000000 7.000000 X( 5, 4) 0.000000 9.000000 X( 5, 5) 0.000000 0.000000
Row Slack or Surplus Dual Price 1 0.000000 0.000000
40 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
2 25.00000 -1.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 6.000000 0.000000 14 0.000000 0.000000 15 7.000000 0.000000 16 2.000000 0.000000 17 3.000000 0.000000 18 0.000000 0.000000 19 3.000000 0.000000 20 0.000000 0.000000 21 6.000000 0.000000 22 1.000000 0.000000 23 3.000000 0.000000 24 2.000000 0.000000 25 3.000000 0.000000 26 1.000000 0.000000 27 2.000000 0.000000 28 0.000000 0.000000
7. Matlab——GA Tool
以测试函数Rastrigin’s和help中实例来说明：
1.
41 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
2.
42 / 43
真诚为您提供优质参考资料，若有不当之处，请指正。
43 / 43
因篇幅问题不能全部显示，请点此查看更多更全内容