Методические указания Петрозаводск Издательство Петрозаводского университета 1998 (стр. 2 из 4)

В клетку J11 занесем формулу, значением которой должна быть ожидаемая в результате реализации оптимального решения прибыль:

=СУММПРОИЗВ(G5 : G9 ; I5 : I9)

Значение этой формулы есть значение целевой функции задачи.

Одному из листов электронной таблицы присвойте имя “Модель”. На этом листе будут размещены формулы, соответствующие левым частям ограничений модели. Поскольку значения ограничений при поиске решения наблюдать не обязательно, они размещаются в том месте, где они не видны пользователю, например, на другом листе. Пояснительные тексты и формулы, размещаемые на листе “Модель”, показаны на рисунке 2.

Примечание: в некоторых версиях табличного процессора Excel все сведения, относящиеся к модели, должны размещаться на одном и том же листе.

Рис. 2. Пояснительные тексты и формулы, размещаемые на листе электронной таблицы с именем “Модель”.

Для формирования условий оптимизационной задачи и поиска оптимального решения необходимо инициировать работу оптимизационного блока Excel с помощью команды меню “Сервис, Поиск решения...”. В результате на экране появится окно “Поиск решения”.

Далее необходимо проделать следующее. В поле окна “Установить целевую ячейку” указать адрес ячейки, значение которой используется в качестве критерия оптимизации - в нашем случае это ячейка J11. Имя ячейки можно ввести вручную или же, сделав описываемое поле активным, указать мышкой нужную ячейку электронной таблицы. Необходимое условие - целевая ячейка обязательно должна содержать формулу, значение которой зависит от изменяемых ячеек, соответствующих переменным задачи. Рядом с целевой ячейкой необходимо установить признак вида оптимизации (максимум или минимум целевой функции или ее равенство некоторому значению, которое в этом случае требуется указать).

В поле “Изменяя ячейки” необходимо указать область ячеек, соответствующих переменным задачи. В нашем случае этой областью будет диапазон K5:K9. При нажатии кнопки “Предположить” в рассматриваемом поле будут указаны все ячейки, связанные с формированием значения целевой функции, что не всегда удобно (например, в нашем случае вместе с клетками K5:K9 будут указаны клетки G5:G9, соответствующие коэффициентам целевой функции, считающимся константами в ходе поиска решения).

Замечание: ссылки на ячейки в полях окна “Поиск решения” автоматически становятся абсолютными.

Ограничения задачи указываются в поле “Ограничения”. Для задания ограничения требуется указать ячейку, соответствующую левой части ограничения, тип ограничения - “не больше”, “не меньше”, “равно”, “целое” (последнее только по отношению к ячейкам переменных), и ячейку или числовое значение левой части ограничения.

Новое ограничение формируется при нажатии кнопки “Добавить...”, вследствие чего открывается окно “Добавление ограничения”, позволяющее задать местонахождение правой и левой части очередного ограничения и характер связи между ними.

Для рассматриваемой нами задачи необходимо определить 14 ограничений, приводимых ниже:

1. $K$5 : $K$9 = целое

2. Модель!$A$3 <= $D$11 Ограничение на площадь посевов

3. Модель!$A$5 <= $D$12 Ограничения на трудовые ресурсы

4. Модель!$A$7 <= $D$13 Ограничение на трудовые ресурсы в напряжен- ный период

5. $J$5 >= $B$5 Группа ограничений на объемы производства

6. $J$6 >= $B$6 продукции (не менее, не более)

7. $J$7 >= $B$7

8. $J$8 >= $B$8

9. $J$9 >= $B$9

10. $J$5 <= $C$5

11. $J$6 <= $C$6

12. $J$7 <= $C$7

13. $J$8 <= $C$8

14. $J$9 <= $C$9

При нажатии кнопки “Добавить” в окне “Добавить ограничение” сформированное ограничение будет добавлено к условиям задачи и станет возможным задание следующего без возврата в окно “Поиск решения”.

Сформировав все параметры задачи, выполните ее решение, нажав на кнопку “Выполнить”. Согласно требованиям Excel изменяемые в процессе поиска оптимального решения ячейки (соответствующие переменным задачи) обязательно должны располагаться на активном листе электронной таблицы. Поэтому в момент нажатия кнопки “Выполнить” текущим должен быть лист “Пользователь”.

Сравните полученное решение с оптимальным, которое приведено на рис. 1. Если они совпадают, значит, Вы все сделали правильно.

4. Параметры поиска решения

Иногда, после формирования модели, приходится уточнять параметры метода решения задачи. Для получения такой возможности следует нажать кнопку “Параметры...”, в результате чего открывается окно “Параметры поиска решения”.

