线性规划

第一章线性规划1．1将下述线性规划问题化成标准形式1)min z＝－3x1＋4x2－2x3＋5 x4－x2＋2x3－x4＝－24xst. x1＋x2－x3＋2 x4 ≤14－2x1＋3x2＋x3－x4 ≥ 2x1，x2，x3≥0，x4无约束2)min z ＝2x1－2x2＋3x3＋x2＋x3＝4－xst. －2x1＋x2－x3≤6x1≤0 ，x2≥0，x3无约束1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

1)min z＝2x1＋3x24x1＋6x2≥6st2x1＋2x2≥4x1，x2≥02)max z＝3x1＋2x22x1＋x2≤2st3x1＋4x2≥12x1，x2≥03)max z＝x1＋x26x1＋10x2≤120st5≤x1≤103≤x2≤84)max z＝5x1＋6x22x1－x2≥2st－2x1＋3x2≤2x1，x2≥01．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解（1）min z＝5x1－2x2＋3x3＋2x4x1＋2x2＋3x3＋4x4＝7st2x1＋2x2＋x3 ＋2x4＝3x1，x2，x3，x4≥01．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。

1) maxz ＝10x 1＋5x 23x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥02) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥01．5 分别用大M 法与两阶段法求解下列LP 问题。

1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥02) minz ＝ 4x 1＋x 2 3x 1＋x 2 ＝3 st 4x 1＋3x 2 －x 3 ＝6x 1＋2x 2 ＋x 4＝4x 1，x 2 ，x 3，x 4≥01231231231231233)max 101512539561515.225,,0z x x x x x x x x x st x x x x x x =++++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩1．6第二章对偶与灵敏度分析2．1写出以下线性规划问题的DLP1)minz＝2x1＋2x2＋4x3x1＋3x2＋4x3≥2st 2x1＋x2＋3x3≤3x1＋4x2＋3x3＝5x1，x2≥0，x3无约束2)max z＝5x1＋6x2＋3x3x1＋2x2＋2x3＝5st－x1＋5x2－x3≥34x1＋7x2＋3x3≤8x1无约束，x2≥0，x3≤03)max z＝c1x1＋c2x2＋c3x3a11x1＋a12x2＋a13x3≤b1st a21x1＋a22x2＋a23x3＝b2a31x1＋a32x2＋a33x3≥b3x1≥0，x2≤0，x3无约束2．2对于给出的LP：minz＝2x1＋3x2＋5x3＋6x4x1＋2x2＋3x3＋x4≥2st－2x1＋x2－x3＋3x4≤－3x j≥0 （j=1,2,3,4）1)写出DLP；2)用图解法求解DLP；3)利用2）的结果及根据对偶性质写出原问题的最优解。

2．3对于给出LP：maxz＝x1＋2x2＋x3x1＋x2－x3≤2st x1－x2＋x3＝12x1＋x2＋x3≥2x1≥0，x2≤0，x3无约束1)写出DLP；2)利用对偶问题性质证明原问题目标函数值Z≤12．4已知LP：max z＝x1＋x2－x1＋x2＋x3≤2st－2x1＋x2－x3≤1x j≥0试根据对偶问题性质证明上述线性问题目标函数值无界。

2．5 给出LP ： maxz ＝2x 1＋4x 2＋x 3＋x 4 x 1＋ 3x 2 ＋x 4 ≤8 2x 1＋ x 2 ≤6 st. x 2 ＋ x 3＋ x 4≤6x 1＋ x 2 ＋ x 3 ≤9 x j ≥01) 写出DLP ；2) 已知原问题最优解X ＝（2,2，4,0），试根据对偶理论，直接求出对偶问题的最优解。

2．6 用对偶单纯形法求解下列线性规划问题1) minz ＝4x 1＋12x 2＋18x 3 x 1 ＋3x 3 ≥3st 2 x 2＋2x 3 ≥5 x j ≥0 (j=1,2,3)1231231231232)min 524324.63510,,0z x x x x x x st x x x x x x =++++≥⎧⎪++≥⎨⎪≥⎩2．7考虑如下线性规划问题 minz ＝60x 1＋40x 2＋80x 3 3x 1＋2x 2＋ x 3 ≥2 st 4x 1＋ x 2＋3x 3 ≥4 2x 1＋2x 2＋2x 3 ≥3x j ≥0 1) 写出DLP ；2) 用对偶单纯形法求解原问题； 3) 用单纯形法求解其对偶问题； 4) 对比以上两题计算结果。

2．8 已知LP ：maxz ＝2x 1－x 2＋x 3 x 1＋ x 2＋ x 3≤6 st －x 1＋2x 2 ≤4x 1，x 2，x 3≥0 1) 用单纯形法求最优解2) 分析当目标函数变为maxz ＝2x 1＋3x 2＋x 3时最优解的变化； 3) 分析第一个约束条件右端系数变为3时最优解的变化。

2．9给出线性规划问题maxz＝2x1＋3x2＋x31/3x1＋1/3x2＋1/3x3≤1st 1/3x1＋4/3x2＋7/3x3≤3x j≥0试分析下列各种条件下，最优解（基）的变化：1)目标函数中变量x3的系数变为6；2)分别确定目标函数中变量x1和x2的系数C1、C2在什么范围内变动时最优解不变；3)约束条件的右端由 1 变为 2 ；3 3第三章运输问题3．13．23．33.4 某市有三个面粉厂，他们供给三个面食加工厂所需的面粉，各面粉厂的产量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均式于下表。

