GWJ的个人小站

整数规划

问题描述

1、某公司生产A、B、C 3种产品，售价分别为12元、7元、6 元。生产每件A需1h技术服务、10h直接劳动、3kg材料; 生 产每件B需2h技术服务、4h直接劳动、2kg材料; 生产每件 C 需 1h 技术服务、5h直接劳动、1kg材料。现在最多能提供100 h技术服务、700h直接劳动、400kg材料。生产成本如下表， 求建立一个总利润最大的生产计划数学模型。

$$\begin{array}{|c|c|c|c|c|} \hline & \text { 技术服务 } / \mathrm{h} & \text { 直接劳动 } / \mathrm{h} & \text { 材料 } / \mathrm{kg} & \text { 售价/元 } \\ \hline \mathrm{A} & 1 & 10 & 3 & 12 \\ \hline \mathrm{B} & 2 & 4 & 2 & 7 \\ \hline \mathrm{C} & 1 & 5 & 1 & 6 \\ \hline \end{array}$$

$$\begin{array}{|c|c|c|c|c|c|} \hline \text { 产品 } \mathrm{A} \text { 产量 (件) } & \text { 成本 (元/件) } & \text { 产品 } \mathrm{B} \text { 产量 (件) } & \text { 成本 (元/件) } & \text { 产品 } \mathrm{C} \text { 产量 (件) } & \text { 成本 (元/件) } \\ \hline 0 \sim 40 & 10 & 0 \sim 50 & 6 & 0 \sim 100 & 5 \\ \hline 41 \sim 100 & 9 & 51 \sim 100 & 4 & 100 \text { 以上 } & 4 \\ \hline 101 \sim 150 & 8 & 100 \text { 以上 } & 3 & & \\ \hline 150 \text { 以上 } & 7 & & & & \\ \hline \end{array}$$

求解

假设A、B、C的生产量分别为$ x_1 $，$ x_2 $，$ x_3 $，那么总售价$w=12x_1+7x_2+6x_3$。

根据题设条件写出相应的目标函数与约束条件如下：

\begin{align*} &\text{目标函数：} \max w=12x_1+7x_2+6x_3 \\ \\ &\text{约束条件：} \left\{\begin{array}{c} x_1+2x_2+x_3\leq1000\quad\left(1\right)\\ 10x_1+4x_2+5x_3\leq700\quad\left(2\right)\\ 3x_1+2x_2+x_3\leq400\qquad\left(3\right)\\ x_1,x_2,x_3\in N \end{array}\right. \end{align*}

由于$x_1$，$x_2$，$x_3$取值不同时，对应的成本是不一样的。因此需要一一分段讨论，过于复杂。为了简化计算，我们先通过一定方式，把$x_1$，$x_2$，$x_3$的范围进行初步确定。

假设全部生产A产品，则由约束条件可得：A产品数量最多不超过70件。

同理，B产品数量不超过50件；C产品数量不超过100件。

成本即可表示为：

$$\left\{\begin{array}{c} 10x_1+6x_2+5x_3\qquad(0\leq x_1\leq 40)\\ 9x_1+6x_2+5x_3+40\qquad(41\leq x_1\leq 70)\\ \end{array}\right.$$

因此

$$\max w= \left\{\begin{array}{c} 12x_1+7x_2+6x_3-\left(10x_1+6x_2+5x_3\right)\qquad(0\leq x_1\leq 40)\\ 12x_1+7x_2+6x_3-\left(9x_1+6x_2+5x_3-40\right)\qquad(41\leq x_1\leq 70)\\ \end{array}\right.$$

化简得

$$\max w= \left\{\begin{array}{c} 2x_1+x_2+x_3\qquad(0\leq x_1\leq 40)\qquad\\ 3x_1+x_2+x_3-40\qquad(41\leq x_1\leq 70)\qquad\\ \end{array}\right.$$

分别解得

$$\left\{\begin{array}{c} x_1=40\\ x_2=0\\ x_3=60\\ w=140 \end{array}\right. \quad\quad\quad \left\{\begin{array}{c} x_1=70\\ x_2=0\\ x_3=0\\ w=170 \end{array}\right.$$

整理后得到生产方案

$$\begin{array}{|c|c|c|c|} \hline \text { 产品 } \mathrm{A} / \text { 件 } & \text { 产品 } \mathrm{B} / \text { 件 } & \text { 产品 } \mathrm{C} / \text { 件 } & \text { 利润/元 } \\ \hline 70 & 0 & 0 & 170 \\ \hline \end{array}$$

问题描述

求解

设一个决策变量$x_{ij}$来表示第$i$个仓库是否建立：

$$\left\{\begin{array}{l} x_i=1\qquad \text{第$i$个仓库建立}\\ x_i=0\qquad \text{第$i$个仓库不建立}\\ \end{array}\right.$$

其中$$\sum_{i=1}^{3}x_i=2,x_i\in{0,1}$$

由于建设投资费用要分摊到10年回收，则每年的建设投资费用可记为：

$$\frac{1}{10}\sum\limits_{i=1}^{3}x_ik_i$$

设$y_{ij}$表示第$i$个仓库对第$j$个用户每年提供的物资。

则依题意每年的:

物资调用费用：$\sum\limits_{i=1}^{3}\sum\limits_{j=1}^{4}x_iy_{ij}c_{ij}$

周转保管费用：$\sum\limits_{i=1}^{3}\sum\limits_{j=1}^{4}x_iy_{ij}P_i$

为了满足用户需求，有：$\sum\limits_{i=1}^{3}x_{i}y_{ij}=D_j$

受最大容量的限制，有：$\sum\limits_{j=1}^{4}x_{i}y_{ij}\leq A_i$

综合各个条件，建立最终模型如下：

\begin{align*} &\text{目标函数：} \min \sum_{i=1}^{3}\sum_{j=1}^{4}x_iy_{ij}\left(c_{ij}+P_i\right)+\frac{1}{10}\sum_{i=1}^{3}x_iK_i \\ \\ &\text{约束条件：} \left\{\begin{array}{l} \sum\limits_{i=1}^{3}x_i=2,\quad x_i\in\{0,1\}\\ \sum\limits_{i=1}^{3}x_iy_{ij}=D_j\\ \sum\limits_{j=1}^{4}x_iy_{ij}\leq A_i\\ \end{array}\right. \end{align*}