1（i）使用两阶段方法来找到以下直线的最佳解决方案：

x1 + x2≤5
3×1 + 2×2≥6。

（ii）使用对偶单纯形法找到问题的最佳解决方案
（i）部分所述。 （10分）

2 CompanyMmix四种成分和一个装填器一起生产营养粉。这

ent）的每种成分都在此表中给出：
A（克/千克）B（克/千克）C（克/千克）成本（英镑/千克）

•根据行销法规，如果M公司要声明

ents。一公斤粉末中的营养素最小值为5克
ent A，B为7克，C为4克。
•CompanyMintend声称该粉末含有至少两种营养素。

•M公司计划混合5000公斤粉末。
•如果使用成分2或成分4，则固定安装成本为300英镑。
•两种成分的化学特性均满足以下条件：

•CompanyM从P公司购买成分1和2。

•淀粉用作填充物。它的营养成分和成本可以忽略不计。

1(I) shǐyòng liǎng jiēduàn fāngfǎ lái zhǎodào yǐx

1 (i) Use the two-phase method to ﬁnd the optimal solution for the following lin-
ear programming problem:
max z = −2×1 − 4×2
subject to x1, x2 ≥ 0 and
x1 + x2 ≤ 5,
3×1 + 2×2 ≥ 6.
State clearly your ﬁnal optimal solution.
Hint: not counting the preprocessing step, you need only one simplex
iteration in phase 1. (15 marks)
(ii) Use the dual simplex method to ﬁnd the optimal solution for the problem
stated in Part (i). (10 marks)

2 CompanyMmixes four ingredients and a ﬁller to produce a nutritional powder. The
powder contains three nutrients: A, B and C. The nutrient contents (unit: grams per
kilogram of the ingredient) and the costs (unit: pounds per kilogram of the ingredi-
ent) of each ingredient are given in this table:
A (g/kg) B (g/kg) C (g/kg) Cost (£/kg)
Ingredient 1 1 8 4 4
Ingredient 2 2 1 5 6
Ingredient 3 7 4 1 8
Ingredient 4 2 6 2 5
The following information is known:
• According to marketing regulations, if company M wants to claim that the
powder contains a nutrient, then the amount of that nutrient must be no less
than a minimum value. The minimum value is different for different nutri-
ents. In one kilogram of the powder, the minimum value is 5 grams for nutri-
ent A, 7 grams for B, and 4 grams for C.
• CompanyMintends to claim that the powder contains at least two nutrients.
They have no preference for which ones.
• Company M plans to mix 5000 kilograms of the powder.
• A ﬁxed set-up cost of £300 is incurred if either ingredient 2 or 4 are used.
• The chemical properties of the ingredients are such that, if both ingredients 1
and 3 are used, then ingredient 2 cannot be used.
• CompanyMpurchases ingredient 1 and 2 from company P. Due to proﬁtabil-
ity considerations, company P does not accept small orders. Therefore, com-
pany M can purchase either no less than 100 kilograms of ingredient 1 alone,
or no less than 120 kilograms of ingredient 2 alone, or no less than 290 kilo-
grams of the two ingredients combined.
• Starch is used as the ﬁller. Its nutritional contents and cost can be neglected.
There is no separate constraint on how much it should be used.
Let x1, x2, x3, and x4 be the amounts (in kilograms) of the four ingredients in 1
kilogram of the powder. Formulate the mixed integer linear programming problem
from which one can ﬁnd the optimal solution to minimise the total cost. Note: do
NOT try to ﬁnd the numerical solution of the problem; youmay need to introduce
more variables. (25 marks)