Решение с помощью прог раммы Excel

Чтобы получить целочисленное решение задачи линейного программиро­вания с помощью программы Excel, к обычным ограничениям задачи добавля­ются условия целочнсленности. Это можно сделать в окне Добавление огра­ничения, вид которого для нашего примера (см. раздел 1.1) показан на рис. 2.2.

В поле Ссылка на ячейки (Ссылка на ячейку) задается диапазон ячеек содержащих значения переменных, а в раскрывающемся списке вместо знака выбирается один из следующих пунктов:

• цел — целое число;

в бин в Excel 2010 (или двоич в предыдущих версиях)— бинарное (двоичное) число 0 или 1;

• раз (только в Excel 2010) — разные целые числа от 1 до N (где N — число переменных).

При этом в поле Ограничение автоматически появляется слова: целое, би­нарное (двоичное) или Все разные.

Если переменные в модели — разных типов (целые, бинарные, разные це­лые, вещественные), можно задать несколько условий целочнсленности, для каждого типа переменных в отдельности.

Поскольку нахождение целочисленного решения зачастую является до­вольно длительной процедурой, предусмотрена возможность ее ускорения. Для этого используются следующие параметры, задаваемые в Excel 2010 в окне Па­раметры (см. рис. 1.26), а в предыдущих версиях — в окне Параметры поис­ка решения (см. рис. 1.27) (названия параметров, используемые в предыдущих версиях, даны в скобках):

• Игнорировать целочисленные ограничения (только в Excel 2010) —

Добавление ограничения

Ссылка на ячеикм:

ГШ

Ограничение:

ок

Отмена

Добавить

Рис. 2.2. Добавление требования целочнсленности переменных

флажок, установка которого приводит к решению задачи без учета условий це­лочисленное™.

1.98. Целочисленная оптимальность (Допустимое отклонение)— ука­зывает, на сколько процентов полученное значение целевой функции может от­личаться от оптимального (по умолчанию в Excel 2010 — 1%, а в предыдущих версиях — 5%). Для ускорения можно увеличить это значение. Если же необ­ходимо получить точное решение, то следует установить этот параметр равным 0%, но это может значительно увеличить время оптимизации,

1.99. Максимальное время — позволяет задать в секундах максимальное время, которое отводится на поиск решения (значение по умолчанию в Excel 2010 не задано, а в предыдущих версиях— 100 секунд).

1.100. Число итераций (Предельное число итераций) — позволяет опре­делить максимальное количество итераций при поиске решения (значение по умолчанию в Excel 2010 не задано, а в предыдущих версиях— 100). Для цело­численных моделей данный параметр указывает максимальное количество ите­раций для каждой подзадачи.

1.101. Максимальное число подзадач (только в Excel 2010)— позволяет задать максимальное количество подзадач при целочисленном решении.

1.102. Максимальное число допустимых решений (только в Excel 2010) — позволяет определить максимальное количество рассматриваемых допустимых целочисленных решений.

Если вы задали некоторые из перечисленных предельных значений, то по­иск решения будет продолжаться до тех пор, пока какое-нибудь нз них не будет достигнуто. Тогда появится окно с предложением остановить вычисления или продолжить. Если вы решили продолжить вычисления, достигнутое предельное значение отменяется н расчеты продолжаются до достижения следующего нз заданных предельных значений. Если вы выбрали вариант остановки вычисле­ний, появится окно с сообщением о том, что решение остановлено по запросу пользователя и на листе окажутся результаты, достигнутые на этот момент. Прервать вычисления можно также нажатием клавиши Esc. При этом также появляется окно с предложением остановить пли продолжить вычисления.

Остальные ограничения и параметры поиска решения — те же, что и для обычной задачи линейного программирования (см. раздел 1.3). Выполнив вы­числения с условием целочнсленности, показанным на рис. 2.2, вы получите целочисленное решение нашей задачи (5; 1; 3, 4).

Глава 3