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 футов.

Теперь можно определить переменные: дгу - количество стандартных рулонов, разрезанных вариантомj,j = 1, 2, 6.

Ограничение в этой модели заключается в том, что произведенных рулонов заданных размеров (5, 7 и 9 футов) должно быть достаточно для выполнения заказа. Если использовать все варианты разрезки, приведенные в таблице, то получим, что

количество рулонов шириной 5 футов = 2х2 + 2х3 + 4jc4 + ха,

количество рулонов шириной 7 футов = дг, + х2 + 2хй,

количество рулонов шириной 9 футов =х1+х3 + 2х6.

Эти числа должны быть не меньше 150, 200 и 300 соответственно.

Для построения целевой функции заметим, что общий объем отходов можно подсчитать как разность между объемом всех использованных стандартных рулонов и объемом рулонов, необходимых для выполнения заказа. Запишем это следующим образом:

объем использованных стандартных рулонов = 20Ддг, + х2 + х3 + хА + хъ + х6),

объем заказных рулонов = Ц150 х 5 + 200 х 7 + 300 х 9) = 4750L.

Поскольку объем рулонов, необходимых для выполнения заказа, постоянен, а также постоянна величина поперечного сечения L, целевую функцию можно записать просто как сумму всех переменных: г = дг, + х2 + х3 + хА + хъ + х6.

Таким образом, получаем следующую задачу линейного программирования. Минимизировать z = дг, + х2 + хг + xt + дг5 + х6

при выполнении условий

2дг2 + 2дг3 + 4xt + дг5 > 150 (ограничение на рулоны шириной 5 футов), хх+х2+ 2хъ > 200 (ограничение на рулоны шириной 7 футов), дг, + дг3 + 2д:6 > 300 (ограничение на рулоны шириной 9 футов), x>0,j=l,2, -.б.

Оптимальное решение этой задачи, представленное на рис. 2.24, показывает, что задача имеет и другие оптимальные решения, где для выполнения того же заказа используется такое же количество рулонов стандартной длины, но применяются другие варианты разрезки. В приведенном решении 12,5 стандартных рулонов разрезаются в соответствии с вариантом 4, 100 стандартных рулонов - в соответствии с вариантом 5, а 150 стандартных рулонов- с вариантом 6. В таком виде это решение нельзя реализовать, так как значение переменной дг4 нецелое. В этой ситуации можно применить к данной задаче алгоритм целочисленного программирования (см. главу 9) или округлить значение переменной дг4 до 13.

LINEAR PROGRAMMING OUTPUT SUMMARY

Title: Trim Loss Model, Example 2.5-4 Final Iteration No.: 7 Objective Value = 262.5

Рис. 2.24. Выходной отчет программы TORA для задачи разрезания рулонов бумаги

При интерпретации результатов, полученных с помощью программы TORA, следует учитывать требование целочисленности значений переменных, которое неявно присутствует в данной задаче. Например, двойственная цена 0,25, соответствующая первому ограничению, показывает, что увеличение на 1 количества заказных рулонов шириной 5 футов потребует дополнительно еще четверти стандартного рулона (шириной 20 футов). Но эта информация в данном случае не имеет практического смысла. Ее нужно переформулировать следующим образом (исходя из условия целочисленности): потребуется дополнительный стандартный рулон при увеличении на 4 единицы количества заказных рулонов шириной 5 футов. Подобные изменения следует внести при интерпретации других двойственных цен.

УПРАЖНЕНИЯ 2.5

1. Вернитесь к задаче из примера 2.5.1 (модель банковских инвестиций) и ее решению, приведенному на рис. 2.19.

а) Рассмотрим таблицу, в которой приведены результаты анализа чувствительности правых частей неравенств ограничений. Объясните, почему