Результаты решения этой задачи ЛП представлены на рис. 2.22. Отметим, что в оптимальном решении общее количество автобусов равно 26, при этом *, = 4, х2 = 10, хг = 0, xt = 8, хъ = 4 и х6 = 0. Приведенные стоимости всех переменных равны нулю; это указывает на альтернативные оптимальные решения (но с тем же значением целевой функции).
Интерес представляет информация о рассчитанных двойственных ценах. Двойственная цена, равная 1, показывает, что увеличение правой части соответствующего неравенства на единицу увеличивает общее количество автобусов также на единицу. Если двойственная цена равна нулю, то увеличение значения правой части соответствующего неравенства не приводит к возрастанию общего числа используемых автобусов. Однако эти утверждения справедливы только тогда, когда значения правых частей неравенств не выходят за пределы соответствующих интервалов (значения в столбцах Min RHS и Max RHS последней таблицы отчета на рис. 2.22).
LINEAR PROGRAMMING OUTPUT SUMMARY
Title: Bus Sceduling Model, Example 2.5-3 Final Iteration No.: 10 Objective Value = 26
Variable | Value | Obj Coeff | Obj Val Contrib | |
x1:12:01AM | 4,00 | 1,00 | 4,00 | |
x2: 4:01AM | 10,00 | 1,00 | 10,00 | |
x3: 8:01AM | 0,00 | 1,00 | 0,00 | |
x4: 12:01PM | 8,00 | 1,00 | 8,00 | |
x5: 4:01PM | 4,00 | 1,00 | 4,00 | |
x6: 8:01PM | 0,00 | 1,00 | 0,00 | |
Constraint | | Slack-/Surplus+ | | |
1(>) | 4,00 | 0,00 | | |
2(>) | 8,00 | 6,00+ | | |
3(>) | 10.00 | 0,00 | | |
4(>) | 7,00 | 1,00+ | | |
5(>) | 12,00 | 0,00 | | |
6(>) | 4,00 | 0,00 | | |
| | "Sensitivity Analysis | | |
Variable | Current Obj Coeff | Min Obj Coeff | Max Obj Coeff | Reduced Cost |
x1: 12:01AM | 1,00 | 0,00 | 1,00 | 0,00 |
x2: 4:01AM | 1,00 | 0,00 | 1,00 | 0,00 |
x3: 8:01AM | 1,00 | 1,00 | infinity | 0,00 |
x4:12:01PM | 1,00 | 1,00 | 1,00 | 0,00 |
x5: 4:01PM | 1,00 | 1,00 | 1,00 | 0,00 |
x6: 8:01PM | 1,00 | 1,00 | infinity | 0,00 |
Constraint | Current RHS | Min RHS | Max RHS | Dual Price |
K>) | 4,00 | 0,00 | infinity | 1,00 |
2(>) | 8,00 | -infinity | 14,00 | 0,00 |
3(>) | 10,00 | 4,00 | infinity | 1,00 |
4(>) | 7,00 | -infinity | 8,00 | 0,00 |
5(>) | 12,00 | 11,00 | infinity | 1,00 |
6(>) | 4,00 | 0,00 | 5,00 | 0,00 |
Рис. 2.22. Выходной отчет программы TORA для задачи составления расписания движения автобусов
Например, правая часть второго неравенства может возрасти от 8 до 14 без увеличения общего количества используемых автобусов. А увеличение на какое-либо значение правой части третьего неравенства (начиная со значения 10 и выше) приводит к такому же увеличению общего количества автобусов. Эта информация очень важна для анализа оптимального решения.
Анализ чувствительности коэффициентов целевой функции в данном случае не имеет особого смысла, поскольку в этой модели они могут иметь только значение 1. Если бы целевая функция отражала какую-нибудь другую "цель" (например, минимизировала бы стоимость эксплуатации автобусов), тогда ситуация могла быть иной и анализ этих коэффициентов имел бы смысл.
Пример 2.5.4. Минимизация потерь при разрезании рулонов бумаги
Тихоокеанская бумажная фабрика производит стандартные рулоны бумаги шириной в 20 футов. Специальные заказы клиентов требуют разрезания стандартных рулонов. Типовой заказ (такие заказы могут меняться каждый день) приведен в следующей таблице.
Позиции заказа | Требуемая ширина рулона (футы) | Требуемое количество рулонов (шт.) |
| | |
| | |
| | |
На фабрике заказы выполняются путем разрезания специальными ножами стандартных рулонов на требуемые. Существует несколько вариантов деления стандартного рулона, три из которых показаны на рис. 2.23. Конечно, существуют и другие варианты, не показанные на этом рисунке (они будут описаны ниже), но сейчас мы ограничимся только представленными. Для выполнения заказа можно совместно использовать несколько вариантов разрезки стандартных рулонов. Например, для выполнения заказа, приведенного в таблице, можно применить следующие комбинации вариантов 1, 2 и 3.
1. Разрезать 300 стандартных рулонов, используя вариант 1, и 75 рулонов с помощью варианта 2.
2. Разрезать 200 стандартных рулонов, используя вариант 1, и 100 рулонов с помощью варианта 3.
Какая из этих комбинаций лучше? Чтобы ответить на этот вопрос, надо рассмотреть потери от каждой из них. На рис. 2.23 серым цветом показаны отходы бумаги после каждого варианта разрезки. Мы можем оценить преимущества каждой комбинации, если подсчитаем суммарные отходы, полученные после их применения. Но, поскольку отрезки рулонов, идущие в отходы, имеют разную длину, нам надо подсчитать объем этих отходов, а не просто количество отрезков. Предполагая, что стандартный рулон бумаги имеет площадь поперечного сечения, равную L квадратным футам, подсчитываем потери для комбинаций 1 и 2.
Комбинация 1: 300х(4 xL) + 75х(3 xL) = 1425L куб. футов.
Комбинация 2: 200х(4 xL) + 100х(1 xL) = 900L куб. футов.
2.5. Примеры моделей ЛП 20
7 -i- 9 . , .4.
Вариант 1
Вариант 2
Вариант 3
Рис. 2.23. Варианты разрезки стандартных рулонов (размеры даны в футах )
Если число рулонов шириной 5, 7 или 9 футов, которые были получены в результате применения какой-либо комбинации вариантов разрезки, превышает количество, необходимое для выполнения заказа, то разность между ними также следует отнести к потерям. В первой комбинации при использовании варианта 1 получено 300 -- 200 = 100 лишних рулонов шириной 7 футов; применение варианта 2 добавляет еще 75 лишних рулонов такой же ширины. Таким образом, дополнительные потери составляют 175x(7xL)= 1225L куб. футов. Комбинация 2 не производит лишних рулонов шириной 7 и 9 футов, но применение варианта 3 приводит к появлению 200 - 150 = 50 лишних рулонов шириной 5 футов, что составляет 50 х (5 х L) = 250L куб. футов дополнительных отходов бумаги. В результате этих выкладок имеем следующее.
Объем отходов от комбинации 1 = 1425L + 1225L = 2650L куб. футов.
Объем отходов от комбинации 2 = 900L + 250L = 1150L куб. футов.
Очевидно, что комбинация 2 лучше, так как имеет меньше отходов.
Для получения оптимального решения данной задачи необходимо определить все допустимые варианты разрезки стандартных рулонов и затем получить все возможные комбинации этих вариантов. Хотя определить все допустимые варианты разрезки несложно, перебор всех комбинаций этих вариантов уже является нетривиальной задачей. Здесь необходим систематический подход к организации такого перебора. В данном случае это поможет выполнить модель линейного программирования.
Математическая модель. Мы должны найти комбинацию вариантов разрезки (переменные), с помощью которой можно было бы. выполнить заказ (ограничения) с минимальными отходами бумаги (целевая функция).
Переменные надо определить таким образом, чтобы их значения можно было интерпретировать в способ разрезки стандартных рулонов бумаги. Поэтому определим переменные как количество стандартных рулонов, разрезанных с помощью конкретных вариантов. Это определение требует описать все возможные варианты разрезки. Три варианта показаны на рис. 2.23, остальные приведены в следующей таблице. Убедитесь, что не пропущены еще какие-нибудь варианты разрезки, при этом помните, что в допустимом варианте разрезки ширина остатка стандартного рулона должна быть меньше 5 футов.