线性规划
第一章　线性规划
1．1 将下述线性规划问题化成标准形式
1) min z ＝ －3x1 ＋ 4x2 － 2x3 ＋ 5 x4
            　4x1 －  x2 ＋ 2x3 －　x4　＝ －2
    st.          x1 ＋  x2 －  x3 ＋ 2 x4 ≤ 14
            －2x1 ＋ 3x2 ＋  x3 －  x4 ≥ 2
            x1 ，x2 ，x3 ≥ 0，x4　无约束
2) min z ＝ 2x1 －2x2 ＋3x3
            － x1 ＋  x2 ＋ x3 ＝ 4
    st.        －2x1 ＋  x2 －  x3 ≤ 6
            x1≤0 ，x2 ≥ 0，x3无约束
1．2 用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。
1) minz＝2x1＋3x2
            4x1＋6x2≥6
    st  　2x1＋2x2≥4
            x1，x2≥0
2) maxz＝3x1＋2x2
            2x1＋x2≤2
    st  　3x1＋4x2≥12
            x1，x2≥0
3) maxz＝x1＋x2
            6x1＋10x2≤120
    st  　5≤x1≤10
            3≤x2≤8
4) maxz＝5x1＋6x2
            2x1－x2≥2
    st  －2x1＋3x2≤2
            x1，x2≥0           
1．3 出下述LP问题所有基解，指出哪些是基可行解，并确定最优解
（1）minz＝5x1－2x2＋3x3＋2x4
            x1＋2x2＋3x3＋4x4＝7
    st  　2x1＋2x2＋x3 ＋2x4＝3
            x1，x2，x3，x4≥0           
1．4 分别用图解法与单纯形法求解下列LP问题，并对照指出最优解所对应的顶点。
1) maxz＝10x1＋5x2
            3x1＋4x2≤9
    st    5x1＋2x2≤8
            x1，x2≥0           
2) maxz＝2x1＋x2
          3x1＋5x2≤15
    st  　6x1＋2x2≤24
            x1，x2≥0           
1．5 分别用大M法与两阶段法求解下列LP问题。
1)    minz＝2x1＋3x2＋x3
            x1＋4x2＋2x3≥8
    st    3x1＋2x2  ≥6
            x1，x2 ，x3≥0
2)  minz＝ 4x1＋x2
            3x1＋x2    　＝3
    st    4x1＋3x2　－x3  ＝6
x1＋2x2    ＋x4＝4
            x1，x2 ，x3，x4≥0
1．6 求下表中a～l的值。
cj
（a）
－1
2
0
0
CB
XB
b
x1
x2
x3
x4
x5
0
x4
6
（b）
（c）
（d）
1
0
0
x5
1
-1
3
（e）
0
1
j
（a）
-1
2
0
0
（a）
x1
（f）
［（g）］
2
-1
1/2
0
0
x5
4
（h）
（I）
1
1/2
1
j
0
-7
（j）
（k）
（l）
第二章 对偶与灵敏度分析
2．1  写出以下线性规划问题的DLP
1) minz＝2x1＋2x2＋4x3
            　x1＋3x2＋4x3　≥2
    st        2x1＋ x2＋3x3　≤3
            　x1＋4x2＋3x3　＝5
            x1，x2≥0，x3无约束
2) maxz＝5x1＋6x2＋3x3
            　x1＋2x2＋2x3　＝5
    st        －x1＋5x2－ x3　≥3
            4x1＋7x2＋3x3　≤8
            x1无约束，x2≥0，x3≤0
3) maxz＝c1x1＋c2x2＋c3x3
            a11x1＋a12x2＋a13x3 ≤b1
小型加工厂项目
    st        a21x1＋a22x2＋a23x3 ＝b2
            a31x1＋a32x2＋a33x3　≥b3
            x1≥0，x2≤0，x3无约束
2．2  对于给出的LP：
        minz＝2x1＋3x2＋5x3＋6x4
            　x1＋2x2＋3x3＋x4　≥2
    st        －2x1＋x2－x3＋3x4　≤－3
            　xj≥0 （j=1,2,3,4）
1) 写出DLP；
2) 用图解法求解DLP；
3) 利用2）的结果及根据对偶性质写出原问题的最优解。
2．3  对于给出LP：
        maxz＝x1＋2x2＋x3
            　x1＋　x2－　x3　≤2
    st        　x1－　x2＋　x3　＝1
            2x1＋　x2＋　x3　≥2
            x1≥0， x2≤0，x3无约束
1) 写出DLP；
2) 利用对偶问题性质证明原问题目标函数值Z≤1
2．4  已知LP：
        maxz＝x1＋x2
            －x1＋　x2＋　x3　≤2
    st        －2x1＋ x2－　x3　≤1
            　xj≥0
    试根据对偶问题性质证明上述线性问题目标函数值无界。
