Требуемая ширина | | | Варианты | | | Требуемое количество |
(футы) | | | | | | | рулонов |
| | | | | | | |
| | | | | | | |
| | | | | | | |
Остаток (футы) | | | | | | | |
Теперь можно определить переменные: дгу - количество стандартных рулонов, разрезанных вариантом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
Variable | Value | Obj Coeff | Obj Val Contrib | |
x1: stngl | 0,00 | 1,00 | 0,00 | |
x2: stng2 | 0,00 | 1,00 | 0,00 | |
x3: stng3 | 0,00 | 1,00 | 0,00 | |
x4: stng4 | 12,50 | 1,00 | 12,50 | |
x5: stng5 | 100,00 | 1,00 | 100,00 | |
x6: stng6 | 150,00 | 1,00 | 150,00 | |
Constraint | | Slack-/Surplus+ | | |
K>) | 150,00 | 0,00 | | |
2(>) | 200,00 | 0,00 | | |
3(>) | 300,00 | 0,00 | | |
| | "Sensitivity Analysis | It** | |
Variable | Current Obj Coeff | Min Obj Coeff | Max Obj Coeff | Reduced Cost |
x1: stngl | 1,00 | 0,88 | infinity | -0,12 |
x2: stng2 | 1.00 | 0,88 | infinity | -0,12 |
x3: stng3 | 1,00 | 1,00 | infinity | 0,00 |
x4: stng4 | 1,00 | 0,00 | 1,00 | 0,00 |
x5: stng5 | 1,00 | 0,25 | 1,25 | 0,00 |
x6: stng6 | 1,00 | 0,00 | 1,00 | 0,00 |
Constraint | Current RHS | Min RHS | Max RHS | Dual Price |
1 (>) | 150,00 | 100,00 | infinity | 0,25 |
2(>) | 200,00 | 0,00 | 300,00 | 0,38 |
3(>) | 300,00 | 0,00 | infinity | 0,50 |
Рис. 2.24. Выходной отчет программы TORA для задачи разрезания рулонов бумаги
При интерпретации результатов, полученных с помощью программы TORA, следует учитывать требование целочисленности значений переменных, которое неявно присутствует в данной задаче. Например, двойственная цена 0,25, соответствующая первому ограничению, показывает, что увеличение на 1 количества заказных рулонов шириной 5 футов потребует дополнительно еще четверти стандартного рулона (шириной 20 футов). Но эта информация в данном случае не имеет практического смысла. Ее нужно переформулировать следующим образом (исходя из условия целочисленности): потребуется дополнительный стандартный рулон при увеличении на 4 единицы количества заказных рулонов шириной 5 футов. Подобные изменения следует внести при интерпретации других двойственных цен.
УПРАЖНЕНИЯ 2.5
1. Вернитесь к задаче из примера 2.5.1 (модель банковских инвестиций) и ее решению, приведенному на рис. 2.19.
а) Рассмотрим таблицу, в которой приведены результаты анализа чувствительности правых частей неравенств ограничений. Объясните, почему
минимальное и максимальное значения интервала изменений величины правой части первого неравенства равны соответственно 4,8 и 12 млн. долл.
b) Предположим, что банк решил вложить все 12 млн. долл. в сельскохозяйственные и коммерческие кредиты. Вычислите чистую прибыль банка.
c) Предположим, что объем капитала, предназначенного для инвестиций, возрос до 20 млн. долл., а лимит на сельскохозяйственные и коммерческие кредиты увеличился до 9 млн. долл. Будет ли новое оптимальное решение включать только кредиты на покупку жилья и коммерческие кредиты? Найдите это новое оптимальное решение.
2. Вернитесь к примеру 2.5.2 (модель освоения и использования земли). Предположим, что компания Birdeyes может купить дополнительные 100 акров земли за 450 ООО долл. Используя результаты анализа чувствительности по этой задаче (см. рис. 2.20), подскажите компании, стоит ли покупать эту землю.
3. Вернитесь к задаче из примера 2.5.3 (составление расписания движения автобусов). На основе оптимального решения, представленного на рис. 2.22, определите оптимальное количество используемых автобусов, предполагая, что минимальные потребности в автобусах для шести 4-часовых периодов (см. рис. 2.22) составляют, во-первых, (4, 12, 10, 7, 12, 4) и, во-вторых, (4, 8, 7, 7, 12, 4).
4. Вернитесь к примеру 2.5.4 (задача минимизации потерь при разрезании рулонов бумаги) и ее оптимальному решению, показанному на рис. 2.24.
a) Определите потери бумаги при разрезании 200 стандартных рулонов по варианту 1 и 100 стандартных рулонов - по варианту 2.
b) Предположим, что ширина стандартного рулона равна 15 футам. Определите возможные варианты разрезки на рулоны шириной 5, 7 и 9 футов и укажите потери бумаги при использовании каждого варианта.
c) В исходной задаче (со стандартными рулонами шириной 20 футов) поступил новый заказ, где потребность в рулонах шириной 7 футов уменьшилась до 80 штук, а необходимое число рулонов другой ширины (5 и 9 футов) осталось неизменным. Сколько стандартных рулонов необходимо для выполнения нового заказа?
d) В исходной задаче требуемое количество рулонов шириной 9 футов возросло до 400 штук. Сколько дополнительных стандартных рулонов необходимо для выполнения такого заказа?
5. Нефтедобывающая компания, расположенная на острове Аруба, добывает 600 000 баррелей сырой нефти в день. Нефтеперерабатывающий завод производит два вида неэтилированного бензина: рядовой и высококачественный. Процесс нефтепереработки включает три стадии: 1) перегонка сырой нефти на перегонной колонне - на выходе бензиновый полуфабрикат, 2) часть полуфабриката поступает на крекинг-установку, где производится бензиновый дистиллят, 3) смесительная установка смешивает полуфабрикат, полученный на выходе перегонной колонны, и бензиновый дистиллят. Как рядовой, так и высококачественный бензин, можно получить на основе либо бензинового полуфабриката, либо бензинового дистиллята (это зависит от того, что является основой смеси в смесительной установке), но стоимость таких видов бензина будет разной. Компания подсчитала, что чистая прибыль от одного барреля рядового бензина составляет 7,70 и 5,20 долл., в зависимости от того, будет ли основой бензина полуфабрикат или дистиллят. Аналогичная