Решение задачи о компьютерах перебором (максимум – стоимость)
На рис. 6.34 и 6.35 приведено решение задачи о компьютерах методом перебора. В программах реализовано три вложенных цикла – по числу типов компьютеров, максимальное количество которых подсчитать несложно: 62 штуки – С2 (лимит по комплектующему №3), 20 – С3 (по №2) и 12 – С4 (по №4). Важное замечание! В программах фиксируются все планы выпуска компьютеров, максимизирующие их число (120 штук) или стоимость (875 600 у.е. – эту цифру можно определить предварительно, отыскивая один план из многих возможных). Что дал перебор и чего не дал бы другой метод решения задачи целочисленного линейного программирования? Оказывается, планов выпуска 120 штук компьютеров целых 156. Можно выпускать не только 100 первых и 20 третьих типов компьютеров (решение, найденное на рис. 6.33), но и 75, 25, 15 и 5. Стоимость компьютеров при этом увеличивается с 560 000 у.е. до 782 500 (см. последний, 155-й столбец).
Функция Maximize «спрятала» от пользователя оптимальный план. Более того, если на рис. 6.33 в качестве начального приближения дать оптимальное первое приближение (75, 25, 15 и 5), то Maximize упорно вернет старый результат – 100, 0, 20 и 0 компьютеров.
На рис. 6.34 выведены первые и последние столбцы матрицы План, содержащей все 156 планов выпуска компьютеров общим числом 120, но с разной стоимостью: от 560000 у.е. (100, 0, 20 и 0 компьютеров разного типа) до782 500 у.е. (75, 25, 15 и 5 компьютеров).
Еще более интересное решение получается при максимизации стоимости компьютеров (рис. 6.35). Дело в том, что при решении задач линейного программирования, как правило, оперируют только неотрицательными значениями переменных (см. ограничение С ³ 0 на рис. 6.33). Но при С1<0 задача может быть сформирована с таким дополнением: «Купи на стороне компьютеры первого типа, разбери их, а дефицитные детали пусти на производство более дорогих машин». Стоимость компьютеров даже с учетом расходов на приобретение машин первого типа может быть выше, чем при традиционном решении. Так и получилось – см. рис. 6.35: матрица План содержит только 2 столбца с «нормальным» решением (1-й столбец: 1, 60, 5 и 10 компьютеров и 4-й столбец: 1, 56, 3 и 11 компьютеров). Максимальная стоимость (883 800 у.е.) получается тогда, когда на стороне покупается 27 компьютеров первого типа.
Метод перебора становится незаменим в том случае, когда задача о компьютерах перестает быть линейной. А это случается, если поставщик комплектующих делает скидку при покупке оптом. Такая динамика изменения цен нами статистически обработана – см. рис. 4.15.
