算法：线性规划

原理：线性规划问题如果有最优解，则最优解一定在可行域的边界上取得，特别地，一定在可行域的顶点上取得。

算例：

(题目来源：http://wenku.baidu.com/link?url= ... FzYJrA_eVeNY70YIFL3)

某厂生产三种产品I，II，III。每种产品要经过A B ,两道工序加工。设该厂有两种规格的设备能完成A工序，它们以A1，A2表示；有三种规格的设备能完成B工序，它们以B1,B2,B3表示。产品I可在BA任何一种规格设备上加工。产品II可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品III只能在A2与B2设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如表1，求安排最优的生产计划，使该厂利润最大。

表1

设     备        产       品        设备有效台时        满负荷时的 设备费用(元)

Ⅰ        Ⅱ        Ⅲ

A1        5        10                6000        300

A2        7        9        12        10000        321

B1        6        8                4000        250

B2        4                11        7000        783

B3        7                        4000        200

原料费(元/件)        0.25        0.35        0.50

单  价(元/件)        1.25        2.00        2.80

解：

如图设出未知数：  (i=1,2,3,4,5,6,7,8)

设     备        产       品        设备平均费用

Ⅰ        Ⅱ        Ⅲ

A1        X1        X6                0.05

A2        X2        X7        X8        0.0321

B1        X3        X6+X7                0.0625

B2        X4                X8        783/7000

B3        X5                        0.05

则目标函数为max z=( + )*1+(   + )*1.65+ *2.3-(0.25* ＋0.2247* ＋0.375* ＋0.4476* ＋0.35* ＋0.5* ＋0.2889* ＋0.5*(   + )＋1.6161* )

约束条件为：

+  - - - =0；

5* +10* <6000；

7* +9* +12* <10000；

*6+( + )*8<4000；

*4+ *11<7000；

*7<4000

在matlab中编写线性规划程序知结果为：

x =

1.0e+03 *

1.2000

0.2300

0.0000

0.8586

0.5714

0.0000

0.5000

0.3241

z =

-1.1464e+03

取整后结果如下表即应按下表生产：

设     备        产       品

Ⅰ        Ⅱ        Ⅲ

A1        1200        0

A2        230        500        324

B1        0        500

B2        859                324

B3        571

最大值为1146.45元

计算程序：

clear

clc

f=[-0.75 -0.7753 0.375 0.4476 0.35 -0.65 -0.8611 -0.6844];

Aeq=[1 1 -1 -1 -1 0 0 0];

beq=[0];

A=[5 0 0 0 0 10 0 0

0 7 0 0 0 0 9 12

0 0 6 0 0 8 8 0

0 0 0 4 0 0 0 11

0 0 0 0 7 0 0 0];

b=[6000 10000 4000 7000 4000];

vlb=zeros(8,1);

vub=[];

[x,z]=linprog(f,A,b,Aeq,beq,vlb,vub)

word文件下载点击下载链接