a) Определите структуру выпускаемой продукции, при которой минимизируется время простоя всех трех линий.

b) Вычислите стоимость одного процента уменьшения времени профилактических работ для каждой линии.

2.4. КОМПЬЮТЕРНОЕ РЕШЕНИЕ ЗАДАЧ ЛП

Графический метод, описанный в разделе 2.2, основывается на некоторых фундаментальных свойствах оптимального решения задач ЛП. Но на практике, когда типичная задача линейного программирования содержит сотни и даже тысячи переменных и ограничений, графический метод неприменим. Здесь требуется использование компьютерных программ.

В этом разделе мы рассмотрим решение задач ЛП с помощью программы TORA, средства Excel Поиск решения, а также программ AMPL и LINGO. Программа TORA и средство Поиск решения предназначены для решения задач средних размеров. Для решения больших задач, содержащих сотни (и даже тысячи) ограничений и переменных, необходимо использовать коммерческие программы, такие как AMPL и LINGO.

2.4.1. Решение задач ЛП с помощью TORA

Ввод необходимых для решения задачи данных в программе TORA прост и понятен и не нуждается в дополнительных инструкциях. Поэтому в этом разделе мы основное внимание уделим интерпретации результатов, получаемых с помощью этой программы.

Пример 2.4.1

На рис. 2.9 показана выходная распечатка решения задачи ЛП для компании Reddy Mikks (пример 2.2.1), выполненная программой TORA. На примере этой неоднократно исследованной задачи проиллюстрируем решение, полученное с помощью программы TORA.

Выходные результаты программы разбиты на два основных раздела: числовые результаты решения задачи и данные анализа чувствительности (раздел Sensitivity Analysis). В первом разделе представлены оптимальные значения переменных (первая таблица) и значение целевой функции (Objective value). В рассматриваемом примере оптимальное значение переменной xt (количество выпускаемой краски для наружных работ) равно 3 т, а переменной х2 (количество выпускаемой краски для внутренних работ) - 1,5 т. Соответственно, доход составляет 21 ООО долл. В следующей таблице данного раздела представлены ограничения (Constraint). В этой таблице показаны значения дополнительных переменных, остаточных (Slack-), избыточных (Surplus+) и значения правых частей неравенств (столбец RHS4).

Из таблицы видно, что значения дополнительных переменных для первых двух неравенств равны нулю. Это означает, что сырье Ml и М2 потребляется полностью, без остатка. В третьем и четвертом ограничениях значения дополнительных переменных отличны от нуля, т.е. неравенства этих ограничений выполняются строго.

В верхней части раздела Sensitivity Analysis в двух таблицах показаны результаты анализа чувствительности при изменении по отдельности коэффициентов целевой

4 RHS - сокращение от Right Hand Side, т.е. правая сторона . - Прим. перев.

функции (первая таблица) и значений правых частей неравенств ограничений (вторая таблица). Например, текущее оптимальное решение сохраняется до тех пор, пока доход на тонну краски для внешних работ составляет от 2000 до 6000 долл. Текущее оптимальное решение также будет сохранено, если ежедневные поступления сырья Ml будут находиться в пределах от 20 до 36 тонн. Такой же результат получен графическим способом в примерах 2.3.1 и 2.3.2.

Теперь рассмотрим информацию, приведенную в столбцах Reduced Cost (Приведенная стоимость) и Dual Price (Двойственная цена) таблиц раздела Sensitivity Analysis.

Начнем с приведенной стоимости. С точки зрения экономиста, переменные в модели ЛП можно рассматривать как числовые характеристики интенсивности определенных видов деятельности (или процессов), в результате которых потребляются ресурсы ( вход модели) в целях получения прибыли ( выход модели). Из этой интерпретации вытекает следующее определение.

Если приведенная стоимость какого-либо процесса положительна, то отсюда следует, что стоимость потребленных ресурсов больше возможного дохода (все на единицу интенсивности процесса), поэтому такой процесс экономически не приемлем. Это обусловливает нулевое значение соответствующей переменной в оптимальном решении. Если же экономически привлекательный процесс имеет нулевую приведенную стоимость, то это означает, что достигнута точка равновесия, когда выход (единичный доход) равен входу (единичной стоимости ресурсов). В оптимальном решении, показанном на рис. 2.9, обе переменные хх и хг имеют положительные значения и нулевые приведенные стоимости.

Приведенная стоимость на4} (Стоимость потребленных4} (Доход иа единицу4

ресурсов на единицу - интенсивности интенсивности процесса у J процесса у ,

Теперь рассмотрим определение двойственной цены. Двойственная цена - это просто еще одно название стоимости единицы ресурсов, определенной в разделе 2.3.3. Она равна вкладу, который привносит в значение целевой функции изменение на одну единицу лимита, определяющего доступность ресурса. Термин двойственная цена произошел от названия проблема двойственности из теории линейного программирования (см. главу 4). Для обозначения стоимости единицы ресурсов такие термины, как теневая цена (shadow price) и симплексный мультипликатор (simplex multiplier), применяются значительно реже. Хотя название стоимость единицы ресурсов , введенное в разделе 2.3.3, лучше отображает смысл, вкладываемый в это понятие, мы все же будем использовать термин двойственная цена (dual price), так как он применяется во всех коммерческих программах решения задач ЛП.

На рис. 2.9 видно, что двойственные цены для сырья Ml и М2 равны соответственно 0,75 и 0,50 (т.е. 750 и 500 долл.) за тонну. Такие же результаты получены графическим способом в примере 2.3.3 и справедливы только при условии, что 20<М,<36 и 4<М2<20/3 (здесь через Мх и М2 обозначено количество сырья Ml иМ2 соответственно). Отсюда следует, что если, например, доступное количество сырья Ml возрастет от текущего уровня в 24 т до 28, то оптимальное значение целевой функции увеличится на 750 х (28 - 24) = 3000 долл. Но если доступное количество сырья Ml возрастет до 40 т (т.е. выйдет за интервал осуществимости), необходимо искать новое оптимальное решение.

единицу интенсивности процесса j

Title: Problem 2.5a-2

Final iteration No: 4

Objective value (max) =63000.0000

1 (<) 60000.0000 0.0000-

2(<) 2000.0000 1500.0000-

3 (<) 6000.0000 0.0000-

*** SENSITIVITY ANALYSIS *** Objective coefficients -- Single Changes:

Variable Current CoefF Min CoefF Max CoefF Reduced Cost

xl Juice 18.0000 0.0000 27.0000 0.0000

x2 Paste 9.0000 6.0000 infinity 0.0000

Right-hand Side - Single Changes:

Constraint Current RHS Min RHS Max RHS Dual Price

1 (<) 60000.0000 48000.0000 96000.0000 0.7500

2(<) 2000.0000 500.0000 infinity 0.0000

3(<) 6000.0000 1500.0000 7500.0000 3.0000

Objective Coefficients - Simultaneous Changes d:

Nonbasic Var Optimality Condition

sx3 0.7500+ 0.0417 dl >= 0

sx5 3.0000+ 1.0000d2+ -0.3333 dl >=0

Right-hand Side Ranging - Simultaneous Changes D:

Basic Var Value/Feasibilty Condition

x2 Paste 6000.0000+ 1.0000 D3>=0

xl Juice 500.0000 + 0.0417D1 + -0.3333 D3>=0

sx4 1500.0000+ -0.0417D1 + 1.0000 D2+ 0.3333 D3>=0

Рис. 2.9. Выходные результаты программы TORA

*** OPTIMUM SOLUTION SUMMARY ***