线性规划

一、线性规划的实例与意义

例1.1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4千元与3千元。生产甲机床需用 A 、 B 机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用 A 、 B 、 C 三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为4机器10小时、 B 机器8小时和 C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？

求最优解问题：
$$
max_z=4x_1+3x_2(1.1)
$$

$$
\begin{cases}2x_1+x_2\leq10\x_1+x_2\leq8\x_2\leq7\x_1,x_2\geq0\end{cases}(1.2)
$$

x1x2被称为决策变量，（1.1）式是目标函数，（1.2)中为约束条件。

matlab里一般求的是最小值，求最大值加负号即可

二、线性规划问题的解的概念

$$
min\quad c^{x}
$$

$$
s.t.\begin{cases}Ax\leq b(不等式约束)\Aeq\cdot x=beq（等式约束）\lb\leq x\leq ub（决策变量取值范围）\end{cases}
$$

c，x，b,beq,lb,ub为n维列向量，A、Aeq为矩阵,f为价值向量，b为资源向量

一般线性规划的数学标准型为：
$$
max\quad z=\sum\limits_{j=1}^nc_jx_j\quad (1.3)
$$

$$
s.t.\begin{cases}\sum\limits_{j=1}^n=b_i\quad i=1,2,…m\x_j\geq0\quad j=1,2,…,n\end{cases}\quad(1.4)
$$

可行解：满足(1.4)

最优解：使目标函数（1.3）达到最大值

可行域：所有可行解构成的集合

三、Matlab用来求解线性规划

1
2
3
4
5
6
7
8
%x返回决策向量的取值
%fval返回目标函数的最优解
c为价值向量
[x,fval]=linprog(c,A,b) %线性不等式约束
[x,fval]=linprog(c,A,b,Aeq,beq) %线性等式约束
[x,fval]=linprog(c,A,b,Aeq,beq,lb,ub) %上下界向量
%只能求最小值
%求最大值加负号

例1.2求解下列线性规划

(感觉只需要联想到线性代数的Ax=b即可)
$$
max\quad z=2x_1+3x_2-5x_3
$$

$$
s.t.\begin{cases}x_1+x_2+x_3=7\2x_1-5x_2+x_3\geq10\x_1+3x_2+x_3\leq12\x_1,x_2,x_3\geq0\end{cases}
$$

求解的Matlab程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
% 目标函数
f = [-2; -3; 5];
% 不等式约束
a = [-2, 5, 1; 1, 3, 1];
b = [-10; 12];
% 等式约束
aeq = [1, 1, 1];
beq = 7;
% 使用 linprog 函数求解
[x, y] = linprog(f, a, b, aeq, beq, zeros(3, 1));
%zeros(3, 1)被用作 linprog 函数的一个参数，用来指定决策变量x的下界为零
% 输出最优解和最优值
disp('最优解 x:');
disp(x);

disp('目标函数的最小值 y:');
disp(y);

% 目标函数的最大值
max_y = -y;
disp('目标函数的最大值 -y:');
disp(max_y);

四、转化为线性规划

image.png