С помощью данного окна можно уточнить некоторые параметры используемого метода решения. Изменять стандартные установки целесообразно лишь в том случае, если Вы достаточно хорошо разбираетесь в методах математического программирования. В большинстве случаев при решении задач небольшой размерности вполне подходят стандартные установки.

Тем не менее дадим краткие пояснения смысла некоторых параметров.

“Максимальное время” определяет предельное время поиска решения (не более 32767 секунд). Если в течение указанного времени оптимальное решение не будет найдено, процесс поиска прерывается и следует запрос о необходимости продолжить или прекратить решение задачи. В последнем случае Вы получите некоторое промежуточное, возможно, недопустимое решение.

“Итерации”. Процесс поиска оптимального решения носит пошаговый, итеративный характер (не более 32767 итераций). Решение, получаемое в ходе очередной итерации, основывается на полученном при выполнении предыдущей. При исчерпании числа итераций процесс поиска решения прерывается (см. предыдущий пункт).

Время решения и требуемое число итераций зависят от начальных значений переменных. Чем ближе они к оптимальным, тем быстрее будет получено решение.

“Относительная погрешность”. Данное поле должно содержать число из интервала (0, 1). Точность определяет близость полученного значения целевой функции оптимальному. Чем больше точность (т.е. чем ближе указанное число к нулю), тем большее число итераций и большее время требуется для поиска оптимального решения.

“Допустимое отклонение” определяет допуск на отклонение от оптимального решения, если на переменные наложено условие целочисленности.

Из остальных возможностей стоит отметить лишь пункт “Линейная модель” - линейность всегда стоит указывать явно, поскольку это позволяет в несколько раз сократить время решения задачи и, скорее всего, получить более точный ответ.

Кнопки “Сохранить модель...” и “Загрузить модель...” позволяют сохранять параметры сформированной модели в какой-либо области электронной таблицы.

Более детальные пояснения Вы можете получить из документации на Excel 7.0 или пользуясь справочной системой Excel.

Задание: обнулите значения переменных (клетки K5:K9), установите признак линейности и снова выполните поиск решения. Теперь он займет гораздо меньше времени.

5. Задания для самостоятельной работы

Предлагаемые ниже задания подобраны таким образом, чтобы при их выполнении требовалось как знание ряда классических задач математического программирования, так и некоторых специальных приемов, используемых при построении математических моделей, относящихся к задачам линейного (ЛП) и смешанного целочисленного программирования (СЦЛП). Все задания подобраны таким образом, чтобы при построении модели была возможность остаться в рамках задач ЛП или СЦЛП (для этих классов задач математического программирования разработаны и используются наиболее эффективные методы решения). Поэтому все построенные Вами модели должны относиться к задачам указанных классов.

В большинстве заданий сначала приводится наиболее простой вариант задачи, близкий к классической постановке, а затем указываются дополнительные условия, которые делают данную задачу нетривиальной.

После построения математических моделей и решения задач каждого задания необходимо подготовить отчет, который должен содержать:

- перечень использованных обозначений с пояснениями смысла каждого обозначения;

- модель задачи в общем виде с пояснениями смысла каждого соотношения;

- модель задачи, сформулированная на основе тех конкретных исходных данных, которые указаны в задании. Все соотношения модели должны быть записаны в развернутом виде и иметь пояснения;

- результат решения задачи с конкретными исходными данными (значения переменных и целевой функции).

Реализация задачи в среде электронной таблицы должна быть удобной для работы пользователя. Исходные данные и результаты расчета необходимо расположить удобным для пользователя образом, убрав, по возможности, все вспомогательные формулы в другую область листа или на другой лист. При изменении исходных данных задачи, не связанных с изменением ее размерности, не должна требоваться перенастройка модели или каких-либо формул.

5.1. Задача оптимального распределения ресурсов

На мебельной фабрике изготавливаются пять видов продукции: столы, шкафы, диван-кровати, кресла-кровати и тахты. Нормы затрат ресурсов: труда, древесины и ткани на производство единицы продукции каждого вида приведены в следующей таблице:

Наименование pесурса	Расход ресурса на единицу продукции (в указанных единицах измерения)					Запас pесурса
	стол	шкаф	диван-кровать	кресло-кровать	тахта
Трудозатраты (чел.-ч.)	4	8	12	9	10	3690
Древесина (м3)	0.4	0.6	0.3	0.2	0.3	432
Ткань (м)	0	0	6	4	5	2400
Прибыль от выпуска 1 изделия (у.е.)	8	10	16	13	17	-
Предельный объем выпуска (шт.)	480	80	180	120	100	-

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