假定在第1，2和3面食加工厂制作单位面粉食品的利润分别为12元、16元和11元，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）。

第四章 动态规划4．1 现有天然气站A ，需铺设管理到用气单位E ，可以选择的设计路线如下图，B 、C 、D 各点是中间加压站，各线路的费用如图所标注（单位：万元），试设计费用最低的线路。

4．2一艘货轮在A 港装货后驶往F 港，中途需靠港加油、加淡水三次，从A 港到F 港全部可能的航运路线及两港之间距离如图，F 港有3个码头F 1，F 2，F 3，试求最合理停靠的码头及航线，使总路程最短。

4．3 某公司有资金4万元，可向A 、B 、C 三个项目投资，已知各项目的投资回报如下，求最大回报。

F4．4某厂有1000台机器，高负荷生产，产品年产量S1与投入机器数Y1的关系为S1＝8Y1，机器完好率为0.7；低负荷生产，产品年产量S2与投入机器数Y2的关系为S2＝5Y2，机器完好率为0.9；请制定一个五年计划，使总产量最大。

4．5某工厂生产三种产品，各种产品重量与利润关系如下表，现将此三种产品运往市场出售，运输能力总重量不超过6t ，问应运输每种产品各多少件可使总利润最大。

4.6 用动态规划方法求解2123123123max 49224310,,0z x x x x x x x x x =++++≤⎧⎨≥⎩第五章 存储论5．1 某建筑工地每月需用水泥800t ，每t 定价2000元，不可缺货。

设每t 每月保管费率为货物单价的0.2%，每次订购费为300元，求最佳订购批量、经济周期与最小费用。

5．2 一汽车公司每年使用某种零件150，000件，每件每年保管费0.2元，不允许缺货，试比较每次订购费为1,000元或100元两种情况下的经济订购批量、经济周期与最小费用。

5．3 某拖拉机厂生产一种小型拖拉机，每月可生产1000台，但对该拖拉机的市场需要量为每年4,000台。

已知每次生产的准备费用为15,000元，每台拖拉机每月的存贮费为10元，允许缺货（缺货费为20元/台月），求经济生产批量、经济周期与最小费用。

5．4 某产品每月需求量为8件，生产准备费用为100元，存贮费为5元/月件。

在不允许缺货条件下，比较生产速度分别为每月20件和40件两种情况下的经济生产批量、经济周期与最小费用。

5．5对某种电子元件每月需求量为4,000件，每件成本为150元，每年的存贮费为成本的10%，每次订购费为500元。

求：（1）不允许缺货条件下的最优存贮策略；（2）允许缺货（缺货费为100元/件年）条件下的最优存贮策略。

5．6某农机维修站需要购一种农机配件，其每月需要量为150件，订购费为每次400元，存贮费为0.96元/件月，并不允许缺货。

（1）求经济订购批量、经济周期与最小费用；（2）该厂为少占用流动资金，希望进一步降低存贮量。

因此，决定使订购和存贮总费用可以超过原最低费用的10%，求这时的最优存贮策略。

5．7某公司每年需电容器15,000个，每次订购费80元，保管费1元/个年，不允许缺货。

若采购量少于1000个时，每个单价为5元，当一次采购1000个以上时每个单价降为4.9元。

求该公司的最优采购策略。

5．8某工厂对某种物料的年需要量为10,000单位，每次订货费为2,000元，存贮费率为20%。

该物料采购单价和采购数量有关，当采购数量在2,000单位以下时，单价为100元；当采购数量在2,000及以上单位时，单价为80元。

求最优采购策略。

5．9某制造厂在装配作业中需用一种外购件，全年需求量为300万件，不允许缺货；一次订购费为100元；存贮费为0.1元/件月。

该外购件进货单价和订购批量Q有关，具体如下表，求最佳订购策略。

5．10试证明：一个允许缺货的EOQ模型的费用，决不会超过一个具有相同存贮费、订购费、但又不允许缺货的EOQ模型的费用。

5．11某时装屋在某年春季欲销售某种流行时装。

据估计，该时装可能的销售量见该款式时装每套进价180元，售价200元。

因隔季会过时，故在季末需低价抛售完，较有把握的抛售价为每套120元。

问该时装屋在季度初时一次性进货多少为宜？第六章排队论6．1某店仅有一个修理工人，顾客到达过程为Poisson流，平均3人/h，修理时间服从负指数分布，平均需10min。

求：（1）店内空闲的概率；（2）有4个顾客的概率；（3）至少有1个顾客的概率；（4）店内顾客的平均数；（5）等待服务的顾客的平均数；（6）平均等待修理时间；（7）一个顾客在店内逗留时间超过15 min的概率。

6．2设有一单人打字室，顾客的到达为为Poisson流，平均到达时间间隔为20 min ，打字时间服从负指数分布，平均为15min。

求：（1）顾客来打字不必等待的概率；（2）打字室内顾客的平均数；（3）顾客在打字室内的平均逗留时间；（4）若顾客在打字室内的平均逗留时间超过1.25h，则主人将考虑增加设备及打字员。