Задача о компьютерах

Если с первым решением все ясно (можно изготовить максимум 120 компьютеров; какой стоимостью и в каком раскладе — мы еще обсудим), то второе нужно дорабатывать: цифры плана выпуска компьютеров следует округлять. Дело в том, что функция Maximize не умеет возвращать решение задачи целочисленного линейного программирования, и мы уже на это посетовали (см. рис. 3.17). Не совсем умеют ее решать и специально созданные для этих целей программы — вспомним, как в среде Excel решалась задача о краске (см. рис. 3.21).

Целочисленное решение, максимизирующее количество компьютеров, получилось, можно сказать, случайно.

Ничего не остается делать, как прибегать к методу перебора. Именно он использован для решения задачи о компьютерах, которое приведено на рис. 3.24 и 3.25. В программах реализованы три вложенных цикла— по числу типов компьютеров, максимальное количество которых подсчитать несложно: 62 штуки — С2 (лимит по комплектующему № 3), 20 — сз (по № 2) и 12 — С4 (по №4).

Примечание

В программах фиксируются все планы выпуска компьютеров, максимизирующие их число (120 штук) или стоимость (875 600 у. е. — эту цифру можно определить предварительно, отыскивая один план из многих возможных).

Что дал перебор и чего не дал бы другой метод решения задачи целочисленного линейного программирования? Оказывается, планов выпуска 120 штук компьютеров целых 156. Можно выпускать не только 100 первых и 20 третьих типов компьютеров (решение, найденное на рис. 3.23), но и 75, 25, 15 и 5. Стоимость компьютеров при этом увеличивается с 560 000 до 782 500 у. е. (см. последний, 155-й столбец на рис. 3.24).

Функция Maximize "спрятала" от пользователя оптимальный план. Более того, если на рис. 3.23 в качестве начального приближения дать оптимальное первое приближение (75, 25, 15 и 5), то Maximize упорно вернет старый результат — 100, 0, 20 и 0 компьютеров.

На рис. 3.24 выведены первые и последние столбцы матрицы план, содержащей все 156 планов выпуска компьютеров общим числом 120, но с разной стоимостью: от 560 000 у. е. (100, 0, 20 и 0 компьютеров разного типа) до 782 500 у. е. (75, 25, 15 и 5 компьютеров).

Рис. 3.24. Решение задачи о максимальном числе компьютеров

Еще более интересное решение получается при максимизации стоимости компьютеров (рис. 3.25). Дело в том, что при решении задач линейного программирования, как правило, оперируют только неотрицательными значениями переменных (см. ограничение с>0 на рис. 3.23). Но при ско задача может быть сформирована с таким дополнением: "Купи на стороне компьютеры первого типа, разбери их, а дефицитные детали пусти на производство более дорогих машин".

Рис. 3.25. Решение задачи о максимальной стоимости компьютеров

Стоимость компьютеров даже с учетом расходов на приобретение машин первого типа может быть выше, чем при традиционном решении. Так и получилось— см. рис. 3.25: матрица План содержит только 2 столбца с "нормальным" решением (нулевой столбец: 1, 60, 5 и 10 компьютеров и 3-й столбец: 1, 56, 3 и 11 компьютеров). Максимальная стоимость (883 800 у. е.) получается тогда, когда на стороне покупается 27 компьютеров первого типа.

Метод перебора становится незаменим в том случае, когда задача о компьютерах перестает быть линейной. А это случается, если поставщик комплектующих делает скидку при покупке оптом, например.

Но, как правило, метод перебора должен сочетаться с аналитическими методами — с "мозговой", а не "компьютерной" атакой. Яркий пример такого сочетания— решения задачи о минимальном (оптимизация!) числе красок для раскраски политической карты мира, например. Суть задачи в том, что соседние государства не должны быть окрашены в один цвет.

Ясно, что трех красок для этого будет мало. А достаточно ли четырех?! Ответ на этот "топографический" вопрос был найден так. Сначала "мозговой атакой" было доказано, что все, даже самые замысловатые границы можно свести к ограниченному числу типов карт, а потом на компьютере простым перебором эти "типичные типы" были раскрашены с использованием только четырех цветов. Но до сих пор в разных научно-популярных журналах публикуются "замысловатые" контурные (незакрашенные) карты с утверждением, что их нельзя закрасить четырьмя красками. Но потом оказывается, что это были первоапрельские шутки.

Метод перебора находится как бы в некотором динамическом равновесии. С одной стороны, растет быстродействие компьютеров, что расширяет применимость этого метода. Но и сложность решаемых задач (число независимых переменных и их разброс) также меняется...