2．5  给出LP：
        maxz＝2x1＋4x2＋x3＋x4
            　x1＋ 3x2  　＋x4　≤8
            2x1＋  x2        ≤6
    st.  　x2 ＋　x3＋ x4≤6
              x1＋  x2 ＋　x3    ≤9
              xj≥0
1) 写出DLP；
2) 已知原问题最优解X＝（2,2，4,0），试根据对偶理论，直接求出对偶问题的最优解。
2．6  用对偶单纯形法求解下列线性规划问题
1) minz＝4x1＋12x2＋18x3               
            x1  　＋3x3  ≥3
    st          2 x2＋2x3　≥5         
            　xj≥0 (j=1,2,3)
2．7  考虑如下线性规划问题
    minz＝60x1＋40x2＋80x3
            3x1＋2x2＋ x3　≥2
    st        4x1＋ x2＋3x3　≥4
            2x1＋2x2＋2x3　≥3
            　xj≥0
1) 写出DLP；
2) 用对偶单纯形法求解原问题；
3) 用单纯形法求解其对偶问题；
4) 对比以上两题计算结果。
2．8  已知LP：maxz＝2x1－x2＋x3
                x1＋ x2＋ x3≤6
          st    　－x1＋2x2  ≤4
                x1，x2，x3≥0
1) 用单纯形法求最优解
2) 分析当目标函数变为maxz＝2x1＋3x2＋x3时最优解的变化；
3) 分析第一个约束条件右端系数变为3时最优解的变化。
2．9  给出线性规划问题
              maxz＝2x1＋3x2＋x3
                    1/3x1＋1/3x2＋1/3x3≤1
            st        1/3x1＋4/3x2＋7/3x3≤3
                    xj≥0
    用单纯形法求解得最终单纯形表如下
cj
2
3
1
0
0
CB
XB
B
x1
x2
x3
x4
X5
2
x1
1
1
0
－1
4
－1
3
x2
2
0
1
2
－1
1
j
0
0
－3
－5
－1
    试分析下列各种条件下，最优解（基）的变化：
1) 目标函数中变量x3的系数变为6；
2) 分别确定目标函数中变量x1和x2的系数C1、C2在什么范围内变动时最优解不变；
3) 约束条件的右端由    1    变为    2    ；
                        3            3
第三章 运输问题
3．1  根据下表，用表上作业法求最优解。
B1
B2
B3
B4
产量
A1
4
1
4
6
8
A2
1
2
5
0
8
A3
3
7
5
1
4
销量
6
5
6
3
20
3．2  根据下表，用表上作业法求最优解。
B1
B2
B3
B4
产量
A1
9
3
8
7
3
A2
4
9
4
5
3
A3
5
7
6
2
5
销量
1
3
2
5
11
3．3　　求给出的产销不平衡问题的最优解
B1
B2
B3
B4
产量
A1
5
12
3
4
8
A2
11
8
5
9
5
A3
9
7
1
5
9
销量
4
3
5
6
3.4 某市有三个面粉厂，他们供给三个面食加工厂所需的面粉，各面粉厂的产量、各面食加
工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均式于下表。假定在第1，2和3面食加工厂制作单位面粉食品的利润分别为12元、16元和11元，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）。
食品厂
面粉厂
1
2
3
面粉厂产值
1
2
3
3
4
8
10
11
11
2
8
4
20
30
20
销量
15
25
20
第四章　动态规划
4．1    现有天然气站A，需铺设管理到用气单位E，可以选择的设计路线如下图，B、C、D各点是中间加压站，各线路的费用如图所标注（单位：万元），试设计费用最低的线路。
 
4．2 一艘货轮在A港装货后驶往F港，中途需靠港加油、加淡水三次，从A港到F港全部可能的航运路线及两港之间距离如图，F港有3个码头F1，F2，F3，试求最合理停靠的码头及航线，使总路程最短。
4．3 某公司有资金4万元，可向A、B、C三个项目投资，已知各项目的投资回报如下，求最大回报。
项目
投资额及收益
0
1
2
3
4
A
0
41
48
60
66
B
0
42
50
60
66
C
0
64
68
78
76
4．4 某厂有1000台机器，高负荷生产，产品年产量S1与投入机器数Y1的关系为S1＝8Y1，机器完好率为0.7；低负荷生产，产品年产量S2与投入机器数Y2的关系为S2＝5Y2，机器完好率为0.9；请制定一个五年计划，使总产量最大。
4．5 某工厂生产三种产品，各种产品重量与利润关系如下表，现将此三种产品运往市场出售，运输能力总重量不超过6t，问应运输每种产品各多少件可使总利润最大。
产品
重量（t/件）
利润（千元/件）
1
2
80
2
3
130
3
4
180
4.6  用动态规划方法求解
第五章　存储论
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有关，具体如下表，求最佳订购策略。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。