在一个城市交通系统中取出一段如下图所示, 其入口为顶点 $v_1$, 出口为顶点 $v_8$. 每条弧段旁的数字表示通过该路段所需的时间. 每次转弯需要附加时间为 3 秒.

求 $v_1$ 到 $v_8$ 的最短时间路径.

求下图中每一结点到其他结点的最短路.

某公司在六个城市 $C_1,C_2,C_3,C_4,C_5,C_6$ 中都有分公司. 从 $C_i$ 到 $C_j$ 的直达航班票价由下述矩阵的第 $i$ 行、第 $j$ 列元素给出 ($\infty$ 表示无直达航班).

该公司希望计算出一张任意两个城市之间最廉价路线表, 试作出这样的表来.

\[
\begin{pmatrix}
0 & 50 & \infty & 40 & 25 & 10\\
50 & 0 & 15 & 20 & \infty & 25\\
\infty & 15 & 0 & 10 & 20 & \infty\\
40 & 20 & 10 & 0 & 10 & 25\\
25 & \infty & 20 & 10 & 0 & 55\\
10 & 25 & \infty & 25 & 55 & 0\\
\end{pmatrix}
\]

钢管下料问题

某钢管零售商从钢管厂进货, 将钢管按照顾客的要求切割出售.

从钢管厂进货得到的原材料钢管的长度都是 1850mm.

现在一顾客需要15根 290mm、 28根315mm、21根 350mm、 30根455mm 的钢管.

为了简化生产过程, 规定所使用的切割模式的种类不能超过 4 种, 使用频率最高的一种切割模式按照一根原料钢管价值的 $\frac{1}{10}$ 增加费用, 使用频率次之的切割模式按照一根原料钢管价值的 $\frac{2}{10}$ 增加费用, 以此类推, 且每种切割模式下的切割次数不能太多(一根原料钢管最多生产 5 根产品). 此外, 为了减少余料浪费, 每种切割模式下的余料浪费不能超过 100mm.

为了使总费用最小, 应该如何下料?

【分析】

为了更好地理解问题, 将一些数据组织成表格的形式.

Remark:

这里的切割模式是指将单根标准钢管(即钢厂生产出的钢管)按照某种长度组合切割的方式. 比如

\[
[290,290,290,290,290,290,110]
\]

就是一种切割模式, 这里不管其排列顺序, 也就是说 $[290,110,290,290,290,290,290]$ 和刚才的 $[290,290,290,290,290,290,110]$ 属于同一种切割模式

某厂向用户提供发动机, 合同规定: 第一、二、三季度末分别交货 40 台、60 台、80 台.

每季度的生产费用为 $f(x)=ax+bx^2$ (元), 其中 $x$ 是该季度生产的发动机台数.

若交货后有剩余, 可用于下季度交货, 但需支付存储费, 每台每季度 $c$ 元.

已知工厂每季度最大生产能力为 100 台, 第一季度开始时无存货.

设 $a=50$, $b=0.2$, $c=4$, 问工厂应如何安排生产计划, 才能既满足合同又使总费用最低?

讨论 $a,b,c$ 变化对计划的影响, 并作出合理的解释.

为便于理解, 将题中的信息列出如下:

已知某工厂计划生产 I、II、III 三种产品, 各产品需要在 $A, B, C$ 设备上加工, 有关数据如下:

试回答:

(1) 如何发挥生产能力, 使每月的生产盈利最大?

(2) 若为了增加产量, 可借用别的工厂设备 $B$, 每月可借用 $60$ 台时, 租金 $1.8$ 万元, 借用设备 $B$ 是否合算?

(3) 若另有两种新产品 IV、V, 其中

• 新产品 IV 需用设备 $A$ 12 台时、 $B$ 5 台时、$C$ 10 台时, 单位产品盈利 $2.1$ 千元；
• 新产品 V 需用设备 $A$ 4 台时、 $B$ 5 台时、$C$ 12 台时, 单位产品盈利 $1.87$ 千元；

     如 $A,B,C$ 的设备台时不增加, 这两种新产品投产在经济上是否合算?

(4) 对产品工艺重新进行设计, 改进结构. 改进后生产每件产品 I 需要设备 $A$ 9 台时、设备 $B$ 12 台时、设备 $C$ 4 台时, 单位产品盈利 $4.5$ 千元, 这时对原计划有何影响?

某工厂制造三种产品, 生产这三种产品需要三种资源:

• 技术服务
• 劳动力
• 行政管理

下表列出了三种单位产品对每种资源的需要量:

现有 $100h$ 的技术服务, $600h$ 的劳动力和 $300h$ 的行政管理时间可使用, 求最优产品品种规划, 且回答下列问题:

(1) 若产品 III 值得生产的话, 它的利润是多少? 假使将产品 III 的利润增加至 $\frac{25}{3}$ 元, 求获利最多的产品品种规划.

(2) 确定全部资源的影子价格.

(3) 制造部门提出建议, 要生产一种新产品, 该产品需要技术服务 $1h$、劳动力 $4h$ 和行政管理 $4h$. 销售部门预测这种产品售出时有 $8$ 元的单位利润. 管理部门应有怎样的决策?

(4) 假定该工厂至少生产 $10$ 件产品 III, 试确定最优产品品种规划.

有两个煤厂 $A,B$, 每月进煤分别不少于 $60t$, $100t$. (单位: $t$ 指吨). 它们担负供应三个居民区的用煤任务, 这三个居民区每月需要用煤分别为 $45t$, $75t$, $40t$.

$A$ 厂离这三个居民区分别为 $10\textrm{km}$, $5\textrm{km}$, $6\textrm{km}$.

$B$ 厂离这三个居民区分别为 $4\textrm{km}$, $8\textrm{km}$, $15\textrm{km}$.

问这两煤厂如何分配供煤, 才能使总运输量最小?

某工厂生产 $A_1$, $A_2$ 两种型号的产品都必须经过零件装配和检验两道工序, 如果每天可用于零件装配的工时只有 100h，可用于检验的工时只有 120h, 各型号产品每件需占用各工序时数和可获得的利润如下表所示:

(1) 试写出此问题的数学模型, 并求出最优生产方案.

(2) 对产品 $A_1$ 的利润进行灵敏度分析.

(3) 对装配工序的工时进行灵敏度分析.

(4) 如果工厂试制了 $A_3$ 型产品, 每件 $A_3$ 产品需装配工时 4h, 检验工时 2h, 可获利润 5 元, 那么该产品是否应投入生产?

某医院负责人每日至少需要下列数量的护士:

每班的护士在值班开始时向病房报到, 连续工作 8 个小时.

医院领导为满足每班所需要的护士数, 最少需雇佣多少护士?